Entropy Attacks!
D. J. Bernstein
if H is any modern cryptographic hash function then H(x,y,z) is at least
as good a random number as H(x,y), no matter how awful z is. So we pile
one source on top of another, hashing them all together and hoping that
at least one of them is good.
But what if z comes from a malicious source that can snoop on x and y?
For example, imagine a malicious "secure randomness" USB device that's
actually spying on all your other randomness sources through various
side channels, or---worse---imagine RDRAND microcode that's looking at
the randomness pool that it's about to be hashed into. I should note
that none of the attacks described below rely on tampering with x or y,
or otherwise modifying data outside the malicious entropy source; you
can't stop these attacks by double-checking the integrity of data.
Of course, the malicious device will also be able to see other sensitive
information, not just x and y. But this doesn't mean that it's cheap for
the attacker to exfiltrate this information! The attacker needs to find
a communication channel out of the spying device. Randomness generation
influenced by the device is a particularly attractive choice of channel,
as I'll explain below.
Here's an interesting example of an attack that can be carried out by
this malicious source:
1. Generate a random r.
2. Try computing H(x,y,r).
3. If H(x,y,r) doesn't start with bits 0000, go back to step 1.
4. Output r as z.
This attack forces H(x,y,z) to start 0000, even if x and y were
perfectly random. It's fast, taking just 16 computations of H on
average.
Maybe the randomness generator doesn't actually output H(x,y,z); it uses
H(x,y,z) as a seed for some generator G, and outputs G(H(x,y,z)). Okay:
the attacker changes H to G(H), and again forces the output G(H(x,y,z))
to start 0000. Similarly, the attack isn't stopped by pre-hashing of the
entropy source before it's mixed with other entropy sources. Every mix
from the malicious entropy source lets the attacker produce another
"random" number that starts 0000.
More generally, instead of producing "random" numbers that start with
0000, 0000, 0000, etc., the malicious entropy source can produce
"random" numbers that start with successive 4-bit components of
AES_k(0),AES_k(1),... where k is a secret key known only to the
attacker. Nobody other than the attacker will be able to detect this
pattern.
Recall that DSA and ECDSA require random "nonces" for signatures. It's
easy to imagine someone grabbing each nonce as a new "random" number
from the system's randomness generator. However, it's well known (see,
e.g., http://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf) that an attacker
who can predict the first 4 bits of each nonce can quickly compute the
user's secret key after a rather small number of signatures. Evidently
hashing an extra entropy source _does_ hurt---in the worst possible way;
the attacker has the user's secret key!---contrary to the conventional
wisdom stated above.
EdDSA (see http://ed25519.cr.yp.to) is different. It uses randomness
once to generate a secret key and is then completely deterministic in
its signature generation (following 1997 Barwood, 1997 Wigley, et al.).
The malicious entropy source can still control 4 bits of the secret key,
speeding up discrete-log attacks by a factor of 4, but this isn't a
problem---we use curves with ample security margins. The source can
increase the 4 bits by carrying out exponentially more H computations,
but this has to fit into the time available after inspecting x and y and
before generating a "random" number.
Of course, there are many other uses of randomness in cryptography: for
example, if you want forward secrecy then you're constantly generating
new ECDH keys. Controlling 4 bits of each secret key isn't nearly as
damaging as controlling 4 bits of DSA/ECDSA nonces---it's the same
factor of 4 mentioned above---but, as I mentioned above, the malicious
entropy source can also use randomness generation as a communication
channel to the attacker. For example, the source controls the low bit of
each _public_ key with an average cost of just 2 public-key generations,
and uses the concatenation of these low bits across public keys to
communicate an encryption of the user's long-term key. This channel is
undetectable, reasonably high bandwidth, and reasonably low cost.
On the other hand, there's no actual need for this huge pile of random
numbers. If you've somehow managed to generate one secure 256-bit key
then from that key you can derive all the "random" numbers you'll ever
need for every cryptographic protocol---and you can do this derivation
in a completely deterministic, auditable, testable way, as illustrated
by EdDSA. (If you _haven't_ managed to generate one secure 256-bit key
then you have much bigger problems.)
With this as-deterministic-as-possible approach, the entire influence of
the malicious entropy source is limited to controlling a few "random"
bits somewhere. There are at least two obvious ways to further reduce
this control:
* Read less-likely-to-be-malicious entropy sources _after_ completing
all reading of the more-likely-to-be-malicious entropy sources. Of
course, this doesn't help if the last source turns out to be
malicious.
* Increase the amount of processing, memory, etc. involved in H---as
in hashcash, proofs of work in general, password hashing, etc. The
costs are negligible, since all of this is done only once.
Let me emphasize that what I'm advocating here, for security reasons, is
a sharp transition between
* before crypto: the whole system collecting enough entropy;
* after: the system using purely deterministic cryptography, never
adding any more entropy.
This is exactly the opposite of what people tend to do today, namely
adding new entropy all the time. The reason that new entropy is a
problem is that each addition of entropy is a new opportunity for a
malicious entropy source to control "random" outputs---breaking DSA,
leaking secret keys, etc. The conventional wisdom says that hash outputs
can't be controlled; the conventional wisdom is simply wrong.
(There are some special entropy sources for which this argument doesn't
apply. For example, an attacker can't exert any serious control over the
content of my keystrokes while I'm logged in; I don't see how hashing
this particular content into my laptop's entropy pool can allow any
attacks. But I also don't see how it helps.)
Is there any serious argument that adding new entropy all the time is a
good thing? The Linux /dev/urandom manual page claims that without new
entropy the user is "theoretically vulnerable to a cryptographic
attack", but (as I've mentioned in various venues) this is a ludicrous
argument---how can anyone simultaneously believe that
(1) we can't figure out how to deterministically expand one 256-bit
secret into an endless stream of unpredictable keys (this is what
we need from urandom), but
(2) we _can_ figure out how to use a single key to safely encrypt
many messages (this is what we need from SSL, PGP, etc.)?
There are also people asserting that it's important for RNGs to provide
"prediction resistance" against attackers who, once upon a time, saw the
entire RNG state. But if the attacker sees the RNG state that was used
to generate your long-term SSL keys, long-term PGP keys, etc., then what
exactly are we gaining by coming up with unpredictable random numbers in
the future? I'm reminded of a Mark Twain quote:
Behold, the fool saith, "Put not all thine eggs in the one basket"---
which is but a manner of saying, "Scatter your money and your
attention;" but the wise man saith, "Put all your eggs in the one
basket and---WATCH THAT BASKET."
We obviously need systems that can maintain confidentiality of our
long-term keys. If we have such systems, how is the attacker supposed to
ever see the RNG state in the first place? Maybe "prediction resistance"
can be given a theoretical definition for an isolated RNG system, but I
don't see how it makes any sense for a complete cryptographic system.
---Dan
Alaric Snell-Pym
On Sunday, 2 February 2014 02:51:14 UTC, D. J. Bernstein wrote:
The conventional wisdom is that hashing more entropy sources can't hurt:
if H is any modern cryptographic hash function then H(x,y,z) is at least
as good a random number as H(x,y), no matter how awful z is. So we pile
one source on top of another, hashing them all together and hoping that
at least one of them is good.
This leads me to wonder about ways of implementing entropy pools to try and prevent this attack...
An attacker needs to either peek into the outputs of each other entropy input individually (which would probably be tricky, unless an underlying vulnerability makes it able to access them all), or attack the entropy mixer/pool itself, which by nature has to have all the other inputs. So the mixer/pool is probably the most important thing to harden - protecting that, and at least *one* non-trivial entropy input, means an attacker controlling an entropy input can't use this attack.
> (There are some special entropy sources for which this argument doesn't
apply. For example, an attacker can't exert any serious control over the
content of my keystrokes while I'm logged in; I don't see how hashing
this particular content into my laptop's entropy pool can allow any
attacks. But I also don't see how it helps.)
If that meagre source of entropy is the only one that can't be observed by the attacker, perhaps because it's implemented by the keyboard interrupt handler poking otherwise-useless data that is not recorded anywhere else (high resolution keystroke timings, perhaps) so can't be found easily by probing memory, then it might just save the day :-)
I think you're quite right that we need to use entropy more cautiously, but I think we can also work from the other end a bit and try to keep the entropy pool safer. Certainly, microkernel-type designs with less code being given "full trust", so the entropy pool is in its own address space accessible only via an API to anything other than its own code and the bit of the system that enforces the memory protection, would help here. I presume that any random third-party binary blob driver loaded into a Linux kernel can get at the entropy pool at will?
D. J. Bernstein
> If that meagre source of entropy is the only one that can't be observed by the
> attacker, perhaps because it's implemented by the keyboard interrupt handler
> poking otherwise-useless data that is not recorded anywhere else (high
> resolution keystroke timings, perhaps) so can't be found easily by probing
> memory, then it might just save the day :-)
then what exactly could it be saving the day from?
If there wasn't enough entropy in the long-term secret keys then the
user is screwed. Adding entropy _now_ isn't going to help.
If there _is_ enough entropy in the long-term secret keys then those
keys can be used to deterministically generate any amount of data that's
indistinguishable from truly random data. So mixing in further entropy
isn't doing anything for us.
> I presume that any random third-party binary blob driver loaded into a
> Linux kernel can get at the entropy pool at will?
etc., plus any other confidential information you might have on the
computer.
Exception: virtualization can provide some serious memory protection
between the virtual machine accessing hardware (e.g., "Dom0" for Xen)
and the virtual machine holding your private data. But this still
doesn't help if the hardware can get at your private data in other
ways. For example, graphics drivers are an unholy mess of buggy code
and certainly have access to the private data on your screen. Even
worse, computer manufacturers think that it's a _good_ idea to give
graphics cards etc. the power to access DRAM directly.
I think that crypto in general, and randomness generation in particular,
is an important enough service that it should be centralized inside
hypervisors. The technique of
https://www1.informatik.uni-erlangen.de/tresor
seems to avoid trusting DRAM and typical DMA devices, although it
obviously still needs a secure keyboard, and still doesn't do anything
to protect graphics.
---Dan
jann...@googlemail.com
> There are also people asserting that it's important for RNGs to provide
> "prediction resistance" against attackers who, once upon a time, saw the
> entire RNG state. But if the attacker sees the RNG state that was used
> to generate your long-term SSL keys, long-term PGP keys, etc., then what
> exactly are we gaining by coming up with unpredictable random numbers in
> the future?
What about the issues with VMs that are cloned or rolled back while they're running? It's bad enough if the random pool is reused for a short while, but still much better than if it was reused forever.
Alaric Snell-Pym
> Alaric Snell-Pym writes:
>> If that meagre source of entropy is the only one that can't be observed by the
>> attacker, perhaps because it's implemented by the keyboard interrupt handler
>> poking otherwise-useless data that is not recorded anywhere else (high
>> resolution keystroke timings, perhaps) so can't be found easily by probing
>> memory, then it might just save the day :-)
>
> But if this is done _after_ the computer generated long-term secret keys
> then what exactly could it be saving the day from?
>
> If there wasn't enough entropy in the long-term secret keys then the
> user is screwed. Adding entropy _now_ isn't going to help.
initial long-term secret key. I'm in full agreement with you about being
deterministic after that!
> I think that crypto in general, and randomness generation in particular,
> is an important enough service that it should be centralized inside
> hypervisors. The technique of
the hypervisor ends up needing to control a lot of stuff in order to
prevent its own software being compromised, so the hypervisor then needs
to run things like mass storage drivers in order to be able to protect
itself from being tampered with. But I'd really like the hypervisor to
contain *less* code. Perhaps if it boots from a simple storage device
(eg, is flashed into the BIOS in the first place) that it can then
gateway access to, and not have to get involved in the implementation of
high-performance RAID controller drivers, that'd be doable.
> https://www1.informatik.uni-erlangen.de/tresor
>
> seems to avoid trusting DRAM and typical DMA devices, although it
> obviously still needs a secure keyboard, and still doesn't do anything
> to protect graphics.
also be free to tamper with the implementation to log the keys somewhere
accessible...
>
> ---Dan
>
ABS
--
Alaric Snell-Pym
http://www.snell-pym.org.uk/alaric/
D. J. Bernstein
> What about the issues with VMs that are cloned or rolled back while
> they're running? It's bad enough if the random pool is reused for a
> short while, but still much better than if it was reused forever.
reasons). Then there's _no_ randomness reuse. That's obviously much
better than the "reused for a short while" situation.
Analogous offline situation: If you're flashing (e.g.) a router from a
master PC, you should use randomness from the master PC to initialize
the entropy pool on the router. This should be a standard feature of
first-stage debootstrap and other flashing tools; it would have
eliminated the security problems documented on https://factorable.net.
Of course, a public audit of the router, no matter how comprehensive it
is, can't tell whether this randomness was actually recorded somewhere.
Someone who buys the router and wants to protect himself _against_ the
master PC needs (1) this audit but also (2) initializing his own entropy
pool.
In all of these situations I see a critical separation between
* initializing the entropy pool with enough good entropy and
* using the entropy pool to generate as much randomness as desired.
It's obviously critical to start crypto (e.g., generating SSL keys) only
_after_ the first stage. We shouldn't be generating any "random" numbers
if the entropy pool hasn't been properly initialized.
Once crypto _has_ been started, I don't see the argument for continuing
to collect entropy. If there was some huge problem in the initialization
then we've had a disaster in the generation of crypto keys, and adding
entropy to future random numbers doesn't help us out of the disaster. If
there _wasn't_ some huge problem in the initialization then it's safe to
deterministically generate all future randomness, whereas adding new
entropy simply means creating new possibilities of undetectable damage
from malicious entropy sources peeing in the entropy pool.
---Dan
David Johnston
On Saturday, February 1, 2014 6:51:14 PM UTC-8, D. J. Bernstein wrote:
...
But what if z comes from a malicious source that can snoop on x and y?
For example, imagine a malicious "secure randomness" USB device that's
actually spying on all your other randomness sources through various
side channels, or---worse---imagine RDRAND microcode that's looking at
the randomness pool that it's about to be hashed into. I should note
that none of the attacks described below rely on tampering with x or y,
or otherwise modifying data outside the malicious entropy source; you
can't stop these attacks by double-checking the integrity of data.
...
---Dan
Gregory Perry
> Of course software is vulnerable to software and software is the
> primary attack vector against other software. The Linux pool state has
> been the subject of attacks and to my mind, the mixing functions and
> API model are questionable. I see no reason for the RNG to be in the
> kernel, other than the kernel being the thing that mediates the shared
> access to the entropy supplying devices. The answer to that is better
> devices, not better kernel code.
A fully transparent RNG/PRNG implementation requires access to the
microcode/firmware or source code, respectively.
Most of the current generation hardware-based RNGs out there are black
boxes, and additionally vulnerable to other more esoteric attacks such
as side channel power rail analysis for divining key materials. At
least with a kernel-based PRNG, you can analyze the source code to audit
entropy gathering sources and mixing algorithms; not so with discrete
hardware RNG implementations.
Most of these issues identified with RdRand and other suspect
vendor-specific RNGs could have been alleviated many moons ago with
statistical analysis and other more advanced methods of entropy
examination that have been around for decades, but apparently everyone
is too busy drinking the Torvalds et al kool aid to pay attention to
these types of security certification and accreditation methods. The
mere fact that the entire Linux community accepted as face value Herr
Torvalds' squawk of "Short answer: we actually know what we are doing.
You don't.” speaks volumes about the current state of security with the
Linux kernel.
At this point I would not trust any hardware-based RNG implementations
out there, the benefits of hardware acceleration for random number
generation does not outweigh the potential for covert backdoors that are
easily thwarted with open source entropy gathering and mixing
algorithms. In fact, I can't think of any mainstream reason for a
hardware accelerated RNG implementation unless the application is a high
bandwidth SSL webserver or a multiple gigabit VPN concentrator.
Twitter's recent forward secrecy announcement pretty much sums up that
sentiment in that there was negligent CPU computational cost associated
with their PFS implementation, and with no mention of any
hardware-accelerated crypto requirement that I can find citation for.
Daniel Cegiełka
> A fully transparent RNG/PRNG implementation requires access to the
> microcode/firmware or source code, respectively.
this project:
https://cryptech.is/
Daniel
D. J. Bernstein
> So with RdRand, you can bypass the OS and get your random numbers
> handed to you by the microcode that executes the RdRand instruction,
> fetching the numbers from the hardware DRNG. This addresses a class of
> attacks against the OS RNG state
figure out what attack class you think you're defending against.
Furthermore, I see tens of thousands of RDRAND code hits on github.com,
and my sampling suggests that essentially all of that code is wrong---
it's using RDRAND in ways that can _fail to generate any randomness_,
according to all of Intel's official documentation. There's no backup
plan in the code when these failures occur, and I have no idea what you
think the backup plan is supposed to be.
Even worse, the RDRAND API _encourages_ exactly this type of failure,
since the code to use RDRAND in a seems-to-work way is much shorter than
the code to use RDRAND in a robust way. I don't mean to say that the
current Linux/BSD interfaces are great (open() can fail, typical use
isn't thread-safe, etc.) but at least the OS _can_ do better. Note to
Linux developers, BSD developers, etc.: please add a simple robust
os_randombytes(buf,len) syscall after #include "os_randombytes.h".
> The DRNG that feeds random numbers to RdRand has its own 256 bit pool, which
> the conditioner mixes new raw entropy bits into.
> Microcode has no access to this pool.
sources (three sources x,y,z in my example). The entropy pool you
designed isn't an example. The Linux and BSD entropy pools are examples.
Maybe we need terminology to distinguish these different types of pools:
there's an obvious security impact from being limited to one source.
Malicious RDRAND microcode has the power to inspect the Linux or BSD
entropy pools and of course carry out computations---without making any
modifications that risk being detected. Malicious RDRAND hardware that
doesn't follow your design has the same power. Malicious USB RNG devices
can have the same power through sufficiently invasive side channels. All
of these settings allow the attacks that I explained _if_ the system
keeps collecting new entropy after starting crypto.
---Dan
Arnold Reinhold
D. J. Bernstein has proposed an attack on RNG schemes that use a hash algorithm to combine output from several entropy sources. (2014.02.05: Entropy Attacks!, on The cr.yp.to blog) I believe his attack can be thwarted by using a key-stretching hash to combine the outputs.
Bernstein showed that, under certain circumstances, one specially crafted rouge entropy source can control, to a limited extent, the final output of the combining RNG. To successfully mount the Bernstein attack, the rogue entropy source must be the last entropy source polled and must know the system under attack’s combining scheme and all outputs the system obtained from the other entropy sources. The rogue RNG then internally repeats the combining hash function many times until it finds a random bit stream to output that, when hashed with the previous entropy outputs, produces a final RNG output value with the desired characteristics.
If the combining hash is a key stretcher with a work parameter set high enough, it will not be possible for the rouge RNG to perform the many tries needed to find an acceptable output without imposing a large, easily detected delay. For simple hashes, especial ones crafted for fast hardware performance like the SHA families, it may be possible for the rouge RNG to make the necessary trials fast enough to avoid notice. But if a key-stretching hash is employed that uses enough CPU and memory resources, such as scrypt or HEKS, it will be infeasible, both physically and economically, to hide enough computation power inside the rouge RNG to do the repeated hash trials many times faster than system under attack, even if the rouge RNG is part of the system’s CPU chip.
Assuming the system under attack has a trusted timer or real-time clock, the system software can set the work level parameter of the combining hash to be on the order of the maximum time that should be needed to interrogate the final entropy source (the potential rogue) after output has been received from all other entropy sources. If the measured time exceeds a reasonable margin above what is expected, the system should fail safe by refusing to accept the RNG outputs. Alternatively, the system can measure the time interval between obtaining the first and last RNG’s data and set its key stretching work factor based on this time interval.
In particular, Intel’s RDRAND is implemented as a CPU instruction, so almost no time should elapse between the penultimate entropy source's data being obtained and the needed RDRAND instructions being completed. Thus a fairly small key stretching work parameter, even a few milliseconds, should suffice to detect a CPU with an RDRAND that attempts to implement Bernstein's attack.
Arguably a CPU chip with a cooked RNG instruction could suspend its timers while possible RNG outputs are being tested, though it would have to know when the critical output was being requested, otherwise the timer interference might be detected. (At some point we must recognize that an all-knowing CPU with lots of covert firmware designed around our software can defeat any security scheme.) Other timing sources are possible. Common, inexpensive external real time clock ICs, such as the DS1302, provide timing to one second resolution. An available GPIO pin could be used to charge a small capacitor with a resistor in parallel and then measure its voltage decay for a rough time check.
While placing a key stretcher in the RNG chain may seem overkill to just thwart the Bernstein entropy combiner attack, an attack which demands somewhat far fetched preconditions, using a key stretching hash can also mitigate the type of attack proposed by Georg T. Becker. et. al. (Stealthy Dopant-Level Hardware Trojans http://people.umass.edu/gbecker/BeckerChes13.pdf ) An attacker using the Becker technique will reduce the effective state space of the RNG being cooked. The cooked state space must be small enough to allow a brute force search of possible RNG states, but not so small as to risk detection. Applying a high work factor key stretcher to the output of a Beckerized RNG would make the state space search far more expensive and possibly force the attacker to shrink the effective state space enough to allow detection.
The key stretching defense is particularly well suited to the difficult case of a black box device needing random data at first start up, when, typically, its secret keys are generated. A tens of seconds delay during first boot would seem a reasonable trade off for enhanced security. The Bernstein attack would then take several minutes, a delay that would be easy to notice. A similar argument applies to systems that generate one time a high quality seed for a deterministic RNG which will then be used to meet all future randomness requirements.
On Saturday, February 1, 2014 9:51:14 PM UTC-5, D. J. Bernstein wrote:
The conventional wisdom is that hashing more entropy sources can't hurt:
if H is any modern cryptographic hash function then H(x,y,z) is at least
as good a random number as H(x,y), no matter how awful z is. So we pile
one source on top of another, hashing them all together and hoping that
at least one of them is good.
But what if z comes from a malicious source that can snoop on x and y?
For example, imagine a malicious "secure randomness" USB device that's
actually spying on all your other randomness sources through various
side channels, or---worse---imagine RDRAND microcode that's looking at
the randomness pool that it's about to be hashed into. I should note
that none of the attacks described below rely on tampering with x or y,
or otherwise modifying data outside the malicious entropy source; you
can't stop these attacks by double-checking the integrity of data.
...
John Kelsey
D. J. Bernstein has proposed an attack on RNG schemes that use a hash algorithm to combine output from several entropy sources. (2014.02.05: Entropy Attacks!, on The cr.yp.to blog) I believe his attack can be thwarted by using a key-stretching hash to combine the outputs.
Bernstein showed that, under certain circumstances, one specially crafted rouge entropy source can control, to a limited extent, the final output of the combining RNG. To successfully mount the Bernstein attack, the rogue entropy source must be the last entropy source polled and must know the system under attack’s combining scheme and all outputs the system obtained from the other entropy sources. The rogue RNG then internally repeats the combining hash function many times until it finds a random bit stream to output that, when hashed with the previous entropy outputs, produces a final RNG output value with the desired characteristics.
If the combining hash is a key stretcher with a work parameter set high enough, it will not be possible for the rouge RNG to perform the many tries needed to find an acceptable output without imposing a large, easily detected delay. For simple hashes, especial ones crafted for fast hardware performance like the SHA families, it may be possible for the rouge RNG to make the necessary trials fast enough to avoid notice. But if a key-stretching hash is employed that uses enough CPU and memory resources, such as scrypt or HEKS, it will be infeasible, both physically and economically, to hide enough computation power inside the rouge RNG to do the repeated hash trials many times faster than system under attack, even if the rouge RNG is part of the system’s CPU chip.
While placing a key stretcher in the RNG chain may seem overkill to just thwart the Bernstein entropy combiner attack, an attack which demands somewhat far fetched preconditions, using a key stretching hash can also mitigate the type of attack proposed by Georg T. Becker. et. al. (Stealthy Dopant-Level Hardware Trojans http://people.umass.edu/gbecker/BeckerChes13.pdf ) An attacker using the Becker technique will reduce the effective state space of the RNG being cooked. The cooked state space must be small enough to allow a brute force search of possible RNG states, but not so small as to risk detection. Applying a high work factor key stretcher to the output of a Beckerized RNG would make the state space search far more expensive and possibly force the attacker to shrink the effective state space enough to allow detection.
John Kelsey
If you were worried about the Intel RNG trying to carry out this attack, you could *start* by collecting 256 bits from RDRAND, and then collect entropy from the other sources until you are ready to seed your RNG. If those other sources actually have any entropy, then the Intel RNG can't predict them, and so can't do anything with them.
This is probably pointless paranoia, since if the CPU you're running on is evil, it's probably impossible to get much security. But assuming the Intel RNG is good, seeding your system RNG in this way would work just fine.
--John
Theodore Ts'o
>
> This is probably pointless paranoia, since if the CPU you're running
> on is evil, it's probably impossible to get much security. But
> assuming the Intel RNG is good, seeding your system RNG in this way
> would work just fine.
standalone component inside the CPU. However, compromising the
execution engine such that you can snoop on memory, etc., would
require at least 10x to 100x more engineers to be able to figure out
that the CPU was doing something evil --- only one of which has to be
have the courage and bravery of Snowden to leak the information to the
whole world.
The other thing I'd note about "The Bernstein Attack" is that it
requires O(2**N) work to reduce the key strength by N bits. That is,
suppose you have a 256 bit AES random session key. Using his algorithm:
1. Generate a random r.
2. Try computing H(x,y,r).
3. If H(x,y,r) doesn't start with bits 0000, go back to step 1.
4. Output r as z.
taking 16 times as long to generate the session key. In order to
reduce the strength of the random session key to be 128 bits, the work
factor would be 2**128!
In other words, this is a straightforward brute force attack, where
you can shift some amount of the work from Fort Meade to the victim
CPU. This is not what I would call exciting, since given the amount
of effort and the number of engineers you would have to suborn inside
Intel, and the corresponding risk of destroying one of US's larger
tech companies, and compare it to the possible benefit to the NSA, it
just isn't worth it.
The NSA could get much better bang for its buck by suborning someone
inside a certifying authority. Give what we know of some of the
"mistakes" made by CA's, perhaps they may have done so already, and
those were really failed operations that couldn't be kept secret.
Cheers,
- Ted
Arnold Reinhold
Sent from my iPhone
[I'm responding to a somewhat old message, because I think this is an interesting idea worth thinking more about]
D. J. Bernstein has proposed an attack..,
...While placing a key stretcher in the RNG chain may seem overkill to just thwart the Bernstein entropy combiner attack, an attack which demands somewhat far fetched preconditions, using a key stretching hash can also mitigate the type of attack proposed by Georg T. Becker. et. al. (Stealthy Dopant-Level Hardware Trojans http://people.umass.edu/gbecker/BeckerChes13.pdf ) An attacker using the Becker technique will reduce the effective state space of the RNG being cooked. The cooked state space must be small enough to allow a brute force search of possible RNG states, but not so small as to risk detection. Applying a high work factor key stretcher to the output of a Beckerized RNG would make the state space search far more expensive and possibly force the attacker to shrink the effective state space enough to allow detection.
Yes, this is a variant of the entropy guessing attack.The obvious problem with making initializing the RNG computationally expensive is that people really don't like waiting for their RNG to be ready to generate random bits. (Note the pressure *not* to make /dev/urandom block when it doesn't have enough input entropy. For that matter, note the use of /dev/urandom for crypto products and libraries that should know better.)I wonder if you might even make some RNGs worse, in practice, by doing this. If my system has to have a working RNG ten seconds after startup, I can either:a. Collect entropy for 10 seconds and seed my RNG.b. Collect entropy for 10-T seconds and then run my key stretching algorithm for T seconds.Suppose we are getting 8 bits of entropy per second, and I set T=5 (so I run my key stretching function for 5 seconds). I now am seeding with 40 bits of entropy, and running for five seconds maybe I'm putting another 25 bits of security into the system, but I am losing more by not incorporating the other 5 seconds' worth of entropy in.
We could incorprate late-arriving entropy into the RNG at the end of the key stretching algorithm, but that kills its value for blocking the attack you were describing above.
D. J. Bernstein
randomness-generation mailing list kept.]
Theodore Ts'o writes:
> The other thing I'd note about "The Bernstein Attack" is that it
> requires O(2**N) work to reduce the key strength by N bits.
the original attack description from the mailing list or from my blog
(http://blog.cr.yp.to/20140205-entropy.html). This includes a standard
signature system being broken at a cost of just 2^4 hashes per RNG call.
> suppose you have a 256 bit AES random session key
there's ample security margin and robustness against deviations from
randomness, while RNGs are very frequently used in much more dangerous
ways. One of the main points I'm making is that we _shouldn't_ be using
RNGs so much.
> compromising the execution engine such that you can snoop on memory,
> etc., would require at least 10x to 100x more engineers to be able to
> figure out that the CPU was doing something evil
for example, the microcoded string-copy instructions. Anyone with a
particular signing key has the power to distribute encrypted microcode
updates that everyone installs and nobody audits.
John Kelsey writes:
> leak your keys (or your RNG seeds) via some subliminal channel.
perfect channel for such leaks---if we're constantly using it, which is
unfortunately the situation today.
---Dan
Theodore Ts'o
> > suppose you have a 256 bit AES random session key
>
> This is a highly misleading example. You're focusing on a case where
> there's ample security margin and robustness against deviations from
> randomness, while RNGs are very frequently used in much more dangerous
> ways. One of the main points I'm making is that we _shouldn't_ be using
> RNGs so much.
fundamentally dangerous system to use. Which again is nothing new....
> It's completely trivial for microcode to "snoop" on memory; consider,
> for example, the microcoded string-copy instructions. Anyone with a
> particular signing key has the power to distribute encrypted microcode
> updates that everyone installs and nobody audits.
to someone who is testing the CPU; but what's *really* hard to do is
make changes that causes the CPU to change its behaviour in an
undocumented way. If the backdoor triggers unexpectedly, perhaps when
the details of the OS's RNG changes, or from internal regression
testing, the fact that the CPU had been compromised would become
evident, and remember the NSA wants to stay covert.
The back door you are proposing is not only very risky, but also
highly fragile when the OS's RNG changes --- for example, in Linux how
we do the mixing has changed several times over the past few years.
So not only would the NSA have to bury a change deep inside the
microcode in a way that some Intel engineer with a conscience doesn't
find it, but they would have to constantly update it.
Honestly, if you are worried about that sort of thing, it's much more
likely and much easier for the NSA would suborn an release engineer at
Microsoft or Red Hat....
- Ted
D. J. Bernstein
> If the backdoor triggers unexpectedly, perhaps when the details of the
> OS's RNG changes, or from internal regression testing, the fact that
> the CPU had been compromised would become evident
that it's happening. The only impact would be that the "random" numbers
change to, e.g., data encrypted under the attacker's key with AES, for
example to exfiltrate your PGP keys.
The original post was explicitly limited to modifications in the
"random" numbers precisely because (when done sensibly) this is safe
against detection---while tampering with other data is much more risky
for the attacker.
> Actually, I'd take as the lesson from your example that DSA is a
> fundamentally dangerous system to use. Which again is nothing new....
post) paints a quite different picture. First, in this setting
_randomized_ DSA is broken, but _deterministic_ DSA is just fine.
Second, and more broadly, the attack has many troubling consequences for
uses of randomness beyond DSA, while systematic use of _deterministic_
cryptography renders the attack practically impotent.
---Dan