Resna varnost: pri Blackjacku ne morete premagati hiše – ali pa lahko?

Kriptogur Bruce Schneier (kjer kripto pomeni kriptografija, ne drugo!) je pravkar objavil zanimiv zapis na svojem blogu z naslovom O naključnosti samodejnih mešalcev kart.

Če ste kdaj bili v igralnici, vsaj eni v Nevadi, boste vedeli, da mize za blackjack ne tvegajo s strankami, ki so v trgovini znane kot števci kartic.

Ta izraz se uporablja za označevanje igralcev, ki so izurili svoj spomin do te mere, da lahko natančno sledijo kartam, ki so bile do tedaj odigrane v roki, kar jim daje teoretično prednost pred hišo pri napovedovanju, ali bodo stali ali udarili kot igra napreduje.

Števci kart lahko pridobijo prednost, tudi če le spremljajo razmerje med 10 kartami (deset, Jack, dama in kralj) in ne-10, ki so ostale v delivčevem čevlju.

Na primer, če ima delivec asa, a je že porabljenih nadpovprečno število kart z vrednostjo 10, ima delivec podpovprečno možnost, da naredi blackjack (21 točk z dvema kartama, tj. As in eden od 10-JQK) in zmaga naenkrat ter nadpovprečna možnost, da propadeš, preden dosežeš končno točko 17 in več.

Če lahko uravnotežite verjetnosti v svoji glavi v realnem času, boste morda lahko ustrezno spremenili svoje stave in dolgoročno dosegli prednost.

Tega pravzaprav ne poskušajte, vsaj v Nevadi: igralnica vas bo verjetno precej hitro ujela, ker se bo vaš vzorec igranja precej razlikoval od najbolj informiranih zmagovalnih izbir, ki so na voljo, če ne štejete kart. Morda ne boste končali na sodišču, vendar vas bodo skoraj zagotovo pospremili iz prostorov in vas nikoli več ne spustili nazaj.

Izravnavanje kvot

Da bi zmanjšali protiutež verjetnosti, ki jo imajo števci kart (vsaj tisti, ki še niso bili ujeti), igralnice običajno:

• Delite roke iz čevlja, polnega šestih paketov (špilov) po 52 kart. To pomeni, da vsaka razdeljena roka popači preostalo porazdelitev kart manj, kot če bi uporabili en sam paket.
• Pred vsako roko premešajte celoten čevelj 312 kart (šest paketov). Da bi prihranili čas in odvrnili sum delivca, psevdonaključni elektromehanski stroj premeša karte kar na mizi, pred vsemi igralci.

To takoj sproži vprašanje, ki ga je postavil Schneier: kako dobro so karte premešane, ko pridejo iz stroja?

Predvsem pri šestih novih paketih kart, ki prispejo v predvidljivem vrstnem redu (npr. od asa do srčnega kralja, od asa do trefnega kralja, kralja do karo asa, kralja do pikovega asa), koliko delnega vrstnega reda ostane po je stroj opravil svoje delo?

Bi lahko naslednjo karto iz čevlja »uganil« bolje, kot kaže naključje?

Popolnoma elektronski randomizator je v svoji kompleksnosti omejen predvsem s hitrostjo procesorja, ki ga uporablja, ki se običajno meri v stotinah milijonov ali milijardah aritmetičnih operacij na sekundo.

Toda elektromehanski mešalec kart mora dobesedno premikati karte v resničnem življenju.

Očitno obstaja omejitev, kako hitro lahko izvede delitve paketov, zamenjave kartic in operacije prepletanja, preden hitrost mehanizma začne poškodovati kartice, kar pomeni, da obstaja omejitev, koliko naključnosti (ali, natančneje, psevdonaključnost) stroj lahko predstavi, preden je čas za naslednjo igro.

Premešajte prekratek čas in igralnica bi lahko dejansko olajšala stvari za števce kart, če je že od začetka znana pristranskost pri razdeljevanju kart.

Premešajte predolgo in igranje bo prepočasno, tako da se bodo igralci dolgočasili in odšli, čemur se igralnice obupno skušajo izogniti.

Schneierjev spletni dnevnik objavlja povezave do a fascinanten kos BBC, ki opisuje, kako je matematik/čarovnik po imenu Persi Diaconis z Univerze Stanford skupaj z Jasonom Fulmanom in Susan Holmes v začetku tega stoletja izvedel uradno preiskavo prav tega vprašanja v prispevku z naslovom preprosto: ANALIZA STROJEV ZA MEŠANJE POLIC V IGRALNICAH.

Ravni kompleksnosti

Jasno je, da obstajajo nekatere tehnike mešanja, ki kart sploh ne pomešajo preveč, na primer preprosto rezanje pakiranje na dva dela in spodnji del premaknite na vrh.

Druge tehnike povzročijo (ali občutek, kot da bi morale povzročiti) boljše mešanje, na primer rifle shuffle, kjer paket približno razdelite na pol, držite eno polovico v vsaki roki in "obrnete" obe polovici skupaj, tako da ju prepletate na psevdonaključni način, ki izmenično vzame nekaj kart z ene strani in nato nekaj kart z druge strani. .

Ideja je, da če paket večkrat premešate, izvedete psevdonaključno zaporedje rezov vsakič, ko razdelite paket pred vsakim riflom, pomešano s psevdonaključno spremenljivim zaporedjem psevdonaključnih operacij prepletanja, ki vključuje N-iz-the- postopek levo nato M-od-desne.

Zanimivo pa je, da ko so vpleteni izurjeni človeški premešalci, nobena od teh predpostavk o nepredvidljivosti ni varna.

Spretni čarovniki in pokvarjeni trgovci (prvi je sam Diaconis, drugi pa ne) lahko izvedejo tisto, kar je znano kot faro premešaali popolni premešaji, kjer naredijo obe naslednji stvari vsakič, ko zapletejo paket:

• Karte natančno razdelite na dva dela, tako dobiš natanko 26 kart v vsaki roki.
• Popolnoma jih prepletite, obračanje natančno ene karte naenkrat izmenično iz vsake roke, vsakič.

Diaconis sam zna narediti popolno mešanje (vključno z redko veščino, da to počne samo z eno roko, da drži obe polovici paketa!), in glede na BBC:

[On] rad demonstrira popolno mešanje tako, da vzame nov komplet kart in na eno stran z debelim črnim flomastrom napiše besedo NAKLJUČNO. Ko on spretno igra s kartami, se črke pomešajo in se tu in tam pojavijo v obliki duhov, kot nepopolno uglašena slika na starem televizorju. Potem, ko opravi osmo in zadnje mešanje, se beseda ponovno materializira na strani krova. Karte so v svojem izvirnem zaporedju, od pikovega asa do srčnega asa.

Dve vrsti popolnosti

Pravzaprav obstajata dve vrsti popolnega mešanja, odvisno od tega, iz katere roke začnete žrebati, potem ko ste karte razrezali na dva kupa po 26 kart.

Karte lahko prepletate tako, da končajo v zaporedju 1-27-2-28-3-29-…-25-51-26-52, če je prva karta, ki jo obrnete navzdol, iz roke, ki jo držite spodnja polovica paketa.

Toda če je prva karta, ki jo obrnete navzdol, spodnja karta tistega, kar je bila prej zgornja polovica paketa, imate na koncu 27-1-28-2-29-3-…-51-25-52-26, torej karta, ki je tik čez polovico, se pozneje konča na vrhu.

Prva vrsta se imenuje an ven-mešati, in prerazporedi paket vsakih osemkrat, ko ga ponovite, kot lahko vidite tukaj (slika ima 52 vrstic slikovnih pik, vsaka vrstica ustreza robu ene kartice z besedo NAKLJUČNO, napisano na njej s flomastrom):

Slednji tip je an v naključju, in to presenetljivo zahteva 52 ponovnih mešanj, preden se ponovi, čeprav lahko tukaj jasno vidite, da paket nikoli zares ne pokaže nobene prave naključnosti in gre celo skozi popoln obrat na polovici poti:

Kaj so rekli matematiki?

Torej, leta 2013, ko je Diaconis el al. na povabilo proizvajalca preučevali stroj za mešanje polic, kaj so ugotovili?

Kot pojasnjuje časopis, je mešalnik na policah elektromehanski poskus zasnove avtomatiziranega, naključnega "mešanja z več rezi in več žlebov", idealno tako, da je treba karte obravnavati samo enkrat, da je čas mešanja kratek.

Karte v mešalniku na policah se hitro "razdelijo" psevdonaključno, ena za drugo, na eno od N kovinskih polic v napravi (od tod tudi ime) in vsakič, ko je karta dodana na polico, jo potisnete noter na dno ali pade na vrh prejšnjih kart. (Predvidevamo, da bi bil poskus, da bi karto vtaknili med dve naključni karti, ki sta že v kupu, počasnejši in lahko poškoduje karte.)

Ko so vse karte dodeljene polici, tako da je na vsaki polici približno 1/N kart, se karte ponovno sestavijo v en sam kup v psevdonaključnem vrstnem redu.

Glede na vpleteno psevdonaključnost bi intuitivno pričakovali, da bi dodatna ponovna premešanja izboljšala splošno naključnost, do neke točke ...

… toda v tem primeru, ko je imel stroj 10 polic, so raziskovalce posebej vprašali, "Ali bo en prehod stroja zadostoval za ustrezno naključnost?"

Verjetno se je podjetje želelo izogniti poganjanju stroja skozi več ciklov, da bi bili igralci zadovoljni in da bi igra dobro tekla, inženirji, ki so zasnovali napravo, pa med lastnimi testi niso odkrili nobenih očitno izkoristljivih statističnih anomalij.

Toda podjetje se je želelo prepričati, da je ni opravil lastnih testov preprosto zato, ker so testi ustrezali stroju, kar bi jim dalo lažen občutek varnosti.

Končno so raziskovalci ugotovili, da je bila naključnost precej slaba, ampak tudi, da so lahko natančno kvantificirali, kako slaba je bila, in tako oblikovali alternativne teste, ki so prepričljivo razkrili pomanjkanje naključnosti.

Predvsem so pokazali, da je samo en prehod naprave pustil dovolj kratkih zaporedij kart v premešanem izhodu, da so lahko zanesljivo predvideli med 9 in 10 kart v povprečju, ko je bil nato razdeljen paket 52 premešanih kart.

Kot so zapisali raziskovalci:

[Z]uporabo naše teorije nam je uspelo pokazati, da lahko dobro obveščen igralec pravilno ugane približno 9 kart in pol v enem samem teku skozi komplet 52 kart. Za dobro premešan komplet ima optimalna strategija pravilne približno 4 karte in pol. Ti podatki so prepričali podjetje. Teorija je predlagala tudi koristno zdravilo.

[...]

Predsednik družbe je odgovoril: "Nismo zadovoljni z vašimi zaključki, vendar jim verjamemo in zato smo vas najeli." Predlagali smo preprosto alternativo: stroj uporabite dvakrat. Posledica tega je mešanje, ki je enakovredno stroju z 200 policami. Naša matematična analiza in nadaljnji testi, o katerih tukaj ne poročamo, kažejo, da je to dovolj naključno.

Kaj storiti?

Ta zgodba vsebuje več »učljivih trenutkov« in pametno bi bilo, da bi se iz njih učili, ne glede na to, ali ste programer ali produktni vodja, ki se tudi sam borite z naključnostjo, ali strokovnjak za SecOps/DevOps/IT/kibernetsko varnost, ki se ukvarja z zagotavljanjem kibernetske varnosti v splošno:

• Opravljanje lastnih testov ni dovolj. Neuspeh na lastnih testih je vsekakor slab, vendar je enostavno končati s testi, za katere pričakujete, da jih bo vaš algoritem, izdelek ali storitev prestal, še posebej, če se vaši popravki ali »popravki napak« merijo glede na to, ali vam pomagajo skozi teste. Včasih potrebujete drugo mnenje, ki prihaja iz objektivnega, neodvisnega vira. Ta neodvisni pregled bi lahko prišel od crack ekipe matematičnih statistikov iz Kalifornije, kot tukaj; iz zunanje »rdeče ekipe« preizkuševalcev penetracije; ali od posadke MDR (upravljano odkrivanje in odziv), ki v vašo situacijo kibernetske varnosti vnese svoje oči in ušesa.
• Poslušanje slabih novic je pomembno. Predsednik podjetja za mešalne stroje je v tem primeru odlično odgovoril, ko je priznal, da je bil nezadovoljen z rezultatom, a da je plačal, da odkrije resnico, ne le zato, da bi slišal, kar je upal.
• Zlasti kriptografija in kibernetska varnost na splošno je težavna. Prošnja za pomoč ni priznanje neuspeha, ampak priznanje, kaj je potrebno za uspeh.
• Naključnost je preveč pomembna, da bi jo prepustili naključju. Merjenje motenj ni enostavno (preberi časopis razumeti, zakaj), vendar je to mogoče in treba storiti.

---

Vam primanjkuje časa ali strokovnega znanja za odgovor na kibernetsko varnost? Vas skrbi, da vas bo kibernetska varnost na koncu odvrnila od vseh drugih stvari, ki jih morate početi?

Več o tem Upravljano odkrivanje in odziv Sophos:
24/7 lov na grožnje, odkrivanje in odziv  ▶

---