Allvarlig säkerhet: Du kan inte slå huset på Blackjack – eller kan du?

Cryptoguru Bruce Schneier (där crypto betyder kryptografi, inte det andra!) publicerade precis en spännande anteckning på sin blogg med titeln Om slumpmässigheten hos automatiska kortblandare.

Om du någonsin har varit på ett kasino, åtminstone ett i Nevada, kommer du att veta att blackjack-borden inte tar chanser med kunder kända i branschen som korträknare.

Den termen används för att hänvisa till spelare som har tränat upp sina minnen till den grad att de kan hålla koll på de kort som spelats hittills i en hand, vilket ger dem en teoretisk fördel över huset när de förutsäger om de ska stå eller slå som spel fortskrider.

Korträknare kan få en fördel även om allt de gör är att hålla reda på förhållandet mellan 10-kort (tio, knekt, dam och kung) och icke-10-kort kvar i dealerns sko.

Till exempel, om dealern sitter med ett ess, men ett över genomsnittet antal kort med 10 värden redan har använts, så har dealern en under genomsnittet chans att göra en blackjack (21 poäng med två kort, dvs. Ess och ett på 10-JQK) och vinst på en gång, och en över genomsnittet chans att gå i konkurs innan du når stopppunkten på 17 och högre.

Om du kan balansera sannolikheterna i ditt huvud i realtid, kan du kanske ändra dina satsningar i enlighet med detta och komma framåt i det långa loppet.

Testa faktiskt inte detta, åtminstone i Nevada: kasinot kommer sannolikt att fånga dig ganska snabbt, eftersom ditt spelmönster kommer att avvika särskilt från de mest välgrundade vinstvalen som finns tillgängliga om du inte räknar kort. Du kanske inte hamnar i domstol, men du kommer med största sannolikhet att bli eskorterad från lokalen och aldrig släppa in igen.

Utjämna oddsen

För att minska motvikten av sannolikheter som korträknare åtnjuter (åtminstone de som inte har fångats ännu), brukar kasinon:

• Dela ut händer från en sko laddad med sex pack (däck) med 52 kort. Detta innebär att varje hand som delas ut snedvrider den återstående fördelningen av kort mindre än om ett enda paket användes.
• Blanda hela skon med 312 kort (sex-pack) före varje hand. För att spara tid och för att ta bort misstankar från dealern, blandar en pseudoslumpmässig elektromekanisk maskin korten direkt på bordet, framför alla spelare.

Det väcker omedelbart frågan som ställs av Schneier: hur väl blandade är korten när de kommer ut ur maskinen?

Särskilt med sex nya kortpaket, som anländer i en förutsägbar ordning (t.ex. ess till hjärtkung, ess till klöverkung, kung till ess av ruter, kung till ess av spader), hur mycket partiell ordning är kvar efter har maskinen gjort sitt jobb?

Kan du "gissa" nästa kort ur skon bättre än vad slumpen antyder?

En helt elektronisk randomiserare begränsas i sin komplexitet huvudsakligen av hastigheten på processorn som den använder, vilket vanligtvis mäts i hundratals miljoner eller miljarder aritmetiska operationer per sekund.

Men en elektromekanisk kortblandare måste bokstavligen flytta runt korten i verkligheten.

Det finns uppenbarligen en gräns för hur snabbt den kan utföra packdelningar, kortbyten och interfolieringsoperationer innan hastigheten på mekanismen börjar skada korten, vilket innebär att det finns en gräns för hur mycket slumpmässighet (eller, mer exakt, pseudoslumpmässighet) kan maskinen introducera innan det är dags att spela nästa hand.

Blanda för kort tid, och kasinot kan faktiskt göra det enklare för korträknare, om det finns en känd bias i fördelningen av korten redan från början.

Blanda för länge och spelet blir för långsamt, så att spelarna blir uttråkade och går iväg, något som kasinon desperat försöker undvika.

Schneiers blogginlägg länkar till en fascinerande stycke av BBC som beskriver hur en matematiker/trollkarl vid namn Persi Diaconis från Stanford University, tillsammans med Jason Fulman och Susan Holmes, genomförde en formell undersökning av just denna fråga tidigare detta århundrade, i en artikel med titeln helt enkelt: ANALYS AV CASINO-HYLLNINGSMASKINER.

Komplexitetsnivåer

Det är uppenbart att det finns vissa blandningstekniker som inte blandar ihop korten så mycket alls, som helt enkelt skärning förpackningen i två delar och flytta den nedre delen till toppen.

Andra tekniker resulterar i (eller känns som om de borde resultera i) till bättre blandning, till exempel gevär shuffle, där du delar upp paketet ungefär på mitten, håller en halva i varje hand och "vänder" de två halvorna tillsammans, interfolierar dem på ett pseudoslumpmässigt sätt som växlar mellan att ta några kort från ena sidan och sedan några kort från den andra .

Tanken är att om du blandar paketet flera gånger, utför du en pseudoslumpmässig sekvens av snitt varje gång du delar paketet före varje riff, blandat med en pseudoslumpmässigt variabel sekvens av pseudoslumpmässiga interfolieringsoperationer som involverar en N-från- vänster-sedan-M-från-höger-processen.

Spännande, men när skickliga mänskliga shufflers är inblandade, är inget av dessa antaganden om oförutsägbarhet säker.

Skickliga magiker och sneda återförsäljare (Diaconis själv är den förra, men inte den senare) kan utföra vad som kallas faro blandar, eller perfekta blandningar, där de gör båda följande saker varje gång de räcker förpackningen:

• Dela korten exakt i två, får alltså exakt 26 kort i varje hand.
• Interfoliera dem perfekt, vända ner exakt ett kort i taget växelvis från varje hand, varje gång.

Diaconis själv kan göra perfekta blandningar (inklusive den sällsynta skickligheten att göra det med bara en hand för att hålla båda halvorna av förpackningen!), och enligt BBC:

[Han] gillar att demonstrera den perfekta blandningen genom att ta en ny kortlek och skriva ordet RANDOM med tjock svart markering på ena sidan. När han utför sitt grepp med korten blandas bokstäverna ihop och dyker upp då och då i spöklik form, som en ofullständigt inställd bild på en gammal TV-apparat. Sedan, efter att han gjort den åttonde och sista blandningen, återuppstår ordet på sidan av kortleken. Korten är i sin exakta ursprungliga sekvens, från spaderess till hjärtess.

Två typer av perfektion

Faktum är att det finns två sorters perfekta shuffle, beroende på vilken hand du börjar riffa från efter att ha klippt korten i två 26-kortshögar.

Du kan interfoliera korten så att de hamnar i sekvensen 1-27-2-28-3-29-...-25-51-26-52, om det första kortet du vänder nedåt kommer från den hand du håller i den nedre halvan av förpackningen.

Men om det första kortet du fäller ner är det nedre kortet i det som tidigare var den övre halvan av paketet, slutar du med 27-1-28-2-29-3-…-51-25-52-26, så kort strax över halvvägs hamnar överst efteråt.

Den förra typen kallas an ut-blanda, och ordnar om paketet var åttonde gång du upprepar det, som du kan se här (bilden har 52 rader med pixlar, varje rad motsvarar kanten på ett kort med ordet RANDOM skrivet på den med en märkpenna):

Den senare typen är en i blandning, och det här, förvånansvärt nog, tar 52 omblandningar innan det upprepas, även om du tydligt kan se här att paketet aldrig riktigt visar någon sann slumpmässighet, och till och med går igenom en perfekt reversering halvvägs:

Vad sa matematikerna?

Så, redan 2013, när Diaconis el al. studerade hyllblandaren på tillverkarens inbjudan, vad hittade de?

Som tidningen förklarar det är en hyllblandning ett elektromekaniskt försök att skapa en automatiserad, slumpmässig "multi-cut multi-riffle shuffle", helst så att korten bara behöver arbetas igenom en gång, för att hålla blandningstiden kort.

Korten i en hyllblandare "delas ut" snabbt pseudoslumpmässigt, ett i taget, på en av N metallhyllor inuti enheten (därav namnet), och varje gång ett kort läggs till en hylla skjuts det antingen in vid botten, eller tappade på toppen av tidigare kort. (Vi antar att försök att sticka in kortet mellan två slumpmässiga kort som redan finns i högen skulle vara både långsammare och benägna att skada korten.)

Efter att alla kort har tilldelats en hylla, så att varje hylla har ungefär 1/N:e av korten på sig, sätts korten ihop till en enda hög i en pseudoslumpmässig ordning.

Intuitivt, med tanke på pseudoslumpigheten som är involverad, skulle du förvänta dig att ytterligare omblandningar skulle förbättra den övergripande slumpmässigheten, upp till en viss punkt...

…men i det här fallet, där maskinen hade 10 hyllor, frågades forskarna specifikt, "Kommer en passage av maskinen att räcka för att producera adekvat slumpmässighet?"

Förmodligen ville företaget undvika att köra maskinen genom flera cykler för att hålla spelarna nöjda och spelet flyta bra, och ingenjörerna som hade designat enheten hade inte upptäckt några uppenbart expoterbara statistiska anomalier under sina egna tester.

Men företaget ville se till att det hade inte klarat sina egna tester bara för att testerna passade maskinen, vilket skulle ge dem en falsk känsla av säkerhet.

I slutändan fann forskarna inte bara att slumpmässigheten var ganska dålig, utan också att de kunde kvantifiera exakt hur dålig den var, och därmed utforma alternativa tester som övertygande avslöjade bristen på slumpmässighet.

I synnerhet visade de att bara ett pass av enheten lämnade tillräckligt många korta sekvenser av kort i den blandade utgången för att de på ett tillförlitligt sätt kunde förutsäga mellan 9 och 10 kort i genomsnitt när ett paket med 52 blandade kort delades ut efteråt.

Som forskarna skrev:

Med vår teori kunde vi visa att en kunnig spelare kunde gissa om 9 och ett halvt kort korrekt i en enda körning genom en 52-kortslek. För en väl blandad kortlek får den optimala strategin ungefär 4 och ett halvt kort korrekt. Dessa uppgifter övertygade företaget. Teorin föreslog också ett användbart botemedel.

[...]

Företagets VD svarade: "Vi är inte nöjda med dina slutsatser, men vi tror på dem och det är vad vi anlitade dig för." Vi föreslog ett enkelt alternativ: använd maskinen två gånger. Detta resulterar i en blandning som motsvarar en maskin med 200 hyllor. Vår matematiska analys och ytterligare tester, som inte redovisas här, visar att detta är tillräckligt slumpmässigt.

Vad göra?

Den här berättelsen innehåller flera "lärbara ögonblick", och du skulle göra klokt i att lära dig av dem, oavsett om du är programmerare eller produktchef som brottas specifikt med slumpmässighet själv, eller en SecOps/DevOps/IT/cybersäkerhetsproffs som är involverad i cybersäkerhetssäkring i allmän:

• Det räcker inte att klara dina egna prov. Att misslyckas med dina egna tester är definitivt dåligt, men det är lätt att sluta med tester som du förväntar dig att din algoritm, produkt eller tjänst ska klara, speciellt om dina korrigeringar eller "buggfixar" mäts efter om de tar dig igenom testerna. Ibland behöver du en andra åsikt som kommer från en objektiv, oberoende källa. Den oberoende översikten kan komma från ett sprickteam av matematiska statistiker från Kalifornien, som här; från ett externt "rött team" av penetrationstestare; eller från ett MDR-team (managed detection and response) som tar med sina egna ögon och öron till din cybersäkerhetssituation.
• Att lyssna på dåliga nyheter är viktigt. Presidenten för blandmaskinsföretaget svarade i det här fallet perfekt när han erkände att han var missnöjd med resultatet, men att han hade betalat för att avslöja sanningen, inte bara för att höra vad han hoppades.
• Kryptografi i synnerhet, och cybersäkerhet i allmänhet, är svårt. Att be om hjälp är inte ett erkännande av misslyckande utan ett erkännande av vad som krävs för att lyckas.
• Slumpmässighet är för viktigt för att lämnas åt slumpen. Att mäta störningar är inte lätt (Läs tidningen för att förstå varför), men det kan och bör göras.

---

Har du ont om tid eller expertis för att ta hand om cybersäkerhetshot? Orolig för att cybersäkerhet kommer att distrahera dig från alla andra saker du behöver göra?

Läs mer om Sophos Managed Detection and Response:
24/7 hotjakt, upptäckt och respons  ▶

---