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

[Adam Back <aba@xxxxxxxxxxxx>]

Uri writes:
> > A stream cipher would also be problematic if used for conventionally
> > encrypted messages, and conventionally encrypted private keys on the
> > private keyring -- the symmetric key is derived from the passphrase,
> > which means you get the same key each time.
> 
> First - an observation. Just like a block cipher must have an IV (PGP
> side-stepped this by prepending the message with random stuff), a
> stram cipher must have a stream offset.

I presume by a stream offset you mean that you spin the stream cipher
PRNG for the published offset number of bytes, before using it to
encrypt data.

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)

- you incur the performance penalty of spinning the PRNG by the offset
  number of bytes (eg could be 100s of megs).

> For messages it may be not as crucial, as the symmetric cipher key is
> supposed to be random anyway (still IMHO having an offset helps).
> 
> 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 ) )

> > Even using the Symmetric-Key Encrypted Session Key packets are dubious
> > unless you start using a block cipher for the SKESK packet.
> 
> I do not see why.

I guess it's not immediately broken, but I don't like it.

Consider:

  rc4key = s2k( passphrase )
  rc4out = rc4-prng( rc4key )

where rc4out is what is xored with the plaintext to encrypt; and that
you're reusing the passphrase.

Now you encrypt with rc4 session keys sk1 and sk2 for two separate
messages m1 and m2, so the SKESK packets contain:

  skesk1 = rc4-encrypt( rc4key, sk1 ) = rc4out xor sk1
  skesk2 = rc4-encrypt( rc4key, sk2 ) = rc4out xor sk2

you can then recover sk1 xor sk2:

  skesk1 xor skesk2 = rc4out xor sk1 xor rc4out xor sk2 = sk1 xor sk2

Leaking of xors of sets of keys means that people can observe which
keybits are the same on a set of messages.  This seems like a leak you
would be better off without.

So, if someone ever recovers one of your sk-n for that passphrase they
can recover all other messages encrypted with that passphrase.

This is problematic for at least 2 reasons:

- you may want to reveal one sk when demanded to by someone

- if multiple SKESKs are used on one document to allow multiple people
  to read the document, anyone you ever shared a document with can
  decrypt all other documents encrypted with that passphrase even if
  they are not on the multiple SKESK list.

Adam