filippo.io/mlkem768: criptografia pós-quântica para o ecossistema Go

 (words.filippo.io)
1 pontos por GN⁺ 2024-02-02 | 1 comentários | Compartilhar no WhatsApp
  • filippo.io/mlkem768 é uma implementação em Go puro do ML-KEM-768, em processo de padronização pelo NIST, permitindo avaliar troca de chaves pós-quântica no ecossistema Go
  • Composto por cerca de 500 linhas de código, 200 linhas de comentários e 650 linhas de testes, sem dependências além de golang.org/x/crypto/sha3, em um formato fácil de levar para um pacote interno da biblioteca padrão do Go
  • Escrito seguindo diretamente a especificação FIPS 203, sem portar a implementação de referência pq-crystals, para verificar se é possível criar uma implementação interoperável apenas a partir da especificação
  • As áreas mais difíceis são compressão/descompressão e operações em tempo constante; usa redução de Barrett para evitar o risco de instruções DIV de tempo variável que poderiam surgir na família de implementações derivadas da referência
  • Embora otimização de desempenho não seja o objetivo principal, o caminho de Bob é semelhante ao X25519 e P-256 do Go, e o caminho de Alice fica abaixo de 2x, mostrando velocidade prática mesmo com uma implementação simples

Implementação em Go puro do ML-KEM-768

  • filippo.io/mlkem768 é uma implementação em Go puro do ML-KEM-768, priorizando correção e legibilidade
  • ML-KEM era anteriormente conhecido como Kyber e é um mecanismo de troca de chaves pós-quântico em processo de padronização pelo NIST
  • O pacote é composto por cerca de 500 linhas de código, 200 linhas de comentários e 650 linhas de testes
  • A única dependência é golang.org/x/crypto/sha3
  • O objetivo é fazer upstream para a biblioteca padrão do Go, inicialmente como um pacote interno de uso exclusivo planejado para experimentos opt-in em crypto/tls

Abordagem de implementação seguindo fielmente o FIPS 203

  • Esta implementação foi escrita do zero, sem portar a biblioteca de referência pq-crystals e sem ler detalhadamente outras bases de código
  • O objetivo central era verificar se seria possível criar uma implementação interoperável apenas a partir da especificação
  • O documento FIPS 203 fornece pseudocódigo detalhado, definições completas e informações de tipo consistentes, sendo adequado como guia de implementação
  • Nomes de funções, nomes de variáveis e ordem das operações refletem a especificação FIPS tanto quanto possível para facilitar revisão e aprendizado
  • A base matemática necessária para implementar ML-KEM foi organizada separadamente em Enough Polynomials and Linear Algebra to Implement Kyber

Compressão/descompressão e implementação em tempo constante

  • Restavam três desafios centrais de implementação
    • Implementar aritmética modular para o primo 3329
    • Implementar funções de compressão/descompressão que mapeiam valores em [0, 3329) para [0, 2ᵈ) e de volta
    • Garantir operações em tempo constante
  • A aritmética modular foi relativamente fácil graças à experiência acumulada com implementações de RSA e curvas elípticas, e o primo pequeno simplificou a implementação
  • Compressão e descompressão foram a parte mais difícil
    • A especificação define isso de forma abstrata com frações e regras de arredondamento
    • A implementação real precisa tratar isso com aritmética em tempo constante e operações de bits
  • A implementação de referência e muitas de suas portas usavam divisão que, dependendo da otimização do compilador e da plataforma, poderia se tornar uma instrução DIV de tempo variável
  • Este pacote usou redução de Barrett desde o início e não foi afetado; o BoringSSL usa a mesma abordagem

Por que mirar apenas ML-KEM-768

  • A implementação mira apenas ML-KEM-768 entre os três níveis de segurança do ML-KEM: -512, -768 e -1024
  • A equipe Kyber recomenda usar -768 em vez de -512 por uma margem de segurança mais conservadora contra novas criptoanálises
  • -1024 é descrito como uma opção pelos mesmos motivos do nível de segurança de 256 bits: conformidade regulatória e alinhamento de força (strength matching)
  • Como a maioria dos protocolos experimentais ou em padronização convergiu para ML-KEM-768, mirar um único nível quase não aumenta o custo
  • Mirar um único nível reduz as partes móveis, favorecendo legibilidade, segurança e desempenho
    • Por exemplo, em vez de tratar a serialização de inteiros de 1, 4, 10 e 12 bits com um único codificador genérico, ela é separada em codificadores e decodificadores dedicados
    • Como o alvo é apenas ML-KEM-768, não foi necessário implementar codificações de 5 e 11 bits

Estratégia de testes e vetores de teste públicos

  • Os testes são o segundo eixo mais importante da estratégia de garantia de segurança deste pacote, depois da legibilidade
  • Os testes básicos incluem roundtrip de geração de chave, encapsulamento e desencapsulamento, além de mais de 95% de cobertura de testes
  • O escopo adicional de testes inclui
    • Verificação de interoperabilidade com vetores de teste do NIST e de outras implementações
    • Comparação de todas as combinações de entrada de adição, subtração e multiplicação módulo 3329 com valores esperados calculados por um método de tempo variável
    • Teste exaustivo de compressão/descompressão contra math/big.Rat
    • Verificação de que constantes pré-computadas correspondem às definições
    • Verificação de que todas as entradas de função retornam erro adequado quando o comprimento é longo ou curto demais
    • Execução de vetores de teste fornecidos por Sophie Schmieg, que futuramente serão incluídos no Wycheproof
  • Os vetores de teste próprios foram publicados como parte do projeto CCTV, para que também possam ser reutilizados por outras implementações
  • Os vetores CCTV incluem valores intermediários que permitem testar e depurar cada etapa intermediária e algoritmo parcial

Erros detectados por vetores de teste especiais

  • Vetores de teste negativos fornecem chaves de encapsulamento inválidas com coeficientes maiores que 3329
    • Como os vetores das equipes Kyber e NIST se concentram em entradas válidas, esse tipo de vetor era frequentemente solicitado
    • Todos os valores de 3329 até 2¹²-1 e todas as posições de coeficiente são testados individualmente
    • Ao compartilhar os demais coeficientes, dados de 1–3MiB são comprimidos para 12–28KiB
  • Vetores “unlucky” testam casos em que é necessário ler uma quantidade anormalmente grande do XOF
    • São chaves públicas que exigem ler 575 bytes ou mais do XOF SHAKE-128 em SampleNTT, algo que geralmente ocorre com probabilidade 2⁻³⁸
    • Os vetores de Sophie foram gerados com mais força bruta e exigem até 591 bytes
  • Vetores strcmp fazem falhar implementações que usam strcmp() em ML-KEM.Decaps
    • No desencapsulamento, ao comparar o ciphertext com a saída de K-PKE.Encrypt, se houver um byte zero, strcmp() pode encerrar a comparação antecipadamente
  • Vetores acumulados são derivados da implementação de referência pq-crystals
    • Em vez de armazenar 300 MB de saída de vetores aleatórios, eles são regenerados durante o teste com um RNG determinístico e o hash é comparado com o valor esperado
    • Também é possível criar hashes de 1 milhão de testes aleatórios, além dos 10 mil da implementação de referência
  • Vários testes adicionados após a conclusão não encontraram problemas em filippo.io/mlkem768, e há pelo menos um caso relatado em que um vetor negativo encontrou uma falha em uma implementação importante

Resultados de desempenho

  • Desempenho não é o objetivo principal deste pacote nem dos pacotes de criptografia do Go, mas ele precisa ser rápido o suficiente para ser útil
  • ML-KEM é rápido o bastante, e esta implementação simples atinge um nível competitivo com as implementações P-256 e X25519 do Go otimizadas em assembly
  • A comparação deve considerar o trabalho total que cada lado precisa realizar na configuração de chave
    • ECDH executa duas multiplicações escalares, incluindo uma com ponto-base fixo
    • KEM faz geração de chave e desencapsulamento de um lado, e encapsulamento do outro
    • ECDH é simétrico, mas a configuração de chave do ML-KEM é assimétrica
  • Nos benchmarks, “Alice” executa geração de chave e desencapsulamento, enquanto “Bob” executa encapsulamento
    • O desencapsulamento inclui uma criptografia completa para verificar se o ciphertext de entrada e o resultado correspondem
    • Alice leva mais tempo que Bob porque executa criptografia, descriptografia e geração de chave
  • Como resultado, Bob é tão rápido quanto X25519 ou P-256, e Alice fica abaixo de 2x disso
  • Em comparação com implementações rápidas de ML-KEM como BoringSSL e libcrux, este pacote leva aproximadamente o dobro do tempo

Números de benchmark e espaço para otimização

  • Os números medidos são os seguintes
    • No macOS arm64, ECDH/P256-8 leva 49,43µs, e ECDH/X25519-8 leva 77,46µs
    • No mesmo ambiente, RoundTrip/Alice-8 leva 109,4µs, e RoundTrip/Bob-8 leva 56,19µs
    • No Linux amd64, ECDH/P256-4 leva 78,88µs, e ECDH/X25519-4 leva 115,6µs
    • No mesmo ambiente, RoundTrip/Alice-4 leva 223,8µs, e RoundTrip/Bob-4 leva 114,7µs
  • A implementação segue padrões de Go de alto desempenho, como reduzir alocações no heap
  • x/crypto/sha3 foi retrabalhado para poder ser usado sem alocações no heap, mas isso teve efeito negativo no Apple M2, ainda não foi mesclado e não está incluído nos benchmarks acima
  • O espaço restante para otimização é claro
    • Como geração de chave e desencapsulamento amostram uma matriz a partir do mesmo valor, armazenar a matriz quando as duas operações são executadas em sequência do lado de Alice pode economizar cerca de 10% do tempo
    • Há possibilidade de reduzir cópias no caminho de leitura de sha3
    • Depois disso, será necessário otimizar a implementação de campo

Suporte a Kyber v3 com uma implementação de ML-KEM

  • O NIST fez algumas pequenas alterações na submissão Kyber Round 3, resumidas na seção 1.3 do rascunho FIPS
  • Há alguns protocolos experimentais baseados em Kyber v3 ou “draft00”, incluindo as principais implantações de troca de chaves PQ TLS
  • É possível oferecer suporte a Kyber v3 usando a implementação de ML-KEM, sem um pacote separado
  • Uma das mudanças adiciona validação para um caso excepcional de codificação não canônica de coeficientes na chave pública
    • Implementações corretas não geram essas chaves, portanto elas podem ser rejeitadas conforme o rascunho FIPS
    • Esse comportamento torna identificável uma implementação Kyber-on-ML-KEM, mas fora isso não é prejudicial
  • Outra mudança removeu uma etapa de hashing que era aplicada à entrada do CSPRNG
    • Como os bytes de entrada são aleatórios, nenhuma parte consegue distinguir a diferença
  • A maior mudança é o comportamento de aplicar hash ao ciphertext no segredo compartilhado
    • Essa diferença pode impedir interoperabilidade
    • Depois de criar o segredo compartilhado K com ML-KEM, aplicar SHAKE-256(K || SHA3-256(c))[:32] produz o segredo compartilhado Kyber
    • Não é necessário quebrar a abstração do ML-KEM
  • Tanto Kyber quanto ML-KEM aplicam hash ao segredo e ao ciphertext para implicit rejection no desencapsulamento
    • Aplicar a derivação de chave acima sobre ML-KEM faz o ciphertext ser hasheado duas vezes no implicit rejection
    • Como a saída do implicit rejection é imprevisível por design e não é alvo de interoperabilidade, isso não é um problema

Leituras relacionadas

1 comentários

 
GN⁺ 2024-02-02
Opiniões no Hacker News

  • Saudações da Kudelski Security. É muito oportuno, já que recentemente tivemos de descontinuar praticamente uma das únicas outras bibliotecas de criptografia resistente a quantum para Go existentes
    A história completa está em https://research.kudelskisecurity.com/2024/02/01/the-kybersl...

    • Kyber-512 não tinha sido enfraquecido de propósito por membros do lado da NSA no NIST?

  • Fico curioso para saber em que nível a computação quântica realmente está para que algo assim se torne necessário
    Será que, como na IA, em vez de algo real ter surgido, a definição só mudou para permitir lançar novos produtos sob um nome já existente?

    • A criptografia lida de um jeito peculiar com a ameaça dos computadores quânticos. Isso porque alguns dos dados e conexões criptografados hoje não podem se tornar decifráveis daqui a 30 ou 50 anos
      Então a pergunta não é “computadores quânticos estão chegando em breve?”, mas “é plausível que computadores quânticos surjam no próximo meio século?”. Não há um consenso preciso, mas a resposta não é “não”, e por isso esse movimento está acontecendo agora
      É por isso que se vê mais progresso em troca de chaves PQC do que em assinaturas. A verificação de assinaturas de hoje não é afetada por computadores quânticos daqui a 50 anos, mas a criptografia é
    • Não se trata de bloquear os computadores quânticos atuais
      O risco é que um atacante possa armazenar o texto cifrado de hoje e decifrá-lo no futuro. Quanto mais cedo migrarmos para criptografia segura contra quantum, menos “texto cifrado acumulado” vulnerável a ataques futuros deixaremos para trás
    • Se a resposta for “a NSA já roda criptoanálise quântica em produção e devemos considerar que ECDH está completamente quebrado”, quem souber disso e disser vai se meter em uma encrenca enorme
      Na prática, isso parece improvável, mas essa pergunta é, em certa medida, difícil de responder. Por enquanto não é uma ameaça conhecida, mas o quão paranoico se deve ser em relação a esse potencial é subjetivo
    • Nos últimos dois anos, mais ou menos, o NIST definiu alguns algoritmos de criptografia pós-quântica, e desde então as implementações vêm aumentando. A computação quântica ainda está distante, mas a atitude parece ser “por que não começar agora?”
      Não tenho certeza, mas imagino que criptografia de curvas elípticas também já tivesse muitas implementações bem antes de se tornar popular. Se alguém que viveu aquela época souber que estou errado, por favor corrija
    • Para que um computador quântico quebre RSA-2048, a qualidade dos qubits físicos atuais teria de aumentar em cerca de 10 vezes, e a quantidade em 10 mil vezes. São números bem aproximados
      O próximo marco importante a observar é um qubit lógico com fidelidade 1000 vezes melhor do que os qubits físicos que o compõem. Quando isso aparecer, será um sinal de que a qualidade dos qubits físicos é suficiente e que agora só resta começar a escalar a quantidade

  • Para discussões relacionadas, a cartilha de John Arundel sobre implementação de sistemas criptográficos com a versão mais recente do Go pode ser útil. A última seção menciona brevemente criptografia pós-quântica e, quando o NIST PQ for padronizado, talvez John atualize o livro incluindo esta biblioteca
    Explore Go: Cryptography (edição Go 1.22):
    https://bitfieldconsulting.com/books/crypto

  • Corrijam-me se eu estiver errado, mas, se foi escrito em Go puro, isso não o torna vulnerável a ataques de canal lateral por timing/energia?

    • É difícil dizer que Go seja mais vulnerável do que C; talvez seja até menos. A diferença é que Go tem um compilador principal e, em geral, não otimiza de forma excessiva, enquanto em C é preciso usar artifícios cada vez mais complexos para impedir que o compilador perceba a intenção e a transforme em uma ramificação de tempo variável mais eficiente
      Esta implementação foi escrita para evitar caminhos de código que dependam de valores secretos. Canais laterais por energia, que exigem acesso físico, estão fora do modelo de ameaça do Go
    • Está escrito que “todas as operações centrais são executadas em tempo constante”
      Eu deveria ter seguido os links até a documentação do projeto; parece que eles estão levando isso em consideração
    • Existe alguma linguagem imune a ataques de canal lateral por energia? A ideia em si parece não fazer sentido
      Quanto a ataques de timing, também não sei por que Go seria mais vulnerável a canais laterais de timing do que outras linguagens

  • Alguém conhece implementações para outras linguagens, como Java e C#?

  • É legal que também possa funcionar com draft00/kyber v3
    Quão difícil seria oferecer suporte ao modo Kyber 90’s rápido, sem SHA-3? Provavelmente, nesse caso, seria preciso quebrar a abstração

    • Para trocar o hash, seria necessário fazer um fork. Esta implementação gasta apenas cerca de 20% do tempo de CPU em SHA-3, então o ganho não seria grande
      Se a implementação do campo for otimizada, essa proporção aumentaria, mas provavelmente não a ponto de valer a pena usar um modo não padronizado e menos testado

  • Nada a ver, mas Filo, a tabela de chamadas de sistema de 32 bits ainda está “coming soon”, né :')

    • Haha, admito. É que toda vez que penso em mexer naquela página, o escopo continua aumentando, tipo querer gerá-la automaticamente a partir do código-fonte do kernel via CI :)

  • Não tenho capacidade para avaliar a qualidade desse algoritmo ou dessa implementação, mas gosto muito do uso de Unicode nos nomes de variáveis
    ρ, σ := G[:32], G[32:]
    De algum jeito, é bem melhor do que ver "rho", "sigma"

    • Difícil concordar. Fica bonito, mas eu não gostaria muito de ver isso em código real
      Para começar, não sei como digitaria isso no teclado. E a maioria das pessoas provavelmente nem saberia o nome desses símbolos. Claro, quem estiver olhando esse código tem mais chance de saber, mas não acho que seja um código amigável
      Clareza é o ponto principal, e "rho" ou "sigma" são bem claros. Além disso, se houver também uma constante "n" e uma constante "η", é perfeito para causar confusão
    • Não gosto nem um pouco. Caracteres que não existem no meu teclado acrescentam uma etapa de entrada e geram atrito demais. Também acho que eu acabaria lendo ρ como p e encontrando algum erro de compilação estranho
      Que tal colocar acentos ou cedilha nas letras? Só aumenta a complexidade. É melhor ficar no menor denominador comum
    • Go permite subscritos Unicode em nomes de variáveis?
      Entre as linguagens que verifiquei, Perl, Python e JavaScript no Chrome e no Firefox não permitiram, enquanto PHP permitiu

  • Quem fez isso é a mesma pessoa que fez https://github.com/FiloSottile/age
    Gosto muito dessa ferramenta

    • É uma pena que ela não tenha negação plausível embutida. Quero dizer que deveria ser possível criptografar pelo menos dois arquivos e descriptografar um deles dependendo da chave fornecida
      Isso parece ser uma fraqueza de segurança da maioria das ferramentas desse tipo. Se só existe uma chave possível, alguém com um martelo pode fazer você entregar essa chave. Mas, se não dá para saber quantas chaves existem, você pode entregar algumas e torcer para que o agressor vá embora enquanto o arquivo realmente protegido continua escondido
    • Eu queria gostar dessa ferramenta, mas faltam manuais ou tutoriais explicando o uso típico. Não estou falando do uso na linha de comando; quero saber como as chaves devem ser gerenciadas e distribuídas, e com o que é preciso tomar cuidado
      Toda a camada social por cima da tecnologia não está clara para mim. Seria bom ter uma história de exemplo com Alice e Bob
    • O Age é ok, mas parece parado. A última versão é de 2022, e ele não usa uma função de derivação de chave baseada em senha mais moderna, como argon
      Se você está procurando algo projetado para armazenar/compartilhar segredos, vale dar uma olhada no rot: https://github.com/candiddev/rot

  • Especificação: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf também está linkada no artigo