Re: stream ciphers (Re: 128 bit block ciphers)

[Adam Back <aba@xxxxxxxxxxxx>]

Uri writes:
> > This has a number of problems/added complexities I think:
> > - you have to remember a current offest to avoid re-using offsets
> >   (adds state to symmetric crypto where there is none currently)
> 
> Similarly to having to remember not to re-use IVs.

Ah, but you get "remembering" not to re-use IVs for free -- you just
use random ones, or for some block modes just non-repeating IVs.
Using random offsets is impractical due to the performance penalty of
spinning the PRNG by 2^(IV size).

> > > For the keys to have a stream offset can mean the difference between
> > > secure and insecure.
> > Another way to do things which avoids some of the problems with
> > offsets is to have a random, or at least non-repeating IV, which is
> > sent in the clear.  Then use the IV as part of the key.  eg.
> > 
> > rc4-key-shedule( iv || s2k( passphrase ) )
> 
> A possibility. Would need more time to evaluate it...

It has a sort of precedent, so must (one presumes!) have been looked
at in that the export versions of SSL cipher suites with RC4
(RC4-40-RSA-MD5) use the construct.  ie they construct a 128 bit RC4
from a 40 bit secret component and a public (sent in the clear) 88 bit
salt, via :

	128bit-key = md5( 88bit-salt || 40bit-key )

(there are some other padding rules, they actually generate two keys,
one for each direction and there are some other values concatenated.)

Probably:

	rc4-key-schedule ( s2k( iv || passphrase ) ) 

would be better as it usees the hash in the s2k for mixing rather than
relying partly on rc4 key schedule (which the rc4-key-schedule( iv ||
s2k (passphrase) does ).

> > you can then recover sk1 xor sk2:
> 
> You might want to take a look at SEAL. It provides the offset VERY
> elegantly. Unfortunately it's patented...

Ah, yes, I suspected you were thinking of SEAL in your earlier
comments on offsets :-) ... SEAL is more than a stream cipher, it is a
pseudo-random function family, so spinning to arbitrary points comes
for free with SEAL.  Very nice, agreed.  But that trick doesn't work
with RC4.

Adam