llvm dev - Aug 2013 - [LLVMdev] Adding diversity for security (and testing)

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

On 08/28/2013 12:01 PM, Stephen Checkoway wrote:
> 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).
Hi Stephen,

Thanks for spelling out the possible attack models in detail. This is 
pretty much the way we were thinking. However, I wanted to make a minor 
clarification on our proposed implementation, just to be clear. Rather 
than inserting NOP sleds before functions, we actually insert various 
NOP-like instructions randomly between existing MachineInstrs, in order 
to provide more fine-grained diversity. This gives the attacker as 
little information as possible about the exact layout of the final 
binary. In terms of RNG selection, we were especially concerned about 
partial leakage of binary contents (or leakage of some but not all 
binary files from a build sharing the same seed) revealing the initial 
seed and therefore, by recompilation, the entire binary.

- Stephen Crane

On Aug 28, 2013, at 5:36 PM, Stephen Crane <sjcrane at uci.edu> wrote:
> Rather than inserting NOP sleds before functions, we actually insert
various NOP-like instructions randomly between existing MachineInstrs, in order
to provide more fine-grained diversity.
Right. I assumed it was something like the multibyte NOPs in
<http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/37204.pdf>
(Section 5.4).
> This gives the attacker as little information as possible about the exact
layout of the final binary. In terms of RNG selection, we were especially
concerned about partial leakage of binary contents (or leakage of some but not
all binary files from a build sharing the same seed) revealing the initial seed
and therefore, by recompilation, the entire binary.
Oh interesting. I hadn't thought about partial information in that way.

One thought I had about seed selection is if it ends up being based on time
(when not chosen by command line flags), then do you have issues with files that
use the __TIME__ macro? Or did you have a better seeding mechanism?

-- 
Stephen Checkoway