Sécurité sérieuse : Vous ne pouvez pas battre la maison au Blackjack - ou pouvez-vous le faire ?

Le cryptogourou Bruce Schneier (où Crypto veux dire de la cryptographie, pas autre chose !) vient de publier une note intrigante sur son blog intitulée Sur le caractère aléatoire des mélangeurs de cartes automatiques.

Si vous avez déjà été dans un casino, au moins un au Nevada, vous saurez que les tables de blackjack ne prennent pas de risques avec les clients connus dans le commerce comme compteurs de cartes.

Ce terme est utilisé pour désigner les joueurs qui ont entraîné leur mémoire au point qu'ils peuvent suivre de près les cartes jouées jusqu'à présent dans une main, ce qui leur donne un avantage théorique sur la maison lorsqu'ils prédisent s'ils doivent rester ou frapper comme jouer. progresse.

Les compteurs de cartes peuvent acquérir un avantage même s'ils ne font que garder une trace du rapport entre les 10 cartes (Dix, Valet, Dame et Roi) et les non-10 restant dans le sabot du croupier.

Par exemple, si le croupier est assis avec un As, mais qu'un nombre supérieur à la moyenne de cartes de valeur 10 a déjà été utilisé, alors le croupier a une chance inférieure à la moyenne de faire un blackjack (21 points avec deux cartes, c'est-à-dire As et un sur 10-JQK) et gagnant immédiatement, et une chance supérieure à la moyenne de faire faillite avant d'atteindre le point d'arrêt de 17 et plus.

Si vous pouvez équilibrer les probabilités dans votre tête en temps réel, vous pourrez peut-être modifier vos paris en conséquence et sortir gagnant à long terme.

N'essayez pas réellement cela, du moins au Nevada : le casino risque de vous attraper assez rapidement, car votre schéma de jeu divergera considérablement des choix gagnants les plus éclairés disponibles si vous ne comptez pas les cartes. Vous ne vous retrouverez peut-être pas au tribunal, mais vous serez presque certainement escorté hors des lieux et ne reviendrez plus jamais.

Égaliser les chances

Pour réduire le contrepoids des probabilités dont jouissent les compteurs de cartes (ceux qui ne se sont pas encore fait prendre, du moins), les casinos typiquement :

• Distribuez les mains d'une chaussure chargée de six paquets (jeux) de 52 cartes. Cela signifie que chaque main distribuée fausse moins la distribution restante des cartes que si un seul paquet était utilisé.
• Mélangez le sabot entier de 312 cartes (six paquets) avant chaque main. Pour gagner du temps et dissiper les soupçons du croupier, une machine électromécanique pseudo-aléatoire mélange les cartes directement sur la table, devant tous les joueurs.

Cela soulève immédiatement la question posée par Schneier : à quel point les cartes sont-elles bien mélangées lorsqu'elles sortent de la machine ?

Notamment, avec six nouveaux jeux de cartes, qui arrivent dans un ordre prévisible (par exemple As à Roi de Cœur, As à Roi de Trèfle, Roi à As de Carreau, Roi à As de Pique), combien de commande partielle reste-t-il après le la machine a fait son travail ?

Pourriez-vous « deviner » la prochaine carte hors du sabot mieux que le hasard ne le suggère ?

Un randomiseur entièrement électronique est limité dans sa complexité principalement par la vitesse du processeur qu'il utilise, qui est généralement mesurée en centaines de millions ou milliards d'opérations arithmétiques par seconde.

Mais un mélangeur de cartes électromécanique doit littéralement déplacer les cartes dans la vraie vie.

Il y a évidemment une limite à la rapidité avec laquelle il peut effectuer des fractionnements de packs, des échanges de cartes et des opérations d'entrelacement avant que la vitesse du mécanisme ne commence à endommager les cartes, ce qui signifie qu'il y a une limite à la quantité d'aléatoire (ou, plus précisément, pseudo-aléatoire) que la machine peut introduire avant qu'il ne soit temps de jouer la main suivante.

Mélangez trop peu de temps, et le casino pourrait en fait faciliter les choses pour les compteurs de cartes, s'il y a un biais connu dans la distribution des cartes dès le début.

Mélangez trop longtemps et le jeu sera trop lent, de sorte que les joueurs s'ennuieront et erreront, ce que les casinos essaient désespérément d'éviter.

Le blog de Schneier publie des liens vers un pièce fascinante par la BBC qui décrit comment un mathématicien/magicien appelé Persi Diaconis de l'Université de Stanford, avec Jason Fulman et Susan Holmes, a mené une enquête formelle sur cette même question au début de ce siècle, dans un article intitulé simplement : ANALYSE DES MACHINES DE BALAYAGE DES ÉTAGÈRES DE CASINO.

Niveaux de complexité

De toute évidence, il existe des techniques de brassage qui ne mélangent pas du tout les cartes, comme simplement Coupe le pack en deux parties et en déplaçant la partie inférieure vers le haut.

D'autres techniques conduisent (ou semblent devoir conduire) à un meilleur mélange, par exemple le mélange de fusil, où vous divisez le paquet à peu près en deux, tenez une moitié dans chaque main et "retournez" les deux moitiés ensemble, en les entrelaçant d'une manière pseudo-aléatoire qui alterne entre prendre quelques cartes d'un côté, puis quelques cartes de l'autre .

L'idée est que si vous mélangez plusieurs fois le pack, vous effectuez une séquence pseudo-aléatoire de coupes chaque fois que vous divisez le pack avant chaque riffle, mélangées avec une séquence variable pseudo-aléatoire d'opérations d'entrelacement pseudo-aléatoire impliquant un N-from-the- processus gauche-puis-M-depuis la droite.

Curieusement, cependant, lorsque des mélangeurs humains qualifiés sont impliqués, aucune de ces hypothèses d'imprévisibilité n'est sûre.

Des magiciens habiles et des marchands véreux (Diaconis lui-même est le premier, mais pas le second) peuvent exécuter ce qu'on appelle faro mélangeou mélanges parfaits, où ils font les deux choses suivantes à chaque fois qu'ils fouillent le peloton :

• Divisez les cartes précisément en deux, obtenant ainsi exactement 26 cartes dans chaque main.
• Entrelacez-les parfaitement, en retournant exactement une carte à la fois alternativement de chaque main, à chaque fois.

Diaconis lui-même peut faire des mélanges parfaits (y compris l'habileté rare de le faire avec une seule main pour tenir les deux moitiés du paquet !), et selon la BBC :

[Il] aime démontrer le mélange parfait en prenant un nouveau jeu de cartes et en écrivant le mot ALÉATOIRE au marqueur noir épais sur un côté. Au fur et à mesure qu'il fait son tour de passe-passe avec les cartes, les lettres se mélangent, apparaissant de temps en temps sous une forme fantomatique, comme une image imparfaitement réglée sur un vieux téléviseur. Puis, après avoir fait le huitième et dernier mélange, le mot se rematérialise sur le côté du jeu. Les cartes sont dans leur ordre original exact, de l'as de pique à l'as de cœur.

Deux types de perfection

En fait, il existe deux types de mélange parfait, selon la main à partir de laquelle vous commencez à jouer après avoir coupé les cartes en deux piles de 26 cartes.

Vous pouvez entrelacer les cartes pour qu'elles se retrouvent dans l'ordre 1-27-2-28-3-29-…-25-51-26-52, si la première carte que vous retournez vers le bas provient de la main dans laquelle vous tenez la moitié inférieure du peloton.

Mais si la première carte que vous retournez est la carte du bas de ce qui était auparavant la moitié supérieure du paquet, vous vous retrouvez avec 27-1-28-2-29-3-…-51-25-52-26, donc le la carte juste après la mi-course se retrouve ensuite sur le dessus.

Le premier type est appelé un hors-mélange, et réorganise le pack toutes les huit fois que vous le répétez, comme vous pouvez le voir ici (l'image a 52 lignes de pixels, chaque ligne correspondant au bord d'une carte avec le mot RANDOM écrit dessus avec un marqueur):

Ce dernier type est un en mélangeant, et ceci, étonnamment, prend 52 remaniements avant qu'il ne se répète, bien que vous puissiez voir clairement ici que le pack ne montre jamais vraiment de véritable caractère aléatoire, et passe même par une inversion parfaite à mi-parcours :

Qu'ont dit les mathématiciens ?

Ainsi, en 2013, lorsque Diaconis el al. ont étudié le mélangeur d'étagères à l'invitation du fabricant, qu'ont-ils trouvé ?

Comme l'explique l'article, un mélangeur d'étagères est une tentative électromécanique de conception d'un "mélange multi-coupes multi-riffle" automatisé et aléatoire, idéalement de sorte que les cartes n'aient besoin d'être travaillées qu'une seule fois, pour que le temps de mélange soit court.

Les cartes d'un mélangeur d'étagères sont rapidement "distribuées" de manière pseudo-aléatoire, une à la fois, sur l'une des N étagères métalliques à l'intérieur de l'appareil (d'où le nom), et chaque fois qu'une carte est ajoutée à une étagère, elle est soit glissée en bas ou déposé sur le dessus des cartes précédentes. (Nous supposons qu'essayer de pousser la carte entre deux cartes aléatoires déjà dans la pile serait à la fois plus lent et susceptible d'endommager les cartes.)

Une fois que toutes les cartes ont été affectées à une étagère, de sorte que chaque étagère contienne environ 1/Nième des cartes, les cartes sont réassemblées en une seule pile dans un ordre pseudo-aléatoire.

Intuitivement, étant donné le pseudo-aléatoire impliqué, vous vous attendriez à ce que des remaniements supplémentaires améliorent le caractère aléatoire global, jusqu'à un certain point…

… mais dans ce cas, où la machine avait 10 étagères, on a spécifiquement demandé aux chercheurs, "Est-ce qu'un seul passage de la machine sera suffisant pour produire un caractère aléatoire adéquat?"

Vraisemblablement, la société voulait éviter de faire fonctionner la machine sur plusieurs cycles afin de garder les joueurs heureux et que le jeu se déroule bien, et les ingénieurs qui avaient conçu l'appareil n'avaient détecté aucune anomalie statistique manifestement exploitable lors de leurs propres tests.

Mais l'entreprise voulait s'assurer qu'elle n'avait pas passé ses propres tests simplement parce que les tests convenaient à la machine, ce qui leur donnerait un faux sentiment de sécurité.

En fin de compte, les chercheurs ont découvert non seulement que le caractère aléatoire était plutôt faible, mais aussi qu'ils étaient capables de quantifier exactement à quel point il était faible, et donc de concevoir des tests alternatifs qui ont révélé de manière convaincante l'absence de caractère aléatoire.

En particulier, ils ont montré qu'un seul passage de l'appareil laissait suffisamment de courtes séquences de cartes dans la sortie mélangée pour qu'ils puissent prédire de manière fiable entre 9 et 10 cartes en moyenne lorsqu'un paquet de 52 cartes mélangées était distribué par la suite.

Comme l'ont écrit les chercheurs :

[U]sing notre théorie, nous avons pu montrer qu'un joueur averti pouvait deviner correctement environ 9 cartes et demie en une seule fois dans un jeu de 52 cartes. Pour un jeu bien mélangé, la stratégie optimale obtient environ 4 cartes et demie correctes. Ces données ont convaincu l'entreprise. La théorie suggérait également un remède utile.

[...]

Le président de l'entreprise a répondu : « Nous ne sommes pas satisfaits de vos conclusions, mais nous les croyons et c'est pour cela que nous vous avons embauché. Nous avons proposé une alternative simple : utiliser la machine deux fois. Il en résulte un mélange équivalent à une machine à 200 étagères. Notre analyse mathématique et d'autres tests, non rapportés ici, montrent que cela est suffisamment aléatoire.

Que faire?

Ce conte contient plusieurs "moments propices à l'apprentissage", et il serait sage d'apprendre d'eux, que vous soyez programmeur ou chef de produit luttant spécifiquement contre le hasard vous-même, ou un professionnel SecOps/DevOps/IT/cybersécurité impliqué dans l'assurance de la cybersécurité dans général:

• Passer ses propres tests ne suffit pas. Échouer à vos propres tests est définitivement mauvais, mais il est facile de se retrouver avec des tests que vous attendez de votre algorithme, produit ou service, surtout si vos corrections ou "corrections de bogues" sont mesurées en fonction de leur réussite aux tests. Parfois, vous avez besoin d'un deuxième avis qui provient alors d'une source objective et indépendante. Cette vue d'ensemble indépendante pourrait venir d'une équipe d'élite de statisticiens mathématiciens de Californie, comme ici ; d'une « équipe rouge » externe de testeurs d'intrusion ; ou d'une équipe MDR (détection et réponse gérées) qui apporte ses propres yeux et oreilles à votre situation de cybersécurité.
• Écouter les mauvaises nouvelles est important. Le président de l'entreprise de shuffling machine dans cette affaire a parfaitement répondu lorsqu'il a admis qu'il était mécontent du résultat, mais qu'il avait payé pour découvrir la vérité, pas simplement pour entendre ce qu'il espérait.
• La cryptographie en particulier, et la cybersécurité en général, sont difficiles. Demander de l'aide n'est pas un aveu d'échec mais une reconnaissance de ce qu'il faut pour réussir.
• Le hasard est trop important pour être laissé au hasard. Mesurer le désordre n'est pas facile (lire le journal comprendre pourquoi), mais cela peut et doit être fait.

---

Vous manquez de temps ou d'expertise pour vous occuper de la réponse aux menaces de cybersécurité ? Vous craignez que la cybersécurité finisse par vous distraire de toutes les autres choses que vous devez faire ?

En savoir plus sur Détection et réponse gérées par Sophos:
Recherche, détection et réponse aux menaces 24h/7 et XNUMXj/XNUMX  ▶

---