# modular exponentiation as a one-way-hash

As far as I can tell most one-way hashes apply some iterated encryption algorithm to the input data.

What would be the issues with a one-way hash based on some fixed large prime p and a generator g with h(x) = g^x mod p? Is it just that the methods used for modern hashes are even harder than the discrete logarithm?

-

It's a fine one-way function, based (as you noted) on the computational difficulty of the discrete logarithm problem. As far as its relation with modern-day cryptographic hash functions, however, it lacks two quite important properties.

Here's an okay definition: a function $H$ is called a cryptographic hash function if it possesses the following three properties:

1. Preimage resistance: Given $H(x)$, it's hard to find $x$
2. Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
3. Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

Note that a general one-way function possesses only property 1. Unfortunately, your $h(x) = g^x \bmod p$ fails property 2. Suppose you had a fixed message $m$ that the adversary knows. Notice that

$$h(m + p - 1) \equiv g^{m + p-1} \equiv g^m \cdot g^{p-1} \equiv g^m \pmod{p}$$

by Fermat's little theorem. By extension, you find that $h(m + k(p-1))$ collides with $h(m)$ for any $k \in \mathbb{Z}^{+}$. So, you can in fact efficiently find infinitely many collisions with any $m_1$, which is relatively exciting, I suppose. And since $h(x)$ doesn't have property 2, it can't possibly have property 3. On the other hand, SHA2 and SHA3 (as two example candidates of modern-day hash functions) are strongly suspected to satisfy even property 3.

Also, even if we wanted a one-way function, modular exponentiation is dreadfully slow. Even with the repeated-squaring method, it's still painful. Some researchers at Intel did a benchmark with a modular exponentiation implementation and found that their implementation took nearly 450,000 cycles (!) for a 512-bit modular exponentiation. On the other hand, the Crypto++ Benchmarks report a figure of 17.7 cycles per byte for SHA-512. Now, I do admit that these were ran on different processors, but the difference is pretty spectacular.

So, in sum, there are essentially two reasons we use hash functions like SHA2: (1) they offer two extra properties, both of which are quite essential for many purposes and (2) modular exponentation is so very painfully slow. I'm sure there are more to be found, but I think these two are the most compelling.

-
Can you give a quick example of when having rules 1 but not 2 (or having 1,2 but not 3) would lead to problems? –  alecb Jun 25 '13 at 16:27
@alecbenzer: Sure. Signature schemes often sign the hash digest of some data instead of the data itself. If the hash used doesn't have second-preimage resistance, this means that an attacker can forge signatures for the collisions. (Imagine signing money transfers or some such deal...) –  Reid Jun 25 '13 at 23:48
Ok, lol, so not to be too picky, but this can easily be circumvented by simply signing the actual message and not using a hash at all, right? This is less efficient but still serves the purpose of signing. Are there any applications that really can't be solved at all without a second preimage resistant hash function? –  alecb Jun 26 '13 at 20:47
@alecbenzer: Taking the hash function out of a signature scheme like RSA (sometimes) enables existential forgery attacks as well as requiring you to deal with messages that are too long (if you simply sign each block, then you have to prevent block reordering somehow). So, it's not quite as simple as just signing the message... I'd recommend asking another question on this site if you want more details. –  Reid Jun 27 '13 at 14:25