the meaning of linearity, was Re: picking a hash function to be encrypted

[Kuehn, Ulrich]

> -----Original Message-----
> From: leichter_jerrold at emc.com [mailto:leichter_jerrold at emc.com]
>  
> The thing I've always wondered about stream ciphers is why we only
> talk about linear ones.  A stream cipher is fundamentally constructed
> of two things:  A stream of bits (alleged to be unpredictable) as
> long as the plaintext; and a combining function that takes one
> plaintext bit and one stream bit and produces a ciphertext bit.
> The combining function has to conserve information.  If you only
> combine single bits, there are only two possible functions:  XOR
> and the complement of XOR.  But consider RC4:  It actually generates
> a byte at a time.  We just choose to use that byte as a vector of
> 8 bits.  For plaintexts that are multiples of 8 bits long - just
> about everything these days - there are many possible combining
> functions.  Most aren't even close to linear.
> 

I am not sure this will add to the security of the whole thing. My reasoning behind that is:

The combining function needs to be invertible (we want to recover the plaintext, don't we?), so we have an 8-bit block cipher with an 8-bit key (supplied by the key stream generator). 

Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case.

Regards,
Ulrich


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com