If you XOR a key k0 to a message m, apply a random permutation to the XOR-sum and XOR the result with another key k1, then you get a one round key-alternating cipher. If you want to have 2 rounds, add another permutation and a key k2. If you want even more rounds, just follow this pattern. AES is an example for such a key-alternating cipher with 10 (in case of AES-128) rounds. For such a simple and prominent design, you would expect it to be very well understood, wouldn't you?
Indeed, if you ask an arbitrary cryptographer which area - block ciphers, public-key cryptography, hash functions or protocols - is the best understood the answer would probably be public-key cryptography. We do have a reliable armory of recipes to build secure block ciphers and the theory to distinguish a secure block cipher from an insecure one is well developed. Despite a few recent attacks on AES, AES stands pretty firm and can be used in many states for encryption of the most secret documents. All recent attacks were extremely involved and haven't had a significant impact on the practical security of AES. However, the gold standard for a cryptographic primitive nowadays is a security proof, i.e. a proof that breaking the block cipher is at least as difficult as solving a very difficult problem.
When AES (Rijndael by its original name) was designed and standardized, the field of provable security was still at its beginnings and none of the AES-finalists had such a security proof when Rihndael was chosen to be the next AES. Having a reliable block cipher standardized, the focus of cryptographic research shifted to the other three areas - public key cryptography, hash functions and protocols - and if you look for example at the current SHA3 candidates, they all have a proof of security in their submission documentation. (This doesn't necessarily imply that we trust them as much as we trust AES.) But for AES, the trusted workhorse of cryptography, we still don't have such a security proof.
The authors of the paper "Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations (Extended Abstract)" (the full version is to appear in the Journal of Crytpology), A. Bogdanov, L. R. Knudsen, G. Leander, F.-X. Standaert, J. Steinberger and E. Tischhauser, stumbled across this oddity when they tried to design an AES variant that is secure against related-key attacks. They started with an old result which gives that a generic attack on a key-alternating cipher with just one round (permutation) requires at least 2n/2 operations. (n is the block size.) One of the well known rules in block-cipher design is that the security of a key-alternating cipher grows with the number of rounds. So in their paper, the authors try to show an improved lower bound for arbitrary many rounds. They show that for t>=3 rounds, a generic attack on such a cipher has to use at least 23n/4 operations in order to break the cipher and they conjecture that a more precise lower bound will be 2(tn/(t+1)).
Can these results be applied to AES? No, at least not directly. We already know that AES is vulnerable against related key attacks. Is the bound tight? All previous research suggests, that the bound is only tight for the special case of t=2. What can it be used for? The authors propose a construction of a cipher that should be secure against related key attacks (unless there is an AES-specfic underlying vulnerability): It is a 2-round key-alternating cipher that uses AES with two different constant keys as permutation.
From their work it becomes clear that the road towards provably secure block ciphers won't be an easy one and that it is far more difficult to prove security of block cipher than, for example proving the security of public-key based crypto schemes. However, the time might have arrived where the techniques of provable security have matured enough to tackle block ciphers.
No comments:
Post a Comment