- Randar é um exploit que, no Minecraft Beta 1.8 a 1.12.2, usa as coordenadas de drops de itens gerados ao quebrar blocos para reconstruir o estado do
java.util.Random do servidor e rastrear a posição de outros jogadores
- A causa central é a reutilização de RNG, em que a geração de terreno/estruturas e eventos de mineração compartilham o mesmo gerador de números aleatórios; posições de drops observáveis viram pistas sobre o estado interno
- Os offsets X/Y/Z de um drop de item são três saídas consecutivas de
World.rand.nextFloat(), expondo os 24 bits superiores de uma seed de 48 bits, que pode ser recuperada rapidamente com redução de reticulado LLL
- A seed recuperada é rebobinada para verificar se veio de uma checagem de Woodland Mansion; se bater, identifica a Woodland region de 1280×1280 blocos carregada recentemente
- Se dados de drops permanecerem em gravações antigas de pacotes, como as do ReplayMod, locais de atividades da era Beta 1.8~1.12.2 podem ser expostos retroativamente mesmo após o servidor ter sido corrigido
Que informação o Randar mira
- O objetivo é encontrar as coordenadas dentro do jogo de outros jogadores no mesmo mundo
- O 2b2t é usado como principal exemplo
- 2b2t é um servidor “anarchy” de Minecraft sem regras
- O mapa do servidor tem 3,6 quadrilhões de tiles quadrados, então manter a localização em segredo é uma condição essencial para proteger itens
- Antes do Randar, o 2b2t já teve o exploit de coordenadas Nocom, usado entre 2018 e 2021
Versões vulneráveis e erro de código
- O problema existe desde o lançamento do Minecraft Beta 1.8, em 2011, até o 1.12.2, lançado em 2017
- O 2b2t permaneceu na 1.12.2 até 14 de agosto de 2023
- O erro central foi reutilizar descuidadamente uma instância de
java.util.Random em vários caminhos de código
- O RNG é compartilhado entre geração de terreno e ações do jogo, como mineração
- O próprio
java.util.Random também não é um RNG para uso em segurança
- O Minecraft usa geração determinística para que a mesma seed de mundo e a mesma posição produzam o mesmo terreno
- Para esse objetivo, usar
java.util.Random é natural
- O problema é que a manipulação do RNG para geração de mundo, que precisa ser previsível, também afetou eventos que deveriam ser imprevisíveis
Checagem de Woodland Mansion e World.rand global
- No processo de verificar posições de geração de Woodland Mansion, o
World.rand é reinicializado
- Uma Woodland region é calculada em unidades de 80×80 chunks
- Para escolher o chunk onde a Mansion será gerada dentro dessa region,
random.nextInt(60) é chamado quatro vezes
- O fluxo vulnerável é uma estrutura em que
World.setRandomSeed(seedX, seedY, seedZ) define uma nova seed no this.rand global e retorna o mesmo objeto
- A fórmula específica do 2b2t é a seguinte
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
setRandomSeed é chamado não só quando se está perto de uma Woodland Mansion real, mas também a cada carregamento de chunk para fins de checagem- O impacto varia por dimensão
- O Overworld é o principal afetado
- O Nether é seguro porque a geração de estruturas sempre usa um RNG seguro
- The End é afetado na geração inicial por causa das end cities, mas é relativamente mais seguro porque o mesmo chunk não causa impacto toda vez que é recarregado depois
Como coordenadas de drops de itens revelam o RNG
- Ao minerar um bloco, o item é dropado em uma posição aleatória dentro do bloco
- Por exemplo, se as coordenadas do bloco forem
(10, 20, 30), o item aparece entre (10.25, 20.25, 30.25) e (10.75, 20.75, 30.75)
- Essa posição define os offsets X, Y e Z com três chamadas a
world.rand.nextFloat()
- É possível voltar das coordenadas do drop para os valores originais de
nextFloat()
- O processo de multiplicar o float por 0,5 apenas reduz o expoente, sem perda de informação
- Depois ele é convertido para double, somado às coordenadas do bloco e transmitido pela rede com precisão completa
java.util.Random.nextFloat() atualiza a seed de 48 bits e então extrai os 24 bits superiores como inteiro, dividindo por 2^24
- A fórmula do LCG é
newSeed = oldSeed * 25214903917 + 11 mod 2^48
- Três floats consecutivos fornecem os 24 bits superiores de três seeds consecutivas
Recuperação da seed com redução de reticulado LLL
- O método simples é tentar todos os
2^24 candidatos de 24 bits inferiores que combinam com a primeira medição
- Esse método também funciona, mas é lento, então é usado um método de reticulado
- As três medições fornecem intervalos para os três valores seguintes
seednextSeed(seed)nextSeed(nextSeed(seed))
- Vendo esses três valores como um ponto 3D
(seed, nextSeed(seed), nextSeed(nextSeed(seed))), todas as seeds possíveis formam uma estrutura de reticulado
- Os vetores-base são definidos assim
(1, a, a^2)(0, c, 0)(0, 0, c)- em que
a = 25214903917, c = 2^48
- LLL basis reduction encontra uma base mais curta e quase ortogonal que gera o mesmo reticulado
- Um exemplo em Mathematica é
LatticeReduce[{{1, a, a^2}, {0, c, 0}, {0, 0, c}}]
- A base resultante é
(1270789291, -2446815537, 2154219555), (-2355713969, 1026597795, 4110294631), (-3756485696, -2345310016, -2015749696)
- Depois de transformar o centro do cubo de medição para o espaço da base reduzida e arredondar cada coeficiente para o inteiro mais próximo, obtém-se um ponto válido do reticulado; a primeira coordenada é a seed interna recuperada
- Um exemplo de código Java otimizado consegue recuperar a seed a partir de três medições em cerca de 10 ns
Processo de rebobinar a seed para encontrar a posição
- O LCG do
java.util.Random pode avançar e retroceder
- Direção normal:
newSeed = oldSeed * 25214903917 + 11 mod 2^48
- Direção inversa:
oldSeed = (newSeed - 11) * 246154705703781 mod 2^48
- A seed recuperada é rebobinada, verificando-se se cada seed poderia ter vindo de uma checagem de Woodland Mansion
- O intervalo do mundo de Minecraft vai de -30 milhões a +30 milhões de blocos
- A implementação define o intervalo de Woodland regions em cada eixo de -23440 a +23440
- O número de Woodland regions possíveis é
(23440*2+1)^2, ou 2.197.828.161
- Comparar todos os 2,2 bilhões de candidatos é lento, e um
HashSet grande também consome muita memória
- Como o coeficiente Z
132897987541 é ímpar, ele tem inverso em mod 2^48
- O inverso é
211541297333629
- Com isso, é possível percorrer apenas os 46.881 candidatos de X e calcular Z para encontrar a region candidata
GPU e otimização com tabela de consulta
- O método que percorre apenas X é razoável para uma única seed, mas quando muitos bots mineram vários blocos por segundo e cada medição precisa verificar milhares de steps de RNG, o processamento em tempo real ficava difícil em um VPS de baixo desempenho
- A implementação posterior mudou para tarefas em lote com CUDA e uma tabela de consulta
- A chave da tabela de consulta são os 32 bits inferiores da mansion seed
- O valor é a coordenada X da Woodland region
- Não havia colisões nas chaves de 32 bits inferiores, e o autor diz não entender o motivo
- A tabela usa
2^32 entradas e 2 bytes por entrada, exigindo cerca de 9 GB de VRAM
- Em uma RTX 3090, era possível crackear cerca de 10 milhões de seeds por segundo
- O resultado recuperado indica a Woodland region de 1280×1280 blocos em que ocorreu o carregamento de chunk mais recente; com esse nível de precisão, alguns minutos de busca bastam para localizar a posição
Distribuição de steps observada em servidores reais
- Teoricamente, o intervalo médio entre Woodland seeds é de cerca de 128.000 steps de RNG
- No 2b2t, a maioria das Woodland seeds era encontrada em algumas dezenas de steps
- A medição ocorre em um ponto muito inicial do tick por causa do momento do processamento de pacotes
- Normalmente, o chunk já havia sido carregado no tick imediatamente anterior
- Medições confiáveis começam em no mínimo 4 steps de RNG
- Isso ocorre porque o código da Woodland Mansion chama
rand.nextInt quatro vezes antes da observação
- Grandes picos aparecem em múltiplos de 1354 steps
- São sugeridas as possibilidades de explosão de end crystal ou wither skull
- No caso de uma explosão de end crystal, o cálculo de dano a blocos
16^3-14^3=1352 mais 2 efeitos sonoros fecha em 1354 steps
ReplayMod e risco de exposição retroativa
- Mesmo que o servidor tenha sido atualizado para uma versão recente ou tenha corrigido a manipulação do RNG, o risco do Randar permanece se dados antigos ainda existirem
- Alguns jogadores de Minecraft gravam pacotes com mods como ReplayMod
- Se o arquivo gravado contiver drops de itens, é possível recuperar o estado do RNG do servidor naquela época
- Quebrar blocos é uma ação muito comum, então há grande chance de ela aparecer nas gravações
- Todas as posições que estiveram ativas entre Beta 1.8 e 1.12.2 devem ser consideradas expostas, mesmo que o servidor tenha sido atualizado há muito tempo
- É oferecida uma ferramenta web client-side para testar o Randar diretamente
- Em hobune.stream/randar, é possível arrastar arquivos do ReplayMod 1.12.2 e verificar coordenadas
- Os arquivos gravados não saem do navegador
Operação do Randar e heatmap
- A SpawnMasons começou a registrar coordenadas de drops de itens em contas que já mineravam stone/cobblestone 24/7 por causa de outro projeto
- Eles reutilizaram o sistema headless de Minecraft usado no Nocom e adicionaram um banco de dados Postgres para armazenar as medições
- O software para crackear medições de RNG foi melhorado várias vezes e, por fim, estabilizou em async CUDA batch job
- Quando uma medição crackeada era adicionada ao banco de dados, a tabela de análise de heatmap também era atualizada
- Ela armazenava contagens de hits para o período inteiro, por dia e por hora
- Uma UI em Plotly Dash permitia selecionar intervalo de tempo e granularity para visualizar no navegador
- O spam de carregamento de chunks causado por caçadas a stashes com Elytra era removido considerando apenas coordenadas carregadas em várias horas distintas
- Também foi adicionado um sistema simples de annotations compartilhadas para acompanhar hotspots encontrados
- Bots Baritone vindos do Nocom automatizavam em AFK o processo de roubar e organizar stashes de itens
Woodland region decoy para proteção
- O Randar nem sempre encontra exatamente o chunk mais recente
- Ao rebobinar o RNG, se uma Woodland region decoy mais recente aparecer primeiro, um exploit que retorna o primeiro match pode gerar falso positivo
- Em média, cerca de 1 em cada 130.000 RNG seeds é uma Woodland seed, mas a distribuição tem outliers
- No 2b2t, diz-se que cerca de 1 em cada 20 mil Woodland regions tem uma propriedade especial de hiding, com outra Woodland region nos 4 steps de RNG seguintes
- A SpawnMasons criou stashes nessas regions
- Por causa da distância de renderização, as estruturas foram construídas de forma compacta para não carregar chunks fora da region protegida
- Na posição decoy, deixaram uma conta AFK e uma pequena base para tentar fazer outros usuários do Randar verem a localização decoy
- Nos próprios logs de Randar, esses stashes permaneceram “clean” durante todo o período, sem carregar acidentalmente Woodland regions vizinhas
- No momento da divulgação, eles afirmaram que esses stashes já haviam sido movidos
Exemplo completo e restrições por versão
- É fornecido um exemplo em Java que detecta itens parecidos com drops de mineração em
SPacketSpawnObject, converte as coordenadas do drop de volta para três medições float, faz o cracking baseado em LLL e rastreia a Woodland region
- Um exemplo de medição real do 2b2t produz o seguinte resultado
- item drop:
0.41882818937301636, 0.6833633482456207, 0.46088552474975586
- medições de RNG:
5664934 14541261 7076144
- seed interna:
95041827771683
- Woodland region:
-12008 0
- intervalo de posição: de
-15370368,-128 a -15369089,1151
- O exemplo para diagrama encontra a Woodland Region
123,456
- O intervalo final de posição vai de
157312,583552 a 158591,584831
- Ele inclui as coordenadas originais de entrada
x=157440 z=583680
- Em versões anteriores à 1.11, a estrutura explorável não é a Woodland Mansion, mas outra estrutura, então é necessário código diferente
- Antes da 1.9, a posição dos itens era transmitida como fixed-point de 5 bits da parte fracionária, não como double; por isso, crackear o estado do RNG com apenas um item é impraticável e exige outra estratégia de medição
Como corrigir
- O jeito fácil é encontrar um patch ou configuração que desative a manipulação do RNG
- A implementação vulnerável faz
World.setRandomSeed definir a seed no this.rand global e retorná-lo
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
this.rand.setSeed(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
return this.rand;
}
- Para proteção completa, é possível mudar para retornar um novo
Random a cada chamada
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
return new Random(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
}
- Se houver preocupação com desempenho, é possível criar um campo de RNG separado só para geração de mundo,
separateRandOnlyForWorldGen, e não compartilhá-lo com outros usos
- O patch para PaperMC 1.12.2 é disponibilizado no commit PaperWithRandarPatched e em um arquivo de patch alternativo
Apêndice de n0pf0x: outros métodos de busca de coordenadas e The End
- n0pf0x usa busca de coordenadas baseada em cache em vez da grande tabela de consulta em GPU do lado da Mason
- Quando ocorre um hit, as coordenadas correspondentes e as coordenadas dentro de um raio ao redor são colocadas em um
HashMap
- O primeiro pass rebobina o RNG e verifica rapidamente hits no cache ou duplicação com seeds processadas imediatamente antes
- O segundo pass só roda quando o primeiro falha, usando o algoritmo caro de busca de coordenadas descrito antes
- Esse método de cache pode ajudar a reduzir falsos positivos por pular locais válidos menos plausíveis
- Em The End, só há impacto no RNG quando um chunk é gerado pela primeira vez, então é difícil observar repetidamente carregamentos de chunks de uma base como no Overworld
- Há duas situações em que se pode depender disso em The End
- Um jogador na base anda por aí e gera chunks ainda não gerados
- Um jogador indo para a base gera uma trilha de novos chunks no caminho
- Uma trilha poderia permitir criar um sistema de identificação automática, mas n0pf0x não implementou isso e a rastreou manualmente de forma visual
- Para identificar jogadores, foi usada a ideia de End Occupancy Tracker(EOT)
- Ela se baseia na hipótese de que o número de chamadas de RNG por tick tem certa correlação com o número de chunks carregados, o que se conecta ao número de jogadores naquela dimensão
- Observando se o número de chamadas de RNG aumenta ou diminui logo após um jogador entrar/sair, estima-se quais jogadores estão em The End
- O EOT foi testado apenas no 9b9t e pode não funcionar sob condições de outros servidores, como o 2b2t
- É preciso conseguir amostrar o RNG de forma estável a cada tick
- Se a atividade de jogadores em The End for muito maior, isso pode ficar mais difícil
1 comentários
Comentários do Hacker News
Em 1999–2000, houve a International RoShamBo Programming Competition, em que bots de computador jogavam pedra-papel-tesoura entre si [1]
O bot de referência usava escolha aleatória, uma estratégia teoricamente impossível de vencer, mas uma inscrição de brincadeira foi projetada para reconstruir o estado do gerador de números aleatórios e prever com 100% de precisão o que o jogador aleatório escolheria
Correção: esse bot era o “Nostradamus”, de Tim Dierks, e foi declarado vencedor da categoria “supermodified” na primeira competição [2]
[1] https://web.archive.org/web/20180719050311/http://webdocs.cs...
[2] https://groups.google.com/g/comp.ai.games/c/qvJqOLOg-oc
Na verdade, acabei indo para a área de segurança, escrevi RFCs de TLS e me tornei engenheiro principal na área de segurança do Google. Obrigado por trazer essa lembrança de volta
https://web.archive.org/web/20180719050236/http://webdocs.cs...
Nostradamus foi escrito por Tim Dierks, VP de engenharia da Certicom, com grande expertise em criptografia, e venceu o jogador ótimo fazendo engenharia reversa do estado interno do gerador
random(). Nas palavras dele, foi “ao mesmo tempo mais fácil e mais difícil do que eu esperava”. Ainda assim, por espírito esportivo, jogou de forma ótima contra todos os outros adversáriosFork Bot surgiu de uma ideia que Dan Egnor teve poucos minutos depois de ouvir falar da competição, explorando a permissão de “rotinas de biblioteca” para usar
fork(), criar três processos, fazer cada um jogar uma opção diferente e matar os dois que perdessem. Andreas Junghanns implementou isso em cerca de 10 linhas de código, mas, depois do primeiro turno, as três jogadas perderam para a Psychic Friends Network, o programa encerrou, e as partidas restantes foram tratadas como desistênciasPsychic Friends Network era um código C ofuscado realmente hilário, escrito por Michael Schatz e o pessoal da RST Corporation, com funções auxiliares para encontrar bom carma, consulta astrológica, preparo de espaguete e pizza mística,
#definetransformando democratas em comunistas,undefde Deus, entre outras coisas. Ainda estamos tentando entender exatamente o que ele faz com o stack frame, mas, a menos que enfrente um meta-meta-trapaceiro, ele não marca menos de +998 em uma partidaThe Matrix foi escrito por Darse Billings, detentor do prestigioso título de “Student for Life”, e venceu todos os adversários com pontuação perfeita usando o simples princípio de que “não há colher”
The Matrix também é o programa do torneio, então tem acesso total a todos os outros algoritmos, estruturas de dados e rotinas de saída, o que torna improvável que seja superado no futuro. Portanto, a categoria foi declarada resolvida e removida das competições seguintes
No fim, essa transparência acabou melhorando a segurança
A redução de reticulados LLL é exatamente o algoritmo que também foi usado, em um CVE de alguns dias atrás, para quebrar chaves do PuTTY com nonces enviesados
tptacekexplicou um pouco o ataque e também linkou um problema do cryptopals que, se você semicerrar os olhos, dá para quase fingir que entende https://news.ycombinator.com/item?id=40045377De forma parecida, o servidor de Minecraft SciCraft tinha uma fazenda de creepers com algum tipo de dispositivo de magia negra que manipulava deterministicamente o estado do gerador de números aleatórios, fazendo raios “aleatórios” atingirem um bloco específico a cada frame para melhorar os drops dos creepers https://youtu.be/TM7SutJyDCk
Nos três casos, tudo que você precisa é algo como álgebra linear básica, e nem tanto assim. Kelby espera que você entenda Gram-Schmidt, que é conteúdo de pouco antes da prova do meio do semestre em uma disciplina introdutória de álgebra linear na graduação
Não tenho palavras para expressar como esse texto é excelente. Fez minha semana melhorar
Uma explicação muito concisa do mesmo processo, que você pode acompanhar depois em Python:
https://crypto.stackexchange.com/questions/37836/problem-wit...
https://youtu.be/ZcdN1wCJPqM?t=390
Imagine acordar de manhã e ver blocos que não estavam lá na noite anterior flutuando no céu; a princípio parecem fantasmas, como neblina, mas logo se revelam redstone, observadores e blocos de slime, e aparece uma situação de TNT caindo infinitamente
Tudo isso só porque o servidor vazou minha posição. Ainda assim, talvez ainda dê para fugir, e talvez haja tempo para pegar em poucos segundos o que importa no baú e correr, ou construir um abrigo de obsidiana. Mas é só isso
Não há tempo suficiente para construir um canhão de mira precisa e, de qualquer forma, eles nem conseguiriam acertar a altitude. Se você tiver elytra e foguetes, talvez consiga ir atrapalhar, mas há um buraco gigantesco de world eater logo a 16 chunks de distância. Será que colocaram armadilhas de lava em todos os portais do Nether por perto?
Já vi muitos problemas de gerador de números aleatórios interessantes e engraçados, mas este é um dos exploits mais sofisticados para o que se obtém. Parece uma bela obra de arte
É um exploit bem legal
A ideia de um servidor em que explorar bugs é liberado também é boa, e parece uma fase totalmente diferente do jogo
Se o metaverso realmente acontecer, acho que “lutar de verdade”, em vez de simplesmente usar mecânicas de combate dentro do jogo, teria uma cara parecida com isso
Como há muito tempo existem muitos itens caros duplicados, o PvP virou uma questão de ficar espalhando cristais do End, que causam dano enorme ao explodir, enquanto a defesa passou a depender de quantos “totens da imortalidade” você tem para absorver dano fatal
Naturalmente, clientes com hack automatizam o posicionamento de cristais do End, o recarregamento de totens e a identificação de posições fracas e fortes, e o jogador segue essas indicações para continuar causando dano
Um pouco antes disso, também havia espadas hackeadas com +32.767 de dano que matavam instantaneamente, até serem corrigidas no servidor
ARK: Survival Evolved e Eve Online são notórios por terem clãs gigantescos, com milhares de pessoas, levando o metajogo e a exploração de bugs a extremos
Nem sempre é romântico. Em ARK, havia uma mecânica que permitia doxxar jogadores e suas várias contas Steam, e parece que algumas relações dentro do jogo transbordaram para a vida real durante a Great War
Às vezes há métodos bem básicos. Por exemplo, quando estavam sendo atacados, construir uma torre enorme e derrubá-la para causar uma negação de serviço no servidor e fazê-lo cair fazia o servidor voltar para um backup de 10 a 20 minutos antes, tornando muito difícil atacar bases com jogadores ativos. É uma técnica muito antiga e foi corrigida há anos
Rust também teve uma política de incentivar que bugs e exploits fossem divulgados no YouTube e tornados públicos, mas com outro objetivo: fazer os desenvolvedores perceberem e corrigirem mais rápido. O resultado foi um jogo bastante robusto, em que é muito difícil abusar sem usar hacks externos de verdade
Mas são apenas coisas que podem ser exploradas manualmente com um controle comum, não hacks reais. Um exploit chamado Wobbling foi banido em 2019, sendo que o jogo é de 2001
Acabei de ver o vídeo sobre esse tema. É um alerta claro sobre o perigo de fontes de aleatoriedade interagirem entre si, e isso se aplica muito a sistemas importantes também
Por desempenho, muitas vezes se compartilha um gerador de números aleatórios no código, e histórias assim definitivamente fazem pensar duas vezes
Porque parecia que ficaria mais difícil observar pontos suficientes de atualização. Mas este caso mostra, de forma bem impressionante e divertida, que essa intuição estava errada
Este vídeo é surpreendente: https://www.youtube.com/watch?v=maMpMOnIJDE
Eu não fazia ideia de que a comunidade era tão sofisticada
Se isso te surpreendeu, veja estes também. Sua cabeça vai explodir
https://www.youtube.com/watch?v=ea6py9q46QU
E
https://www.youtube.com/watch?v=GaRurhiK-Lk
Indo além, esse tipo de cracking de gerador de números aleatórios já foi implementado até dentro do jogo
https://youtu.be/FPmQ0rnJjNc?si=tTFObcfZ-ILanL_A
Surpreendentemente, existe o Mess Detector, uma máquina construída dentro do próprio Minecraft. Em vez de drops de blocos, ele usa a posição de TNT acesa para prever o estado interno do gerador de números aleatórios
https://www.youtube.com/watch?v=FPmQ0rnJjNc
Isto parece um ataque de extensão por comprometimento de estado (https://en.wikipedia.org/wiki/Random_number_generator_attack)
É um ataque que pode atingir PRNGs que não são geradores pseudoaleatórios criptograficamente seguros (CSPRNGs)
Hoje, a própria ideia de bibliotecas oferecerem PRNG como padrão já não parece muito segura. É parecido com permitir TLSv1.0 ou blowfish por padrão em 2024