7

我想将加密函数从 C 移植到 Java。该函数必须在恒定时间内运行，因此不允许有条件分支（也不允许基于 x 的表查找）。

原始C代码是：

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

因此，如果 'x==7' 则将 'result' 设置为 1，否则设置为 0。然后在进一步的计算中使用“结果”变量。

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

我目前使用

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

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

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

4

5 回答 5

7

@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 编译器更聪明。

于 2015-09-05T04:18:33.033 回答
6

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

鉴于此，以下是我的建议：

  • 如果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 编译器。

于 2015-09-05T04:18:11.123 回答
3

既然目标是完成

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

以某种没有分支的代数方式，

result = 1 >> (x^7);

但这不起作用，因为右移仅被屏蔽为几位。所以，你能做的是，

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

但它仍然在 -6 的情况下被屏蔽（在 -6 ^ 7 的情况下设置所有位），所以，

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

那么，它比条件分支慢多少？上述解决方案使用 bitCount() 来多次比较整个范围 int range，

user    0m5.948s

使用分支 (x == 7 ? 1 : 0),

user    0m2.104s

所以考虑到你得到适用于任何值的恒定时间比较，这并不算太糟糕，7 只是一个例子。是的， Integer.bitCount() 也是常数时间。

于 2015-09-05T05:13:00.997 回答
2

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

result = x == 7 ? 1 : 0;

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

于 2015-09-05T00:09:48.763 回答
2

利用 x 的极其有限的范围（在 [0,15] 中），我建议使用寄存器内表查找，每个表条目使用一位。该表为那些应该产生 1 的输入设置了位i ，否则为零。这意味着我们的表是字面常量 2 7 = 128：

int x,result;
result = (128 >> x) & 1;
于 2015-09-12T21:42:41.590 回答