MASH-1

Short description: Cryptographic hash function

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 [math]\displaystyle{ N }[/math], whose bitlength affects the security. [math]\displaystyle{ N }[/math] is a product of two prime numbers and should be difficult to factor, and for [math]\displaystyle{ N }[/math] of unknown factorization, the security is based in part on the difficulty of extracting modular roots.

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

The message is padded by appending the message length and is separated into blocks [math]\displaystyle{ D_1, \cdots, D_q }[/math] of length [math]\displaystyle{ L/2 }[/math]. From each of these blocks [math]\displaystyle{ D_i }[/math], an enlarged block [math]\displaystyle{ B_i }[/math] of length [math]\displaystyle{ L }[/math] is created by placing four bits from [math]\displaystyle{ D_i }[/math] 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:

[math]\displaystyle{ H_0 = IV }[/math]

[math]\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 }[/math]

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

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

[math]\displaystyle{ H_q = Y_1 \,\|\, Y_3 \,\|\, Y_0 \,\|\, Y_2; \quad |Y_i| = L/4 }[/math]

[math]\displaystyle{ Y_i = Y_{i-1} \oplus Y_{i-4}; \quad i=4,\cdots,15 }[/math]

[math]\displaystyle{ D_{q+i} = Y_{2i-2} \,\|\, Y_{2i-1}; \quad i=1,\cdots,8 }[/math]

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

[math]\displaystyle{ H_i = f(B_i, H_{i-1}); \quad i=q+1,\cdots,q+8 }[/math]

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

MASH-2

There is a newer version of the algorithm called MASH-2 with a different exponent. The original [math]\displaystyle{ e=2 }[/math] is replaced by [math]\displaystyle{ e=2^8+1 }[/math]. 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