Segurança séria: Você não pode vencer a casa no Blackjack – ou pode?

Cryptoguru Bruce Schneier (onde cripto significa criptografia, não outra coisa!) acaba de publicar uma nota intrigante em seu blog intitulada Sobre a aleatoriedade dos embaralhadores automáticos de cartas.

Se você já esteve em um cassino, pelo menos um em Nevada, saberá que as mesas de blackjack não se arriscam com clientes conhecidos no comércio como contadores de cartas.

Esse termo é usado para se referir a jogadores que treinaram suas memórias a ponto de poderem acompanhar de perto as cartas jogadas até agora em uma mão, o que lhes dá uma vantagem teórica sobre a casa ao prever se devem parar ou bater enquanto jogam. progride.

Os contadores de cartas podem adquirir uma vantagem mesmo se tudo o que eles fizerem for acompanhar a proporção de 10 cartas (dez, valete, rainha e rei) para não 10 restantes no sapato do dealer.

Por exemplo, se o dealer está sentado com um Ás, mas um número acima da média de cartas de valor 10 já foi usado, então o dealer tem uma chance abaixo da média de fazer um blackjack (21 pontos com duas cartas, ou seja, Ás e um de 10-JQK) e vencer de uma vez, e uma chance acima da média de quebrar antes de atingir o ponto de parada de 17 e acima.

Se você puder equilibrar as probabilidades em sua cabeça em tempo real, poderá modificar suas apostas de acordo e sair na frente a longo prazo.

Na verdade, não tente isso, pelo menos em Nevada: o cassino provavelmente o pegará rapidamente, porque seu padrão de jogo divergirá notavelmente das escolhas vencedoras mais informadas disponíveis se você não estiver contando cartas. Você pode não acabar no tribunal, mas quase certamente será escoltado para fora das instalações e nunca mais voltará.

Nivelando as probabilidades

Para reduzir o contrapeso de probabilidades que os contadores de cartas desfrutam (aqueles que ainda não foram pegos, pelo menos), os cassinos normalmente:

• Distribua as mãos de um sapato carregado com seis baralhos (baralhos) de 52 cartas. Isso significa que cada mão distribuída distorce a distribuição restante de cartas menos do que se um único pacote fosse usado.
• Embaralhe todo o conjunto de 312 cartas (seis pacotes) antes de cada mão. Para economizar tempo e tirar as suspeitas do dealer, uma máquina eletromecânica pseudo-aleatória embaralha as cartas bem na mesa, na frente de todos os jogadores.

Isso levanta imediatamente a questão colocada por Schneier: quão bem embaralhadas estão as cartas quando saem da máquina?

Notavelmente, com seis novos pacotes de cartas, que chegam em uma ordem previsível (por exemplo, Ás para Rei de Copas, Ás para Rei de Paus, Rei para Ás de Ouros, Rei para Ás de Espadas), quanta ordenação parcial resta após o máquina fez o seu trabalho?

Você poderia “adivinhar” a próxima carta do sapato melhor do que o acaso sugere?

Um randomizador totalmente eletrônico é limitado em sua complexidade principalmente pela velocidade da CPU que ele usa, que normalmente é medida em centenas de milhões ou bilhões de operações aritméticas por segundo.

Mas um embaralhador eletromecânico de cartas literalmente precisa mover as cartas na vida real.

Obviamente, há um limite para a rapidez com que ele pode realizar divisões de pacotes, trocas de cartas e operações de intercalação antes que a velocidade do mecanismo comece a danificar as cartas, o que significa que há um limite para quanta aleatoriedade (ou, mais precisamente, pseudoaleatoriedade) a máquina pode apresentar antes da hora de jogar a próxima mão.

Embaralhe por um tempo muito curto, e o cassino pode realmente facilitar as coisas para os contadores de cartas, se houver um viés conhecido na distribuição das cartas desde o início.

Embaralhe por muito tempo e o jogo será muito lento, para que os jogadores fiquem entediados e divaguem, algo que os cassinos tentam desesperadamente evitar.

O blog de Schneier tem links para um peça fascinante pela BBC que descreve como um matemático/mágico chamado Persi Diaconis da Universidade de Stanford, juntamente com Jason Fulman e Susan Holmes, conduziram uma investigação formal sobre esta questão no início deste século, em um artigo intitulado simplesmente: ANÁLISE DE MÁQUINAS DE EMBARALHAMENTO DE PRATELEIRAS DE CASINO.

Níveis de complexidade

Claramente, existem algumas técnicas de embaralhamento que não misturam muito as cartas, como simplesmente corte o pacote em duas partes e movendo a parte de baixo para cima.

Outras técnicas resultam em (ou parecem que deveriam resultar) em uma melhor mixagem, por exemplo, a embaralhamento de espingarda, onde você divide o baralho mais ou menos ao meio, segura uma metade em cada mão e “vira” as duas metades, intercalando-as de forma pseudo-aleatória que alterna entre pegar algumas cartas de um lado e depois algumas cartas do outro .

A ideia é que, se você embaralha o pacote várias vezes, executa uma sequência pseudo-aleatória de cortes cada vez que divide o pacote antes de cada riffle, misturada com uma sequência variável pseudo-aleatória de operações de intercalação pseudo-aleatórias envolvendo um N-do-o- processo de esquerda-então-M-da-direita.

Curiosamente, no entanto, quando há embaralhadores humanos envolvidos, nenhuma dessas suposições de imprevisibilidade é segura.

Magos hábeis e negociantes desonestos (o próprio Diaconis é o primeiro, mas não o último) podem realizar o que é conhecido como faro embaralhaou embaralhamento perfeito, onde eles fazem as duas coisas a seguir toda vez que vasculham o pacote:

• Divida as cartas precisamente em dois, obtendo assim exatamente 26 cartas em cada mão.
• Intercalá-los perfeitamente, virando para baixo exatamente uma carta de cada vez alternadamente de cada mão, todas as vezes.

O próprio Diaconis pode fazer embaralhamentos perfeitos (incluindo a rara habilidade de fazê-lo com apenas uma mão para segurar as duas metades do pacote!), e de acordo com a BBC:

[Ele] gosta de demonstrar o embaralhamento perfeito pegando um novo baralho de cartas e escrevendo a palavra RANDOM em marcador preto grosso de um lado. Enquanto ele faz seu truque com as cartas, as letras se misturam, aparecendo de vez em quando em forma fantasmagórica, como uma imagem imperfeitamente sintonizada em um velho aparelho de TV. Então, depois que ele faz o oitavo e último embaralhamento, a palavra se materializa na lateral do baralho. As cartas estão em sua exata sequência original, do Ás de Espadas ao Ás de Copas.

Dois tipos de perfeição

Na verdade, existem dois tipos de embaralhamento perfeito, dependendo de qual mão você começa a riffs depois de cortar as cartas em duas pilhas de 26 cartas.

Você pode intercalar as cartas para que elas terminem na sequência 1-27-2-28-3-29-…-25-51-26-52, se a primeira carta que você virar para baixo vier da mão que você está segurando ele metade inferior do pacote.

Mas se a primeira carta que você virar para baixo for a carta de baixo do que anteriormente era a metade superior do baralho, você acaba com 27-1-28-2-29-3-…-51-25-52-26, então o cartão logo após a metade acaba no topo depois.

O primeiro tipo é chamado de embaralhar, e reordena o pacote a cada oito vezes que você o repete, como você pode ver aqui (a imagem tem 52 linhas de pixels, cada linha correspondendo à borda de um cartão com a palavra RANDOM escrita nele com uma caneta marcadora):

Este último tipo é um embaralhado, e isso, surpreendentemente, leva 52 re-embaralhamentos antes de se repetir, embora você possa ver claramente aqui que o pacote nunca mostra nenhuma aleatoriedade verdadeira e até passa por uma reversão perfeita no meio do caminho:

O que os matemáticos disseram?

Então, em 2013, quando Diaconis el al. estudaram a máquina de embaralhamento de prateleiras a convite do fabricante, o que eles encontraram?

Como o artigo explica, um embaralhador de prateleira é uma tentativa eletromecânica de conceber um “embaralhamento multi-riffle multi-corte” automatizado e aleatório, idealmente para que os cartões só precisem ser trabalhados uma vez, para manter o tempo de embaralhamento curto.

Os cartões em um embaralhador de prateleiras são rapidamente “distribuídos” pseudoaleatoriamente, um de cada vez, em uma das N prateleiras de metal dentro do dispositivo (daí o nome), e cada vez que um cartão é adicionado a uma prateleira, ele é inferior, ou caiu no topo dos cartões anteriores. (Assumimos que tentar enfiar a carta entre duas cartas aleatórias já na pilha seria mais lento e propenso a danificar as cartas.)

Depois que todas as cartas foram atribuídas a uma prateleira, de modo que cada prateleira tenha cerca de 1/Nth das cartas, as cartas são reagrupadas em uma única pilha em uma ordem pseudo-aleatória.

Intuitivamente, dada a pseudoaleatoriedade envolvida, você esperaria que re-embaralhamentos adicionais melhorariam a aleatoriedade geral, até certo ponto…

…mas neste caso, onde a máquina tinha 10 prateleiras, os pesquisadores foram convidados especificamente, “Uma passagem da máquina será suficiente para produzir aleatoriedade adequada?”

Presumivelmente, a empresa queria evitar executar a máquina em vários ciclos para manter os jogadores felizes e o jogo fluindo bem, e os engenheiros que projetaram o dispositivo não detectaram nenhuma anomalia estatística obviamente explicável durante seus próprios testes.

Mas a empresa queria ter certeza de que não passou em seus próprios testes simplesmente porque os testes se adequavam à máquina, o que lhes daria uma falsa sensação de segurança.

Em última análise, os pesquisadores descobriram não apenas que a aleatoriedade era bastante ruim, mas também que eles eram capazes de quantificar exatamente quão ruim era e, assim, elaborar testes alternativos que revelavam de forma convincente a falta de aleatoriedade.

Em particular, eles mostraram que apenas uma passagem do dispositivo deixou sequências curtas suficientes de cartas na saída embaralhada que eles poderiam prever com segurança entre 9 e 10 cartas em média quando um baralho de 52 cartas embaralhadas fosse distribuído posteriormente.

Como os pesquisadores escreveram:

[U]sando nossa teoria, fomos capazes de mostrar que um jogador experiente poderia adivinhar cerca de 9 cartas e meia corretamente em uma única passagem por um baralho de 52 cartas. Para um baralho bem embaralhado, a estratégia ideal obtém cerca de 4 cartas e meia corretas. Esses dados convenceram a empresa. A teoria também sugeriu um remédio útil.

[...]

O presidente da empresa respondeu: “Não estamos satisfeitos com suas conclusões, mas acreditamos nelas e foi para isso que o contratamos”. Sugerimos uma alternativa simples: usar a máquina duas vezes. Isso resulta em um embaralhamento equivalente a uma máquina de 200 prateleiras. Nossa análise matemática e outros testes, não relatados aqui, mostram que isso é adequadamente aleatório.

O que fazer?

Este conto contém vários “momentos de aprendizado”, e você seria sábio em aprender com eles, seja você programador ou gerente de produto lutando especificamente com a aleatoriedade, ou um profissional de SecOps/DevOps/TI/segurança cibernética que está envolvido em garantia de segurança cibernética em em geral:

• Passar em seus próprios testes não é suficiente. Falhar em seus próprios testes é definitivamente ruim, mas é fácil acabar com testes nos quais você espera que seu algoritmo, produto ou serviço passe, especialmente se suas correções ou “correções de bugs” forem medidas pelo fato de você passar pelos testes. Às vezes, você precisa de uma segunda opinião que vem de uma fonte objetiva e independente. Essa visão independente pode vir de uma equipe de especialistas matemáticos da Califórnia, como aqui; de uma “equipe vermelha” externa de testadores de penetração; ou de uma equipe de MDR (detecção e resposta gerenciadas) que traz seus próprios olhos e ouvidos para sua situação de segurança cibernética.
• Ouvir más notícias é importante. O presidente da empresa de máquinas de embaralhar neste caso respondeu perfeitamente quando admitiu que estava descontente com o resultado, mas que havia pago para descobrir a verdade, não apenas para ouvir o que esperava.
• A criptografia em particular e a segurança cibernética em geral são difíceis. Pedir ajuda não é uma admissão de fracasso, mas um reconhecimento do que é preciso para ter sucesso.
• A aleatoriedade é importante demais para ser deixada ao acaso. Medir a desordem não é fácil (Leia o papel entender o porquê), mas pode e deve ser feito.

---

Pouco tempo ou experiência para cuidar da resposta a ameaças de segurança cibernética? Preocupado que a segurança cibernética acabe distraindo você de todas as outras coisas que você precisa fazer?

Saiba mais sobre Detecção e Resposta Gerenciada Sophos:
Caça, detecção e resposta a ameaças 24 horas por dia, 7 dias por semana  ▶

---