Subject: [Crypto-panel] Request for review: draft-irtf-cfrg-randomness-improvements

From: Alexey Melnikov <[email-masked]>
Date: Fri, 6 Mar 2020 17:44:03 +0000

Dear Crypto Panel members,

I would like to request at least one review for this document: 
<https://datatracker.ietf.org/doc/draft-irtf-cfrg-randomness-improvements/>

Thank you,

Alexey

---

From: Russ Housley <[email-masked]>
Date: Fri, 6 Mar 2020 13:55:30 -0500

I can do a review, but it will probably be 2 week.  I yield if someone else can do it sooner.

Russ

> On Mar 6, 2020, at 12:44 PM, Alexey Melnikov <[email-masked]> wrote:
> 
> I would like to request at least one review for this document: <https://datatracker.ietf.org/doc/draft-irtf-cfrg-randomness-improvements/>
> 
> Thank you,
> 
> Alexey
> 
> _______________________________________________
> Crypto-panel mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/crypto-panel

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Fri, 6 Mar 2020 21:07:41 +0100

I can do a review as well.

> On 6 Mar 2020, at 18:44, Alexey Melnikov <[email-masked]> wrote:
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 6 Mar 2020 20:17:37 +0000

I'll go through it as well

> -----Original Message-----
> From: Crypto-panel <[email-masked]> On Behalf Of
> Karthikeyan Bhargavan
> Sent: Friday, March 06, 2020 3:08 PM
> To: Alexey Melnikov <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Crypto-panel] Request for review: draft-irtf-cfrg-randomness-
> improvements
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Mon, 9 Mar 2020 15:32:11 +0000

This draft looks quite good, congratulations to the authors.  However, because this review wouldn't feel complete unless I have some complaints, here are some nits:

Who is this draft targeted towards?  I believe that, at some point, we'll need an RFC detailed enough that we could give it to an implementor and be reasonably confident that he'll implement something secure.  Currently, this isn't that - it leaves far too many options open for an implementor (who may be somewhat ignorant of cryptography) to make bad choices.
Things that should be specified (and we could allow a range of selections)
	- What is Extract.  The draft gives as an example HKDF-Extract; with what hash function?
	- What is L (the size of output of the Extract function)?
	- What is H?
	- What is Expand (HKDF-Expand?)
Also, we might want to expand on the guidance relating to the generation of tag2 - I would suggest that we should mandate (or, at least, strongly suggest) that it consist of a timestamp (if a real time clock is available) and a counter (which is incremented on every invocation).  One issue with the current recommendation (needs to be unique for each combination of G(L), tag1 and sk values) is that might be difficult to ensure on a platform with no real time clock (and while this is not an ideal scenario, it will happen, and we shouldn't tell the user "you have to do this" when it may be infeasible.

The draft states that:
      We require that L >= n - L' for each value of tag2.

Why is this requirement here?  It would appear to me that, because tag2 is a potentially public string, its length is not specifically relevant to the security (as long as it is long enough that it never repeats).  One can certainly conceive of badly chosen options (L=1, L' = 32, n no more than 32) that is quite insecure but meets this criteria.

The draft states that:
	Sig MUST be a deterministic signature function, e.g., deterministic
	ECDSA [RFC6979], or use an independent (and completely reliable)
	entropy source
	...
	if the
	signatures are probabilistic and use weak entropy, our construction
	does not help and the signatures are still vulnerable due to repeat
	randomness attacks.
Why is this requirement here?  I would disagree with the reasoning; if the computation of Sig involves calls to a potentially weak RNG, it will still generate a valid signature; and (assuming that the private key and the signature scheme is secure), the attacker cannot guess any valid signature to a message.
If the concern is that a signature with a weak RNG might leak the private key (e.g. ECDSA), then I would note that this draft mandates that the signature not be leaked, and that it uses the hash of the signature (and the draft might want to give guidance that it's the hash that needs to be cached, and that the signature should be discarded immediately after the hash has been computed).

The document claims:
	the relatively inexpensive
	computational cost of HKDF dominates when comparing G' to G

I don't believe that is quite as true as the document hopes.  Most good CSRNGs run considerably faster than the HKDF Extract/Expand pair; hence G' is rather more expensive than the underlying G.  One could state that the cost of G' is generally considerably smaller than the protocol that's using G' (e.g. the ECDH operation).

In the tag1 section (in section 4), the document promises that section 5 will give additional advice on how some TLS protocol information could be used in generating a tag1 value.  Section 5 doesn't give any such guidance.

> From: Crypto-panel <[email-masked]> On Behalf Of Scott
> Fluhrer (sfluhrer)
> Sent: Friday, March 06, 2020 3:18 PM
> To: Karthikeyan Bhargavan <[email-masked]>; Alexey
> Melnikov <[email-masked]>
> > Subject: Re: [Crypto-panel] Request for review:
> > draft-irtf-cfrg-randomness- improvements
> >

---

From: Jon Callas <[email-masked]>
Date: Tue, 10 Mar 2020 15:28:49 -0700

I also read through it and agree with others -- it's a nice paper. I think there are a number of things to improve it, too, and I'm going to keep from repeating others.

* It could use an introduction that's a somewhat an expansion of the abstract. It's hard to recognize what the RFC is trying to say otherwise. It took me three readings, and I only really figured out what's going on while writing up these comments. This is a great crypto engineering paper, spliced into an RFC template. As an RFC, it ought to say some things actionable. Most people who read RFCs are quasi-knowledgeable implementers. It's always good to spell things out for them. I'm a knowledgable implementer and I like things spelled out.

* Terms should be used precisely. For example, "CSPRNG" means "Cryptographically Strong Pseudo-Random Number Generator." If you have a CSPRNG that is not cryptographically strong, then say "PRNG." The term CSPRNG should only be used when the PRNG is CS. The abstract defines it, putting scare quotes around "cryptographically strong" with the result being that the reader has to think about what the term means every time it's used. In following discussion, I'm using "CSPRNG" to mean something actually cryptographically secure; "PRNG" to mean mathematically pseudo-random but not cryptographically secure; and "RNG" to mean an allegedly random generator such as one that is statistically random but utterly guessable.

* Abstract says: "This improves randomness from broken or otherwise subverted CSPRNGs." I suggest: "This improves the security of a protocol when it uses a broken or subverted PRNG." My rationale is that "security" is a better term here than "randomness" and that there are a whole lot of broken RNGs and relatively few subverted ones; broken is not a subset of subverted. Moreover, there are problems that are neither subversion nor a broken RNG that this can help. For example, a state compromise of a CSPRNG is neither broken as a CSPRNG nor is it subverted in the sense that DualEC DRBG was subverted.

* I'd like to see some general cases of brokenness. I can think of three general cases.

a) A mathematically pseudo random generator with known state. For example, AES in counter mode with a fixed key of zero and a naive counter (0, 1, 2 ...). Looking at the output, it's secure, but if you know the state, it's not. This models state compromises, VM restarts that reuse state, and many other issues that are otherwise-good yet compromised RNGs. 

The Debian bug falls in here, because it was a badly seeded, but mathematically good RNG. We could also put in here controversies about the Intel RDRAND instruction, which many people believe is broken or subverted despite being apparently a CSPRNG.

b) An RNG with non-random output. For example, the octets 0, 1, 2, ... 255 repeated. The DualEC DRBG, whose state could be learned if an eavesdropper could see small bits of raw output falls into this case.

c) A totally broken bit string. For example a string of all zero bits or all one bits.

In all of these cases, the technique enhances the security of the input RNG such that breaking the RNG output is equivalent to breaking the underlying secret key. This is really nice and the whole reason to use this technique. 

I think this covers the brokenness that the draft does in a slightly more rigorous and general form.

* In the introduction, it seems to be a little too TLS-specific. TLS is a marvelous example of a protocol, and the specific one the authors are addressing, but the technique is good in many other places. 

* I think there's another broad use case that can be added. For example, get a sample from the main RNG, do this protection on the sample, and then use that to seed some suitable DRBG and use it in a subsystem. This would make a nice Section 6 after the TLS example that's more generalized. I think two or three paragraphs is all that is needed.

Summing up, I like this. Various times in the past, I've done something ad hoc that was similar to this, kinda the way NAXOS did, and having this be a documented implementation trick is a good thing.

	Jon

---

From: Russ Housley <[email-masked]>
Date: Sun, 15 Mar 2020 17:20:11 -0400

Document: draft-irtf-cfrg-randomness-improvements-10
Reviewer: Russ Housley
Review Date: 2020-03-15

The CFRG Chairs asked the Crypto Panel to review this document.
I am providing one review.  There may be others.

Summary:

A technique for improving the security of a random number generator
is provided.  Nice work, but some improvements in the document are
desirable before publication as an Informational RFC.

Major Concerns:

Section 3 requires that "Sig MUST be a deterministic signature
function".  This is inconsistent with the third paragraph in
Section 9.  I think that any "good" signature algorithm with a
"properly" generate private key should work out fine.  So, please
remove the requirement for a deterministic signature function.

Section 4 says: "See Section 5 for example protocol information that
can be used in the context of TLS 1.3."  I did not find that in
Section 5 or anywhere else.

Section 9: Please inclue the rationale for this requirement that
L >= n - L' for each value of tag2.

Minor Concerns:

Abstract: I think it is too long.  I think the examples of broken
random sources can be moved to the Introduction.

Abstract and Intoduction: Why call out TLS?  TLS, IPsec, S/MIME, PGP,
and every other security protocol relies upon random numbers.

Section 4: A real-time clock should be listed as a possible source for
a portion of the tag2 value.

Nits:

I do not think the assignment of "Adv" to the adversary helps explain
the goals.  I think plain English is fine here.  I suggest:

Section 1: s/An adversary Adv with /An adversary with /

Section 1: s/by adversary Adv,/by an adversary,/

Section 1: s/unknown to Adv./unknown to the adversary./

Suggestion:

Appendix A of [SecAnalysis] required an implementation of the algorithm,
with reasonable choices for all of the parameters.  I think it would be
useful to put that pseudo-code in an Appendix of this document along
with a test vector.