MASH-1

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

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.

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

MASH-1 involves use of an RSA-like modulus ${\displaystyle N}${\displaystyle N}, whose bitlength affects the security. ${\displaystyle N}${\displaystyle N} is a product of two prime numbers and should be difficult to factor, and for ${\displaystyle N}${\displaystyle N} of unknown factorization, the security is based in part on the difficulty of extracting modular roots.

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

The message is padded by appending the message length and is separated into blocks ${\displaystyle D_{1},\cdots ,D_{q}}${\displaystyle D_{1},\cdots ,D_{q}} of length ${\displaystyle L/2}${\displaystyle L/2}. From each of these blocks ${\displaystyle D_{i}}${\displaystyle D_{i}}, an enlarged block ${\displaystyle B_{i}}${\displaystyle B_{i}} of length ${\displaystyle L}${\displaystyle L} is created by placing four bits from ${\displaystyle D_{i}}${\displaystyle 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:

${\displaystyle H_{0}=IV}${\displaystyle H_{0}=IV}

${\displaystyle H_{i}=f(B_{i},H_{i-1})=((((B_{i}\oplus H_{i-1})\vee E)^{e}{\bmod {N}}){\bmod {2}}^{L})\oplus H_{i-1};\quad i=1,\cdots ,q}${\displaystyle H_{i}=f(B_{i},H_{i-1})=((((B_{i}\oplus H_{i-1})\vee E)^{e}{\bmod {N}}){\bmod {2}}^{L})\oplus H_{i-1};\quad i=1,\cdots ,q}

Where ${\displaystyle E=15\cdot 2^{L-4}}${\displaystyle E=15\cdot 2^{L-4}} and ${\displaystyle e=2}${\displaystyle e=2}. ${\displaystyle \vee }${\displaystyle \vee } denotes the bitwise OR and ${\displaystyle \oplus }${\displaystyle \oplus } the bitwise XOR.

From ${\displaystyle H_{q}}${\displaystyle H_{q}} are now calculated more data blocks ${\displaystyle D_{q+1},\cdots ,D_{q+8}}${\displaystyle D_{q+1},\cdots ,D_{q+8}} by linear operations (where ${\displaystyle \|}${\displaystyle \|} denotes concatenation):

${\displaystyle H_{q}=Y_{1},円\|,円Y_{3},円\|,円Y_{0},円\|,円Y_{2};\quad |Y_{i}|=L/4}${\displaystyle H_{q}=Y_{1},円\|,円Y_{3},円\|,円Y_{0},円\|,円Y_{2};\quad |Y_{i}|=L/4}

${\displaystyle Y_{i}=Y_{i-1}\oplus Y_{i-4};\quad i=4,\cdots ,15}${\displaystyle Y_{i}=Y_{i-1}\oplus Y_{i-4};\quad i=4,\cdots ,15}

${\displaystyle D_{q+i}=Y_{2i-2},円\|,円Y_{2i-1};\quad i=1,\cdots ,8}${\displaystyle D_{q+i}=Y_{2i-2},円\|,円Y_{2i-1};\quad i=1,\cdots ,8}

These data blocks are now enlarged to ${\displaystyle B_{q+1},\cdots ,B_{q+8}}${\displaystyle B_{q+1},\cdots ,B_{q+8}} like above, and with these the compression process continues with eight more steps:

${\displaystyle H_{i}=f(B_{i},H_{i-1});\quad i=q+1,\cdots ,q+8}${\displaystyle H_{i}=f(B_{i},H_{i-1});\quad i=q+1,\cdots ,q+8}

Finally the hash value is ${\displaystyle H_{q+8}{\bmod {p}}}${\displaystyle H_{q+8}{\bmod {p}}}, where ${\displaystyle p}${\displaystyle p} is a prime number with ${\displaystyle 7\cdot 2^{L/2-3}<p<2^{L/2}}${\displaystyle 7\cdot 2^{L/2-3}<p<2^{L/2}}.^[1]

There is a newer version of the algorithm called MASH-2 with a different exponent. The original ${\displaystyle e=2}${\displaystyle e=2} is replaced by ${\displaystyle e=2^{8}+1}${\displaystyle e=2^{8}+1}. This is the only difference between these versions.

• A. Menezes, P. van Oorschot, S. Vanstone, Handbook of Applied Cryptography, ISBN 0-8493-8523-7