Seriøs sikkerhet: Du kan ikke slå huset på Blackjack – eller kan du det?

Cryptoguru Bruce Schneier (hvor krypto midler kryptografi, ikke den andre tingen!) publiserte nettopp et spennende notat på bloggen hans med tittelen Om tilfeldigheten til automatiske kortstokkere.

Hvis du noen gang har vært på et kasino, minst ett i Nevada, vil du vite at blackjack-bordene ikke tar sjanser med kunder kjent i bransjen som korttellere.

Dette begrepet brukes for å referere til spillere som har trent opp minnene sine til det punktet at de kan holde nøye oversikt over kortene som er spilt så langt i en hånd, noe som gir dem en teoretisk fordel over huset når de forutsier om de skal stå eller slå som spill. utvikler seg.

Korttellere kan oppnå en fordel selv om alt de gjør er å holde styr på forholdet mellom 10-kort (ti, knekt, dronning og konge) og ikke-10-er som er igjen i dealerens sko.

For eksempel, hvis dealeren sitter med et ess, men et over gjennomsnittet antall kort med 10 verdier allerede er brukt opp, så har dealeren en under gjennomsnittet sjanse til å lage blackjack (21 poeng med to kort, dvs. Ess og en på 10-JQK) og vinne på en gang, og en over gjennomsnittet sjanse for å gå bust før du når stopppunktet på 17 og over.

Hvis du kan balansere sannsynlighetene i hodet ditt i sanntid, kan det hende du kan endre innsatsene dine tilsvarende og komme foran i det lange løp.

Ikke prøv dette, i hvert fall i Nevada: kasinoet vil sannsynligvis fange deg ut ganske raskt, fordi spillemønsteret ditt vil avvike spesielt fra de mest informerte vinnervalgene som er tilgjengelige hvis du ikke teller kort. Du havner kanskje ikke i retten, men du vil nesten helt sikkert bli eskortert ut av lokalene og aldri slippe inn igjen.

Utjevne oddsen

For å redusere motvekten av sannsynligheter som korttellere nyter godt av (i det minste de som ikke har blitt tatt ennå), vanligvis:

• Del hender fra en sko lastet med seks pakker (kortstokker) med 52 kort. Dette betyr at hver hånd som deles ut skjev den gjenværende fordeling av kort mindre enn om en enkelt pakke ble brukt.
• Bland hele skoen med 312 kort (seks pakker) før hver hånd. For å spare tid og fjerne mistanke fra dealeren, blander en pseudotilfeldig elektromekanisk maskin kortene rett på bordet, foran alle spillerne.

Det reiser umiddelbart spørsmålet fra Schneier: hvor godt blandet er kortene når de kommer ut av maskinen?

Spesielt med seks nye pakker med kort, som kommer i en forutsigbar rekkefølge (f.eks. ess til hjertekonge, ess til kløverkonge, konge til ess av ruter, konge til spar ess), hvor mye delvis rekkefølge er igjen etter at har maskinen gjort jobben sin?

Kunne du "gjettet" neste kort ut av skoen bedre enn tilfeldighetene tilsier?

En helelektronisk randomiser er begrenset i sin kompleksitet hovedsakelig av hastigheten til CPU-en den bruker, som typisk måles i hundrevis av millioner eller milliarder av aritmetiske operasjoner i sekundet.

Men en elektromekanisk kortstokker må bokstavelig talt flytte kortene rundt i det virkelige liv.

Det er åpenbart en grense for hvor raskt den kan utføre pakkedelinger, kortbytteoperasjoner og interleaving-operasjoner før hastigheten på mekanismen begynner å skade kortene, noe som betyr at det er en grense for hvor mye tilfeldighet (eller mer presist, pseudotilfeldighet) kan maskinen introdusere før det er på tide å spille neste hånd.

Bland i for kort tid, og kasinoet kan faktisk gjøre ting enklere for korttellere, hvis det er en kjent skjevhet i fordelingen av kortene helt fra starten.

Bland for lenge, og spillet vil gå for sakte, slik at spillere vil kjede seg og vandre bort, noe kasinoer desperat prøver å unngå.

Schneiers blogginnlegg lenker til en fascinerende stykke av BBC som beskriver hvordan en matematiker/trollmann kalt Persi Diaconis fra Stanford University, sammen med Jason Fulman og Susan Holmes, gjennomførte en formell undersøkelse av nettopp dette problemet tidligere dette århundret, i en artikkel med tittelen ganske enkelt: ANALYSE AV KASINOREYLLE MASKINER.

Nivåer av kompleksitet

Det er tydelig at det er noen stokketeknikker som ikke blander kortene mye i det hele tatt, for eksempel ganske enkelt skjæring pakken i to deler og flytt den nederste delen til toppen.

Andre teknikker resulterer i (eller føles som om de burde resultere i) til bedre blanding, for eksempel rifle shuffle, hvor du deler pakken omtrent i to, holder den ene halvdelen i hver hånd, og «snu» de to halvdelene sammen, og setter dem sammen på en pseudorandom måte som veksler mellom å ta noen kort fra den ene siden, så noen kort fra den andre. .

Tanken er at hvis du blander pakken flere ganger, utfører du en pseudorandom-sekvens av kutt hver gang du deler pakken før hver riffle, blandet sammen med en pseudorandomly variabel sekvens av pseudorandom-interleaving-operasjoner som involverer en N-fra-the- venstre-så-M-fra-høyre-prosessen.

Spennende, men når dyktige menneskelige blandere er involvert, er ingen av disse antakelsene om uforutsigbarhet trygge.

Flinke tryllekunstnere og skjeve forhandlere (Diaconis selv er førstnevnte, men ikke sistnevnte) kan utføre det som er kjent som faro blander segeller perfekte shuffles, der de gjør begge de følgende tingene hver gang de svir med flokken:

• Del kortene nøyaktig i to, får dermed nøyaktig 26 kort i hver hånd.
• Interleave dem perfekt, vipp ned nøyaktig ett kort om gangen vekselvis fra hver hånd, hver eneste gang.

Diaconis selv kan gjøre perfekte stokkinger (inkludert den sjeldne ferdigheten å gjøre det med bare én hånd for å holde begge halvdelene av flokken!), og ifølge BBC:

[Han] liker å demonstrere den perfekte stokkingen ved å ta en ny kortstokk og skrive ordet TILFELDIG med en tykk svart tusj på den ene siden. Etter hvert som han utfører sin slemming med kortene, blir bokstavene blandet sammen, og dukker opp nå og da i spøkelsesaktig form, som et ufullkomment innstilt bilde på et gammelt TV-apparat. Så, etter at han har gjort den åttende og siste stokkingen, gjenmaterialiseres ordet på siden av kortstokken. Kortene er i sin nøyaktige opprinnelige rekkefølge, fra spar-ess til hjerte-ess.

To typer perfeksjon

Faktisk er det to typer perfekte shuffle, avhengig av hvilken hånd du begynner å riffel fra etter å ha kuttet kortene i to 26-korts hauger.

Du kan flette kortene slik at de havner i sekvensen 1-27-2-28-3-29-...-25-51-26-52, hvis det første kortet du snur nedover kommer fra hånden du har den nederste halvdelen av pakken.

Men hvis det første kortet du vipper ned er det nederste kortet i det som tidligere var øvre halvdel av pakken, ender du opp med 27-1-28-2-29-3-…-51-25-52-26, så kort like over halvveis havner på toppen etterpå.

Den førstnevnte typen kalles en ut-stokke, og omorganiserer pakken hver åttende gang du gjentar den, som du kan se her (bildet har 52 linjer med piksler, hver linje tilsvarer kanten av ett kort med ordet TILFELDIG skrevet på den med en tusj):

Sistnevnte type er en i shuffle, og dette tar utrolig nok 52 omstokkinger før det gjentas, selv om du tydelig kan se her at pakken egentlig aldri viser noen ekte tilfeldighet, og til og med går gjennom en perfekt reversering halvveis:

Hva sa matematikerne?

Så tilbake i 2013, da Diaconis el al. studerte hyllestokkmaskinen på produsentens invitasjon, hva fant de?

Som avisen forklarer det, er en hyllestokker et elektromekanisk forsøk på å utvikle en automatisert, randomisert "multi-cut multi-riffle shuffle", ideelt slik at kortene bare trenger å bli gjennomarbeidet én gang, for å holde stokkingen kort.

Kortene i en hyllestokker blir raskt "delt ut" pseudotilfeldig, ett om gangen, på en av N metallhyller inne i enheten (derav navnet), og hver gang et kort legges til en hylle, skyves det enten inn ved bunnen, eller falt på toppen av tidligere kort. (Vi antar at det å prøve å stikke kortet mellom to tilfeldige kort som allerede er i bunken, vil være både tregere og utsatt for å skade kortene.)

Etter at alle kortene har blitt tildelt en hylle, slik at hver hylle har omtrent 1/Ndel av kortene på seg, settes kortene sammen til en enkelt haug i en pseudorandom rekkefølge.

Intuitivt, gitt pseudorandomiteten involvert, ville du forvente at ytterligere omstokkinger ville forbedre den generelle tilfeldigheten, opp til et punkt ...

…men i dette tilfellet, hvor maskinen hadde 10 hyller, ble forskerne spesifikt spurt, "Vil én omgang av maskinen være tilstrekkelig til å produsere tilstrekkelig tilfeldighet?"

Antagelig ønsket selskapet å unngå å kjøre maskinen gjennom flere sykluser for å holde spillerne fornøyde og spillet flyte godt, og ingeniørene som hadde designet enheten hadde ikke oppdaget noen åpenbart utskiftbare statistiske anomalier under sine egne tester.

Men selskapet ville sørge for at det hadde ikke bestått sine egne tester bare fordi testene passet til maskinen, noe som ville gi dem en falsk følelse av trygghet.

Til syvende og sist fant forskerne ikke bare at tilfeldigheten var ganske dårlig, men også at de var i stand til å kvantifisere nøyaktig hvor dårlig den var, og dermed utarbeide alternative tester som overbevisende avslørte mangelen på tilfeldighet.

Spesielt viste de at bare ett pass av enheten etterlot tilstrekkelig mange korte sekvenser med kort i den stokkede utgangen til at de pålitelig kunne forutsi mellom 9 og 10 kort i gjennomsnitt når en pakke med 52 stokkede kort ble delt ut etterpå.

Som forskerne skrev:

Ved å synge teorien vår var vi i stand til å vise at en kunnskapsrik spiller kunne gjette om 9 og et halvt kort riktig i en enkelt kjøring gjennom en kortstokk med 52 kort. For en godt blandet kortstokk får den optimale strategien omtrent 4 og et halvt kort korrekt. Disse dataene overbeviste selskapet. Teorien foreslo også et nyttig middel.

[...]

Presidenten for selskapet svarte: "Vi er ikke fornøyd med konklusjonene dine, men vi tror på dem, og det er det vi ansatt deg for." Vi foreslo et enkelt alternativ: bruk maskinen to ganger. Dette resulterer i en shuffle tilsvarende en 200-hylle maskin. Vår matematiske analyse og ytterligere tester, som ikke er rapportert her, viser at dette er tilstrekkelig tilfeldig.

Hva gjør jeg?

Denne historien inneholder flere «lærbare øyeblikk», og du vil gjøre klokt i å lære av dem, enten du er programmerer eller produktsjef som sliter spesifikt med randomess selv, eller en SecOps/DevOps/IT/cybersikkerhetsekspert som er involvert i cybersikkerhetssikring i generell:

• Det er ikke nok å bestå dine egne tester. Å feile på dine egne tester er definitivt dårlig, men det er lett å ende opp med tester som du forventer at algoritmen, produktet eller tjenesten din skal bestå, spesielt hvis rettelsene eller "feilrettingene" måles etter om de får deg gjennom testene. Noen ganger trenger du en annen mening som kommer fra en objektiv, uavhengig kilde. Den uavhengige oversikten kan komme fra et crack-team av matematiske statistikere fra California, som her; fra et eksternt "rødt team" av penetrasjonstestere; eller fra et MDR-mannskap (managed detection and response) som tar med sine egne øyne og ører til din cybersikkerhetssituasjon.
• Det er viktig å lytte til dårlige nyheter. Presidenten for stokkingsmaskinselskapet i denne saken svarte perfekt da han innrømmet at han var misfornøyd med resultatet, men at han hadde betalt for å avdekke sannheten, ikke bare for å høre hva han håpet.
• Kryptografi spesielt, og cybersikkerhet generelt, er vanskelig. Å be om hjelp er ikke en innrømmelse av feil, men en erkjennelse av hva som skal til for å lykkes.
• Tilfeldighet er for viktig til å overlates til tilfeldighetene. Å måle lidelse er ikke lett (Les avisen for å forstå hvorfor), men det kan og bør gjøres.

---

Har du mangel på tid eller ekspertise til å ta seg av cybersikkerhetstrusselrespons? Bekymret for at cybersikkerhet vil ende opp med å distrahere deg fra alle de andre tingene du trenger å gjøre?

Lær mer om Sophos Managed Detection and Response:
24/7 trusseljakt, deteksjon og respons  ▶

---