Subject: [CFRG] SipHash recommendation?

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 15 Dec 2020 16:02:29 -0800

Hi all,

We have a document (draft-ietf-dnsop-server-cookies) in front of the IESG
that proposes to use the SipHash-2-4 algorithm
(https://www.aumasson.jp/siphash/,
https://www.aumasson.jp/siphash/siphash.pdf) as a MAC over what is in some
sense a return-routability and freshness token, the "DNS cookie" originally
specified in RFC 7873.

Unfortunately, the authors of this draft have not yet written down a clear
description of what properties they believe are needed from this MAC for
this usage, which makes it slightly hard to confirm that SipHash is a
suitable algorithm for this purpose, though that is certainly a question
that I am interested in.

Regardless of that, I would also like to get the CFRG's input on whether
SipHash is a suitable algorithm for its stated goals (paraphrasing
slightly): a performant keyed (family of) PRF suitable for use as a MAC,
with the security goal for a MAC being considered to be that an attacker,
even after seeing tags for many messages (perhaps selected by the
attacker), is unable to guess tags for any other messages.

In short: is SipHash fit for this purpose?

There does seem to be a decent amount of literature analyzing SipHash, but
I have not attempted to review it to any significant degree.

Thanks,

Ben

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Wed, 16 Dec 2020 15:58:08 +0100

SipHash co-author here, that draft uses the 2-4 versions (like the Linux
kernel,
https://www.kernel.org/doc/html/latest/security/siphash.html), which has
lower security margin than 4-8, but I’m not aware of any cryptanalysis
result that would affect any of these in the context of this proposed
application.

On Wed 16 Dec 2020 at 01:03, Benjamin Kaduk <[email-masked]> wrote:

> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Dec 2020 10:59:20 -0500

Hi Jean-Philippe:

Section 3 of the SipHash paper [1] writes "We define SipHash-c-d for 
smaller c and d to provide targets for cryptanalysis. Cryptanalysts are 
thus invited to break", while Section 1 writes "Our concrete proposal 
SipHash-2-4 was designed and evaluated to be a cryptographically strong 
PRF (pseudorandom function), i.e., indistinguishable from a uniform 
random function.
This implies its strength as a MAC."

I am curious about the cryptanalysis that went into supporting the 
indistinguishability claim. From a cursory look at [1] and [2] I could 
not immediately find this.

Is indistinguishability the (or one of the) "security goals" alluded to, 
but not mentioned, on the last slide of the presentation [2]?

Best regards, Rene

Ref:
[1] Hash Functions - SipHash, A Fast Short-Input PRF (Jean-Philippe 
Aumasson, Daniel Bernstein, DIAC 2012)
[2] https://cr.yp.to/talks/2012.12.12/slides.pdf

On 2020-12-16 9:58 a.m., Jean-Philippe Aumasson wrote:
> SipHash co-author here, that draft uses the 2-4 versions (like the 
> Linux kernel,
> https://www.kernel.org/doc/html/latest/security/siphash.html 
> <https://www.kernel.org/doc/html/latest/security/siphash.html>), which 
> has lower security margin than 4-8, but I’m not aware of any 
> cryptanalysis result that would affect any of these in the context of 
> this proposed application.
>
>
>
> On Wed 16 Dec 2020 at 01:03, Benjamin Kaduk <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hi all,
>
>     (https://www.aumasson.jp/siphash/ <https://www.aumasson.jp/siphash/>,
>     https://www.aumasson.jp/siphash/siphash.pdf
>     <https://www.aumasson.jp/siphash/siphash.pdf>) as a MAC over what
>     is in some
>     [email-masked] <mailto:[email-masked]>
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Wed, 16 Dec 2020 17:05:11 +0100

The most recent results are these 2019 works:

https://eprint.iacr.org/2019/865.pdf
and
https://askworkshop.github.io/ask2019/assets/slides/ask2019talk_yunwenliu.pdf

Summary tables below, where distinguishers are the type of attacks related
to indistinguishabilty:

On Wed, Dec 16, 2020 at 4:59 PM Rene Struik <[email-masked]> wrote:

> SipHash-2-4 was designed and evaluated to be a cryptographically strong PRF
> (pseudorandom function), i.e., indistinguishable from a uniform random
> function.
> indistinguishability claim. From a cursory look at [1] and [2] I could not
> immediately find this.
>
> CFRG mailing [email-masked]://www.irtf.org/mailman/listinfo/cfrg
>
>
> --

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Dec 2020 11:17:19 -0500

Hi Jean-Philippe:

So, it seems your 2012 paper does not provide any evidence of the 
indistinguishability claim in the introduction hereof, but there has 
been some subsequent work in this direction (your 2019 pointers). Isn't 
an indistinguishability claim different from an attack actually building 
a distinguisher with high complexity?

Best regards, Rene

On 2020-12-16 11:05 a.m., Jean-Philippe Aumasson wrote:
> <https://eprint.iacr.org/2019/865.pdf>
> and
> <https://askworkshop.github.io/ask2019/assets/slides/ask2019talk_yunwenliu.pdf>
>
> Summary tables below, where distinguishers are the type of attacks 
> related to indistinguishabilty:
>
> image.png
> image.png
>
> On Wed, Dec 16, 2020 at 4:59 PM Rene Struik <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hi Jean-Philippe:
>
>     Section 3 of the SipHash paper [1] writes "We define SipHash-c-d
>     for smaller c and d to provide targets for cryptanalysis.
>     Cryptanalysts are thus invited to break", while Section 1 writes
>     "Our concrete proposal SipHash-2-4 was designed and evaluated to
>     be a cryptographically strong PRF (pseudorandom function), i.e.,
>     indistinguishable from a uniform random function.
>     indistinguishability claim. From a cursory look at [1] and [2] I
>     could not immediately find this.
>
>     Is indistinguishability the (or one of the) "security goals"
>     alluded to, but not mentioned, on the last slide of the
>     presentation [2]?
>
>     Best regards, Rene
>
>     Ref:
>     [1] Hash Functions - SipHash, A Fast Short-Input PRF
>     (Jean-Philippe Aumasson, Daniel Bernstein, DIAC 2012)
>     <https://cr.yp.to/talks/2012.12.12/slides.pdf>
>
>>     SipHash co-author here, that draft uses the 2-4 versions (like
>>     the Linux kernel,
>>     <https://www.kernel.org/doc/html/latest/security/siphash.html>),
>>     which has lower security margin than 4-8, but I’m not aware of
>>     any cryptanalysis result that would affect any of these in the
>>     context of this proposed application.
>>
>>
>>
>>         <https://www.aumasson.jp/siphash/siphash.pdf>) as a MAC over
>>         what is in some

>>     https://www.irtf.org/mailman/listinfo/cfrg  <https://www.irtf.org/mailman/listinfo/cfrg>
>
>
>     -- 
>     email:[email-masked]  <mailto:[email-masked]>  | Skype: rstruik

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Wed, 16 Dec 2020 17:22:48 +0100

The security goal of a PRF is to be indistinguishable from a random
function, according to some formal and precise definition. I've not checked
but I believe that these papers' distinguishers fall in this category (as
opposed, for example, to "known-key distinguishers").

AFAIU, these results don't seem to violate the claim of
indistinguishability on Siphash-2-4 or 4-8.

One limitation of SipHash is its tag size (64 bits). We've a 128-bit
version in the github repo, but it's not in the paper, and arguably less
analyzed than the original. Linux also has this "halfsiphash".

What's important to keep in mind is that SipHash is a PRF/MAC, not a hash
function (probably bad name choice), and should thus not be used as an
unkeyed hash (unless you dont worry about collision resistance).

On Wed, Dec 16, 2020 at 5:17 PM Rene Struik <[email-masked]> wrote:

> indistinguishability claim in the introduction hereof, but there has been
> some subsequent work in this direction (your 2019 pointers). Isn't an
> indistinguishability claim different from an attack actually building a
> distinguisher with high complexity?
>
> Best regards, Rene
>

---

From: Rene Struik <[email-masked]>
Date: Wed, 16 Dec 2020 11:34:15 -0500

My point was that one should not make all kind of claims and then not 
provide any supporting evidence. (It has, sadly, been a common refrain 
in some crypto papers, where it is hard for the reader to distinguish 
promise from overpromise/hype.)

In the same vain, why reference subsequent papers as purported evidence 
if one adds disclaimer language "I've not checked but believe" in.

For clarity: this does not mean SipHash is necessarily suspect, but 
perhaps there are some loose ends that, by uncareful language, may or 
may not have been brushed under the carpet.

Rene

On 2020-12-16 11:22 a.m., Jean-Philippe Aumasson wrote:
> function, according to some formal and precise definition. I've not 
> checked but I believe that these papers' distinguishers fall in this 
> category (as opposed, for example, to "known-key distinguishers").
>
> version in the github repo, but it's not in the paper, and arguably 
> less analyzed than the original. Linux also has this "halfsiphash".
>
> What's important to keep in mind is that SipHash is a PRF/MAC, not a 
> hash function (probably bad name choice), and should thus not be used 
> as an unkeyed hash (unless you dont worry about collision resistance).
>
>
>
> On Wed, Dec 16, 2020 at 5:17 PM Rene Struik <[email-masked] 
>     indistinguishability claim in the introduction hereof, but there
>     has been some subsequent work in this direction (your 2019
>     pointers). Isn't an indistinguishability claim different from an
>     attack actually building a distinguisher with high complexity?
>
>     Best regards, Rene
>
>>     Summary tables below, where distinguishers are the type of
>>     attacks related to indistinguishabilty:
>>
>>     image.png
>>     image.png
>>
>>     On Wed, Dec 16, 2020 at 4:59 PM Rene Struik
>>     <[email-masked] <mailto:[email-masked]>> wrote:
>>
>>         Hi Jean-Philippe:
>>
>>         Section 3 of the SipHash paper [1] writes "We define
>>         SipHash-c-d for smaller c and d to provide targets for
>>         cryptanalysis. Cryptanalysts are thus invited to break",
>>         while Section 1 writes "Our concrete proposal SipHash-2-4 was
>>         designed and evaluated to be a cryptographically strong PRF
>>         (pseudorandom function), i.e., indistinguishable from a
>>         uniform random function.
>>         I am curious about the cryptanalysis that went into
>>         supporting the indistinguishability claim. From a cursory
>>         look at [1] and [2] I could not immediately find this.
>>
>>>         SipHash co-author here, that draft uses the 2-4 versions
>>>         (like the Linux kernel,
>>>         which has lower security margin than 4-8, but I’m not aware
>>>         of any cryptanalysis result that would affect any of these
>>>         in the context of this proposed application.
>>>
>>>
>>>
>>>             <https://www.aumasson.jp/siphash/siphash.pdf>) as a MAC
>>>             over what is in some

---

From: Jean-Philippe Aumasson <[email-masked]>
Date: Wed, 16 Dec 2020 17:43:13 +0100

This kind of claim without absolute evidence is usually how new symmetric
cryptography designs do. Unless you have a formal security proof with
reduction (rare in symkey), the best you can do is make security claims and
offer supporting arguments based on preliminary analysis and differential
cryptanalysis observations (as we have in the SipHash paper).

"I've not checked but believe": at the moment I only had time to do cursory
review and am not 100% sure of my claim's correctness, thus this
disclaimer. Sorry at the moment I don't have time to make an in-depth
review of these works.

There's been extensive discussions in the context of the Linux integration,
you may find them if you search in LKML archives.

SipHash was published in 2012 and we have evidence that some of the best
cryptanalysts in the world attempted to break it, so in my experience a
major cryptanalysis breakthrough is unlikely.

On Wed, Dec 16, 2020 at 5:34 PM Rene Struik <[email-masked]> wrote:

> provide any supporting evidence. (It has, sadly, been a common refrain in
> some crypto papers, where it is hard for the reader to distinguish promise
> from overpromise/hype.)
>
> In the same vain, why reference subsequent papers as purported evidence if
> one adds disclaimer language "I've not checked but believe" in.
>
> perhaps there are some loose ends that, by uncareful language, may or may
> not have been brushed under the carpet.
>
> Rene
>
>
>>> https://www.kernel.org/doc/html/latest/security/siphash.html), which
>>> has lower security margin than 4-8, but I’m not aware of any cryptanalysis