Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

13
  • The part about caches seems out of place. I've never seen a bit hack that uses less memory than the obvious way. If anything, they add lookup tables. Usually they only add bitwise operations, and sometimes (shorter) loops and branches. Occasionally a fast bit hack may make it worthwhile to calculate values on the fly instead of caching them but that too seems rather rare. Commented Jun 29, 2014 at 18:34
  • Side-channel countermeasure is more an art of machine code obfuscation than optimization. Commented Jun 29, 2014 at 19:59
  • @rwong when you are dealing with Java, you have difficulty getting the degree of machine code obfuscation that one would find in something closer to the metal. What you do have is the ability to avoid branches. For crypto, its not about making it run fast (many times its intended to make it run slow), but to make it run consistently. Commented Jun 29, 2014 at 20:15
  • 1
    @rwong by forcing the system to do things without branching and preforming all of the operations on each piece of data (even if they are null operations). By using the bit version of min (the sample code), the system doesn't know what you are trying to do with those bit operations and so can't optimize out any of those operations. As there are no branches, branch prediction isn't something that one can use to figure out the data. Thus, by careful choice of bit operations, one can avoid the compiler and runtime optimizations that could happen with branches and more straight forward code. Commented Jun 29, 2014 at 20:23
  • 1
    @MichaelT Removing the if is obviously necessary to avoid side-channels. But even without an if, I wouldn't trust < to be constant time. Since the output of a comparison goes to the flag register not to a normal register of x86, I wouldn't be surprised if a compiler emitted a branch to turn the flag into 0 or 1. I've never seen < in code claiming to be constant time, always workarounds like subtract and shift. Commented Jul 1, 2014 at 17:15