问题标签 [constant-time]

我正在使用一些 bigint 公钥加密代码。使用按位掩码来确保计算时序和访问的内存地址独立于数据值是否安全？

这种技术是否容易受到基于指令时序、功率、射频发射或其他我不知道的事情的侧信道攻击？（作为参考，我知道 RSA 致盲、EC 蒙哥马利阶梯、缓存刷新等技术。）

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

现在翻译为使用恒定时间掩码：

注意a < b是 0 或 1，掩码为 0x00000000 或 0xFFFFFFFF。

同样，对于高级操作 (C++)：

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

语境

OpenSSL 中的功能 BN_consttime_swap很漂亮。在此代码段中，condition已计算为0or (BN_ULONG)-1：

目的是为了确保更高级别的 bignum 操作花费恒定的时间，这个函数要么交换两个 bignum，要么在恒定的时间内将它们留在原处。当它把它们留在原地时，它实际上读取每个 bignum 的每个单词，计算一个与旧单词相同的新单词，并将结果写回原始位置。

目的是这将花费与 bignums 被有效交换的时间相同的时间。

在这个问题中，我假设一个现代的、广泛使用的架构，例如 Agner Fog 在他的优化手册中描述的架构。还假定将 C 代码直接转换为汇编（没有 C 编译器取消程序员的努力）。

问题

我试图理解上面的构造是否被描述为“尽力而为”的恒定时间执行，还是完美的恒定时间执行。

特别是，我担心调用a函数时 bignum 已经在 L1 数据缓存中BN_consttime_swap，而函数返回后的代码立即开始处理 bignum的情况a。在现代处理器上，可以同时运行足够多的指令，以便在使用 bignum 时复制不会在技术上完成a。允许调用后的指令BN_consttime_swap工作的机制a是内存依赖推测。为了论证，让我们假设幼稚的内存依赖推测。

这个问题似乎归结为：

当处理器最终检测到BN_consttime_swap从内存中读取的代码（与推测相反，已写入函数内部）时，它是在检测到地址已被写入后立即取消推测执行，还是允许自己当它检测到已写入的值与已经存在的值相同时保留它？

在第一种情况下，BN_consttime_swap看起来它实现了完美的恒定时间。在第二种情况下，它只是尽力而为的常数时间：如果没有交换 bignums，则调用之后的代码的执行BN_consttime_swap速度将比交换它们时快得多。

即使在第二种情况下，这看起来也可以在可预见的未来（只要处理器保持足够幼稚）通过为两个 bignums 中的每一个的每个单词写入一个与两个可能的 final 不同的值来修复值之前再次写入旧值或新值。在某些时候可能需要使用volatile类型限定符以防止普通编译器过度优化序列，但听起来仍然可行。

注意：我知道商店转发，但商店转发只是一个捷径。它不会阻止在它应该之后的写入之前执行读取。在某些情况下它会失败，尽管在这种情况下人们不会期望它会失败。

AHashMap具有恒定的访问时间，但不允许重复。AnArrayList允许重复但没有固定的访问时间。

java中是否有允许恒定访问时间并允许重复的数据结构？

我知道我可以自己制作HashMap允许重复的，但我想使用已经存在的数据结构。

先感谢您。

列表的属性：

1. 大小必须为 N，其中 N 是整数的数量

2. 没有空单元格

3. 数字可能不是完全连续的（即 {-23,-15,-3,1,2,6,7,8,15,100}）

4. 插入/查找需要在恒定时间内。

我的第一个直觉是使用哈希表，但这会创建未使用的单元格，其中会跳过数字。

如果该列表中存在一个数字，是否可以构建这样的列表以检查恒定时间？

我有一段时间试图提出一个不违反 C/C++ 标准的恒定时间轮换。

问题是边缘/角落的情况，其中运算在算法中被调用并且这些算法无法更改。例如，以下来自Crypto++并在GCC ubsan（即）下执行测试工具g++ fsanitize=undefined：

和代码misc.h:637：

Intel 的 ICC 尤其无情，它把整个函数调用都去掉了，没有y %= sizeof(T)*8. 几年前我们修复了这个问题，但由于缺乏恒定的时间解决方案，将其他勘误保留在原地。

剩下一个痛点。什么时候y = 0，我得到一个条件 where 32 - y = 32，它设置了未定义的行为。如果我添加检查if(y == 0) ...，则代码无法满足恒定时间要求。

我查看了许多其他实现，从 Linux 内核到其他加密库。它们都包含相同的未定义行为，因此它似乎是一个死胡同。

如何以最少的指令在几乎恒定的时间内执行旋转？

编辑：通过接近恒定的时间，我的意思是避免分支，所以总是执行相同的指令。我不担心 CPU 微码计时。虽然分支预测在 x86/x64 上可能很好，但在其他平台上可能表现不佳，例如嵌入式。

如果GCC或Clang提供了在接近恒定的时间内执行旋转的内在函数，则不需要这些技巧。我什至会满足于“执行轮换”，因为他们甚至没有。

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

原始C代码是：

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

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

我目前使用

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

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

我需要在不使用 Java.Util 的 PriorityQueue 表单的情况下实现自定义优先级队列...我有三种基本方法：插入、删除和清除。所有操作必须在恒定时间 O (log n) 内完成。我怎样才能做到这一点？我应该为这些操作使用什么算法？最后，我应该使用什么类型的容器来保存通用值？

这是我到目前为止所做的......

不多..但帮助将不胜感激！

这是Nifi ExecuteScript 中 Import Modules 的后续

我是 python 和 nifi 的新手。我正在尝试在 ExecuteScript 处理器中执行我的 python 脚本。

我想访问服务器。所以我使用了 paramiko 客户端。但是当我运行处理器时，它在 session.write() 行显示“导入错误没有名为 constant_time 的模块”。虽然我在“/usr/local/lib/python2.7/dist-packages/”下有这个 constant_time.py

我在 sys.path 中也有路径“/usr/local/lib/python2.7/dist-packages/”。我还在“模块目录”属性中给出了这个路径。

这是我的代码：

任何帮助，将不胜感激。

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

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

我目前正在研究一种算法的实现，我想证明它可以在恒定时间内工作，即使有非常多的元素。

不幸的是，我需要一个数据结构来存储元素。当元素的数量非常多，但对于我的算法来说不是不合理的高时，std::vector 和 std::valarray 都不会在恒定时间内访问任意元素，如您在此图中看到的那样。

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