General problem / Intro: encrypting the (computable) relation in between two random numbers which are members of a as small as possible set while anything except the order of execution is known to the adversary.
This question is about solving that problem with a concatenation of block-cipher.
Simplification:
- we only consider block-cipher which are similar to AES
- instead of $N$ different block-cipher we using one block-cipher with $N$ different keys (or even more)
- the block-cipher only transfer one input to another (so they run in ECB mode)
What is known:
If we apply a block-cipher $BC$ to a given input $m$ over and over again we will reach the input at some point again.
$$BC^l(m,k) = m$$
For a given random input $m$ and key $k$ the cycle length $l$ can be every length from $1$ to the size of the domain of $m$ with (in optimal case) same probability each.
(pretty sure that's also the case:)
If we use $N$ different keys and concatenate block-cipher with those keys on each other (always same order & always multiple of $N$ steps) we result in cycle lengths $N$ times $[1,..,D]$ with $D$ the size of the domain of m.
$$BC(....BC(...BC(..BC(BC(BC(m,k_0),k_1),k_2)..,k_{N-1})...,k_{i \mod{N}})....,k_{l \equiv N-1 \mod{N}}) = m$$
We can see this concatenation as applying rounds inside a single BC.
Applying it to the general problem from above:
For this the order of execution (so the order of used keys) is unknown to the adversary (but the keys themselves are known).
For example a value $V$ can be computed out of value $W$ with: $$BC(BC(BC(BC(BC(W,k_5),k_2),k_3,k_5,k_1,k_1) =V$$
The adversary does know $V,W$ and also ever key by itself but he want to know the key execution order $5,2,3,5,1,1$ or any other order which also does the job.
If we use no fixed key order anymore the cycle size properties are not valid anymore.
Solution trial 1 (failed):
If the adversary want to find a execution order which transfers $W \rightarrow V$ he can compute the $N$ possible next values of $W$ and the $N$ possible previous values of $V$ with the inverse BC. He can repeat this until a mach has been found.
With this he should find an execution order in mean by about $\sqrt{D}$ steps which is not secure enough.
Solution trial 2 (failed):
To higher security we limit result $V$ to values which have been computed with using the $i$-th key at their last BC computation.
The adversary can just use the inverse BC at this $V$ with the target $i$-th key and do the same as in solution trial 1.
Solution trial 3 (question/edit: failed...):
To gain security we can limit the execution number to multiple of $E$ steps and with this also altering the keys of each depth.
Besides using the $i$-th BC key for computation of $V$ it now also need to be a multiple of $E$ steps ahead of $W$
in our example from above with $E=3$ that would be: $$BC(BC(BC(BC(BC(W,k_5^0),k_2^1),k_3^2,k_5^0,k_1^1,k_1^2) =V$$
So for a given $V$ with $i$-th last key at depth $d$ the adversary can compute the relation to a given $W$ with depth $d$:
Computing the inverse of $V$: $$BC^{-1}(V,k_i^{d-1 \mod E}) = V'$$
And compute the values step-by-step as he did in solution trial 1.
This should take about $N^{\lfloor{\frac{E-1}{2}}\rfloor}$ trials if he is doing it brute force.
If for example $D=2^{128}, N=2^{16}, E=2^{5}$ this would be $2^{16 \cdot 15} = 2^{240}$ trials.
.... after writing this whole text I noticed he don't need to compute every part of every depth and just needs $\sqrt{D}$ steps again...
=====> Question: Does someone has any other idea how a concatenation of block-cipher can be more secure (close to $D$)?
Histroy
- $D$ size of input and output set
- $V,W$ random values which can have up to $D$ different values
- $E$ total number of block cipher executions need to be multiple of $E$
- $N$ number of different block-cipher keys for each depth
- $k_a^b$ key variable used for block-cipher with indices $a,b$ with $a\in\{0,N-1\}, b\in\{0,E-1\}$
