Monday, July 19, 2010

Some thoughts on Rijndael

When I heard that the Rijndael block cipher was selected as the algorithm for the Advanced encryption standard, I was so excited I sent one of the creators of Rijndael a very excited email.

OK, I should probably explain this in more layman’s terms. AES—the advanced encryption standard—is the standard cipher people use when people get a clue and realize they need to use strong cryptography and not ad-hoc schemes to protect data. WEP used RC4 instead of AES, and was soon broken; this has been replaced by WPA2, which does use AES. Indeed, the wireless packets being sent to publish this blog are encrypted with AES. The blu ray discs sitting on the player in the other room are encrypted with AES (this is another form of cluelessness, since cryptography only makes it inconvenient, not computationally infeasible, for the intended user of a piece of media to copy said media. The way you stop piracy is by teaching freetards integrity and morals, not with cryptographic ideas that will never work). AES is the most secure way to make web sites encrypted with https.

I liked Rijndael more than the other contestants because it was a good deal more flexible. Rijndael was designed with something called the wide trail strategy that allows components to be readily replaced or modified. For example, it is possible to change its block size; all other AES candidates (with the exception of HPC and possibly RC6) had a fixed block size of 128 bits; Rijndael can have a block size of 128, 160, 192, 224, or 256 bits. Or, if desired, it is relatively straightforward to make an unofficial Rijndael variant with a 32, 64, or 96 bit block size.

It is also possible to change its S-box if one feels Rijndael is somehow too algebraic.

Another thing that is possible to do is to make a Rijndael variant using 64-bit instead of 32-bit integers. If this is done, the variant’s “natural” block size is 512 bits; this can be adapted to have a block size of any multiple of 64 bits from 64 to 1024 bits (64, 128, 192, 256, 320, 384, 448, 512, 576, 640, 704, 768, 832, 896, 960, or 1024 bits). The dirty work of coming up with magic constants for a 64-bit Rijndael variant has already been done with the Whirlpool hash; the only constants we need to pull out of the air are the “shift row” constants.

The Rijndael/Whirlpool variant with a 1024-bit block size has a large enough block to be used in a “sponge function” mode of operation. A cryptographic sponge allows any significantly large random-looking permutation to be used as the code of a hash function or stream cipher (it’s a hash function with an arbitrarily long output). We can use a 1024-bit block size cipher as a sponge to generate a 256-bit hash, or by having things be twice as slow, a 384-bit hash (For people familiar with sponge constructions: The 256-bit hash is done with a “capacity” and “rate” of 512 bits; the 384-bit hash is done with a “capacity” of 768 bits and a “rate” of 256 bits).

Another idea that has been implemented is both 64-bit and 128-bit Rijndael variants where the encryption and decryption operations are identical—useful for minimizing code size in implementations where encryption and decryption are both supported. We give up block size flexibility when we do this (the 32-bit version needs a block size of 128 bits, but the 64-bit version can have a block size of either 64 bits or 512 bits). This has been implemented with Anubis (32-bit words, 128-bit block size) and Khazad (64-bit words, 64-bit block size; can be modified to be a 512-bit block). In addition, there is a proposed 128-bit word size primitive (PDF file) that could be used to make either a 128-bit or 2048-bit Rijndael variant using the same operations for encryption and decryption.

Rijndael has a couple of issues. One is that the key schedule is not as strong as it could be; this has resulted in their being an academic weakness called a “related key attack”. This does not result in any practical security problems; a related key attack is one of the hardest to utilize in the real world (cipher keys are usually hashed using cryptographic hashes). Indeed, the website describing this attack on Rijndael uses, of all things, Rijndael to encrypt traffic.

The other issue is that in an optimized implementation, Rijndael uses a lot of table lookups, which make it vulnerable to an attack called a “cache timing attack”. A cache timing attack could be used by an adversary with limited access to a system running Rijndael encryptions to determine a Rijndael key used elsewhere on the system. The attack is right now a purely academic attack; no one has seen it used by a real-world adversary, and some processors (such as the ARM) series can thwart it with cache lock-down. With the AES instruction set now a reality, these attacks will soon be a non-issue.

So, yes, Rijndael is a very nice, very flexible cryptographic primitive.