Abstract
In this paper, we introduce Constraint Programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. The problem is solved in two steps: In Step 1, bytes are abstracted by binary values; In Step 2, byte values are searched. We introduce two CP models for Step 1: Model 1 is derived from AES rules in a straightforward way; Model 2 contains new constraints that remove invalid solutions filtered out in Step 2. We also introduce a CP model for Step 2. We evaluate scale-up properties of two classical CP solvers (Gecode and Choco) and a hybrid SAT/CP solver (Chuffed). We show that Model 2 is much more efficient than Model 1, and that Chuffed is faster than Choco which is faster than Gecode on the hardest instances of this problem. Furthermore, we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution.
This research was conducted with the support of the FEDER program of 2014-2020, the region council of Auvergne, and the Digital Trust Chair of the University of Auvergne.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The upper bound \(\frac{l}{6}\) comes from the fact that \(D_{\alpha ,\beta }\le 2^{-6}, \forall (\alpha ,\beta )\ne (0^8,0^8)\), and probability \(p_2\) must be larger than \(2^{-l}\) which corresponds to a probability with uniform distribution of the \(2^l\) possible keys.
- 2.
We tried other parameter settings. The best results were obtained with default ones.
- 3.
Let us recall that it has been shown in [3] that it is useless to try to solve the problem for more than 5 rounds when the key length is \(l=128\).
References
Biham, E.: New types of cryptanalytic attacks using related keys. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 398–409. Springer, Heidelberg (1994)
Biham, E., Shamir, A.: Differential cryptanalysis of feal and N-Hash. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 1–16. Springer, Heidelberg (1991)
Biryukov, A., Nikolić, I.: Automatic search for related-key differential characteristics in byte-oriented block ciphers: application to AES, Camellia, Khazad and others. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 322–344. Springer, Heidelberg (2010)
Chu, G., Stuckey, P.J.: Chuffed solver description (2014). http://www.minizinc.org/challenge2014/description_chuffed.txt
Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, Heidelberg (2002)
De, D., Kumarasubramanian, A., Venkatesan, R.: Inversion attacks on secure hash functions using sat solvers. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 377–382. Springer, Heidelberg (2007)
Fages, J.-G.: On the use of graphs within constraint-programming. Constraints 20(4), 498–499 (2015)
FIPS 197. Advanced Encryption Standard. Federal Information Processing Standards Publication 197. U.S. Department of Commerce/N.I.S.T (2001)
Fouque, P.-A., Jean, J., Peyrin, T.: Structural evaluation of AES and chosen-key distinguisher of 9-round AES-128. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 183–203. Springer, Heidelberg (2013)
Team, G.: Gecode: Generic constraint development environment (2006). http://www.gecode.org
Karpman, P., Peyrin, T., Stevens, M.: Practical free-start collision attacks on 76-step SHA-1. IACR Cryptology ePrint Archive 2015:530 (2015)
Legendre, F., Dequen, G., Krajecki, M.: Encoding hash functions as a sat problem. In: IEEE 24th International Conference on Tools with Artificial Intelligence, ICTAI 2012, Athens, Greece, 7–9 November 2012, pp. 916–921. IEEE (2012)
Michel, L.D., Van Hentenryck, P.: Constraint satisfaction over bit-vectors. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 527–543. Springer, Heidelberg (2012)
Minier, M., Solnon, C., Reboul, J.: Solving a Symmetric Key Cryptographic Problem with Constraint Programming. In: ModRef 2014, Workshop of the CP 2014 Conference, September 2014, Lyon, France, July 2014
Mironov, I., Zhang, L.: Applications of SAT solvers to cryptanalysis of hash functions. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 102–115. Springer, Heidelberg (2006)
Morawiecki, P., Srebrny, M.: A sat-based preimage analysis of reduced keccak hash functions. Inf. Process. Lett. 113(10–11), 392–397 (2013)
Mouha, N., Wang, Q., Gu, D., Preneel, B.: Differential and linear cryptanalysis using mixed-integer linear programming. In: Wu, C.-K., Yung, M., Lin, D. (eds.) Inscrypt 2011. LNCS, vol. 7537, pp. 57–76. Springer, Heidelberg (2012)
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.R.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007)
Prudhomme, C., Fages, J.-G.: An introduction to choco 3.0: an open source java constraint programming library. In: CP Workshop on CP Solvers: Modeling, Applications, Integration, and Standardization (2013)
Soos, M., Nohl, K., Castelluccia, C.: Extending SAT solvers to cryptographic problems. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol. 5584, pp. 244–257. Springer, Heidelberg (2009)
Sun, S., Hu, L., Wang, M., Yang, Q., Qiao, K., Ma, X., Song, L., Shan, J.: Extending the applicability of the mixed-integer programming technique in automatic differential cryptanalysis. In: López, J., Mitchell, C.J. (eds.) ISC 2015. LNCS, vol. 9290, pp. 141–157. Springer, Heidelberg (2015)
Sun, S., Hu, L., Wang, P., Qiao, K., Ma, X., Song, L.: Automatic security evaluation and (related-key) differential characteristic search: application to SIMON, PRESENT, LBlock, DES(L) and other bit-oriented block ciphers. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 158–178. Springer, Heidelberg (2014)
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Wang, X., Yu, H., Yin, Y.L.: Efficient collision search attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
Acknowledgements
Many thanks to Jean-Guillaume Fages, for sending us Choco 4 before the official public release, and to Yves Deville, Pierre Schaus and François-Xavier Standaert for enriching discussions on this work.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendices
Appendix
A Solution with \(obj=12\) Active S-Boxes for AES with \(r=4\) Rounds and \(l=128\) Bits
The byte-consistent binary solution is displayed below. Each binary variable assigned to 1 is colored in blue, and is surrounded in red when it belongs to the objective function (i.e., it passes through an S-box).
The optimal byte solution is displayed below, in hexadecimal notation.
Round | \(\delta X = X \oplus X'\) | \(\delta K = K \oplus K'\) |
|---|---|---|
Init | 0d151846 0dacf2f2 0dfff2f2 0dacf2f2 | |
0 | 00000000 00ac0000 00000000 00ac0000 | 0d151846 0d00f2f2 0dfff2f2 0d00f2f2 |
1 | 00000000 00ff0000 00ff0000 00000000 | 0dfff2f2 00ff0000 0dfff2f2 00000000 |
2 | 00000000 00ff0000 00000000 00000000 | 0dfff2f2 0d00f2f2 00000000 00000000 |
3 | 00000000 00ff0000 00ff0000 00ff0000 | 0dfff2f2 00ff0000 00ff0000 00ff0000 |
End/4 | fa000000 faff0000 fa000000 f700f2f2 | f7fff2f2 f700f2f2 f7fff2f2 f700f2f2 |
The corresponding plaintexts X and \(X'\) and keys K and \(K'\) are displayed below, in hexadecimal notation. The probability \(p_2\) associated with these plaintexts and keys is \(p_2=2^{-79}\) whereas it is equal to \(p_2=2^{-81}\) in the solution given in [3, 9] (solution with \(obj=13\) active S-boxes).
Round | K | \(K'\) |
|---|---|---|
0 | 00000000 00000000 00000000 00000000 | 0d151846 0d00f2f2 0dfff2f2 0d00f2f2 |
1 | 62636363 62636363 62636363 62636363 | 6f9c9191 629C6363 6f639191 62636363 |
2 | 9b9898c9 f9fbfbaa 9b9898c9 f9fbfbaa | 96676a3b f4fb0958 9b9898c9 f9fbfbaa |
3 | 90973450 696ccffa f2f45733 0b0fac99 | 9d68c6a2 6993cffa f2b5733 0bf0ac99 |
4 | ee60da7b 876a1581 759e42b2 7e91ee2b | 19f92889 706ae773 8261b040 89911cd9 |
Round | X | \(X'\) |
|---|---|---|
Init. | 6b291f8d a800d3d7 f239d5a4 510035ef | 663c07cb a5ac2125 ffc62756 5cacc71d |
0 | 6b291f8d a800d3d7 f239d5a4 510035ef | 6b291f8d a8acd3d7 f239d5a4 51ac35ef |
1 | e5000327 00796300 0079005c 0000005a | e5000327 00866300 0086005c 0000005a |
2 | 2e2de80b 5186a759 e0d3cbb2 2b02c803 | 2e2de80b 5179a759 e0d3cbb2 2b02c803 |
3 | 5a74f2ae b979ce4a e286aa6a ea86647b | 5a74f2ae b986ce4a e279aa6a ea79647b |
End | c501f2fa 4095b6af cdd8f67b 4fadf0a4 | 3f01f2fa ba6ab6af 37d8f67b b8ad0256 |
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Gerault, D., Minier, M., Solnon, C. (2016). Constraint Programming Models for Chosen Key Differential Cryptanalysis. In: Rueher, M. (eds) Principles and Practice of Constraint Programming. CP 2016. Lecture Notes in Computer Science(), vol 9892. Springer, Cham. https://doi.org/10.1007/978-3-319-44953-1_37
Download citation
DOI: https://doi.org/10.1007/978-3-319-44953-1_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44952-4
Online ISBN: 978-3-319-44953-1
eBook Packages: Computer ScienceComputer Science (R0)