Java中"x == 7"到1(真)或0(假)的快速恒定时间评估

Question

我想将一个加密函数从C移植到Java.该函数必须在恒定时间内运行,因此不允许使用条件分支(并且不允许基于x的表查找).

原始的C代码是:

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

因此,如果'x == 7','result'设置为1,否则设置为0.然后将'result'变量用于进一步的计算.

我现在正在寻找将其转换为Java的最佳方法.就像在Java表达式中评估为布尔值而不是整数一样,必须使用运算符来模拟上述情况.

我目前正在使用

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

这对我来说很好,因为我的x在{0,...,15}范围内.(请注意,shift函数仅使用低5位,因此当x太大时,您将得到误报.)

表达式将被评估数百万次,因此如果有一个聪明的解决方案只使用2个运算符而不是3个运算符,这将使整体计算更快.

Answer 1

@ Hosch250指出的最佳选择是三元运算符.让我们看一下JIT编译器为这个方法生成的汇编程序:

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

它实际上取决于分支分析.当你经常x有价值时7,它的编译方式如下:

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

看到三元被替换cmovne为不是分支指令.

另一方面,如果你传递7非常罕见的情况(例如5000次通话中),那么分支就在这里:

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

现在分支几乎从未被占用,因此保持条件的速度越快,因为CPU分支预测器几乎总是正确的.需要注意的是<slowpath>不只是return 1;,它还更新了分支配置属性,因此,如果它发生了程序执行过程中改变了模式(7变得更经常出现),那么该方法将被重新编译的第一个版本.

通常,在这种简单的情况下,不要试图比JIT编译器更聪明.

Answer 2

好吧,所以我认为你问这个问题的原因是,如果加密函数的执行时间取决于函数的输入,那么攻击者可以通过测量执行时间来获得有关这些输入的线索.(因此,正常的"过早优化"和"不要试图超越编译器"的建议并不真正适用.)

鉴于此,以下是我的建议:

• 如果x在编译时(或JIT编译时)是常量,那么代码可能会被优化为 result = true;或者result = false;

• 如果x不是常数,但有一小部分可能的值,那么下列方法之一可能会起作用:

  // 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;
  }
  

问题是,在我能想到的每种可能的方法中,JIT编译器可以合法地将非分支代码优化为分支代码.如果这对安全性至关重要,那么您需要调查为每个需要认证的平台发出的实际本机代码.

另一种方法是:

1. 分析Java代码算法,
2. 尝试发现可能存在条件分支的情况,
3. 设计测试输入来触发那些分支路径,
4. 测量执行时间(在所有目标平台上),以查看您的测试输入集之间是否存在可检测的差异.

当然,另外需要注意的是,无论如何这可能是没有意义的; 例如,result然后在密码函数的另一部分中使用if 来决定执行路径.

而......

表达式将被评估数百万次,因此如果有一个聪明的解决方案只使用2个运算符而不是3个运算符,这将使整体计算更快.

如果这是你真正的动机......那么我的建议就是不要打扰.这是不成熟的优化.将它留给JIT编译器.

Answer 3

三元在这里是一个不错的选择：

result = x == 7 ? 1 : 0;

如果表达式计算结果为1，则此代码分配，否则分配。resultx == 7true0