Quão aleatório é o aleatório? Um tour jogável pelo Mersenne Twister

Um dos primeiros bugs que eu vi em bug bounty não tinha nada de mágico. Um código de reset de senha era gerado com o mesmo tipo de random() que um jogo usaria pra sortear um item. Aleatório o bastante pra parecer seguro, previsível o bastante pra não ser.

Esse bug ficou na minha cabeça porque levanta uma pergunta que parece boba até você tentar responder: como um computador, uma máquina que faz exatamente o que mandam, inventa alguma coisa aleatória?

Resposta curta: não inventa. Ele finge. A resposta longa é bem mais divertida, e cada figura abaixo roda o algoritmo de verdade no seu navegador, então dá pra mexer à vontade.

Primeiro, um teste

Aqui estão dois campos com 90 pontos. Um deles foi montado por um gerador de números aleatórios. O outro, não.

Se você escolheu o arrumadinho, bem-vindo ao clube dos humanos. A gente espera que o aleatório seja bem distribuído, sem aglomerados e sem buracos. O aleatório de verdade é embolado: alguns pontos caem um em cima do outro e sobram espaços vazios enormes, porque cada ponto é colocado sem ligar pra onde os outros foram.

Guarda isso. "Parece aleatório" e "é aleatório" são coisas diferentes, e é nesse espaço entre as duas que mora tudo de interessante deste post.

Computador não joga moeda: números pseudoaleatórios e seeds

Uma CPU é determinística: mesma entrada, mesma saída, sempre. Então, em vez de números aleatórios, os programas usam números pseudoaleatórios: uma fórmula que recebe um número (a seed) e produz uma sequência longa que parece aleatória.

Mesma seed, mesma sequência. Sempre.

Parece um defeito, mas quase sempre é uma vantagem. É assim que um jogo consegue reproduzir uma partida a partir de uma seed, que uma simulação roda de novo exatamente igual, e que um mundo gerado proceduralmente fica igual na sua máquina e na minha. A seed é o mundo inteiro comprimido num número.

Então a pergunta de verdade vira: que fórmula transforma um número numa sequência que parece aleatória?

Tentativa nº 1: middle-square (1949)

John von Neumann precisava de muitos dígitos aleatórios pras primeiras simulações em computador e propôs uma coisa lindamente simples: pegue um número de 4 dígitos, eleve ao quadrado e fique com os quatro dígitos do meio. Esse é o próximo número. Repita.

Teste algumas seeds. Começa parecendo aleatório, até que ou despenca pro zero ou cai num loop curto e fica lá pra sempre. Com 2026 de seed, ele solta 97 números antes de começar a repetir 4100 → 8100 → 6100 → 2100.

Von Neumann sabia que o método era fraco. Quando o apresentou, também soltou uma das melhores frases da computação:

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.

(Algo como: "quem considera métodos aritméticos pra produzir dígitos aleatórios está, é claro, em estado de pecado". Ele usou mesmo assim. Era rápido, e quando quebrava, quebrava de um jeito óbvio que dava pra perceber.)

Tentativa nº 2: o RANDU e seus 15 planos

Depois vieram os geradores congruenciais lineares: multiplica, soma, pega o resto.

x = (a * x + c) % m

Escolha bem a, c e m e você ganha sequências longas e decentes. Escolha mal e você ganha o RANDU, o gerador da IBM dos anos 1960, usado por anos em código científico:

x = (65539 * x) % 2 ** 31

Numa olhada rápida, passa. Os números parecem espalhados, sem padrão óbvio. Agora pegue três saídas seguidas e use como coordenadas de um ponto num cubo. Faça isso 3.000 vezes:

De quase qualquer ângulo: neblina. De um ângulo: todo ponto está em um de só 15 planos. Numa nuvem realmente aleatória, os pontos podem estar em qualquer lugar. Aqui, a maior parte do cubo fica garantidamente vazia.

Por quê? Porque 65539 = 2¹⁶ + 3, e com um pouco de álgebra essa escolha amarra cada saída às duas anteriores:

x[k + 2] = (6 * x[k + 1] - 9 * x[k]) % 2 ** 31

O terceiro número nunca é livre. Qualquer simulação que sorteava pontos em 3D com o RANDU estava amostrando um punhado de fatias, não um volume. A lição é esta: um gerador pode passar em todo teste que você resolveu olhar e ainda esconder estrutura numa dimensão que você não checou.

Como o Mersenne Twister funciona

Em 1998, Makoto Matsumoto e Takuji Nishimura publicaram o gerador que viraria o padrão em quase todo lugar: o random do Python, o Random do Ruby, o mt_rand do PHP, o padrão do R e o std::mt19937 do C++.

Três ideias fazem ele funcionar.

1. Um estado enorme. O RANDU lembra de um número. O Mersenne Twister lembra de 624: 624 × 32 bits, quase 20.000 bits de estado. Cada chamada de random() lê a próxima palavra dessa pilha.

2. O twist. Quando as 624 palavras acabam, ele reconstrói a pilha inteira. Cada palavra nova sai de três antigas: o bit mais alto da palavra i, os 31 bits de baixo da palavra i + 1 e a palavra i + 397, misturados com um shift, um XOR e uma constante mágica.

Use a seed 5489 (o padrão do C++) e o primeiro número que sai é 3499211612. Igual na sua máquina, na minha e em toda implementação correta já escrita. É a história da seed de novo.

3. Tempering. As palavras cruas do estado têm alguns padrões estatísticos, então antes de uma palavra sair do gerador, quatro passos de shift e XOR embaralham os bits:

A recompensa está no nome. A sequência só se repete depois de 2¹⁹⁹³⁷ − 1 números. Esse número é um primo de Mersenne (um primo da forma 2ⁿ − 1, batizado em homenagem ao frade Marin Mersenne) e, escrito por extenso, tem 6.002 dígitos. Você nunca vai ver ele repetir. Nem o universo.

Ele também não tem o problema do RANDU. As saídas ficam bem distribuídas em até 623 dimensões ao mesmo tempo, e é por isso que o cubo do RANDU lá em cima vira neblina de novo quando você troca pro Twister.

O núcleo inteiro cabe numa tela:

// O twist: reconstrói as 624 palavras.
for (let i = 0; i < 624; i++) {
  const y = (mt[i] & 0x80000000) | (mt[(i + 1) % 624] & 0x7fffffff);
  mt[i] = mt[(i + 397) % 624] ^ (y >>> 1) ^ (y & 1 ? 0x9908b0df : 0);
}
 
// Tempering: embaralha uma palavra na saída.
function temper(y: number) {
  y ^= y >>> 11;
  y ^= (y << 7) & 0x9d2c5680;
  y ^= (y << 15) & 0xefc60000;
  y ^= y >>> 18;
  return y >>> 0;
}

Rápido, com um período que ninguém nunca vai alcançar e ótima estatística. Problema resolvido?

Plot twist: prevendo o Mersenne Twister com 624 saídas

Olhe de novo o fim da figura do tempering. Eu rodei ele de trás pra frente. Todo passo do tempering pode ser desfeito, então a partir de uma saída dá pra recuperar exatamente a palavra de estado de onde ela veio.

E o gerador não é nada além das suas 624 palavras de estado. Junte 624 saídas seguidas, desfaça o tempering de cada uma e você tem uma cópia perfeita do gerador. Daí em diante, você sabe todo número que ele vai produzir.

Bora testar. Este servidor de mentira distribui tokens de reset de senha direto de um Mersenne Twister com seed secreta:

Sem força bruta e sem adivinhar a seed: 624 tokens e um pouco de malabarismo com bits. Esse é o bug do começo do post, e é por isso que ele é um bug de verdade: se um atacante consegue ver saídas suficientes, ele prevê o código de reset que era pra conta de outra pessoa.

O Mersenne Twister não foi mal projetado. Ele foi projetado pra ser aleatório estatisticamente (ótimo pra simulações, jogos e amostragem), não imprevisível. São trabalhos diferentes. A documentação do Python fala isso com todas as letras: o módulo random não deve ser usado pra segurança, e ela te manda pro secrets.

(Se você está se perguntando sobre JavaScript: o Math.random() do V8 não é um Mersenne Twister. Ele usa xorshift128+ desde 2015. Também não foi feito pra ser imprevisível; só precisa de outro truque pra prever.)

De onde vem a imprevisibilidade de verdade: CSPRNGs

De coisas que uma fórmula não tem como saber: variações de tempo no hardware, interrupções, ruído nos circuitos da CPU. O sistema operacional junta esse tipo de entropia num pool e alimenta um gerador criptograficamente seguro (um CSPRNG). Ele é feito pra que, mesmo depois de ver um milhão de saídas, você não consiga prever a próxima nem voltar pras anteriores.

Tem empresa que vai além. A Cloudflare aponta uma câmera pra uma parede de lâmpadas de lava no saguão do escritório e mistura as imagens na sua aleatoriedade, junto com outras fontes. Parece piada, mas é verdade.

Você não precisa de lâmpada de lava. Já tem um CSPRNG a uma chamada de distância:

// Navegador e Node
crypto.getRandomValues(new Uint32Array(1));
crypto.randomUUID();

# Python
import secrets
secrets.token_urlsafe(32)

A cola

Então, quão aleatório é o aleatório? Num computador, quase nunca de verdade. É uma fórmula boa o bastante pra enganar um teste, ou o olho, ou anos de código científico (foi mal, RANDU). A pergunta útil não é "isso é aleatório?". É "aleatório o bastante pra quem?". Pra um dado, um twister é perfeito. Pra alguém tentando adivinhar seu código de reset, só imprevisibilidade de verdade resolve.

Respostas rápidas

O Mersenne Twister é criptograficamente seguro? Não. Cada saída é um embaralhamento reversível de uma palavra do estado, então 624 saídas seguidas de 32 bits bastam pra reconstruir o gerador e prever todos os valores depois delas. Pra tokens, chaves e códigos de reset, use um CSPRNG como crypto.getRandomValues ou o secrets do Python.

Por que o nome Mersenne Twister? O período dele, 2¹⁹⁹³⁷ − 1, é um primo de Mersenne. O "twister" vem do passo de twist que reconstrói as 624 palavras de estado; ele é uma variante de uma família anterior de geradores chamada twisted GFSR.

Quem usa? O random do Python, o Random do Ruby, o mt_rand do PHP, o gerador padrão do R e o std::mt19937 do C++ são todos MT19937.

O que o Math.random() do JavaScript usa? Depende do motor. O V8 (Chrome, Node.js) usa xorshift128+ desde 2015. Também não é criptograficamente seguro.

Qual era o problema do RANDU? O multiplicador, 65539, é 2¹⁶ + 3. Isso faz cada saída ser uma combinação fixa das duas anteriores (x[k+2] = 6·x[k+1] − 9·x[k] mod 2³¹), então trios seguidos caem em só 15 planos.

Fontes

• Makoto Matsumoto e Takuji Nishimura, Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation 8(1), 1998.
• Documentação do Python, random: Generate pseudo-random numbers.
• Blog do V8, There's Math.random(), and then there's Math.random() (2015).
• Cloudflare, Randomness 101: LavaRand in Production (2017).
• MDN, Crypto.getRandomValues().
• Wikipedia, RANDU e Middle-square method.

As figuras rodam um MT19937 em TypeScript que bate com a implementação de referência: com a seed 5489, a primeira saída é 3499211612 e a de número 10.000 é 4123659995, o valor que o padrão do C++ exige do std::mt19937.