标签: constant-time

我有一段时间试图提出一个不违反C/C++标准的恒定时间旋转.

问题是边缘/角落情况,其中操作在算法中被调出并且那些算法不能被改变.例如,以下内容来自Crypto ++并执行GCC ubsan(即g++ fsanitize=undefined)下的测试工具:

$ ./cryptest.exe v | grep runtime
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is …

上下文

OpenSSL中的功能 BN_consttime_swap是一件美丽的事情.在此片段中,condition已计算为0或(BN_ULONG)-1:

#define BN_CONSTTIME_SWAP(ind) \
    do { \
            t = (a->d[ind] ^ b->d[ind]) & condition; \
            a->d[ind] ^= t; \
            b->d[ind] ^= t; \
    } while (0)
…
    BN_CONSTTIME_SWAP(9);
…
    BN_CONSTTIME_SWAP(8);
…
    BN_CONSTTIME_SWAP(7);

目的是为了确保更高级别的bignum操作需要恒定的时间,这个功能要么交换两个bignum,要么在恒定时间内将它们留在原位.当它离开它们时,它实际上读取每个bignum的每个单词,计算一个与旧单词相同的新单词,并将该结果写回原始位置.

目的是这将花费相同的时间,好像有效地交换了bignums.

在这个问题中,我假设一个现代的,广泛的架构,如Agner Fog在他的优化手册中描述的那些.还假设C代码直接转换为汇编(没有C编译器撤消程序员的努力).

题

我试图理解上面的构造是否表征为"尽力而为"的恒定时间执行,或者是完美的恒定时间执行.

特别是,我担心a在BN_consttime_swap调用函数时bignum 已经在L1数据缓存中的情况,并且函数返回后的代码立即开始在bignum上工作a.在现代处理器上,足够的指令可以同时在飞行中,以便在a使用bignum时技术上不会完成复制.在调用之后允许指令BN_consttime_swap工作的机制a是存储器依赖性推测.让我们假设为了论证而进行天真的记忆依赖性推测.

这个问题似乎归结为:

当处理器最终检测到BN_consttime_swap从内存读取后的代码,与推测相反,已经写入函数内部时,一旦检测到地址已被写入,它是否取消推测执行,或者它是否允许自己当它检测到已写入的值与已存在的值相同时保留它？

在第一种情况下,BN_consttime_swap看起来它实现了完美的恒定时间.在第二种情况下,它只是尽力而为的恒定时间:如果没有交换bignums,那么在调用之后执行的代码BN_consttime_swap将比它们被交换时快得多.

即使在第二种情况下,这看起来似乎可以在可预见的未来固定(只要处理器保持足够天真),对于两个bignums中的每一个的每个单词,写出不同于两个可能的最终值的值.在再次写入旧值或新值之前的值.该volatile类型修饰符可能需要在某一时刻参与,以防止一个普通的编译器过度优化的序列,但它仍然听起来可能. …

我想将一个加密函数从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个运算符,这将使整体计算更快.

这个问题基本上说明了一切。假设我有一个（排序的）列表，可以包含 1K 到 1M 的任何项目。我有一个starting index和一个ending index。如果我使用该ArrayList.sublist(start, end)方法，时间复杂度是 O(n) 还是 O(1)？我确实在这里检查了答案，因为我认为这是一个常见问题，但是虽然我找到了 LinkedList 的重复答案，但我找不到关于 ArrayList 的具体问题。感谢大家的回答！

我正在使用一些bigint公钥加密代码.使用按位屏蔽以确保访问的计算时序和存储器地址与数据值无关是否安全？

这种技术是否容易受到基于指令时序,功率,RF发射或其他我不知道的事情的旁道攻击？(作为参考,我知道RSA盲法,EC蒙哥马利梯形图,高速缓存刷新等技术.)

简单代码示例(C/C++):

uint a = (...), b = (...);
if (a < b)
    a += b;

现在翻译为使用恒定时间屏蔽:

uint a = (...), b = (...);
uint mask = -(uint)(a < b);
a = ((a + b) & mask) | (a & ~mask);

注意,它a < b是0或1,掩码是0x00000000或0xFFFFFFFF.

同样,对于高级操作(C++):

Integer x = (...);
if (x.isFoo())
    x.doBar();

以下是可接受的安全翻译吗？

Integer x = (...);
uint mask = -(uint)x.isFoo();  // Assume this is constant-time
Integer y(x);                  // Copy constructor
y.doBar();                     // Assume this is constant-time …

我的网站上有以下 JavaScript，以便在执行某些特定搜索时，答案会被硬编码到特定页面：

function redirect() {
    var input = document.getElementById('searchBox').value.toLowerCase();

    switch (input) {
      case 'rectangular':
        window.location.replace('http://www.Example.com/Rectangular/');
        break;
      case 'elephant':
        window.location.replace('http://www.Example.com/Elephants/');
        break;
      case 'coils':
        window.location.replace('http://www.Example.com/Parts/');
        break;
      default: // No keyword detected: submit the normal search form.
        return true;
        break;
    }
    return false; // Don't let the form submit
}

我想知道 JavaScript 中的搜索语句是否与 case 语句的数量或恒定时间呈线性关系？如果是线性的，是否有更好的方法来编写此代码，以便无论我编码的特殊情况有多少，它都是恒定时间？

我正在研究一种算法的实现,我想表明它可以在恒定时间内工作,即使有很多元素也是如此.

不幸的是,我需要一个存储元素的数据结构.当元素的数量非常高,但对我的算法而言并非不合理时,std :: vector和std :: valarray都不会在常量时间访问任意元素,如此图所示.

是否有更好的数据结构来存储值？是否有任何技术可以实现以实现恒定时间访问？