 Hash functions based on modular arithmetic

The basic idea of hash functions based on modular arithmetic is to construct an iterated hash function using mod M arithmetic as the basis of a compression function. Two motivating factors are re-use of existing software or hardware (in public-key systems) for modular arithmetic, and scalability to match required security levels. Significant disadvantages, however, include speed (e.g., relative to the customized hash functions of §9.4.2), and an embarrassing history of insecure proposals.

MASH

MASH-1 (Modular Arithmetic Secure Hash, algorithm 1) is a hash function based on modular arithmetic. It has been proposed for inclusion in a draft ISO/IEC standard. MASH-1 involves use of an RSA-like modulus M, whose bitlength affects the security. M should be difficult to factor, and for M of unknown factorization, the security is based in part on the difficulty of extracting modular roots (§3.5.2). The bitlength of M also determines the blocksize for processing messages, and the size of the hash-result (e.g., a 1025-bit modulus yields a 1024-bit hash-result). As a recent proposal, its security remains open to question (page 381). Techniques for reducing the size of the final hash-result have also been proposed, but their security is again undetermined as yet.

9.56 Algorithm MASH-1 (version of Nov. 1995)

INPUT: data x of bitlength 0 < b < 2n/,2.

OUTPUT: n-bit hash of a; (n is approximately the bitlength of the modulus M).

• 1. System setup and constant definitions. Fix an RSA-like modulus Л/ = pq of bitlength m, where p and q are randomly chosen secret prunes such that the factorization of M is intractable. Define the bitlength n of the hash-result to be the largest multiple of 16 less than m (i.e., n = 16»' < m). HQ = 0 is defined as an IV, and an n- bit integer constant A = OxfO... 0. “V” denotes bitwise inclusive-OR; “ф” denotes bitwise exclusive-OR.
• 2. Padding, blocking, and MD-strengthening. Pad x with 0-bits, if necessary, to obtain a string of bitlength t n/2 for the smallest possible t > 1. Divide the padded text into (n/2)-bit blocks x'i,... , xt, and append a final block xt+i containing the (n/2)-bit representation of b.
• 3. Expansion. Expand each xt to an n-bit block y, by partitioning it into (4-bit) nibbles and inserting four 1-bits preceding each, except for yt+ wherein the inserted nibble is 1010 (not 1111).
• 4. Compression function processing. Foil < i < t+1, map two /(-bit inputs (#,_i, yf) to one n-bit output as follows: Я; <- ((((Я,_1Фу,;) V A)2 mod M) 4 n)®#,_i. Here 4 n denotes keeping the rightmost n bits of the m-bit result to its left.
• 5. Completion. The hash is the n-bit block Я(+1.

MASH-2 is defined as per MASH-1 with the exponent e = 2 used for squaring in the compression function processing stage (step 4) replaced with e = 28 + 1.