2
$\begingroup$

This question relates to bit flip attacks on OTP encrypted messages.

Lets say I've got a list of numbers from 0 to 2^24-1

I want to re-order the list so it has the following property:

If you start at a random (unknown) position and go forward 1 step, I want it to be as hard as possible to guess how the the value will change. Assuming the re-ordered list is known. The list is circular.

Edit: By changes I mean "which bits in the value will flip". To put it another way:

  1. Attacker knows value from list AFTER OTP is applied (they don't know the actual value)
  2. Attacker does something which they know will cause the list position to step forward 1.
  3. Attacker wants to guess what the new value will be AFTER OTP.

Examples:

  • For a simple ordered sequence 1,2,3,4... It's quite easy. If you go forward one step in the sequence, 50% of the time this will cause only the LSB to toggle. Chance of correct guess: 1/2

  • I tried a few completely random sequences and found the most common changes occurred 9-10 times. Chance of correct guess: 10/2^24.

  • 1/2^24 would be considered "perfect". Since that's the base chance of guessing without knowing anything.

So my question is. How would I go about choosing the order to maximize the difficulty of this guess.

Edit2: I will try to describe the problem using the notation from the comments.

  • Start with a list of all possible values for a 24 bit number, in order. 0,1,2,3, etc. We will call this list U.

  • We will re-order this list in some way, generating list V.

  • An index in the list is chosen at random. We will call this i.

  • An attacker has access to V, but not i

  • The attacker must guess the value Vi⊕V(i+1modn)

  • The goal is to modify the list in such a way as to maximize the difficulty of this guess.

Some thoughts: To achieve 1/2^24, each difference would have to appear exactly once. I'm not sure that's even possible.

$\endgroup$
9
  • 2
    $\begingroup$ Err Drew, I think that you might have to reword this question as it's difficult to understand what you're after exactly. Soz. $\endgroup$
    – Paul Uszak
    Apr 14 at 21:37
  • 1
    $\begingroup$ The question seems clear enough to me: We want a public probabilistic polynomial time algorithm which on input a vector $U$ of $n>0$ values $u_i$ of $b=24$ bits, generates a reordered list $V$ of values $v_i$, such that the probability of an attacker guessing $v_i⊕v_{(i+1\bmod n)}$ knowing $U$ is minimized. We can assume that probability is averaged over all indexes $i∈[0,n)$ (or equivalently, for a random secret $i$; and nearly equivalently for $i=0$, if we end the algorithm with a rotation by a random secret value). Update: but it's unclear if if $u_i=u_j⟹i=j$, and if $n=2^b$. $\endgroup$
    – fgrieu
    Apr 15 at 9:57
  • $\begingroup$ @fgrieu as I read the question the adversary actually knows $V$. But it is indeed unclear if the list is the input or we only need to find an order for $[0, 2^b)$ $\endgroup$ Apr 15 at 16:01
  • $\begingroup$ @CommandMaster: If we read « Assuming the list is known » to mean that $V$ is known, then if $i$ is known, an attacker can guess $v_i⊕v_{(i+1\bmod n)}$ with certainty. And 1/2/3 strongly suggests that an attacker knows $i$ (because to alter a ciphertext, an attacker must know where they make that alteration). That's why I'm reading « Assuming the list is known » to mean that $U$ is known, not $V$. $\endgroup$
    – fgrieu
    Apr 15 at 16:55
  • $\begingroup$ I interpreted it as $V$ being known and $i$ not, but what you're saying does make sense. OP, could you clarify? $\endgroup$ Apr 15 at 16:57

1 Answer 1

1
$\begingroup$

Let $U=\{v(0),v(1),\ldots,v(2^n-1)\}$ where $v(k)$ is the binary vector representing the integer $n,$ and each $v(i) \in \{0,1\}^n,$ which we can take as $GF(2)^n$ for convenience.

Almost Perfect Nonlinear functions.

A function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is APN if the multiset $$\{f(x)\oplus f(x\oplus a): x \in \{0,1\}^n\},$$ has half the possible vectors in $\{0,1\}^n$ occur twice (hence another half are missing). By symmetry if $f(x)=f(x\oplus a)\oplus f(x)$ then $x'=x\oplus a$ is also a solution of the equation so we always get 2 solutions in characteristic 2 (i.e., binary arithmetic) and this is the best possible, perfect distribution of differences is impossible in binary. That means the difference with the next value is equidistributed on half the possible values, which is quite good, since you choose the point i at random and this holds for all $i$.

Here we wish to have $n=m.$ Unfortunately, we must have $n$ odd for an APN permutation to exist. For example, the map $x\mapsto x^{2^n-2}$ which is used in AES Sbox for $n=8$ is APN for any $n$ which is odd.

Therefore, if you were ready to use $n=23$ or $n=25$ you'd be done and get the APN property.

I demonstrate this with the magma script below for $n=3$. You can run it at http://magma.maths.usyd.edu.au/calc/ I know SageMath and pari/gp can also do the same but magma is what I am familiar with. See here for more.

Since $x^7=1$ for all $x$ in $GF(2^3)$ (multiplicative group has order 7 and thus all elements have order dividing 7) the map usually shown as the inverse map for nonzero elements is actually $x\mapsto x^6.$

K:=GF(2); F:=ext<K|3>; F;

"list of field elements";

[u: u in F];

"corresponding vectors";

[Eltseq(u): u in F];

"list of XORs of vectors with the next element";

[Eltseq(u+u^6): u in F];

"permutation you want";

[Eltseq(u^6): u in F];

Output is below with probability of correctly guessing the next element being $1/2^{n-1}.$

enter image description here

Oops, here is the permutation you want listed:

[ [ 0, 0, 0 ], [ 1, 0, 0 ], [ 1, 0, 1 ], [ 1, 1, 1 ], [ 0, 1, 1 ], [ 1, 1, 0 ], [ 0, 0, 1 ], [ 0, 1, 0 ] ]

References: Alex Pott has a nice set of slides here with definition but is focused on finding non-power APN permutations, i.e., not of the form $x\mapsto x^d$ which are very rare. Claude Carlet has a whole Chapter on related topics see here.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! I don't fully understand all the math yet, but I from what I do understand I believe this is the answer. Will keep working on it. $\endgroup$
    – Drew
    Apr 16 at 15:21

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.