在線撲克如何作弊：一次軟件安全研究

        英文原文：How We Learned to Cheat at Online Poker: A Study in Software Security

        撲克是一種風靡世界的紙牌游戲，我們不僅可以在家中的餐桌上、賭場上、或者橋牌室中玩撲克，現在還可以在網上玩。我們研究可靠軟件技術的一些人 也玩撲克。因為我們現在都會花大量的時間在網上，所以將打撲克和可靠軟件技術研究結合在一起只是時間問題。我們將在線撲克游戲和軟件安全結合起來研究后， 發現一個巨大的安全漏洞，這就是本篇文章所要講的。

        人們可以在 PlanetPoker 這樣的互聯網橋牌室與其他人打德州撲克，這些游戲是實時的，而且用真錢。由于我們的主要工作是為公司提供安全、可靠且健壯的軟件，所以我們很好奇在線游戲 背后的軟件是什么樣的。它如何運行？是否公平？我們查看了 PlanetPoker 網站上的 FAQ 頁面，這個頁面包含它們的洗牌算法（為展現游戲公平性而公開洗牌算法，這還是很令人驚訝的），這些足以開始我們的分析了。當我們看到洗牌算法時，就開始懷 疑這其中可能有問題。一個小小的調查研究證明這種直覺是正確的。

        游戲

        在德州撲克中，每個玩家發兩張牌（稱作底牌）。最初的發牌后是一輪下注。第一輪下注結束后，接下來所有的發牌都是牌面朝上，所有玩家都可以看到 的。莊家在牌桌上發三張牌面朝上的牌（稱為翻牌），然后就是第二輪下注。德州撲克一般是定額下注，就是說每個玩家在每一輪下注都是定額。比如，在 3 美元到 6 美元的游戲中，前兩輪是 3 美元賭注，而第三輪和第四輪是 6 美元賭注。第二輪下注后，莊家在牌桌上再發一張牌面朝上的牌（稱為轉牌），然后就是第三輪下注。最后，莊家在牌桌上再發最后一張牌面朝上的牌（稱為河 牌），然后就是最后一輪下注。剩余的每個玩家使用自己手中的兩張底牌和牌桌上的五張公共牌，從這七張牌中選五張，湊成最大的組合。玩家湊成的成手牌的好壞 由標準撲克成手牌順序決定。

        德州撲克是一種快節奏的，令人興奮的游戲。這個游戲很重要的一個組成是虛張聲勢，并且玩家要對其他玩家持有的牌做快速判斷，這些判斷決定誰是最終的勝者。有趣的是，德州撲克還是每年在拉斯維加斯舉辦的世界撲克系列賽中的其中一項。

        既然現在每個人和他們的狗都是在線的，而且幾乎所有類型的業務都被呈現在互聯網上，那么在線賭場和橋牌室的出現就再自然不過了。雖然說要進賭場 的話，去印第安保留區和河船就很容易做到，但是更方便的參與游戲仍是現在的真實需求。如果能在自己家舒舒服服的上網娛樂（更別說可以穿著自己的睡衣），不 用忍受二手煙，以及那些令人討厭的玩家，這絕對是很吸引人的。

        安全風險無處不在

        所有的便利都伴隨著一定的代價。很不幸，玩在線撲克存在真正的風險。賭場本身可能就是一個騙局，其存在只是為了從玩家手上拿錢，它根本沒有打算 回報玩家任何勝局。運行在線賭場的服務器也可能被惡意攻擊者破解，以獲得信用卡號碼，或者嘗試在游戲中利用一些優勢。因為大多數賭場不對玩家的客戶端程序 和托管紙牌游戲的服務器之間的網絡流量進行認證和加密，可想而知，一個惡意玩家就可能檢查這些網絡流量（采用經典的中間人攻擊），以確定對手牌。這些風險 都是網絡安全專家非常熟悉的。

        串通也是一個撲克所獨有的問題（不同于其他游戲，如 21 點或擲骰子）。因為撲克玩家互相對抗，他們的對手并不是賭場本身。當一個桌子上的兩個或多個玩家互相串通時，他們作為一個團隊一起玩，往往會使用相同的資 金。互相串通的玩家知道他們團隊成員手上的牌（通常是通過細微的信號），而且他們為使團隊獲得最大的利益而下注，不管是團隊中的誰贏都行。串通在現實的橋 牌室中是一個問題，但對在線撲克來說，這個問題更嚴重。在線玩家可以使用即時通訊工具、電話會議聊天工具等，這使得串通問題成為一個嚴重的風險。如果一個 在線游戲的所有玩家都一起合作，來欺騙那些不質疑網絡安全的，容易受騙的玩家怎么辦？你怎么保證你永遠不會成為這些攻擊的受害者呢？

        最后也很重要的一個風險（特別是對本文而言），就是在線撲克軟件本身可能存在缺陷。軟件問題是引起安全風險的一種臭名昭著的形式，而且它常常被 過分相信防火墻和加密技術的公司所忽略。軟件應用程序會給一個系統帶來非常多的安全漏洞，我們每天都會花大量的時間來找出并解決這些軟件安全問題，所以我 們注意到在線撲克也是遲早的事。本文的其余部分就專門來討論我們在一個流行的在線撲克游戲中發現的軟件安全問題。

        軟件安全風險

        洗虛擬牌

        我們關注的第一個軟件缺陷涉及洗虛擬牌。公平洗牌意味著什么呢？本質上來說，它意味著牌的所有可能組合出現的概率相等，我們稱對這 52 張牌的每個排序為一次洗牌。

        對真實的一副牌，有 52!（約2^226）種不重復的洗牌。計算機洗一副虛擬牌時，它從這些可能的組合中選一種。現在有很多洗牌算法，一些算法優于其它，一些則是完全錯誤的。

        ASF 軟件公司開發的算法被大部分在線撲克游戲所使用。我們發現他們的洗牌算法有很多缺陷，根據這些發現，我們聯系了 ASF 公司，他們更改了他們的算法，但是我們還沒有看他們的新算法。從安全角度確保一切都完全正確并不容易啊（本文的其余部分將會介紹）。

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

procedure TDeck.Shuffle;var     ctr: Byte;
    tmp: Byte;

    random_number: Byte;
begin
    { Fill the deck with unique cards }
    for ctr := 1 to 52 do         Card[ctr] := ctr;

    { Generate a new seed based on the system clock }
    randomize;

    { Randomly rearrange each card }
    for ctr := 1 to 52 do begin
        random_number := random (51)+1;
        tmp := card[random_number];
        card[random_number] := card[ctr];
        card[ctr] := tmp;
    end;

    CurrentCard := 1;
    JustShuffled := True;
end;

        上面是 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：不要這樣洗牌

for (i is 1 to 3)
    Swap i with random position between i and 3

        圖 2 描述了我們所采用的洗牌算法，并且描繪了采用該算法生成所有可能的洗牌結果的樹。如果隨機數源設計良好的話，那么這棵樹中所有葉子出現的概率相等。

        即使只考慮這個小例子，我們就可以發現，該算法的洗牌結果不是等概率的。231、213、132 比 312、321、123 出現的更頻繁。如果你要對第一張牌下注，并且你知道上述這些洗牌結果的出現概率，你就會知道牌 2 比其它牌出現的概率大。而當一副牌的牌數增加時，這種概率不等現象會愈發被放大。當用上述算法洗 52 張牌時（n=52），洗牌的這種不均勻分布會造成某些手牌出現概率偏大，從而改變賠率。一些經驗豐富的玩家，他們專門研究賠率，然后就可以利用這種傾斜的 手牌概率來贏得賭博。

        圖3：可以這樣洗牌

for (i is 1 to 3)
    Swap i with random position between i and 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 ()函數實現

long long RandSeed = #### ;

unsigned long Random (long max)
{
     long long x ;
     double i ;
     unsigned long final ;
     x = 0xffffffff;
     x += 1 ;

     RandSeed *= ((long long)134775813);
     RandSeed += 1 ;
     RandSeed = RandSeed % x ;
     i = ((double) RandSeed) / (double)0xffffffff ;
     final = (long) (max * i) ;

     return (unsigned long) final;
}

        歷史經驗表明，隨機數生成器的種子通常是基于系統時鐘產生，也就是用系統時間的某些方面作為種子。這意味著，如果你知道生成器是基于哪個時間做 種子，你就知道生成器將會生成的所有數值（包括數字出現的順序）。這一切的結果是，偽隨機數完全可預知。毋庸置疑，這一事實對洗牌算法影響深遠。

        在玩撲克時，隨機數生成器是如何被錯誤使用的

        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!種洗牌結果，因為玩牌時只會用到很少部分的洗牌結果。然而算法產生的洗牌結果必須是均勻分布的，這非常重要。良好的分布確保在一次洗牌中，每張牌在 每個位置出現的概率基本相等。這個分布性要求相對容易實現和驗證。下面的偽代碼描述了一個簡單的洗牌算法，如果配上合適的隨機數生成器，該算法產生的洗牌 結果是均勻分布的。

START WITH FRESH DECK
GET RANDOM SEED
FOR CT = 1, WHILE CT <= 52, DO
X = RANDOM NUMBER BETWEEN CT AND 52 INCLUSIVE
SWAP DECK[CT] WITH DECK[X]

        這個算法成功的關鍵在于隨機數生成器（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 位偽隨機數生成器準備種子，有這兩點，足以使洗牌實現公平性以及安全性。實現一個公平的系統并非很難，在線撲克玩家有權提出這樣的要求。

        翻譯： 伯樂在線 - hf_cherish
        譯文鏈接： http://blog.jobbole.com/70736/