[LLVMdev] Adding diversity for security (and testing)

[Stephen Checkoway]

On Aug 28, 2013, at 1:50 PM, Paul Robinson <pogo.work at gmail.com> wrote:

> On Mon, Aug 26, 2013 at 9:14 PM, Todd Jackson <quantum.skyline at gmail.com>wrote:
> 
>> Personally, I think it is necessary to go for the strongest random number
>> generator possible.  Cryptographically secure pseudorandom number
>> generators have good properties that make them resistant to compromise.  In
>> the case of the generator I think Stephen is proposing -- a generator based
>> on running AES-128 in Counter Mode and described in one of NIST's documents
>> -- the security comes from strong crypto building blocks, while still
>> suitable for embedding in a  compiler.
>> 
> 
> Security comes from careful threat analysis and establishing
> counter-measures appropriate to the threats, which might or might not
> warrant crypto.


This is a very good point. It may help to clarify your threat model here. Let's think about who the attackers are. Some possibilities:

1. Local attacker who can read the contents of the binary. This defense doesn't really buy you anything given automated attack creation frameworks like Q [1].

2. Local attacker who cannot read the contents of the binary. (This is a pretty strange one, but it's possible.) The attacker is forced to rely on side channel information such as timing channels in an attempt to discover the length of the inserted NOP sleds. This sounds like an extraordinarily difficult task, but possibly doable. With a weak PRNG like a LCG, for example, you may have sufficient information to break it [2] (I believe there are better attacks, but this is the first that came up with a quick search).

3. Remote attacker who can use a memory disclosure bug to read the contents of the memory. Like attacker 1, the defense can be bypassed.

4. Remote attacker who cannot read out memory. This is similar to 2 but would seem to be far more difficult since your timing channel is far more noisy and the delay added by the NOPs is miniscule. Given how many sessions the latest DTLS attack took [3], even for attackers on the same LAN, and the fact that the difference in timing was in number of blocks to be MAC'd which takes at least two order of magnitude more time than some NOPs (500 to 1000 cycles according to AlFardan and Paterson), I'm doubtful the number of NOPs in even a single sled could be recovered.

For attackers 1 and 3, any PRNG is as good as any other. For 4, I'd be shocked if anything could be recovered using any PRNG (for whatever that's worth). Attacker 2 seems like the only situation where choice of PRNG might actually matter in practice.

Are there other classes of attackers you have in mind?

Of course, AES is _really_ fast [4] and in general, for a security application, I can't think of a good reason not to use a CSPRNG when random numbers are warranted.

1. http://users.ece.cmu.edu/~ejschwar/papers/usenix11.pdf
2. http://www.reteam.org/papers/e59.pdf
3. http://www.isg.rhul.ac.uk/tls/TLStiming.pdf
4. http://cr.yp.to/aes-speed/aesspeed-20080926.pdf

-- 
Stephen Checkoway