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

"Stanislav V. Smyshlyaev" <smyshsv@gmail.com> Tue, 09 July 2019 09:32 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 C4E3E1203DB for <cfrg@ietfa.amsl.com>; Tue, 9 Jul 2019 02:32:16 -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 nmnbZOptVQ8M for <cfrg@ietfa.amsl.com>; Tue, 9 Jul 2019 02:32:14 -0700 (PDT)
Received: from mail-lj1-x232.google.com (mail-lj1-x232.google.com [IPv6:2a00:1450:4864:20::232]) (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 A9FD11200B6 for <cfrg@irtf.org>; Tue, 9 Jul 2019 02:32:13 -0700 (PDT)
Received: by mail-lj1-x232.google.com with SMTP id 16so18829752ljv.10 for <cfrg@irtf.org>; Tue, 09 Jul 2019 02:32:13 -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=N3/erZGkRIsTCwMBI+DqyMprlWpvK/YbU5NwPKMr6+E=; b=qt/IUpRHrOyFBkAb/1VNyToD7NOXeLAOmIRwoiBa7VpJ9XwGqSMz6KohQTx0brlEbi tyzIQVLiRknnHsejxCXExJ+sSkInT0W/UluX7l0C0JYSPv1M+lIudzre7Sf6M/b9odFg iXFzRpVySFyIzUJ2JA6fLXDapnTlGlCIOK9DY9veCPttcCnqK20e4SSZbwjAi4WzroNH i7X7r7/rhLb5StKqzrXcD1sVcbYGe+8Mvb6p6gKIHOxFExgDz/gusAoOjAxs7OxHdMZH PxWLB/7JaNhHwFvkZe+luvsjWNW6rXKOnd4KKBtzjbOUPVFlO1Ja+9p43fr0h9+rVOmq 0tEA==
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=N3/erZGkRIsTCwMBI+DqyMprlWpvK/YbU5NwPKMr6+E=; b=m9Xn7eaHPRjvAAqy+9qZocN9W7SuYB3M7Y9CKY3m6gGBy0tzjwW6yUp/erVvl/jyXV IwRMO/SJ7FffO7VsdV3AOGH74yYaStM3JRQLz+mM6B1R8lk2Nv58fHwkTBMQSSOZFNGy oSPNsmvcrBzEAj4r846CQXCMYSMHIx9Qjl4vfmFUaT6eThP2XFKGcmWHPdhD2FR1PN+G J8ypsV8MQxTWO1UYUmO6VI/NyNMu3mc7tyEZzBgIHPPdFnp5ShIP7E7VZbk1r+yo5SIO XiDsW3CYzyw1IJpDtF9c+7cw7ndCX27yazfTXL5T4/aDgsH+PThFUdvcj6GcgYd2oUon dJig==
X-Gm-Message-State: APjAAAXrqYAyHxZIySSS9FLbWfDPvOq15BnRk8pDnl+INxJ7y2n29RzF aSl0JlCx6KSIYDkPNdhUpoGzzlLP/07n8ZKvx5I=
X-Google-Smtp-Source: APXvYqwIIK7pyupq9tlbpmjxGRpeGUcM7lUuIKFec3sJxlwZkDi3UV2csaHMNa1y3iqaAL3c/S27RUQKNgsMeZ2ajlA=
X-Received: by 2002:a2e:98d7:: with SMTP id s23mr10764871ljj.179.1562664731810; Tue, 09 Jul 2019 02:32:11 -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>
In-Reply-To: <5518f189-b680-4e24-99f6-7cd6ae1ad116@www.fastmail.com>
From: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
Date: Tue, 09 Jul 2019 12:33:35 +0300
Message-ID: <CAMr0u6mr6arqQ15oM0BcL0gWJSzbwEyS2BBL7dgJkd00yhE8YA@mail.gmail.com>
To: Martin Thomson <mt@lowentropy.net>
Cc: "Salz, Rich" <rsalz@akamai.com>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000003e20e5058d3c3c07"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/t7v5Gw38ruCG49RgrXO7TPDE0hw>
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 09:32:17 -0000

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