Using RSA for a hash

Question

I am thinking of creating a hash function (e.g. md5 or sha1) using the RSA encryption algorithm. I am wondering if there are obvious reasons why this algorithm will not work:

• Generate RSA public / private keys.
• Discard the private key, never store it at all.
• Start with a block length hash for RSA encryption.
• Encrypt the message using the public key, one block at a time.
• For each encrypted message block, accumulate it in a hash using the specified algorithm (possibly a combination of +, xor, etc.).

To verify that the message has the same hash as the stored hash, use the stored public key and repeat the process.

Is it possible safe and practical?

Thanks for any comments.

Answer 1

There are already hashes that do this essentially, with the possible exception, perhaps, of the RSA algorithm in particular. They are called cryptographic hashes, and their main point is that they are cryptographically secure, which means that they also include the same considerations as for security and security that go into public key cryptographic functions.

The only difference is that they were designed from scratch as hashes, so they also meet the individual requirements of the hash functions, which can be considered as additional strengths that cryptographic functions do not need.

In addition, there are factors that completely contradict each other, for example, you want the hash functions to be as fast as possible, without compromising security, while slowness is often considered as a function of cryptographic functions, since it limits the brute force of attacks significantly.

SHA-512 is a great cryptographic hash and probably deserves your attention. Whirlpool, Tiger and RipeMD are also great choices. You will not go wrong with any of them.

One more thing: if you really want it to be slow, then you definitely DO NOT want a hash function, and this happens completely wrong. If, as I assume, what you want is a very, very safe hash function, then, as I said, there are many options that are better suited to your example, although they are the same or even more cryptographically secure.

By the way, I'm not quite sure that there is no weakness with your mixing algorithm. Although the output of each RSA block is designed to be homogeneous with a high level of avalanche, etc. Etc. Etc., I am still concerned that this could create a problem for the selected plaintext or comparative analysis of similar messages.

Answer 2

RSA encryption is not deterministic: if you follow the RSA standard, you will see that some random bytes are entered. Therefore, if you encrypt RSA twice with the same message, most likely you will not get the same result twice.

In addition, your “unspecified step 5” is likely to be weak. For example, if you define a way to hash a block, and then just XOR the blocks together, then A || B and B || A (for A and B values ​​of block size) will have a hash with the same value; that clash of bonanza.

In the academic plan, the construction of hash functions from set-theoretic structures was tried (i.e. not raw RSA, but reuse of the same mathematical element); see this presentation from Lars Knudsen for some details. Similarly, an ECOH hash function was sent to the SHA-3 contest using elliptic curve curves (but it was “broken”). The fundamental hope is that the security of the hash function may be somehow related to the underlying set-theoretic problem, thereby providing provable security. However, in practice, such hash functions are either slow or weak, or both.

Answer 3

Without thinking too much about it, it looks like it will be cryptographically secure.

However, you should be careful with the selected plaintext attacks, and if your input is large, you may run into speed problems (since asymmetric crypto signal is much slower than cryptographic hashes).

So, in short: yes, it seems that this can be possible and safe ... But if there is no good reason, I would use the standard HMAC if you need a hash key.

Answer 4

Generally, it is best to use a publicly available algorithm that has gone through the review process. Despite the fact that there may be known flaws with such algorithms, it is probably better than unknown flaws in a makeshift algorithm. Note that I am not saying that the proposed algorithm has flaws; it is simple that even if a large number of answers are given here that say it seems good, it does not guarantee that it is not. Of course, the same can be said about algorithms such as MD5, SHA, etc. But, at least with them, a large number of people led them through a thorough analysis.

In addition to the previous “template” warnings against developing your own cryptographic functions, it seems that the proposed solution can be somewhat expensive in terms of processing time. RSA encryption on a large document can be prohibitive.