# How can a concatenation of $N$ block-cipher with known keys be more secure?

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\}$$
• 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? Oct 10 at 17:11
• @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). Oct 10 at 17:51
• @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. Oct 10 at 17:51