Score:3

Why is RSA not a hashfunction?

lk flag

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?

Morrolan avatar
ng flag
One straightforward issue is that we generally want our hash functions to have an infinitely large domain - or at least one large enough to be infinite for practical purposes. RSA does not offer this, instead limiting messages to the size of the modulus.
Morrolan avatar
ng flag
Another - less technical - issue is that you'd somehow need to convince users of your `(e, N)` pair (which would have to be standardized, if we were to use RSA as a hash function), that you truly did throw away the corresponding private key, respectively factorization of the modulus.
Mark avatar
ng flag
RSA is also homomorphic by default, so it would at least be a bad model of a random oracle, as $H(a)H(b) = H(ab)$. You could potentially "fix" this via padding, or simply have the constructed hash function have some collision-resistance property, but not be a good random oracle (e.g. not have pseudorandomness properties).
Score:3
in flag

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.

cn flag
"they have a much larger range than their domain" no, entire point of hash function is that its codomain (and thereby necessarily its range) is much smaller than its domain. Later you use the term "the domain range" which is not something I have ever heard of. What you're talking about is the domain.
kelalaka avatar
in flag
@Maeher yes, there was a mistake there. Thanks.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.