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

["Stanislav V. Smyshlyaev" <[e-mail]>]

>> 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 <[e-mail]>:

> 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 <[e-mail]>:
> > > 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.
>