A inutilidade das lava lamps: o que aleatoriedade realmente significa

• A divulgação da aleatoriedade baseada em lava lamps pela Cloudflare se parece mais com marketing e teatro de segurança do que com uma grande contribuição prática para a criptografia da internet
• Na criptografia, o importante não é a aleatoriedade intrínseca de um valor, mas o quanto um atacante sabe sobre esse valor; essa diferença de conhecimento é o que determina a segurança
• O One-time pad oculta a informação da mensagem se uma chave suficientemente aleatória for usada apenas uma vez, mas quebra quando a mesma chave é reutilizada e combinada com informações observadas
• Sistemas modernos usam CSPRNG e cifras de fluxo no lugar de one-time pads, e ChaCha20 ou AES-256-CTR oferecem segurança prática com uma chave de 256 bits
• RNGs físicos verdadeiros são difíceis de desenviesar e trazem pouco ganho de segurança; um projeto mais simples, em que o próprio servidor gera a semente e usa fast key erasure, é mais seguro

---

A aleatoriedade depende do conhecimento do observador, não do objeto

• A Cloudflare promove o uso de lava lamps como algo que ajuda na criptografia da internet, mas essa abordagem contribui pouco para a segurança e se parece mais com marketing e teatro de segurança
• Além das lava lamps, a Cloudflare também usa dispositivos físicos de imprevisibilidade como double pendulums, wave motion e mobiles
• A função ao estilo XKCD que só faz return 4 sempre retorna 4, então não é aleatória por si só; mas, se quem a chama souber apenas que se trata de uma “constante escolhida com um dado justo” e fizer uma chamada, ela pode ser tratada como aleatória dentro da distribuição de probabilidade do observador
• Na criptografia, a pergunta importante não é se o resultado é intrinsecamente aleatório, e sim o quanto o atacante sabe sobre esse resultado
• Mesmo o mesmo valor pode ter significados diferentes em termos de aleatoriedade dependendo de quem sabe o quê; em sistemas criptográficos, essa diferença de conhecimento determina a segurança

Como o one-time pad funciona e como ele quebra

• Na analogia da roleta russa, o cúmplice sabe onde está a bala e anuncia para o lado de fora apenas o resultado de somar à posição da bala um valor de dado previamente compartilhado com o jogador
• O jogador pode reconstruir a posição da bala subtraindo o valor do dado do número anunciado, mas o adversário não consegue descobrir a posição da bala só com o número anunciado, porque não conhece o valor do dado
• Se o dado for justo, a probabilidade a priori P(Ci) que o adversário tem e a probabilidade a posteriori P(Ci|S3) após ouvir um número específico S3 serão iguais
• Pela fórmula de Bayes, P(Ci|S3) = P(Ci) × 1/6 ÷ 1/6 = P(Ci), então o adversário não aprende absolutamente nada ao ouvir o valor anunciado
• Essa estrutura é o núcleo do One-time pad: se uma chave suficientemente aleatória for combinada com a mensagem uma única vez, o texto cifrado não revela informação sobre o texto original
• Se a mesma chave for reutilizada em um segundo jogo, a informação revelada no primeiro permite ao adversário restringir o conjunto de possibilidades para o valor do dado
• Se no primeiro jogo se confirmar que as quatro primeiras câmaras da arma estão vazias, o adversário passa a saber que o dado só podia ter sido 3 ou 4; se, no segundo, o cúmplice disser “Four”, o adversário ainda aprende que a bala está ou na primeira câmara ou na última
• O One-time pad é seguro exatamente uma vez, como o nome diz; se a mesma chave for reutilizada, o texto cifrado observado se combina com informações anteriores e a segurança colapsa

Tamanho de chave e a segurança prática da criptografia moderna

• Na internet, enviamos bits e bytes em vez da posição da bala, e uma mensagem de um bit com “sim/não” pode ser ocultada com um único lançamento de moeda
• Se der cara, a mensagem é mantida; se der coroa, “sim” e “não” são invertidos, o que esconde a mensagem original de um observador que não conhece o resultado da moeda
• Mas, se o mesmo resultado da moeda for usado para cifrar dois bits, o texto cifrado reduz as quatro mensagens possíveis a duas
  • “Yes yes” significa que a mensagem original era “yes yes” ou “no no”
  • “No no” significa que a mensagem original era “no no” ou “yes yes”
  • “Yes no” significa que a mensagem original era “yes no” ou “no yes”
  • “No yes” significa que a mensagem original era “no yes” ou “yes no”
• Generalizando, ao cifrar n bits com um único lançamento de moeda, o espaço de mensagens possíveis cai de 2^n para 2
• Em sentido informacional completo, para cifrar corretamente n bits são necessários n bits de chave; em mensagens maiores que isso, partes acabam sendo decifradas, e se o observador já souber mais de n bits de informação, em geral toda a mensagem pode ser recuperada
• Aplicar one-time pads a todo o tráfego processado pela Cloudflare exigiria uma quantidade astronômica de números aleatórios, mas os sistemas modernos não usam one-time pads
• Com uso correto de criptografia autenticada e cifras de fluxo, uma chave de 256 bits pode cifrar muito dado com segurança prática
• Usando uma cifra de fluxo adequada como ChaCha20 ou AES-256-CTR, um observador passivo teria de tentar cerca de 2^255 combinações para descobrir o texto original
• Para quem conhece a chave, o fluxo é totalmente previsível; para um observador no nível de uma civilização planetária que não conhece a chave, ele se comporta como uma “entropia” completamente imprevisível
• O nome formal disso é Cryptographically Secure Pseudo-Random Number Generator, abreviado como CSPRNG

Geração real de números aleatórios e fast key erasure

• Para derivar todos os números aleatórios necessários a partir de uma única chave mestra de 256 bits, é possível manter a chave mestra em um servidor mestre ou módulo de segurança de hardware, gerar um fluxo local de chaves e distribuí-lo com segurança por toda a empresa
• Cada servidor ou núcleo de CPU pode gerar quantos bytes aleatórios forem necessários usando uma chave local de 256 bits e um contador
• O problema central é que a distribuição segura é muito difícil
• Se uma chave local vazar, todas as mensagens que aquela máquina cifrou no passado e cifrará no futuro ficam em risco; se a chave mestra vazar, o impacto é muito maior
• fast key erasure é um procedimento para reduzir tanto a chance de vazamento quanto o dano caso ele ocorra
  • Coloca-se uma semente aleatória de 32 bytes no início de um buffer de 512 bytes
  • Essa semente gera 512 bytes que sobrescrevem o buffer
  • Tudo após os primeiros 32 bytes é emitido sob demanda e depois apagado
  • Quando o buffer acaba, o processo volta à etapa de geração
• O termo “erasure” vem do fato de que a etapa de geração apaga a chave anterior
• Se o buffer vazar, mensagens futuras podem ficar em risco, mas valores passados, que já foram emitidos e apagados, permanecem protegidos
• Um cuidado ainda mais importante é não duplicar o buffer
  • Não se deve criar dois fluxos com a mesma semente
  • Ao fazer fork de um processo, o fluxo deve ser dividido corretamente em dois
• Se surgirem dois ou mais fluxos idênticos, os mesmos bytes aleatórios serão repetidos, o que pode ser catastrófico
• Por isso, RNG em espaço de usuário não é recomendado; o RNG do kernel, embora não seja simples, reduz a quantidade de componentes que precisam ser auditados

Escolha da cifra de fluxo e margem de segurança

• O tamanho do bloco interno da cifra de fluxo subjacente também importa
• O bloco de 512 bits do ChaCha20 é grande o bastante para não ser motivo de preocupação, e o bloco de 128 bits do AES também é suficientemente grande
• Existem ataques práticos contra o AES com probabilidade de sucesso muito melhor que força bruta simples; considera-se que o AES-128 pode ser quebrado, mas o AES-256 é seguro
• Blocos menores devem ser considerados quebrados para esse uso
• As escolhas recomendadas são ChaCha20 ou AES-256, com preferência por ChaCha20
• Cifras de fluxo modernas são extremamente seguras e, considerando a literatura acadêmica e o uso por diversos governos, especialmente os Estados Unidos, é muito improvável que sejam quebradas em um futuro próximo
• Como CSPRNG e criptografia dependem ambos de cifras, se uma delas for quebrada, o sistema inteiro quebra junto
• Se você assumir que existe uma chance significativa de AES-256 ou ChaCha20 serem quebrados em breve, há formas de aumentar a margem de segurança
  • Se o mesmo algoritmo for usado no CSPRNG e na criptografia, elimina-se a possibilidade de o atacante escolher entre quebrar AES ou ChaCha; ele precisará quebrar um algoritmo específico
  • Aumentar o número de rodadas ajuda não só contra força bruta, mas também contra ataques melhores que força bruta
  • O AES-256 usa 14 rodadas, e o ChaCha20 usa 20 rodadas
  • Há ataques contra o ChaCha7 melhores do que exhaustive search, mas atualmente não há ataques desse tipo contra o ChaCha8
  • O ChaCha20 usa 20 rodadas para manter folga suficiente caso um ataque de 12 rodadas apareça de repente
• Usar vários sistemas em paralelo aumenta muito a complexidade total, e essa complexidade tem mais chance de criar vulnerabilidades fatais do que um ataque matemático contra um dos componentes

True RNG físico e a semente inicial

• É preciso cautela com a ideia de que um true RNG físico seja mais seguro do que um CSPRNG teoricamente quebrável
• Em muitos casos, para segurança, a saída aleatória precisa não ter viés detectável, o que significa uma distribuição uniforme a ponto de não se conseguir detectar viés nem mesmo analisando 2^64 amostras
• Como é difícil ajustar processos físicos a esse nível, na prática a saída da fonte de ruído precisa passar por um hash criptográfico
• Comparado com uma cifra de fluxo com fast key erasure, o ganho de segurança é pequeno, enquanto o custo de desempenho pode ser alto, dependendo da necessidade
• Para produzir qualquer quantidade de números aleatórios, ainda é preciso uma semente inicial com alguns bytes
• É possível obter uma semente mestra registrando digitalmente por tempo suficiente uma fonte imprevisível para reunir mais de 256 bits de entropia e então aplicar um hash de 256 bits, como SHA-256 ou BLAKE2s, sobre esse registro
• Fontes possíveis de aleatoriedade incluem hardware random number generator, jitter da CPU, uma foto aleatória de uma árvore, beam splitter, eventos de teclado ou mouse, dados etc.
• Distribuir números aleatórios entre sites não é prático; além de complexo, pode se tornar uma fonte de comprometimento
• Números aleatórios não são necessários só uma vez, mas sempre que houver suspeita de comprometimento ou quando for feita uma atualização importante de segurança
• Para reduzir incômodo e risco, em geral é melhor que o próprio computador gere a semente aleatória que vai usar, em vez de buscá-la externamente
• Servidores comuns já têm jitter da CPU, interação com periféricos e eventos de rede, o que normalmente é suficiente para usos gerais
• Se quiser segurança adicional, é possível adicionar alguns dongles de RNG por hardware por rack de servidores, mas qualquer solução mais complexa do que isso é complexidade desnecessária

Por que a parede de lava lamps é desnecessária

• A parede de lava lamps da Cloudflare não é necessária e, ao conectar-se aos servidores pela rede local, ela apenas aumenta a complexidade e a superfície de ataque
• Se for implementada corretamente, o risco pode ser muito baixo, mas ainda assim maior do que o benefício obtido
• Se a Cloudflare leva segurança realmente a sério, deveria parar de usar lava lamps e deixá-las apenas como decoração e marketing
• É mais simples e mais seguro que cada servidor gere seus próprios números aleatórios diretamente
• É possível que a Cloudflare já faça isso

[GN⁺]

Comentários no Lobste.rs

• Este texto parece ter sido escrito com alguns equívocos e ainda por cima soa um pouco estraga-prazeres. A geração moderna de números aleatórios usa várias fontes independentes de entropia, e enquanto o computador está em funcionamento vai misturando tudo continuamente no pool de entropia por meio de hash
  O computador não tem uma única “semente aleatória”; ele é continuamente resemeado em tempo de execução usando a entropia de várias fontes, em algo como seed = hash(seed, new_data). Adicionar dados de uma câmera filmando lâmpadas de lava nunca reduz a segurança do sistema. Os dados que entram no pool de entropia já são combinados por hash com outros dados que já estavam lá. O sistema é projetado para ser seguro desde que exista ao menos um pouquinho de informação desconhecida para o atacante, então misturar muitos dados com graus variados de aleatoriedade não prejudica a segurança
  As lâmpadas de lava não prejudicam a segurança do sistema e, pessoalmente, eu as vejo como uma obra de arte divertida e funcional que faz parte do sistema. Elas também melhoram a qualidade dos números aleatórios, ainda que de forma extremamente pequena, e tornam visuais os conceitos de aleatoriedade e entropia

  • Sim, mas os geradores aleatórios do kernel já usam há mais de 30 anos vários tipos de aleatoriedade de hardware, e é melhor não exagerar o quanto eles são resemeados “continuamente” ou “sem parar”
    A aleatoriedade do hardware é coletada continuamente, mas o gerador aleatório do Linux é resemeado periodicamente. No primeiro minuto após o boot, isso acontece a cada poucos segundos; depois, desacelera para algo como uma vez por minuto

    https://zx2c4.com/projects/linux-rng-5.17-5.18/…

  • Não sei de onde veio a impressão de que eu disse ou sugeri que os sistemas existentes não funcionam assim. Aqui, tirando a parte das lâmpadas de lava, eu não estava tentando descrever os sistemas atuais, mas sim destacar quão pouco realmente precisamos: 256 bits bastam
    Quando se diz que adicionar dados de uma câmera filmando lâmpadas de lava não reduz a segurança, eu penso em superfície de ataque. Você está adicionando um computador embarcado e comunicação de rede entre esse computador e um servidor. Para mim, esse pequeno risco adicional parece muito maior do que o risco absurdamente baixo de que lâmpadas de lava realmente venham a ser necessárias

• Uma forma diferente de expressar a distinção filosófica seria esta: quantos resultados possíveis existem, e quão previsível é o resultado
  Para fins criptográficos, a previsibilidade ficou estabelecida no nível de 2^-256, mas curiosamente existem processos comuns com um número muito maior de resultados possíveis, e às vezes queremos poder produzir todos os resultados possíveis, por menor que seja a probabilidade. Nessas situações, a aleatoriedade criptográfica pode não ser suficiente
  Um baralho padrão tem 52! embaralhamentos, o que dá cerca de 2^226, então uma semente criptograficamente aleatória consegue gerar todos os embaralhamentos. Mas se você estiver jogando Uno ou misturando vários baralhos juntos, um gerador de números aleatórios de 256 bits não tem estado suficiente para produzir todos os embaralhamentos. Se toda a aleatoriedade em espaço de usuário do sistema vier do kernel, e o kernel estiver passando toda a aleatoriedade de hardware por um CSPRNG de 256 bits, talvez isso não seja suficiente para embaralhar cartas em Las Vegas :-)
  O que faltou no texto foi resemeadura, que é um tema interessante por mostrar como ela interage com o fast key erasure e a dificuldade de obter a semente inicial. O texto dá a entender que o Linux usa apenas jitter de CPU, mas isso é uma simplificação excessiva. O Linux usa muitas fontes de aleatoriedade, e a dança do jitter é usada só como último recurso

  • Não. No mundo real, absolutamente nunca se faz isso desse jeito
    No mundo real, você nunca conseguiria nem obter 2^128 amostras. Na verdade, muito menos do que isso, e é por isso que o AES-128 ainda é seguro o bastante para muitos usos. Quando o número de resultados possíveis é maior que 2^256, “executar todos os resultados possíveis” é totalmente impossível. É melhor esquecer isso. Isso não existe
    Mesmo no blackjack, usando 6 baralhos em vez de 1, o que você quer na prática não é um processo de embaralhamento cuja probabilidade esteja uniformemente distribuída sobre todos os embaralhamentos possíveis. Basta uma distribuição boa o suficiente para que, mesmo coletando o máximo de amostras possível, você não consiga distinguir a diferença. Mesmo que o número de embaralhamentos fique limitado a 2^256, ou até 2^128, você não perceberia diferença
    Omiti a resemeadura de propósito. Ela só é necessária em momentos específicos, como suspeita de comprometimento e algumas atualizações de segurança. Isso também vale para reboot, caso seja mais simples ou mais seguro do que manter o estado do gerador aleatório em memória não volátil. Por isso, prefiro ver isso não como “resemeadura”, mas como reiniciar com uma nova semente inicial
    Em operação normal, não há necessidade alguma de resemeadura. Implementar isso só aumentaria a complexidade
    A insinuação de que o Linux usa apenas jitter de CPU eu deveria ter verificado. Pelo que eu entendia, no momento do boot aquilo era a única fonte. Em especial antes de haver entrada do usuário e tráfego de rede, eu achava que era isso. Você conhece outras fontes? Imagino que já haja suporte a geradores aleatórios de hardware
  • Essa distinção entre possibilidade e previsibilidade me lembrou o artigo de Shamir, Rivest e Adleman. O artigo prova que é matematicamente impossível que duas pessoas joguem pôquer com segurança por telefone usando um baralho virtual
    Não dá. Mas, deixando isso de lado, eis aqui uma forma de fazer isso com segurança...
  • Interessante. Se me lembro bem, ler de uma fonte de aleatoriedade verdadeira é uma operação bloqueante, então, se o kernel não tiver bytes aleatórios suficientes, pode demorar bastante até conseguir ler aleatoriedade suficiente
    Meu palpite é que placas de hardware para geração aleatória existiam não só pela densidade de bits, mas também para obter fontes paralelas de aleatoriedade medidas em bits por unidade de tempo

• Não há muitas afirmações individuais das quais eu discorde fortemente, mas o argumento geral me pareceu meio nebuloso. O texto constrói tudo em torno da ideia de que “a criptografia moderna precisa de muito menos aleatoriedade real do que as pessoas imaginam” e depois aterrissa em “logo, lâmpadas de lava são piores porque ampliam a superfície de ataque”
  As duas afirmações podem ser verdadeiras, mas a passagem de uma para a conclusão parece brusca

  • Sinceramente, a estrutura narrativa não me parece tão satisfatória. Ainda assim, metade da conclusão já estava no título

• O LavaRand já fazia esse tipo de coisa há mais de 20 anos. Na época era fofo, mas os sensores de câmera daquele tempo eram muito menores e, por características previsíveis como as das lentes, não eram boas fontes de entropia
  Eu gosto de lâmpadas de lava, mas o consumo elétrico de uma parede com centenas delas me parece bem alto para um dispositivo tão de brinquedo

• Está mais para autopromoção. Quase não compartilha links e, quando compartilha, publica links próprios. Os 5 posts mais recentes, todos os 5, apontam para material dele

  • Isso depende de como você interpreta “stories and comments”
    “É bom que o autor participe da comunidade, mas isso não deve ser abusado como uma ferramenta de mão única para anunciar produtos ou direcionar tráfego ao próprio trabalho. Como regra prática, autopromoção deve ficar abaixo de um quarto de suas stories e comments.”
    Com 15 postagens e 1399 comentários, ele claramente participa da comunidade. Isso, claro, se ele não estiver deixando mais de 90 comentários próprios em cada um dos próprios posts

• A Cloudflare contribuiu com entropia obtida de lâmpadas de lava, a University of Chile com dados sísmicos, e, se bem me lembro, a EPFL com medições de decaimento radioativo, além de vários outros participantes que contribuíram com materiais diversos para a cerimônia inicial de geração de chaves da rede drand
  Poderiam ter usado um CSPRNG? Claro. Mas aí onde estaria a graça?

  • A graça é válida. As lâmpadas de lava são bonitas, e a parede ondulante delas é realmente bela. O problema é quando isso cruza a linha e finge ajudar na segurança de verdade