Seguridad Seria: No puedes vencer a la casa en el Blackjack, ¿o sí?

El criptogurú Bruce Schneier (donde cripto significa criptografía, no lo otro!) acaba de publicar una intrigante nota en su blog titulada Sobre la aleatoriedad de los barajadores automáticos de cartas.

Si alguna vez ha estado en un casino, al menos uno en Nevada, sabrá que las mesas de blackjack no se arriesgan con clientes conocidos en el comercio como contadores de cartas.

Ese término se usa para referirse a los jugadores que han entrenado su memoria hasta el punto de que pueden seguir de cerca las cartas jugadas hasta el momento en una mano, lo que les da una ventaja teórica sobre la casa al predecir si plantarse o pedir como jugada. progresa

Los contadores de cartas pueden adquirir una ventaja incluso si todo lo que hacen es realizar un seguimiento de la proporción de 10 cartas (Diez, Jota, Reina y Rey) a las que no son 10 que quedan en el zapato del crupier.

Por ejemplo, si el crupier está sentado con un As, pero ya se ha usado un número superior al promedio de cartas de valor 10, entonces el crupier tiene una probabilidad inferior al promedio de hacer un blackjack (21 puntos con dos cartas, es decir, As y uno de 10-JQK) y ganando a la vez, y una probabilidad superior a la media de pasarse antes de llegar al punto de parada de 17 y más.

Si puede equilibrar las probabilidades en su cabeza en tiempo real, entonces podrá modificar sus apuestas en consecuencia y salir ganando a largo plazo.

En realidad, no intente esto, al menos en Nevada: es probable que el casino lo atrape bastante rápido, porque su patrón de juego divergirá notablemente de las opciones ganadoras más informadas disponibles si no está contando cartas. Es posible que no termine en la corte, pero es casi seguro que lo escoltarán fuera de las instalaciones y nunca más lo dejarán entrar.

Nivelando las probabilidades

Para reducir el contrapeso de probabilidades que disfrutan los contadores de cartas (aquellos que aún no han sido atrapados, al menos), los casinos típicamente:

• Reparte manos desde un zapato cargado con seis paquetes (mazos) de 52 cartas. Esto significa que cada mano repartida sesga menos la distribución restante de cartas que si se usara un solo paquete.
• Baraja todo el zapato de 312 cartas (paquetes de seis) antes de cada mano. Para ahorrar tiempo y quitar sospechas al crupier, una máquina electromecánica pseudoaleatoria baraja las cartas directamente sobre la mesa, frente a todos los jugadores.

Eso plantea de inmediato la pregunta planteada por Schneier: ¿qué tan bien barajadas están las cartas cuando salen de la máquina?

En particular, con seis nuevos paquetes de cartas, que llegan en un orden predecible (por ejemplo, as a rey de corazones, as a rey de tréboles, rey a as de diamantes, rey a as de picas), ¿cuánto orden parcial queda después de la máquina ha hecho su trabajo?

¿Podrías "adivinar" la siguiente carta que sale del zapato mejor de lo que sugiere el azar?

Un aleatorizador totalmente electrónico está limitado en su complejidad principalmente por la velocidad de la CPU que utiliza, que normalmente se mide en cientos de millones o miles de millones de operaciones aritméticas por segundo.

Pero un barajador de cartas electromecánico literalmente tiene que mover las cartas en la vida real.

Obviamente, hay un límite en la rapidez con la que puede realizar divisiones de paquetes, intercambios de cartas y operaciones de entrelazado antes de que la velocidad del mecanismo comience a dañar las cartas, lo que significa que hay un límite en la cantidad de aleatoriedad (o, más precisamente, pseudoaleatoriedad) que la máquina puede introducir antes de que llegue el momento de jugar la siguiente mano.

Si se baraja durante un tiempo demasiado corto, el casino podría facilitar las cosas para los contadores de cartas, si existe un sesgo conocido en la distribución de las cartas desde el principio.

Baraja durante demasiado tiempo y el juego será demasiado lento, por lo que los jugadores se aburrirán y se alejarán, algo que los casinos tratan de evitar desesperadamente.

El blog de Schneier publica enlaces a un pieza fascinante por la BBC que describe cómo un matemático/mago llamado Persi Diaconis de la Universidad de Stanford, junto con Jason Fulman y Susan Holmes, llevaron a cabo una investigación formal sobre este mismo tema a principios de este siglo, en un artículo titulado simplemente: ANÁLISIS DE LAS MÁQUINAS BARAJADAS DE ESTANTERÍAS DE CASINO.

Niveles de complejidad

Claramente, hay algunas técnicas de barajar que no mezclan mucho las cartas, como simplemente corte el paquete en dos partes y moviendo la parte inferior hacia la parte superior.

Otras técnicas resultan (o se siente como si debieran resultar) en una mejor mezcla, por ejemplo, el mezcla rápida, donde divide el paquete aproximadamente por la mitad, sostiene una mitad en cada mano y "voltea" las dos mitades, intercalándolas de una manera pseudoaleatoria que alterna entre tomar algunas cartas de un lado y luego algunas cartas del otro .

La idea es que si mezclas el paquete varias veces, realizas una secuencia pseudoaleatoria de cortes cada vez que divides el paquete antes de cada cambio, mezcladas con una secuencia variable pseudoaleatoria de operaciones entrelazadas pseudoaleatorias que involucran una N-de-la- proceso de izquierda-luego-M-desde-la-derecha.

Curiosamente, sin embargo, cuando se trata de hábiles barajadores humanos, ninguna de esas suposiciones de imprevisibilidad es segura.

Los magos diestros y los traficantes corruptos (el propio Diaconis es el primero, pero no el segundo) pueden realizar lo que se conoce como Faro barajao mezclas perfectas, donde hacen las dos cosas siguientes cada vez que revisan el paquete:

• Partir las cartas precisamente en dos, obteniendo así exactamente 26 cartas en cada mano.
• intercalarlos perfectamente, volteando hacia abajo exactamente una carta a la vez alternativamente de cada mano, cada vez.

El propio Diaconis puede hacer mezclas perfectas (¡incluida la rara habilidad de hacerlo con una sola mano para sostener ambas mitades del paquete!), y según la BBC:

[A él] le gusta demostrar el barajado perfecto tomando una nueva baraja de cartas y escribiendo la palabra ALEATORIO en un marcador negro grueso en un lado. A medida que realiza su juego de manos con las cartas, las letras se mezclan, apareciendo de vez en cuando en forma fantasmal, como una imagen imperfectamente sintonizada en un viejo televisor. Luego, después de barajar por octava y última vez, la palabra vuelve a materializarse en el lateral de la baraja. Las cartas están en su secuencia original exacta, desde el As de Picas hasta el As de Corazones.

Dos tipos de perfección

De hecho, hay dos tipos de barajado perfecto, según la mano con la que empieces a barajar después de dividir las cartas en dos pilas de 26 cartas.

Puede intercalar las cartas para que terminen en la secuencia 1-27-2-28-3-29-…-25-51-26-52, si la primera carta que voltea hacia abajo proviene de la mano que tiene. Él parte inferior de la mitad del paquete.

Pero si la primera carta que volteas hacia abajo es la carta inferior de lo que antes era la mitad superior del paquete, terminas con 27-1-28-2-29-3-…-51-25-52-26, por lo que el la tarjeta justo después de la mitad termina arriba después.

El primer tipo se llama barajar, y reordena el paquete cada ocho veces que lo repites, como puedes ver aquí (la imagen tiene 52 líneas de píxeles, cada línea corresponde al borde de una tarjeta con la palabra ALEATORIO escrita con un rotulador):

Este último tipo es un al azar, y esto, sorprendentemente, requiere 52 reorganizaciones antes de que se repita, aunque puedes ver claramente aquí que el paquete nunca muestra verdadera aleatoriedad, e incluso pasa por una inversión perfecta a la mitad:

¿Qué dijeron los matemáticos?

Entonces, allá por 2013, cuando Diaconis el al. estudiaron la máquina barajadora de estantes por invitación del fabricante, ¿qué encontraron?

Tal como lo explica el documento, un barajador de estantes es un intento electromecánico de diseñar un "barajador de múltiples cortes" automático y aleatorio, idealmente para que las cartas solo deban trabajarse una vez, para que el tiempo de barajado sea corto.

Las cartas en un barajador de estantes se "reparten" rápidamente de forma pseudoaleatoria, una a la vez, en uno de los N estantes metálicos dentro del dispositivo (de ahí el nombre), y cada vez que se agrega una tarjeta a un estante, se desliza en el abajo, o se dejó caer en la parte superior de las tarjetas anteriores. (Suponemos que intentar meter la carta entre dos cartas aleatorias que ya están en la pila sería más lento y propenso a dañar las cartas).

Una vez que todas las cartas se han asignado a un estante, de modo que cada estante tenga aproximadamente 1/N de las cartas, las cartas se vuelven a ensamblar en una sola pila en un orden pseudoaleatorio.

Intuitivamente, dada la pseudoaleatoriedad involucrada, esperaría que las reorganizaciones adicionales mejoraran la aleatoriedad general, hasta cierto punto...

…pero en este caso, donde la máquina tenía 10 estantes, se les preguntó específicamente a los investigadores, "¿Será suficiente una pasada de la máquina para producir la aleatoriedad adecuada?"

Presuntamente, la compañía quería evitar ejecutar la máquina a través de múltiples ciclos para mantener contentos a los jugadores y que el juego fluya bien, y los ingenieros que diseñaron el dispositivo no detectaron ninguna anomalía estadística obviamente explotable durante sus propias pruebas.

Pero la compañía quería asegurarse de que no había pasado sus propias pruebas simplemente porque las pruebas se adaptaban a la máquina, lo que les daría una falsa sensación de seguridad.

En última instancia, los investigadores encontraron no solo que la aleatoriedad era bastante pobre, sino que también pudieron cuantificar exactamente cuán pobre era y, por lo tanto, diseñar pruebas alternativas que revelaron de manera convincente la falta de aleatoriedad.

En particular, demostraron que solo una pasada del dispositivo dejaba suficientes secuencias cortas de cartas en la salida barajada como para poder predecir de manera confiable entre 9 y 10 cartas en promedio cuando se repartía un paquete de 52 cartas barajadas después.

Como escribieron los investigadores:

[U]sando nuestra teoría, pudimos demostrar que un jugador experto podía adivinar aproximadamente 9 cartas y media correctamente en una sola pasada a través de una baraja de 52 cartas. Para un mazo bien barajado, la estrategia óptima es obtener aproximadamente 4 cartas y media correctas. Este dato convenció a la empresa. La teoría también sugirió un remedio útil.

[...]

El presidente de la empresa respondió: “No estamos contentos con sus conclusiones, pero las creemos y para eso lo contratamos”. Sugerimos una alternativa simple: usar la máquina dos veces. Esto da como resultado una reproducción aleatoria equivalente a una máquina de 200 estantes. Nuestro análisis matemático y otras pruebas, que no se informan aquí, muestran que esto es adecuadamente aleatorio.

¿Qué hacer?

Esta historia contiene varios "momentos de enseñanza", y sería prudente aprender de ellos, ya sea que sea un programador o un gerente de producto que lucha específicamente con la aleatoriedad, o un profesional de SecOps/DevOps/TI/seguridad cibernética que esté involucrado en la garantía de seguridad cibernética en general:

• Pasar tus propias pruebas no es suficiente. Reprobar sus propias pruebas definitivamente es malo, pero es fácil terminar con pruebas que espera que pase su algoritmo, producto o servicio, especialmente si sus correcciones o "correcciones de errores" se miden por si lo ayudaron a pasar las pruebas. A veces, necesita una segunda opinión que provenga de una fuente independiente y objetiva. Esa visión general independiente podría provenir de un excelente equipo de estadísticos matemáticos de California, como aquí; de un "equipo rojo" externo de probadores de penetración; o de un equipo de MDR (detección y respuesta gestionadas) que aportan sus propios ojos y oídos a su situación de ciberseguridad.
• Escuchar las malas noticias es importante. El presidente de la empresa de máquinas barajadoras en este caso respondió perfectamente cuando admitió que estaba disgustado con el resultado, pero que había pagado para descubrir la verdad, no simplemente para escuchar lo que esperaba.
• La criptografía en particular y la ciberseguridad en general son difíciles. Pedir ayuda no es una admisión de fracaso sino un reconocimiento de lo que se necesita para tener éxito.
• La aleatoriedad es demasiado importante para dejarla al azar. Medir el desorden no es fácil (Lee el papel entender por qué), pero puede y debe hacerse.

---

¿Le falta tiempo o experiencia para encargarse de la respuesta a amenazas de ciberseguridad? ¿Le preocupa que la seguridad cibernética termine distrayéndolo de todas las otras cosas que debe hacer?

Aprenda más sobre Detección y respuesta gestionadas por Sophos:
Búsqueda, detección y respuesta de amenazas las 24 horas del día, los 7 días de la semana  ▶

---