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

From: Alexey Melnikov <[email-masked]>
Date: Wed, 3 Jul 2019 14:56:51 +0100

Dear CFRG participants,

This message is starting 2 weeks RGLC on 
draft-irtf-cfrg-randomness-improvements-05 ("Randomness Improvements for 
Security Protocols"), that will end on July 17th 2019. If you've read 
the document and think that it is ready (or not ready) for publication 
as an RFC, please send a message in reply to this email or directly to 
CFRG chairs (Kenny Paterson <[email-masked]> and Alexey 
Melnikov <[email-masked]> in this case). If you also have 
detailed comments, these woulbe be very helpful at this point.

Thank you,

Alexey, for CFRG chairs.

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 3 Jul 2019 15:39:51 +0000

I re-read the document; it’s ready to move forward.

I would revise the last sentence of the first paragraph of Section 1 to be “recover secret key material used to protect the connection.”

From: Alexey Melnikov <[email-masked]>
Date: Wednesday, July 3, 2019 at 9:57 AM
To: "[email-masked]" <[email-masked]>
Subject: [Cfrg] RGLC on draft-irtf-cfrg-randomness-improvements-05

draft-irtf-cfrg-randomness-improvements-05

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 04 Jul 2019 10:56:47 +1000

This is good, though I have a number of editorial comments, and a question (the answer to which seems important, but I am happy to be wrong).

The use of "let x be" in the first paragraph of Section 2 isn't necessary.  You don't use 'x' anywhere but in that statement, so it could be rephrased more simply.

   When properly instantiated, the output of a CSPRNG should be indistinguishable from a random string of bits.  However, as previously discussed, this is not always true.  To mitigate this problem, we propose an approach for wrapping CSPRNG output with a construction that mixes secret data into a value that may be lacking randomness.

In Section 2, the rules about release of Sig(..) are repeated:

   Sig(sk, tag1) should only be computed once for the lifetime of the
   randomness wrapper, and MUST NOT be used or exposed beyond its role
   in this computation.  

I believe that this is a "need only" rather than a "should only".  There is no requirement that the signature not be recalculated or replaced over time, only that there is no need to do so.  Use of "should" implies recommendation.  This follows from text that repeats this later: "In systems where signature computations are expensive, Sig(sk, tag1) may be cached."  Maybe only say this once.

  To achieve this, tag1 may have the format that
   is not supported (or explicitly forbidden) by other applications
   using sk.

The "may have the format" statement implies permissiveness in a 2119 sense, but the intent is to communicate a strategy for achieving the hard requirement.  Perhaps this could be reworded to say "If sk could be used for other purposes, then selecting a value for tag1 that is different than the form allowed by those other uses ensures that the signature is not exposed."  Is this statement better moved to Section 3, with only a forward reference here?

   In that case the relative cost of using G'(n) instead
   of G(n) tends to be negligible with respect to cryptographic
   operations in protocols such as TLS.  

You might instead say that the relatively inexpensive computational cost of HKDF dominates when comparing G' to G.

In Section 3, the "it" in this sentence isn't clear: "It is needed to address the problem of CSPRNG state cloning (see [RY2010]). "

The construction of tag2 is confusing.  I would instead say: "A nonce. That is, a value that is unique for each use of the same combination of G(n), tag1, and sk values.  The tag2 value can be implemented using a counter, or a timer, provided that the timer is guaranteed to be different for each invocation of G'(n)."

In Section 4, the recommended construction for tag1 fails to take into account some of the advice from Sections 3 and 7.  Specifically, it does not encode include information about the host.  And it does not explicitly point out that the value is constructed in a way as to be illegal in TLS 1.3 (because TLS 1.3 signature inputs all start with a sequence of 0x20).

And, buried at the bottom, the question:

I'm sure that the analysis covers this, but what are the concrete requirements on the randomness extraction and expansion functions?  You use HKDF as an example, but you don't restrict this to HKDF.  That implies some properties, but as we learned from TLS analysis, there are properties that HKDF provides that we might rely on that are different than a generic KDF function.  For TLS, one property we rely on HKDF providing is collision resistance (which follows from its use of collision-resistant hash functions).  It would appear here that this relies on preimage resistance.  As the intro says H(x, sk) might be sufficient, but that implies that H() provides preimage resistance.  This is never stated, but it seems rather important.

On Wed, Jul 3, 2019, at 23:57, Alexey Melnikov wrote:
> draft-irtf-cfrg-randomness-improvements-05 ("Randomness Improvements 
> for Security Protocols"), that will end on July 17th 2019. If you've 
> read the document and think that it is ready (or not ready) for 
> publication as an RFC, please send a message in reply to this email or 
> directly to CFRG chairs (Kenny Paterson <[email-masked]> 
> and Alexey Melnikov <[email-masked]> in this case). If you 
> also have detailed comments, these woulbe be very helpful at this point.
> 
> Thank you,
> 
> Alexey, for CFRG chairs.
> 
> 
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 9 Jul 2019 08:35:53 +0300

Dear Martin and Rich,

Many thanks for your positive feedback, for your comments and
considerations!

Regarding the last question of Martin, we (Cas, Christopher, Luke, Nick,
Liliya and I) believe that the following additional statement in the I-D
after
"Let Extract(salt, IKM) be a randomness extraction function, which accepts
a salt and input keying material (IKM) parameter and produces a
pseudorandom key of length L suitable for cryptographic use."
will help:
«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. We'll add this statement after the I-D submission is open again.

Regarding the other minor concerns – we've addressed a few of them in the
updated version of the I-D, which we managed to submit yesterday before the
cut-off; after the submission is open again, we'll address all other ones.

Kindest regards,
Stanislav

чт, 4 июл. 2019 г. в 03:57, Martin Thomson <[email-masked]>:

> This is good, though I have a number of editorial comments, and a question
> (the answer to which seems important, but I am happy to be wrong).
>
> The use of "let x be" in the first paragraph of Section 2 isn't
> necessary.  You don't use 'x' anywhere but in that statement, so it could
> be rephrased more simply.
>
>    When properly instantiated, the output of a CSPRNG should be
> indistinguishable from a random string of bits.  However, as previously
> discussed, this is not always true.  To mitigate this problem, we propose
> an approach for wrapping CSPRNG output with a construction that mixes
> secret data into a value that may be lacking randomness.
>
> I believe that this is a "need only" rather than a "should only".  There
> is no requirement that the signature not be recalculated or replaced over
> time, only that there is no need to do so.  Use of "should" implies
> recommendation.  This follows from text that repeats this later: "In
> systems where signature computations are expensive, Sig(sk, tag1) may be
> cached."  Maybe only say this once.
>
> The "may have the format" statement implies permissiveness in a 2119
> sense, but the intent is to communicate a strategy for achieving the hard
> requirement.  Perhaps this could be reworded to say "If sk could be used
> for other purposes, then selecting a value for tag1 that is different than
> the form allowed by those other uses ensures that the signature is not
> exposed."  Is this statement better moved to Section 3, with only a forward
> reference here?
>
> You might instead say that the relatively inexpensive computational cost
> of HKDF dominates when comparing G' to G.
>
> In Section 3, the "it" in this sentence isn't clear: "It is needed to
> address the problem of CSPRNG state cloning (see [RY2010]). "
>
> The construction of tag2 is confusing.  I would instead say: "A nonce.
> That is, a value that is unique for each use of the same combination of
> G(n), tag1, and sk values.  The tag2 value can be implemented using a
> counter, or a timer, provided that the timer is guaranteed to be different
> for each invocation of G'(n)."
>
> In Section 4, the recommended construction for tag1 fails to take into
> account some of the advice from Sections 3 and 7.  Specifically, it does
> not encode include information about the host.  And it does not explicitly
> point out that the value is constructed in a way as to be illegal in TLS
> 1.3 (because TLS 1.3 signature inputs all start with a sequence of 0x20).
>
> I'm sure that the analysis covers this, but what are the concrete
> requirements on the randomness extraction and expansion functions?  You use
> HKDF as an example, but you don't restrict this to HKDF.  That implies some
> properties, but as we learned from TLS analysis, there are properties that
> HKDF provides that we might rely on that are different than a generic KDF
> function.  For TLS, one property we rely on HKDF providing is collision
> resistance (which follows from its use of collision-resistant hash
> functions).  It would appear here that this relies on preimage resistance.
> As the intro says H(x, sk) might be sufficient, but that implies that H()
> provides preimage resistance.  This is never stated, but it seems rather
> important.
>

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 09 Jul 2019 16:46:25 +1000

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.

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 9 Jul 2019 12:33:35 +0300

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 <[email-masked]>:

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

---

From: "Martin Thomson" <[email-masked]>
Date: Tue, 09 Jul 2019 19:44:43 +1000

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:
> Yes, that's the way we plan to do this (2 weeks of RGLC will end before 
> the submission is available again :) ).
> 
> >> 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. 
> 
> 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 
> 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).
> 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
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 9 Jul 2019 15:01:43 +0300

>> 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 <[email-masked]>:

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