8
$\begingroup$

As I understand, there are a few requirements for a good hash function.

  1. Hard to find any message from a given hash
  2. Hard to find any 2 messages which give the same hash
  3. A single bit change in the input message should lead to change of each bit of the output with a probability of 0.5 (as close as possible to 0.5)
  4. Good collision resistance

So my question is if I have a asymmetric key encryption method, erase off the private key, encrypt the message with the public key, then take the least significant (say) 256 bits. Do I have a good hashing function? Does my hashing function provide some guarantees on the points 3,4? I am fairly sure points 1,2 are fine though. Aren't they?

My aim is to explore the possibility of creating a hash function out of an encryption function. So put aside the fact that messages are usually padded with random information before encryption. Just Encrypt(Message, Public-key).

edit : Some of the answers ask, how can i be sure I destroyed my private key properly. What I can do is even before generating a public/private key pair, I would just create a single random string and call it public key(if the public key has some requirements on the length or other properties, I would generate a string of that particular length). In general I would create a string which is acceptable as an public key by the encryption machine.

Improve this question
$\endgroup$
1
  • $\begingroup$ See projectbullrun.org/dual-ec to get some idea of why you should not do something that theoretically allows for a trapdoor... Regarding random generation with nothing-up-my-sleeves numbers have a look at bada55.cr.yp.to Summary: Really bad idea! $\endgroup$
    – mephisto
    Oct 3, 2015 at 11:08

4 Answers 4

Reset to default
5
$\begingroup$

Provably secure cryptographic hash functions are often built using the same sort of operations as what are used in asymmetric crypto. The major problem with these constructions are that they are very inefficient. Also, a lot of these sorts of constructions have finite input domains. Thus, you have to figure out how to extend it to arbitrary length inputs.

Now, on to your specific construction. I wouldn't use it, inefficiencies aside. How do I know that you destroyed your private key? If you didn't, likely you would have a great advantage in breaking some of the properties listed above.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ What if instead of a real public key you used a nothing-up-my-sleeve bit stream like some digits of pi? Or can arbitrary bit streams not be used as public keys? $\endgroup$
    – Random832
    Oct 3, 2015 at 7:38
  • 1
    $\begingroup$ From my understanding, that is what these provable hash functions do. $\endgroup$
    – mikeazo
    Oct 3, 2015 at 12:30
  • 1
    $\begingroup$ Using a "nothing-up-my-sleeve" number is a bit trickier when you need to have the number have some special properties (e.g., not easily factorized, or is a generator of a large subgroup, or is prime). Not impossible, but more difficult than just using the first 1000 digits of PI, for example. $\endgroup$
    – mikeazo
    Oct 3, 2015 at 13:12
  • $\begingroup$ Would this changed if you always used the message as the private key? At first glance, it appears to me that you could even use a symmetric encryption function in that case (which should also make it more efficient) $\endgroup$
    – Marian
    Oct 9, 2018 at 12:32
4
$\begingroup$

Generically, this certainly does not work. For example, with RSA, if you take the domain to be ${\mathbb Z}_N^*$ then it's a permutation so is clearly collision resistant but also completely useless. Then, if you take a larger domain, it's trivial to find a collision. For example, take any $x\in{\mathbb Z}_N^*$ and then take $x'=x + N$. It is clear that an encryption of $x$ and an encryption of $x'$ are the same. Thus, this is a collision.

This doesn't mean that you cannot use factoring or DLOG as an assumption to build collision resistant hash functions (and this can be done). However, you cannot take a generic asymmetric scheme and use it.

Improve this answer
$\endgroup$
2
$\begingroup$

Well, first of all you forgot one requirement:

  1. hashing should be a deterministic procedure (everyone should compute the same hash for the same input)

and that one you do not meet with a secure public key encryption scheme. Now you could fix the used randomness to a fixed value. Then I assume you get an inefficient hash function that in theory fulfils all requirements (oh and 3. is not a necessary condition. This is just a design principle). However, in practice there is no way to verify that the entity that generated the public key really erased the secret key. That way, this person would be able to invert and to find collisions. Hence, this would be considered a chameleon hash function (have a look at your favourite search engine).

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Encryption is not deterministic? Every body knows my public key, every body knows my encryption method, why would the output be non-deterministic? $\endgroup$
    – user28093
    Oct 3, 2015 at 3:54
  • 1
    $\begingroup$ Because otherwise, if the same message was encrypted twice it would give the same ciphertext and hence an attacker would learn that the same message was encrypted. Therefore, encryption takes some randomness and adds this e.g. in the padding. $\endgroup$
    – mephisto
    Oct 3, 2015 at 3:55
  • $\begingroup$ Let us assume that we are not adding any padding etc to the message before encryption. Just Encrypt(Message, Public-key). $\endgroup$
    – user28093
    Oct 3, 2015 at 3:58
  • $\begingroup$ That's what I suggested in my answer: fix the randomness to some public value. $\endgroup$
    – mephisto
    Oct 3, 2015 at 4:06
  • $\begingroup$ Oh ok. Got it.. $\endgroup$
    – user28093
    Oct 3, 2015 at 4:07
1
$\begingroup$

Your idea violates rule 1. With asymmetric key encryption, it is not difficult to find a message given the encrypted message, if you have the private key.

Also, if you randomly generate a number and call it the public key for a hash function, this is diverging significantly from public private keypair generation, which generally relies on finding two relatively prime numbers as a pair, and use them to generate the keypair. So, an adaptation of asymmetric key cryptography to use any random public key seems not like an adaptation but rather an abandonment of the asymmetric key generation guidelines.

If all you need is a random public key for a hash function, then asymmetric key cryotography serves no purpose.

Improve this answer
$\endgroup$
0

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.