I read that AES can be broken by solving a Linear Integer Program (IP).
- From a given encrypted text, how can one construct this IP?
- How big is the system?
$\begingroup$
$\endgroup$
10
-
$\begingroup$ 2. Too big to be easier than just brute forcing AES. $\endgroup$– NovaMar 3, 2015 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$– ddddavideeMar 3, 2015 at 14:42
-
$\begingroup$ yes i know, but i am still interested how this system look like! $\endgroup$– user3613886Mar 3, 2015 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 NACIRIMar 3, 2015 at 15:21
-
$\begingroup$ Where did you read this? Did they not give any references? $\endgroup$– mikeazoMar 3, 2015 at 15:23
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
