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

Cryptoguru Bruce Schneier (hvor krypto midler kryptografi, ikke den anden ting!) har lige offentliggjort en spændende note på sin blog med titlen Om tilfældigheden af ​​automatiske kortblandere.

Hvis du nogensinde har været på et kasino, mindst et i Nevada, vil du vide, at blackjack-bordene ikke tager chancer med kunder kendt i branchen som korttællere.

Dette udtryk bruges til at referere til spillere, der har trænet deres hukommelse til det punkt, at de kan holde tæt styr på de kort, der er spillet indtil videre i en hånd, hvilket giver dem en teoretisk fordel i forhold til huset, når de forudsiger, om de skal stå eller slå som spil skrider frem.

Korttællere kan opnå en fordel, selvom det eneste, de gør, er at holde styr på forholdet mellem 10-kort (Ti, Knægt, Dronning og Konge) og ikke-10-kort, der er tilbage i dealerens sko.

For eksempel, hvis dealeren sidder med et es, men et over gennemsnittet antal af 10-værdikort allerede er brugt op, så har dealeren en under gennemsnittet chance for at lave blackjack (21 point med to kort, dvs. Es og en på 10-JQK) og vinde på én gang, og en over gennemsnittet chance for at gå bust, før man når stoppunktet på 17 og derover.

Hvis du kan balancere sandsynligheden i dit hoved i realtid, så kan du muligvis ændre dine indsatser i overensstemmelse hermed og komme ud foran i det lange løb.

Prøv faktisk ikke dette, i det mindste i Nevada: kasinoet vil sandsynligvis fange dig ret hurtigt, fordi dit spillemønster vil afvige væsentligt fra de mest informerede vindervalg, der er tilgængelige, hvis du ikke tæller kort. Du ender måske ikke i retten, men du vil næsten helt sikkert blive eskorteret væk fra stedet og aldrig slippe ind igen.

Udjævning af odds

For at reducere modvægten af ​​sandsynligheder, som korttællere nyder godt af (i det mindste dem, der ikke er blevet fanget endnu), typisk:

• Giv hænder fra en sko fyldt med seks pakker (dæk) med 52 kort. Det betyder, at hver hånd, der uddeles, skæver den resterende fordeling af kort mindre, end hvis en enkelt pakke blev brugt.
• Bland hele skoen med 312 kort (seks pakker) før hver hånd. For at spare tid og fjerne mistanke fra dealeren, blander en pseudorandom elektromekanisk maskine kortene lige på bordet foran alle spillerne.

Det rejser straks spørgsmålet fra Schneier: Hvor godt blandede er kortene, når de kommer ud af maskinen?

Især med seks nye pakker med kort, som ankommer i en forudsigelig rækkefølge (f.eks. es til hjertekonge, es til kløverkonge, konge til es af ruder, konge til spar es), hvor meget delvis rækkefølge, der er tilbage efter har maskinen gjort sit arbejde?

Kunne du "gætte" det næste kort ud af skoen bedre end tilfældighederne antyder?

En fuldt elektronisk randomiser er begrænset i sin kompleksitet hovedsageligt af hastigheden på den CPU, den bruger, som typisk måles i hundredvis af millioner eller milliarder af aritmetiske operationer i sekundet.

Men en elektromekanisk kortblander skal bogstaveligt talt flytte rundt på kortene i det virkelige liv.

Der er åbenlyst en grænse for, hvor hurtigt den kan udføre pakkeopdelinger, kortbytninger og interleaving-operationer, før hastigheden af ​​mekanismen begynder at beskadige kortene, hvilket betyder, at der er en grænse for, hvor meget tilfældighed (eller mere præcist, pseudorandom) kan maskinen introducere, før det er tid til at spille den næste hånd.

Bland i for kort tid, og kasinoet kan faktisk gøre tingene lettere for korttællere, hvis der er en kendt skævhed i fordelingen af ​​kortene lige fra starten.

Bland for længe, ​​og spillet vil være for langsomt, så spillere vil kede sig og vandre væk, noget som kasinoer desperat forsøger at undgå.

Schneiers blogindlæg linker til en fascinerende stykke af BBC, der beskriver, hvordan en matematiker/tryllekunstner kaldet Persi Diaconis fra Stanford University sammen med Jason Fulman og Susan Holmes gennemførte en formel undersøgelse af netop dette spørgsmål tidligere i dette århundrede, i et papir med titlen ganske enkelt: ANALYSE AF CASINO HYLDE BLOKKE MASKINER.

Kompleksitetsniveauer

Det er klart, at der er nogle blandeteknikker, der slet ikke blander kortene meget, som f.eks. skære pakken i to dele og flytte den nederste del til toppen.

Andre teknikker resulterer i (eller føles som om de burde resultere i) til bedre blanding, for eksempel riffel shuffle, hvor du deler pakken nogenlunde i to, holder den ene halvdel i hver hånd og "vender" de to halvdele sammen, og indfletter dem på en pseudorandom måde, der skifter mellem at tage et par kort fra den ene side og derefter et par kort fra den anden side .

Ideen er, at hvis du blander pakken flere gange, udfører du en pseudorandom-sekvens af klip, hver gang du deler pakken før hver riffle, blandet sammen med en pseudorandomly variabel sekvens af pseudorandom-interleaving-operationer, der involverer en N-fra-the- venstre-så-M-fra-højre-processen.

Spændende er det dog, at når dygtige menneskelige blandere er involveret, er ingen af ​​disse antagelser om uforudsigelighed sikre.

Behændige tryllekunstnere og skæve dealere (Diaconis selv er førstnævnte, men ikke sidstnævnte) kan udføre, hvad der er kendt som faro blander sig eller perfekte shuffles, hvor de gør begge følgende ting, hver gang de ryster med flokken:

• Del kortene præcist i to, får således præcis 26 kort i hver hånd.
• Interleave dem perfekt, vippe præcis et kort ned ad gangen skiftevis fra hver hånd, hver eneste gang.

Diaconis selv kan lave perfekte shuffles (herunder den sjældne evne at gøre det med kun én hånd for at holde begge halvdele af flokken!), og ifølge BBC:

[Han] kan lide at demonstrere den perfekte blanding ved at tage et nyt kortspil og skrive ordet TILFÆLDIGT med en tyk sort tusch på den ene side. Mens han udfører sin hånd med kortene, bliver bogstaverne blandet sammen og dukker nu og da op i spøgelsesagtig form, som et ufuldkomment indstillet billede på et gammelt tv. Så, efter han har lavet den ottende og sidste blanding, rematerialiseres ordet på siden af ​​bunken. Kortene er i deres nøjagtige originale rækkefølge, fra spar-es til hjerte-es.

To typer af perfektion

Faktisk er der to slags perfekte shuffle, afhængigt af hvilken hånd du begynder at riffel fra efter at have skåret kortene i to bunker med 26 kort.

Du kan flette kortene, så de ender i rækkefølgen 1-27-2-28-3-29-...-25-51-26-52, hvis det første kort, du vender nedad, kommer fra den hånd, du har den nederste halvdel af pakken.

Men hvis det første kort, du vender ned, er det nederste kort i det, der tidligere var øverste halvdel af pakken, ender du med 27-1-28-2-29-3-...-51-25-52-26, så kort lige over halvvejs ender ovenpå bagefter.

Førstnævnte type kaldes en ud-shuffle, og omarrangerer pakken hver ottende gang, du gentager den, som du kan se her (billedet har 52 linjer med pixels, hver linje svarer til kanten af ​​et kort med ordet RANDOM skrevet på det med en tusch):

Sidstnævnte type er en i-shuffle, og dette tager utroligt nok 52 omblandinger, før det gentager sig, selvom du tydeligt kan se her, at pakken aldrig rigtig viser nogen sand tilfældighed, og endda passerer gennem en perfekt vending halvvejs igennem:

Hvad sagde matematikerne?

Så tilbage i 2013, da Diaconis el al. studerede hylde-shuffler-maskinen på producentens invitation, hvad fandt de?

Som avisen forklarer det, er en hyldeblander et elektromekanisk forsøg på at udtænke en automatiseret, randomiseret "multi-cut multi-riffle shuffle", ideelt så kortene kun skal gennemarbejdes én gang for at holde blandetiden kort.

Kortene i en hyldeblander bliver hurtigt "uddelt" pseudotilfældigt, et ad gangen, på en af ​​N metalhylder inde i enheden (hvoraf navnet), og hver gang et kort føjes til en hylde, glides det enten ind ved bunden, eller faldet på toppen af ​​tidligere kort. (Vi antager, at forsøg på at stikke kortet mellem to tilfældige kort, der allerede er i stakken, vil være både langsommere og tilbøjelige til at beskadige kortene.)

Efter at alle kort er blevet tildelt en hylde, så hver hylde har omkring 1/Nth af kortene på sig, samles kortene igen i en enkelt bunke i en pseudotilfældig rækkefølge.

Intuitivt, givet den involverede pseudotilfældighed, ville du forvente, at yderligere omblandinger ville forbedre den overordnede tilfældighed, op til et punkt...

…men i dette tilfælde, hvor maskinen havde 10 hylder, blev forskerne specifikt spurgt, "Vil en omgang af maskinen være tilstrækkelig til at producere tilstrækkelig tilfældighed?"

Formentlig ønskede virksomheden at undgå at køre maskinen gennem flere cyklusser for at holde spillerne glade og spillet flydende godt, og ingeniørerne, der havde designet enheden, havde ikke opdaget nogen åbenlyst udskiftelige statistiske anomalier under deres egne tests.

Men det ville virksomheden sikre sig ikke havde bestået sine egne tests, blot fordi testene passede til maskinen, hvilket ville give dem en falsk følelse af sikkerhed.

I sidste ende fandt forskerne ikke kun ud af, at tilfældigheden var ret ringe, men også at de var i stand til at kvantificere præcis, hvor ringe den var, og dermed udtænke alternative tests, der overbevisende afslørede manglen på tilfældighed.

De viste især, at kun én gang af enheden efterlod tilstrækkelig mange korte sekvenser af kort i det blandede output, til at de pålideligt kunne forudsige mellem 9 og 10 kort i gennemsnit, når en pakke med 52 blandede kort blev uddelt efterfølgende.

Som forskerne skrev:

[U]at synge vores teori, var vi i stand til at vise, at en kyndig spiller kunne gætte omkring 9 og et halvt kort korrekt i en enkelt omgang gennem et 52-korts kortspil. For et godt blandet kortspil får den optimale strategi omkring 4 og et halvt kort korrekt. Disse data overbeviste virksomheden. Teorien foreslog også et nyttigt middel.

[...]

Præsidenten for virksomheden svarede: "Vi er ikke tilfredse med dine konklusioner, men vi tror på dem, og det er det, vi hyrede dig til." Vi foreslog et simpelt alternativ: brug maskinen to gange. Dette resulterer i en blanding svarende til en maskine med 200 hylder. Vores matematiske analyse og yderligere test, som ikke er rapporteret her, viser, at dette er tilstrækkeligt tilfældigt.

Hvad skal jeg gøre?

Denne fortælling indeholder flere "lærsomme øjeblikke", og du gør klogt i at lære af dem, uanset om du er programmør eller produktchef, der selv kæmper med tilfældigheden, eller en SecOps/DevOps/IT/cybersikkerhedsprofessionel, der er involveret i cybersikkerhedssikring i generel:

• Det er ikke nok at bestå dine egne prøver. At fejle dine egne tests er bestemt dårligt, men det er nemt at ende med tests, som du forventer, at din algoritme, dit produkt eller din service består, især hvis dine rettelser eller “fejlrettelser” måles på, om de får dig igennem testene. Nogle gange har du brug for en anden mening, der kommer fra en objektiv, uafhængig kilde. Det uafhængige overblik kunne komme fra et crack-hold af matematiske statistikere fra Californien, som her; fra et eksternt "rødt hold" af penetrationstestere; eller fra et MDR-hold (managed detection and response), som bringer deres egne øjne og ører til din cybersikkerhedssituation.
• Det er vigtigt at lytte til dårlige nyheder. Præsidenten for blandemaskinefirmaet svarede i dette tilfælde perfekt, da han indrømmede, at han var utilfreds med resultatet, men at han havde betalt for at afsløre sandheden, ikke blot for at høre, hvad han håbede.
• Kryptografi i særdeleshed og cybersikkerhed generelt er svært. At bede om hjælp er ikke en indrømmelse af fiasko, men en erkendelse af, hvad der skal til for at lykkes.
• Tilfældighed er for vigtig til at overlades til tilfældighederne. Det er ikke let at måle lidelse (læs avisen at forstå hvorfor), men det kan og bør gøres.

---

Mangler du tid eller ekspertise til at tage sig af cybersikkerhedstrusler? Bekymret for, at cybersikkerhed vil ende med at distrahere dig fra alle de andre ting, du skal gøre?

Lær mere om Sophos Managed Detection and Response:
24/7 trusselsjagt, detektion og reaktion  ▶

---