[25841] in cryptography@c2.net mail archive
RE: the meaning of linearity, was Re: picking a hash function to
daemon@ATHENA.MIT.EDU (Kuehn, Ulrich)
Wed May 17 10:06:28 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Kuehn, Ulrich" <Ulrich.Kuehn@telekom.de>
To: leichter_jerrold@emc.com, solinym@gmail.com
Cc: cryptography@metzdowd.com
Date: Wed, 17 May 2006 09:54:29 +0200
> -----Original Message-----
> From: leichter_jerrold@emc.com [mailto:leichter_jerrold@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@metzdowd.com
