0
$\begingroup$

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\}$
$\endgroup$
3
  • $\begingroup$ I get that we apply the same block cipher $\ell$ times with different keys, the keys are known but their order is not known. But I don't get the rest of the problem statement. Do we just need to evalute such block cipher's security or ...? What are the two random numbers from a small set then? $\endgroup$
    – Fractalice
    Oct 10, 2021 at 17:11
  • $\begingroup$ @Fractalice Those are just some random numbers out of the domain. It should be hard to find an execution/key order in between them or any other combination of other random values. The security is often related to the domain size. To validate as secure it needs a certain number of steps before breaking it, lets say 2^100. I'm looking for a domain which is as small as possible but still secure. In other words the security can only by a fraction of the domain size (like for AES) and not e.g. a square root (like for EC). $\endgroup$
    – J. Doe
    Oct 10, 2021 at 17:51
  • $\begingroup$ @Fractalice I though my solution 3 may work but upon writing it I noticed I doesn't. Those are only examples how it doesn't work. Now I'm looking for an alternative way how block cipher concatenation can be as secure as AES. $\endgroup$
    – J. Doe
    Oct 10, 2021 at 17:51

0

Your Answer

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