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

> > We would also include a secure random number generator which links
> > against OpenSSL. This would of course be an optional module disabled
> > by default, but is necessary so the randomization is cryptographically
> > secure and useful in security applications.
>
> I am not sure why you need this feature.   You can provide LLVM with a
> SEED value that can be controlled from the command line.  A wrapper (such
> as a build-script) can control this value.

(disclaimer:  I was a member of Stephen's research group and worked on this
project.)

To my knowledge, the pseudorandom number generator in LLVM is not
cryptographically secure.  In this use case, the intent is to make it
difficult to get the random number seed or the generator's state at any
point in the random number stream by looking at the output.  If the state
of the generator can be compromised, then an attacker can predict the
output of the generator by playing it forward.  If an attacker can play the
generator forward, then the attacker can reproduce the rest of the
executable, including the randomized components that are no longer random
to the attacker.  Reproducing the executable means that diversification
isn't going to work because the attacker can plan around it.

For reproducibility, such as for debugging, a pure software generator is a
good idea.  This also prevents blocking read operations in the generator,
slowing down the compiler.  Software generators can be optimized for speed.
 These are reasons to avoid /dev/random et al.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130826/5464f79f/attachment.html>

On Mon, Aug 26, 2013 at 9:14 PM, Todd Jackson <quantum.skyline at
gmail.com>wrote:
>
>  > We would also include a secure random number generator which links
>> > against OpenSSL. This would of course be an optional module
disabled
>> > by default, but is necessary so the randomization is
cryptographically
>> > secure and useful in security applications.
>>
>> I am not sure why you need this feature.   You can provide LLVM with a
>> SEED value that can be controlled from the command line.  A wrapper
(such
>> as a build-script) can control this value.
>
>
> (disclaimer:  I was a member of Stephen's research group and worked on
> this project.)
>
> To my knowledge, the pseudorandom number generator in LLVM is not
> cryptographically secure.  In this use case, the intent is to make it
> difficult to get the random number seed or the generator's state at any
> point in the random number stream by looking at the output.  If the state
> of the generator can be compromised, then an attacker can predict the
> output of the generator by playing it forward.  If an attacker can play the
> generator forward, then the attacker can reproduce the rest of the
> executable, including the randomized components that are no longer random
> to the attacker.  Reproducing the executable means that diversification
> isn't going to work because the attacker can plan around it.
>
> I should think that the choices at each decision point of the randomized
code-generation effect would require only a few bits from the output of
each run of the RNG, and you can run the RNG again for each decision point.
Because the vast majority of the RNG output is therefore not available to
the attacker, it's really really really hard to reconstruct the sequence.
 Even if it's not a crypto-based RNG.

Any RNG with adequately long cycles, reasonable bit-width, and
minimum-width enforcement on the seed value would be fine. And
computationally a lot cheaper than a crypto-based RNG.
> For reproducibility, such as for debugging, a pure software generator is a
> good idea.  This also prevents blocking read operations in the generator,
> slowing down the compiler.  Software generators can be optimized for speed.
>  These are reasons to avoid /dev/random et al.
>
> 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.  My house would be "more secure" if I put 24x7 armed
guards
around it, but the threat level doesn't justify the cost.

As for using AES-128, I see buzzword value, but no real technical need.
 (No question that "crypto == good" syndrome comes into play here;
it's
rare that you have to defend using crypto even if it isn't warranted.
 Until you run into a cranky-pants like me!)  In any case you need a
fallback for when OpenSSL isn't available.  I'm not claiming what LLVM
has
now is adequate for you (looks like it uses rand(2)) but AES-128 seems like
overkill. (I've lost track of the general crypto-export-control state of
things, but just a reminder that LLVM avoids anything that could possibly
be export-controlled.)

Pogo
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130828/4950b4c2/attachment.html>

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 Wed, Aug 28, 2013 at 10:50 AM, 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:
>
>>
>>  > We would also include a secure random number generator which
links
>>> > against OpenSSL. This would of course be an optional module
disabled
>>> > by default, but is necessary so the randomization is
cryptographically
>>> > secure and useful in security applications.
>>>
>>> I am not sure why you need this feature.   You can provide LLVM
with a
>>> SEED value that can be controlled from the command line.  A wrapper
(such
>>> as a build-script) can control this value.
>>
>>
>> (disclaimer:  I was a member of Stephen's research group and worked
on
>> this project.)
>>
>> To my knowledge, the pseudorandom number generator in LLVM is not
>> cryptographically secure.  In this use case, the intent is to make it
>> difficult to get the random number seed or the generator's state at
any
>> point in the random number stream by looking at the output.  If the
state
>> of the generator can be compromised, then an attacker can predict the
>> output of the generator by playing it forward.  If an attacker can play
the
>> generator forward, then the attacker can reproduce the rest of the
>> executable, including the randomized components that are no longer
random
>> to the attacker.  Reproducing the executable means that diversification
>> isn't going to work because the attacker can plan around it.
>>
>> I should think that the choices at each decision point of the
randomized
> code-generation effect would require only a few bits from the output of
> each run of the RNG, and you can run the RNG again for each decision point.
> Because the vast majority of the RNG output is therefore not available to
> the attacker, it's really really really hard to reconstruct the
sequence.
>  Even if it's not a crypto-based RNG.
>
Yes and no.  My primary concern was RNG state compromise.

You are correct in that the majority of the RNG output is probably not
available to the attacker.  However, it is still possible to reconstruct
the state of the RNG depending on how it's designed.  I did an experiment
where I used a linear congruential generator (I know they're not great
generators either, but it was a place to start when defining requirements)
to add random pads to the stack frame, and then tried to reconstruct the
seed from observing the resulting executable.  I was able to do this in a
few minutes on a Pentium 4, using three values of the RNG in order. I can
provide details on the experiment off list if people are interested.

My requirements for this use case became:
1) Reproducible and deterministic.  This is a side effect of researchers
thinking I was insane for proposing a RNG inside of a compiler, saying that
output couldn't be debugged since it was random.  The intent is that if you
put in the same seed and source code, you will always get the same
executable.
2) Resistant to state compromise.
3) Small enough to embed into a compiler that's open source, without making
assumptions about underlying hardware instructions.  That's why I used AES
in counter mode -- people have optimized the heck out of it to run on
multiple platforms.  Compilers already take long enough to build on some
platforms, and I didn't want to add a whole new library.
4) Generates good enough randomness.  I trusted NIST on this one.  Linear
conguential generators don't fit.  Last thing I wanted was a generator that
"looks" random, biases or invalidates results, and gives a false sense
of
security.

Any compliant RNG will do.  I used a crypto based RNG because it was
available, I was unaware of any other resistant generators, and I was being
conservative, not because I was looking for "buzzwords".
> Any RNG with adequately long cycles, reasonable bit-width, and
> minimum-width enforcement on the seed value would be fine. And
> computationally a lot cheaper than a crypto-based RNG.
>
Maybe.  State compromise still matters.  Sure, I could have used a hardware
generator, or Intel's AES instructions, but that didn't meet the
requirements.

As an implementation detail, I had to do key stretching to turn a 64-bit
numerical seed into something long enough to properly seed the generator.
 This was the actual time sink (measured by profiling), not the generator,
as AES was fast enough for proof of concept, and my experiments didn't
generate that many random numbers.  Stephen's version may vary from mine.

>  For reproducibility, such as for debugging, a pure software generator is
>> a good idea.  This also prevents blocking read operations in the
generator,
>> slowing down the compiler.  Software generators can be optimized for
speed.
>>  These are reasons to avoid /dev/random et al.
>>
>> 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.  My house would be "more secure" if I put 24x7
armed guards
> around it, but the threat level doesn't justify the cost.
>
I believe you've missed my point.  I was aiming for a conservative proof of
concept and a secure RNG.

> As for using AES-128, I see buzzword value, but no real technical need.
>
I'm not sure what to make of that.  See above. If you're aware of an RNG
that meets the above requirements, please feel free to suggest it.  It's
entirely possible I've missed something.

> (No question that "crypto == good" syndrome comes into play here;
it's
> rare that you have to defend using crypto even if it isn't warranted.
>  Until you run into a cranky-pants like me!)  In any case you need a
> fallback for when OpenSSL isn't available.  I'm not claiming what
LLVM has
> now is adequate for you (looks like it uses rand(2)) but AES-128 seems like
> overkill. (I've lost track of the general crypto-export-control state
of
> things, but just a reminder that LLVM avoids anything that could possibly
> be export-controlled.)
>
Fair point on export, but the cipher and/or generator can be substituted.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130828/6d1228f2/attachment.html>

I think others more qualified than myself have sufficiently addressed 
why having a strong (aka crypto-secure) RNG is a good idea, so I will 
leave that. However, I can shed some light on a few of the practical 
concerns of our proposed additions.

On 08/28/2013 10:50 AM, Paul Robinson wrote:
> As for using AES-128, I see buzzword value, but no real technical 
> need.  (No question that "crypto == good" syndrome comes into
play
> here; it's rare that you have to defend using crypto even if it
isn't
> warranted.  Until you run into a cranky-pants like me!)  In any case 
> you need a fallback for when OpenSSL isn't available.  I'm not 
> claiming what LLVM has now is adequate for you (looks like it uses 
> rand(2)) but AES-128 seems like overkill. (I've lost track of the 
> general crypto-export-control state of things, but just a reminder 
> that LLVM avoids anything that could possibly be export-controlled.)
We do provide a fall-back (currently a simple LCG) if linking against 
OpenSSL is undesirable in some circumstances. The crypto export battle 
is basically over, and all Linux distributions and (so far) OS X ship 
OpenSSL. OpenSSL binary packages are also available for building on Windows.

- stephen