Cryptanalysis of a hash function, and the modular subset sum problem

Research output: Contribution to journalArticle

Abstract

Recently, Shpilrain and Sosnovski proposed a hash function based on composition of affine maps. In this paper, we show that this hash function with its proposed parameters is not weak collision resistant, for plaintexts of size at least 1.9MB (about 2 24 {2{24}} bits). Our approach is to reduce the preimage problem to a (very) high density instance of the Random Modular Subset Sum Problem, for which we give an algorithm capable of solving instances of the resulting size. Specifically, given plaintexts of about 1.9MB, we were able to produce other plaintexts of the same size with the same hash value in about 13 hours each, on average.

Original languageEnglish
JournalGroups, Complexity, Cryptology
DOIs
StateAccepted/In press - 2019

Keywords

  • Cayley hash function
  • Subset-sum problem
  • cryptanalysis

Fingerprint Dive into the research topics of 'Cryptanalysis of a hash function, and the modular subset sum problem'. Together they form a unique fingerprint.

  • Cite this