Sicurezza seria: non puoi battere la casa al Blackjack – o puoi?

Il criptoguru Bruce Schneier (dove crypto si intende crittografia, non l'altra cosa!) ha appena pubblicato una nota intrigante sul suo blog dal titolo Sulla casualità dei mescolatori automatici di carte.

Se sei mai stato in un casinò, almeno uno in Nevada, saprai che i tavoli del blackjack non corrono rischi con clienti conosciuti nel settore come contatori delle carte.

Questo termine è usato per riferirsi a giocatori che hanno allenato la loro memoria al punto da poter tenere traccia delle carte giocate fino a quel momento in una mano, il che dà loro un vantaggio teorico rispetto al banco nel prevedere se stare o chiedere carta durante il gioco. progredisce.

I contatori di carte possono acquisire un vantaggio anche se tutto ciò che fanno è tenere traccia del rapporto tra 10 carte (dieci, fante, regina e re) e carte non 10 rimaste nella scarpa del banco.

Ad esempio, se il dealer è seduto con un asso, ma è già stato utilizzato un numero superiore alla media di carte di valore 10, il dealer ha una probabilità inferiore alla media di realizzare un blackjack (21 punti con due carte, ovvero Asso e uno di 10-JQK) e vincere subito, e una probabilità superiore alla media di sballare prima di raggiungere il punto fermo di 17 e oltre.

Se riesci a bilanciare le probabilità nella tua testa in tempo reale, allora potresti essere in grado di modificare le tue scommesse di conseguenza e ottenere un vantaggio a lungo termine.

In realtà non provatelo, almeno in Nevada: è probabile che il casinò vi coglierà di sorpresa abbastanza rapidamente, perché il vostro schema di gioco divergerà notevolmente dalle scelte vincenti più informate disponibili se non contate le carte. Potresti non finire in tribunale, ma quasi sicuramente verrai scortato fuori dai locali e non ti farò mai più rientrare.

Livellare le probabilità

Per ridurre il controbilanciamento delle probabilità di cui godono i contatori di carte (almeno quelli che non sono stati ancora scoperti), i casinò in genere:

• Distribuisci le mani da un sabot carico con sei mazzi (mazzi) da 52 carte. Ciò significa che ogni mano distribuita distorce la distribuzione rimanente delle carte in misura minore rispetto a quanto accadrebbe se venisse utilizzato un singolo mazzo.
• Mescola l'intero sabot da 312 carte (sei mazzi) prima di ogni mano. Per risparmiare tempo e allontanare i sospetti del dealer, una macchina elettromeccanica pseudocasuale mescola le carte direttamente sul tavolo, davanti a tutti i giocatori.

Ciò solleva immediatamente la domanda posta da Schneier: quanto sono ben mescolate le carte quando escono dalla macchina?

In particolare, con sei nuovi mazzi di carte, che arrivano in un ordine prevedibile (ad esempio, dall'asso al re di cuori, dall'asso al re di fiori, dal re all'asso di quadri, dal re all'asso di picche), quanto ordine parziale rimane dopo il la macchina ha fatto il suo lavoro?

Potresti “indovinare” la prossima carta estratta dal sabot meglio di quanto suggerisce il caso?

Un randomizzatore completamente elettronico è limitato nella sua complessità principalmente dalla velocità della CPU che utilizza, che viene tipicamente misurata in centinaia di milioni o miliardi di operazioni aritmetiche al secondo.

Ma un mescolatore di carte elettromeccanico deve letteralmente spostare le carte nella vita reale.

C'è ovviamente un limite alla velocità con cui può eseguire divisioni dei pacchetti, scambi di carte e operazioni di interleaving prima che la velocità del meccanismo inizi a danneggiare le carte, il che significa che c'è un limite a quanta casualità (o, più precisamente, pseudocasualità) la macchina può introdurre prima che sia il momento di giocare la mano successiva.

Mescola per un tempo troppo breve e il casinò potrebbe effettivamente rendere le cose più facili per i contatori di carte, se c'è un noto pregiudizio nella distribuzione delle carte fin dall'inizio.

Mescola troppo a lungo e il gioco sarà troppo lento, tanto che i giocatori si annoieranno e si allontaneranno, qualcosa che i casinò cercano disperatamente di evitare.

I post del blog di Schneier si collegano a a pezzo affascinante dalla BBC che descrive come un matematico/mago chiamato Persi Diaconis dell’Università di Stanford, insieme a Jason Fulman e Susan Holmes, condusse un’indagine formale proprio su questo problema all’inizio di questo secolo, in un articolo intitolato semplicemente: ANALISI DELLE MACCHINE PER MESCOLARE GLI SCAFFALI DEI CASINÒ.

Livelli di complessità

Chiaramente, ci sono alcune tecniche di mescolamento che non mescolano molto le carte, come semplicemente taglio il pacco in due parti e spostando la parte inferiore verso l'alto.

Altre tecniche portano (o sembrano come se dovessero portare) a un migliore mixaggio, ad esempio il rimescolamento, dove dividi il mazzo all'incirca a metà, tieni una metà in ciascuna mano e "giri" le due metà insieme, intercalandole in un modo pseudocasuale che alterna il prendere alcune carte da un lato, poi alcune carte dall'altro .

L'idea è che se si mescola il pacchetto più volte, si esegue una sequenza pseudocasuale di tagli ogni volta che si divide il pacchetto prima di ogni riffle, mescolati insieme con una sequenza pseudocasuale variabile di operazioni di interleaving pseudocasuali che coinvolgono un N-from-the- processo da sinistra e poi M da destra.

Curiosamente, tuttavia, quando sono coinvolti abili mescolatori umani, nessuno di questi presupposti di imprevedibilità è sicuro.

Maghi abili e trafficanti disonesti (Diaconis stesso è il primo, ma non il secondo) possono eseguire ciò che è noto come faro mescola, o mescolamenti perfetti, dove fanno entrambe le cose seguenti ogni volta che rimescolano il pacchetto:

• Dividi le carte esattamente in due, ottenendo così esattamente 26 carte in ogni mano.
• Interlacciateli perfettamente, girando esattamente una carta alla volta alternativamente da ciascuna mano, ogni singola volta.

Lo stesso Diaconis può mescolare perfettamente (inclusa la rara abilità di farlo con una sola mano per tenere entrambe le metà del mazzo!), e secondo la BBC:

A [Lui] piace dimostrare la mescolanza perfetta prendendo un nuovo mazzo di carte e scrivendo la parola RANDOM con uno spesso pennarello nero su un lato. Mentre esegue il suo gioco di prestigio con le carte, le lettere si confondono, apparendo di tanto in tanto in forma spettrale, come un'immagine non perfettamente sintonizzata su un vecchio televisore. Poi, dopo aver mescolato l'ottavo e ultimo, la parola si rimaterializza sul lato del mazzo. Le carte sono nella loro esatta sequenza originale, dall'asso di picche all'asso di cuori.

Due tipi di perfezione

In effetti, ci sono due tipi di mescolamento perfetto, a seconda della mano da cui inizi a sfogliare dopo aver tagliato le carte in due pile da 26 carte.

Puoi intercalare le carte in modo che finiscano nella sequenza 1-27-2-28-3-29-…-25-51-26-52, se la prima carta che giri verso il basso proviene dalla mano che hai in mano la metà inferiore del pacchetto.

Ma se la prima carta che giri è l'ultima carta di quella che prima era la metà superiore del mazzo, ti ritroverai con 27-1-28-2-29-3-…-51-25-52-26, quindi il la carta appena passata la metà finisce in cima in seguito.

Il primo tipo è chiamato an fuori mescolamento, e riordina il mazzo ogni otto volte che lo ripeti, come puoi vedere qui (l'immagine ha 52 linee di pixel, ciascuna linea corrisponde al bordo di una carta su cui è scritta la parola RANDOM con un pennarello):

Quest'ultimo tipo è un in ordine casuale, e questo, sorprendentemente, richiede 52 rimescolamenti prima di ripetersi, anche se puoi vedere chiaramente qui che il mazzo non mostra mai alcuna vera casualità, e passa anche attraverso una perfetta inversione a metà:

Cosa hanno detto i matematici?

Così, nel 2013, quando Diaconis el al. hanno studiato la macchina mescolatrice di scaffali su invito del produttore, cosa hanno trovato?

Come spiega l'articolo, uno scaffale mescolatore è un tentativo elettromeccanico di ideare un "mescolamento multi-riffle multi-taglio" automatizzato e randomizzato, idealmente in modo che le carte debbano essere elaborate solo una volta, per mantenere breve il tempo di mescolamento.

Le carte in uno scaffale mescolatore vengono rapidamente "distribuite" in modo pseudocasuale, una alla volta, su uno degli N ripiani metallici all'interno del dispositivo (da cui il nome), e ogni volta che una carta viene aggiunta a uno scaffale viene fatta scivolare all'interno in basso o lasciato cadere in cima alle carte precedenti. (Partiamo dal presupposto che provare a infilare la carta tra due carte casuali già nella pila sarebbe più lento e incline a danneggiare le carte.)

Dopo che tutte le carte sono state assegnate a uno scaffale, in modo che ogni scaffale contenga circa 1/N delle carte, le carte vengono riassemblate in un'unica pila in ordine pseudocasuale.

Intuitivamente, data la pseudocasualità coinvolta, ci si aspetterebbe che ulteriori rimescolamenti migliorassero la casualità complessiva, fino a un certo punto...

…ma in questo caso, dove la macchina aveva 10 ripiani, ai ricercatori è stato chiesto espressamente: “Un passaggio della macchina sarà sufficiente per produrre un’adeguata casualità?”

Presumibilmente, l'azienda voleva evitare di far funzionare la macchina attraverso più cicli per mantenere i giocatori felici e il gioco scorreva bene, e gli ingegneri che avevano progettato il dispositivo non avevano rilevato alcuna anomalia statistica evidentemente sfruttabile durante i propri test.

Ma l'azienda voleva esserne sicura non aveva superato i propri test semplicemente perché i test erano adatti alla macchina, il che darebbe loro un falso senso di sicurezza.

Alla fine, i ricercatori hanno scoperto non solo che la casualità era piuttosto scarsa, ma anche che erano in grado di quantificare esattamente quanto fosse scarsa e quindi di ideare test alternativi che rivelassero in modo convincente la mancanza di casualità.

In particolare, hanno dimostrato che un solo passaggio del dispositivo lasciava nell'output mescolato un numero sufficiente di brevi sequenze di carte da poter prevedere in modo affidabile tra 9 e 10 carte in media quando un mazzo di 52 carte mescolate veniva successivamente distribuito.

Come hanno scritto i ricercatori:

[U] la nostra teoria, siamo stati in grado di dimostrare che un giocatore esperto potrebbe indovinare correttamente circa 9 carte e mezzo in una singola corsa attraverso un mazzo da 52 carte. Per un mazzo ben mescolato, la strategia ottimale prevede che siano corrette circa 4 carte e mezzo. Questi dati hanno convinto l’azienda. La teoria suggeriva anche un utile rimedio.

[...]

Il presidente della società ha risposto: "Non siamo soddisfatti delle tue conclusioni, ma ci crediamo ed è per questo che ti abbiamo assunto". Abbiamo suggerito una semplice alternativa: utilizzare la macchina due volte. Ciò si traduce in una riproduzione casuale equivalente a quella di una macchina da 200 ripiani. La nostra analisi matematica e ulteriori test, non riportati qui, mostrano che questo è adeguatamente casuale.

Cosa fare?

Questo racconto contiene diversi "momenti di insegnamento" e faresti bene a imparare da essi, che tu sia un programmatore o un product manager alle prese con la casualità, o un professionista SecOps/DevOps/IT/sicurezza informatica coinvolto nella garanzia della sicurezza informatica in generale:

• Superare i propri test non è sufficiente. Fallire i tuoi test è sicuramente negativo, ma è facile finire con test che ti aspetti che il tuo algoritmo, prodotto o servizio superi, soprattutto se le tue correzioni o "correzioni di bug" vengono misurate in base al fatto che ti aiutano a superare i test. A volte è necessaria una seconda opinione che provenga da una fonte obiettiva e indipendente. Questa panoramica indipendente potrebbe provenire da un team di esperti statistici matematici della California, come qui; da un “red team” esterno di penetration tester; o da un team MDR (rilevamento e risposta gestiti) che porta i propri occhi e le proprie orecchie sulla tua situazione di sicurezza informatica.
• Ascoltare le cattive notizie è importante. Il presidente dell'azienda shuffling machine in questo caso ha risposto perfettamente quando ha ammesso di essere scontento del risultato, ma di aver pagato per scoprire la verità, non semplicemente per sentire ciò che sperava.
• La crittografia in particolare, e la sicurezza informatica in generale, sono difficili. Chiedere aiuto non è un’ammissione di fallimento ma un riconoscimento di ciò che serve per avere successo.
• La casualità è troppo importante per essere lasciata al caso. Misurare il disordine non è facile (leggi il documento per capirne il motivo), ma si può e si deve fare.

---

A corto di tempo o competenze per occuparsi della risposta alle minacce alla sicurezza informatica? Preoccupato che la sicurezza informatica finisca per distrarti da tutte le altre cose che devi fare?

Scopri Rilevamento e risposta gestiti da Sophos:
Ricerca, rilevamento e risposta alle minacce 24 ore su 7, XNUMX giorni su XNUMX  ▶

---