MASH-1

This article is about Modular Arithmetic Secure Hash. For MASH-1 gene, see ASCL1.

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},\cdots ,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}\oplus H_{i-1})\vee E)^{e}{\bmod {N}}){\bmod {2}}^{L})\oplus H_{i-1};\quad i=1,\cdots ,q$

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

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

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

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

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

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

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

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

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, ISBN 0-8493-8523-7