Re: [CFRG] SipHash recommendation?

Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> Wed, 16 December 2020 16:23 UTC

Return-Path: <jeanphilippe.aumasson@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 102333A109D for <cfrg@ietfa.amsl.com>; Wed, 16 Dec 2020 08:23:06 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.097
X-Spam-Level:
X-Spam-Status: No, score=-1.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FREEMAIL_REPLY=1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id U7J7-q7NPjnY for <cfrg@ietfa.amsl.com>; Wed, 16 Dec 2020 08:23:03 -0800 (PST)
Received: from mail-lf1-x12d.google.com (mail-lf1-x12d.google.com [IPv6:2a00:1450:4864:20::12d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E0D8C3A10AA for <cfrg@ietf.org>; Wed, 16 Dec 2020 08:23:01 -0800 (PST)
Received: by mail-lf1-x12d.google.com with SMTP id l11so49837410lfg.0 for <cfrg@ietf.org>; Wed, 16 Dec 2020 08:23:01 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=StE3pTmGLHyKI0ajpZW6R5ndp41wZjkzBukLvKykBWc=; b=O148APORhRvExstVmnZZ1t/zwSBzP0fQxqRIpWgP6CrKhdb4Y//qI59BdCn4y/dgUe WnUXHHr7pjN/ajRNTDQsGtTMcNw7EayfS+3q+zd8LGKu35At7RGMASZyIYXs4kRkWWf4 yvx8PCEf5U7qb8AHuX45E3DCLXBTql5yxxh059DZhm40pjJpm/xxBLrtLHFmI7BqnSBn Ui+qzGigdbgu7OE3F3vsRJZxZ9k/k/19vCVkZJCEbZi5oMtFGvwTiqAQQ9XaSuXfKyZj VXB6S7NCbqztnOwLRTzN4q4WhZi2MqjHjVOW33aVbcNobWzDB7REb/nnrl5Mdqc9gyQq zEng==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=StE3pTmGLHyKI0ajpZW6R5ndp41wZjkzBukLvKykBWc=; b=PQN3wucFqauQ4w+BcSRPJTw2yaR7kE7SQleJZg+qCqvEfMlYqb3KZQdxtxRgbaLT7J 2MBHBzMS2PRllF52gz1z5bs7M4pc8cMbbluCAD7uXmfYl4vKddM9IqcUpgBJa7f2a4TW hUpAcgjIUJCOI5ESty6K2IFRFhWa2lnHsPwtBCwEBW+GSWrqvIhD4tDIn482ohHsrNkG T3z9I7k7HajYFQT+lnY3spCPDMXNWVq6djA6UbD4tx3kvroz084/y77mYzUYAH05GuvN x8vdpVuQmk44KK3u+5Lng3h8TH8ZwGpBpzhwSpmKfWl8U4eJpFnavaxRNDTaqncFD1UA Rk6Q==
X-Gm-Message-State: AOAM530jPIYk/Kzw0JtNuMRyovnq31j7wkFwhf89j4O7oSj3BHOvEy8V HthgTzJMtkssRoL43WhOVGeeChnH8PpDLj8N9go/8/r9Bzg=
X-Google-Smtp-Source: ABdhPJzHBNaXU+D3R0R8xtrutXVPpCsBPcXLYDs9NkuXTZjgbe95qXtxCqgQA25UIV4FBaypGCRbq/ewomL+3+K00ws=
X-Received: by 2002:a05:651c:2c7:: with SMTP id f7mr14575731ljo.127.1608135779458; Wed, 16 Dec 2020 08:22:59 -0800 (PST)
MIME-Version: 1.0
References: <20201216000229.GG64351@kduck.mit.edu> <CAGiyFdcaqyEhxhJTys0sZ6YvyRAZ9MM7=Kh1z2TqWVFckUrNrg@mail.gmail.com> <db703fe0-073d-07d0-3c81-c820e9497970@gmail.com> <CAGiyFdfd99MUQm1paypoGR8v1uV9f4tfKbnG51CCnMhu7VLDVA@mail.gmail.com> <1cdfad53-eed6-e619-8ed8-a3ec5b8d5d9b@gmail.com>
In-Reply-To: <1cdfad53-eed6-e619-8ed8-a3ec5b8d5d9b@gmail.com>
From: Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
Date: Wed, 16 Dec 2020 17:22:48 +0100
Message-ID: <CAGiyFdeiZ3OYj4OD=gXwuCv=JDW=A_+3QB8noa7yTxuYM50WRA@mail.gmail.com>
To: Rene Struik <rstruik.ext@gmail.com>
Cc: Benjamin Kaduk <kaduk@mit.edu>, cfrg@ietf.org
Content-Type: multipart/related; boundary="000000000000e43edc05b6974962"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/AB3N9lelxnMyK_SDb_wBlXwjP78>
X-Mailman-Approved-At: Mon, 21 Dec 2020 08:58:31 -0800
Subject: Re: [CFRG] SipHash recommendation?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 16 Dec 2020 16:23:06 -0000

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 <rstruik.ext@gmail.com> wrote:

> 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:
>
> 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:
>
> [image: image.png]
> [image: image.png]
>
> On Wed, Dec 16, 2020 at 4:59 PM Rene Struik <rstruik.ext@gmail.com> 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.
>> 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), 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 <kaduk@mit.edu> wrote:
>>
>>> 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
>>>
>>> _______________________________________________
>>> CFRG mailing list
>>> CFRG@irtf.org
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>>
>> _______________________________________________
>> CFRG mailing listCFRG@irtf.orghttps://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>> --
>> email: rstruik.ext@gmail.com | Skype: rstruik
>> cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
>>
>>
> --
> email: rstruik.ext@gmail.com | Skype: rstruik
> cell: +1 (647) 867-5658 | US: +1 (415) 287-3867
>
>