Vakava turvallisuus: Et voi voittaa taloa Blackjackilla – vai voitko?

Cryptoguru Bruce Schneier (missä Crypto välineet kryptografia, ei se toinen asia!) julkaisi juuri kiehtovan huomautuksen blogissaan otsikolla Automaattisten korttisekoittajien satunnaisuudesta.

Jos olet koskaan käynyt kasinolla, ainakin yhdellä Nevadassa, tiedät, että blackjack-pöydät eivät ota riskejä asiakkaiden kanssa, jotka tunnetaan alalla korttilaskurit.

Tätä termiä käytetään viittaamaan pelaajiin, jotka ovat harjoittaneet muistiaan niin pitkälle, että he pystyvät seuraamaan tarkasti kädessä tähän mennessä pelattuja kortteja, mikä antaa heille teoreettisen edun taloon verrattuna, kun he ennustavat seisovatko vai lyövät pelinä. etenee.

Korttilaskijat voivat saada etua, vaikka he vain seuraavat 10 kortin (Kymmenen, Jack, Queen ja King) suhdetta jakajan kenkään jäljellä oleviin 10 korttiin.

Esimerkiksi, jos jakaja istuu ässän kanssa, mutta keskimääräistä suurempi määrä 10 arvoisia kortteja on jo käytetty, jakajan mahdollisuus tehdä blackjack on keskimääräistä pienempi (21 pistettä kahdella kortilla, ts. Ässä ja yksi 10-JQK) ja voitto kerralla, ja keskimääräistä suurempi mahdollisuus kaatua ennen kuin saavut pysähdyspisteeseen 17 tai enemmän.

Jos pystyt tasapainottamaan todennäköisyydet päässäsi reaaliajassa, saatat pystyä muokkaamaan panoksiasi vastaavasti ja pääsemään eteenpäin pitkällä aikavälillä.

Älä todellakaan kokeile tätä ainakaan Nevadassa: kasino saa sinut todennäköisesti kiinni melko nopeasti, koska pelimallisi poikkeaa huomattavasti tietoisimmista käytettävissä olevista voittovalinnoista, jos et laske kortteja. Et ehkä päädy oikeuteen, mutta sinut saatetaan melkein varmasti pois tiloista etkä koskaan päästää takaisin sisään.

Todennäköisyyksien tasoitus

Vähentääkseen korttilaskijoiden (ainakin ne, jotka eivät ole vielä jääneet kiinni) nauttimien todennäköisyyksien vastapainoa kasinot tyypillisesti:

• Jaa käsiä kengästä, jossa on kuusi 52 kortin pakkausta (pakkaa). Tämä tarkoittaa, että jokainen jaettu käsi vääristää jäljellä olevaa korttien jakautumista vähemmän kuin jos käytettäisiin yhtä pakettia.
• Sekoita koko 312 kortin kenkä (kuusi pakkausta) ennen jokaista kättä. Ajan säästämiseksi ja jakajan epäilyksen poistamiseksi näennäissatunnainen sähkömekaaninen kone sekoittaa kortit suoraan pöydällä kaikkien pelaajien edessä.

Tämä herättää heti Schneierin kysymyksen: kuinka hyvin sekoittuneet kortit ovat, kun ne tulevat ulos koneesta?

Erityisesti kuudella uudella korttipakkauksella, jotka saapuvat ennustettavassa järjestyksessä (esim. ässästä sydänkuninkaan, ässästä mailakuninkaan, kuninkaasta timanttiässään, kuninkaasta pataässään), kuinka paljon osittaista järjestystä on jäljellä onko kone tehnyt tehtävänsä?

Voisitteko "arvata" seuraavan kortin kengästä paremmin kuin sattuma antaa ymmärtää?

Täysin elektronisen satunnaistajan monimutkaisuutta rajoittaa pääasiassa sen käyttämän CPU:n nopeus, joka mitataan tyypillisesti sadoissa miljoonissa tai miljardeissa aritmeettisissa operaatioissa sekunnissa.

Mutta sähkömekaanisen korttisekoittimen on kirjaimellisesti siirrettävä kortteja tosielämässä.

On selvää, kuinka nopeasti se pystyy suorittamaan paketin jakamista, korttien vaihtoja ja lomittelutoimintoja, ennen kuin mekanismin nopeus alkaa vahingoittaa kortteja, mikä tarkoittaa, että satunnaisuudella (tai tarkemmin sanottuna, näennäissatunnaisuus) kone voi esitellä ennen kuin on aika pelata seuraava käsi.

Sekoita liian vähän aikaa, ja kasino saattaa itse asiassa helpottaa korttilaskijoiden asioita, jos korttien jakamisessa on tiedossa alusta alkaen harhaa.

Sekoita liian pitkään, ja pelaaminen on liian hidasta, jotta pelaajat kyllästyvät ja vaeltavat pois, mitä kasinot yrittävät epätoivoisesti välttää.

Schneierin blogitekstit linkittävät a kiehtova pala BBC, joka kuvaa kuinka matemaatikko/taikuri nimeltä Persi Diaconis Stanfordin yliopistosta yhdessä Jason Fulmanin ja Susan Holmesin kanssa suoritti muodollisen tutkimuksen juuri tästä asiasta aiemmin tällä vuosisadalla, artikkelissa, jonka otsikko on yksinkertaisesti: KASINON HYLLYTYÖKONEISTOJEN ANALYYSI.

Monimutkaisuustasot

On selvää, että on joitain sekoitustekniikoita, jotka eivät sekoita kortteja ollenkaan, kuten yksinkertaisesti leikkaus pakkaus kahteen osaan ja siirrä alaosa ylöspäin.

Muut tekniikat johtavat (tai tuntuvat siltä, ​​että niiden pitäisi johtaa) parempaan sekoitukseen, esimerkiksi riffle shuffle, jossa jaat paketin karkeasti puoliksi, pidät toista puolikasta kummassakin kädessä ja "käännät" kaksi puoliskoa yhteen ja lomitat ne näennäissatunnaisella tavalla siten, että otat muutaman kortin toiselta puolelta ja sitten muutaman kortin toiselta puolelta. .

Ajatuksena on, että jos sekoitat paketin useita kertoja, suoritat näennäissatunnaisen leikkaussarjan joka kerta, kun jaat pakkauksen ennen jokaista riffausta, ja sekoitat yhteen näennäissatunnaisesti vaihtelevan sekvenssin näennäissatunnaisia ​​lomitustoimintoja, joihin liittyy N-alkaen. vasen-sitten-M-oikealta-prosessi.

Mielenkiintoista on kuitenkin, että kun mukana on taitavia ihmissekoittajia, mikään näistä arvaamattomuudesta oleuksista ei ole turvallinen.

Taitavat taikurit ja kiero jakajat (Diaconis itse on edellinen, mutta ei jälkimmäinen) voivat suorittaa ns. faro sekoittaatai täydellinen sekoitus, jossa he tekevät molemmat seuraavat asiat joka kerta, kun he sotkevat paketin:

• Jaa kortit tarkasti kahtia, jolloin jokaisessa kädessä on täsmälleen 26 korttia.
• Limitä ne täydellisesti, kääntämällä alas tasan yhden kortin kerrallaan vuorotellen kustakin kädestä, joka kerta.

Diaconis itse osaa tehdä täydellisiä sekoitusta (mukaan lukien harvinainen taito tehdä niin yhdellä kädellä pitääkseen kiinni molemmista puoliskoista!), ja BBC:n mukaan:

[Hän] haluaa esitellä täydellisen sekoituksen ottamalla uuden korttipakan ja kirjoittamalla sanan RANDOM paksulla mustalla tussilla yhdelle puolelle. Kun hän tekee käsityötään korttien kanssa, kirjaimet sekoittuvat ja ilmestyvät silloin tällöin aavemaisessa muodossa, kuin vanhassa televisiossa epätäydellisesti viritetty kuva. Sitten, kun hän on tehnyt kahdeksannen ja viimeisen sekoituksen, sana materialisoituu uudelleen kannen kylkeen. Kortit ovat täsmälleen alkuperäisessä järjestyksessään pataässästä sydämen ässään.

Kahden tyyppistä täydellisyyttä

Itse asiassa täydellistä sekoitusta on kahdenlaisia ​​sen mukaan, kummasta kädestä aloitat riffauksen leikattuasi kortit kahteen 26 kortin pinoon.

Voit limittää kortit siten, että ne päätyvät sekvenssiin 1-27-2-28-3-29-…-25-51-26-52, jos ensimmäinen kortti, jonka käännät alaspäin, tulee kädestä, jossa pidät. hän pakkauksen alaosassa.

Mutta jos ensimmäinen kortti, jonka käännät alas, on alin kortti, joka oli aiemmin pakkauksen ylin puolisko, päädyt 27-1-28-2-29-3-…-51-25-52-26, joten puolessa välissä oleva kortti päätyy jälkeenpäin.

Edellinen tyyppi on nimeltään an out-shuffle, ja järjestää pakkauksen uudelleen joka kahdeksan kertaa toistat sen, kuten näet tästä (kuvassa on 52 riviä pikseliä, jokainen rivi vastaa yhden kortin reunaa, johon on kirjoitettu merkkikynällä sana RANDOM):

Jälkimmäinen tyyppi on an satunnaistoistossa, ja tämä vaatii hämmästyttävällä tavalla 52 uudelleensekoitusta ennen kuin se toistuu, vaikka näet selvästi, että pakkaus ei koskaan osoita mitään todellista satunnaisuutta ja jopa käy läpi täydellisen käännöksen puolivälissä:

Mitä matemaatikot sanoivat?

Joten vuonna 2013, kun Diaconis el al. tutkinut hyllysekoitinkonetta valmistajan kutsusta, mitä he löysivät?

Kuten paperi selittää, hyllysekoitin on sähkömekaaninen yritys suunnitella automatisoitu, satunnaistettu "multi-cut multi-riffle shuffle", ihannetapauksessa niin, että kortit tarvitsee käsitellä vain kerran läpi, jotta sekoitusaika pysyy lyhyenä.

Hyllysekoittimessa olevat kortit "jaetaan" nopeasti näennäissatunnaisesti yksi kerrallaan yhdelle laitteen sisällä olevasta N metallihyllystä (josta nimi), ja aina kun kortti lisätään hyllylle, se joko liu'utetaan sisään alas tai pudotettu aiempien korttien päälle. (Oletamme, että kortin työntäminen kahden pinossa jo olevan satunnaisen kortin väliin olisi sekä hitaampaa että alttiimpaa vahingoittamaan kortteja.)

Kun kaikki kortit on kohdistettu hyllylle siten, että kullakin hyllyllä on noin 1/N-osa korteista, kortit kootaan yhdeksi pinoksi näennäissatunnaisessa järjestyksessä.

Intuitiivisesti, kun otetaan huomioon siihen liittyvä näennäissatunnaisuus, voit odottaa, että lisäsekoitukset parantaisivat yleistä satunnaisuutta tiettyyn pisteeseen asti…

…mutta tässä tapauksessa, jossa koneessa oli 10 hyllyä, tutkijoilta kysyttiin erityisesti, "Riittääkö yksi koneen kierros riittävän satunnaisuuden tuottamiseen?"

Oletettavasti yritys halusi välttää koneen pyörittämistä useiden syklien läpi, jotta pelaajat olisivat tyytyväisiä ja peli sujuisi hyvin, eivätkä laitteen suunnitellut insinöörit olleet havainneet omissa testeissään ilmeisen hyödyllisiä tilastollisia poikkeamia.

Mutta yritys halusi varmistaa sen ei ollut läpäissyt omia testejään vain siksi, että testit sopisivat koneelle, mikä antaisi heille väärän turvallisuuden tunteen.

Lopulta tutkijat havaitsivat paitsi, että satunnaisuus oli melko heikkoa, myös että he pystyivät mittaamaan tarkalleen kuinka huono se oli, ja siten suunnittelemaan vaihtoehtoisia testejä, jotka paljastavat vakuuttavasti satunnaisuuden puutteen.

Erityisesti he osoittivat, että vain yksi laitteen siirto jätti sekoitettuun ulostuloon tarpeeksi lyhyitä korttisarjoja, jotta he pystyivät luotettavasti ennustamaan keskimäärin 9–10 korttia, kun 52 sekoitettua korttia sisältävä paketti jaettiin jälkeenpäin.

Kuten tutkijat kirjoittivat:

[Käyttäen teoriaamme, pystyimme osoittamaan, että asiantunteva pelaaja pystyi arvaamaan noin 9 ja puoli korttia oikein yhdellä juoksulla 52 kortin pakassa. Hyvin sekoitettuun pakkaan optimaalinen strategia saa noin 4 ja puoli korttia oikein. Nämä tiedot vakuuttivat yrityksen. Teoria ehdotti myös hyödyllistä lääkettä.

[...]

Yrityksen toimitusjohtaja vastasi: "Emme ole tyytyväisiä päätelmiinne, mutta uskomme niihin ja siihen olemme palkanneet sinut." Ehdotimme yksinkertaista vaihtoehtoa: käytä konetta kahdesti. Tämä johtaa satunnaistoistoon, joka vastaa 200 hyllyn konetta. Matemaattinen analyysimme ja lisätestimme, joita ei ole raportoitu tässä, osoittavat, että tämä on riittävän satunnaista.

Mitä tehdä?

Tämä tarina sisältää useita "opetettavia hetkiä", ja sinun on viisasta ottaa niistä oppia, olitpa sitten ohjelmoija tai tuotepäällikkö, joka painii nimenomaan satunnaisuuden kanssa, tai SecOps/DevOps/IT/kyberturvallisuuden ammattilainen, joka on mukana kyberturvallisuuden varmistamisessa yleistä:

• Omien kokeiden läpäiseminen ei riitä. Omien testien epäonnistuminen on ehdottomasti huono asia, mutta on helppo päätyä testeihin, joiden odotat algoritmisi, tuotteesi tai palvelusi läpäisevän, varsinkin jos korjauksiasi tai "virheenkorjauksiasi" mitataan sen mukaan, pääsevätkö ne testin läpi. Joskus tarvitset toisen mielipiteen, joka tulee objektiivisesta, riippumattomasta lähteestä. Tuo riippumaton yleiskatsaus voisi tulla kalifornialaisen matemaattisten tilastotieteilijöiden halkeamien tiimiltä, ​​kuten täällä; ulkopuolisesta läpäisytestaajien "punaisesta ryhmästä"; tai MDR-henkilöstöltä (managed detection and reponse), joka tuo omat silmänsä ja korvansa kyberturvallisuustilanteeseesi.
• Huonojen uutisten kuunteleminen on tärkeää. Sekoituskoneyhtiön toimitusjohtaja vastasi tässä tapauksessa täydellisesti, kun hän myönsi olevansa tyytymätön tulokseen, mutta että hän oli maksanut paljastaakseen totuuden, ei vain saadakseen kuulla, mitä hän toivoi.
• Varsinkin kryptografia ja kyberturvallisuus yleensä on vaikeaa. Avun pyytäminen ei ole epäonnistumisen myöntämistä, vaan sen tunnustamista, mitä menestyminen vaatii.
• Satunnaisuus on liian tärkeää jätettäväksi sattuman varaan. Häiriön mittaaminen ei ole helppoa (Lue paperi ymmärtää miksi), mutta se voidaan ja pitää tehdä.

---

Puuttuuko aika tai asiantuntemus kyberturvallisuusuhkien torjuntaan? Oletko huolissasi siitä, että kyberturvallisuus häiritsee sinua kaikista muista asioista, joita sinun on tehtävä?

Lisätietoja Sophosin hallinnoima tunnistus ja vastaus:
24/7 uhkien metsästys, havaitseminen ja reagointi  ▶

---