Why is RSA not a hashfunction?

Question

The RSA-Assumption says that $(GenSP,F,SampleX)$ is one-way. So if we initialize an instance of RSA $(n,e), (n,d)$ and fairly forget the secret-key and SampleX uniformly distributed over $X, F = x^e \bmod N$ should be one-way.

Now it is also known that Injective functions imply collision resistance, but not one-way of course.

So far, we have pre-image resistance and collision resistance. And the second pre-image resistance should be given if we take $x$ only from $\{0,\ldots,n-1\}$.

We talk about deterministic RSA, so no randomized process is involved with random-padding. Therefore our F is also deterministic.

Am I missing something?

Answer 1

RSA is a trapdoor-permutation, with the way your design you simply offer RSA-HASH with these problems;

• Limited domain with a permutation: cryptographic hash functions, although they can hash arbitrary size, they have a much larger domain than their range; consider

  • SHA-256 while it can have a 256-bit output size the domain range is $2^{64}$ bits.
  • SHA-3 while it can have a 256- or more-bit output size the domain range is $2^{128}$ bits.

  Though Keccak (SHA-3) uses permutations, it is not permutation at the end since it uses a larger input size $2^{128}$. A single permutation may trigger some problems.

  Premutation as a hash, on the other hand, has little usage, as long as you are not considering very huge modulus sizes file hashing or signatures are not possible with RSA-HASH.

• The standard: Assume NIST published the RSA-HASH-3 function as $H(m) = m^3 \bmod n$. Now, everybody in the crypto community will argue that while constructing the RSA-HASH-3, they did not destroy the $p$ and $q$ and they keep $d$ as private. There is no guarantee that they will do this or not. So, naively believing that they erased is not the way how cryptography works ( Morralan's comment).

• We expect that hash functions can simulate Random Oracles and some are failed this since their length extension attack. RSA-HASH on the other hand far from a random oracle. The multiplicative property of RSA prevents this. In a Random Oracle, we don't expect a general relation between inputs are carried into som relation between the outputs, however, RSA-HASH has it $$RSA(m_1)RSA(m_2) = RSA(m_1 m_2)$$

• Short input space: To reduce the timing of the hashing you may want to use $e=3$, then with the cube root attack all messages < $\sqrt[3]{N}$ can be easy. Increasing the $e$ will increase the cost of hashing. Remember on needs to use 2048-bit RSA.

• Post-Quantum: currently the block ciphers and hash function are safe again Grover's algorithm. Just use the 256-bit key for block ciphers and use at least a 256-bit output hash function. There is an improved work (Brassard et al.) for hash functions that reduce the size into cube-root ( instead of the square-root of Grover - asymptotically optimal!), however, the area cost is the same cost, so there is no danger there.

  RSA, on the other hand, is going to be destroyed once Shor's algorithm is built. So, RSA-HASH is not post-quantum secure.

Any usage?: RSA-HASH can serve as a good random permutation if the modulus size is fine for your application.

In conclusion: permutation, security with obscurity, speed, and no post-quantum is not a good choice for the cryptographic hash function.

Use SHA-2, SHAKE series of SHA-3, BLAKE2 ( very fast), BLAKE3 (ridiculously fast), etc. for your applications.