Performance of various SMT Solvers in Cryptanalysis
Praveen Kumar Gundaram, Appala Naidu Tentu, Naresh Babu Muppalaneni · 2021 International Conference on Computing, Communication, and Intelligent Systems (ICCCIS) · 2021
Satisfiability (SAT) or Satisfiability Modulo Theories (SMT) are important verification tools and attracting attentions several domains and recently in cryptanalysis of ciphers. Technology of SAT solver has extraordinary advancement in the most recent decade, and the new innovation called SMT solver is also emerged as an impact of them.In this paper, we presented the applications of various SMT solvers in block cipher cryptanalysis. We formulated an algorithm for algebraic attack of block ciphers. In this attack, we represent encryption procedure of block cipher in terms of boolean representations and convert these into a suitable format (i.e. SMT-LIB and Z3py) accepted by respective SMT solvers. Our attack requires a few plain text-cipher text pairs to retrieve the master secret key. We apply the proposed procedure to demonstrate the cryptanalysis of SIMON upto certain rounds. Finally, we solve these boolean formulas using various serial and parallel SMT solvers and compared their performances.