Fast constant time evaluation from "x == 7" to 1 (true) or 0 (false) in Java

Question

I want to transfer a cryptographic function from C to Java. The function must be executed in constant time, so there are no conditional branches (and viewing tables based on x).

Source Code C:

int x,result; ... result = (x==7); ... 

So, 'result' is set to 1 if 'x == 7' and 0 otherwise. Then, in further calculations, the variable "result" is used.

Now I am looking for a better way to port this to Java. As in Java expressions, they are calculated as logical, not integer, you need to simulate the above using operators.

I am currently using

 int x,result; ... result = (1<<(x-7))&1; ... 

which is great for me, since my x is in the range {0, ..., 15}. (Note that the shift function only uses the lower 5 bits, so you will get false positives when x is too large.)

The expression will be evaluated millions of times, so if there is, for example, a smart solution that uses only 2 operators instead of 3, it will speed up the overall calculation.

Answer 1

The best option noted by @ Hosch250 is the triple operator. Take a look at the assembler generated by the JIT compiler for this method:

 public static int ternary(int x) { return x == 7 ? 1 : 0; } 

Actually, it depends on branch profiling. When your x has a value of 7 quite often, it is compiled as follows:

 xor %r11d,%r11d mov $0x1,%eax cmp $0x7,%edx cmovne %r11d,%eax ;*ireturn ; - Test:: ternary@11 (line 12) 

See that the triple has been replaced by cmovne , which is not a branch statement.

On the other hand, if you transfer 7 in very rare cases (for example, once every 5000 calls), then the branch is here:

 cmp $0x7,%edx je <slowpath> ;*if_icmpne ; - Test:: ternary@3 (line 12) xor %eax,%eax 

Now the branch is almost never taken, therefore it is faster to save the state, since the processor branch predictor will almost always be correct. Note that <slowpath> not just return 1; , but also updates the profile of the branch, so if the template changes during program execution ( 7 becomes more common), then the method will be recompiled into the first version.

In general, do not try to be smarter than the JIT compiler in such simple cases.

Answer 2

OK, so I think the reason you ask for this is because if the execution time of the cryptofunction depends on the input of the function, then the attacker can obtain information about these inputs by measuring the execution time. (Therefore, the recommendations of "premature optimization" and "do not try to outsmart the compiler" do not actually apply.)

In light of this, here are my suggestions:

• If x is a constant at compile time (or JIT compile time), then the probability that the code will be optimized for result = true; or result = false;

• If x not a constant, but there is a small range of possible values, then one of the following approaches will probably work:

   // It is possible but unlikely that the JIT compiler will // turn this into conditional code. private boolean[] LOOKUP = new boolean[] { true, true, true, true, true, true, true, false}; ... result = LOOKUP[x]; // This depends on how the JIT compiler translates this to native // code. switch (x) { case 0: case 1: case 2: case 3: case 4: case 5: case 6: result = false; case 7: result = true; } 

The problem is that in all possible approaches that I can think of, the JIT compiler can legally optimize non-branching code into the branch code. If this is security critical, you need to examine the actual native code emitted for each platform that needs to be certified.

Another approach is as follows:

• analyze the Java code algorithm,
• try to identify cases where a conditional branch is probable,
• Introductory test inputs to run these branches,
• measure runtime (on all target platforms) to see if there is a detectable difference in your set of test inputs.

---

Of course, it should be noted that this can be controversial in any case; for example, if result then used in another part of the crypto function to decide which path to execute from.

AND...

The expression will be evaluated millions of times, so if there is, for example, a smart solution that uses only 2 operators instead of 3, it will speed up the overall calculation.

If this is your real motivation ... then my advice is Do not disturb . This is premature optimization. Leave it to the JIT compiler.

Answer 3

Because the goal is to achieve

 if (x == 7) result = 1; else result = 0; 

in some kind of algebraic form without branching,

 result = 1 >> (x^7); 

But then this does not work, because the right shift is masked by only a few bits. So what can you do

 result = 1 >> Integer.bitCount(x^7); 

but it is still masked for case -6 (all bits are set in case -6 ^ 7), therefore

 int bc = Integer.bitCount(x^7); return 1 >> (bc | (bc>>1)); 

So how much slower than the branch is conditional? Above solution using bitCount () to compare the entire int range more than once,

 user 0m5.948s 

Using the branch, (x == 7? 1: 0),

 user 0m2.104s 

So, this is not so bad, given that you get a constant time comparison that works for any value, 7 is just an example. Yes, Integer.bitCount () is also a constant time.

Answer 4

A triple option would be a good option:

 result = x == 7 ? 1 : 0; 

This code assigns 1 to result if x == 7 evaluates to true and assigns 0 otherwise.

Answer 5

Using the extremely limited range of x that is in [0,15], I suggest using a lookup in the register table, using one bit to write to the table. The table has bit i set for those inputs that must produce 1, and zero otherwise. This means that our table is a literal constant 2 ⁷ = 128:

 int x,result; result = (128 >> x) & 1;