Welcome to the resource topic for
**2005/350**

**Title:**

Is SHA-1 conceptually sound?

**Authors:**
Charanjit S. Jutla, Anindya C. Patthak

**Abstract:**

We argue that if the message expansion code of SHA-1 is replaced

by a linear code with a better minimum distance, then the resulting

hash function is collision resistant. To support this argument,

we characterize the disturbance vectors which are used to build

local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1.

We also show that the following constraint satisfaction problem is

\np-hard. The constraints are restricted to being XOR constraints,

or Majority constraints on at most three variables each. The

instances are further restricted by requiring that the constraints

can be listed in a sequence C_1, C_2,…,C_m, such that for

every constraint C_i, two of the variables in it occur only in

constraints C_j, with |j-i|< 48. This problem is similar to the

problem modeling the one-way function property of SHA-1.

**ePrint:**
https://eprint.iacr.org/2005/350

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .