Is SHA-1 conceptually sound?

Charanjit S.  Jutla; Anindya C.  Patthak

Paper 2005/350

Is SHA-1 conceptually sound?

Charanjit S. Jutla and 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 -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.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: Hash Functions Linear Codes minimum distance CSPs oneway functions
Contact author(s): csjutla @ us ibm com
History: 2005-11-28: last of 3 revisions; 2005-10-05: received; See all versions
Short URL: https://ia.cr/2005/350
License: CC BY

BibTeX

@misc{cryptoeprint:2005/350,
      author = {Charanjit S.  Jutla and Anindya C.  Patthak},
      title = {Is {SHA}-1 conceptually sound?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2005/350},
      year = {2005},
      url = {https://eprint.iacr.org/2005/350}
}