MASH-1 explained

For a cryptographic hash function (a mathematical algorithm), a MASH-1 (Modular Arithmetic Secure Hash) is a hash function based on modular arithmetic.

History

Despite many proposals, few hash functions based on modular arithmetic have withstood attack, and most that have tend to be relatively inefficient. MASH-1 evolved from a long line of related proposals successively broken and repaired.

Standard

Committee Draft ISO/IEC 10118-4 (Nov 95)

Description

MASH-1 involves use of an RSA-like modulus

N , whose bitlength affects the security. N is a product of two prime numbers and should be difficult to factor, and for N of unknown factorization, the security is based in part on the difficulty of extracting modular roots.

Let

L be the length of a message block in bit. N is chosen to have a binary representation a few bits longer than L , typically L < |N| \leq L +16 .

The message is padded by appending the message length and is separated into blocks

D _{1,} … , D _{q} of length L/ 2 . From each of these blocks D _{i} , an enlarged block B _{i} of length L is created by placing four bits from D _{i} in the lower half of each byte and four bits of value 1 in the higher half. These blocks are processed iteratively by a compression function:H _{0} = IV H _{i} = f(B _{i,} H _{i-1} ) = ((((B _{i} ⊕ H _{i-1} ) \vee E) ^{e} \bmod N) \bmod 2 ^{L)} ⊕ H _{i-1} ; i =1 , … ,q

Where

E =15 ⋅ 2 ^{L-4} and e =2 . \vee denotes the bitwise OR and ⊕ the bitwise XOR.

From

H _{q} are now calculated more data blocks D _{q+1} , … ,D _{q+8} by linear operations (where \| denotes concatenation):H _{q} = Y _{1} \| Y _{3} \| Y _{0} \| Y _{2;} |Y _{i|} = L/ 4 Y _{i} = Y _{i-1} ⊕ Y _{i-4} ; i =4 , … , 15 D _{q+i} = Y _{2i-2} \| Y _{2i-1} ; i =1 , … , 8

These data blocks are now enlarged to

B _{q+1} , … ,B _{q+8} like above, and with these the compression process continues with eight more steps:H _{i} = f(B _{i,} H _{i-1} ); i = q +1 , … ,q +8

Finally the hash value is

H _{q+8} \bmod p , where p is a prime number with 7 ⋅ 2 ^{L/2-3} < p < 2 ^{L/2} .^[1]

MASH-2

There is a newer version of the algorithm called MASH-2 with a different exponent. The original

e =2 is replaced by e =2 ^{8+1} . This is the only difference between these versions.

References

• A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography,

Notes and References

1. https://eprint.iacr.org/2013/589.pdf Smashing MASH-1, Vladimir Antipkin