在这篇文章中，我们发现了一个奇怪的生物叫模偏差，了解它是如何诞生的，为什么它如此危险，以及如何对抗它。

永久的发现

在过去的3年里，我做了无数的代码审查，如果有一个漏洞，我不断看到一遍又一遍，那肯定是模偏差。例如，c语言ddos防御软件，我最近在做一个审计，在代码库中对模运算符做了一个简单的搜索，得到了3个结果…好吧，猜猜怎么着？其中两个引入了模偏差，但这些都在测试文件中，这本身可以说不是问题。但最后一个是引入了一个实际的模偏差，这可能会破坏人们对所述代码库的信任，因为它会产生有偏差的结果。我并不是说我看到的所有模运算都引入了模偏差，但它们确实太频繁了。

遗憾的是，每次我想给某人发一个链接来解释清楚，以及如何避免它，我发现自己在网上四处寻找都无济于事。关于这个主题的文档的稀缺性仍然让我感到惊讶，特别是当我想到有多少次听说模偏差并在野外看到它时。

正如我们将看到的，模偏差的一个大问题是，它们可以让你恢复某些方案的私钥，包括比特币中使用的方案，以太坊和许多其他区块链，或由制造商签署其固件！

那么，让我们这样做：

模？

首先，我们需要讨论什么是模。模运算在密码学中被大量使用，因为我们通常处理的是以模运算为核心的数论和代数结构。但它在计算机科学中的应用也更为广泛。它通常在代码中用符号%表示，它是一个二进制运算符，将两个整数作为输入，一个整数作为输出。我们在代码中所知道的模是计算整数a除以整数b的余数。也就是说：对于可能的最大值，那么a%b==r，我们读作"模b等于r"，其中r是a除以b的其余部分。说实话，数学中定义的模是定义在整数环上的等价关系，它表示两个整数，是等价的模（即，在同一等价类中）当且仅当差可被整除。但是我们不需要关心我们的典型的模用法的等价类，我们将只考虑我们通常使用的编程语言中的模。不管怎样，ddos攻击犯怎么防御，它与数学定义是相容的，即使不是严格等价的。）

关于模的说明，以及它们在计算机科学中的基础，是在DonaldE。克努斯的"基本算法"（第三版），"计算机编程艺术"的第一卷。在那里，它是用"地板"和"除法"的概念来定义的，这两个概念共同构成了我们在编程中所拥有的所谓的"整数除法"。具体定义如下：

如果和是实数，我们定义如下二进制运算：donalde。"基本算法"中的Knuth

偏差？

那么它是什么意思，模偏差？当你必须随机选取一个整数时，问题就出现了，通常你想要选取给定范围内的整数，但是你想要整数在给定范围内均匀分布。例如，如果您的范围是[0，106]，那么您希望0和106之间的所有值（包括0和106）都尽可能相似，因此获得107个值中任何一个值的概率是这样的，但是，在生成随机值时，通常会得到一个随机字节字符串。通常依赖于GetRandom或/dev/urandom，这两者都将为您提供一组随机字节数。所以在这个例子中，随机抽取1个字节就足够了，因为8位可以代表255个值。但是你需要一种方法来限制你的随机字节只有0到106的值，这通常是模被误用并导致模偏差的地方：你的随机字节，一旦被转换成整数，它的值将在0到255之间，因此人们可能会倾向于取模107的值，因为这样你就可以得到一个0到106之间的值，因为107会被映射到0，108到1，等等，并显示值分布：

12345import pandasimport os s=pandas.DataFrame（{'value'：list（os.urandom（1000000））}）s['value'].value\u counts（）.sort\u index（）.plot（figsize=（20,5），kind='bar'）

按值出现的次数

这些值看起来均匀分布在255个可能的值上，这是随机数发生器的预期结果。那么模107的随机值的分布呢？

12345import pandasimport os s=pandas.DataFrame（{value'：[x%107 for x in os.urandom（1000000）]}）s['value'].value\u counts（）.sort\u index（）.plot（figsize=（20,5），kind='bar'）

按值出现的次数

您可以看到模在最低的42个值上引入了偏差！为什么会有这些价值观？很简单，因为随机值最初是在0到255之间采样的，因为我们取的是1字节的随机数据。所以从0到213的所有值都被映射到范围，每个结果模107出现两次（），但是从214到255的值只被映射到范围…这意味着在模运算之后，后一个范围和它的42个值出现了3次，而如果你要将所有的数字从0减少到255模107，这些值只出现了两次。这实际上是由于107不能平均除以256造成的。

这个问题基本上和你把绳子切成给定尺寸的小块时是一样的：最后一个一根绳子的大小很可能与其他绳子不同，除非绳子的初始长度完全除以绳子的长度。

这种偏差的危险

现在，我们一开始采样的值是随机的，我们将其模化，但最终结果仍然是随机的…当然，带ddos防御的国外服务器，前42个值更有可能，但我们真的需要一个完全均匀的随机值分布吗？你仍然很难预测一个随机的32字节整数模128位整数的归约结果，因为有太多的可能性，你不觉得吗？

好吧，是和否！是的，一个人无法预测它，是的，如果你用这个方法生成一个nonce，你的nonce仍然有绝对的机会是独一无二的。但是没有！您不应该依赖这些声明，因为即使对256位nonce值有1位的偏差也足以攻击某些加密方案！

一般来说，偏差对于以下（有些相关）方案是极其危险的：

（EC）DSA签名方案需要均匀分布的nonce作为其值，利用偏差nonce的攻击自1999年以来就为人所知，并且在实践中多次用于ECDSA（臭名昭著的PS3 hack，偏差nonce Sense，例如，最近的LadderLeak论文提出了一种针对ECDSA的私钥恢复攻击，"不到1位的nonce泄漏"，这基本上意味着有可能发生泄漏，你猜怎么着？非均匀分布可视为泄漏：在我们的示例中，较低的5位被设置的几率高于其他位。是的，你读对了：如果现在的任何一位有点可预测，只要你能收集到足够的有偏签名，你就可以破坏（EC）DSA。

针对这些方案的攻击通常依赖于隐藏数问题（HNP，它在33年前的Crypto'86中就已经被引入了），并且经常使用格表示来解决，在格表示中，人们可以解决最近的（或最短的）向量问题来获得解决方案，或者使用FFT进行统计攻击，例如Bleichenbacher攻击。这些攻击背后的想法是，你有一个nonce泄漏，你可以通过收集足够的"泄漏签名"（注意，模偏差可以被视为某些位值的概率泄漏）来利用它来构造一个隐藏数问题，其解决方案通常允许你恢复方案中使用的私钥。这是公钥方案可能出现的最坏情况(有趣的是，其他方案（如Pedersen承诺）对模偏差不敏感，因为它们不依赖于重用私钥。）请注意，如果要获得旁道泄漏，则可以以相同的方式执行这些攻击，该旁道泄漏允许您获得有关生成的nonce的一些信息，即使这些信息是正确生成的。我们在这里只讨论了一种情况，抗ddos攻击防御系统，即nonce没有正确生成，模偏差允许利用它们，但请记住，这并不是唯一的威胁，这取决于你的威胁模型。

通常情况下，偏见"只是"减少了随机生成值的实际熵，因此不像上述方案那样危险，但未来密码分析的突破可能会利用它们。因此，我们确实更喜欢均匀分布的随机值，而且当我们有一个随机值时，它们通常也允许我们真正依赖于安全性的数学证明。

这里还有趣地注意到，网络游戏ddos防御，关于这个主题的唯一维基百科条目可以在Fisher–Yates shuffle（又名Knuth shuffle）的文章中找到，因为这种洗牌需要在洗牌过程中均匀地随机选取一些索引。如果你在那里引入模偏差，你会得到一个有偏差的洗牌…这可能对你的电子投票解决方案、混合网络或在线彩票代码非常不利，这取决于你在哪里使用这种洗牌。

避免模偏差

有不同的方法来避免模偏差和获得无偏差，均匀分布随机整数