Ernstige beveiliging: je kunt het huis niet verslaan bij Blackjack - of wel?

Cryptoguru Bruce Schneier (waar crypto middel geheimschrift, niet het andere!) heeft zojuist een intrigerende notitie op zijn blog gepubliceerd met de titel Over de willekeur van automatische kaartenschudders.

Als je ooit in een casino bent geweest, tenminste één in Nevada, weet je dat de blackjacktafels geen risico nemen met klanten die in de handel bekend staan ​​als kaart tellers.

Die term wordt gebruikt om te verwijzen naar spelers die hun geheugen zo hebben getraind dat ze de kaarten die tot nu toe in een hand zijn gespeeld, nauwkeurig kunnen volgen, wat hen een theoretisch voordeel geeft ten opzichte van het huis bij het voorspellen of ze moeten passen of slaan als spelen vordert.

Kaarttellers kunnen een voordeel behalen, zelfs als ze alleen de verhouding van 10 kaarten (tien, boer, vrouw en heer) tot niet-10's in de schoen van de dealer bijhouden.

Als de dealer bijvoorbeeld met een aas zit, maar er is al een bovengemiddeld aantal kaarten van 10 opgebruikt, dan heeft de dealer een benedengemiddelde kans om blackjack te maken (21 punten bij twee kaarten, dus Aas en een van 10-JQK) en tegelijk winnen, en een bovengemiddelde kans om failliet te gaan voordat het stoppunt van 17 en hoger wordt bereikt.

Als u de kansen in uw hoofd in realtime kunt afwegen, kunt u uw weddenschappen dienovereenkomstig aanpassen en op de lange termijn vooruit komen.

Probeer dit niet echt, tenminste niet in Nevada: het casino zal u waarschijnlijk vrij snel betrappen, omdat uw spelpatroon aanzienlijk zal afwijken van de best geïnformeerde winnende keuzes die beschikbaar zijn als u geen kaarten telt. Je komt misschien niet in de rechtbank terecht, maar je wordt vrijwel zeker van het terrein geëscorteerd en nooit meer binnengelaten.

De kansen nivelleren

Om het tegenwicht van kansen die kaarttellers genieten te verminderen (in ieder geval degenen die nog niet gepakt zijn), zijn de casino's meestal:

• Deal handen van een schoen geladen met zes pakjes (decks) van 52 kaarten. Dit betekent dat elke uitgedeelde hand de resterende kaartenverdeling minder vertekent dan wanneer een enkel pakket zou worden gebruikt.
• Schud de hele schoen van 312 kaarten (six packs) voor elke hand. Om tijd te besparen en argwaan bij de dealer weg te nemen, schudt een pseudo-willekeurige elektromechanische machine de kaarten recht op tafel, in het bijzijn van alle spelers.

Dat roept meteen de vraag van Schneier op: hoe goed zijn de kaarten geschud als ze uit de machine komen?

Met name, met zes nieuwe pakken kaarten, die in een voorspelbare volgorde aankomen (bijv. Aas tot Hartenkoning, Aas tot Klaverenkoning, Koning tot Aas van Ruiten, Koning tot Schoppenaas), hoeveel gedeeltelijke volgorde er overblijft na de machine zijn werk heeft gedaan?

Kun je de volgende kaart beter 'raden' dan het toeval doet vermoeden?

Een volledig elektronische randomizer wordt in zijn complexiteit voornamelijk beperkt door de snelheid van de CPU die hij gebruikt, die doorgaans wordt gemeten in honderden miljoenen of miljarden rekenkundige bewerkingen per seconde.

Maar een elektromechanische kaartenschudmachine moet de kaarten in het echte leven letterlijk verplaatsen.

Er is duidelijk een limiet aan hoe snel het pakketsplitsingen, kaartwisselingen en interleaving-bewerkingen kan uitvoeren voordat de snelheid van het mechanisme de kaarten begint te beschadigen, wat betekent dat er een limiet is aan hoeveel willekeur (of, meer precies, pseudowillekeurigheid) de machine kan introduceren voordat het tijd is om de volgende hand te spelen.

Schud voor een te korte tijd, en het casino zou het zelfs gemakkelijker kunnen maken voor kaarttellers, als er vanaf het begin een bekende vooringenomenheid is in de verdeling van de kaarten.

Schud te lang en het spel zal te langzaam zijn, zodat spelers zich gaan vervelen en wegdwalen, iets dat casino's wanhopig proberen te vermijden.

Schneier's blog plaatst links naar a fascinerend stuk door de BBC die beschrijft hoe een wiskundige/goochelaar genaamd Persi Diaconis van Stanford University, samen met Jason Fulman en Susan Holmes, eerder deze eeuw een formeel onderzoek naar deze kwestie heeft uitgevoerd, in een paper met de eenvoudige titel: ANALYSE VAN CASINO PLANK SCHUDDE MACHINES.

Niveaus van complexiteit

Het is duidelijk dat er enkele schudtechnieken zijn die de kaarten helemaal niet door elkaar halen, zoals gewoon: snijdend het pakket in twee delen en het onderste deel naar boven verplaatsen.

Andere technieken resulteren in (of voelen alsof ze zouden moeten resulteren in) tot een betere menging, bijvoorbeeld de geweer shuffle, waarbij je het pakket ruwweg in tweeën splitst, een helft in elke hand houdt en de twee helften "omdraait", waarbij je ze op een pseudowillekeurige manier door elkaar laat lopen, waarbij je afwisselend een paar kaarten van de ene kant neemt en vervolgens een paar kaarten van de andere kant .

Het idee is dat als je het pakket meerdere keren schudt, je een pseudo-willekeurige reeks sneden uitvoert elke keer dat je het pakket voor elk geweer verdeelt, vermengd met een pseudo-willekeurig variabele reeks pseudo-willekeurige interleaving-bewerkingen waarbij een N-van-de- links-dan-M-van-rechts proces.

Het is echter intrigerend dat wanneer er bekwame menselijke schudders bij betrokken zijn, geen van die aannames van onvoorspelbaarheid veilig is.

Handige goochelaars en malafide dealers (Diaconis zelf is de eerste, maar niet de laatste) kunnen uitvoeren wat bekend staat als faro schudtof perfecte shuffles, waar ze beide volgende dingen doen elke keer dat ze het peloton doorzoeken:

• Splits de kaarten precies in twee, dus precies 26 kaarten in elke hand krijgen.
• Interleave ze perfect, precies één kaart tegelijk omdraaien vanuit elke hand, elke keer opnieuw.

Diaconis zelf kan perfecte shuffles doen (inclusief de zeldzame vaardigheid om dit te doen met slechts één hand om beide helften van het peloton vast te houden!), En volgens de BBC:

[Hij] demonstreert graag de perfecte shuffle door een nieuw pak kaarten te nemen en het woord RANDOM in dikke zwarte stift op één kant te schrijven. Terwijl hij zijn vingervlugheid met de kaarten uitoefent, raken de letters door elkaar en verschijnen af ​​en toe in spookachtige vorm, als een onvolmaakt afgestemd beeld op een oud tv-toestel. Dan, nadat hij de achtste en laatste shuffle heeft gedaan, komt het woord weer terug op de zijkant van het kaartspel. De kaarten staan ​​in hun exacte originele volgorde, van de schoppenaas tot de hartenaas.

Twee soorten perfectie

In feite zijn er twee soorten perfecte shuffle, afhankelijk van uit welke hand je begint te rommelen nadat je de kaarten in twee stapels van 26 kaarten hebt gesneden.

Je kunt de kaarten tussen elkaar schuiven zodat ze in de volgorde 1-27-2-28-3-29-…-25-51-26-52 komen, als de eerste kaart die je naar beneden draait uit de hand komt die je vast hebt hij onderste helft van het peloton.

Maar als de eerste kaart die je omdraait de onderste kaart is van wat voorheen de bovenste helft van het pak was, krijg je 27-1-28-2-29-3-...-51-25-52-26, dus de kaart net over de helft belandt daarna bovenaan.

Het eerste type heet an uit-shuffle, en herschikt het pakket elke acht keer dat je het herhaalt, zoals je hier kunt zien (de afbeelding heeft 52 lijnen pixels, elke lijn komt overeen met de rand van een kaart met het woord RANDOM erop geschreven met een markeerstift):

Het laatste type is een in willekeurige volgorde, en dit, verbazingwekkend genoeg, duurt 52 her-shuffles voordat het zich herhaalt, hoewel je hier duidelijk kunt zien dat het pakket nooit echt enige echte willekeur vertoont, en zelfs halverwege een perfecte omkering doorloopt:

Wat zeiden de wiskundigen?

Dus, in 2013, toen Diaconis el al. op uitnodiging van de fabrikant de schappenschudmachine bestudeerden, wat vonden ze?

Zoals de krant het uitlegt, is een plankenschudmachine een elektromechanische poging om een ​​geautomatiseerde, gerandomiseerde "multi-cut multi-riffle shuffle" te bedenken, idealiter zodat de kaarten maar één keer hoeven te worden verwerkt, om de shuffle-tijd kort te houden.

De kaarten in een plankenschudmachine worden snel pseudo-willekeurig "uitgedeeld", één voor één, op een van de N metalen planken in het apparaat (vandaar de naam), en elke keer dat een kaart aan een plank wordt toegevoegd, wordt deze ofwel aan de onderste, of op de top van vorige kaarten laten vallen. (We gaan ervan uit dat het proberen om de kaart tussen twee willekeurige kaarten te steken die al in de stapel zitten, zowel langzamer zou zijn als de kaarten zou beschadigen.)

Nadat alle kaarten aan een plank zijn toegewezen, zodat op elke plank ongeveer 1/Ne van de kaarten staat, worden de kaarten in een pseudo-willekeurige volgorde weer samengevoegd tot een enkele stapel.

Intuïtief, gezien de pseudo-willekeurigheid, zou je verwachten dat extra herschikkingen de algehele willekeur zouden verbeteren, tot op zekere hoogte...

... maar in dit geval, waar de machine 10 planken had, werd de onderzoekers specifiek gevraagd: "Zal één beweging van de machine voldoende zijn om voldoende willekeur te produceren?"

Vermoedelijk wilde het bedrijf voorkomen dat de machine meerdere cycli moest doorlopen om de spelers tevreden te houden en het spel goed te laten verlopen, en de ingenieurs die het apparaat hadden ontworpen, hadden tijdens hun eigen tests geen duidelijk aantoonbare statistische afwijkingen ontdekt.

Maar het bedrijf wilde ervoor zorgen dat het had zijn eigen tests niet doorstaan, simpelweg omdat de tests geschikt waren voor de machine, wat hen een vals gevoel van veiligheid zou geven.

Uiteindelijk ontdekten de onderzoekers niet alleen dat de willekeur nogal mager was, maar ook dat ze precies konden kwantificeren hoe slecht het was, en zo alternatieve tests konden bedenken die het gebrek aan willekeur overtuigend aan het licht brachten.

Ze toonden met name aan dat slechts één doorgang van het apparaat voldoende korte reeksen kaarten in de geschudde uitvoer achterliet dat ze betrouwbaar gemiddeld tussen de 9 en 10 kaarten konden voorspellen wanneer een pakket van 52 geschudde kaarten daarna werd uitgedeeld.

Zoals de onderzoekers schreven:

Met behulp van onze theorie konden we aantonen dat een goed geïnformeerde speler ongeveer 9-en-een-halve kaarten correct kan raden in een enkele reeks door een kaartspel van 52 kaarten. Voor een goed geschud kaartspel krijgt de optimale strategie ongeveer 4 en een halve kaart correct. Deze gegevens hebben het bedrijf wel overtuigd. De theorie suggereerde ook een nuttige remedie.

[...]

De president van het bedrijf antwoordde: "We zijn niet blij met uw conclusies, maar we geloven ze en daarom hebben we u ingehuurd." We stelden een eenvoudig alternatief voor: gebruik de machine twee keer. Dit resulteert in een shuffle die gelijk is aan een machine met 200 planken. Onze wiskundige analyse en verdere tests, die hier niet worden vermeld, laten zien dat dit voldoende willekeurig is.

Wat te doen?

Dit verhaal bevat verschillende "leermomenten", en het is verstandig om van hen te leren, of u nu programmeur of productmanager bent die specifiek worstelt met willekeur, of een SecOps/DevOps/IT/cybersecurity-professional die betrokken is bij cybersecurity assurance in algemeen:

• Het doorstaan ​​van uw eigen tests is niet genoeg. Falen voor je eigen tests is zeker slecht, maar het is gemakkelijk om te eindigen met tests waarvan je verwacht dat je algoritme, product of dienst zal slagen, vooral als je correcties of "bugfixes" worden gemeten aan de hand van het feit of ze je door de tests helpen. Soms heeft u een second opinion nodig en komt die dan uit een objectieve, onafhankelijke bron. Dat onafhankelijke overzicht zou kunnen komen van een geweldig team van wiskundige statistici uit Californië, zoals hier; van een extern “rood team” van penetratietesters; of van een MDR-team (managed detectie en respons) dat met eigen ogen en oren naar uw cyberbeveiligingssituatie kijkt.
• Luisteren naar slecht nieuws is belangrijk. De president van het bedrijf schuifelmachines antwoordde in dit geval perfect toen hij toegaf dat hij ontevreden was over het resultaat, maar dat hij had betaald om de waarheid te achterhalen, niet alleen om te horen wat hij hoopte.
• Cryptografie in het bijzonder, en cyberbeveiliging in het algemeen, is moeilijk. Hulp vragen is geen erkenning van mislukking, maar een erkenning van wat er nodig is om te slagen.
• Willekeur is te belangrijk om aan het toeval over te laten. Het meten van wanorde is niet eenvoudig (de krant lezen om te begrijpen waarom), maar het kan en moet worden gedaan.

---

Gebrek aan tijd of expertise om te zorgen voor respons op cyberbeveiligingsdreigingen? Bezorgd dat cyberbeveiliging u uiteindelijk zal afleiden van alle andere dingen die u moet doen?

Lees verder over Door Sophos beheerde detectie en respons:
24/7 jacht op bedreigingen, detectie en reactie  ▶

---