Subject: [dsfjdssdfsd] Discussion: Malicious Entropy Attacks: Eggs, and Baskets

From: Alyssa Rowan <[email-masked]>
Date: Tue, 11 Mar 2014 19:13:44 +0000

djb posted a blog <http://blog.cr.yp.to/20140205-entropy.html> last
month which presents some interesting viewpoints on RNG design,
examining a hypothetical¹ scenario in which a malicious entropy source
to an otherwise good RNG can cause the sorts of havoc an attacker
dreams of.

It advocates that instead of the common
continuous-entropy-pool-injection designs we see today, a better
approach might be to make RNGs with a sharp transition between two
states:-

A. An entropy-gathering 'setup' state, collecting enough entropy for
   one really good 256-bit key, reading more-trusted entropy sources
   after less-trusted ones and using a high-cost hash function (to
   really increase the work a malicious entropy source would have to
   do); and then,

B. A 'running' state, which uses that key, holds it securely, and runs
   a good deterministic random bit generator to generate as much
   randomness as we need [up to some limit].

Specifically, djb advocates running A -then- run B (presumably, up to
some defined limit, as no DRBG is sound _ad infinitum_, then we'd have
to block and go back to A to gather another key?).

This is the exact opposite of what we usually do today, which would be
to run A continuously in parallel (possibly in many pools) and using B
in limited quantities to extract randomness from the running pool/s if
and when we need it.

I think that's a fascinating concept: although it runs counter to
usual existing practice, it does so specifically to minimise the
opportunity an attacker has to manipulate the RNG state. (One wonders
about the effect that might have on the window for an attacker to
observe the RNG state, although this _might_ be more defensible as
once in state B, it doesn't seem to provide them with an in-band path
to then exfiltrating it? Out-of-band exfiltration could be a problem
no matter which way you sliced it, although if it occurred, it would
be a live problem for longer, until the next re-key.)

It relies entirely on the DRBG to be strong for our external
prediction resistance. While this has potential pitfalls, it also has
potential benefits. After all, the DRBG is the deterministic element
of an RNG: the testable, easily-verifiable part (at least, compared to
the entropy sources). We already know several approaches that'll
probably work well (e.g. HMAC_DRBG; CTR_DRBG; a strong stream cipher
like ChaCha20 with a monotonically-increasing counter, maybe?) as well
as, of course, ones which infamously won't work out so well (e.g.
Dual_EC_DRBG).

I'm not completely sure if this type of "discrete-setup" RNG is a good
balance, but it's certainly an interesting one about which others may
have some thoughts...?

___
1. *Currently* hypothetical, but alarmingly possible for a sufficiently-
   determined attacker with a penchant for malicious microcode - and we
   know sufficiently-determined and funded attackers exist, and like
   weak RNGs. Maybe we could even see a PoC someday?

- -- 
/akr

---

From: Dan Brown <[email-masked]>
Date: Tue, 11 Mar 2014 19:48:24 +0000

The ANSI/NIST standards already require seeding with entropy equal to the security level before generating any outputs: i.e. your setup state A (minus the high-cost hash functions).  Also, aren't some linux RNGs blocking, isn't that a similar idea.  Maybe I should read the blog.

Anyway, it may well be true that many RNG implementations do not operate this way.  That's a problem, and they wouldn't be compliant to the latest ANSI/NIST specs.

On the research side, Barak and Halevi describe an algorithm with good and bad states, if I recall correctly, in an effort to model malicious seeds (with adequate entropy).

> -----Original Message-----
> From: dsfjdssdfsd [mailto:[email-masked]] On Behalf Of Alyssa
> Rowan
> Sent: Tuesday, March 11, 2014 3:14 PM
> To: [email-masked]
> Subject: [dsfjdssdfsd] Discussion: Malicious Entropy Attacks: Eggs, and Baskets
> 
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> djb posted a blog <http://blog.cr.yp.to/20140205-entropy.html> last month
> which presents some interesting viewpoints on RNG design, examining a
> hypothetical¹ scenario in which a malicious entropy source to an otherwise good
> RNG can cause the sorts of havoc an attacker dreams of.
> 
> continuous-entropy-pool-injection designs we see today, a better approach
> might be to make RNGs with a sharp transition between two
> states:-
> 
> Specifically, djb advocates running A -then- run B (presumably, up to some
> defined limit, as no DRBG is sound _ad infinitum_, then we'd have to block and
> go back to A to gather another key?).
> 
> This is the exact opposite of what we usually do today, which would be to run A
> continuously in parallel (possibly in many pools) and using B in limited quantities
> to extract randomness from the running pool/s if and when we need it.
> 
> I think that's a fascinating concept: although it runs counter to usual existing
> practice, it does so specifically to minimise the opportunity an attacker has to
> manipulate the RNG state. (One wonders about the effect that might have on
> the window for an attacker to observe the RNG state, although this _might_ be
> more defensible as once in state B, it doesn't seem to provide them with an in-
> band path to then exfiltrating it? Out-of-band exfiltration could be a problem no
> matter which way you sliced it, although if it occurred, it would be a live
> problem for longer, until the next re-key.)
> 
> It relies entirely on the DRBG to be strong for our external prediction resistance.
> While this has potential pitfalls, it also has potential benefits. After all, the DRBG
> is the deterministic element of an RNG: the testable, easily-verifiable part (at
> least, compared to the entropy sources). We already know several approaches
> that'll probably work well (e.g. HMAC_DRBG; CTR_DRBG; a strong stream cipher
> like ChaCha20 with a monotonically-increasing counter, maybe?) as well as, of
> course, ones which infamously won't work out so well (e.g.
> Dual_EC_DRBG).
> 
> I'm not completely sure if this type of "discrete-setup" RNG is a good balance,
> but it's certainly an interesting one about which others may have some
> thoughts...?
> 
> ___
> -----BEGIN PGP SIGNATURE-----
> 
> iQIcBAEBCgAGBQJTH2BoAAoJEOyEjtkWi2t6hE4P/3SmC3EDQvLbIUHxahpWj7j7
> hd94kNr4IfByMKqwk7zMw6pW1qFsdrKvbFp7ZwEC/ZglbUptZ1taQyVDMX/ii9ZD
> z7lbGDwWJN6XtLR5hn6sU5m1wkUdCHJ6FeQKgMH7sLu9tRilG6XekuYVu7bcpluQ
> FJpt5MbgPjRAz43uDCO9FQrEfI0IljIIlmdmJWIAREvvaJfXwV/RnBf2mrTMUTFm
> I+tyvaJn7TLc3w3L0tU+7MbRghq8UP611qeeTjpsn3HUjY6xUvSaKzeGL4J6xV3U
> tq8kVc6sWCe85W8OcV2yXi7fYYAuxbxSPops83mRb2YH0Ks8Pk68o3PCvty79YpS
> NeSM/jiYe0GGr3mtEXsIeYirVSdLxJuEP0lUxqSHABgHS8MsxrHQOgcR//s0V/B5
> GiBwvE3xE2tf55WgGomPhs2Kqmpa6nsagwrkY6YLk5W+bV12WiCIM447DKzu86
> mg
> O4n6DrQ7h8MMwSIt2qb90Cye48IncuXczJWIVJK3ZO6TMBR1JemwSM1WP35GU
> tH9
> QdOAKPr+zWEwAangT8ztx05XrPAq5cxzclX9ykrF43HQhizjicX9KgcsGSR3GAYe
> 1b3Y9IbLQc6xMWg0iOjs6Yoo3ngiF4Z8Z75n8lbl3/PoolywGRGj3unpyvSQ4qVM
> ByE6GO0YsjeIbrMo/tNs
> =PuzB
> -----END PGP SIGNATURE-----
> 
> _______________________________________________
> dsfjdssdfsd mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dsfjdssdfsd

---

From: Theodore Ts'o <[email-masked]>
Date: Tue, 11 Mar 2014 15:54:43 -0400

> to block and go back to A to gather another key?).

I'll note that an criteria for judging RNG's which is very popular
with academics who love to write papers poking (theoretical) holes
into random number generators is how quickly a RNG can recover from
state compromise.

One of the reasons why some people love RNG's such as Fortuna and
Yarrow is that it is specifically designed to recover from state
compromises --- and the scheme which djb has suggested would do poorly
on that particular metric.

Does it matter?  Well, entire virtual forests of electronic trees have
been felled by people speculating on whether fast/reliable recovery
from state recovery is critically important compared to other design
considerations.

Personally, my take is that if you can compromise the state of the
RNG, you can probably far more damage, so I'm not convinced state
compromise is a very high priority threat to defend against.  But
there are tons and tons of academic papers which are convinced that
any RNG which doesn't worry about this attack is Fatally Flawed.

    	      	      	    	       	      - Ted

---

From: Dan Brown <[email-masked]>
Date: Wed, 12 Mar 2014 18:42:31 +0000

> From: Dan Brown (me)
> Sent: Tuesday, March 11, 2014 3:48 PM
> 
> The ANSI/NIST standards already require seeding with entropy equal to the
> security level before generating any outputs: i.e. your setup state A (minus the
> high-cost hash functions).  Also, aren't some linux RNGs blocking, isn't that a
> similar idea.  Maybe I should read the blog.
> 

Now I've actually read Bernstein's blog entry that you previously cited. It is well-written and raises some important and interesting issues. 

One of the blog entry's arguments is an instance of something more general: measures addressing one esoteric security feature (in this case, prediction resistance measures) may undermine another esoteric security feature (in this case, resistance to malicious seed sources).  In particular, it raises the questions of appropriateness of security definitions.  I may elaborate on security definitions in a separate email (perhaps after reviewing previous emails on the archive of this list). Meanwhile, here are a few small thoughts regarding blog entry:

First, as I understand the ANSI/NIST specs, the entropy source is presumed to be within the same security boundary as the whole RBG, i.e. free from observation or influence.  Maybe that is not too realistic in complex systems.  Anyway, that is how they "solve" (or wave away) the problem of a malicious entropy (seed) source, which is a different approach than DJB's blog proposal.  The blog entry's example about (EC)DSA is illustrative: the sensitivity of the long-term key private key to the ephemeral private key requires the ephemeral to be entirely within the same security boundary as the static private key.  Deterministic (EC)DSA is one way to do this without a live entropy source in the security boundary.  Arguably the ANSI/NIST spec for ECDSA can implicitly used in such a way: and an I-D or RFC explicitly describes one such way.

Second, the main situation that (at least) I have in mind where prediction resistance (i.e. RNG state compromise recovery) may be useful is if a device with a running RNG switches hands.  This switchover could occur at manufacture, at retail, at repair, at charging kiosk, or at an software installation/removal.  A state compromise might occur prior to the this switchover.  Are any of these realistic threats, or not?  Perhaps expert developers have such perfect control of their systems that they do not need such prediction resistance, and are more worried about a continuous persistent threat co-existing on the system.  

Third, the blog entry describes an adversary with two powers: effective RNG state compromise (by knowing x and y) and entropy source control.  If this is a realistic adversary, then this seems to suggest that RNG state compromise is a also realistic threat (going back to the second point).  Is the idea here that intermediate RNG state compromise only (but no entropy source control) adversary is no more realistic that this two-power adversary?

Fourth, I think the "conventional wisdom" alluded to in the blog entry is not correctly represented.  The conventional wisdom would be merely this: if x and y are secret, then  H(x,y,z) ought to be pretty good even if z is chosen maliciously, i.e. by an adversary that does not know x and y.  I think the blog entry is pointing out, correctly that the adversary may have two parts: an embedded malware that knows x and y, and an external adversary that only observes network communications, but has no idea of x and y. Perhaps the conventional wisdom ignores this latter split adversary.

---

From: Arnold Reinhold <[email-masked]>
Date: Fri, 14 Mar 2014 12:20:56 -0400

Here are some scenarios where recovery from a state compromise would be important:

o A bug in system software that exposes PRNG state only rarely
o An attack that that exposes PRNG state in a system that is well guarded against covert channels, limiting undetected outbound messages to very low bit rate
o An attack that exposes PRNG state which requires physical access to a computer in a well guarded location, for example a Tempest attack where receiving equipment must be placed close to the system under attack
o A flaw in the hash algorithm used to protect the PRNG state that takes massive processing power to exploit
o Any attack that reveals only part of the PRNG state, forcing an expensive search to recover the unknown portion 

My response to the expected question "How likely are any of these situations, really?" is "How difficult is it to implement a PRNG that safely and rapidly recovers from a state compromise?"  If you believe the Dodis paper (http://www.cs.nyu.edu/~dodis/ps/rng.pdf), not very.

We know that both criminal organizations and state actors devote great effort to find any weaknesses. In particular, the expected rapid advance of the "Internet of Things" will produce many black-box diskless devices, some in critical functions, that have minimal entropy sources and software that is updated infrequently or never. I suggest that the Internet of Things should be a primary test case for any new RNG standards activity.

Arnold Reinhold

---

From: Krisztián Pintér <[email-masked]>
Date: Sat, 15 Mar 2014 16:50:37 +0100

Arnold Reinhold (at Friday, March 14, 2014, 5:20:56 PM):
> o An attack that that exposes PRNG state in a system that is well
> guarded against covert channels, limiting undetected outbound messages to very low bit rate
[...]

and these are the attacks about which djb says: your system is broken.
don't patch it, fix it. if such attacks could be carried out, session
keys or long term keys might have been compromised. recovering your
prng won't help that, the damage has been done.

it is not the way to reduce the chance of any attack by a small
factor, let the factor be a 100, or even a million, it is still small.
what we want is systems that are reliable and safe. and if our system
is safe, we don't need reseeding.

---

From: Arnold Reinhold <[email-masked]>
Date: Sun, 16 Mar 2014 11:18:29 -0400

> is safe, we don't need reseeding.

I am not aware of anyone who even claims to have a system that is "safe", as in free from any security bugs, much less one that remains safe from bugs being added as new software is developed and other bugs are fixed. 

And note that not all the issues I raised are software related. Tempest, for example, is a very tricky business. The NSA specs for Tempest protection are not publicly available, but I have been told they require tight physical configuration control, as even a single wire change can destroy Tempest protection.  Perhaps the best that can be achieved is to keep any attacker a safe distance from critical systems. A determined attacker might be willing to absorb the effort and risk to covertly penetrate physical security barriers if doing so will lead to a permanent compromise of a one-time-seeded PRNG, less so if the benefits will last only briefly as the PRNG reseeds after they leave.

We now have something we never had before, an apparently thorough rigorous analysis of the reseeding issue. Of course, time should be allowed for responses and critiques to the Dodis paper to emerge, but planning new security guidelines that ignore this work seems foolhardy.

Arnold Reinhold

---

From: [email-masked]
Date: Sun, 16 Mar 2014 13:17:16 -0400

On Sun, Mar 16, 2014 at 11:18:29AM -0400, Arnold Reinhold wrote:
> 
> And note that not all the issues I raised are software
> related. Tempest, for example, is a very tricky business. The NSA
> specs for Tempest protection are not publicly available, but I have
> been told they require tight physical configuration control, as even
> a single wire change can destroy Tempest protection.  Perhaps the
> best that can be achieved is to keep any attacker a safe distance
> from critical systems. A determined attacker might be willing to
> absorb the effort and risk to covertly penetrate physical security
> barriers if doing so will lead to a permanent compromise of a
> one-time-seeded PRNG, less so if the benefits will last only briefly
> as the PRNG reseeds after they leave.

One of the things which is not obvious is whether or not each
contributor has the same threat model in mind.  (In fact, it seems
pretty obvious to me that we don't all share the same threat model,
but I'm trying to be polite.  :-)

The sort of things that you might need to worry about if you are
trying to protect against pervasive monitoring are very different if
you are worried about a targetted attack.  If someone is willing to
bring in a listening truck and park it outside your house, or coverly
penetrate physical security, there is a whole host of things that you
would need to protect against before you are fully protected against
that level of attack.

In particular, who cares about how carefully constructed your RNG
might be if the attacker can replace it (along with perhaps your
entire networking stack, and the monitoring tools that might allow you
to notice that something strange has happened to your system)?  Or
just simply drop in some malware which leaks the session key after
your perfect RNG that meets with all of the academics' worries about
state compromise recovery....

						- Ted

---

From: Arnold Reinhold <[email-masked]>
Date: Mon, 17 Mar 2014 20:43:36 -0400

On Mar 16, 2014, at 1:17 PM, [email-masked] wrote:

> state compromise recovery….

I agree completely that there are multiple threat models in play regarding RNG and that this is a cause for much confusion. As I see it there are two broad categories:

1. The corporate threat model, which focuses on facilitating e-commerce and financial transections, complying with privacy regulations, (HIPPA, SOX, EU Data Directive, etc.), avoiding potential legal liability and protecting trade secrets.

2. The personal privacy threat model, which fears the mass surveillance society, doesn’t trust corporate vendors and certifying bodies, and considers state actors principal threats. I’d put Bitcoin and the like here.

Intel’s RDrand instruction is a good example of the difference. It is deeply distrusted by group 2, but would appear to meet the needs of  group 1 (except maybe for trade secret protection at non-US companies).

Nonetheless, I would like to see future RNG standards address both groups' concerns as far as reasonably possible. And I would not be dismissive about ”exotic” attacks such as Tempest. What was once the purview of state actors like NSA, e.g. massively parallel machines for brute forcing passwords and keys, is now widely in use by the private and criminal sectors.  

The time interval between RFCs 1750 and 4086 is over ten years and another ten are likely to have elapsed before a successor is adopted. A lot can happen in ten years, so it seems to me the goal should be to recommend the best available technology and to at least consider as many threats and use cases as can be reasonably foreseen, making technical compromises only when clearly needed after due consideration of alternatives.

Arnold Reinhold

---

From: [email-masked]
Date: Mon, 17 Mar 2014 22:39:32 -0400

On Mon, Mar 17, 2014 at 08:43:36PM -0400, Arnold Reinhold wrote:
> 2. The personal privacy threat model, which fears the mass
> surveillance society, doesn’t trust corporate vendors and certifying
> bodies, and considers state actors principal threats. I’d put
> Bitcoin and the like here.

... and this also needs to separated into the "proof against a
targetted attack" and "protect against mass surveillance".

There's a big difference between NSA or FBI cutting a deal with AT&T
so that they get to put an Carnivore style keyword monitoring device
in a telephone closet at a fiber exchange point, and the FBI deciding
to park a Tempest van outside of your house.

Cheers,

						- Ted

---

From: Arnold Reinhold <[email-masked]>
Date: Tue, 18 Mar 2014 16:57:25 -0400

> to park a Tempest van outside of your house.

What used to require a Tempest van, today probably fits in a briefcase or even a shirt pocket. And the hardware, in terms of of wide band digitizing and signal processing is now widely available and inexpensive. 

The targeted attack vs mass surveillance/war driving/bang-on-every-exposed-port model should be another dimension to the threat model, but the former shouldn’t be ignored.  Trillions of dollars already flow through financial systems daily and the Internet of Things is just getting started. There will be ever more high value systems to attack, and increasingly sophisticated evil-doers with the means to go after them. (My nightmare sees drug cartels wishing to develop new revenue streams to replace market share lost to legalization and following Sutton’s Law in its most literal sense.)

Before eliminating any capability, such as rapid recovery from PRNG state compromise, based on a claim that the requirement is unreasonable under the threat models being addressed, those threat models (and the claim) should be made fully explicit and subjected to review like any other aspect of the proposed standard.

Arnold Reinhold

---

From: Arnold Reinhold <[email-masked]>
Date: Fri, 28 Mar 2014 13:33:19 -0700 (PDT)

On Tuesday, March 18, 2014 7:17:31 PM UTC-4, D. J. Bernstein wrote:
>
> Arnold Reinhold writes: 
> > A determined attacker might be willing to absorb the effort and risk 
> > to covertly penetrate physical security barriers if doing so will lead 
> > to a permanent compromise of a one-time-seeded PRNG 
>
> You misunderstand the argument that you're responding to. 
>
> The argument, in the case of side-channel attacks, is _not_ "Don't worry 
> about side-channel attacks---you aren't being targeted by those." 
>
> The argument is "When a side-channel attacker is stealing your long-term 
> PGP key, your long-term SSH key, your long-term SSL key, etc., what 
> exactly do you think you're accomplishing by dribbling fresh entropy 
> into your RNG? It's too late! You've already lost! Try paying attention 
> to the actual problem: go back to the system design and start applying 
> side-channel countermeasures." 
>
> There's an extensive public literature on side-channel attacks and 
> defenses, notably in the proceedings of the top-tier Cryptographic 
> Hardware and Embedded Systems conference series. The attacks are much 
> more expensive for RNGs than for long-term keys (RNG state has far less 
> interaction with attacker-controlled input, and each state is used only 
> once), and the defenses are correspondingly easier; anyone capable of 
> protecting the long-term keys is also capable of protecting the RNG. 
>
> Similar comments apply to other "RNG state compromise" attacks. Sure, 
> there have been security failures that allowed attackers to read the 
> system's RNG state, but those failures also allowed attackers to read 
> long-term keys, and that's a much worse problem. Viewing this as an RNG 
> issue, and trying to "recover" from it by complicating the RNG, doesn't 
> make any sense. What makes sense is to address the underlying security 
> failures, protecting _all_ of the secrets stored in the system. 
>
> > We now have something we never had before, an apparently thorough 
> > rigorous analysis of the reseeding issue. 
>
> I see no connection between "the reseeding issue" and actual security. 
>
> ---Dan 
>

I was answering what I perceived as skepticism about the Tempest attack 
threat, but I would like to respond to your broader point. 

A random number generator (RNG) is a component of security systems. 
Electronic signature, symmetric and asymmetric encryption algorithms are 
other components. The argument seems to be that component A need not be 
resistant to attack X because critical component B is even more susceptible 
to X than A is. A counter position is that we should make component A as 
resistant to X as it can safely be, with reasonable effort, and also try to 
improve the resistance of component B to X. 

It’s at least conceivable that credentials can be made less subject to side 
channel attack. One  might, for example, use multi-layer credentials, with 
the operational credentials changed regularly. Transactions would be signed 
and encrypted using working keys with a short lifespan. The top level 
credential would be used very infrequently, limiting its exposure to side 
channels. The top level credential might also subject to further 
protections, perhaps stored in a separate module, or encrypted after 
signing second level credentials, perhaps using a public key of some remote 
station. That station might then authorize decryption for signing only when 
the system is under direct supervision. Such a system could recover from a 
compromise of its short term and intermediate term keys, perhaps in in a 
time frame comparable to an RNG recovery or even synchronized with the RNG 
reseeds.

It might be argued that any credential compromise is damaging, but the 
damage from a short term compromise can be limited. A seed-only-once RNG 
can never recover from a state compromise. 

The context here is a proposed revision for RFC 4086 Randomness 
Requirements for Security. If all goes smoothly the new RFC might come out 
in 2015 or 2016. Any new RNG recommendations it makes will take several 
years to appear in common operating systems and crypto libraries. Secure 
systems based on those components will then likely be in the field for a 
decade or more. That means systems influenced by the new RFC will be 
operating well into the 2030s. I don’t think we can predict all the uses 
for unpredictable quantities and possible attacks in that long a time 
frame. 

The Dodis paper suggests a sound basis for designing RNGs that recover from 
state compromise. It remains to be seen if flaws in their reasoning surface 
and if practical code based on their ideas will emerge free of intellectual 
property restrictions. But I think it is much too soon to rule out 
inclusion of such a scheme in the proposed RFC.

Arnold Reinhold