Subject: [Cfrg] I-D Action: draft-irtf-cfrg-randomness-improvements-08.txt

From: [email-masked]
Date: Sat, 02 Nov 2019 16:41:23 -0700

A New Internet-Draft is available from the on-line Internet-Drafts directories.
This draft is a work item of the Crypto Forum RG of the IRTF.

        Title           : Randomness Improvements for Security Protocols
        Authors         : Cas Cremers
                          Luke Garratt
                          Stanislav Smyshlyaev
                          Nick Sullivan
                          Christopher A. Wood
	Filename        : draft-irtf-cfrg-randomness-improvements-08.txt
	Pages           : 10
	Date            : 2019-11-02

Abstract:
   Randomness is a crucial ingredient for TLS and related security
   protocols.  Weak or predictable "cryptographically-strong"
   pseudorandom number generators (CSPRNGs) can be abused or exploited
   for malicious purposes.  The Dual EC random number backdoor and
   Debian bugs are relevant examples of this problem.  An initial
   entropy source that seeds a CSPRNG might be weak or broken as well,
   which can also lead to critical and systemic security problems.  This
   document describes a way for security protocol participants to
   augment their CSPRNGs using long-term private keys.  This improves
   randomness from broken or otherwise subverted CSPRNGs.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-irtf-cfrg-randomness-improvements/

There are also htmlized versions available at:
https://tools.ietf.org/html/draft-irtf-cfrg-randomness-improvements-08
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-randomness-improvements-08

A diff from the previous version is available at:
https://www.ietf.org/rfcdiff?url2=draft-irtf-cfrg-randomness-improvements-08

Please note that it may take a couple of minutes from the time of submission
until the htmlized version and diff are available at tools.ietf.org.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

---

From: John Mattsson <[email-masked]>
Date: Wed, 20 Nov 2019 22:33:55 +0000

Hi,

This draft was discussed and recommended during the LAKE WG (https://datatracker.ietf.org/wg/lake) session yesterday, which encouraged me to review it. Some comments and suggestions.

-- I think this is great. Improving randomness more generally than RFC 6979 is very much needed. However the reliance on Signatures makes is quite unsuitable for many constrained IoT devices, which might be the single use case most needing improved randomness. Many IoT devices do not have a private signature key and adding code for signatures may take up significant storage (which may be limited). Would it be possible for the draft to also suggest a scheme with symmetric crypto commonly implemented in such devices (like e.g. SHA-256) using a symmetric key K. E.g. something like

G'(n) = Expand(Extract(HMAC(K, tag1), G(L)), tag2, n)

(I have not read [SecAnalysis]...)

-- "crucial ingredient for TLS and related security protocols"
I think it is crucial for many security protocol that are not related to TLS. Suggestion

OLD "crucial ingredient for TLS and related security protocols"
NEW "crucial ingredient for many security protocols, e.g. TLS"

-- "Implementations SHOULD apply this technique when indirect access to a private key is available and CSPRNG randomness guarantees are dubious, or to provide stronger guarantees about possible future issues with the randomness."

What if direct access is available? And what if indirect access is not available, shouldn't the recommendation then be to generate a key for this. I would suggest removing that part about access:

NEW "Implementations SHOULD apply this technique when CSPRNG randomness guarantees are dubious, or to provide stronger guarantees about possible future issues with the randomness."

--    "3.  If the CSPRNG is broken or controlled by adversary Adv, the
       output of the proposed construction remains indistinguishable
       from random provided the private key remains unknown to Adv."

This assumes that the adversary do not control other parts of the system like the generation of tag2. I don't know how probable a scenario is where the adversary controls CSPRNG but not tag2. While the construction helps in cases like [DualEC], the current text may give a wrong impression of the security when the attacker control essential part of the system like CSPRNG. I would suggest removing "or controlled" and only focus on the cases where the CSPRNG is broken or weak.

-- The abbreviation "Adv" feels a bit unnecessary. I would suggest removing the first two "Adv" and changing the third "Adv" to "the adversary"

-- "Let H be a cryptographic hash function that produces output of length M. "
    M is never used. Maybe just "Let H be a cryptographic hash function"

-- "dynamically changing" is not well-defined. I would for example say that a pendulum or y = sin(x) is dynamically changing.

-- "tag2 be a dynamically changing string (e.g., a counter) of L' bytes.  We require that L >=  n - L'."

   Note that L >=  n - L' implies that n <=  L + L'

   That is a quite big limitation of the augmented CSPRNG G' that should be stated clearer. HKDF-SHA-256 and a 64-bit encoding of tag2 gives n <= 40

   Also, that n depends on the encoding of tag2 seems strange to me.  Encoding tag2 as 0x0001, 0x00000001, or 0x0000000000000001 gives different maximum values for n. 

  I think you might want to do

          G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(n)), tag2, n)

   or not put a limit on n at all (L is already greater or equal to 32 if current security levels are followed)

-- "Thus, the security of this construction depends upon the secrecy of H(Sig(sk, tag1)) and G(L)."
    I don't think any of the 3 stated security properties depends upon G(L)

--  "If the signature is leaked, then security of G'(n) reduces to the scenario wherein randomness is expanded directly from G(L)."

This should maybe be added as a forth security property.

--  "Generally speaking, the following security theorem has been proven: if the adversary learns only one of the signature or the usual randomness
      generated on one particular instance, then under the security
      assumptions on our primitives, the wrapper construction should output
      randomness that is indistinguishable from a random string."

The above sentence "proven:   ..... should ...." seems strange. Why is there a "should"?

-- "Under these conditions, applying this construction should never yield
     worse security guarantees than not applying it assuming that applying
     the PRF does not reduce entropy."

    Isn't this only true if n < = L. Not applying the construction would optimally give n bits entropy and using the construction gives entropy L (if the adversary learns the signature or the randomness).

 -- [SP80090A] was updated to rev. 1 in 2015

 -- There are two references [X9.62], [X9.62] to ANSI X.62. [X9.62] is not used.

 -- X.62 is withdrawn. I suggest referring to FIPS 186-5(Draft) instead
     https://csrc.nist.gov/publications/detail/fips/186/5/draft

Cheers,
John

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of "[email-masked]" <[email-masked]>
Reply to: "[email-masked]" <[email-masked]>
Date: Sunday, 3 November 2019 at 07:41
To: "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: [Cfrg] I-D Action: draft-irtf-cfrg-randomness-improvements-08.txt

    
    Abstract:

    

    
    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://protect2.fireeye.com/v1/url?k=dfcd666c-83196001-dfcd26f7-867011091b6c-666021e68d3e14d5&q=1&e=7d1d5b7a-75fb-4272-834f-7629afb128df&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 21 Nov 2019 13:42:41 +0300

Dear John,

Many thanks for your great comments!

*-- I think this is great. *

Thank you! :)

*-- Would it be possible for the draft to also suggest a scheme with
symmetric crypto commonly implemented in such devices using a symmetric key
K. E.g. something like G'(n) = Expand(Extract(HMAC(K, tag1), G(L)), tag2,
n)*

Yes, I believe that it can be a great future direction of work, but this
will be another construction, requiring additional security analysis etc. I
think that the topic of improving randomness will be always a very
important one, so a lot of other good ideas and good constructions may
arise in the future.

*-- "crucial ingredient for TLS and related security protocols"*
*I think it is crucial for many security protocol that are not related to
TLS. *
*Suggestion*
*OLD "crucial ingredient for TLS and related security protocols"*
*NEW "crucial ingredient for many security protocols, e.g. TLS"*

I like this change – if Chris, Cas, Nick and Luke won’t object, I believe
it’s worth to be made.

*-- "Implementations SHOULD apply this technique when indirect access to a
private key is available and CSPRNG randomness guarantees are dubious, or
to provide stronger guarantees about possible future issues with the
randomness."*
*What if direct access is available? And what if indirect access is not
available, shouldn't the recommendation then be to generate a key for this.
I would suggest removing that part about access:*
*NEW "Implementations SHOULD apply this technique when CSPRNG randomness
guarantees are dubious, or to provide stronger guarantees about possible
future issues with the randomness."*

I like both variants, but personally I don’t see a big problem with the
current text: if direct access is available, then indirect access is also
available.

*--    "3.  If the CSPRNG is broken or controlled by adversary Adv, the*
*       output of the proposed construction remains indistinguishable*
*       from random provided the private key remains unknown to Adv."*
*This assumes that the adversary do not control other parts of the system
like the generation of tag2. I don't know how probable a scenario is where
the adversary controls CSPRNG but not tag2. While the construction helps in
cases like [DualEC], the current text may give a wrong impression of the
security when the attacker control essential part of the system like
CSPRNG. I would suggest removing "or controlled" and only focus on the
cases where the CSPRNG is broken or weak.*

>From the cryptographic point of view, the controlled CSPRNG is a stronger
vulnerability than “just” a backdoored one – since it assumes that an
adversary can try to affect CSPRNG outputs adaptively. As an example, it
can happen if CSPRNG used by some user gets its data based on a joint
system entropy pool, which can be affected by another user (an adversary).

*-- The abbreviation "Adv" feels a bit unnecessary. I would suggest
removing the first two "Adv" and changing the third "Adv" to "the
adversary"*

Agreed. Thanks!

*-- "Let H be a cryptographic hash function that produces output of length
M. "*
*    M is never used. Maybe just "Let H be a cryptographic hash function"*

Agreed! Many thanks, John!

*-- "dynamically changing" is not well-defined. I would for example say
that a pendulum or y = sin(x) is dynamically changing.*

Which word would you suggest instead of “dynamically”?..

*-- "tag2 be a dynamically changing string (e.g., a counter) of L' bytes.
We require that L >=  n - L'."*
*   Note that L >=  n - L' implies that n <=  L + L'*
*   That is a quite big limitation of the augmented CSPRNG G' that should
be stated clearer. HKDF-SHA-256 and a 64-bit encoding of tag2 gives n <= 40*
*   Also, that n depends on the encoding of tag2 seems strange to me.
Encoding tag2 as 0x0001, 0x00000001, or 0x0000000000000001 gives different
maximum values for n.*
*  I think you might want to do G'(n) = Expand(Extract(H(Sig(sk, tag1)),
G(n)), tag2, n) or not put a limit on n at all (L is already greater or
equal to 32 if current security levels are followed)*

Yes, we’ve had a lot of discussions about whether to include this
limitation (following from the security assessment, see [SecAnalysis]) into
the I-D – just for the reasons you are talking about. But since we wanted
our construction to be solid and well-proven for all recommended cases, we
decided not to omit this limitation. And you are right about the encoding
issue – the thing is that in the security assessment we assume that tag2
can have 2^L’.

*-- "Thus, the security of this construction depends upon the secrecy of
H(Sig(sk, tag1)) and G(L)."*

*    I don't think any of the 3 stated security properties depends upon
G(L)*

The first one  (“If the CSPRNG works fine…”) does. But maybe it will be
better to rephrase this as “Thus, the security of this construction depends
upon G(L) and the secrecy of H(Sig(sk, tag1)).”, so no one can read it like
“the secrecy … of G(L). What do you think?

*--  "If the signature is leaked, then security of G'(n) reduces to the
scenario wherein randomness is expanded directly from G(L)."*
*This should maybe be added as a forth security property.*

Actually, the first one is about this: “If the CSPRNG works fine”, we are
not afraid of signature leakage.

*--  "Generally speaking, the following security theorem has been proven:
if the adversary learns only one of the signature or the usual
randomness  generated on one particular instance, then under the security
assumptions on our primitives, the wrapper construction should output
randomness that is indistinguishable from a random string."*
*The above sentence "proven:   ..... should ...." seems strange. Why is
there a "should"?*

Yes, “the wrapper construction outputs” seems to be less confusing. Thanks!

*-- "Under these conditions, applying this construction should never yield*
*     worse security guarantees than not applying it assuming that applying*
*     the PRF does not reduce entropy."*
*    Isn't this only true if n < = L. Not applying the construction would
optimally give n bits entropy and using the construction gives entropy L
(if the adversary learns the signature or the randomness).*

Yes, I get your point – the phrase was about deep and nontrivial security
properties, but reducing the length of CSPRNG output can clearly trivially
make things worse. I think that adding a clarification like “(for the
corresponding length of CSPRNG output)” can help.

* -- [SP80090A] was updated to rev. 1 in 2015*
* -- There are two references [X9.62], [X9.62] to ANSI X.62. [X9.62] is not
used.*
* -- X.62 is withdrawn. I suggest referring to FIPS 186-5(Draft) instead*
*     https://csrc.nist.gov/publications/detail/fips/186/5/draft
<https://csrc.nist.gov/publications/detail/fips/186/5/draft>*

Thanks a million! Instead of FIPS 186-2 (Draft) a reference to RFC 6979
looks reasonable.

Many thanks again, John!

Best regards,
Stanislav

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 22 Nov 2019 08:27:58 -0800

> important one, so a lot of other good ideas and good constructions may

I looked at the security analysis a while ago and although it's not
fresh in my mind now, at the time I was convinced that the analysis
applied almost directly to HMAC rather than a signature. Maybe I'm
crazy, incompetent, or mis-remembering, though! :)

As a more general point: the document's intro hints at this, but
maybe it should be made more explicit that this protocol is geared
towards the case where one's key is stored in an HSM. Sure, it works
in other cases, but the choice to use signatures appears to be directly
motivated by HSMs---otherwise, why not use a cheaper construction?

-=rsw

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sun, 24 Nov 2019 18:13:04 +0300

Thanks, Riad!

The security analysis can be modified for HMAC instead of Signature without
significant problems, I suppose. And also several useful alternative
constructions can be proposed (based on HMAC or DH as an operation with a
key).
But this makes the scope of the I-D (initially motivated by TLS servers)
wider - a "menu of choices" of good solutions instead of one good solution.
If we want to do this, then, as it seems to me, the current process with an
I-D, which has already passed the RGLC and has moved to Waiting for
Document Shepherd stage, should be stopped and returned to the previous
stage of a work item before RGLC.

Personally, I really like the task of providing several good constructions
for "improving randomness" using various constructions - but I'm not sure
that it should be done in this document and not in a new one (Nick, Chris,
could you please share your opinion on this?..).

Best regards,
Stanislav

---

From: "Riad S. Wahby" <[email-masked]>
Date: Sun, 24 Nov 2019 13:37:17 -0800

> stage of a work item before RGLC.

In this case, it seems like a separate document for other constructions
is definitely more appropriate---no sense introducing serious delay for
this document.

But: would it be possible to clarify, maybe just in the intro, that this
document is primarily geared toward the HSM case?

-=rsw

---

From: John Mattsson <[email-masked]>
Date: Tue, 26 Nov 2019 12:43:50 +0000

Thanks for answers Stanislav!

>constructions can be proposed (based on HMAC or DH as an operation with a

I think that would be a very useful thing for CFRG to do in a new draft. Even if you only look at TLS servers, they may only have a PSK (RFC 4279 or TLS 1.3), and in the future, they may only have a static DH key (draft-rescorla-tls-semistatic-dh-02). More good recommendations and concrete constructs for randomness is very needed practically. The ideas in the draft to 
use a context tag1, a nonce tag2, to split of inside HSM/outside HSM, and to prove the security of the construction are great.

How to use randomness is also a topic for discussion (I don’t suggest inclusion in this draft). NIST (FIPS 186-5 Draft) is currently planning to include deterministic ECDSA but does not recommend it in general due to side-channel and fault attacks (https://eprint.iacr.org/2017/975.pdf). One of the recommendation in that paper is to calculate k based on the message, but with added noise, an approach implemented in several places such as https://signal.org/docs/specifications/xeddsa/

>As an example, it can happen if CSPRNG used by some user gets its data based on a joint

Ok, that is a good explanation why the attacker could control the CSPRNG but not other parameters. I would suggest adding that to the draft.

>Which word would you suggest instead of “dynamically”?.

unique or nonce would be better. Looking at the draft again, I think it would make sense to just rename tag2 to "nonce" and tag1 to "context". That make things easier to understand and aligns with other RFCs.

>Yes, we’ve had a lot of discussions about whether to include this limitation (following
>from the security assessment, see [SecAnalysis]) into the I-D – just for the reasons you
>are talking about. But since we wanted our construction to be solid and well-proven for
>all recommended cases, we decided not to omit this limitation. And you are right about
>the encoding issue – the thing is that in the security assessment we assume that tag2
>can have 2^L’.

If you keep the limitation, I think you need to add more clarification and guidance to the reader.

- The limitation the construction cannot output more than L + L' bytes for each nonce tag2 would be good to write in a sentence.
- Given a fixed L (e.g. 32 in HMAC-SHA-256) and a need to generate N byte of randomness. Should the implementer then choose a N - L byte encoding for the counter tag2? (Even after reading [SecAnalysis], I do not understand why the encoding of tag2 would affect the output length n). Or should the implementer choose a small L' and then generate several outputs (with different tag2) and concatenate?
- Is L' fixed or can the implementation choose different encoding lengths for each value of tag2 depending on how many output bytes are needed.
- When using a function with fixed-length output like HMAC-SHA-256 the value of L is given. When using a function with variable-length output like KMAC128 the value L is set by the user. Any recommendation there, or are all values of L equally good?
- Is L fixed or can the implementation use different L for different values of tag1?

/John

-----Original Message-----
From: Cfrg <[email-masked]> on behalf of "Riad S. Wahby" <[email-masked]>
Date: Sunday, 24 November 2019 at 22:37
To: "Stanislav V. Smyshlyaev" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-randomness-improvements-08.txt

    
    
    -=rsw
    
    _______________________________________________
    Cfrg mailing list
    [email-masked]
    https://protect2.fireeye.com/v1/url?k=d36fcb1e-8fe51eaa-d36f8b85-866a015dd3d5-c0d8356a21bc1bcc&q=1&e=4d7edf27-0f3a-48d3-885e-ec53b1141db0&u=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Fcfrg

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 27 Nov 2019 12:56:32 +0300

this document

Many thanks, Riad!

I'll definitely think about this - maybe it will be reasonable to arrange a
discussion of this (with slides, at CFRG) at IETF 107 and initiate a
document on this.
If you don't mind, I'll get in touch with you off-list in the beginning of
2020 - to discuss, what should be included in such a document. Would you
like to participate in this?..

document is primarily geared toward the HSM case?
I think that mentioning HSMs as one of most important cases when the
construction is needed, can be helpful.
Chris, Nick, what do you think?

Best regards,
Stanislav

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Wed, 27 Nov 2019 13:02:26 +0300

Many thanks, John!

Regarding a new document on different constructions for "improving
randomness", as I've just written to Riad (in the CFRG list) - I'll be
definitely happy to be involved in this, it seems really important (and,
maybe, arranging a discussion at CFRG at IETF 107 will be useful).
Don't mind if I'll get in touch with you off-list (to discuss, what should
be included in such a document) in the beginning of 2020? Would you like to
participate in this?

About the proposed changes in the I-D - I like all three of them.
Nick, Chris?

Best regards,
Stanislav

вт, 26 нояб. 2019 г. в 15:43, John Mattsson <[email-masked]>:

> I think that would be a very useful thing for CFRG to do in a new draft.
> Even if you only look at TLS servers, they may only have a PSK (RFC 4279 or
> TLS 1.3), and in the future, they may only have a static DH key
> (draft-rescorla-tls-semistatic-dh-02). More good recommendations and
> concrete constructs for randomness is very needed practically. The ideas in
> the draft to
> use a context tag1, a nonce tag2, to split of inside HSM/outside HSM, and
> to prove the security of the construction are great.
>
> How to use randomness is also a topic for discussion (I don’t suggest
> inclusion in this draft). NIST (FIPS 186-5 Draft) is currently planning to
> include deterministic ECDSA but does not recommend it in general due to
> side-channel and fault attacks (https://eprint.iacr.org/2017/975.pdf).
> One of the recommendation in that paper is to calculate k based on the
> message, but with added noise, an approach implemented in several places
> such as https://signal.org/docs/specifications/xeddsa/
>
> Ok, that is a good explanation why the attacker could control the CSPRNG
> but not other parameters. I would suggest adding that to the draft.
>
> unique or nonce would be better. Looking at the draft again, I think it
> would make sense to just rename tag2 to "nonce" and tag1 to "context". That
> make things easier to understand and aligns with other RFCs.
>
> limitation (following
> - The limitation the construction cannot output more than L + L' bytes for
> each nonce tag2 would be good to write in a sentence.
> - Given a fixed L (e.g. 32 in HMAC-SHA-256) and a need to generate N byte
> of randomness. Should the implementer then choose a N - L byte encoding for
> the counter tag2? (Even after reading [SecAnalysis], I do not understand
> why the encoding of tag2 would affect the output length n). Or should the
> implementer choose a small L' and then generate several outputs (with
> different tag2) and concatenate?
> - Is L' fixed or can the implementation choose different encoding lengths
> for each value of tag2 depending on how many output bytes are needed.
> - When using a function with fixed-length output like HMAC-SHA-256 the
> value of L is given. When using a function with variable-length output like
> KMAC128 the value L is set by the user. Any recommendation there, or are
> all values of L equally good?
> Subject: Re: [Cfrg] I-D Action:
> draft-irtf-cfrg-randomness-improvements-08.txt
>