CODEWITHSUNDEEP
javaperformancebit-manipulationconstant-time
Chris
Chris

Reputation: 187

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

I want to port a crypto function from C to Java. The function has to run in constant time, so no conditional branchings (and no table lookups based on x) are allowed.

The original C code is:

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

So that 'result' is set to 1 if 'x==7' and to 0 otherwise. The 'result' variable is then used in further computations.

I am now looking for the best way to transpose this to Java. As in Java expressions evaluate to booleans and not to integers, one has to simulate the above using operators.

I currently use 

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

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

The expression will be evaluated millions of times, so if it there is for instance a clever solution that uses only 2 operators instead of 3, this would make the overall computation faster.

Upvotes: 7

Views: 1447

Answers (5)

njuffa
njuffa

Reputation: 26185

Taking advantage of the extremely limited range of x, which is in [0,15], I propose using an in-register table lookup, using one bit per table entry. The table has bit i set for those inputs that should produce a 1, and zero otherwise. This means our table is the literal constant 27 = 128:

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

Upvotes: 2

user3427419
user3427419

Reputation: 1779

Since the goal is to accomplish

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

in some sort of algebraic fashion without branching,

result = 1 >> (x^7);

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

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

but it's still masked for case of -6 (all bits set in case of -6 ^ 7), so,

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

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

user    0m5.948s

Using branching, (x == 7 ? 1 : 0),

user    0m2.104s

So it's not too bad considering you get constant time comparison that works for any value, 7 being just an example. Yes, Integer.bitCount() is constant time too.

Upvotes: 3

Tagir Valeev
Tagir Valeev

Reputation: 100279

The best option as noted by @Hosch250 is ternary operator. Let's take a look at the assembler generated by JIT compiler for this method:

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

It actually depends on branch profiling. When your x has value 7 quite often, it's compiled like this:

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

See that ternary was replaced with cmovne which is not the branch instruction.

On the other hand if you pass 7 in very rare cases (e.g. once in 5000 calls), then branch is here:

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

Now branch is almost never taken, so the faster is to keep the condition as CPU branch predictor will be almost always correct. Note that <slowpath> is not just return 1;, it also updates the branch profile, so if it happens that the pattern changed during the program execution (7 become to appear more often), then the method will be recompiled to the first version.

In general, don't try to be smarter than JIT-compiler in such simple cases.

Upvotes: 7

Stephen C
Stephen C

Reputation: 719336

OK, so I think that the reason you are asking this is that if the execution time of a crypto function depends on the inputs to the function, then an attacker can gain clues as to those inputs by measuring the execution time. (Hence, the normal "premature optimization" and "don't try to outsmart the compiler" advice don't really apply.)

In the light of that, here are my suggestions:

  • If x is a constant at compile time (or JIT compile time) then the chances are that the code will be optimized to either result = true; or result = false;

  • If x is 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 every possible approach I can think of, the JIT compiler could legally optimize non-branching code into branching code. If this is security critical, then you need to investigate the actual native code emitted for every platform that you need to certify.

The other approach is to:

  1. analyze the Java code algorithm,
  2. try to spot cases where conditional branching is likely,
  3. design test inputs to trigger those branching paths,
  4. measure execution time (on all target platforms) to see if there is a detectable difference across your set of test inputs.

Of course, the other thing to note is that this may be moot anyway; e.g. if result is then used in another part of the crypto function to decide with execution path to take.

And ...

The expression will be evaluated millions of times, so if it there is for instance a clever solution that uses only 2 operators instead of 3, this would make the overall computation faster.

If this is your real motivation ... then my advice is Don't Bother. This is premature optimization. Leave it to the JIT compiler.

Upvotes: 6

user2509848
user2509848

Reputation:

A ternary would be a good option here:

result = x == 7 ? 1 : 0;

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

Upvotes: 2

Related Questions