Stream ciphers
Ivan Voras
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.
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)?
unruh
> 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.
Remember that a one time pad-- xoring a true random stream with the
message ( which has the same xor operation) is the only provably secure
cryptosystem. the purpose of the stream cypher is to mimic the one time
pad with a stream which, while not a random stream, is indistiguishable
from a random stream to anyone who does not have the key.
>
> 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)?
>
Remember that the operation must be reversible, other wise it is not a
cypher. stream cyphers should be as simple as possible.
Thus the problem with yours is reversibility and speed.
amzoti
Perhaps you can have at look at:
1. Stream Ciphers: http://en.wikipedia.org/wiki/Stream_cipher
2. eStream Competition: http://en.wikipedia.org/wiki/ESTREAM (the
competition to design new ones)
Thomas Pornin
> 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.
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.
The XOR itself is not a downside. XORing allows an active attacker to
flip bits at will; but the mistake would be to believe that a non
XOR-based cipher would be immune against an active attacker. The XOR
merely illustrates that against an active attacker you need an
appropriate response, i.e. a MAC.
--Thomas Pornin
Ivan Voras
> On 2009-12-29, Ivan Voras <ivo...@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.
Ivan Voras
> According to Ivan Voras <ivo...@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?
Maaartin
> 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?
Greg Rose
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
unruh
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.
Ivan Voras
> In article <hhe0nk$g75$1...@sunce.iskon.hr>, Ivan Voras <ivo...@gmail.com> wrote:
>> On 29.12.2009 22:40, unruh wrote:
>>> On 2009-12-29, Ivan Voras <ivo...@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.
WTShaw
There are endless ways to do stream ciphers, many much better than
XOR. Endless complexity does not make it good if adequate primitives
are used wisely in the first place.
Thomas Pornin
> ciphers (and probably similarly complex to create), or would they?
Precisely.
A block cipher can be converted into a stream generator by encrypting
successive values of a counter; this is called "CTR" mode. The whole
point of designing a _stream cipher_ is that we hope, by restraining the
ways the cipher may be used (when compared with a generic block cipher),
we can achieve some better performance, stronger security analysis,
smaller implementation, or any other such gain.
--Thomas Pornin
Maarten Bodewes
Secure hash functions are inherently more difficult to construct - some
people even think they are impossible to construct - than block ciphers
which is reflected in their speed. Using a (safe) PRNG to create a
stream cipher is fine, but if both are in software, I'd use a
standardized block cipher in a standardized CTR mode.
Regards,
Maarten
WTShaw
> Ivan Voras wrote:
> > On 30.12.2009 0:42, Greg Rose wrote:
Such is the hype. However, this not true. If I explained a most
simple hash process to you, and gave you some output to play with,
there is no chance that you could solve it. But, so many like to live
in la la land and hold there head in there hands when there are better
ways. Defeating prejudice is threatening and the prejudice is that
there are no simple answers for any critical problems. As happened in
London, the cesspool workers fought the introduction of sewers because
it threatened their way of life...it didn't but blocking public health
would have.