<div dir="ltr">I've been meaning to write about this for a while, but I think now is good timing. While LLVM has plenty of problems regarding generation of constant-time code (or actually any sophisticated enough compiler), it simultaneously provides plenty of resources for tracking information flow and building a static analysis tool to check for variable-time behavior in compiled code. That's the approach we used in FlowTracker:<div><br></div><div><div><a href="http://cuda.dcc.ufmg.br/flowtracker/">http://cuda.dcc.ufmg.br/flowtracker/</a> <br><br>You can type or upload your code (currently, we only deal with algorithms implemented in C), and we can point out if the implementation's run time depends on secret information. We use an XML file to describe sensitive data. A tutorial and examples of use are available at <a href="http://cuda.dcc.ufmg.br/flowtracker/example.html">http://cuda.dcc.ufmg.br/flowtracker/example.html</a>. Of course, not having information about exactly what instructions take constant time is still a limitation.</div><div><br></div><div>PS: Beware this is ongoing work, with lots of space for improvement.<br><br><div>Best,</div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal">--</span><br style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal">Diego de Freitas Aranha</span><br style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal"><span style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal">Institute of Computing - University of Campinas</span><br style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:normal"><a href="http://www.ic.unicamp.br/~dfaranha" target="_blank" style="color:rgb(17,85,204);font-family:arial,sans-serif;line-height:normal">http://www.ic.unicamp.br/~dfaranha</a><br></div><div><br><div class="gmail_quote">On Fri, Apr 3, 2015 at 3:53 PM Irene Knapp <<a href="mailto:ireneista@gmail.com">ireneista@gmail.com</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Well, my revised suggestion is actually to skip its codegen and go directly to the class that knows how to output x86-64.  It's conceptually an internal class, but it's still part of the documented API (to the extent that any of LLVM can be said to be documented).  You'd be hooking in as if your code were the codegen, and yes, it'd be specific to the architecture but that's what you wanted.<div><br></div><div>I definitely don't want to push this too hard; I understand that I'm not the one who would actually be implementing any solution. :)  Coming from the compilers background, it's the appealing route to me.</div></div><div dir="ltr"><div><br></div><div>Irene</div></div><br><div class="gmail_quote">On Fri, Apr 3, 2015 at 11:48 AM Michael Hamburg <<a href="mailto:mike@shiftleft.org" target="_blank">mike@shiftleft.org</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><blockquote type="cite"><div>On Apr 3, 2015, at 11:41 AM, Tony Arcieri <<a href="mailto:bascule@gmail.com" target="_blank">bascule@gmail.com</a>> wrote:</div><br><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Apr 3, 2015 at 11:35 AM, Irene Knapp <span dir="ltr"><<a href="mailto:ireneista@gmail.com" target="_blank">ireneista@gmail.com</a>></span> wrote:<br><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"><span style="font-size:19.7999992370605px;line-height:23.7600002288818px">Surely, what you are describing is a lightweight tool that either generates LLVM bitcode, or hooks into the LLVM backends at a slightly lower level than that to output particular instructions when that's what you really, really want - but I suspect its hinting system already makes that unnecessary for this use-case.  LLVM bitcode is precisely this "mostly concrete assembly" concept that you're describing.</span></div></blockquote><div><br></div><div>The problem with using LLVM in this context is robust cryptographic implementations need to follow a very specific set of rules to avoid cache timing attacks, and LLVM is not designed to follow these rules:</div><div><br></div><div><a href="https://cryptocoding.net/index.php/Coding_rules" target="_blank">https://cryptocoding.net/index.php/Coding_rules</a></div><div><br></div><div>LLVM has not been designed to support the generation of constant time code and is instead rather eager to do things like insert branches in otherwise branch free code if it thinks the code can be better optimized. </div></div><div><br></div>-- <br><div>Tony Arcieri</div></div></div></div></blockquote><br></div></div><div style="word-wrap:break-word"><div>It may be that if your tool chooses carefully the optimization passes — or even avoids most of them entirely — you could get constant-time operation.  But I don’t know enough about LLVM’s codegen to be sure one way or the other.  At least until recently, though, it was absolutely terrible at things like add-with-carry intrinsics.  (Not necessarily making them variable time, but lowering add; addc to add; setc; zext; add; add.)</div><div><br></div><div>— Mike</div></div></blockquote></div>
______________________________<u></u>_________________<br>
Curves mailing list<br>
<a href="mailto:Curves@moderncrypto.org" target="_blank">Curves@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/curves" target="_blank">https://moderncrypto.org/<u></u>mailman/listinfo/curves</a><br>
</blockquote></div></div></div></div></div>