Tõsine turvalisus: Blackjackis ei saa te maja vastu võita – või saate?

Krüptoguru Bruce Schneier (kus krüpto vahendid krüptograafia, mitte teine ​​asi!) avaldas just oma ajaveebis intrigeeriva märkuse pealkirjaga Automaatsete kaardisegajate juhuslikkusest.

Kui olete kunagi käinud kasiinos, vähemalt ühes Nevadas, teate, et blackjacki lauad ei võta riske klientidega, kes on tuntud kui kaardiloendurid.

Seda terminit kasutatakse mängijate tähistamiseks, kes on treeninud oma mälu nii kaugele, et nad suudavad täpselt jälgida jaotuses seni mängitud kaarte, mis annab neile teoreetilise eelise maja ees, kui nad ennustavad, kas mänguna seisa või lüüa. edeneb.

Kaardiloendurid võivad omandada eelise isegi siis, kui nad jälgivad vaid 10-kaardi (kümme, jack, kuninganna ja kuningas) ja mitte-10-kaartide suhet diileri kingades.

Näiteks kui diiler istub ässaga, kuid üle keskmise 10 väärtusega kaarte on juba ära kasutatud, siis on diileril võimalus blackjacki tegemiseks alla keskmise (kahe kaardiga 21 punkti, st. Äss ja üks 10-JQK) ja võit korraga ning keskmisest suurem võimalus kukkuda enne peatuspunkti 17 ja kõrgemat jõudmist.

Kui suudate oma peas tõenäosusi reaalajas tasakaalustada, saate oma panuseid vastavalt muuta ja pikas perspektiivis eduseisust välja tulla.

Ärge proovige seda, vähemalt Nevadas: kasiino tabab teid tõenäoliselt üsna kiiresti, sest teie mängumuster erineb märkimisväärselt kõige teadlikumatest võiduvalikutest, kui te kaarte ei loe. Te ei pruugi kohtusse sattuda, kuid teid saadetakse peaaegu kindlasti ruumist välja ja teid ei lasta enam kunagi tagasi.

Koefitsientide tasandamine

Et vähendada kaardilugejate (vähemalt need, keda pole veel tabatud) tõenäosuste vastukaalu, teevad kasiinod tavaliselt järgmist.

• Jagage käsi kinga abil, mis on laetud kuue 52 kaardiga pakki (pakki). See tähendab, et iga jaotatud jaotus kallutab ülejäänud kaartide jaotust vähem kui siis, kui kasutataks ühte pakki.
• Segage kogu 312 kaardist koosnev kinga (kuus pakki) enne iga jaotust. Aja säästmiseks ja diileri kahtluse eemaldamiseks segab pseudojuhuslik elektromehaaniline masin kaardid otse laual, kõigi mängijate silme all.

See tõstatab kohe küsimuse, mille Schneier esitas: kui hästi on kaardid masinast väljudes segatud?

Kuue uue kaardipaki korral, mis saabuvad ennustatavas järjekorras (nt äss südamekuningaks, äss pallikuningaks, kuningat teemantide kuningaks, kuningaks labidaässaks), kui palju on osalist järjestamist alles pärast kas masin on oma töö teinud?

Kas saaksite järgmise kaardi kingast välja arvata paremini, kui juhus viitab?

Täielikult elektroonilist randomiseerijat piirab selle keerukus peamiselt selles kasutatava protsessori kiirus, mida tavaliselt mõõdetakse sadades miljonites või miljardites aritmeetilistes operatsioonides sekundis.

Kuid elektromehaaniline kaardisegaja peab sõna otseses mõttes kaarte päriselus liigutama.

Ilmselgelt on piir, kui kiiresti see suudab sooritada pakkide jagamise, kaartide vahetamise ja vahelejätmise toiminguid, enne kui mehhanismi kiirus hakkab kaarte kahjustama, mis tähendab, et juhuslikkuse (või täpsemalt pseudojuhuslikkus) saab masin kasutusele võtta enne, kui on aeg mängida järgmist jaotust.

Segage liiga lühikest aega ja kasiino võib tegelikult kaardilugejate jaoks asja lihtsamaks teha, kui kaartide jagamisel on algusest peale teadaolevalt eelarvamus.

Segage liiga kaua ja mängimine on liiga aeglane, nii et mängijatel hakkab igav ja nad eksivad, mida kasiinod püüavad meeleheitlikult vältida.

Schneieri ajaveebi postitustes on lingid a põnev tükk BBC poolt, mis kirjeldab, kuidas Stanfordi ülikooli matemaatik/mustkunstnik nimega Persi Diaconis koos Jason Fulmani ja Susan Holmesiga viisid selle sajandi alguses läbi selle probleemi ametliku uurimise, artiklis pealkirjaga lihtsalt: KASIINO RIIULIDE SEGAVIMISMASINATE ANALÜÜS.

Keerukuse tasemed

On selge, et on mõned segamistehnikad, mis ei sega kaarte üldse, näiteks lihtsalt lõikamine pakk kaheks osaks ja liigutada alumine osa üles.

Muude tehnikate tulemuseks on (või tundub, nagu peaks nende tulemuseks olema) parem segunemine, näiteks riffle shuffle, kus jagate paki laias laastus pooleks, hoiate ühte poolt mõlemas käes ja "keerate" kaks poolt kokku, pannes need pseudojuhuslikult vahele, võttes vaheldumisi ühelt poolt paar kaarti, seejärel teiselt poolt paar kaarti. .

Idee seisneb selles, et kui segate pakki mitu korda segamini, sooritate pseudojuhusliku kärpete jada iga kord, kui jagate paki enne iga lööki, segades kokku pseudojuhuslikult muutuva pseudojuhuslike põimimisoperatsioonide jadaga, mis hõlmab N-st-the- vasak-siis-M-paremalt-protsess.

Huvitaval kombel ei ole aga ükski neist ettearvamatuse eeldustest ohutu, kui tegemist on osavate inimeste segamisega.

Osavad mustkunstnikud ja kõverad diilerid (Diaconis ise on esimene, kuid mitte viimane) võivad teha nn. faro segabvõi täiuslik segadus, kus nad teevad mõlemat järgmist tegevust iga kord, kui nad pakki riisuvad:

• Jagage kaardid täpselt kaheks, seega saab igas käes täpselt 26 kaarti.
• Lõika need ideaalselt vahele, keerates igast käest vaheldumisi täpselt ühe kaardi korraga, iga kord.

Diaconis ise suudab teha täiuslikke segamisi (sealhulgas haruldane oskus teha seda vaid ühe käega, et hoida mõlemat pakipoolt!) ja BBC andmetel:

[Talle] meeldib demonstreerida täiuslikku segamist, võttes uue kaardipaki ja kirjutades ühele poole paksu musta markeriga sõna RANDOM. Kui ta kaartidega oma vingerpussi sooritab, lähevad tähed segamini, ilmudes aeg-ajalt kummituslikul kujul nagu ebatäiuslikult häälestatud pilt vanas teleris. Pärast seda, kui ta teeb kaheksanda ja viimase segamise, rematerialiseerub sõna teki küljel. Kaardid on oma täpses algses järjestuses, alates labidaässast kuni südameässani.

Kaks täiuslikkuse tüüpi

Tegelikult on kahte tüüpi täiuslikku segamist, olenevalt sellest, millisest käest hakkate pärast kaartide kaheks 26-kaardiliseks hunnikuks lõikamist riffima.

Saate kaardid vahele jätta nii, et need jõuaksid järjestusse 1-27-2-28-3-29-…-25-51-26-52, kui esimene allapoole pööratud kaart pärineb käest, milles te hoiate ta alumine pool pakist.

Aga kui esimene kaart, mille alla keerate, on varem paki ülemise poole alumine kaart, saate lõpuks 27-1-28-2-29-3-…-51-25-52-26, nii et kaart, mis oli just poole peal, jõuab pärast seda peal.

Endist tüüpi nimetatakse an välja-segamine, ja järjestab paki iga kaheksa korda, kui seda kordate, nagu näete siit (pildil on 52 pikslirida, iga rida vastab ühe kaardi servale, millele on markerpliiatsiga kirjutatud sõna RANDOM):

Viimane tüüp on an segamises, ja see nõuab hämmastaval kombel 52 uuesti segamist, enne kui see kordub, kuigi siin on selgelt näha, et pakk ei näita kunagi tõelist juhuslikkust ja läbib poolel teel isegi täiusliku tagasikäigu:

Mida matemaatikud ütlesid?

Niisiis, veel 2013. aastal, kui Diaconis el al. uurisid tootja kutsel riiulisegamismasinat, mida nad leidsid?

Nagu paberis selgitatakse, on riiulisegaja elektromehaaniline katse luua automatiseeritud, juhuslikult valitud "mitmelõikeline mitme riffli segamine", ideaalis nii, et kaardid tuleb läbi töötada ainult üks kord, et segamisaeg oleks lühike.

Riiulisegistis olevad kaardid jagatakse kiiresti pseudojuhuslikult, ükshaaval, ühele seadme sees olevast N metallriiulist (sellest ka nimi) ja iga kord, kui kaart riiulile lisatakse, libistatakse see kas alumine või eelmiste kaartide peale langenud. (Eeldame, et kahe juba virnas oleva juhusliku kaardi vahele torkamine oleks aeglasem ja võib kaarte kahjustada.)

Pärast seda, kui kõik kaardid on riiulile määratud, nii et igal riiulil on umbes 1/N kaartidest, koondatakse kaardid pseudojuhuslikus järjekorras ühte hunnikusse.

Arvestades sellega kaasnevat pseudojuhuslikkust, võiks intuitiivselt eeldada, et täiendavad ümbersegamised parandavad üldist juhuslikkust kuni teatud punktini…

…aga sel juhul, kui masinal oli 10 riiulit, küsiti teadlastelt konkreetselt, "Kas ühest masinakäigust piisab piisava juhuslikkuse tekitamiseks?"

Arvatavasti soovis ettevõte vältida masina käivitamist läbi mitme tsükli, et mängijad oleksid rahul ja mäng sujuks hästi, ning seadme projekteerinud insenerid ei olnud oma katsetuste käigus tuvastanud ilmselgelt kasulikke statistilisi kõrvalekaldeid.

Kuid ettevõte tahtis selles veenduda ei olnud läbinud oma katseid lihtsalt sellepärast, et need testid masinale sobisid, mis tekitaks neile vale turvatunde.

Lõppkokkuvõttes avastasid teadlased mitte ainult, et juhuslikkus oli üsna halb, vaid ka seda, et nad suutsid täpselt kvantifitseerida, kui halb see oli, ja seega töötada välja alternatiivsed testid, mis veenvalt näitasid juhuslikkuse puudumist.

Eelkõige näitasid nad, et ainult üks seadme läbimine jättis segatud väljundisse piisavalt palju lühikesi kaardijadasid, et nad võisid usaldusväärselt ennustada keskmiselt 9–10 kaarti, kui hiljem jagati välja 52 segatud kaardist koosnev pakk.

Nagu teadlased kirjutasid:

[Oma teooriat lauldes suutsime näidata, et asjatundlik mängija suudab ühe 9-kaardilise kaardipaki korraga ära arvata umbes 52 ja pool kaarti. Hästi segatud kaardipaki puhul on optimaalseks strateegiaks umbes 4 ja pool kaarti õiged. Need andmed veensid ettevõtet. Teooria pakkus välja ka kasuliku abinõu.

[...]

Ettevõtte president vastas: "Me ei ole teie järeldustega rahul, kuid me usume neid ja selleks me teid palkasime." Soovitasime lihtsat alternatiivi: kasutage masinat kaks korda. Selle tulemuseks on segamine, mis vastab 200 riiuliga masinale. Meie matemaatiline analüüs ja edasised testid, mida siin ei ole kirjeldatud, näitavad, et see on piisavalt juhuslik.

Mida teha?

See lugu sisaldab mitmeid "õpetatavaid hetki" ja teil oleks mõistlik neist õppida, olenemata sellest, kas olete programmeerija või tootejuht, kes maadleb ise konkreetselt juhuslikkusega, või SecOps/DevOps/IT/küberturvalisuse professionaal, kes tegeleb küberturvalisuse tagamisega üldine:

• Enda testide sooritamisest ei piisa. Enda testide läbikukkumine on kindlasti halb, kuid lihtne on lõpetada testidega, mille puhul eeldate, et teie algoritm, toode või teenus läbib, eriti kui teie parandusi või „veaparandusi” mõõdetakse selle järgi, kas need viivad teid testidesse. Mõnikord on teil vaja teist arvamust, mis pärineb objektiivsest sõltumatust allikast. See sõltumatu ülevaade võiks tulla California matemaatiliste statistikute meeskonnalt, nagu siin; väliselt läbitungimistestijate "punaselt meeskonnalt"; või MDR-i (hallatud tuvastamise ja reageerimise) meeskonnalt, kes juhib oma silmad ja kõrvad teie küberjulgeoleku olukorda.
• Halbade uudiste kuulamine on oluline. Segamismasinate ettevõtte president vastas antud juhul suurepäraselt, kui tunnistas, et oli tulemusega rahul, kuid maksis tõe paljastamise eest, mitte lihtsalt selle eest, et kuulda, mida ta loodab.
• Eriti krüptograafia ja küberjulgeolek üldiselt on rasked. Abi küsimine ei ole ebaõnnestumise tunnistamine, vaid edu tunnustamine.
• Juhuslikkus on liiga oluline, et seda juhuse hooleks jätta. Häire mõõtmine ei ole lihtne (lugeda lehte aru saada, miks), kuid seda saab ja tuleks teha.

---

Kas napib aega või teadmisi küberjulgeolekuohtudele reageerimiseks? Kas olete mures, et küberturvalisus tõmbab teie tähelepanu kõrvale kõigilt muudelt asjadelt, mida peate tegema?

Lisateave Sophose hallatav tuvastamine ja reageerimine:
Ööpäevaringne ohtude otsimine, avastamine ja reageerimine  ▶

---