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

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