17
$\begingroup$

I'm just trying to wrap my mind around the decision to select the 128-bit Rijndael as the AES cipher, even with 192-bit and 256-bit keys. Even with a 256-bit key, you only get 2^128 possible outputs per 128-bit block, thus kind of rendering the larger key size meaningless (not to mention the weaker key schedules).

Was this a NIST oversight when standardizing AES?

(Answering this isn't urgent. I'm using libsodium, which uses Xsalsa20 + Poly1305, in most of my projects these days, but it's something I don't readily know the answer to.)

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Note: There are actually $(2^n)!$ n-bit permutations, i.e. there are roughly $2^{2^{135}}$ 128-bit permutations, meaning finding $2^{256}$ ones isn't too hard. $\endgroup$ – SEJPM♦ Dec 22 '15 at 20:21
  • 1
    $\begingroup$ my own analysis has shown that pretty much any block cipher should have a key size at least 1.4 times larger than the block size $\endgroup$ – Richie Frame Dec 22 '15 at 20:47
  • 2
    $\begingroup$ @RichieFrame How did you come up with that number? $\endgroup$ – kasperd Dec 23 '15 at 9:53
  • 1
    $\begingroup$ @kasperd brute force calc of all possible PT/CT pairs for all keys on several small block ciphers, then looking at the distribution of the pairs for multiple key sizes. For all block sizes, it was about 1.4, which I assume approximates $\sqrt2$ in reality, for which there was a 100% match of some metric, I no longer have the data files (they took up a lot of space). Same metric was 0.7 when key and block size matched ($1/\sqrt2$?) $\endgroup$ – Richie Frame Dec 23 '15 at 20:29
15
$\begingroup$

No, this isn't an oversight. AES is a block cipher, which is a keyed permutation. Now if you have a permutation of, say, three elements there are e few permutations possible:

a -> a
b -> b
c -> c

but also:

a -> b
b -> c
c -> a

and

a -> c
b -> a
c -> b

and

a -> c
b -> b
c -> a

(there should be $6$ for $3!$, the factorial of three, I won't write them all out)

Now if you look closely, there are more than 3 permutations possible. The actual number of permutations is higher than the input/output! To be precise, the number of permutations is $(2^{128})!$, which is a lot more than $2^{256}$.

The purpose of the key is to select one of the possible permutations. So the key could be a lot larger than 256 bits and still be meaningful. This also means that there may be multiple keys that map a specific ciphertext block to a specific plaintext block. An attacker may have to validate more pairs to be reasonably sure of success. For instance, in both the last two permutations in the example, a maps to c.

The block size is - as Yehuda Lindell writes in the other answer - needed when many blocks are encrypted. For instance when you choose a random nonce for CTR mode, the blocksize must be high enough or you will get overlaps in the counter that is encrypted to create the key stream (i.e. choosing a twice in the example). In that case the key stream would repeat, breaking the stream cipher.

An example of a block cipher with a much larger maximum key than block size is Blowfish, which has a block size of 64 bits and a key size of max 448 bits. Blowfish is considered deprecated by the author, Bruce Schneier. Besides other issues, the small block size is a major reason for the deprecation. Both followup ciphers, Twofish and Threefish, expand the blocksize.

| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ For your illustration: $(2^{128})!\approx2^{2^{135}}\approx2^{4306521928262132675756558040498023782891}$ $\endgroup$ – SEJPM♦ Dec 22 '15 at 20:45
  • 3
    $\begingroup$ Actually, for three elements there are only $6 = 3!$, not 9. $\endgroup$ – Paŭlo Ebermann Dec 22 '15 at 21:42
  • $\begingroup$ Thanks, I figured there was something I was missing and it turned out to be not reasoning by lego. :) $\endgroup$ – Scott Arciszewski Dec 23 '15 at 6:45
  • 1
    $\begingroup$ Nice article, but I don't think you were reasoning by Lego :) $\endgroup$ – Maarten Bodewes♦ Dec 23 '15 at 10:23
8
$\begingroup$

There is no NIST oversight here. The key size and the block size are two completely different parameters and issues. The only reason that you need a large block size is because bad things start to happen when you encrypt too many blocks. Specifically, for an $n$-bit block size, the birthday paradox kicks in at $\sqrt{2^n}$. So, for a 128-bit block, you need to encrypt so much that it makes no difference. In contrast, a larger key and more rounds (which is what you get for AES-192 and AES-256) gives you a better security margin against cryptanalysis.

| improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.