3
$\begingroup$

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?

$\endgroup$
3
  • 4
    $\begingroup$ 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. $\endgroup$
    – Morrolan
    Mar 19, 2022 at 16:39
  • 4
    $\begingroup$ 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. $\endgroup$
    – Morrolan
    Mar 19, 2022 at 16:41
  • 2
    $\begingroup$ 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). $\endgroup$
    – Mark
    Mar 19, 2022 at 18:49

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "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. $\endgroup$
    – Maeher
    Mar 20, 2022 at 11:21
  • $\begingroup$ @Maeher yes, there was a mistake there. Thanks. $\endgroup$
    – kelalaka
    Mar 20, 2022 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.