Criptografia aplicada. Como restauramos bitcoins por 300 mil dólares

Vou compartilhar com você uma história. Cerca de vinte anos atrás, me formei em física, mas estava envolvido em engenharia reversa e criptoanálise. Nossa empresa AccessData trabalhou no final dos anos 90 e início dos anos 2000. Então o governo dos EUA gradualmente levantou restrições à exportação de criptografia, no entanto, a proteção por senha na maioria dos programas ainda era bastante inútil. Pegamos programas de escritório, realizei engenharia reversa e descobri o algoritmo de criptografia e depois quebrei a proteção criptográfica.

Era um fluxo interminável de quebra-cabeças matemáticos interessantes, mas não particularmente difíceis. Durante todo o tempo, escrevi cerca de quarenta crackers de senha. Nós os vendemos para usuários domésticos, administradores de sistema e agências de aplicação da lei locais e federais. Eu tive que ir ao centro federal de treinamento de aplicação da lei em Glinko várias vezes para explicar aos funcionários do Serviço Secreto, do FBI e do ATF os conceitos básicos de criptografia e como usar nossos produtos.

Lembro-me especialmente de dois projetos. O primeiro foi o Microsoft Word 97. Antes de aparecer, os arquivos eram criptografados usando bytes XOR de texto não criptografado e uma string de 16 bytes que era emitida pela senha. Os bytes mais comuns em um arquivo do Word geralmente eram 0x00, 0xFF ou 0x20 (espaço), então escolhemos o caractere mais comum em cada coluna e verificamos de 3 a ¹⁶ opções. A recuperação de chave geralmente acontecia instantaneamente, mas para que as pessoas não pensassem que haviam desperdiçado dinheiro, inserimos uma pequena animação semelhante à cena dos hackers de Hollywood com muitos caracteres aleatórios, a partir dos quais a senha correta emerge gradualmente.

Microsoft Word 97 mudou tudo. Talvez o MSDN também tenha revelado o formato de criptografia, mas nossa pequena empresa não podia pagar por uma assinatura. E não o fato de termos permissão para escrever um programa para hackers após o recebimento de informações. Para entender, no SoftICE defini um ponto de interrupção imediatamente após inserir a senha e, em seguida, subi lentamente a pilha até encontrar um algoritmo. Isso foi antes do lançamento do IDA Pro, então eu tinha dezenas de páginas de impressões com um código de montador riscado com um marcador vermelho na parede. Fiquei muito satisfeito quando finalmente descobri. Naquela época, a Microsoft tinha permissão para exportar apenas criptografia de 40 bits; portanto, a empresa implementou obedientemente a criptografia estritamente permitida: eles repetidamente dividiram a senha no MD5 usando "salt" (bytes selecionados aleatoriamente no arquivo),para obter uma chave de 40 bits, o sal foi adicionado a ela e misturado novamente. A verificação de senha nos computadores da época levou cerca de meio segundo. Tivemos que usar um ataque de dicionário porque era quase impossível decifrar uma senha com força bruta. Como resultado, escrevemos um quebra-senha para grandes empresas e agências. O programa executou a força bruta de um espaço de chave de 40 bits usando estas instruções sofisticadas do MMX Pentium. Ouvi dizer que uma vez ela trabalhou nove meses antes de eu pegar a senha.O programa executou a força bruta de um espaço de chave de 40 bits usando estas instruções sofisticadas do MMX Pentium. Ouvi dizer que uma vez ela trabalhou nove meses antes de eu pegar a senha.O programa executou a força bruta de um espaço de chave de 40 bits usando estas instruções sofisticadas do MMX Pentium. Ouvi dizer que uma vez ela trabalhou nove meses antes de eu pegar a senha.

Outro projeto realmente divertido são os arquivos zip. Phil Katz, criador do PKZIP, tomou uma decisão incomum naquela época para documentar seu formato de arquivo e incluir essa documentação no pacote de software, que fez do ZIP o formato favorito dos desenvolvedores. Roger Schlafly desenvolveu uma cifra de fluxo para criptografar arquivos. O padrão zip rapidamente se tornou o mais popular no Windows, e muitos outros formatos, como arquivos .jar java e documentos do OpenOffice, eram na verdade arquivos zip com uma estrutura de diretórios específica. A versão de código aberto do programa chamava-se InfoZIP, era a base de quase todos os arquivadores proprietários, como o WinZip. Quando comecei a hackear o WinZip, ele ocupava 95% do mercado.

Eli Biham e Paul Kocher publicaram uma descrição do ataque com texto simples conhecido (texto antes da criptografia), mas, no nosso caso, o texto simples conhecido foi arquivado . Para obter os códigos Huffman no início de um arquivo compactado, você precisa essencialmente do arquivo inteiro. O ataque foi praticamente inútil para a aplicação da lei.

O fecho de correr cifra contém 96 bits de estado interno, divididas em três blocos de 32 bits denominado key0, key1ekey2. O primeiro e o terceiro são o estado interno de duas cópias do CRC32, um registro de deslocamento linear com feedback (um modelo matemático simples que permite criar sequências pseudo-aleatórias). Se, em suma, para atualizar o estado com um novo byte de dados, reduza tudo em um byte (descartando o byte inferior) e faça do XOR c uma constante da tabela de conversão indexada pelo byte de dados após o XOR com o byte inferior. key1É o estado interno de um gerador congruente linear truncado (TLCG). Para atualizar seu estado interno, adicionamos um byte de dados, multiplicado por uma constante, que chamaremosce adicione um. A cifra funciona da seguinte maneira: insira o byte de dados no primeiro CRC32, pegue o byte inferior e o TLCG, pegue o byte superior e insira o segundo CRC32, pegue o estado e o quadrado (aproximadamente) e emita o segundo byte resultar em um fluxo de bytes. Para inicializar 96 bits do estado interno, você começa com um estado conhecido e criptografa a senha e depois criptografa dez bytes de salt.

O PKZIP obtém seus bytes de sal, alocando memória sem inicializá-lo, para que contenha pedaços de materiais de outros programas, imagens ou documentos em execução, o que for. Isso funcionou bem no Windows, mas em muitos sistemas Unix, a memória é inicializada automaticamente quando alocada. InfoZIP seleciona bytes de sal usando a funçãorandLinguagem C. Ele inicializou o estado do gerador de números aleatórios criando um registro de data e hora XOR no ID do processo e, em seguida, gerou dez bytes por arquivo. Nesse caso, sabendo o registro de data e hora e o identificador do processo, foi possível, teoricamente, recuperar os bytes do cabeçalho, o que, por sua vez, possibilitou o ataque de Biham e Kocher. Parece que os autores do InfoZIP sabiam desse ataque porque foram um passo adiante - e criptografaram o cabeçalho usando uma senha. Portanto, o invasor tinha apenas o dobro do texto criptografado e o ataque não teria funcionado.

Percebi isso, porque a senha é a mesma em ambas as passagens, o primeiro byte do fluxo é o mesmo em cada uma delas. Da mesma maneira que quando o interruptor da luz é alternado duas vezes, ele permanece onde estava no início, quando o byte é repetido XOR com o mesmo byte de fluxo, ele permanece intocado. Isso me permitiu desenvolver um ataque muito poderoso apenas no texto cifrado : tendo recebido cinco arquivos criptografados no arquivo morto, eu pude exibir o estado interno da funçãorandsem precisar olhar para o carimbo de data / hora ou saber o ID do processo. Então eu poderia gerar os cabeçalhos não criptografados originais. Como apenas alguns bits em cada parte da cifra afetam a próxima parte, eu também poderia adivinhar alguns bits de status e verificar se a decodificação dos próximos bytes duas vezes fornece a resposta que eu esperava. Ao avançar, tive que adivinhar cada vez menos pedaços da chave. Cada arquivo adicional também permitiu excluir mais materiais importantes em potencial; naquele momento, levou várias horas em um desktop. Publiquei um artigo sobre isso e tive a oportunidade de apresentá-lo no Japão na conferência Fast Software Encryption 2001.

Logo saí do AccessData, trabalhei por uma startup em redes neurais por um ano, passei três anos estudando um mestrado em ciência da computação na Universidade de Auckland com Chris Kaloud, iniciei meus estudos de doutorado com o físico matemático John Baez na Universidade da Califórnia em Riverside, trabalhei por seis anos Como parte da equipe de segurança aplicada do Google, ele concluiu seu doutorado e, alguns anos depois, tornou-se o CTO da nova startup.

Cerca de meio ano atrás, recebi inesperadamente uma mensagem no LinkedIn de um russo. Ele leu o artigo que escrevi há 19 anos e queria saber se o ataque funcionaria em um arquivo que contém apenas dois arquivos. Uma análise rápida mostrou que requer uma enorme quantidade de poder e dinheiro de computação. Como existem apenas dois arquivos, em cada estágio da seleção, há muito mais falsos positivos. O resultado são ^2.773 chaves possíveis para testes, quase 10 sextilhões. Calculei que um grande cluster na GPU funcionará por um ano e seu custo será de cerca de 100 mil dólares. Ele me bateu, dizendo que concordou em gastar tanto dinheiro para restaurar a chave.

O fato é que, em janeiro de 2016, ele comprou bitcoins por cerca de US $ 10 a 15 mil e colocou as chaves em um arquivo zip criptografado. Agora eles custam mais de US $ 300 mil, e ele não conseguia se lembrar da senha. Felizmente, ele ainda tinha o laptop original e sabia exatamente o tempo de criptografia. Como o InfoZip gera entropia com base em um carimbo de data / hora, isso prometeu reduzir significativamente o número de opções-chave possíveis "para apenas" 10 quintilhões - e tornou o ataque bastante viável em alguns meses em um farm de GPU médio. Assinamos um contrato e eu comecei a trabalhar.

Passei algum tempo recuperando o ataque descrito no artigo. Para meu desgosto, houve alguns detalhes complicados que eu perdi no artigo, mas os resolvi novamente. E então eu descobri que havia cometido um erro terrível ao avaliar a quantidade de computação!

No meu ataque original, adivinhei os altos bytes das teclas key1 · c, key1 · c ² , key1 · c ³ e key1 · c ⁴ . Quando adivinhei esse quarto byte, já sabia o estado completo do resto da cifra; Eu só precisava converter esses quatro bytes na chave original1, e é isso. Eu examinaria o espaço de estado de 32 bits da chave1 e verificaria cada uma para ver se ela fornece os bytes altos corretos. No entanto, aqui teria que verificar quintilhões de chaves; se você precisar fazer 2 ³² testes em cada um, levaria várias centenas de milhares de anos.

Lembrei-me vagamente de que algum trabalho havia sido feito na análise criptográfica do TLCG por meio da redução da base de treliça, então desenterrei o artigo original. Então foi! Foi apenas necessário determinar a rede com os vetores de base dados por 2 ³² e o grau de constante de TLCG e, em seguida, fazer a redução da base da rede. Em uma base reduzida, eu poderia restaurar o estado original de bytes altos simplesmente multiplicando as matrizes.

Pelo menos essa é a ideia. Foram necessários cinco bytes para chegar ao único resultado correto e, naquela época, eu tinha apenas quatro ataques. O processo descrito no artigo raramente dava a resposta correta. No entanto, eu sabia que a resposta deveria estar próxima da correta, para que eu pudesse revisar todos os valores possíveis da chave1 e verificar a diferença entre a resposta real e a verdadeira. A diferença sempre foi um dos 36 vetores! Com essa otimização, posso reduzir a pesquisa para apenas 36 opções em vez de quatro bilhões. Ainda estamos no negócio.

Além disso, enfrentamos o problema de transferir dados entre máquinas com uma GPU. Meu parceiro de negócios, Nash Foster, estava envolvido na implementação da GPU. Ele me aconselhou a rapidez com que várias operações são executadas e escreveu a maioria das estruturas de suporte para o aplicativo com meu código para quebra de criptografia. Como obter esses petabytes de chaves candidatas para testes de GPU? Eles ficam ociosos quase o tempo todo, jogando seus núcleos em antecipação ao trabalho. Ocorreu-me que, em todas as etapas do meu ataque, muitos bits são verificados e, em seguida, apenas um dos cerca de 65 mil candidatos é salvo. Se eu pudesse encontrar uma maneira de produziresses bits são baseados nas informações disponíveis, e não apenas em força bruta, eu economizaria muito trabalho e, mais importante, muito tráfego de rede. O problema aqui eram algoritmos muito complicados, representando uma mistura de campos finitos com anéis de números inteiros, mas eles não se encaixam muito bem um com o outro.

Pensei em outros ataques criptoanalíticos que conheço. Um deles foi o ataque "meet-in-the-middle". Ela parecia uma candidata promissora. O ataque é aplicado a uma cifra de bloco quando ele usa uma parte do material da chave para executar a primeira metade da criptografia e a outra parte para a segunda. Isso se aplicava à cifra zip, mas o material principal superava em muito o número de bits no meio. Então me ocorreu: e se usarmos a linearidade do CRC32: se executarmos a operação XOR nas duas saídas do último CRC32, o resultado será independente da chave2! Em vez de calcular o estado intermediário da cifra e armazená-lo em uma tabela, eu calcularia o XOR dos dois estados intermediários e o armazenaria.

Eu escrevi uma reunião diferencial “reunião no meio” e a lancei no meu laptop. O estágio, que costumava levar várias horas, agora é concluído em apenas alguns segundos. O próximo estágio, que poderia levar uma semana no farm de GPU, terminou em algumas horas em uma CPU poderosa. Não consegui otimizar o terceiro estágio do ataque o suficiente para afetar a velocidade geral, mas não havia necessidade de mover os dados completamente: apenas calculamos os candidatos para cada GPU no computador com esses cartões. Nash escreveu o código GPU que funcionava a uma velocidade incrível.

O ataque durou dez dias e terminou em fracasso.

Meu coração foi quebrado. Estamos perdendo uma das chaves possíveis? Voltamos e examinamos o identificador de processo máximo em seu laptop e descobrimos que ele era vários bits a mais do que esperávamos, e, portanto, havia um pouco mais de sementes de origem possíveis rand. Eu também verifiquei todo o nosso código. Talvez tenhamos perdido alguma coisa? Talvez a versão na CPU tenha funcionado de maneira diferente da GPU? Por fim, descobri que a versão na GPU não conseguia encontrar a chave correta quando era a segunda na lista de candidatos, mas apenas a primeira. Revendo o código, descobrimos que confundimos o índice de bloco com o índice de fluxo ao calcular o deslocamento na estrutura de dados.

Corrigimos o erro, executamos novamente o código e encontramos a chave correta em um dia. Nosso cliente ficou muito satisfeito e nos deu um grande bônus por encontrar a chave tão rapidamente e economizar muito dinheiro além da estimativa inicial.

Agora estou procurando trabalho. Se você tiver problemas interessantes com análise técnica ou otimização, me avise.

---