Score:0

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

at flag

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\}$
Fractalice avatar
in flag
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?
J. Doe avatar
at flag
@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).
J. Doe avatar
at flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.