當隨機不夠隨機：一個在線撲克游戲的教訓

　　英文原文：When Random Isn't Random Enough: Lessons from an Online Poker Exploit

　　今天我要講一個發生于1999年，一個很流行的在線撲克平臺的開發者開發的洗牌軟件，帶有很微小但很致命的漏洞的故事。雖然這個故事已經15年了，但它給算法開發者帶來的教訓仍有重要意義。

　　在隨機數產生器或算法中，很容易出現一些微小的漏洞，但這些漏洞可能會導致災難性的結果。在線撲克和真正的撲克一樣，是以洗牌開始的。保證洗牌的隨機性尤為重要。

　　一副正常的牌有52張，并且各不相同，這樣就有52！，也就是8.0658×10^67種不同的洗牌方式。這是一個巨大的數字。

　　1999年，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;

　　錯誤1： 差一錯誤 

　　上述算法試圖遍歷所有牌，將每一張牌跟另外一張隨機選擇的牌進行交換。但是犯了每個程序員都犯過的錯誤——差一錯誤。函數random(n)返回一個0到n-1之間的隨機數，而不是程序員所想的1到n之間的。因此，這個算法中第52張牌永遠不會和他自己進行交換，也就是說第52張牌永遠不會停在第52個位置。這是隨機洗牌不夠隨機的第一個原因。

　　錯誤2：洗牌不均勻

　　上述算法將第i張牌和另外一張從整副也就是52張牌中隨機選擇的牌進行交換。而合適的洗牌算法應該只和第i到第n張牌中的一張進行交換。這是因為考慮到每一張牌應該只進行一次隨機交換。一副牌有n!種不同的排列，合適的洗牌算法應該只產生每種排列一次。原算法使一些排列出現的概率明顯高于另一些排列，是個不好的實現。 

　　錯誤3：32位種子

　　如果你的業務或技術依賴于隨機數的使用，最好的選擇是采用一個硬件隨機數產生器。ASF卻不是，他用了一個帶有偽隨機數產生器的確定機。更糟糕的是，他使用的是32位的種子。由于種子100%的決定了偽隨機數產生器的輸出，只有N^32種可能的種子值就意味著只有N^32種可能的打亂順序。所以在理論上有8.0658×10^67種打亂順序的情況下，他只有4百萬可能。

　　錯誤4：系統時鐘作為種子

　　上述算法使用Pascal函數Randomize()生成隨機數，而這個函數是根據從午夜開始的毫秒數來選擇種子的。由于一天之中只有86,400,000毫秒，也就意味著上述算法只能產生86,400,000種可能的亂序。

　　但更糟糕的是，由于隨機數產生器的種子是基于服務器時鐘的，黑客們只要將他們的程序與服務器時鐘同步就能夠將可能出現的亂序減少到只有200,000種。到那個時候一旦黑客知道5張牌，他就可以實時的對200,000種可能的亂序進行快速搜索，找到游戲中的那種。所以一旦黑客知道手中的兩張牌和3張公用牌，就可以猜出轉牌和河牌時會來什么牌，以及其他玩家的牌。（注：在德州撲克中，倒數第二張公共牌，叫“轉牌”，最后一張牌，叫“河牌”。）

　　以《算法》的作者Robert Sedgewick的一段話作為結束語：

“That’s a pretty tough thing to have happen if you’re implementing online poker. You might want to make sure that if you’re advertising that you’re doing a random shuffle that you go ahead and do so.”—Robert Sedgewick, Professor of Computer Science, Princeton

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈