0

It seems that algebraic attacks against cipher algorithms have not succeeded in practically breaking ciphers. The reason primarily is that the algebraic models of ciphers under with a known plaintext ciphertext pair and unknown key bits are too complex both in structure and number of variables. However if number of variables are brought down in a model to a sufficiently small number then it is possible to find structural weaknesses of equations or systematic algebraic heuristics of solution algorithms to find key bits. Although current algebraic models of AES have 9000+ variables and equations, these models contain mostly latent variables which can be eliminated algebraically offline. Hence in principle a 128 variable model of AES128 with a given plaintext ciphertext pair of blocks can be developed from an offline algebraic model. Should this not be a warning that AES can in principle be broken even with classical computers? Some agencies might already have such models.

Viren Sule
  • 141
  • 6
  • There are successfully broken ones like Keeloq. Your sentence these models contain mostly latent variables which can be eliminated algebraically offline requires a reference. You write in a way that there is an algebraic attack that breaks the AES. – kelalaka Nov 03 '19 at 07:54
  • Yes Keeloq is a success story. The number of variables were small enough in the Keeloq model. I have reported another such success by estimating a complete 80 bit key recovery in practically feasible time and memory (a paper is accepted in SPACE 2019 conference). This break was achieved by parallel solution to a system of Boolean equations in 177 variables. Elimination of variables in Boolean equations is a well established theory as presented in the book by F.M.Brown, Boolean Reasoning, The Logic of Boolean Equations, Dover, 2003. – Viren Sule Nov 03 '19 at 11:40
  • Actually, the number of variables is not small, but Bard noticed a structure and exploited that. – kelalaka Nov 03 '19 at 12:32
  • Thanks for your comments. I am sure there were algebraic structural properties which must have been most effective in cryptanalysis of Keeloq. I dont remember the number of variables in Keeloq equations. So my guess that they may be small is possibly not correct. – Viren Sule Nov 03 '19 at 15:38
  • Related https://crypto.stackexchange.com/questions/76725/symbolic-computation-in-finite-fields – hola Sep 12 '20 at 13:17

0 Answers0