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 [EMAIL PROTECTED]