Subject: [Cfrg] comments on Randomness Improvements for Security Protocols

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 17 Jul 2018 17:19:42 +0000

Hi Cas, Luke, Stanislav, Nick, Chris, and CFRG members,

I would like to share some comments on draft-irtf-cfrg-randomness-improvements-02.

As I understand it, the draft aims to improve randomness "from broken or otherwise subverted CSPRNGs” through the replacement of a CSPRG with a function that depends on a private signing key (indirectly, through a signature) and/or the entropy source used in a signature scheme, as well as the CSPRG state.   That’s a worthy goal; the construction in the draft could also improve security in cases where entropy source that seeds the CSPRG itself might be weak, and I suggest adding that motivation to the abstract (unless I’m missing something there).

The phrase "mix their long-term private key into the entropy pool(s) from which random values are derived” is misleading.   It seems more accurate to say that the draft defines a CSPRG G’, defined as

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

that makes use of G() and other functions, and that the state of G’ consists of the state associated with G plus the state associated with tag2.  I think the draft would be more understandable to potential implementers if written that way.

There is an important problem that the draft does not speak to:  the fact that CSPRG state is sometimes unwittingly cloned due to virtual machine full snapshots [1] or process forking.   This problem occurs in the real world [2], and deserves to be addressed.   I suggest extending the description of how tag1 is computed in a way that recommends incorporating information specific to the process,  VM-guest, or container, and that considers when tag1 is initialized.  It would also be good to add discussion to the Security Considerations section; we especially want to make sure that the reader doesn’t walk away with a misunderstanding that all CSPRG problems are addressed by this draft.

The draft says that "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.”  Doesn’t that imply that the signature scheme MUST somehow avoid signing tag1, either because tag1 is unpredictable, or the message format somehow makes that impossible?   This seems like an important security consideration, if people were to depend on this construction to compensate for weak CSPRGs or entropy sources.

The construction is somewhat underspecified.  Potential implementers could ask: what functions should be used for Extract, Expand, and H, and what security levels can be expected?  What crypto agility considerations are there?    How can I validate an implementation?   What implementation pitfalls should I look out for?

“A security analysis was performed by two authors of this document” - is there something published somewhere?   I suggests either expanding the writeup or adding a reference.

Thanks for your consideration,

David

[1] Ristenpart and Yilek, When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography<https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwi_qYO7zabcAhWNKXwKHVVADFQQFggyMAE&url=https%3A%2F%2Frist.tech.cornell.edu%2Fpapers%2Fndss10x.pdf&usg=AOvVaw2H9tYsfesotjFRkPX4u6e8>, NDSS, 2010.
[2] McGrew, Anderson, Fluhrer, Shenefeil, PRNG Failures and TLS Vulnerabilities in the Wild<https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx>, RWC 2017.

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 17 Jul 2018 17:42:55 +0000

I sent to ietf.org instead of irtf.org the first time – apologies if you get the message twice.

David

David

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 17 Jul 2018 13:45:48 -0400

Dear David,

Thank you very much for your comments - they are very constructive and
helpful.

I’m very glad that your overall opinion of the document motivation and
principles seems to be positive.

Personally, I agree with the vast majority of your considerations.

Indeed, one important part of motivation is connected with the initial
entropy source itself - it’s stated clearly in my slides which I’ll be
presenting today, and we’ll add corresponding clarifications to the
document.

We’ll definitely think about clearer notation, e.g. G’ as you suggested.

About the cloning issue - yes, that’s an extremely important one; tag1 is
exactly the part that’s introduced to fight such problems. I’ll comment on
this issue during my talk today and we’ll think about how to clarify this
in the draft.

The phrase about Sig “to be computed once” should be refined to be more
clear - your point is correct here.

Specifications, code examples and updated security assessment are the
things “to be done” - of course we plan to solve these issues before
finishing the document.

I’ll be very happy to discuss these or other considerations of yours at
CFRG session today, if you wish.

Kindest regards,
Stanislav

вт, 17 июля 2018 г. в 13:20, David McGrew (mcgrew) <mcgrew=
[email-masked]>:

> I would like to share some comments on
> draft-irtf-cfrg-randomness-improvements-02.
>
> As I understand it, the draft aims to improve randomness "from broken or
> otherwise subverted CSPRNGs” through the replacement of a CSPRG with a
> function that depends on a private signing key (indirectly, through a
> signature) and/or the entropy source used in a signature scheme, as well as
> the CSPRG state.   That’s a worthy goal; the construction in the draft
> could also improve security in cases where entropy source that seeds the
> CSPRG itself might be weak, and I suggest adding that motivation to the
> abstract (unless I’m missing something there).
>
> The phrase "mix their long-term private key into the entropy pool(s) from
> which random values are derived” is misleading.   It seems more accurate to
> say that the draft defines a CSPRG G’, defined as
>
> that makes use of G() and other functions, and that the state of G’
> consists of the state associated with G plus the state associated with
> tag2.  I think the draft would be more understandable to potential
> implementers if written that way.
>
> There is an important problem that the draft does not speak to:  the fact
> that CSPRG state is sometimes unwittingly cloned due to virtual machine
> full snapshots [1] or process forking.   This problem occurs in the real
> world [2], and deserves to be addressed.   I suggest extending the
> description of how tag1 is computed in a way that recommends incorporating
> information specific to the process,  VM-guest, or container, and that
> considers when tag1 is initialized.  It would also be good to add
> discussion to the Security Considerations section; we especially want to
> make sure that the reader doesn’t walk away with a misunderstanding that
> all CSPRG problems are addressed by this draft.
>
> The draft says that "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.”  Doesn’t that imply that the
> signature scheme MUST somehow avoid signing tag1, either because tag1 is
> unpredictable, or the message format somehow makes that impossible?   This
> seems like an important security consideration, if people were to depend on
> this construction to compensate for weak CSPRGs or entropy sources.
>
> The construction is somewhat underspecified.  Potential implementers could
> ask: what functions should be used for Extract, Expand, and H, and what
> security levels can be expected?  What crypto agility considerations are
> there?    How can I validate an implementation?   What implementation
> pitfalls should I look out for?
>
> “A security analysis was performed by two authors of this document” - is
> there something published somewhere?   I suggests either expanding the
> writeup or adding a reference.
>
> [1] Ristenpart and Yilek, When Good Randomness Goes Bad: Virtual Machine
> Reset Vulnerabilities and Hedging Deployed Cryptography
> <https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0ahUKEwi_qYO7zabcAhWNKXwKHVVADFQQFggyMAE&url=https%3A%2F%2Frist.tech.cornell.edu%2Fpapers%2Fndss10x.pdf&usg=AOvVaw2H9tYsfesotjFRkPX4u6e8>
> , *NDSS*, 2010.
> [2] McGrew, Anderson, Fluhrer, Shenefeil, PRNG Failures and TLS
> Vulnerabilities in the Wild
> <https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx>, *RWC* 2017.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Thu, 19 Jul 2018 16:48:57 +0300

Thank you very much again for the comments and considerations again.

Based on this e-mail discussion and on discussions after the CFRG session,
for now, I see the following list of things to be done with the "Randomness
improvements..." draft.

1) Add the issue with weak (or broken) initial entropy source seeding the
CSPRNG as additional motivation.
2) Refine the security considerations related to
a) the usage of Sig - to explicitly address the issue with desired secrecy
of Sig(sk, tag1).
b) tag1 - to address the issue with cloning VMs more explicitly.
3) Think about better wordings about the end construction. Personally, I
like David's idea of defining this as something like CSPRNG G'.
4) Update security assessment taking into account the new version of the
construction and three target properties enumerated in the document.
5) Add more details to the description to make it fully specified.
6) Do more experiments with existing implementations.

Comments about additional issues with the draft to be addressed are highly
appreciated.

Best regards,
Stanislav Smyshlyaev

2018-07-17 20:45 GMT+03:00 Stanislav V. Smyshlyaev <[email-masked]>:

>> The construction is somewhat underspecified.  Potential implementers
>> could ask: what functions should be used for Extract, Expand, and H, and
>> what security levels can be expected?  What crypto agility considerations
>> are there?    How can I validate an implementation?   What implementation