1
$\begingroup$

$$f_0 = A$$ $$f_{n+1}=AES(f_n,k_n)$$ $$f_i = B$$

For given 128-bit values $A, B$ we want to find a chain of suitable 128-bit keys $k_1$ to $k_i$.
The total length $i$ is undetermined. Every valid key chain size gets accepted.


How long will it take?
If we limit $i=1$ it would be equal to the normal use case. $$B = AES(A,k_1)$$ Finding the 128-bit key $k_1$ for given $A, B$ would take in mean $\approx 2^{126}$ steps (wiki).

But as soon as we allow another chain element it will get much easier.
e.g. for $i=2$ it would be $$B = AES(AES(A,k_1),k_2)$$ To find $k_1, k_2$ we can just start from both directions and generate values $a_m, b_n$ $$AES(A,k_{1,m}) = a_m$$ $$AES^{-1}(B,k_{2,n}) = b_n$$ until we find some intersection of their value sets $\{a_m\}$ and $\{b_n\}$. In mean this should take $\approx \sqrt{\pi} \cdot 2^{64}$ steps (stack).
This would be not secure anymore.


Can we improve the security by limiting the key space?
To avoid those $\approx 2^{64}$ $a_m, b_n$ we could reduce the possible options of progression by limiting the key space to e.g. $2^{32}$ values. For AES128 the other 96 values could be e.g. always $0$.
With this we can only produce $\approx 2^{32}$ different values out of $A$ and $B$ each. They won't match up for most pairs $A, B$.
However if we increase the chain length to $i=4$ every of those $2^{32}$ values can again produce another $2^{32}$ values.
In total $\approx 2^{64}$ which makes an intersection much more likely again.

--> it can not


How about a filter function?
Given any $C,D,k$ in $$ D = AES(C,k)$$ We call this connection/key valid if a filter function $g = 1$ $$ g ( C,D,k) = \begin{cases} 1 & \text{in rare cases } 1:2^{24} \text{combinations from } C,D,k\\ 0 & \text{otherwise} \end{cases}$$

Given this, starting from $A, B$ we can only produce about $2^{8}$ most likely new values but have to compute $2^{32}$ different keys for it.
We have to increase the total chain length $i$ to $> 16$ to reach those $\sqrt{\pi}\cdot 2^{64}$ necessary members for an intersection.

For $i=16$ with in mean $\approx 2^{64}$ members for both sides we would have to compute AES $\approx 2^{88}$ times.

$2^{88}$ no high security but far better then $2^{64}$. Example values could be tweaked for more security.


Questions
Are those step counts (round about) correct? Or does exist any significant faster way to do it?
If e.g. the keys can only be a small number of different values are there any security shortcomings here?


Further details:
Different to usual AES use case we do not want to encrypt any plain text message here. The goal is to encrypt the relation in between 128-bit values for everyone. So AES is in ECB mode here.
There need to be:

  • a fast way to proof if a chain connection is correct (< 1 sec at normal desktop PC)
  • Given $A$ it should be not too easy/hard to find any connection (> 1sec, < 10h)
  • Given $A$ and $B$ it should be as hard as possible to find a connection in between them
  • (The total number of different values (like $A,B$) should be a small as possible. I think it can't be much less than 128 bit)
  • (edited: need to be symmetric. If A->B is known B->A will use the same keys in opposite order)
$\endgroup$

1 Answer 1

1
$\begingroup$

If you want to prevent meet-in-the-middle attacks, the most straight-forward approach would to make the 'forward' direction noninvertable, such as:

$$f_{n+1} = AES( f_n, k_n ) \oplus f_n$$

From what I can see, that change still meets your requirements...

$\endgroup$
4
  • $\begingroup$ Thank you for the post but I'm sorry I forgot to mention this. It need to be invertible using the same keys in opposite order. $\endgroup$
    – J. Doe
    Jan 4, 2023 at 22:46
  • $\begingroup$ But btw for $i=1$ would this be less secure than normal AES? This function can not reach every value B. $\endgroup$
    – J. Doe
    Jan 4, 2023 at 22:59
  • 1
    $\begingroup$ @J.Doe: actually, with the original algorithm with $i=1$, you also cannot reach every value $B$ with a fixed $A$; $\text{AES}(A, K)$ is not (unlikely to be) a permutation on $K$ $\endgroup$
    – poncho
    Jan 5, 2023 at 14:39
  • $\begingroup$ thanks for the hint. Did not thought about this. Given a random 128-bit input $A$ the expected proportion of values in reach using every 128-bit key $K$ should only be $1-e^{-1}$ or $\approx 63\%$ $\endgroup$
    – J. Doe
    Jan 5, 2023 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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