In a companion paper (work in progress) we will show many other versions of our attacks, for example with 256 chosen plaintexts, and for 27 % of all keys, we can break KeeLoq with the total complexity of 257 KeeLoq encryptions. With 16 Gb of RAM, half of this number. In terms of complexity, this result is hard to improve, because we cannot expect to beat 264 CPU clocks (about 253KeeLoq computations) with an improved brute force approach. However, the more chosen plaintexts we have, the higher will be the success probability of this attack (in this paper we do get the same complexity but only for for 11 % of all keys).
5 Conclusion
KeeLoq is a block cipher widely used in the automotive industry. We present an attack that accelerates both hardware and software brute force attacks by the same factor. Unlike other known attacks on KeeLoq, this is not a sliding attack, but a related key attack based on self-similarity of the cipher, in which several keys are tried simultaneously. Our results are summarized in Table 1.
Legend: The unit of time complexity here is one KeeLoq encryption.
This approach has obvious limitations and cannot break ciphers in which the key size is large from the start, but gives very good result in cryptanalysis of
Table 1.Various attacks on KeeLoq in order of increasing plaintext requirements Type of attack Data Time % Keys Memory Reference
Brute Force 2 KP 263 100% small
B. F. + Precomp. Speed-up 2 KP 262 100% 16 Gb NEW: this paper Brute F. + Self-Similarity 2 CP 261.4 100% small NEW: this paper Brute F. + Self-Similarity 2 CP 260.4 100% 16 Gb NEW: this paper Brute F. + Self-Similarity 2 CP 257 11% small NEW: this paper B.F. + Self-Sim. + Precomp. 2 CP 256 11% 16 Gb NEW: this paper
Slide-Algebraic 216KP 253 63% small Slide-Alg. Attack 2 in [11]
Slide-Meet-in-the-Middle 216KP 246 63% 3 Mb Dunkelmanet al[2]
Slide-Meet-in-the-Middle 216CP 245 63% 3 Mb Dunkelmanet al[2]
Slide-Correlation 232KP 251 100% 16 Gb Bogdanov[4,5]
Slide-Fixed Points 232KP 243 26% 16 Gb Attack 4 eprint/2007/062/
Slide-Cycle-Algebraic 232KP 240 63% 18 Gb Attack A in [13]
Slide-Cycle-Correlation 232KP 240 100% 18 Gb Attack B in [13]
Two basic versions in [11]:
Slide-Determine 232KP 231 63% 16 Gb Version A in [11]
Slide-Determine 232KP 228 30% 16 Gb Version B in [11]
Improved versions in [12]:
Slide-Determine 232KP 230 63% 16 Gb Overall average time [12]
Slide-Determine 232KP 227 30% 16 Gb ’Realistic’ version, [12]
Slide-Determine 232KP 223 15% 16 Gb ’Optimistic’ version, [12]
KeeLoq in which the key size is quite short. This in combination with the self- similarity property of KeeLoq, allows realistic attacks on KeeLoq systems. Due to the protocol (KeeLoq IFF mode, cf. [5]), chosen ciphertext attacks are realistic and allow to clone KeeLoq transponders in practice.
In the current state of art (cf. Table 1) KeeLoq remains as secure as allowed by the key size, for adversaries disposing of a small number of known plaintexts.
The main contribution of this paper is to show that the security of KeeLoq does already degrade by a factor bigger than 3, as soon as the adversary disposes of two chosen plaintexts. Future research should show it will further decrease with more chosen plaintexts. We also showed that an extra factor of 2 can be gained with some extra memory.
References
1. Biham, E., Dunkelman, O., Indesteege, S., Keller, N., Preneel, B.: How to Steal Cars A Practical Attack on KeeLoq. Crypto 2007 rump session talk (2007), http://www.cosic.esat.kuleuven.be/keeloq/keeloq-rump.pdf
2. Biham, E., Dunkelman, O., Indesteege, S., Keller, N., Preneel, B.: How to Steal Cars A Practical Attack on KeeLoq. In: Smart, N.P. (ed.) EUROCRYPT 2008.
LNCS, vol. 4965, pp. 1–18. Springer, Heidelberg (2008)
3. Biryukov, A., Wagner, D.: Slide attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999)
4. Bogdanov, A.: Cryptanalysis of the KeeLoq block cipher, http://eprint.iacr.org/2007/055
5. Bogdanov, A.: Attacks on the KeeLoq Block Cipher and Authentication Systems.
In: 3rd Conference on RFID Security, RFIDSec (2007)
6. Bogdanov, A.: Linear slide attacks on the keeLoq block cipher. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds.) Inscrypt 2007. LNCS, vol. 4990, pp. 66–80. Springer, Heidelberg (2008)
7. Keeloq wikipedia article (January 25, 2007), http://en.wikipedia.org/wiki/KeeLoq
8. Keeloq C source code by Ruptor,http://cryptolib.com/ciphers/
9. Courtois, N.: Examples of equations generated for experiments with algebraic cryptanalysis of KeeLoq,http://www.cryptosystem.net/aes/toyciphers.html 10. Courtois, N., Bard, G.V., Wagner, D.: Algebraic and Slide Attacks
on KeeLoq, Older preprint with an incorrect specification of KeeLoq, eprint.iacr.org/2007/062/
11. Courtois, N.T., Bard, G.V., Wagner, D.: Algebraic and slide attacks on keeLoq.
In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 97–115. Springer, Heidelberg (2008)
12. Courtois, N., Bard, G.V.: Random Permutation Statistics and An Improved Slide- Determine Attack on KeeLoq. In: Naccache, D. (ed.) Festschrift Quisquater. LNCS, vol. 6805, pp. 55–66. Springer, Heidelberg (2011)
13. Courtois, N., Bard, G.V., Bogdanov, A.: Periodic Ciphers with Small Blocks and Cryptanalysis of KeeLoq, vol. 41, pp. 167–188. Tatra Mountains Mathematic Pub- lications (2008); Post-Proceedings of Tatracrypt 2007 Conference, The 7th Central European Conference on Cryptology, Smolenice, Slovakia (June 22-24, 2007) 14. Hellman, M.E., Merkle, R., Schroppel, R., Washington, L., Diffie, W., Pohlig, S.,
Schweitzer, P.: Results of an initial attempt to cryptanalyze the NBS Data Encryp- tion Standard, Technical report, Stanford University, U.S.A. (September 1976);
Known also as Lexar Report, Lexar Corporation, Unpublished Report, 11611 San Vicente Blvd., Los Angeles (1976)
15. Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptog- raphy. CRC Press, Boca Raton
16. Microchip. An Introduction to KeeLoq Code Hopping (1996), http://ww1.microchip.com/downloads/en/AppNotes/91002a.pdf 17. Microchip. Hopping Code Decoder using a PIC16C56, AN642 (1998),
http://www.keeloq.boom.ru/decryption.pdf
18. Microchip. Using KeeLoq to Validate Subsystem Compatibility, AN827 (2002), http://ww1.microchip.com/downloads/en/AppNotes/00827a.pdf
Increasing Block Sizes Using Feistel Networks:
The Example of the AES
Jacques Patarin1, Benjamin Gittins2, and Joana Treger1,3
1 University of Versailles Saint-Quentin-en-Yvelines, France jacques.patarin@prism.uvsq.fr
2 Synaptic Laboratories Limited, PO Box 5, Nadur, Gozo, NDR-1000 Malta, Europe cto@pqs.io
3 ANSSI, 51 boulevard de la tour Maubourg, 75007 Paris, France joana.treger@ssi.gouv.fr
Abstract. In this paper we study how to generate new secret key block ciphers based on the AES and Feistel constructions, that allow arbi- trary large input/output lengths while maintaining the ability to select -a priori- arbitrary security levels. We start from the generation of block ciphers that are simple balanced Feistel constructions that exploit the pseudorandomness of functions, namely the AES, as round function. This results in block ciphers with inputs and outputs of size 256 bits, i.e., that are doubled compared to the AES. We then extend this principle following the “Russian Doll” design principle to build block ciphers with (arbitrarily) larger inputs and outputs. As an example, we build block ci- phers with an expected security in about2512, or21024, instead of2128for the classical AES with 128 key-bits. The expected security is not proven, but our constructions are based on the best known attacks against Feis- tel networks with internal random permutations, as well as some natural security assumptions. We study two configurations of assumptions, lead- ing to two families of simple and efficient new block ciphers, which can thus be seen as candidate schemes for higher security.
1 Introduction and Related Works
1.1 Introduction
The Advanced Encryption Standard (AES) cipher was selected in October 2000 by the United States (U.S.) National Institute of Standards and Technologies (NIST) to be the new U.S encryption standard. This secret key block cipher accepts a block size of 128 bits and symmetric keys of 128 bits, 192 bits or 256 bits in length. Up to now, no attack better than the exhaustive search on the key is known when AES is used in NIST FIPS 140-2 authorised modes of operation [16]. However, some cryptanalysis attempts are potentially dangerous and have to be studied carefully. For instance, the algebraic cryptanalysis of the AES [5] and a range of related key attacks [2], [21], [8].
In 2009, the standard security bound for a cryptographic algorithm,i.e., the maximum number of computations that an enemy is expected to be able to do in
D. Naccache (Ed.): Quisquater Festschrift, LNCS 6805, pp. 67–82, 2012.
c Springer-Verlag Berlin Heidelberg 2012
practice, stands between280 and 2100. There are many publications estimating the duration of security for a given symmetric key length against brute force attacks based on Moore’s law [12], [17], [7]. Moore’s law model is an important semiconductor trend that has continued for more than half a century: the number of transistors that can be inexpensively placed on an integrated circuit should be doubling approximately every two years [14]. Krauss and Starkman estimates that the entire computing capacity of the universe would be exhausted after 600 more years of Moore’s Law [11]. Some pundits expect Moore’s law to continue for at least another decade at least and perhaps much longer.
Going back to the AES, it is likely that a security of2128remains satisfying for a long time again. In the classical computation model this would require only a 128-bit key. The eventuality to one day see the emergence of quantum computers is nowadays taken very seriously by some parts of the scientific community. In the context of block ciphers, Grover’s quantum algorithm provides a quadratic improvement over the classical brute force search, enabling a quantum computer to find one of exactlykitems in an unsorted database ofN items inO(
(N/k)) operations and approximatelylog2N qubits [9]. AES with a 256-bit key length appears to be designed to provide2128 security against Grover’s algorithm.
It is possible that we will never reach a computation capacity of 2256 oper- ations. As a consequence, if no efficient cryptanalysis of the AES with keys of size256bits is found, and if the keys are updated every264 blocks to avoid the birthday paradox on the entries, the AES may go on being suitable for all our future needs for secret key encryption.
There however exist some real motivations for proposing secret key algorithms presenting a claimed security larger than2256, as the ones based on some simple constructions that we propose in this article.
First of all, restricting the length of the keys to 128 or 256 bits might appear somehow artificial with respect to the cost of the computations made. Personal computers are now sold with many gigabytes of memory and compute the AES very quickly (<0,001 second). Multiplying these values by 10, 100, or even 1000 is not noticeable from the user’s point of view in many cases such as secure email, virtual private networks run over wide area networks, and the protection of data at rest. In constrained environments such as smart cards and sensor networks multiplying the computations by 4 to 8 times, and key lengths by 10 to 100 times may not pose a significant problem.
From another point of view, the security of the AES remains unproven. It is then not unreasonable to want to have some safety margin to prevent from eventual cryptanalysis discoveries.
There are also some drivers that call for long range security with increased levels of assurance [6].
In this perspective, and assuming the use of TEMPEST certified operating environments and hardened operating software, it is therefore appropriate to propose secret key cryptosystems with a key length of the order of 512 bits and a security on classical computers of the order of2512.
In this article, we study some very simple constructions. These constructions are based on iterations of Feistel ciphers, as already proposed in the “Russian Doll” paper by Patarin and Seurin [19]. We propose to use them with the AES whose key length is 128 bits (AES128,128) as internal function. Other internal functions are possible, like the AES with larger keys, the Rijndael with larger input/outputs, the DES or 3-DES for instance. Notice that one of the finalists for the AES contest, DEAL, designed by Knudsen [10], already used the idea of taking some known scheme (in that case, the DES) as internal function of Feistel schemes. But here, we go further by iterating this process. Our analysis is based on the recent results of Treger and Patarin [22], giving the actual best known generic attacks on Feistel networks with internal permutations.
Surprisingly enough, it is no easy task to try to adapt a scheme to larger secu- rity or larger inputs and outputs [13]. This may be the reason why such designs barely exist, though it seems a rather natural thing to do. Our proposal appears to be very simple, but we needed to define and work under some assumptions to build a consistent security model. These assumptions seem quite natural to us, but may also be arguable. We study two different scenarios, depending on the assumptions we make, leading to two different families of constructions. We sup- port our proposal with experimental simulations that compare the performance of different families of cipher for given levels of security and sizes of inputs and outputs.
1.2 Related Works and Organization of the Paper
Building new block ciphers from existing block ciphers is well known in the art.
The 3DES mode of operation for DES chains the data path of three indepen- dently keyed invocations of DES, without increasing the block length [15]. The DEAL cipher [10] is a balanced Feistel network construction with 6 to 8 rounds that used DES with a 56 bit key as the round function. Unlike 3DES, DEAL employed a simple stateless key expansion technique that had security imperfec- tions [13]. The “Russian Doll” technique is used by Patarin and Seurin [19] as a self-similar method of increasing the block length by building balanced Feistel Networks using round functions that implement balanced Fesitel networks. See also the unpublished TURTLE block cipher [3] for another construction based on the “Russian Doll” technique.
The article is organized as follows. Section 2 explains the construction of our ciphers. First, it gives some known results on Feistel ciphers, namely the table of the best known attacks on Feistel ciphers with internal random permutations.
In this section 2, we also state the different sets of assumptions we work un- der. Then we detail in this same section on our construction for both sets of assumptions, as well as on the security estimation of the resulting permutations.
We support the construction by experimentations at the end of this section 2.
Section 3 concludes this paper.
2 Building Block Ciphers Using Block Ciphers
2.1 Introduction
In this part of the document we propose schemes that use the AES cipher as our internal function. These schemes employ a balanced Feistel structure sim- ilar to DEAL, and a key management strategy that is similar to 3DES. We adapt the self-similar balanced Feistel construction of the cipher described in the “Russian Doll” paper to support variable length block widths. Specifically where the “Russian Doll” paper uses small randomly generated s-boxes as the underlying cryptographic primitive, our constructions substitute the randomly generated s-boxes with randomly keyed AES invocations. Other internal func- tions are conceivably possible, like the AES with larger keys, the Rijndael with larger block width, the DES or 3DES. Ciphers with security ratings less than the block width, such as DES, will require additional study that is outside the scope of this paper.
2.2 Known Results on Feistel Ciphers with Internal Random Permutations
Our results in this paper are based on the recent results of Treger and Patarin [22]
in which the best known generic attacks on Feistel networks with internal random permutations are published. Table 1 below issued from [22] gives the maximum number of computations needed to distinguish a Feistel cipher (depending on the number of rounds) from an even random permutation. From this table, we can deduce the minimum number of rounds of Feistel ciphers needed to reach a given security. It is possible that improved attacks exist and will be found, in which case the analysis presented in this paper will need to be adapted to the new results. For this reason we recommend selecting security ratings slightly larger than the target level to improve our assurance levels.
2.3 Randomising Even Permutations so They Are Odd Permutations 50% of the Time
Symmetric block ciphers based on Feistel networks are all even permutations [22], [18], [20]. It is also known that the AES block cipher is an even permutation [4].
This property can be used to distinguish these block ciphers from a random permutation which will have an even permutation approximately 50% of the time. In our constructions we want to mask this even permutation property so we cannot distinguish Feistel Network or AES in this way.
To mask this property we assign an extra key bit to each invocation of the block cipher and use this bit to perform a conditional permutation on the plain- text inputs with value 0x0000...0000 and 0x0000...0001 before supplying the transformed plaintext to the block cipher. For encryption if the value of the extra bit is 1 and if the value of the plaintext AND 0xFFFF...FFFE is equal to0x0000...0000then we XOR the value of the plaintext with0x0000...0001to permute between the two values and encrypt this intermediate value using an
Table 1.Maximum number of computations needed to distinguish random even per- mutations on2nbits from Feistel networks build from random permutations onnbits, with the best known attacks
numberk
of rounds KPA CPA-1 CPA-2 CPCA-1 CPCA-2
1 1 1 1 1 1
2 2n/2 2 2 2 2
3 2n 2n/2 2n/2 2n/2 3
4 2n 2n/2 2n/2 2n/2 2n/2
5 23n/2 2n 2n 2n 2n
6 23n 23n 23n 23n 23n
7 23n 23n 23n 23n 23n
8 24n 24n 24n 24n 24n
9 26n 26n 26n 26n 26n
10 26n 26n 26n 26n 26n
11 27n 27n 27n 27n 27n
12 29n 29n 29n 29n 29n
k≥6, k=0mod3 2(k−3)n2(k−3)n 2(k−3)n 2(k−3)n 2(k−3)n
k≥6, k=1 or 2mod32(k−4)n2(k−4)n 2(k−4)n 2(k−4)n 2(k−4)n
invocation of the block cipher encryption algorithm. The inverse process is per- formed for decryption. In this paper,every invocation of a block cipheris modified with this logic. In this way n invocations of modified AES128,129 we will consumen∗129bits of key material. The invocation to AES128,128 itself is NIST compliant.
2.4 Assumptions and limitations
Limitations. All arguments in this paper assume the symmetric primitive in question is not based on number-theoretic arguments (factoring, dihedral hidden subgroup problem, coding theory, etc). In this paper anbit key must havenbits of entropy. We do not permit the attacker to perform related key attacks. Our block ciphers should not be used in modes of operation that chain the previous ciphertext into the key input. Likewise, our block ciphers should not employ counters in the key input.
We are unaware of any cryptographic publications formally studying the se- curity of message authentication code protocols in the light of Grover’s quantum algorithm. Prof D. J. Bernstein’s article [1] (2009) studies the best known re- sults for finding preimages and collisions in hash functions under the classical and quantum computing models. In that article it is stated that the best classical attack for unkeyedb-bit preimage collisions is2b hash invocations and the best quantum attack is 2b/2 hash invocations. It appears conservative to say that keyed message authentication codes with a b-bit digest length of 2x classical securityrating in bits will be at leastsecurityrating secure against quantum computer attacks.
Randomly keyed AES is considered a2128 classically secure approxi- mation of a random bijective permutation. At date of publication there are no known adaptive chosen plaintext or adaptive chosen ciphertext attack under a fixed unknown key that can distinguish AES from random in under2128 computations under a classical computation model. The best known related key distinguisher attack against AES128,128 is [2].
2.5 Two Sets of Security Assumptions
In this paper we will describe two methods of building block ciphers. The first family of block ciphers is built under the set of assumptionsA and the second family of block ciphers under the set of assumptionsB. The set of assumptions B result in a family of ciphers that perform more work per bit of output than under the set of assumptionsA.
Set of assumptionsA:
1. The generic attacks given by table 1 are the best generic attacks.
2. The complexities obtained when using a) an internal permutation that has a claimed classical security rating in bits at least as large as the its block size in bits, or b) constructions generated by Feistel ciphers with internal permutations that has a claimed classical security rating in bits at least as large as the its block size in bits, are both the same as the generic ones. For example, the complexities obtained when using a) the AES128,128while rated at 128-bit secure against classical attacks or b) constructions generated by Feistel ciphers based on the AES128,128 that are classically rated as secure at their block width, are both the same as the generic attacks.
Set of assumptionsB:
1. The generic attacks given by table 1 are the best generic attacks.
2. The complexities obtained when using the AES128,128as internal function of Feistel ciphers are the same as the generic ones. (In this way we restrict the second assumption of setAto just the AES128,128.)
2.6 Building Ciphers under the Set of Assumptions A
2x block width ciphers. In this section we construct new permutations under the set of assumptionsA. The AES128,128 has a block widthnof 128-bits and a key length of 128-bits. To build a block cipher with a block width of 256-bits we can apply the modified AES128,129as the internal function (in fact internal per- mutation) of a balanced Feistel cipher, in which each invocation of the modified AES128,129 is independently keyed with 129-bits of entropy. The resulting con- struction is considered a ‘Balanced Feistel Network with Internal Permutations’.
Because all Feistel networks, including those based on random permutations, result in an even permutation we modify our constructing using section 2.3. The resulting function (a modified Feistel network) isG256,keylen,securitymeaning that the permutation has a block width of 256 bits, a key length ofkeylenbits and can