×

Sparse Boolean equations and circuit lattices. (English) Zbl 1213.94132

Authors’ abstract: A system of Boolean equations is called sparse if each equation depends on a small number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper we study new properties of the Agreeing Algorithm, which was earlier designed to solve such equations. Then we show that mathematical description of the Algorithm is translated straight into the language of electric wires and switches. Applications to the DES and the Triple DES are discussed. The new approach, at least theoretically, allows a faster key-rejecting in brute-force than with COPACOBANA.
The paper describes a hardware implementation of the Agreeing Algorithm aimed to find solutions to a system of sparse Boolean equations, e.g. coming from ciphers. Some variables guess is introduced into the device which signals out if the system is inconsistent after that guess. The device architecture implemented with a lattice of circuits is transparent.
The paper consists of the following parts: (0) Introduction; (2) Agreeing procedure; (3) Agreeing with a circuit lattice; (4) Reduced circuit lattices; (5) Guessing the variable values; (6) DES and triple DES equations; (7) Conclusion, open problems and discussion; (8) Appendix.

MSC:

94A60 Cryptography
68Q25 Analysis of algorithms and problem complexity
94C15 Applications of graph theory to circuits and networks
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bardet M., Faugére J.-C., Salvy B.: Complexity of Gröbner basis computation for semi-regular overdetermined sequences over F 2 with solutions in F 2, Research report RR–5049, INRIA (2003).
[2] Clayon R., Bond M.: Experience using a low-cost FPGA design to crack DES keys. In: CHES 2002, LNCS 2523, pp. 579–592, Springer-Verlag (2002). · Zbl 1019.68543
[3] Courtois N., Klimov A., Patarin J., Shamir A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Eurocrypt 2000, LNCS 1807, pp. 392–407, Springer-Verlag (2000). · Zbl 1082.94514
[4] Courtois N.T., Bard G.V.: Algebraic Cryptanalysis of the Data Encryption Standard, Cryptology ePrint Archive: Report 2006/402.
[5] Courtois N.T., Bard G.V., Wagner D.: Algebraic and Slide Attacks on KeeLoq, Cryptology ePrint Archive: Report 2007/062. · Zbl 1154.68388
[6] Diffie W., Hellman M.: Exhaustive cryptanalysis of the NBS Data Encryption Standard. Computer 10(6), 74–84 (1977) · Zbl 05332334 · doi:10.1109/C-M.1977.217750
[7] Electronic Frontier Foundation: Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design, O’Reilly and Assotiates Inc. (1998).
[8] Faugère, J.-C.: A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), Proc. of ISSAC 2002, pp. 75–83, ACM Press (2002). · Zbl 1072.68664
[9] http://www.intel.com .
[10] http://www.semiconductor.net/article/CA6514491.html .
[11] Geiselmann W., Matheis K., Steinwandt R.: PET SNAKE: A Special Purpose Architecture to Implement an Algebraic Attack in Hardware, Cryptology ePrint Archive, 2009/222. · Zbl 1366.94495
[12] Iwama K.: Worst-case upper bounds for kSAT. The Bulletin of the EATCS 82, 61–71 (2004) · Zbl 1169.68443
[13] Kumar S., Paar C., Pelzl J., Pfeiffer G., Schimmler M.: Breaking ciphers with Copacobana-a cost-optimized parallel code breaker. In: CHES2006, LNCS 4249, pp. 101–118, Springer-Verlag(2006).
[14] Osvik D.A., Tromer E.: Cryptologic applications of the Playstation3: Cell SPEED, http://www.hyperelliptic.org/SPEED/slides/Osvik_cell-speed.pdf .
[15] Raddum H., Semaev I.: New technique for solving sparse equation systems, Cryptology ePrint Archive, 2006/475.
[16] Raddum H., Semaev I.: Solving Multiple Right Hand Sides linear equations, Designs, Codes and Cryptography, vol. 49, pp. 147–160 (2008), extended abstract in Proceedings of WCC’07, 16-20 April 2007, Versailles, France, INRIA (2007). · Zbl 1179.94067
[17] Rouvroy G., Standaert F.-X., Quisquater J.-J., Legat, J.-D.: Design strategies and modified desciptions to optimize cipher FPGA implementations: fast and compact results for DES and Triple-DES. In: FPL2003, LNCS 2778, pp. 181–193, Springer-Verlag (2003).
[18] Semaev I.: On solving sparse algebraic equations over finite fields, Designs, Codes and Cryptography, vol. 49, pp. 47–60,(2008), extended abstract in Proceedings of WCC’07, 16-20 April 2007, Versailles, France, INRIA(2007). · Zbl 1196.11171
[19] Semaev I.: Sparse algebraic equations over finite fields. SIAM J. Comput. 39, 388–409 (2009) · Zbl 1248.11105 · doi:10.1137/070700371
[20] Semaev I.: Improved Agreeing-Gluing algorithm. In: Proceedings of SCC’10, 23–25 June 2010, Royal Holloway, University of London, UK, pp. 73–88. · Zbl 1343.94080
[21] Yang B.-Y., Chen J-M., Courtois, N.: On asymptotic security estimates in XL and Gröbner bases-related algebraic cryptanalysis. In: ICICS 2004, LNCS 3269, pp. 401–413, Springer-Verlag (2004). · Zbl 1109.94353
[22] Wiener M.J.: Efficient DES key search. In: Stalling, W.R. (ed.) Practical Cryptography for Data Interworks, pp.31–79. IEEE Computer Society Press (1996).
[23] Zakrevskij A., Vasilkova I.: Reducing large systems of Boolean equations. In: 4th Int. Workshop on Boolean Problems, Freiberg University, September, pp. 21–22 (2000).
[24] Zeitzoff P.: 2007 International Technology Roadmap: MOSFET scaling challenges, Solid State Technology Magazine, February (2008).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.