-----BEGIN PGP SIGNED MESSAGE-----
At 07:28 AM 23-11-99 -0800, David Honig wrote:
I am not privy to any inside knowledge of NIST's
motivations, but I can see some reasons for these decisions:
>1. Why does AES require 128 bit blocks? Any other reason
>than to make ECB codebook attacks tougher?
Here are two obvious reasons:
a. To avoid leaking plaintext information in
reasonable-length messages.
b. Because longer blocks make it easier to do some things,
like building hashing and MACing modes, and encrypting
128-bit keys in a single block.
When you have an n-bit block cipher, chaining modes start
leaking information after 2^{n/2} blocks encrypted under the
same key. For example, think about a message encrypted
under CBC-mode in which two ciphertext blocks are the same.
C[i] = Enc(C[i-1] XOR P[i])
C[j] = Enc(C[j-1] XOR P[j])
When we see C[i] == C[j], we can infer that
P[i] XOR P[j] == C[i-1] XOR C[j-1], by doing a little
algebra on the above equations. Now, each ciphertext block
can be thought of as more-or-less an n-bit hash of all
previous message bits. With an n-bit hash, we expect to
have to look at about 2^{n/2} hashes before we find a pair
with the same value. So for DES-CBC, with a 64-bit block,
after about 2^{32} message blocks we expect to get two
ciphertext blocks with the same value. At that point, we
start leaking XORs of plaintext blocks.
The number of expected collisions goes up with the square of
message blocks, so longer messages can wind up leaking a
lot of information.
>2. Why does AES require >128 bit keylength support? 2^128
>is not practically breakable. What am I missing? Is this
>simple "overengineering" aka "safety margins" (plus "bits
>are cheap, but not so cheap that using minimal-128 isn't
>worth it sometimes")?
Three reasons come to mind:
a. If quantum computers ever become practical, keysearch
attacks could be done on n-bit keys with 2^{n/2} steps. If
quantum computers become practical, they're already going to
destroy all of our public key cryptosystems; it would be
nice to at least get to keep using our symmetric systems.
b. There is a nice argument for making all of your block
cipher parameters resistant to accidental collisions. That
is, with a 256-bit key, we expect to have to wait a long
time for a collision in a random key generation mechanism or
anything.
c. 128 bits is impractical for keysearch attack, but it's
not quite as far out there as we'd like. I mean, a really
determined and well-funded three letter agency might be able
to do 80-90 bits today. Improving their abilities by
several trillion times may not be totally impossible over
the next several years.
On the other hand, I question whether anyone really
understands how to design ciphers for a world where (say)
200-bit searches can be done. Imagine what powerful things
we can do to analyze round structures, visualize various
properties, etc., with 2^{200} operations. We have all
tried to do this for our AES submissions, and we all hope
we've succeeded. But it's a little like asking the best
aircraft designers of the second world war to design
fighters to be used in the 1990s. The whole world of
assumptions and available technology is different.
Disclaimer: I am one of the designers of Twofish, one of
the AES finalists. Add grains of salt to taste.
- --John Kelsey, Counterpane Internet Security, [EMAIL PROTECTED]
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCVAwUBODuN9SZv+/Ry/LrBAQEkTAP/QGNaxNL2XR/LOOIioKQ4v/MUobTLKZNU
OY2yAjzpunoPtuSI1C4m/7mWFrmaX/sX7lUAQlOahlNVRmg1ANkT+fYv/mYiBODB
WzQYFzYggC0anTazRXV/Xa13i+m7J0qZ0pD3KOAmxWvou4w6GGtL4NzHNC1CBQGe
znXoJTj/DqI=
=Lshj
-----END PGP SIGNATURE-----
--John Kelsey, Counterpane Internet Security, [EMAIL PROTECTED]
PGP: 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
