5
$\begingroup$

I know that for encryption we require non-linearity because it impedes the ability to attack the cipher by solving for the key with linear equations.

Does hashing require non-linear components as well? I presume it does, but I do not know why.

How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search?

I would like to work with the assumption that the linear permutation has appropriate diffusion and is sufficiently complicated/iterated enough to preclude trivial attacks.

$\endgroup$
7
$\begingroup$

Does hashing require non-linear components as well?

Yes

How would a hash built from a linear psuedo-random permutation be vulnerable to collision/preimage search?

You could find a preimage by solving for the preimage with linear equations; that is, for a linear function, each output bit is a linear function of the input bits. We would express the entire output as a set of linear equations (with the preimage bits being the unknown), set the right side to be image we're looking for, and solve that set of linear equations, giving us the preimage.

$\endgroup$

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.