(在线)扑克是否需要加密安全的随机性?

信息安全 随机的
2021-08-11 18:01:30

这是来自 reddit 讨论的引述

……对于扑克 [一个加密安全的 RNG] 是完全没有必要的。如果你有一个适当的不可预测的种子,并且你丢弃了很多随机性,那么 MT 是完全安全的。

我通常会将此视为无知,但这种情况仍在继续:

我实际上已经实现了一个真钱扑克后端,公司甚至还对其进行了认证

而且由于没有人在互联网上撒谎,这让我想知道。所述人在讨论的另一部分对此进行了扩展

[为了防止可预测性],您不会使用 [MT 生成器] 生成的 624 个连续值。如果你想要一个真钱应用程序。通过认证,标准之一是丢弃大量且不可预测的 PRNG 输出。

您也不知道如何使用 PRNG 来产生 shuffle 的细节。因此,您无法将您在桌子上看到的牌映射到 PRNG 中的序列。

您也不知道何时重新播种 PRNG。

最后一件事。您需要存储 (2 19937 − 1) * 4 字节的数据进行查找,以便找到您需要预测的模式。

除了最后一段,这些论点听起来很可疑,就像默默无闻的安全。最后一段听起来不那么重要,但讨论中的其他人声称该陈述是不真实的,您不需要这么大的查找表。

澄清一下,我知道 MT19937 在密码学上并不安全(我引用的人也是如此)。然而,到目前为止,我的假设是赌博(和扑克)需要一个加密安全的随机源——而不仅仅是一个安全的种子——(a)防篡改,(b)用于认证。这是错的吗?

3个回答

这是密码学家的观点。你引用的人:“你不需要加密安全的 PRNG”,但他实际上声称的是“当我使用 MT 19937 并做一些笨拙的事情时,比如扔掉大部分输出,它不知何故变成了加密安全的 PRNG”。

他关于存储“(2 19337 -1)*4 字节以供查找”的评论足以证明他对安全性、密码学​​、随机性和不可预测性究竟是什么的头脑不是很清楚。这个数字就是“周期”;该时期在(非常)较早的时期被用作安全措施,因为从那时起已知的 PRNG 有非常小的时期,以至于在实践中确实发生了重复。这产生了整个非加密 PRNG 家族,设计师们试图通过尽可能长的繁荣期来威慑竞争对手。从密码学的角度来看,这没有真正的意义。PRNG 的安全性与不可预测性有关, 一个非常短的时期是一个问题,只是因为它允许未来的输出是可预测的。CTR 模式下使用的 AES 是一个周期为 2 135(位)的 PRNG,这个数字远低于 2 19337 -1,但根本不是问题。

“丢弃大量且不可预测的产出”也说明了这种混乱。从输出中删除位可能会隐藏一些弱 PRNG 的状态泄漏;这甚至可以将一个弱 PRNG 变成一个强 PRNG,正如使用收缩生成器所研究的那样。但是,它对种子的可预测性没有任何作用;实际上,如果某些输出被“丢弃”,那么有一个机制决定保留什么以及丢弃什么,并且该机制也是 PRNG 的一部分。如果所有这些都是当前时间的种子,那么对可能的“当前时间”值进行详尽搜索是有效的(当前时间不是秘密)并且解开整个事情。


然而,我们可能会争辩说,尽管 MT 在密码学上并不安全,但这并不意味着进行有效的攻击很容易PRNG 分为三种类型:

  • 非常弱的算法,要么通过非常糟糕的处理(泄漏内部状态),要么通过可预测的种子,或两者兼而有之。这些在实践中被打破了。
  • “密码学强” PRNG,即使在学术界假设的荒谬条件下也能抵抗攻击(如果算法声称 128 位安全性但仅提供 2 123.4抵抗力,学者会认为该算法“已损坏”)。
  • 介于两者之间的灰色地带:按照学者的说法,已被打破,但实际攻击不是立即的。

凭借他的Mersenne Twister,他处于灰色地带,他相信他的巫术操纵将保持这种状态。他也可以说服审计师相信伏都教有效,这完全有可能。这绝不意味着该算法是安全的;只是审计员准备签署一份文件,声称该算法符合某些法律要求。在这一点上,记住其他一些审计师发现签署文件声称安然是一家财务健全和廉洁的企业是一件好事:这有助于将事情放在正确的角度。

根据他的描述,最初的种子很可能是基于时间的,而实际的安全性完全依赖于算法细节的不公开。这是最好的(或最坏的,取决于观点)默默无闻的安全性。

首先,有一件非常重要的事情:当我们说“必需”时,您是什么意思?游戏本身(在线扑克)并不真正需要那种级别的随机性。您可能可以摆脱普通的 old rand()

但是,合法和受监管的在线扑克游戏需要遵循一定的规则,其中之一就是 RNG 应该由独立的审计公司进行审计。英国就是这种情况。世界上许多地方的审计公司(普华永道安永CigitalGaming Laboratories International)和监管机构(Kahnawake Gaming Commission)都曾处理过此类案件,并且通常确实会处理此类案件。

此类审计公司和监管机构要求 RNG 具有非常高的随机性、公正性和不可预测性。现在,我们知道哪些 RNG 易于实施和使用,并且适合此类法规?好吧,你猜对了;你的好人值得信赖的CSPRNG

正如@Ladadadada 所提到的,除了法规和法律之外,让游戏尽可能公平符合游戏运营商的最大利益,因为不公平和“可破解性”会将用户赶走。因此,为了达到这种公平水平,您需要 CSPRNG 提供的高质量随机性和不可预测性。

通过快速的 Google 会话,您会发现几个经过高度测试、审查和审查的 CSPRNG,可以按原样使用,并用于您的在线扑克项目。

当他说 CSRNG “完全没有必要”时,这个人是错误的。当他说你需要一颗“不可预测的种子”时,他甚至证实了这一点。

什么是不可预测的种子?

当我给你从那个种子派生的合理数量的伪随机数时,你将无法计算下一个数字。简单的。从数学的角度来看,这种生成器的安全性可以通过一个简单的游戏来证明。

我发给你一个数字序列,你必须决定它们是完全随机的还是由函数 (F) 派生的。如果您的平均成功率高于一半(+/- 微不足道的数量),您就赢了。

你会发现你获胜的机会(至少)取决于函数获得的输入量。如果我只使用几位输入,那么您肯定可以区分完全随机性和函数输出,而不是一半。

到目前为止,没有办法绕过好种子。魔法扔掉怎么办

丢弃一些输出是否会使其更安全?

我觉得“扔掉大量不可预测的数量”的说法有点滑稽。他们在这里所做的是跳过函数输出的部分内容。但是到底有多少字节呢?他说“数量巨大且不可预测”。这基本上意味着您从上面修改函数。

但是,您仍处于开始的位置。您玩游戏并尝试区分完全随机性和新函数 (F') 的输出。毕竟有一个算法正在运行,它必须准确地决定要跳过多少字节。所以这个值是通过某种方式计算出来的,可以看作是原始函数的附加部分。

你可以做什么?

如您所见,丢弃不可预测的输出量并不会使函数更安全。相反,如果您选择丢弃完全随机数量的字节,则此colud会导致更安全的算法。

如果算法输出位 0101010101... 等等,您赢得比赛的机会就很大。如果我跳过随机数量的输出并发送给您一位,然后再次跳过另一数量并发送给您一位,依此类推,会是什么?您获胜的机会是您预测跳过位数量的机会。最后你必须预测随机性,你获胜的机会将不再那么好。

但是,我的数字生成器的安全性得益于仅在某些条件下跳过,其评估将超出此线程。只是为了得到正确的印象:如果我的函数在 99% 的时间输出位“1”而仅在 1% 的时间输出“0”,那么跳过会带来什么?您会发现,即使我跳过随机数量的位,统计分布仍然是恒定的。

结论

你肯定会想要扑克游戏中的真正随机性,用于种子或输出的跳过或两者兼而有之。但是,将这种昂贵的随机性用作作为 CSPRNG 工作的明确定义的函数的输入就足够了。

仅作记录:您可以使用加密原语创建这样的函数,该函数可以承受所有提到的测试,如果您知道密钥,则序列是可预测的。在不知道密钥的情况下,它看起来如此随机,以至于您赢得游戏的机会大约是一半。