Attacker has to win following game by distinguishing that output was updated by a certain function or not?

  1. Attacker queries an oracle for the output.

  2. Oracle generates fresh 4 random bytes $a$, $b$, $c$, and $d$ and one random bit $x$.

  3. if $x=0$, Oracle outputs values of $a$, $b$, $c$, and $d$.

  4. if $x=1$, it first updates the values using following equations (applied sequentially) and then outputs updated values of $a$, $b$, $c$, and $d$. $$\begin{align} a &= (a + dc) \bmod 256;\\ b &= (b + ad) \bmod 256;\\ c &= (c + ba) \bmod 256;\\ d &= (d + cb) \bmod 256;\\ \end{align}$$

  5. Goal of attacker is to find that output was result of step 3 or 4?

*Attacker can make infinite queries.

Example: if a=0, b=0, c=1, d=1 and x=1 at step 2, then Oracle outputs 1,1,2,3.

  • $\begingroup$ What is the attacker objective?What is the Profit/gain or utility fn? $\endgroup$
    – ShAr
    Jun 25 at 17:41
  • $\begingroup$ @ShAr updated the question. $\endgroup$
    – elonnoe
    Jun 25 at 20:08
  • $\begingroup$ I answered, but I think this Q is better suited in Computer Science or game Theory/number thorey for the mod operations if there's ones. Anyways, this is just an opinion not voting anything $\endgroup$
    – ShAr
    Jun 26 at 4:28
  • 1
    $\begingroup$ The problem statement at 4 is unclear about if the equations are applied sequentially, or as a bloc, E.g. if at step 2 a=0, b=0, c=1, d=1, x=1 does the oracle output 1,1,2,3 or 1,0,1,1 ? The first reading makes the problem easier: what does each change make to the distribution of what it changes? The second reading is more interesting. Hint: explore what happens for the low-order bit, then the second one. That's enough to win the game, but not get the best advantage. To ponder: $(\mathbb Z_{2^k},+,\cdot)$ is a field only when $k=0$. If you want help, tell us what you did, where you are stuck! $\endgroup$
    – fgrieu
    Jun 26 at 10:30
  • $\begingroup$ @fgrieu I updated the question to address your query. I computed frequency of each possible value for each output byte and least significant bit of each output byte, but couldnt find any pattern in it. Since attacker has no control on input bytes and Oracle generates fresh random bytes each time it is queried, the output of step 4 appears random!!!. $\endgroup$
    – elonnoe
    Jun 26 at 14:55

Let $f(a,b,c,d)$ denote your transformation in step 4. It is the sequential composition of these 4 steps:

  1. $(a,b,c,d) \mapsto (a+dc \bmod 256,b,c,d)$
  2. $(a,b,c,d) \mapsto (a,b+ad \bmod 256,c,d)$
  3. $(a,b,c,d) \mapsto (a,b,c+ba \bmod 256,d)$
  4. $(a,b,c,d) \mapsto (a,b,c,d+cb \bmod 256)$

Note that each step is invertible. For instance, the first step is invertible as $(a',b,c,d) \mapsto (a'-dc \bmod 256,b,c,d)$. Hence, the entire transformation $f(a,b,c,d)$ is invertible.

Since the distribution over $(a,b,c,d)$ is initially uniform and $f$ is invertible, the distribution on $f(a,b,c,d)$ is uniform too. That means: regardless of $x=0$ or $x=1$, the output is uniform, so a distinguisher has no advantage guessing $x$.

  • $\begingroup$ Yes. The case where the transformation is $a'=(a+dc)\bmod256$, $b'=(b+ad)\bmod256$, $c'=(c+ba)\bmod256$, $d'=(d+cb)\bmod256$ followed by $a=a'$, $b=b'$, $c=c'$, $d=d'$ is more difficult/interesting. Now there's a non-negligible advantage to compute. $\endgroup$
    – fgrieu
    Jun 27 at 8:37
  • $\begingroup$ so that holds true for any invertible f? $\endgroup$
    – crypt
    Jun 29 at 6:19
  • Probability of winning from 1st trial =0.5 (pure guessing assuming uniform random X values 0 or1)

  • Probability of winning at 2nd trial given he knows the output of the 1st trial= 1 - prob[((a=a+dc)mod256) AND ((b=b+ad) mod256) AND ((c=c+ba) mod256) AND ((d=d+cb) mod256)]

As a start for these formulas to be ≥256 (reach the same value thru mod operation) at least 3 of the 4 values must be ≥128

In fact they must contain(not just be larger or equal) enough powers of 2 (dc=n•256, ad=m•256, ab=k•256, cb=l•256)

.... and so on, however I think to go further check if the values must be stored in one byte; ie by default a,b,c,d < 256?

»»» In the case of step2 is repeated every trial, then I guess the only way the adversary gains from knowing the function ( change his winning probability to more than 0.5 pure guessing) is if the given formulas r not uniform random, ie if u can prove modified a,b,c,d are skewed towards more 1s or more 9s, maybe the probability of winning should increase by the decrease in the degree of Randomness.

  • $\begingroup$ The probability to win depends on how we read the problem statement for step 4, and on the strategy used by the adversary (to be determined). With these two things fixed, since the trials are independent, the probability to win can't depend on the trial number, as asserted in the current answer. $\endgroup$
    – fgrieu
    Jun 26 at 10:35
  • $\begingroup$ Indeed if u made 2 successive trials & found the output is different u can have 100% winning by saying X=1 meaning the adversary had an advantage at least in this case by knowing the game underlying fn $\endgroup$
    – ShAr
    Jun 26 at 10:48
  • $\begingroup$ Step 2 is performed, and generates fresh a, b, c, d, x, before step 3 or step 4 each time these are reached. Thus knowing two outputs are different is not enough to conclude on x in either the first or second output. More generally, there's no point in comparing outputs of different experiments, since they are independent. The question is about devising a strategy that gives an advantage, and that will be at each experiment, independently. As I explain in comment to the Q, that's possible or not depending on how we read step 4, and there are two ways. $\endgroup$
    – fgrieu
    Jun 26 at 13:05
  • $\begingroup$ Aha Ok, sorry, I thought (solved on the basis that) step2 is done once only like a seed for a random number generator $\endgroup$
    – ShAr
    Jun 26 at 13:20
  • $\begingroup$ @ShAr no, step 2 is performed again for each new query. $\endgroup$
    – elonnoe
    Jun 26 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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