1
$\begingroup$

Isn't addition the most linear operation possible? I read in another post that some said that addition modulo the 32-bit integer limit, in cryptographic hash function adds non-linearity, but what exactly does this mean?

If I tell you that I have a secret, S, and I tell you that the sum of it's components equals some value in the 32-bit integer range, isn't it easy to calculate S?

What I mean is this: if one component of S is increased in size by an arbitrary amount N, then that increase also reflects an increase of N in the output, right? a + b equals c, but if you increment a or b by an amount, then that same amount is used to increase the final value c.

So what exeactly is meant when we say that addition modulo the 32-bit limit adds "nonlinearity" to a hash function?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Isn't addition the most linear operation possible?

Linearity needs to be defined in terms of a specific group. That is, where we have the linear relation:

$$F(a + b) = F(a) + F(b)$$

where is $+$ defined as?

When talking about ARX-type ciphers (and SHA-2 is largely an ARX-type construction), there are two different groups involved:

  • The group of bit strings, where $a+b$ is defined as the bit-wise exclusive or of $a$ and $b$

  • The group $\mathbb{Z}^+_{n}$, where $a+b$ is defined as modular addition.

It turns out that the addition operation is nonlinear in the first group, while bitwise exclusive-or is nonlinear in the second group, and so the combination is nonlinear in both groups.

As for why addition is specifically called out, well, in crypto, we most commonly use the first definition of linearity (because it's more generally applicable), and so it is commonly assumed. I'm sure that statement was made in that context.

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.