0
$\begingroup$

Knowing all AES parameters (including the key k) with

$AES(m_0,k)\rightarrow c_0$
$c_0\rightarrow m_1$
$AES(m_1,k)\rightarrow c_1$
$c_1\rightarrow m_2$
...
$AES(m_{n-1},k)\rightarrow c_{n-1}$
$c_{n-1}\rightarrow m_n$

Is there any (much) faster way to compute $m_n$? (instead of computing AES $n$ times)

Or compute $n$ for given $m_0$ and $m_n$?

$\endgroup$
5
$\begingroup$

No, there is no big shortcut possible in practice, as far as we know. One would be a major blow of AES.

A small speedup is pre-computing the subkeys, which saves a small constant factor (like 2) compared to doing that computation on the fly at each iteration. Also, the first and last subkeys can be grouped into one by XOR, saving one 128-bit XOR at each iteration. We could merge the subkeys involved in the AddRoundKey step with tables implementing the SubBytes step, essentially removing AddRoundKey, at the cost of more tables. With dedicated logic, we could bring the time $t$ an iteration takes to few nanoseconds.

IF we first reach $m_i=m_0$ for $i=l<n$, then we know that $m_n=m_{n\bmod l}$ and we have already computed that value. By keeping intermediary values of $m_i$ (say, at regular interval, doubling the interval when we exceed available memory), we can find $m_n$ with little more computations. However, that occurs with probability about $2^{-128}$ for each $l$ with $0<l\le2^{128}$ if we model AES as a random permutation, thus the probability that we can use this shortcut is $\max(1,(n-1)/2^{128})$.

For very large $n$, it is conceivable to parallelize the computation, obtaining the result in sizably less time than $n\;t$. But the expected effort would be in the order of $2^{128}$ AES computations, which is perhaps a million times more than what was wasted so far in bitcoin mining, thus impractically large.

Another thing that we can do, in theory: first reduce $n$ modulo the Least Common Multiple of all possible periods $l$, that is A003418$(2^{128})$. For example, we can state with certainty that for $n=(2^{128})!+42$, we have $m_n=m_{42}$, which is pretty easy to compute. However, any $n$ allowing that shortcut is too large to store as an explicit integer.

$\endgroup$

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.