another feature RNGs could provide

David Malone dwmalone at maths.tcd.ie
Wed Dec 28 05:46:59 EST 2005


On Tue, Dec 27, 2005 at 11:34:15PM +0000, Ben Laurie wrote:
> If you don't have sufficient plain/ciphertext, then of course you can
> choose incorrect pairs.

Yep - that's my point. The thing to note is that for an arbitrary
permutation, knowing the image of n plaintexts tells you (almost)
nothing else.  Usually for a block cipher with a smaller key space,
knowing a plaintext/ciphertext pair actually has a pretty big impact
on what you know about the key, and this is how people usually think
about block ciphers.

In AES with a 128 bit block and 256 bit key, if the images are
uniformly and independently distributed, then each pair known reduces
the possible amount of key space by about 128 bits, so 2 or 3 pairs
will nail the key down with reasonable probability. For good measure
we could say 20 or 30 would be sufficient, even if the images aren't
well distributed.

For S_(2^128) the original key space has (2^128)! keys so it is
about 128*(2^128) bits. Knowing 30 pairs here will reduce the key
space by about 128*30 bits, leaving us with 128*(2^128) - 128*30 =
128*(2^128-30) bits. We've barely had any impact at all, because
the key space was much bigger to begin with.

Of course, this also shows why using an arbitrary permutation in
S_(2^128) isn't very practical - you need to store 128*(2^128) bits
to remember which one you're using!

	David.

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



More information about the cryptography mailing list