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

From: [email-masked]
Date: Fri, 23 Mar 2018 03:12:46 -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-00.txt
	Pages           : 7
	Date            : 2018-03-23

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.  This document
   describes a way for security protocol participants to mix their long-
   term private key into the entropy pool(s) from which random values
   are derived.  This augments and 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-00
https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-randomness-improvements-00

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: "Salz, Rich" <[email-masked]>
Date: Fri, 23 Mar 2018 13:56:35 +0000

I am not a cryptographer, so please excuse possibly-stupid questions.

I think it's a mistake to use CSPRNG for anything that is weak or actually, ya know, not cryptographically strong.  So perhaps just use RNG. That also makes it more clear that this is to help "shore up" weak RNG's. Do they rise to the level of a true CSPRNG?  That's something I'd like to see the draft discuss.

I am also confused by "randomness," "random bytes," and "entropy" and would appreciate more clarity and precision around those terms.  For what it's worth, OpenSSL uses "entropy" as a bitstream to feed into its CSPRNG, and what you get out is "random bytes."  We use the word "randomness" rather than say thing like "a measure of the entropy in the bytes."

So when would someone actually use this?  To add additional seed material when they don't have a good source of initial random bits?  (It's also a neat hack to use the private key as a personalization data into a DRBG, but I don't think it gets beyond the "neat hack" level.)

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:09:49 +0000

Hi Rich,

Thanks for the comments. Please see inline below.

On Fri, Mar 23, 2018 at 6:56 AM Salz, Rich <rsalz=
[email-masked]> wrote:

> I think it's a mistake to use CSPRNG for anything that is weak or
> actually, ya know, not cryptographically strong.  So perhaps just use RNG.
> That also makes it more clear that this is to help "shore up" weak RNG's.
> Do they rise to the level of a true CSPRNG?  That's something I'd like to
> see the draft discuss.
>

Good point. I'll review our use of these terms and clean them up where
appropriate.

>
> I am also confused by "randomness," "random bytes," and "entropy" and
> would appreciate more clarity and precision around those terms.  For what
> it's worth, OpenSSL uses "entropy" as a bitstream to feed into its CSPRNG,
> and what you get out is "random bytes."  We use the word "randomness"
> rather than say thing like "a measure of the entropy in the bytes."
>

Your definitions seem sensible to me. If there are no objections, I'll try
to align the draft to match.

>
> So when would someone actually use this?  To add additional seed material
> when they don't have a good source of initial random bits?  (It's also a
> neat hack to use the private key as a personalization data into a DRBG, but
> I don't think it gets beyond the "neat hack" level.)
>

The construction as presented does not re-seed the DRBG -- it simply
augments the output when needed via the wrapper. One might use this to
harden against system RNGs. Alternatively, as you describe, one could use
this to seed and personalize your own DRBG.

Best,
Chris

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:09:49 +0000

Hi Rich,

Best,
Chris

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 26 Mar 2018 13:18:47 +0000

Thanks for the reply.  Feel free to steal text from https://www.openssl.org/docs/manmaster/man3/RAND_add.html and others, if appropriate.

> Alternatively, as you describe, one could use this to seed and personalize your own DRBG..

Mentioning that would be useful; I keep bumping into folks who want a separate DRBG per connection …

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 13:28:48 +0000

On Mon, Mar 26, 2018 at 6:18 AM Salz, Rich <[email-masked]> wrote:

> Thanks for the reply.  Feel free to steal text from
> https://www.openssl.org/docs/manmaster/man3/RAND_add.html and others, if
> appropriate.
>

I'll borrow, with the appropriate citation. :-)

> separate DRBG per connection …

I concur.

Cheers,
Chris

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 26 Mar 2018 06:33:23 -0700

I will note that the unit Shannon exists and might be a useful unit to
use in this draft on randomness improvements to disambiguate a bit or
number of bits in memory from the number of Shannons in that sample.

    The shannon (symbol: Sh), more commonly known as the bit, is a unit
    of information and of entropy defined by IEC 80000-13. One shannon
    is the information content of an event occurring when its
    probability is one half.[1][2]

[1] "IEC 80000-13:2008". International Organization for Standardization.
    Retrieved 21 July 2013.
[2] https://en.wikipedia.org/wiki/Shannon_(unit)

-- 
Mark D. Baushke
[email-masked]

---

From: Dan Brown <[email-masked]>
Date: Mon, 26 Mar 2018 14:19:34 +0000

Hi,

I think the draft used “entropy” just fine, and needs no correction.  

Why: Entropy is a measure, like length or weight, so (in precise language) it should not be used for the thing being measured.  So, I do (mildly) “object” to using the term “entropy” for to calling a bunch of bits that has entropy.  The current draft using compound nouns like “entropy output”, etc., which is not best grammar (like saying length rope, or weight fuel), but is ok, but is more precise than saying just “entropy”.

I think the draft uses “randomness” in a  more problematic way, but this is just an instance of a common, perennial (and unfortunate) conundrum (in terminology).  

Why: Mathematicians generally use the term “random variable” to describe non-uniform distributions, like normal distribution, binomial distribution, even zero-entropy variables (like constants).  (E.g. random variable X is constant if and only if Var(X)=0, or it its entropy is zero.)  By contrast, some cryptographers use “random” to mean uniform, as in pseudorandom, or PRNG, DRBG, CSPRNG, etc., which to me is a mistake, which should be not be exacerbated (by using “random” more loosely).  In everyday language, random sometimes implies uniform, sometimes not (e.g. weather patterns are random, etc.).  Unfortunately, for this dilemma, I don’t have a good solution.  I feel that using pseudorandom is a concession (for distinguishable from uniform), that I can reluctantly accept (keeping in mind that it should really be pseudo-uniformly).  I admit this may seem pedantic.

Suggestion: This draft is really about mitigating corrupted/failed (intentionally, or not) system PRNGs, specifically failure in their secret entropy, it is not really about the more general concepts of randomness (including uniformity) and entropy (something can have public entropy, or leaked entropy, for example).  For example, when I first saw the title, I thought it would be about finding better sources of entropy, and no clue that it was about resisting corrupted PRNGs.  So, I would suggest trying to use terms aimed this more specific goal (in the title and throughout the draft).  The application is really for key (or nonce) generation, so I would terminology like this: “strengthening key (and nonce) generation against the presence of corrupted entropy sources”.

Best regards,

Dan

From: Cfrg [mailto:[email-masked]] On Behalf Of Christopher Wood

Your definitions seem sensible to me. If there are no objections, I'll try to align the draft to match.

---

From: Dan Brown <[email-masked]>
Date: Mon, 26 Mar 2018 14:19:34 +0000

Hi,

Best regards,

Dan

---

From: Dan Brown <[email-masked]>
Date: Mon, 26 Mar 2018 14:30:01 +0000

At the risk of sounding pedantic, Shannon entropy is not usually the best
type of entropy for cryptography.  (Of course, it is the best for
compression and error correction, AFAIK.)

Almost invariably, min-entropy (or some minor variation) is what
cryptography needs, because, unlike Shannon entropy, min-entropy does not
average out high-probability spikes.  

That said, before today, I hadn't heard of the unit of entropy called a
Shannon, and I don't know if it is defined to be used only for Shannon
entropy.  At the moment, I would find it confusing to speak about "5
Shannons of min-entropy".

Is there a Renyi unit?

-----Original Message-----
From: Cfrg [mailto:[email-masked]] On Behalf Of Mark D. Baushke
Sent: Monday, March 26, 2018 9:33 AM
To: Crypto Forum Research Group <[email-masked]>
Subject: Re: [Cfrg] I-D Action:
draft-irtf-cfrg-randomness-improvements-00.txt

I will note that the unit Shannon exists and might be a useful unit to use
in this draft on randomness improvements to disambiguate a bit or number of
bits in memory from the number of Shannons in that sample.

--
Mark D. Baushke
[email-masked]

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Mark D. Baushke" <[email-masked]>
Date: Mon, 26 Mar 2018 08:18:00 -0700

Hi Dan,

> Is there a Renyi unit?

No, I suspect it is because he is known for both Renyi entropy and Renyi
divergence.

There is a somewhat confusing article on Renyi entropy is here:
  https://en.wikipedia.org/wiki/R%C3%A9nyi_entropy

it tries to compare the various kinds of entropy:

  Hartley or max-entropy

  Shannon entropy

  Collision entropy (sometimes called Renyi entropy)

  Min-entropy

as well as talking to the point of Shannon entropy and Kullback-Leibler
divergence.

I will not argue about which entropy is best for cryptography.

I will suggest that many people try to confuse the use of all of the
types of entropy as if they were only one thing. By using good
definitions and examples, we can try to help in the education process.

I hope this helps to answer your question?

	-- Mark

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 26 Mar 2018 15:26:05 +0000

It's like the old joke, you get 10 cryptographers in a room and you end up with 12 definitions of entropy, randomness, etc.

Most of the people reading this document, especially if it is to have an impact on the Internet, will be engineers and not cryptographers. And almost everyone will have an intuitive, and even correct, sense of what "random bytes" means.

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 14:37:35 -0700

> Most of the people reading this document, especially if it is to have an impact on the Internet, will be engineers and not cryptographers. And almost everyone will have an intuitive, and even corre…

+1

Best,
Chris

---

From: Christopher Wood <[email-masked]>
Date: Mon, 26 Mar 2018 14:37:35 -0700

+1

Best,
Chris

---

From: Jon Callas <[email-masked]>
Date: Tue, 27 Mar 2018 20:51:32 -0700

> On Mar 26, 2018, at 8:26 AM, Salz, Rich <rsalz=[email-masked]> wrote:
> 

Perhaps it's even more like the old story that Von Neumann told Shannon to use the word "entropy" because "no one knows what it means." There's no proof that Von Neumann said it, but it's the sort of thing that he would have said.

In a few more comments, yes, when as cryptographers we talk about random values and tacitly mean evenly distributed (especially when talking about keys), we also talk about "whitening functions" and get really cranky when we can't peer into "entropy" inputs and can't estimate the internals well. 

When dealing with a number of crypto functions, like a number of the coding-based post-quantum public key algorithms, they require Gaussian-distributed random inputs and are more fragile to "bad entropy" (which would include evenly distributed) than some of the functions that want evenly distributed randomness.

I think that one can have a discussion about the importance of randomness, entropy, whatever you want to call it independently of the distribution function. 

I concur that in cryptography, min-entropy is probably what one wants to measure rather than Shannon entropy. Calling a unit of entropy a Shannon is both cringe-worthy and charming. Arguably it's a fitting punishment to Shannon for having listened to Von Neumann to have a unit of something that no one knows what it is named for him. Me, I wouldn't punish him that way.

	Jon

---

From: Jon Callas <[email-masked]>
Date: Tue, 27 Mar 2018 20:51:32 -0700

Jon