扑克是一种风靡世界的纸牌游戏，我们不仅可以在家中的餐桌上、赌场上、或者桥牌室中玩扑克，现在还可以在网上玩。我们研究可靠软件技术的一些人也玩扑克。因为我们现在都会花大量的时间在网上，所以将打扑克和可靠软件技术研究结合在一起只是时间问题。我们将在线扑克游戏和软件安全结合起来研究后，发现一个巨大的安全漏洞，这就是本篇文章所要讲的。

人们可以在PlanetPoker这样的互联网桥牌室与其他人打德州扑克，这些游戏是实时的，而且用真钱。由于我们的主要工作是为公司提供安全、可靠且健壮的软件，所以我们很好奇在线游戏背后的软件是什么样的。它如何运行？是否公平？我们查看了PlanetPoker网站上的FAQ页面，这个页面包含它们的洗牌算法（为展现游戏公平性而公开洗牌算法，这还是很令人惊讶的），这些足以开始我们的分析了。当我们看到洗牌算法时，就开始怀疑这其中可能有问题。一个小小的调查研究证明这种直觉是正确的。

游戏

在德州扑克中，每个玩家发两张牌（称作底牌）。最初的发牌后是一轮下注。第一轮下注结束后，接下来所有的发牌都是牌面朝上，所有玩家都可以看到的。庄家在牌桌上发三张牌面朝上的牌（称为翻牌），然后就是第二轮下注。德州扑克一般是定额下注，就是说每个玩家在每一轮下注都是定额。比如，在3美元到6美元的游戏中，前两轮是3美元赌注，而第三轮和第四轮是6美元赌注。第二轮下注后，庄家在牌桌上再发一张牌面朝上的牌（称为转牌），然后就是第三轮下注。最后，庄家在牌桌上再发最后一张牌面朝上的牌（称为河牌），然后就是最后一轮下注。剩余的每个玩家使用自己手中的两张底牌和牌桌上的五张公共牌，从这七张牌中选五张，凑成最大的组合。玩家凑成的成手牌的好坏由标准扑克成手牌顺序决定。

德州扑克是一种快节奏的，令人兴奋的游戏。这个游戏很重要的一个组成是虚张声势，并且玩家要对其他玩家持有的牌做快速判断，这些判断决定谁是最终的胜者。有趣的是，德州扑克还是每年在拉斯维加斯举办的世界扑克系列赛中的其中一项。

既然现在每个人和他们的狗都是在线的，而且几乎所有类型的业务都被呈现在互联网上，那么在线赌场和桥牌室的出现就再自然不过了。虽然说要进赌场的话，去印第安保留区和河船就很容易做到，但是更方便的参与游戏仍是现在的真实需求。如果能在自己家舒舒服服的上网娱乐（更别说可以穿着自己的睡衣），不用忍受二手烟，以及那些令人讨厌的玩家，这绝对是很吸引人的。

安全风险无处不在

所有的便利都伴随着一定的代价。很不幸，玩在线扑克存在真正的风险。赌场本身可能就是一个骗局，其存在只是为了从玩家手上拿钱，它根本没有打算回报玩家任何胜局。运行在线赌场的服务器也可能被恶意攻击者破解，以获得信用卡号码，或者尝试在游戏中利用一些优势。因为大多数赌场不对玩家的客户端程序和托管纸牌游戏的服务器之间的网络流量进行认证和加密，可想而知，一个恶意玩家就可能检查这些网络流量（采用经典的中间人攻击），以确定对手牌。这些风险都是网络安全专家非常熟悉的。

串通也是一个扑克所独有的问题（不同于其他游戏，如21点或掷骰子）。因为扑克玩家互相对抗，他们的对手并不是赌场本身。当一个桌子上的两个或多个玩家互相串通时，他们作为一个团队一起玩，往往会使用相同的资金。互相串通的玩家知道他们团队成员手上的牌（通常是通过细微的信号），而且他们为使团队获得最大的利益而下注，不管是团队中的谁赢都行。串通在现实的桥牌室中是一个问题，但对在线扑克来说，这个问题更严重。在线玩家可以使用即时通讯工具、电话会议聊天工具等，这使得串通问题成为一个严重的风险。如果一个在线游戏的所有玩家都一起合作，来欺骗那些不质疑网络安全的，容易受骗的玩家怎么办？你怎么保证你永远不会成为这些攻击的受害者呢？

最后也很重要的一个风险（特别是对本文而言），就是在线扑克软件本身可能存在缺陷。软件问题是引起安全风险的一种臭名昭著的形式，而且它常常被过分相信防火墙和加密技术的公司所忽略。软件应用程序会给一个系统带来非常多的安全漏洞，我们每天都会花大量的时间来找出并解决这些软件安全问题，所以我们注意到在线扑克也是迟早的事。本文的其余部分就专门来讨论我们在一个流行的在线扑克游戏中发现的软件安全问题。

软件安全风险

洗虚拟牌

我们关注的第一个软件缺陷涉及洗虚拟牌。公平洗牌意味着什么呢？本质上来说，它意味着牌的所有可能组合出现的概率相等，我们称对这52张牌的每个排序为一次洗牌。

对真实的一副牌，有52!（约2^226）种不重复的洗牌。计算机洗一副虚拟牌时，它从这些可能的组合中选一种。现在有很多洗牌算法，一些算法优于其它，一些则是完全错误的。

ASF软件公司开发的算法被大部分在线扑克游戏所使用。我们发现他们的洗牌算法有很多缺陷，根据这些发现，我们联系了ASF公司，他们更改了他们的算法，但是我们还没有看他们的新算法。从安全角度确保一切都完全正确并不容易啊（本文的其余部分将会介绍）。

图表一：有缺陷的ASF洗牌算法

上面是ASF软件公司发布的洗牌算法，以使人们相信他们的计算机生成的洗牌是完全公平的。不过讽刺的是，这一举措对我们来说是完全相反的效果。

算法开始时先初始化一个数组，其值按顺序依次为1到52，代表52张可能的牌。然后程序用系统时间作种子，调用Randomize()初始化一个伪随机数发生器。实际的洗牌是通过依次将数组中的每个位置与一个随机选择的位置交换。这个随机选择的位置是通过调用伪随机数发生器选择的。

问题一：大小差一（Off-By-One）错误

精明的程序员就会发现，该算法包含一个大小差一（off-by-one）错误。该算法遍历初始的那副牌，将其每张牌与其它任意牌交换。然而和大多数Pascal函数不同，Random(n)函数实际上返回一个0到n-1的数字，而不是1到n。算法利用接下来的一小段代码来选择与当前牌交换的牌：这个公式设置一个值在1到51之间的随机数。总之，该算法从不选择最后一张牌与当前牌交换。当ctr最终指向最后一张牌，也就是第52张牌时，这张牌可以与任何其它牌交换，除了它自身。也就是说，这个洗牌算法从不允许第52张牌在洗牌结束后依然在第52个位置。这很明显违反了公平原则，不过很容易修复。

问题二：设计不良的洗牌分布

进一步考察该洗牌算法后，我们发现，即使不考虑大小差一（off-by-one）问题，该算法返回的洗牌结果也不是均匀分布的。该洗牌的核心基本算法如图2所示。

洗牌

进一步考察算法后发现，即使不考虑大小差一（off-by-one）错误，该算法返回的洗牌结果也不是均匀分布的。也就是说，一些洗牌结果出现的概率比其它洗牌结果出现的概率大。如果一个玩家知道这个漏洞，就可以在一个牌桌上坐很久，从而利用这种不均匀分布的优势。

我们用一个小例子来说明这种问题，这里我们采用上述洗牌算法来洗牌，这副牌只有三张（n=3）。

图2：不要这样洗牌

图2描述了我们所采用的洗牌算法，并且描绘了采用该算法生成所有可能的洗牌结果的树。如果随机数源设计良好的话，那么这棵树中所有叶子出现的概率相等。

即使只考虑这个小例子，我们就可以发现，该算法的洗牌结果不是等概率的。231、213、132比312、321、123出现的更频繁。如果你要对第一张牌下注，并且你知道上述这些洗牌结果的出现概率，你就会知道牌2比其它牌出现的概率大。而当一副牌的牌数增加时，这种概率不等现象会愈发被放大。当用上述算法洗52张牌时（n=52），洗牌的这种不均匀分布会造成某些手牌出现概率偏大，从而改变赔率。一些经验丰富的玩家，他们专门研究赔率，然后就可以利用这种倾斜的手牌概率来赢得赌博。

图3：可以这样洗牌

图3提供了一个更好的洗牌算法。它与上述算法的关键区别在于，遍历一副牌时，每张牌可能的交换位置减少了。同样，我们用三张牌的洗牌树来解释这个算法。和ASF提供的算法不同，该新算法将每张牌i与[i，n]中的某张牌交换，而不是[1，n]中的某张牌交换，从而将叶子数从3^3=27减少到了3!=6.这很重要，因为n!个不同的叶子意味着，所有可能的洗牌结果，新洗牌算法都会洗出一次，而且仅仅一次，从而每种洗牌结果出现的概率相等，这才是公平！

在确定性机器上生成随机数

我们讨论的第一组软件缺陷仅仅改变某些牌出现的概率，一些聪明的赌徒可以利用这种概率倾斜为自己创造优势，但是这种缺陷并不会完全破环这个系统。相比之下，这部分我们将要讨论的第三种缺陷，绝对是可以让在线扑克玩家完全妥协的“好东西”了。首先我们简短介绍伪随机数生成器，为下文奠定基础。

伪随机数生成器原理

假设我们要生成1到52之间的一个随机数，每个数字等概率出现。理想情况下，我们生成0到1之间的一个值，然后将这个值乘以52，其中每个值等概率出现，且不受前值影响。注意0到1之间有无穷多个数，但是计算机不提供无限精度。

为使计算机做到上述算法所描述的，伪随机数生成器通常产生一个从0到N之间的整数，然后用那个整数除以N，这样返回结果就总是0到1之间的数了。之后我们调用生成器时，它将第一次调用产生的整数结果传递给一个函数，这个函数生成一个0到N之间的新整数，然后返回新整数除以N的结果。这意味着，任何伪随机数生成器返回的唯一值的数目被限定为0到N之间整数的个数。而在大多数常见的随机数生成器中，N是2^32（约40亿），也就是32位数的最大值。换句话说，这种生成器最多能产生40亿个可能的值。扳起手指数一数也知道，40亿不算多。

开始要给伪随机数生成器提供一个种子，作为初始的整数，将其传递给那个函数。种子是生成随机数字序列的开端。要注意，伪随机数生成器的输出是完全可预测的，它返回的每个值都完全由其先前返回的值决定（最终，由种子决定，即种子是一切的开始）。如果我们知道用于计算任意一个值的那个整数，那么生成器后续给出的所有值都是可知的。

图4是宝蓝（Borland）编译器提供的伪随机数生成器，它就是一个很好的例子。如果我们知道RandSeed的当前值为12345，那么它产生的下一个整数是1655067934，然后其返回值将是20.由于计算机是完全确定性的机器，所以事情总是如此。

图4：宝蓝的Random()函数实现

历史经验表明，随机数生成器的种子通常是基于系统时钟产生，也就是用系统时间的某些方面作为种子。这意味着，如果你知道生成器是基于哪个时间做种子，你就知道生成器将会生成的所有数值（包括数字出现的顺序）。这一切的结果是，伪随机数完全可预知。毋庸置疑，这一事实对洗牌算法影响深远。

在玩扑克时，随机数生成器是如何被错误使用的

ASF软件使用的洗牌算法总是开始于一副有序的牌，然后生成一个随机数序列，用于重排那副牌。回想一下，一副真正的扑克牌有52!（约2^226）种各不相同的洗牌结果，而一个32位随机数生成器的种子必须是一个32位数，也就是只有40多亿个可能的种子。而每次洗牌前，都会对牌以及生成器种子初始化，所以该算法只能产生40多亿个可能的洗牌结果，而40多亿要远远小于52!.

更糟的是，图一所示的算法采用Pascal函数Randomize()为随机数生成器选择种子。Randomize()函数基于午夜开始的毫秒数选择种子，一天只有86,400,000毫秒。因为这些数字被用作生成器的种子，从而可能的洗牌结果缩减为86,400,000个。八千六百万要远远小于40亿，但这还不是最糟的。

破坏系统

了解系统时钟种子后，我们有一个想法，可以把洗牌结果数目减少的更多。通过将我们的程序与生成伪随机数的服务器系统时钟同步，我们可以将可能的组合数降至200,000之后，这个系统就是我们的了，因为搜索这么小的洗牌结果集完全不在话下，在PC上就可以实时完成。

RST攻击本身要求这副牌中的5张牌已知，基于这5张已知牌，我们的程序搜索那几十万个洗牌结果集，然后推导出完美匹配的一个。在德州扑克这个案例中，我们的程序将作弊玩家的两张底牌以及前三张翻牌（公共牌）作为输入。这五张牌在第一轮下注后就全部已知了，有这些信息就足以让我们在比赛中实时确定准确的洗牌结果。图5是我们为攻击粗粗设计的GUI。左上角的“Site Parameters“框用于同步时钟，右上角的”Game Parameters“用于输入5张牌，并初始化搜索。图5是所有的牌都被程序确定后的一张截图。我们现在知道谁拿了什么牌，以及剩余的翻牌值，还有谁会提前赢。

图5：攻击的图形用户界面GUI

一旦知道5张牌，我们的程序就开始不断的生成洗牌，直到那个洗牌中包含这5张牌，并且顺序也一样。由于Randomize()函数基于服务器的系统时间，因此在合理精度内猜对开始的种子并不难（猜得越接近，需要搜索的洗牌结果数就越少）。然而最棒的是这个，一旦找到一个正确的种子，就有可能在几秒钟内将我们的攻击程序与服务器同步。这种事后同步允许我们的程序不到1秒就确定随机数生成器使用的种子，以及接下来游戏将要使用的所有的洗牌。

除了技术细节，我们的攻击也被很多新闻媒体所报道，这种媒体覆盖也体现了这个发现人性的一面。登陆我们的网站Web site ，可以看到我们最初的发布稿 original press release，CNN视频剪辑，还有纽约时报的一个故事。

洗虚拟牌的正确做法

正如我们所见，洗虚拟牌乍看容易，其实不然。要写洗牌算法，最好的方法是，基于扎实的数学基础开发一种可以安全地产生良好的洗牌的技术。此外，我们认为发布一个好算法，并允许被大家审查，是一个很不错的想法（这与开源狂热者的观点不谋而合），关键是不能置安全性于模糊状态。像ASF一样发布一个差算法并不好，但不发布这样的差算法也不好！

密码学基于坚实的数学基础开发健壮的算法，用于保护个人、政府和商业机密，而不是基于模糊的理论。洗牌也一样，我们可以将加密密钥的长度与随机种子的规模做类比，其中，加密密钥的长度直接关系到很多加密算法的强度。

开发一个洗牌算法相当简单。首先要清楚，算法不需要能产生52!种洗牌结果，因为玩牌时只会用到很少部分的洗牌结果。然而算法产生的洗牌结果必须是均匀分布的，这非常重要。良好的分布确保在一次洗牌中，每张牌在每个位置出现的概率基本相等。这个分布性要求相对容易实现和验证。下面的伪代码描述了一个简单的洗牌算法，如果配上合适的随机数生成器，该算法产生的洗牌结果是均匀分布的。

这个算法成功的关键在于随机数生成器（RNG）的选择。RNG直接影响上述算法能否成功的产生均匀分布的洗牌，以及这些洗牌能否用于安全的在线牌类游戏。首先，RNG本身必须产生均匀分布的随机数。一些伪随机数生成器（PRNG）已经被证明具有此数学属性，比如基于Lehmer算法的伪随机数生成器。这些好的PRNG足以用于生成洗牌时的“随机“数。

正如我们所见，初始种子的选择是成功与否的关键。所有的事情最终都归结于种子。因此，玩家在玩由PRNG生成的洗牌时，无法确定生成该副洗牌所使用的种子，这一点至关重要。

要确定生成特定洗牌所使用的种子，一种蛮力做法是，系统地遍历所有可能的种子，生成相应的洗牌序列，并将其与待寻找的洗牌序列对比。为避免这种攻击，可用的种子数一定要多，使得在特定时间限制内，执行穷举搜索不可行。但是要注意，找到一个匹配的洗牌平均只需搜索一半的种子空间。而对于在线扑克，特定时间限制应该是一场游戏的时长，这个时长通常以分钟计。

根据我们的经验，运行在奔腾400计算机上的简单程序，可以每分钟检查大约200万个种子。按照这个速度，这个机器对32位种子空间（约2^32个可能的种子）的穷举搜索需一天多一点。尽管这个时长必然超过我们规定的那个时间限制，但是如果利用计算机网络执行分布式搜索，那么在我们的时间限制内完成搜索是完全可能的。

我们讲蛮力攻击主要是想强调加密密钥长度与洗牌使用的种子之间的相似性。暴力破解密码攻击要尝试每个可能的密钥，以破解加密信息。同样，蛮力攻击洗牌算法也要检查所有可能的种子。有关加密密钥的长度，目前已有一个重大的研究发现。总体而言，该研究是这样的：

人们以前认为实时破解56位的数据加密算法（DES）不可行，但事实并非如此。1997年1月，一个保密的DES密钥在96天内被找到。之后，又做到41天内破解，然后是56小时，然后是1999年1月，在22小时15分钟内破解。对短的密钥长度或者小的种子集来说，这种破解能力的飞跃发展当然不是好兆头。

人们甚至还发明了专门的机器，用于破解加密算法。1998年，电子前沿基金会EFF就制造了一个专用机，用于破解DES信息。制造这个机器的目的在于强调DES是多么不堪一击（DES是一种流行的、政府认可的算法，要深入了解DES攻击，请点击 http://www.eff.org/descracker/ ）。DES之所以易于被破解，与其密钥长度直接相关。由此可见，制造专用于破解RNG种子的机器也并非不可能啊。

我们认为32位的种子空间不足以对抗猛烈的蛮力攻击，但是64位的种子空间应该足以抵抗几乎所有的蛮力攻击。因为现在很多计算机都支持64位整数，所以使用64位的种子就很有必要了，而且一个64位数应该足以避免洗牌时遭受蛮力攻击。

单单用64位还不行。我们决不能断定攻击者肯定无法预测或估计PRNG使用的种子。如果他们有方法预测种子，那么上述蛮力攻击的计算压力就变得无关紧要了，因为相比而言，此时破坏整个系统还要容易的多。我们利用的漏洞，不仅仅是ASF的缺陷算法采用很小的32位的PRNG，还有该方法的种子依赖于一天之中的时间。我们已经证明，这种算法基本无随机性可言。

总结分析一下，整个系统的安全依赖于选择一个不可预测的随机种子，要实现这样的选择，最好是采用基于硬件的技术。基于硬件的方法从物理环境直接拿到不可预测的随机数据。由于在线扑克等涉及真钱交易的游戏，都对安全性要求至高，所以有必要进行一些投资，以确保随机数生成器正确完成。

总而言之，开发一个好的洗牌算法，并且采用经过验证的硬件设备为64位伪随机数生成器准备种子，有这两点，足以使洗牌实现公平性以及安全性。实现一个公平的系统并非很难，在线扑克玩家有权提出这样的要求。