I read that AES can be broken by solving a Linear Integer Program (IP).

  1. From a given encrypted text, how can one construct this IP?
  2. How big is the system?
  • $\begingroup$ 2. Too big to be easier than just brute forcing AES. $\endgroup$ – Nova Mar 3 '15 at 14:31
  • $\begingroup$ If I am correct, every symmetric algorithm can be described by a system. The problem is the whole system is too much big to be solved. $\endgroup$ – ddddavidee Mar 3 '15 at 14:42
  • $\begingroup$ yes i know, but i am still interested how this system look like! $\endgroup$ – user3613886 Mar 3 '15 at 14:51
  • 1
    $\begingroup$ @user3613886, to make simple, each output bit is a boolean function depending of the 128-bits of input message ${x_1, \cdots, x_{128}}$ with also their ONE-Complement and the n-bits of the key ${k_1, \cdots, k_n}$ with also their ONE complement. n=128, 192 or 256 depending of the required secutity. Then each output bit can be viewed as a huge sum of these monomials. After that you can allways try to optimize with KARNAUGH or Queen-Mac Cluskey. I however warn that these method are generally limited to few number of variables $\leq 10$. $\endgroup$ – Robert NACIRI Mar 3 '15 at 15:21
  • $\begingroup$ Where did you read this? Did they not give any references? $\endgroup$ – mikeazo Mar 3 '15 at 15:23

First I find the question legitimate and trying to evaluate the complexity is not an easy problem. But regarding how it looks like, I would mention beforehand that AES or any other crypto algorithm could be written in many different ways.

See for example https://www.iacr.org/archive/asiacrypt2002/25010159/25010159.ps

BTW any crypto function appears like a map $\{0,1\}^n \times \{0,1\}^m \longrightarrow \;\{0,1\}^n$, with appropriate identification of message and key spaces. We then can mathematically modelize with the theory of boolean functions.

For a chosen m-bit key; $y_i=f_{k,i}(x_1,\cdots,x_n)=\sum_{(u_1,\cdots,u_n)}a_u.x_1^{u_1}\cdots x_n^{u_n}=\sum_u.a_ux^u$, with a compact representation where $u=(u_1,\cdots,u_n)$ and $u_i \in \{-1,0,+1\}$, and $u_i^{-1}=1-u_i$ represents the ONE-complement of the bit $u_i$.

This representation by the boolean function is to indicate the complexity of for synthetisation of a crypto algorithm (even in hardware we can easily build a circuit dedicated to DES, AES or even PKC).
The reduction methods employed in logic design analysis (KARNAUGH, QUEEN_McCLUSKEY,...) are generally limited to a restricted number of variables.
However, boolean functions is an active field of research in cryptography and attacks. See for example how Linear and Differantial cryptanalysis manage the question.

I hope this gives a general idea of this interesting question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.