Ernste Sicherheit: Beim Blackjack kann man nicht das Haus schlagen – oder doch?

Kryptoguru Bruce Schneier (wo Krypto Mittel Geheimschrift, nicht das andere!) hat gerade eine faszinierende Notiz in seinem Blog mit dem Titel veröffentlicht Über die Zufälligkeit automatischer Kartenmischer.

Wenn Sie schon einmal in einem Casino waren, zumindest in einem in Nevada, werden Sie wissen, dass die Blackjack-Tische bei Kunden, die in der Branche als bekannt sind, kein Risiko eingehen Kartenzähler.

Dieser Begriff wird verwendet, um sich auf Spieler zu beziehen, die ihr Gedächtnis so weit trainiert haben, dass sie die bisher in einer Hand gespielten Karten genau verfolgen können, was ihnen einen theoretischen Vorteil gegenüber dem Haus verschafft, wenn sie vorhersagen, ob sie halten oder ziehen sollen fortschreitet.

Kartenzähler können einen Vorteil erlangen, selbst wenn sie nur das Verhältnis von 10-Karten (Zehn, Bube, Dame und König) zu Nicht-10-Karten im Schuh des Dealers verfolgen.

Wenn der Dealer zum Beispiel mit einem Ass sitzt, aber bereits überdurchschnittlich viele 10er-Karten aufgebraucht sind, dann hat der Dealer eine unterdurchschnittliche Chance auf einen Blackjack (21 Punkte mit zwei Karten, d.h Ass und einer von 10-JQK) und sofort zu gewinnen, und eine überdurchschnittliche Chance, pleite zu gehen, bevor der Haltepunkt von 17 und höher erreicht wird.

Wenn Sie die Wahrscheinlichkeiten in Ihrem Kopf in Echtzeit ausbalancieren können, können Sie Ihre Wetten möglicherweise entsprechend anpassen und langfristig die Nase vorn haben.

Versuchen Sie dies nicht wirklich, zumindest in Nevada: Das Casino wird Sie wahrscheinlich ziemlich schnell erwischen, da Ihr Spielmuster deutlich von den am besten informierten Gewinnmöglichkeiten abweichen wird, wenn Sie keine Karten zählen. Sie werden vielleicht nicht vor Gericht landen, aber Sie werden mit ziemlicher Sicherheit vom Gelände eskortiert und nie wieder hineingelassen.

Nivellierung der Chancen

Um das Gegengewicht der Wahrscheinlichkeiten zu verringern, die Kartenzähler genießen (zumindest diejenigen, die noch nicht erwischt wurden), gehen die Casinos typischerweise so vor:

• Geben Sie Hände aus einem Schuh, der mit sechs Packungen (Decks) mit 52 Karten gefüllt ist. Dies bedeutet, dass jede ausgeteilte Hand die verbleibende Verteilung der Karten weniger verzerrt, als wenn ein einzelnes Paket verwendet würde.
• Mischen Sie vor jeder Hand den gesamten Schuh mit 312 Karten (Six Packs). Um Zeit zu sparen und den Dealer von Verdacht zu befreien, mischt eine pseudozufällige elektromechanische Maschine die Karten direkt auf dem Tisch, vor allen Spielern.

Da stellt sich sofort die Frage von Schneier: Wie gut sind die Karten gemischt, wenn sie aus der Maschine kommen?

Bei sechs neuen Kartenspielen, die in einer vorhersehbaren Reihenfolge eintreffen (z. B. Ass zu Herz-König, Ass zu Kreuz-König, König zu Karo-As, König zu Pik-As), wie viel Teilreihenfolge nach dem Spiel übrig bleibt Maschine hat ihre Arbeit getan?

Könnten Sie die nächste Karte aus dem Schuh besser „erraten“, als es der Zufall vermuten lässt?

Ein vollelektronischer Randomizer ist in seiner Komplexität hauptsächlich durch die Geschwindigkeit der verwendeten CPU begrenzt, die typischerweise in Hunderten von Millionen oder Milliarden arithmetischer Operationen pro Sekunde gemessen wird.

Aber ein elektromechanischer Kartenmischer muss die Karten im wirklichen Leben buchstäblich bewegen.

Es gibt offensichtlich eine Grenze dafür, wie schnell es Pack-Splits, Kartentausch und Interleaving-Operationen durchführen kann, bevor die Geschwindigkeit des Mechanismus beginnt, die Karten zu beschädigen, was bedeutet, dass es eine Grenze dafür gibt, wie viel Zufälligkeit (oder genauer gesagt Pseudozufälligkeit) kann die Maschine einführen, bevor es Zeit ist, die nächste Hand zu spielen.

Mischen Sie zu kurz, und das Casino könnte es den Kartenzählern tatsächlich erleichtern, wenn es von Anfang an eine bekannte Voreingenommenheit bei der Verteilung der Karten gibt.

Mischen Sie zu lange, und das Spiel wird zu langsam sein, so dass sich die Spieler langweilen und abwandern, etwas, das Casinos verzweifelt versuchen zu vermeiden.

Schneiers Blog postet Links zu a faszinierendes Stück von der BBC, die beschreibt, wie ein Mathematiker/Zauberer namens Persi Diaconis von der Stanford University, zusammen mit Jason Fulman und Susan Holmes, Anfang dieses Jahrhunderts eine formelle Untersuchung genau dieses Themas durchführte, in einem Artikel mit dem einfachen Titel: ANALYSE VON CASINO SHELF SHUFFLING MASCHINEN.

Komplexitätsstufen

Natürlich gibt es einige Mischtechniken, die die Karten überhaupt nicht durcheinander bringen, wie z. B. einfach Schneiden die Packung in zwei Teile zerlegen und den unteren Teil nach oben bewegen.

Andere Techniken führen (oder fühlen sich an, als ob sie dazu führen sollten) zu einem besseren Mischen, zum Beispiel dem Riffle-Shuffle, wo Sie die Packung grob in zwei Hälften teilen, eine Hälfte in jeder Hand halten und die beiden Hälften „umdrehen“, indem Sie sie pseudozufällig verschachteln, indem Sie abwechselnd ein paar Karten von einer Seite und dann ein paar Karten von der anderen nehmen .

Die Idee ist, dass Sie, wenn Sie das Paket mehrmals riffle-mischen, jedes Mal, wenn Sie das Paket teilen, vor jedem Riffle eine pseudozufällige Folge von Schnitten ausführen, gemischt mit einer pseudozufällig variablen Folge von pseudozufälligen Verschachtelungsoperationen, die ein N-aus-dem- Links-dann-M-von-rechts-Prozess.

Faszinierenderweise ist jedoch keine dieser Annahmen der Unvorhersehbarkeit sicher, wenn erfahrene menschliche Mischer beteiligt sind.

Geschickte Zauberer und krumme Händler (Diaconis selbst ist der erstere, aber nicht der letztere) können das ausführen, was als bekannt ist Faro mischt, oder perfektes Mischen, wo sie jedes Mal, wenn sie das Rudel durchsuchen, die beiden folgenden Dinge tun:

• Teilen Sie die Karten genau in zwei Teile, Dadurch erhält er genau 26 Karten in jeder Hand.
• Verschränke sie perfekt, indem Sie jedes Mal abwechselnd genau eine Karte aus jeder Hand aufdecken.

Diaconis selbst kann perfekt mischen (einschließlich der seltenen Fähigkeit, dies mit nur einer Hand zu tun, um beide Hälften des Rudels zu halten!), und laut BBC:

[Er] demonstriert gerne das perfekte Mischen, indem er ein neues Kartenspiel nimmt und das Wort RANDOM mit einem dicken schwarzen Marker auf eine Seite schreibt. Während er mit den Karten spielt, geraten die Buchstaben durcheinander und erscheinen hin und wieder in gespenstischer Form, wie ein unvollkommen abgestimmtes Bild auf einem alten Fernseher. Dann, nachdem er das achte und letzte Mischen gemacht hat, erscheint das Wort wieder an der Seite des Decks. Die Karten sind in ihrer exakten ursprünglichen Reihenfolge, vom Pik-As bis zum Herz-Ass.

Zwei Arten von Perfektion

Tatsächlich gibt es zwei Arten von perfektem Mischen, je nachdem, von welcher Hand Sie mit dem Riffling beginnen, nachdem Sie die Karten in zwei 26-Karten-Stapel aufgeteilt haben.

Sie können die Karten so verschachteln, dass sie in der Reihenfolge 1-27-2-28-3-29-…-25-51-26-52 enden, wenn die erste Karte, die Sie nach unten drehen, aus der Hand stammt, die Sie halten Die untere Hälfte der Packung.

Aber wenn die erste Karte, die Sie umdrehen, die unterste Karte der zuvor oberen Hälfte des Stapels ist, erhalten Sie am Ende 27-1-28-2-29-3-…-51-25-52-26, also die Karte kurz nach der Hälfte landet danach oben.

Der erstere Typ heißt an herausmischen, und ordnet das Paket alle acht Male neu, wenn Sie es wiederholen, wie Sie hier sehen können (das Bild hat 52 Pixelzeilen, jede Zeile entspricht dem Rand einer Karte, auf der mit einem Markierungsstift das Wort RANDOM geschrieben ist):

Letzterer Typ ist ein in-shuffle, und dies dauert erstaunlicherweise 52 Neumischungen, bevor es sich wiederholt, obwohl Sie hier deutlich sehen können, dass das Rudel nie wirkliche Zufälligkeiten zeigt und sogar eine perfekte Umkehrung auf halbem Weg durchläuft:

Was haben die Mathematiker gesagt?

Also, damals im Jahr 2013, als Diaconis el al. hat die Regalmischmaschine auf Einladung des Herstellers untersucht, was haben sie herausgefunden?

Wie das Papier erklärt, ist ein Regalmischer ein elektromechanischer Versuch, einen automatisierten, zufälligen „Multi-Cut-Multi-Riffle-Shuffle“ zu entwickeln, idealerweise so, dass die Karten nur einmal durchgearbeitet werden müssen, um die Mischzeit kurz zu halten.

Die Karten in einem Regalmischer werden pseudozufällig, eine nach der anderen, schnell auf eines von N Metallregalen im Inneren des Geräts (daher der Name) „ausgeteilt“, und jedes Mal, wenn eine Karte zu einem Regal hinzugefügt wird, wird sie entweder hineingeschoben unten oder auf die Oberseite vorheriger Karten fallen gelassen. (Wir gehen davon aus, dass der Versuch, die Karte zwischen zwei zufällige Karten zu stecken, die sich bereits im Stapel befinden, sowohl langsamer als auch anfälliger für die Beschädigung der Karten wäre.)

Nachdem alle Karten einem Regal zugewiesen wurden, so dass jedes Regal etwa 1/N der Karten darauf hat, werden die Karten in einer pseudozufälligen Reihenfolge wieder zu einem einzigen Stapel zusammengesetzt.

In Anbetracht der damit verbundenen Pseudozufälligkeit würde man intuitiv erwarten, dass zusätzliche Neumischungen die Gesamtzufälligkeit bis zu einem gewissen Punkt verbessern würden …

…aber in diesem Fall, wo die Maschine 10 Regale hatte, wurden die Forscher speziell gefragt, „Wird ein Durchlauf der Maschine ausreichen, um eine angemessene Zufälligkeit zu erzeugen?“

Vermutlich wollte das Unternehmen vermeiden, die Maschine durch mehrere Zyklen laufen zu lassen, um die Spieler bei Laune zu halten und das Spiel gut fließen zu lassen, und die Ingenieure, die das Gerät entwickelt hatten, hatten bei ihren eigenen Tests keine offensichtlich ausnutzbaren statistischen Anomalien entdeckt.

Das wollte das Unternehmen aber sicherstellen hatte seine eigenen Tests nicht bestanden, einfach weil die Tests für die Maschine geeignet waren, was ihnen ein falsches Gefühl der Sicherheit geben würde.

Letztendlich stellten die Forscher nicht nur fest, dass die Zufälligkeit ziemlich schlecht war, sondern sie konnten auch genau quantifizieren, wie schlecht sie war, und so alternative Tests entwickeln, die den Mangel an Zufälligkeit überzeugend aufzeigten.

Insbesondere zeigten sie, dass nur ein Durchgang des Geräts ausreichend viele kurze Kartenfolgen in der gemischten Ausgabe hinterließ, dass sie im Durchschnitt zwischen 9 und 10 Karten zuverlässig vorhersagen konnten, wenn ein Paket von 52 gemischten Karten anschließend ausgeteilt wurde.

Wie die Forscher schrieben:

[Anhand unserer Theorie konnten wir zeigen, dass ein sachkundiger Spieler in einem einzigen Durchlauf durch ein 9-Karten-Deck ungefähr 52 Karten richtig erraten konnte. Für ein gut gemischtes Deck sind mit der optimalen Strategie etwa 4 Karten richtig. Diese Daten haben das Unternehmen überzeugt. Die Theorie schlug auch ein nützliches Heilmittel vor.

[...]

Der Präsident des Unternehmens antwortete: „Wir sind mit Ihren Schlussfolgerungen nicht zufrieden, aber wir glauben ihnen und dafür haben wir Sie eingestellt.“ Wir haben eine einfache Alternative vorgeschlagen: Verwenden Sie die Maschine zweimal. Dies führt zu einem Mischen, das einer Maschine mit 200 Fächern entspricht. Unsere mathematische Analyse und weitere Tests, die hier nicht berichtet werden, zeigen, dass dies hinreichend zufällig ist.

Was ist zu tun?

Diese Geschichte enthält mehrere „lehrbare Momente“, und es wäre ratsam, daraus zu lernen, egal ob Sie Programmierer oder Produktmanager sind, der selbst speziell mit Zufälligkeiten ringt, oder ein SecOps/DevOps/IT/Cybersecurity-Experte, der an der Sicherung der Cybersicherheit beteiligt ist Allgemeines:

• Das Bestehen eigener Tests reicht nicht aus. Bei eigenen Tests durchzufallen ist definitiv schlecht, aber es ist leicht, Tests zu erhalten, von denen Sie erwarten, dass Ihr Algorithmus, Ihr Produkt oder Ihre Dienstleistung besteht, insbesondere wenn Ihre Korrekturen oder „Bugfixes“ daran gemessen werden, ob sie Sie durch die Tests bringen. Manchmal benötigen Sie eine zweite Meinung, die dann von einer objektiven, unabhängigen Quelle stammt. Dieser unabhängige Überblick könnte wie hier von einem erstklassigen Team mathematischer Statistiker aus Kalifornien stammen; von einem externen „roten Team“ von Penetrationstestern; oder von einer MDR-Crew (Managed Detection and Response), die ihre eigenen Augen und Ohren in Ihre Cybersicherheitssituation einbringt.
• Es ist wichtig, schlechte Nachrichten zu hören. Der Präsident der Mischmaschinenfirma antwortete in diesem Fall perfekt, als er zugab, dass er mit dem Ergebnis unzufrieden war, aber dass er bezahlt hatte, um die Wahrheit aufzudecken, und nicht nur, um zu hören, was er hoffte.
• Kryptographie im Besonderen und Cybersicherheit im Allgemeinen sind schwierig. Um Hilfe zu bitten ist kein Eingeständnis des Versagens, sondern eine Anerkennung dessen, was es braucht, um erfolgreich zu sein.
• Zufälligkeit ist zu wichtig, um sie dem Zufall zu überlassen. Unordnung zu messen ist nicht einfach (die Zeitung lesen zu verstehen, warum), aber es kann und sollte getan werden.

---

Fehlt Ihnen die Zeit oder das Fachwissen, um sich um die Reaktion auf Cybersicherheitsbedrohungen zu kümmern? Befürchten Sie, dass die Cybersicherheit Sie am Ende von all den anderen Dingen ablenken wird, die Sie tun müssen?

Erfahren Sie mehr darüber Sophos Managed Detection and Response:
Bedrohungssuche, -erkennung und -reaktion rund um die Uhr  ▶

---