TY - JOUR

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

AU - Monico, Chris

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Cayley hash function

KW - Subset-sum problem

KW - cryptanalysis

UR - http://www.scopus.com/inward/record.url?scp=85064715958&partnerID=8YFLogxK

U2 - 10.1515/gcc-2019-2001

DO - 10.1515/gcc-2019-2001

M3 - Article

AN - SCOPUS:85064715958

JO - Groups, Complexity, Cryptology

JF - Groups, Complexity, Cryptology

SN - 1867-1144

ER -