Stream ciphers
in [Cryptography]
|
Prev: Nothing is Hid – All will be revealed-2
Next: Cryptography Researcher: Increase Your Research Productivity with the Leading Web 2.0 Research Portal
From: Ivan Voras on 29 Dec 2009 17:50 On 29.12.2009 23:00, Thomas Pornin wrote: > According to Ivan Voras <ivoras(a)gmail.com>: >> Is there some fundamental problem that prohibits designing some other >> classes of stream ciphers, for example in which incoming data would be >> mixed with/permutated by key data and internal state byte by byte and >> then some result of this mixing is outputted byte by byte (modifying >> the internal state while passing through)? > > It has been done. The stream cipher which was incorporated in the ZIP > archive format was such a system; that specific cipher turned out to > be quite weak, but not because of its state-machine structure. Thanks for the pointer! > However, stream ciphers which produce a pseudo-random stream, to be > XORed with the data to encrypt, are easier to build and analyze: there > is much less need for reversibility, and the analysis can be performed > without needing to model the input data itself. From an implementation > point of view, it may also help a bit, since much of the computation can > be performed by chunks, outside of the main data processing path. For > these reasons, stream cipher designers tend to favour the PRNG+XOR > model. I'd guess they would be no more complicated to analyze than block ciphers (and probably similarly complex to create), or would they?
From: Maaartin on 29 Dec 2009 18:07 On Dec 29, 11:42 pm, Ivan Voras <ivo...(a)gmail.com> wrote: > I am thinking about big flipping and key / keystream reuse. You must NEVER reuse the key. This is usually acomplished by dividing the "whole key" in two parts: The master key (called simply key) and the nonce. The master key may stay the same and must be kept secret, the nonce may never repeat and may be implemented simply as a counter. For example, Salsa20 uses a 256 bit key and 64 bit nonce. Mixing the plaintext into the internal state could help a bit in case of repeating the "whole key", but it always leaks some information. At least with two ciphertexts c1 and c2, which happen to be equal, you know the plaintexts are equal too. My question: What are the most interesting stream ciphers working not by simple xoring?
From: Greg Rose on 29 Dec 2009 18:42 In article <hhe0nk$g75$1(a)sunce.iskon.hr>, Ivan Voras <ivoras(a)gmail.com> wrote: >On 29.12.2009 22:40, unruh wrote: >> On 2009-12-29, Ivan Voras <ivoras(a)gmail.com> wrote: >>> Hi, >>> >>> I'm not an expert but it looks like the canonical description of a >>> stream cipher boils down to "a PRNG which generates a keystream, which >>> is XOR-ed with plaintext to produce the ciphertext". This has some >>> obvious downsides mostly caused by the XOR step. >> >> This has an obvious downside why? The xor step has no downside. > >I am thinking about bit flipping and key / keystream reuse. Bit flipping is an attack against message integrity and must be defeated by a message integrity check of some kind. There are also serious attacks against block ciphers without message integrity, and even if you had some more complicated combination funtion, there would still be integrity attacks unless you directly prevent them. Also any block cipher mode that uses an IV or nonce will have attacks if the nonce is repeated. (Any that don't, eg. ECB, is already weak). So, since you already need non-repeating nonces and message integrity, the simplicity of a stream cipher with XOR combiner is pretty compelling to me... Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: unruh on 29 Dec 2009 20:16 On 2009-12-29, Ivan Voras <ivoras(a)gmail.com> wrote: > On 29.12.2009 22:40, unruh wrote: >> On 2009-12-29, Ivan Voras <ivoras(a)gmail.com> wrote: >>> Hi, >>> >>> I'm not an expert but it looks like the canonical description of a >>> stream cipher boils down to "a PRNG which generates a keystream, which >>> is XOR-ed with plaintext to produce the ciphertext". This has some >>> obvious downsides mostly caused by the XOR step. >> >> This has an obvious downside why? The xor step has no downside. > > I am thinking about big flipping and key / keystream reuse. bit flipping? But that can happen in any system. Only in most what comes out is gibberish. But you can use a hash to protect against that. And why do you want to reuse the keystream? If you really do, get a block cypher rather than a stream cypher.
From: Ivan Voras on 29 Dec 2009 20:19
On 30.12.2009 0:42, Greg Rose wrote: > In article <hhe0nk$g75$1(a)sunce.iskon.hr>, Ivan Voras <ivoras(a)gmail.com> wrote: >> On 29.12.2009 22:40, unruh wrote: >>> On 2009-12-29, Ivan Voras <ivoras(a)gmail.com> wrote: >>>> Hi, >>>> >>>> I'm not an expert but it looks like the canonical description of a >>>> stream cipher boils down to "a PRNG which generates a keystream, which >>>> is XOR-ed with plaintext to produce the ciphertext". This has some >>>> obvious downsides mostly caused by the XOR step. >>> >>> This has an obvious downside why? The xor step has no downside. >> >> I am thinking about bit flipping and key / keystream reuse. > > Bit flipping is an attack against message > integrity and must be defeated by a message I would guess it could also be useful if the basic structure of the message is known (e.g. a data file contains 32-bit integers in known places) so it can get serious. > integrity check of some kind. There are also But I agree with you in general :) > So, since you already need non-repeating nonces > and message integrity, the simplicity of a stream > cipher with XOR combiner is pretty compelling to > me... OTOH I have been experimenting a little and it is very easy - practically trivial - to construct a stream cipher described in my original post (e.g. not keystream-xor-plaintext based) from a generic hash function[*] - so this answers my question. [*] Though it isn't necessarily fast (at least my attempts aren't): around 2 MB/s for MD5-based stream cipher and 33 MB/s for adler32-based, on a 2.4 GHz Core2 CPU. |