6
$\begingroup$

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)?

$\endgroup$
9
  • 1
    $\begingroup$ "just the same as a hash function" in what sense? $\;$ $\endgroup$
    – user991
    Feb 7, 2015 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, 2015 at 21:37
  • 4
    $\begingroup$ There are almost-universal hash families and information-theoretically secure MACs. $\hspace{1.3 in}$ $\endgroup$
    – user991
    Feb 7, 2015 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, 2015 at 2:17
  • $\begingroup$ @MaartenBodewes : $\:$ Alternatively, it could require that the messages be chosen non-adaptively. $\hspace{.55 in}$ $\endgroup$
    – user991
    Feb 8, 2015 at 4:46

2 Answers 2

1
$\begingroup$

Is there a "theoretically perfect" hash function, even if it is impractical?

Yes.

A "random function oracle" is often used in descriptions of cryptographic attacks as an impractical, but theoretically ideal hash function.(a) (b)

One implementation of a 64-bit random function oracle:

  1. Anyone can write down any text on a card and hand it to Carole -- an anagram of oracle (c) -- and wait for her response.
  2. If Carole does not already have that exact text in her files, Carole flips 64 pennies to get a fresh random number, and writes that 64-bit number on the back of that card. Then Carole makes a copy of that number.
  3. If Carole already has that exact text in her file, she tears up and throws away the new card (with the blank back), and makes a copy of the number on back of the old card.
  4. Carole files the card (with the text she was just given on the front, and the 64-bit number on the back) in her files for possible later retrieval.
  5. Carole hands that copied number back to the person who originally handed her that text.
  6. Carole doesn't allow anyone but herself to peek into her files.
  7. Carole never tells anyone the texts she's seen -- she only hands out the number, and only to the person who just gave her the text that is now associated with that number.
  8. Carole doesn't even reveal if this is a new, freshly-generated number, or if someone has already presented this exact text and this is another copy of the number already in her files attached to that old text.

(A "random permutation oracle" is often used in descriptions of cryptographic attacks as an impractical, but theoretically ideal block cipher. A "random permutation oracle" can be constructed from a "random function oracle". (d). )

$\endgroup$
-2
$\begingroup$

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, ....

$\endgroup$
2
  • $\begingroup$ This does not seem to attempt to answer the question. $\endgroup$
    – Maeher
    Feb 9, 2015 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, 2015 at 18:55

Your Answer

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

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