2
$\begingroup$

In my introduction to cryptography course I only ever did differential cryptanalysis on ciphers which were completly linear. Now I am analyzing a hash function, where I have to propagate XOR differences through a modular addition. I am now trying to find high-probability output differences for the modular addition.

I will first explain my notation:

Let $x$ and $y$ be $32$-bit strings.

Modular addition $\boxplus$ of two bitstrings $x$ and $y$ is defined like the following: $$x\boxplus y=x+y\pmod{2^{32}}$$

Whenever I speak about a (input/output) difference I mean the result of $\delta=x\oplus y$. When I am speaking about a difference we only know/search the value of the difference $\delta$ and not of $x$ and $y$. I denote differences with greek letters. Whenever I just use a $0$, I mean a difference of $0$.

A modular addition that receives an input difference $\alpha=x\oplus y$ as first summand, and an input difference $\beta=x'\oplus y'$, produces an output difference of $\gamma=(x\boxplus x')\oplus (y\boxplus y')$. I am aware that $\alpha\boxplus\beta\neq\gamma$, because of the nonlinearity. I use this notation ($\alpha\boxplus\beta=\gamma$) to indicate that the modular addition receives the summands $\alpha$ and $\beta$ and produces an output difference of $\gamma$.

I am aware that brute forcing for the best probability output is infeasible, so I am looking for more practical methods.

In the following I want to give three different cases, which are relevant for me.

Case 1

Assuming we have the following equation:

$$\alpha\boxplus 0=\beta$$

Assume for this case that I am able to choose the values for $\alpha=x\oplus y$. How can I choose an $\alpha\neq 0$ such that $\beta$ is a high probability output difference? The output difference $\beta=0$ is allowed.

Case 2

Now assume the same equation as in the first case, but I am not able to choose $\alpha$, it is given. How can I now find the a high probability output difference $\beta$?

Case 3

Now we have the following equation:

$$\alpha\boxplus\beta=\gamma$$

Given $\alpha\neq 0,\beta\neq 0$ (with $\alpha = \beta$ allowed), how can we find a high probability output difference $\gamma$?

So my question is: Are there general methods or heuristics to compute high-probability output differences for modular addition that apply to all three cases? Or does each case require a separate approach?

I looked at the following questions and papers:

  • Question 1: Here it is only stated how to calculate the probability of a given output difference $\gamma$, when also $\alpha$ and $\beta$ are given.
  • Question 2: Is not explaining anything regarding to modular addition.
  • Question 3: I think is also not useful for me.
  • Cryptographic Properties of Modular Addition $2^n$: Could probably help, but I did not understand all the math and I think it would be difficult for me to transform the results presented there, to an actualy method which can help me.
Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Case 1: The best pair would be $\alpha=\beta=2^{31}$ where the probability is 1. To see this note that the high bit position does not propagate carries in addition (unlike the other positions) and so flipping the top bit does not change any other position.

Case 2: Let $m$ denote the lest significant 1 bit of $\alpha$. First note that if $\beta$ has any bits in positions below $m$ that are set or if the $m$th position of $\beta$ is not set, then the probability is 0. This is because the operator behaves as a $T$-function where less significant outputs do not depend on more significant inputs.

A not too terrible choice is $\alpha=\beta$. We can bound the probability of this below by noting that the probability of this difference occurring is greater than the probability that flipping our input bits does not change the carry bits in our calculation. As the $i$th carry bit is computed as the majority vote of the $i$th input bits and the $(i-1)$th carry bit, we see that we want $\mathrm{MAJ}(x_i,y_i,c_{i-1})=\mathrm{MAJ}(x'_i,y_i,c'_{i-1})$. Assuming that $c_i=c'_i$ and the $i$th bit of $\alpha$ is set so that $x_i\neq x_i'$, if $y_i=0$ we want the case $c_{i-1}=c'_{i-1}=0$ and if $y_i=1$ we want the case $c_{i-1}=c'_{i-1}=1$. We see that the case that the $i$th carry bit is unaffected is $1/2$. This gives a lower bound for the probability of the input difference as $2^{-W(\alpha)}$ where $W(\alpha)$ is the Hamming weight of $\alpha$ and $\beta$.

Case 3 Again, we note that the least significant 1 in $\gamma$ should not be below the least significant 1 in both $\alpha$ and $\beta$. If the least significant 1 in $\alpha$ and $\beta$ lie in the same position, the corresponding position in $\gamma$ can be 0 with a non-zero probability. This suggests a choice $\gamma=\alpha\oplus\beta$ and again producing a lower bound based on the probability that our bit flips do not change the carries in our calculations. The problem is complicated by dependencies. It may be useful to note that taken over all input pairs, the probability that the $i$th carry bit is 1 is given by $(2^i-1)/(2^{i+1})$ and that the conditional probability that the $j$th carry bit is 1 given that the $i$th carry bit is 0 (for $j>i$) is given by $(2^{j-i}-1)/(2^{j-i+1})$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.