5 ms·

I don't understand what you mean by "leak" here. Again, not a crypto expert, but my understanding is that all stream ciphers leak some bits of the key with eno

I don't understand what you mean by "leak" here. Again, not a crypto expert, but my understanding is that all stream ciphers leak some bits of the key with enough output. This is why differential cryptanalysis is possible against them. This is also why RC4 could be broken. EDIT: Perhaps a better algorithm: Accumulate 128 bits of entropy and use that to key Salsa20. Then, whenever another 128 bits are accumulated, simply re-key the stream cipher.

tptacek 3y ago
It’s why RC4 is broken, not a thing we accept from ciphers that aren’t comically broken.
- stcredzero 3y ago
  Isn't that a matter of degree? RC4 leaks a lot. "Acceptable" ciphers leak so little, it's still not feasible to break the full version. But apparently this scales with increasing or reducing rounds. So it seems unlikely it ever goes to zero. It just gets near enough to zero, that there are no feasible attacks for some length of message.
  - tptacek 3y ago
    No, it's not. A reasonable cryptanalytical model of a modern stream cipher (AED in a stream mode, or Salsa20, or whatever) is that --- within the birthday bounds of the underlying cipher (exabytes? you'd look it up, whatever you're using), and, in the case of something like an AEAD (or maybe just in the idiosyncratic case of GCM), the bounds of your nonce width --- they're not leaking _anything_. "Comical" really is the right word to use with respect to what RC4 did. It is kind of amazing that a cipher that broken remained in common use for as long as it did.
    - stcredzero 3y ago
      within the birthday bounds of the underlying cipher (exabytes? So modern stream ciphers do leak, just so slowly, it shouldn't ever matter in a practical sense if you're using them correctly? That was more or less my understanding to begin with, but maybe expressed ineptly. the bounds of your nonce width --- they're not leaking _anything_ This reminds me of unicity distance. So under a certain number of outputs, one simply can't infer the internal state of the algorithm? It could be any number of internal states? That makes sense to me.
      - tptacek 3y ago
        I don't think "leak" is the right way to think about it. There's are birthday bounds on the transform and, for nonce-based modes, on the nonces used for successive encryptions. I'm not sure it's really meaningful to think about the incremental marginal degree of "leakage" with each successive ciphertext up to that limit. We're coming up to the limit of what I'm comfortable talking about though; this is normally the point where 'pbsd jumps in to explain why what I'm saying is dumb.
adrian_b 3y ago
The term "stream cipher" is much more general than how you understand it. There is a huge number of stream ciphers that have never been broken. There is also a great number of stream ciphers that have been broken, but almost all of them belong to a class of ciphers that deserves the name "cheap stream ciphers". Such "cheap stream ciphers" have been designed so that they can have a much cheaper implementation than the ciphers that are based on pseudorandom functions similar in complexity to DES and its successors, with the hope that despite being cheaper they will still be hard enough to break. In most cases, sooner or later these hopes have been shown to be unfounded. The term "stream cipher" just means that it encrypts a stream of plaintext symbols by combining a stream of encryption mask symbols with them. There are many kinds of stream ciphers based on how the stream of encryption mask symbols are generated and based on the methods used to combine them with the plaintext. Even if more general combination functions are possible when the only condition is to be able to decrypt the ciphertext, when an additional condition is imposed, that the statistical properties of the plaintext must not leak into the ciphertext, then the encryption mask symbols must be combined with the plaintext symbols using a quasigroup operation (a.k.a. a Latin square operation). Most frequently, it is preferred that the quasigroup operation is a group operation, because this makes it simpler to implement. Moreover, usually it is preferred that the group operation is an additive group operation, to have an even cheaper implementation. Such stream ciphers are called additive stream ciphers. When implemented in software, there are many additive group operations with equal complexity. However, when the encryption is implemented in hardware, addition modulo 2 is the cheapest so it is preferred. The use of addition modulo 2 as a combination method has been invented by Gilbert S. Vernam in 1918. The term "binary additive stream cipher" should have been synonymous with "Vernam cipher". Unfortunately, in another example of mistaken historical attribution, the term "Vernam cipher" is used to mean any stream cipher where the encryption mask stream is truly random, which is a different invention, first described by Frank Miller in 1882 and rediscovered and popularized by Joseph Mauborgne, a user of Vernam machines. Based on how the encryption mask stream is generated, there are many kinds of stream ciphers, but most of the practical stream ciphers are either synchronous stream ciphers, where the initial state and the transition function and the output function of the automaton that generates the encryption mask symbols do not depend on the plaintext or on the ciphertext, and self-synchronizing stream ciphers, where the encryption mask symbols are generated either as a pseudorandom function of the ciphertext symbols (these are a.k.a. ciphertext autokey stream ciphers) or as a pseudorandom function of the plaintext symbols (these are a.k.a. plaintext autokey stream ciphers; they have been abandoned a long time ago, because they are less secure). The two kinds of self-synchronizing stream ciphers are dual, i.e. starting from one such cipher a dual cipher is obtained by using the encryption algorithm for decryption and the decryption algorithm for encryption. The stream ciphers that are most frequently used nowadays are binary additive synchronous stream ciphers, but there is a great variety of possible structures for the automaton that generates the encryption mask symbols. When implemented in software on a modern CPU, the simplest such automaton is made by using AES in counter mode (CTR mode).

tptacek 3y ago

It’s why RC4 is broken, not a thing we accept from ciphers that aren’t comically broken.

stcredzero 3y ago
Isn't that a matter of degree? RC4 leaks a lot. "Acceptable" ciphers leak so little, it's still not feasible to break the full version. But apparently this scales with increasing or reducing rounds. So it seems unlikely it ever goes to zero. It just gets near enough to zero, that there are no feasible attacks for some length of message.
- tptacek 3y ago
  No, it's not. A reasonable cryptanalytical model of a modern stream cipher (AED in a stream mode, or Salsa20, or whatever) is that --- within the birthday bounds of the underlying cipher (exabytes? you'd look it up, whatever you're using), and, in the case of something like an AEAD (or maybe just in the idiosyncratic case of GCM), the bounds of your nonce width --- they're not leaking _anything_. "Comical" really is the right word to use with respect to what RC4 did. It is kind of amazing that a cipher that broken remained in common use for as long as it did.
  - stcredzero 3y ago
    within the birthday bounds of the underlying cipher (exabytes? So modern stream ciphers do leak, just so slowly, it shouldn't ever matter in a practical sense if you're using them correctly? That was more or less my understanding to begin with, but maybe expressed ineptly. the bounds of your nonce width --- they're not leaking _anything_ This reminds me of unicity distance. So under a certain number of outputs, one simply can't infer the internal state of the algorithm? It could be any number of internal states? That makes sense to me.
    - tptacek 3y ago
      I don't think "leak" is the right way to think about it. There's are birthday bounds on the transform and, for nonce-based modes, on the nonces used for successive encryptions. I'm not sure it's really meaningful to think about the incremental marginal degree of "leakage" with each successive ciphertext up to that limit. We're coming up to the limit of what I'm comfortable talking about though; this is normally the point where 'pbsd jumps in to explain why what I'm saying is dumb.

adrian_b 3y ago

The term "stream cipher" is much more general than how you understand it. There is a huge number of stream ciphers that have never been broken. There is also a great number of stream ciphers that have been broken, but almost all of them belong to a class of ciphers that deserves the name "cheap stream ciphers". Such "cheap stream ciphers" have been designed so that they can have a much cheaper implementation than the ciphers that are based on pseudorandom functions similar in complexity to DES and its successors, with the hope that despite being cheaper they will still be hard enough to break. In most cases, sooner or later these hopes have been shown to be unfounded. The term "stream cipher" just means that it encrypts a stream of plaintext symbols by combining a stream of encryption mask symbols with them. There are many kinds of stream ciphers based on how the stream of encryption mask symbols are generated and based on the methods used to combine them with the plaintext. Even if more general combination functions are possible when the only condition is to be able to decrypt the ciphertext, when an additional condition is imposed, that the statistical properties of the plaintext must not leak into the ciphertext, then the encryption mask symbols must be combined with the plaintext symbols using a quasigroup operation (a.k.a. a Latin square operation). Most frequently, it is preferred that the quasigroup operation is a group operation, because this makes it simpler to implement. Moreover, usually it is preferred that the group operation is an additive group operation, to have an even cheaper implementation. Such stream ciphers are called additive stream ciphers. When implemented in software, there are many additive group operations with equal complexity. However, when the encryption is implemented in hardware, addition modulo 2 is the cheapest so it is preferred. The use of addition modulo 2 as a combination method has been invented by Gilbert S. Vernam in 1918. The term "binary additive stream cipher" should have been synonymous with "Vernam cipher". Unfortunately, in another example of mistaken historical attribution, the term "Vernam cipher" is used to mean any stream cipher where the encryption mask stream is truly random, which is a different invention, first described by Frank Miller in 1882 and rediscovered and popularized by Joseph Mauborgne, a user of Vernam machines. Based on how the encryption mask stream is generated, there are many kinds of stream ciphers, but most of the practical stream ciphers are either synchronous stream ciphers, where the initial state and the transition function and the output function of the automaton that generates the encryption mask symbols do not depend on the plaintext or on the ciphertext, and self-synchronizing stream ciphers, where the encryption mask symbols are generated either as a pseudorandom function of the ciphertext symbols (these are a.k.a. ciphertext autokey stream ciphers) or as a pseudorandom function of the plaintext symbols (these are a.k.a. plaintext autokey stream ciphers; they have been abandoned a long time ago, because they are less secure). The two kinds of self-synchronizing stream ciphers are dual, i.e. starting from one such cipher a dual cipher is obtained by using the encryption algorithm for decryption and the decryption algorithm for encryption. The stream ciphers that are most frequently used nowadays are binary additive synchronous stream ciphers, but there is a great variety of possible structures for the automaton that generates the encryption mask symbols. When implemented in software on a modern CPU, the simplest such automaton is made by using AES in counter mode (CTR mode).