<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Aug 28, 2013 at 10:50 AM, Paul Robinson <span dir="ltr"><<a href="mailto:pogo.work@gmail.com" target="_blank">pogo.work@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="im">On Mon, Aug 26, 2013 at 9:14 PM, Todd Jackson <span dir="ltr"><<a href="mailto:quantum.skyline@gmail.com" target="_blank">quantum.skyline@gmail.com</a>></span> wrote:<br>
</div><div class="gmail_extra"><div class="gmail_quote"><div class="im">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><div class="gmail_quote">
<div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>
> We would also include a secure random number generator which links<br>
> against OpenSSL. This would of course be an optional module disabled<br>
> by default, but is necessary so the randomization is cryptographically<br>
> secure and useful in security applications.<br>
<br>
</div>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.</blockquote><div><br></div>
</div><div>(disclaimer: I was a member of Stephen's research group and worked on this project.) </div><div><br></div><div>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.</div>
<div><br></div></div></div></div></blockquote></div><p>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.</p></div></div></div></blockquote><div>Yes and no. My primary concern was RNG state compromise.</div><div><br></div><div>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.</div>
<div><br></div><div>My requirements for this use case became:</div><div>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.</div>
<div>2) Resistant to state compromise.</div><div>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. </div>
<div>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.</div>
<div> </div><div>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".</div>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><p>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.</p>
</div></div></div></blockquote><div>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. </div><div><br></div>
<div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div class="im">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div></div><div>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.</div>
<div><br></div><div>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.</div>
</div></div></div></blockquote><div><br></div></div><div>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.</div>
</div></div></div></blockquote><div><br></div><div>I believe you've missed my point. I was aiming for a conservative proof of concept and a secure RNG. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>As for using AES-128, I see buzzword value, but no real technical need. </div></div></div></div></blockquote><div><br></div><div>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.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>(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.)</div>
</div></div></div></blockquote><div><br></div><div>Fair point on export, but the cipher and/or generator can be substituted.</div></div></div></div>