As crônicas dos reis da Noruega contam que o rei Olaf Haraldsson, o Santo, disputava com o vizinho rei da Suécia a posse da ilha de Hísing. Eles decidiram resolver a disputa pacificamente com um jogo de dados. Depois de concordar que ganharia a pontuação mais alta, o rei da Suécia jogou os dados primeiro.

-Doze! Ganhei! Você não precisa rolar os dados, rei Olaf.

Enquanto agitava os dados em suas mãos, Olaf, o Santo, respondeu:

«Ainda faltam dois seis nos dados e não será difícil para Deus, meu Senhor, fazê-los aparecer novamente a meu favor.»

Os dados voaram e dois seis voltaram. Mais uma vez, o rei da Suécia lançou os dados e novamente tirou dois seis. Quando chegou a vez de Olaf, o Santo, um dos dados lançados foi dividido em dois, metade mostrando um 6 e o ​​outro um 1, totalizando 13. Como consequência, a propriedade da ilha foi concedida a A Noruega e os dois reis se despediram como amigos.

A aleatoriedade desempenha um papel fundamental em todos os jogos de azar. E o que mais pode te surpreender: a criptografia não poderia existir sem aleatoriedade. Neste artigo você descobrirá como a aleatoriedade é usada na criptografia e como obter números aleatórios, uma tarefa, como você verá, nada fácil.

O que é a aleatoriedade?

Existem tantas definições de aleatoriedade que poderíamos encher um livro com elas. A seguinte interpretação é comum na criptografia, que cito de Bruce Scheneier:

A aleatoriedade se refere ao resultado de um processo probabilístico que produz valores independentes, uniformemente distribuídos e imprevisíveis que não podem ser reproduzidos de forma confiável.

Quero destacar os três ingredientes a seguir que todo gerador aleatório deve exibir para ser usado com garantias em «saladas criptográficas»:

• Independência de valor: não há correlação entre os valores gerados. Por exemplo, se você lançar uma moeda (sem trapacear) e sair cara nove vezes consecutivas, o que é mais provável? Cara ou coroa no 10º lance? Bem, a probabilidade ainda é 1/2, porque o resultado de um lançamento é independente dos lançamentos anteriores.
• Imprevisibilidade: mesmo se você ficar entediado em olhar para valores e mais valores, você não pode prever o próximo valor com maior probabilidade aleatoriamente, não importa quanto tempo a sequência anterior tenha durado. Novamente, moedas, dados e rodas de roleta são excelentes geradores aleatórios porque, independentemente de quantas teorias você inventar, você não saberá o que virá a seguir (supondo que não sejam manipuladas).
• Distribuição uniforme: certamente ao ler a crônica do Santo Rei Olaf você pensou: “Impossível! Como vão sair dois seis quatro vezes seguidas? ». E você faz bem em duvidar, porque a probabilidade dessa sequência é (1/36)·(1/36)·(1/36)·(1/36)=(1/36)⁴ = 0,00000059537… ou 1 entre 1,67 milhões. Essa sequência não é provável, mas é possível. Na verdade, se os dados fossem lançados um bilhão de vezes, eles apareceriam em média 600 vezes. A aleatoriedade, como a imaginamos, se manifesta em grandes números, não em pequenos números. À medida que mais valores são gerados, esperaremos ver todas as sequências possíveis, uniformemente distribuídas, sem qualquer tendência.

O problema da aleatoriedade é que você nunca tem certeza. Os dados dos reis nórdicos foram manipulados? Coincidiu, vejam onde, que coincidência, aquela improvável sequência aconteceu naquele dia? Existem testes de aleatoriedade que determinam com alta confiança se um gerador é aleatório ou não, mas você nunca pode ter certeza absoluta. Na verdade, existe uma ampla gama de suítes de teste estatístico (NIST, Test01, Diehard, ENT, etc.) que tentam descartar sequências que não verificam certas propriedades estatísticas, embora não possam garantir a aleatoriedade perfeita.

Como os números aleatórios são gerados

Sim, mas como você gera números aleatórios em um computador? Para manter as coisas simples, vamos nos limitar a duas abordagens:

• Geradores de bits verdadeiramente aleatórios (TRNG): requerem uma fonte natural de aleatoriedade. Projetar um dispositivo de hardware ou programa de software para aproveitar essa aleatoriedade e produzir uma sequência de bits livre de vieses e correlações é uma tarefa difícil. Por exemplo, o ruído térmico de um resistor é conhecido por ser uma boa fonte de aleatoriedade. Os TRNGs também podem coletar entropia em um sistema operacional em execução por meio do uso de sensores conectados, dispositivos de E/S, atividade de rede ou disco, logs do sistema, processos em execução e atividades do usuário, como pressionamentos de teclas e movimentos. rato. Essas atividades geradas pelo sistema e pelo homem podem funcionar como uma boa fonte de entropia, mas podem ser frágeis e manipuladas por um invasor. Além disso, eles são lentos para produzir bits aleatórios.
• Geradores de números pseudo-aleatórios (PRNG): infelizmente, a maioria das fontes naturais são impraticáveis ​​devido à lentidão inerente da amostragem do processo e à dificuldade de garantir que um adversário não observe o processo. Além disso, seria impossível reproduzi-la, o que exigiria duas cópias da mesma sequência: uma para Alice e outra para Bob, o que implica na dificuldade quase intransponível de conseguir as duas. Portanto, é necessário um método de geração de aleatoriedade que possa ser implementado em software e que seja facilmente reproduzível, quantas vezes forem necessárias. A resposta está em geradores de números pseudo-aleatórios: um algoritmo matemático eficiente e determinístico para transformar uma string curta e uniforme de comprimento k, chamada de seed, em uma string de saída mais longa e de aparência uniforme (ou pseudo-aleatória), de comprimento l>>k. Em outras palavras:

» Um gerador pseudo-aleatório usa uma pequena quantidade de verdadeira aleatoriedade para gerar uma grande quantidade de pseudo-aleatoriedade.»

O que é o uso da aleatoriedade na criptografia

A aleatoriedade é difícil de gerar e difícil de medir. Independentemente disso, é um ingrediente chave para o sucesso de qualquer algoritmo de criptografia. Observe as diferentes funções que a aleatoriedade pode desempenhar para tornar a criptografia segura.

• Chaves de encriptaçao: para criptografar uma mensagem, você precisa de uma chave de encriptaçao, tanto para algoritmos de chave secreta quanto para algoritmos de chave pública. Se essa chave for fácil de adivinhar, que golpe! Um requisito fundamental para o uso seguro de qualquer algoritmo de criptografia é que a chave seja selecionada aleatoriamente (ou o mais aleatoriamente possível). Na verdade, um problema que o ransomware enfrenta é como gerar chaves aleatórias para criptografar os arquivos das vítimas. O melhor algoritmo de criptografia do mundo não vale nada se a chave for revelada. É recomendável usar um dispositivo de hardware para gerá-los, como o TPM de sistemas Windows ou um HSM.
• Vetores de inicialização: algoritmos de cifra de bloco usam um valor inicial aleatório, chamado de vetor de inicialização (IV), para iniciar a criptografia do primeiro bloco e garantir que a mesma mensagem criptografada com a mesma chave nunca retornará o mesmo valor, contanto que um IV diferente seja usado. Este valor pode ser conhecido, mas não previsível. Novamente, é portanto crítico usar valores aleatórios (e imprevisíveis) para evitar a repetição. Mais uma vez, é recomendável ir aos dispositivos de hardware para gerá-los.
• Nonces: um uso único é um número que pode ser usado apenas uma vez (number used once) em um protocolo seguro de comunicação. E que uso podem ter esses nonces fugazes? De forma semelhante ao que foi explicado com os vetores de inicialização, os nonces garantem que mesmo que as mesmas mensagens sejam transmitidas durante uma comunicação, elas serão criptografadas de uma forma completamente diferente, o que evita ataques de repetição ou reinjeção. Na verdade, os nonces geralmente funcionam como IVs: um nonce é geradoe é criptografado com a chave secreta para criar o IV. Eles também são usados ​​em protocolos de autenticação, como em HTTPS, ou para sistemas de prova de trabalho, como em Bitcoin.
• Salts: sal é outro valor aleatório comumente usado ao armazenar senhas em um banco de dados. Como você sabe, as senhas nunca devem ser armazenadas em claro: qualquer invasor que acessasse a tabela do usuário veria as senhas! O hash de senha pode ser armazenado em seu lugar . Mas o que acontecerá se duas senhas forem iguais? Eles vão dar o mesmo hash ! Se um invasor rouba o banco de dados e vê muitos hashes de senha idênticos, bingo! Você sabe que são senhas fáceis, aquelas que todo mundo escolhe quando não está se esforçando. Por outro lado, tabelas de hash de senha gigantescas conhecidas podem ser pré – computadas e procurar esses hashes no banco de dados roubado. Para evitar esses problemas, um valor aleatório é adicionado: sal. A partir de agora, o hash da senha não será salvo , mas o salt e o hash da senha concatenados com o salt: H(senha || salt). Portanto, duas senhas idênticas resultarão em dois hashes diferentes, desde que o salt seja aleatório. Da mesma forma, os ataques que calculam previamente hashes de senhas conhecidas não têm mais nenhuma utilidade. Como os nonces, os sais não precisam ser secretos, mas precisam ser aleatórios. Outra aplicação típica de vendas é em funções de derivação de senhas (KDF). Um esquema muito simples consiste em repetir o hash de uma senha e um salt n vezes :

chave=Hⁿ(senha || salt)

• Preenchimento: o famoso algoritmo de criptografia de chave pública RSA é determinístico, ou seja, a mesma mensagem criptografada com a mesma chave sempre retornará o mesmo texto cifrado. Isso não pode ser! A mensagem clara precisa ser randomizada. Como? Adicionar bits aleatórios com muito cuidado, no que é conhecido como esquema OAEP, que transforma o RSA tradicional em um esquema probabilístico. Da mesma forma, para evitar a maleabilidade da criptografia RSA em assinaturas digitais, o esquema PSS adiciona aleatoriedade.
• Assinaturas cegas: para fazer com que uma pessoa assine digitalmente um documento, mas sem conseguir ver o conteúdo do documento assinado, também são utilizados valores aleatórios que “cegam” o assinante, ocultando o conteúdo da mensagem a ser assinada. Posteriormente, uma vez conhecido o valor aleatório, o valor da assinatura pode ser verificado. É o equivalente digital de assinar um documento colocando nele um papel vegetal: impede que você veja o documento a ser assinado, mas transfere perfeitamente a assinatura para o documento. E quem iria querer assinar algo sem ver primeiro? Esses protocolos de assinatura cega são usados, por exemplo, em votações eletrônicas e aplicações de dinheiro digital.

Sem aleatoriedade não há segurança

Os números aleatórios são de suma importância na criptografia: eles são a base da segurança. A criptografia não pode ser incorporada a produtos e serviços sem números aleatórios. Um gerador de número aleatório inadequado pode facilmente comprometer a segurança de todo o sistema, conforme confirmado pela longa lista de vulnerabilidades devido à baixa aleatoriedade. Portanto, a escolha do gerador aleatório deve ser feita com cuidado ao projetar qualquer solução de segurança. Sem boa aleatoriedade não há segurança.