Wydarzenia, które doprowadziły do dzisiejszego wpisu miały miejsce mniej więcej siedemnaście lat temu, w 1999 roku. Historia jest bardzo popularna w świecie pokerowym, była już wiele razy opisywana na różnych forach i blogach - dziś czas na mnie. Lepiej późno niż wcale 😉
Przypuszczam, że wiesz, sympatyczny Czytelniku, czym jest poker. Jeżeli tak, wiesz też, że jest to gra karciana, w którą gra się pełną talią (52 karty), bez jokerów.
Poker jest grą bardzo popularną. Istnieje mnóstwo jego odmian (między innymi popularny w Polsce Cantrell Draw, od którego większość ludków zaczyna swoją przygodę z grą). Najpopularniejszym wariantem jest Texas Hold'em, grany przez miliony ludzi na całym świecie.
Osobiście lubię obydwie odmiany: Texas Hold'em, bo jest popularny i solidnie przemyślany, a Cantrell Draw, bo grałem weń sporo za gówniarza i darzę go zwykłym, ludzkim sentymentem (a także, ponieważ wbrew obiegowej opinii wcale nie jest tak "prymitywny", za jakiego się go tu i ówdzie uważa).
Niezależnie jednak od tego, w którą odmianę pokera gramy, każde rozdanie rozpoczyna się od potasowania kart.
Od razu uprzedzam Czytelników o ciągotach fizykochemicznych, iż nie chodzi nam tu o traktowanie kart potasem (ani żadnym jego związkiem), tylko o wymieszanie talii w sposób możliwie losowy.
W pokera można grać przy stole - takim prawdziwym, z nogami, blatem, kotem ocierającym się o łydkę i śladem po maczecie (stryj Zenon przegrał w 2012 sosjerkę, na szczęście palec wuja Antoniego udało się przyszyć na pogotowiu).
Można też grać w pokera on-line, co ma swoje zalety: przede wszystkim łatwiej znaleźć chętnych do gry o każdej porze dnia i nocy, oszczędza się również trochę czasu i wysiłku przy tasowaniu, zapamiętywaniu kto jest w danej rundzie BB i SB i liczeniu żetonów - wszystko robi się "samo". No i mniejsze ryzyko, że wzburzony przebiegiem rozgrywki oponent zechce dokonać przekształceń własnościowych na naszych kończynach czy innych członkach.
No właśnie. Tasowanie. W wersji on-line to również robi się "samo" - specjalny algorytm miesza karty przed każdym rozdaniem, zapewniając wysokiej jakości losowość, brak możliwości przewidzenia jaka karta będzie następna i tak dalej. Współczesne systemy pokerowe są tak pozabezpieczane, że nawet sama gra "nie wie" jaka karta znajduje się na szczycie talii - jest ona bowiem losowana dopiero w momencie, kiedy zachodzi potrzeba jej użycia. Tym samym jeżeli ktoś włamałby się do serwera, na którym odbywa się partia w wirtualnego pokera, i nawet jeżeli uzyskałby prawa administratora (czy roota - jak zwał tak zwał), nie byłby w stanie odczytać karty leżącej na szczycie "kupki", ponieważ tej karty jeszcze "nie ma". Coś jakby kot Schroedingera, tylko z zerowym odsetkiem martwych futrzaków (nie mylić z Futrakami!).
Jednak siedemnaście lat temu sprawy wyglądały nieco inaczej.
Pewna znana firma udostępniała wówczas większości dużych portali pokerowych swoje algorytmy związane z obsługą gry. A wśród nich algorytm tasujący.
Niestety, algorytm pisali ludzie. A - jak mawiali starożytni - errare ludzium est. Czy coś.
Grube pomyłki są łatwe do wyłapania i szybkiej korekty. Natomiast pomyłki subtelne... No cóż. Bywają bolesne.
W tym konkretnym przypadku kilka drobnych pomyłek skumulowało się w jedną katastrofalną całość.
Kwestią dyskusyjną był już sam wybór algorytm tasującego. Sposobów na "uczciwe" potasowanie talii jest całkiem sporo. Można na przykład zrobić tak: niepotasowane karty ponumerować od jeden do 52, następnie wylosować jedną z nich (innymi słowy: losujemy liczbę z przedziału 1-52), odłożyć ją do talii potasowanej, powtarzać aż do wyczerpania puli kart niepotasowanych. W efekcie dostaniemy "uczciwie" potasowaną talię, oczywiście przy założeniu, że losowość użyta do wybierania kolejnych kart również będzie "uczciwa". Algorytm jest niezbyt szybki - wymaga bowiem wielokrotnego numerowania kart - ale działa. Jest dużo innych, bardziej wydajnych sposobów.
Natomiast algorytm tasujący naszej niesławnej firmy działał tak: wybierał dwie losowe karty i zamieniał je miejscami - i tak określoną (zawsze taką samą) ilość razy.
Pozornie nie ma w takim podejściu niczego złego. Jednak szczegółowe analizy dowodzą, że prowadzi ono do nieco "skrzywionej" dystrybucji możliwych potasowań talii. "Skrzywienie" owo jest nieznaczne, ale jest. Powoduje, że niektóre potasowania są bardziej prawdopodobne od innych. A w pokerze on-line tasowanie musi być zrobione naprawdę porządnie.
To jednak mogłoby jeszcze przejść niezauważone.
Niestety, programiści popełnili cztery kolejne błędy. Każdy z nich z osobna byłby prawdopodobnie niegroźny, ale ich kombinacja doprowadziła do tego, do czego doprowadziła.
Po pierwsze programiści użyli deterministycznego generatora liczb pseudolosowych. Jeżeli ktoś sądzi, że poprzednie zdanie jest sprzeczne logicznie, spieszę wyjaśnić, że nie do końca. Losowość w komputerze jest dość trudna do uzyskania - trzeba sięgać po zewnętrzne jej źródła: jakiś termometr, jakiś generator białego szumu, albo trzeba poprosić użytkownika, żeby poruszał myszą. Bez tego wszystkiego komputer nie ma skąd wziąć losowych bitów (stąd przedrostek "pseudo" w nazwie "generator liczb pseudolosowych") - i musi je powyliczać, a to prowadzi do tego, że zaczynając od danej wartości otrzymamy każdorazowo tę samą sekwencję.
Po drugie liczba początkowa sekwencji pseudolosowej była wartością 32-bitową. Ilość możliwych potasowań talii 52-bitowej wynosi \(\pi\) x oko \(8 * 10^{67}\). To jest astronomicznie wielka liczba - jeżeli "porządnie" potasujesz talię kart, szanse na to, że ktoś kiedykolwiek, gdziekolwiek (w całym Kosmosie) uzyska takie samo wymieszanie jest praktycznie zerowa.
Tymczasem jednak ponieważ użyto generatora pseudolosowego, którego wartość początkowa była 32-bitowa, ilość możliwych kombinacji spadła drastycznie: z \(8*10^{67}\) do zaledwie \(2^{32}\) (czyli trochę ponad cztery miliardy).
Oczywiście gdyby zastosować zmienną 64-bitową, wówczas zamiast czterech miliardów z hakiem zwiększylibyśmy ilość dostępnych potasowań do mniej więcej \(1.8*10^{19}\), co w dalszym ciągu jest niewyobrażalnie małym ułamkiem z \(8*10^{67}\), ale byłoby o wiele trudniejsze do wykorzystania przez hakerów.
Trzecim błędem był sposób inicjalizacji pierwszego elementu sekwencji: zamiast skorzystać z faktycznej losowości analogowego świata na zewnątrz komputera, algorytm wybierał pierwszy element sekwencji używając wbudowanego w komputer "zegarka". Zegarka, który "tyka" z dokładnością do jednej milisekundy. Doba ma 24 godziny, czyli 1440 minut, czyli 86400 sekund, czyli 86400000 milisekund. Niecałe osiemdziesiąt sześć i pół miliona - to o dwa rzędy wielkości mniej, niż (już okrutnie okrojone) cztery i trzy dziesiąte miliarda z poprzedniego błędu. To już prawdziwa gratka dla ewentualnego kombinatora.
Największym, czwartym z kolei błędem było jednak... udostępnienie kodu źródłowego owego generatora światu.
Firma jest bowiem wielkim zwolennikiem otwartości i udostępnia wszystkie swoje aplikacje na licencji zbliżonej do GPL.
Efekt?
Po upływie bardzo krótkiego czasu kilku spryciarzy wyłapało wszystkie ww. błędy (tak naprawdę błędów było więcej, ale pomijam niektóre z nich dla zwięzłości) i wykombinowało, że jeżeli zsynchronizujemy "zegarek" naszego komputera z serwerem, na którym odbywa się tasowanie, wówczas znając czas rozpoczęcia tasowania jesteśmy w stanie ograniczyć zbiór możliwych wymieszań talii do zaledwie około dwustu tysięcy.
Dwieście tysięcy możliwych potasowań to tyle co nic. Okazuje się, że żeby stwierdzić jednoznacznie o które potasowanie chodzi, wystarczy znać pięć pierwszych kart z "kupki".
W pokerze (w wariancie Cantrell) na początku gry znamy właśnie pięć kart. W Texas Hold'em na dzień dobry dostajemy tylko dwie karty, ale od razu po pierwszej turze (flop) znamy ich już pięć. Wystarczy więc wejść do gry i dojść do momentu, kiedy rozdający położy trzy karty na stole, a następnie przeszukać naszą bazę 200000 możliwych potasowań, znaleźć to właściwe - i już wiemy kto ma jakie karty i jaki będzie flop i river. Krótko mówiąc - z góry wiemy czy nasza ręka jest najsilniejsza czy nie.
Szach, mat.
Błąd załatano dość szybko - ale zanim to nastąpiło, całkiem sporo "spryciarzy" zdążyło się obłowić.
Wniosek: wszystkie algorytmy mogące w jakiś sposób być wykorzystane do nieuczciwego zarabiania pieniędzy powinny być bardzo, ale to bardzo rygorystycznie testowane. Można zlitować się nad kotem w pudełku (i po prostu odłączyć butlę z trującym gazem), ale nie wolno mieć litości dla kodu, który pójdzie w świat i będzie używany przez miliony graczy, 24 godziny na dobę.
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.