A Comparison of Local Reduction and Sat-Solver Based Algebraic Cryptanalysis of Jh And Keccak

Adamček, Peter; Loderer, Marek; Zajac, Pavol

doi:10.2478/v10127-012-0036-6

Abstract

Local reduction methods can be used to assess the resistance of cryptosystems against algebraic attacks. The assessment is based on the separation of the attack into polynomial-time reduction algorithm, and exponential time guessing and backtracking. This approach is similar to that employed by the DPLL algorithm that is used as a core of various modern SAT-solvers. In the article we show the application of this method to evaluate the strength of (reduced versions of) two chosen SHA-3 candidates: JH, and Keccak, respectively. We compare the complexity estimates with the behavior of the full search algorithm. We also compare the results based on the local reduction with the attack based on the use of SAT-solvers PrecoSAT, and CryptoMiniSAT, respectively.

References

[1] ADAMČEK, P.: Cryptanalysis of Keccak. Master’s Thesis. Slovak University of Technology in Bratislava, 2012. (In Slovak)
Search in Google Scholar
[2] BARD, G. V.: Algebraic Cryptanalysis, Springer, Dordrecht, 2009.10.1007/978-0-387-88757-9
Search in Google Scholar
[3] BERTONI, G. - DAEMEN, J.- PEETERS, M.- VAN ASSCHE, G.: The Keccak reference, Tech. Report, 2011, http://keccak.noekeon.org/Keccak-reference-3.0.pdf.
Search in Google Scholar
[4] BIERE, A.: Lingeling, Plingeling, PicoSAT and PrecoSAT at SAT Race 2010, Tech. Report, Institute for Formal Models and Verication, Johannes Kepler University, Linz, Austria, 2010.
Search in Google Scholar
[5] COURTOIS, N. T. - BARD, G. V.: Algebraic cryptanalysis of the data encryption standard, in: Cryptography and Coding (S. Galbraith, ed.), Lecture Notes in Comput. Sci. Vol. 4887, Springer Berlin, 2007, pp. 152-169, http://dx.doi.org/10.1007/978-3-540-77272-9_10.10.1007/978-3-540-77272-9_10
Search in Google Scholar
[6] COURTOIS, N. T.: Algebraic complexity reduction and cryptanalysis of GOST, Cryptol-ogy ePrint Archive, Report 2011/626, http://eprint.iacr.org/.
Search in Google Scholar
[7] COURTOIS, N. T. - BARD, G. V. - WAGNER, D.: Algebraic and slide attacks onKeeLoq, Cryptology ePrint Archive, Report 2007/062, http://eprint.iacr.org/.
Search in Google Scholar
[8] DAVIS, M. - LOGEMANN, G. - LOVELAND, D.: A machine program for theorem-proving, Commun. ACM 5 (1962), 394-397, http://doi.acm.org/10.1145/368273.368557.
Search in Google Scholar
[9] GEISELMANN, W. - MATHEIS, K. - STEINWANDT, R.: PET SNAKE: A special purpose architecture to implement an algebraic attack in hardware, Cryptology ePrint Archive, Report 2009/222, http://eprint.iacr.org/.10.1007/978-3-642-17499-5_12
Search in Google Scholar
[10] IMPAGLIAZZO, R. - PATURI, R.: The Complexity of k-SAT, in: Computational Complexity, Annual IEEE Conference 1999, IEEE Computer Society, Los Alamitos, CA, USA, pp. 237-240.
Search in Google Scholar
[11] LODERER, M.: Cryptanalysis of JH function. Master’s Thesis, Slovak University of Technology in Bratislava, 2012. (In Slovak)
Search in Google Scholar
[12] MORAWIECKI, P.- SREBRNY, M.: A SAT-based preimage analysis of reduced KECCAK hash functions, Cryptology ePrint Archive, Report 2010/285, 2010, http://eprint.iacr.org/.
Search in Google Scholar
[13] RADDUM, H.: Cryptanalytic results on TRIVIUM. Tech. Report 2006/039, eSTREAM, ECRYPT Stream Cipher Project, 2006.
Search in Google Scholar
[14] RADDUM, H.- SEMAEV, I.: New technique for solving sparse equation systems, Cryp-tology ePrint Archive, Report 475/2006, http://eprint.iacr.org/2006/475.
Search in Google Scholar
[15] SCHILLING, T. - RADDUM, H.: Solving equation systems by agreeing and learning, in: Arithmetic of Finite Fields (M. Hasan, T. Helleseth, eds.), Lecture Notes in Comput. Sci. Vol. 6087, Springer, Berlin, 2010, pp. 151-165. http://dx.doi.org/10.1007/978-3-642-13797-6_11.10.1007/978-3-642-13797-6_11
Search in Google Scholar
[16] SCHILLING, T. - ZAJAC, P.: Phase transition in a system of random sparse Booleanequations , Tatra Mt. Math. Publ. 45 (2010), 93-105.
Search in Google Scholar
[17] SEMAEV, I.: On solving sparse algebraic equations over finite fields, Des. Codes Cryptography 49 (2008), 47-60.10.1007/s10623-008-9182-x
Search in Google Scholar
[18] SEMAEV, I.: Sparse algebraic equations over finite fields, SIAM J. Comput. 39 (2009), 388-409.10.1137/070700371
Search in Google Scholar
[19] SEMAEV, I.: Improved agreeing-gluing algorithm, Cryptology ePrint Archive, Report 140/2010, http://eprint.iacr.org/2010/140.
Search in Google Scholar
[20] SOOS, M.: CryptoMiniSat2, 2012, http://www.msoos.org/cryptominisat2/.
Search in Google Scholar
[21] VALKY, G.- LEHOCKI, F.: Modern approach in multiple patients ECG monitoring, in: BHI, IEEE, 2012, pp. 131-134.
Search in Google Scholar
[22] WU, H.: The hash function JH, Submission to NIST (round 3), (2011), http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf.
Search in Google Scholar
[23] ZAJAC, P.: Local reduction in evaluation of cipher security, 2012 (preprint).
Search in Google Scholar
[24] ZAJAC, P.: Solving trivium-based Boolean equations using the method of syllogisms, Fund. Inform. 114 (2012), 359-373.
Search in Google Scholar
[25] ZAJAC, P.: On the use of the method of syllogisms in algebraic cryptanalysis, in: Proceedings of the 1st Plenary Conference of the NIL-I-004, University of Bergen, 2009, pp. 21-30.
Search in Google Scholar
[26] ZAJAC, P.: Implementation of the method of syllogisms, 2010 (preprint).
Search in Google Scholar
[27] ZAJAC, P. - ČAGALA, R.: Local reduction and the algebraic cryptanalysis of the blockcipher GOST, Period. Math. Hungar. 65 (2012), 239-255.10.1007/s10998-012-6376-9
Search in Google Scholar
[28] ZAKREVSKIJ, A. - VASILKOVA, I.: Reducing large systems of Boolean equations, in: 4th International Workshop on Boolean Problems, Freiberg University, 2000, pp. 21-22.
Search in Google Scholar

A Comparison of Local Reduction and Sat-Solver Based Algebraic Cryptanalysis of Jh And Keccak

Abstract

Paradigm

My account