$$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)
