2

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)

09182736471890
  • 516
  • 4
  • 9
  • 4
    Depends on [what you mean by ‘hash function’](https://crypto.stackexchange.com/a/59390). For example, the [first message authentication code in history](https://crypto.stackexchange.com/a/74920), built out of what would later be called universal hashing, provides the optimal possible ‘information-theoretic’ bound on forgery probability. But it's not a _collision-resistant hash function_ like SHA-256, a concept which doesn't even have a mathematical formalization that could conceivably have a notion of ‘information-theoretic security’. – Squeamish Ossifrage Oct 29 '19 at 05:06
  • So would Poly1305 be an information-theoretically secure "hash function", while SHA-256 is a computationally-secure function but with collision resistant? – 09182736471890 Oct 29 '19 at 05:13
  • I wouldn't say that, no, and I definitely wouldn't draw specifically that _contrast_ between [different types of security](https://crypto.stackexchange.com/a/68606) for the two qualitatively different _goals_ of _bounded difference probability_ (Poly1305) and _collision resistance_ (SHA-256). Poly1305 and SHA-256 are _entirely different kinds of thing_ which both happen to fit under the wide umbrella of the vague term ‘hash function’, meaning a function that kinda scrambles its input in some way. The FNV-1 hash is also called a ‘hash function’ but it doesn't aspire to _any_ security. – Squeamish Ossifrage Oct 29 '19 at 14:17

1 Answers1

2

The Gilbert-MacWilliams-Sloane MAC referred to by @SqueamishOssifrage in the comments is information theoretically secure "for single use", at the cost of having hashes that have length $2\ell$ for fixed length messages of length $\ell.$

Poly1305 is not information theoretically secure.

It is much more flexible, can take essentially arbitrary length inputs, and has a low probability $p$ of being spoofed which depends on four factors, $\delta,C,D,L$ and which is essentially $\delta$ plus a tiny correction factor, so $$p\leq \delta+f(L,D)2^{-106}.$$ See the original paper by Bernstein (Springer LNCS vol. 3557, also available at his site https://cr.yp.to/mac/poly1305-20050329.pdf) :

  • One can have up to $C\leq 2^{64}$ authenticated messages
  • Messages are of maximum length $L.$
  • One can attempt up to $D$ forgeries
  • $\delta$ is the probability of distinguishing AES output from a random permutation

To start with, we don't know what $\delta$ is. AES could be replaced if it was found to be weak, but the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution, which would enable one to define information theoretic security, which depends on entropy, a well defined functional of a probability distribution.

kodlu
  • 18,817
  • 2
  • 23
  • 47
  • ‘Poly1305 is not information theoretically secure.’ What is your definition of ‘information theoretically secure’ which Poly1305 fails? You proceeded to quote a paper about the _composition_ Poly1305-AES, which uses Poly1305 as a component. – Squeamish Ossifrage Oct 29 '19 at 14:05
  • ‘the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution’—This is…not an issue in _any_ of the security theorems related to Poly1305, not even Poly1305-AES or crypto_secretbox_xsalsa20poly1305. The theorems involving Poly1305 are all quantified _for all_ messages, _for uniform random_ keys. – Squeamish Ossifrage Oct 29 '19 at 14:07
  • For a little more on the history of universal hashing one-time authenticators, their easily proven security properties, and how they fit in with other components, see https://crypto.stackexchange.com/a/67639. Poly1305-AES is an example of a Carter–Wegman–Shoup MAC based on Poly1305 _and_ AES, but essentially nobody uses it today—ChaCha/Poly1305 as used in TLS 1.3 and crypto_secretbox_xsalsa20poly1305 both just derive a one-time Poly1305 authenticator key per message pseudorandomly, with no AES involved. – Squeamish Ossifrage Oct 29 '19 at 14:12
  • 2
    It's unclear to me why you brought up Poly1305-AES at all. The OP wasn't asking for a MAC that's _not_ ‘information-theoretically secure’, and wasn't asking about Poly1305, but now you seem to have misled the OP into the conclusion that there _is not_ an ‘information-theoretic security’ theorem for Poly1305 when exactly the opposite is true. – Squeamish Ossifrage Oct 29 '19 at 17:40
  • By the way, there are universal hashing MACs—not GMS, not Poly1305—that have $h$-bit outputs for $\ell$-bit messages with the smallest possible bound $1/2^h$ on forgery probability and keys much smaller than $2\ell$ bits. _E.g._, if a message $m$ is broken into an $n$-element sequence of $h$-bit chunks $(m_1, m_2, \dotsc, m_n)$ interpreted in $\operatorname{GF}(2^h)$, and a key is a tuple $(r_1, r_2, \dotsc, r_n, s)$ of $n + 1$ elements of $\operatorname{GF}(2^h)$, then the MAC $m_1 r_1+m_2 r_2+\dotsb+m_n r_n+s$ attains the bound $1/2^h$ on forgery probability with $\ell+h<2\ell$ key bits. – Squeamish Ossifrage Oct 29 '19 at 18:15
  • @SqueamishOssifrage the OP has a question on a comment about Poly1305. – kelalaka Oct 29 '19 at 18:39