We know that the one-time pad is provably secure as a cipher to encrypt some data. Is there an algorithm which does the same just as a hash function? Can we get a provably secure hash function? Maybe with some ridiculous properties like the one-time pad got them (really big key length, fully random key)?

  • 1
    $\begingroup$ "just the same as a hash function" in what sense? $\;$ $\endgroup$ – user991 Feb 7 '15 at 21:32
  • $\begingroup$ We don't know if our hash functions are really secure. Maybe someone finds a way to break all of them, like MD5 was broken? The one-time pad can't be broken (if you don't make implementation mistakes), it is impossible. Is there an hash algorithm which also can't be broken? Maybe I need to differentiate the use cases of hashes: Hashing for authentication, or just hashing for the three important hashing properties (first and second pre-image resistance and collision resistance). $\endgroup$ – Nova Feb 7 '15 at 21:37
  • 4
    $\begingroup$ There are almost-universal hash families and information-theoretically secure MACs. $\hspace{1.3 in}$ $\endgroup$ – user991 Feb 7 '15 at 22:16
  • 1
    $\begingroup$ As a hash smaller than the message space will always have collisions and since provable security would allow for brute force search of all messages, the hash function would have to redefine the meaning of "compression" to be secure. I.e. the hash should be larger than the message itself - that kind of ridiculous property? $\endgroup$ – Maarten Bodewes Feb 8 '15 at 2:17
  • $\begingroup$ @MaartenBodewes : $\:$ Alternatively, it could require that the messages be chosen non-adaptively. $\hspace{.55 in}$ $\endgroup$ – user991 Feb 8 '15 at 4:46

OTP requires 1) random key material as long as the message to be encrypted 2) no reuse of the key material or any part, ever 3) secure transmission of the key material between communicants 4) no key material becomes known to anyone ever. And even then, OTP only guarantees that no other encryption will be harder to break. NOT that a message can't ever be recovered.

1) random -- for crypto purposes, random is very very hard, and very very tricky. We don't know how to do it, though we think some schemes are pretty good. There are many tests, but there are more ways to be non-random than there can be tests.

2) no reuse -- reuse makes an OTP worthless. The Russians did a little reuse in WWII and NSA was eventually able to read some of the traffic encrypted with reused key material. See Venona Project.

3) secure transmission -- NO ONE has solved the secure transmission of arbitrarily long material between nodes. There are Xerox machines, disk copiers, thumb drive copiers, ... Plus burglary (which can sometimes be covered up, leaving the sender making a very bad and completely insecure assumption),

4) no exposure of key material ever -- this requires a degree of fail safe control of the security of stuff well into the future. Humans aren't really compatible with this sort of thing.

But, good hash algorithms (and we are not SURE any of ours are good enough, there's been a poor track record) can be claimed to produce an unpredictable (and so random) string when fed with a suitable input. Sadly, they are deterministic. Feed a hash algorithm abcd... more than once and you'll get out the same hash. Which means that the unpredictability of hash algorithms is dependent on unpredictability in their inputs. Not a good thing, people being people. But, if you use some CSRNG for the inputs, why bother with the hash algorithm? If the CSRNG is defective, so will be the randomness of the hashes you produce.

But even if you, foolishly, hand wave away these issues, nearly all hash algorithms produce a shortish bit string. Say, 128 bits, or 256, or some such. So you could send a message, using one of these hashes as the OTP key material, 128 or 256 bits long.

I wouldn't bother in practice, and wouldn't touch it with a ten foot pole for a theoretical study. Too much contingency, too much dependence on things athat are out of anyone's control, ....

  • $\begingroup$ This does not seem to attempt to answer the question. $\endgroup$ – Maeher Feb 9 '15 at 17:57
  • 1
    $\begingroup$ I think you just misunderstood my question: I don't want to build a one-time pad out of a hash function, but just have a hash function, which is "as unbreakable" as the one-time pad. Well, I just ask if that is possible. $\endgroup$ – Nova Feb 9 '15 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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