Score:2

Crypto

Advantage of Adversary against a simple function?

elonnoe

10/25/22, 5:09 PM

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

Attacker queries an oracle for the output.
Oracle generates fresh 4 random bytes $a$, $b$, $c$, and $d$ and one random bit $x$.
if $x=0$, Oracle outputs values of $a$, $b$, $c$, and $d$.
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}$$
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.

113

2 + 7

randomness

ShAr

10/25/22, 5:41 PM

What is the attacker objective?What is the Profit/gain or utility fn?

elonnoe

10/25/22, 8:08 PM

@ShAr updated the question.

ShAr

10/26/22, 4:28 AM

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

fgrieu

10/26/22, 10:30 AM

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!

elonnoe

10/26/22, 2:55 PM

@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!!!.

fgrieu

10/26/22, 3:24 PM

This is correct: with the equations applied sequentially, there is no way to distinguish 3 from 4. That's because each of the four changes leaves the distribution of $(a,b,c,d)$ uniform (argument: in any group with law $\boxplus$, it's enough that $u$ is uniformly random and independent of $v$ for $u\boxplus v$ to be uniformly random). Not so for `(a,b,c,d)=((a+d*c)%256,(b+a*d)%256,(c+b*a)%256,(d+c*b)%256)` in the sense that has in Python, which is where I suggest examining what happens for the low bits, then the two low-order bits.

elonnoe

10/26/22, 5:11 PM

@fgrieu thanks for the help. i was stuck, but now i understand that underlying reason.

Score:3

Crypto

Mikero

10/27/22, 1:48 AM

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

$(a,b,c,d) \mapsto (a+dc \bmod 256,b,c,d)$
$(a,b,c,d) \mapsto (a,b+ad \bmod 256,c,d)$
$(a,b,c,d) \mapsto (a,b,c+ba \bmod 256,d)$
$(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$.

0 + 2

fgrieu

10/27/22, 8:37 AM

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.

crypt

10/29/22, 6:19 AM

so that holds true for any invertible f?

Score:0

Crypto

ShAr

10/26/22, 4:21 AM

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.

0 + 5

fgrieu

10/26/22, 10:35 AM

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.

ShAr

10/26/22, 10:48 AM

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

fgrieu

10/26/22, 1:05 PM

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.

ShAr

10/26/22, 1:20 PM

Aha Ok, sorry, I thought (solved on the basis that) step2 is done once only like a seed for a random number generator

elonnoe

10/26/22, 2:57 PM