[Cryptography] [IP] 'We cannot trust' Intel and Via's chip-based crypto, FreeBSD developers say

[Jerry Leichter]

On Dec 17, 2013, at 7:26 AM, Roland C. Dowdeswell wrote:
>> The RDRAND instruction I'd say is the low hanging fruit, because it
>> is called rarely and for precise purposes.  Inside that instruction,
>> check whether there is a XOR coming up...
> 
> It's probably sufficient to just have RDRAND output a predictable
> value XORed with all of the registers.  Given that the only
> unpredictable value in any of the registers is going to be the
> output of the OS RNG, this would likely be enough....
A couple of invocations of RDRAND would test whether that attack had been implemented.

In fact, an attack against any particular bit of RDRAND-using code that relied on a constant could be just as easily detected.  To be undetectable, the attack has to mix in a value that (a) cannot be distinguished from a random value by an auditor with realistic resources ("distinguishable given 2^64 outputs" is effectively indistinguishable; (b) is predictable to the attacker.

I've been putting some thought into characterizing attacks against RNG's that would not be readily detectable by a reasonably-resourced opponent who suspect they were there.  I don't think this is possible if all the CPU's used are assumed to be internally identical.  But if an attacker is in a position to provide, say, a unique seed on each chip, and the chip can save state across restarts, the RDRAND instruction can simply use something like AES in counter mode.  Even if the attacker doesn't know what particular chip is being used or how often it's been power-cycled, given a sequence of RDRAND outputs, it need "only" try all known seed values and all "reasonably small" counts of generated values.  An auditor, lacking access to the database of seeds, has to consider all *possible* values for the seed. It does have the Birthday Paradox in its favor - it would look for a collision in about O(sqrt(# seeds)), but the size of the seed space can easily be large enough to defeat this.

To mount such an attack, the attacker has to be in a position to see raw RDRAND outputs (or known/predictable transformations of that output).  For one thing, this suggests that RDRAND should only be accessible to kernel code!  Feeding RDRAND into a Yarrow-like construction would block that.  Actually XOR'ing with the output of the existing RNG is dangerous to the degree that the existing RNG is predictable, but in and of itself doesn't seem to help the attacker.  If, somehow, we have some existing bits from an RNG and code implementing some function F(RNG, RDRAND) that combines them, an attacker who can recognize that RDRAND is being called inside of F can substitute a different function F'(RDRAND) that ignores RNG completely.  For any "normal" instruction, this is readily detectable by testing - just put in different RNG values and make sure that the output changes.  But there's no way to conduct such a test here, because there's no way for an auditor to force, or predict, the RDRAND output.  (A special test mode wouldn't help as the "spike" code would disable itself in that mode, so you could never run the same test in both test and regular mode.)

There is a relatively straightforward defense against all this:  Save a large number of RDRAND output values away somewhere, and only use them much later.  If RDRAND doesn't have access to the code that uses its values, it can only produce its random-looking output stream.  A separate thread continuously filling a 1000 RDRAND-output-sized values, which would then be drawn out to be XOR'ed with the output of some other RNG, would probably be so difficult to suborn that the attackers would move elsewhere (and there are plenty of other plausible attacks).
                                                        -- Jerry