Re: [Cfrg] RGLC on draft-irtf-cfrg-randomness-improvements-05

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Tue, 09 July 2019 12:00 UTC

Return-Path: <smyshsv@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 4A786120132 for <cfrg@ietfa.amsl.com>; Tue, 9 Jul 2019 05:00:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.702
X-Spam-Level:
X-Spam-Status: No, score=-0.702 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, PDS_NO_HELO_DNS=1.295, RCVD_IN_DNSWL_NONE=-0.0001, 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 MEyHnysg7NE6 for <cfrg@ietfa.amsl.com>; Tue, 9 Jul 2019 05:00:22 -0700 (PDT)
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 6BA7912010F for <cfrg@irtf.org>; Tue, 9 Jul 2019 05:00:21 -0700 (PDT)
Received: by mail-lf1-x12d.google.com with SMTP id p197so13233173lfa.2 for <cfrg@irtf.org>; Tue, 09 Jul 2019 05:00:21 -0700 (PDT)
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=QKni+62/zjqiY0sM5JRNITgXYsPOzFmcZS1Xw+ftqYY=; b=tVzu0j4vy0EmI4uYhwzex62Y3JeFDUP8HYyfgMcFSWCbRposatS2UVzamN0ARoaE8X fPmXhYgeRUPN+2o2FYBBJwPSdSHTUiO2rIUTSyYfzi2wrcqD+Nc6rEuBW1FfYnuka2m5 WS84ViAvYPsbS5LGdkYHi8B12yoW99I77sPliFdVkhbECYZQzJswqDOpN5JosCS1tEvp T3gh4qgUSQRQDNIoT9TIkHlGLNKDSTJjgMVrzVjSeZ+zdpu1m+9+BoCL9ZywwTRP3HxC V4NyZ02ex6bozKm966Q7Dv0uCBnSrweJcaa1zqI6LJXnbz8c5S9iD4WiXnWjOjZF+btd 6Yww==
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=QKni+62/zjqiY0sM5JRNITgXYsPOzFmcZS1Xw+ftqYY=; b=H3pgRY1t8Af7P5pPDalqfNYbG2AUPZBsuhvSlQhSX8t1lV6bj3R5DKttu3cdZyQnZR 9C1Ne6R025wytWNueGAJnFR3ySpY3Pv+/013c+0ipLJHPL1shnNuMVd05iYBH0UbDUAd inYweVW11qMmZAmcaoBj8/+jJCWsEemVW/pFXFAC1azaBkw+z3K5XXXLpGz/if28ypg3 ASExU/1rX2SZJmA4LelEoV5Tx/7tpAkOQuO2VTelmwT5d2PGOkhYyoGqebJIxsICKesG RCHJNRSm0Y30xN2nND93FmUW0csJFwh+PMwWBND+Br2fk0QBj3rIXMQo7fO3P7fbwVhM yC/A==
X-Gm-Message-State: APjAAAWznOO3CLUct5KdRA9hKywugDW2ilQpI4zTQJpnkn0iczjuTg5N FgkBZkB7MEG82CJyggLIDvAMEWaZqASrdUdQpkwIz5D1
X-Google-Smtp-Source: APXvYqxCFFrfzPQRm7UrE9sS94Lj/kCmWogjuJYFIf4qP18W4zjzChl0GZBZYLMUHlHjDIJOu32oZXC9kaI+aPSVuvo=
X-Received: by 2002:ac2:5c1d:: with SMTP id r29mr10627731lfp.72.1562673619437; Tue, 09 Jul 2019 05:00:19 -0700 (PDT)
MIME-Version: 1.0
References: <3644133e-93c2-e5bf-b39b-04e4423becc5@isode.com> <4fd28f76-0bde-4c91-8ddc-2b3fab0b298e@www.fastmail.com> <CAMr0u6mV0Zs29tpTZ-KEGi713xDNLiQehVdA53HgOpx4Dbyruw@mail.gmail.com> <5518f189-b680-4e24-99f6-7cd6ae1ad116@www.fastmail.com> <CAMr0u6mr6arqQ15oM0BcL0gWJSzbwEyS2BBL7dgJkd00yhE8YA@mail.gmail.com> <075a991b-df0b-4af6-8f1d-25cd963b4f7d@www.fastmail.com>
In-Reply-To: <075a991b-df0b-4af6-8f1d-25cd963b4f7d@www.fastmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Tue, 9 Jul 2019 15:01:43 +0300
Message-ID: <CAMr0u6mHnko1Ckw+x=j5wY82uVV1mKBtC4orYFtRLcCmoiBVuw@mail.gmail.com>
To: Martin Thomson <mt@lowentropy.net>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000fc8be2058d3e4dcb"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/iirhyCCsiywBUAMhzVsbgA66c6g>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-randomness-improvements-05
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: Tue, 09 Jul 2019 12:00:24 -0000

>> we might intuit simpler designs or stronger properties, but those would
only be intuitions.
That's a really great summary for what I tried to say – thanks a lot for
such an elegant wording, Martin!

Hope to see you in Montreal!

Kind regards,
Stanislav

вт, 9 июл. 2019 г. в 12:44, Martin Thomson <mt@lowentropy.net>;:

> Thanks for educating me Stanislav.  That all makes sense.
>
> We made a number of design choices in TLS 1.3 that might seem to the
> uneducated (which includes me), like compromises.  All of these were in the
> spirit of making formal analysis more tractable.
>
> I now understand both the use of H() and the weaker guarantees that we are
> asking of Extract(); we might intuit simpler designs or stronger
> properties, but those would only be intuitions.
>
> Cheers,
> Martin
>
> On Tue, Jul 9, 2019, at 19:32, Stanislav V. Smyshlyaev wrote:
> > Dear Martin,
> >
> > >> A new nit: you should probably include the usual RFC 2119/8174
> boilerplate. You use MUST and such.
> > Right, thanks!
> >
> > >> I'd wait until LC ends and batch any changes :)
> > Yes, that's the way we plan to do this (2 weeks of RGLC will end before
> > the submission is available again :) ).
> >
> > >> A secure PRF for just salt implies that the PRF property doesn't
> apply to IKM. But to a degree we are treating both inputs equally here. If
> G(L) is non-uniform, we expect to use entropy from Sig(...) to cover any
> deficit, and vice-versa.
> > >> And when you say preserve uniformness, HKDF-Extract won't preserve
> > any non-uniformity of its inputs. Taking non-uniform input and
> > producing uniform output is one of its main features. So I don't quite
> > understand the second part of your text as formulated.
> > Of course, having a function, which is a PRF for both inputs and
> > preserves uniformness for both inputs would be great. But that will be
> > a very restrictive requirement, which can be really difficult to gain
> > and prove.
> >
> > Moreover, it is not necessary to obtain the desirable properties of the
> > construction.
> > If you look at the security properties, which are declared (and proven)
> > for the construction (see three points at the end of Section 1 in the
> > draft), you'll see that we don't really treat both inputs equally: we
> > assume that either the CSPRNG is not broken (and in that case we just
> > want not to make things worse by our construction – without promising
> > that we'll improve the "almost perfect" CSPRNG), or we can't rely on
> > CSPRNG, but the key "sk" is unknown for an adversary (and in that case
> > we forget about the CSPRNG - it may give constant outputs or, even
> > worse, may be controlled by an adversary).
> > Moreover, I'd like to draw your attention to the fact that the
> > signature value is the same for all calls of a single G' instance,
> > while G(L) is new for every call (thus inputs of Extract are not equal'
> > the PRF property is required for the first input, which remains
> > constant for a single G' instance).
> >
> > In practice, good constructions, such as HKDF, may also do things
> > better even in some senses that are hard to formalize.
> >
> > >> That leads me to my next question, which I apologize for missing
> > first time around. Why do you need to hash the signature? Is this
> > because you want to make Extract generic rather than rely on
> > HKDF-Extract?
> > In case of Sig(sk, tag1) instead of H(Sig(sk, tag1)), even in the case
> > of Extract = HKDF-Extract, a preliminary hashing doesn't necessary
> > occurs: if you use SHA-256 and ECDSA with 256-bit curve, you'll have a
> > block size of 512 bits with exactly the same size of signature input
> > (so it won't be hashed before being fed as an input to HMAC in
> > HKDF-Extract).
> > For H(Sig(sk, tag1)), in the case of HKDF, for H with an output length
> > less or equal than the block length of a hash in HKDF, there won't be
> > any additional hashing (e.g. if you build HKDF on SHA-256 and use the
> > same SHA-256 as H), so I don't see any practical problems here. I
> > apologize if I miss something here.
> >
> > From the theoretical point of view, that hashing is needed, since in
> > the security proof (while assessing one of the security properties) in
> > https://eprint.iacr.org/2018/1057.pdf we assume that the first input is
> > indistinguishable from random for an adversary (this is a basic
> > assumption when we deal with PRFs). For Sig(...) that's not correct for
> > all usual signature primitives - and we don't want the security proof
> > be made for a construction that is "slightly" different from the
> > described one (all of us know what happens when we prove security for
> > something "slightly" different).
> > The practical reason for that hashing is the following. As you know, a
> > signature key is compromised for ECDSA-like constructions if that the
> > value of a signature is obtained by an adversary, provided the RNG used
> > by signature implementation is broken (Sony PS3 ECDSA bug, etc.). Thus
> > in those cases we must treat the value of Sig(sk, tag1) as a secret.
> > Suppose that one ignores the recommendations in the draft and 1) uses
> > some valuable long-term key as sk, 2) relies on the same (potentially
> > broken) entropy source (e.g., for ECDSA), as used for CSPRNG. In that
> > case, hashing of signature output before caching it for the following
> > usage protects against leakage of a key due to side-channel attacks
> > against a cached value ("H(Sig(sk, tag1))" is used many times, for each
> > invocation of G' - so if some side channel exists, the value can be
> > leaked).
> >
> >
> > Kind regards,
> > Stanislav
> >
> > вт, 9 июл. 2019 г. в 09:46, Martin Thomson <mt@lowentropy.net>;:
> > > On Tue, Jul 9, 2019, at 15:34, Stanislav V. Smyshlyaev wrote:
> > >  > «It must be a secure PRF (for salt as a key) and preserve
> uniformness
> > >  > of IKM (for details see [SecAnalysis])».
> > >  > It should be sufficient to avoid any confusion and point to the
> right
> > >  > place as well.
> > >
> > >  Would it be better to say "Extract() MUST be a secure PRF for both
> the salt and IKM inputs and produce a uniform output." ?
> > >
> > >  A secure PRF for just salt implies that the PRF property doesn't
> apply to IKM. But to a degree we are treating both inputs equally here. If
> G(L) is non-uniform, we expect to use entropy from Sig(...) to cover any
> deficit, and vice-versa.
> > >
> > >  And when you say preserve uniformness, HKDF-Extract won't preserve
> any non-uniformity of its inputs. Taking non-uniform input and producing
> uniform output is one of its main features. So I don't quite understand the
> second part of your text as formulated.
> > >
> > >  That leads me to my next question, which I apologize for missing
> first time around. Why do you need to hash the signature? Is this because
> you want to make Extract generic rather than rely on HKDF-Extract?
> > >
> > >  Draft-05:
> > >  G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n)
> > >  Simplified:
> > >  G'(n) = Expand(Extract(Sig(sk, tag1), G(L)), tag2, n)
> > >
> > >  It seems - at least for HKDF-Extract or any function that observes
> the PRF relationship with respect to both inputs - that these are
> functionally equivalent. The only difference being that you don't have to
> define H and people using this technique don't have to run another
> iteration of the hash function. Even better, for HKDF-Extract, these are
> concretely the same unless Sig(...) is <= a single block of the hash
> function (which is possible, but not guaranteed).
> > >
> > >  > We'll add this statement after the I-D submission is open again.
> > >
> > >  I'd wait until LC ends and batch any changes :)
> > >
> > >  A new nit: you should probably include the usual RFC 2119/8174
> boilerplate. You use MUST and such.
>