Aritmética de curvas NIST em Pascal puro para assinatura PDF

O HotPDF executa acordo de chaves em curvas elípticas e verificação de assinaturas para PDF em Object Pascal puro, sem ligação a OpenSSL e sem fornecedor criptográfico de plataforma no caminho. Isso cobre cinco curvas: P-256, P-384 e P-521 para as famílias de primos NIST, mais X25519 e X448 para acordo de chaves em curvas de Montgomery. A razão para escrever esse código em vez de o ligar é a implantação, não a pureza. Uma aplicação Delphi ou Free Pascal que distribui um executável e nenhuma DLL criptográfica não tem desvio de versões para gerir, nem fornecedor por plataforma para detetar, nem nada que mude de comportamento quando um cliente atualiza as bibliotecas do sistema

O custo é que agora é dono da aritmética. A multiplicação modular de inteiros grandes é código impiedoso: ou produz resultados idênticos byte a byte contra vetores de teste publicados, ou produz lixo de aparência plausível, e a distância entre esses dois estados pode ser uma única comparação. Esta é a história dessa comparação, porque a forma do bug generaliza-se a qualquer port Pascal de aritmética de corpo

Porque é que uma biblioteca PDF precisa de aritmética de curvas?

Duas funcionalidades puxam por ela. A primeira é a encriptação de documentos por chave pública: o tratador de listas de destinatários da ISO 32000 embrulha uma chave por documento para certificados nomeados, e quando um destinatário tem uma chave EC o embrulho corre através de acordo de chaves em vez de transporte de chaves RSA. Sem ECDH não há forma de abrir tal documento. A segunda é a validação de assinaturas. Verificar uma assinatura ECDSA sobre os bytes do /ByteRange precisa de uma multiplicação de pontos na curva do signatário, e o P-384 é comum em perfis governamentais e de assinatura qualificada onde o P-256 é considerado o piso em vez do alvo. O HotPDF expõe os resultados desse trabalho através do caminho de verificação ECDSA e CMS e através do modelo plugável de fornecedores de assinatura

CIOS, e a única subtração no fim

A multiplicação de Montgomery evita a divisão trabalhando num domínio transformado onde a redução é um deslocamento. A variante que o HotPDF usa é Coarsely Integrated Operand Scanning, que entrelaça a multiplicação e a redução limb a limb de modo a que o intermédio nunca cresça para além da largura do módulo mais um limb. O corpo do ciclo é direto e fácil de testar. A cauda não é: depois das passagens entrelaçadas o acumulador pode estar em qualquer ponto do intervalo até duas vezes o módulo, pelo que o algoritmo termina com uma subtração condicional que remove uma cópia do primo se e só se o acumulador for maior ou igual a ele

Comparar dois números de múltiplos limbs significa percorrer do limb mais significativo para baixo enquanto transporta um empréstimo. A forma óbvia de o escrever é comparar o limb do acumulador com o limb do módulo mais o empréstimo recebido. Essa expressão está errada, e está errada de um modo que a maioria das curvas esconde

// Errado: P[I] + Borrow pode dar a volta quando P[I] é $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Correto: comparar sem nunca somar a um limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Como se parece realmente um wrap-around de empréstimo?

Parece uma curva que funciona em todo o lado exceto em produção. Os primos de P-384 e P-521 contêm limbs que são inteiramente uns, pelo que P[I] é igual a $FFFFFFFFFFFFFFFF. Some a isso o empréstimo recebido de um e um inteiro sem sinal de 64 bits dá a volta a zero. A comparação pergunta então se o limb do acumulador é menor que zero, decide que não, e conclui que não é preciso empréstimo. Um limb do resultado está desviado por um

O P-256 escapa porque nenhum dos seus limbs é todo de uns, pelo que a soma nunca transborda e a expressão com bug acontece de concordar com a correta. Esse é o pior desfecho possível para uma suíte de testes: a curva mais testada passa, as menos testadas falham intermitentemente dependendo dos valores dos operandos, e a falha superficia como um resultado de verificação de "assinatura inválida" em documentos perfeitamente válidos. O HotPDF transportava um bloqueio explícito no P-384 por exatamente esta razão, devolvendo um estado de indisponível em vez de uma resposta errada, até a aritmética ser provada contra vetores de referência

Como o bug foi realmente localizado

Não lendo o código. A sequência produtiva foi mecânica, e é reutilizável. Primeiro, eliminar as constantes: cada limb de p, R e R^2 foi regenerado de forma independente e comparado limb a limb, o que exclui a fonte única mais comum de bugs de curvas. Segundo, instrumentar a aritmética em vez da API: um procedimento temporário de dump imprimia os valores intermédios da multiplicação de Montgomery de R^2, de x^3, e de y^2 para um ponto conhecido, para que pudessem ser verificados contra verdade calculada de forma independente

Essa comparação apontou direto ao culpado. A cadeia do x estava correta de ponta a ponta, enquanto y^2 diferia em exatamente um limb por exatamente um. Uma diferença de um único limb por um não é um bug de multiplicação, um bug de propagação de carry, nem um bug de constante; é um bug de cadeia de empréstimos, e a única cadeia de empréstimos na rotina é a subtração condicional final. Um detalhe quase descarrilou isto: a constante de referência usada para o dump estava ela própria escrita na ordem de bytes errada na primeira tentativa, o que produziu uma discrepância no valor y e sugeriu brevemente um segundo defeito inexistente. Verifique a endianidade da sua verdade de referência antes de a confiar para acusar o seu código

As armadilhas vizinhas na mesma rotina

Mais três modos de falha vivem a poucas linhas dessa comparação, e os três estiveram ativos em algum momento durante o desenvolvimento

// 1. O acumulador tem um limb acima da largura do módulo. Comparar
//    apenas os L limbs baixos perde o caso em que T é exatamente
//    igual a p mais 2^(64*L), o que acontece para uma parcela
//    significativa das entradas aleatórias porque 2p excede
//    2^256 no P-256 e 2^384 no P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Uma subtração genérica de múltiplos limbs tem o mesmo risco de
//    volta: quando Y[I] é $FFFFFFFFFFFFFFFF, Y[I] + Borrow dá a volta
//    a zero e o empréstimo tem de sobreviver para o limb seguinte em
//    vez de ser limpo
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

A terceira não é código, é proveniência. O primo de P-521 foi inicialmente transcrito com 130 dígitos hexadecimais em vez de 131, um F a menos, e as constantes de Montgomery foram então calculadas a partir desse primo errado, pelo que as constantes eram autoconsistentes e conjuntamente erradas. Os parâmetros de curvas têm de ser derivados, nunca digitados: calcule R como (1 shl (64 * L)) mod p a partir do primo que está realmente a usar, depois confirme cruzadamente R * R mod p contra o valor que a sua constante R^2 afirma. Um par de constantes que concordam entre si não prova nada sobre nenhuma delas

Estratégia de verificação que escala para além de uma curva

A técnica que tornou X25519 e X448 tratáveis foi escrever uma implementação espelho numa linguagem com inteiros sem limites e transcrever para ela o fluxo de controlo Pascal linha a linha. Quando o espelho produz a resposta certa e o Pascal não, o defeito é um lapso de transcrição e sondar o mesmo valor intermédio nas duas implementações encontra-o em segundos. Os três erros clássicos da escada do RFC 7748 foram apanhados desta forma: uma troca de tempo constante cuja segunda linha reutilizava o valor já trocado, uma inversão final que devolvia z à potência menos um em vez de o multiplicar em X, e uma multiplicação por constante pequena que montava produtos de meia palavra com um ou bit a bit e perdia o carry

Para material de teste, tome os vetores como bytes em vez de como texto. Extrair uma chave privada com um padrão de texto é como uma implementação correta é acusada de um erro de um byte que vive inteiramente no passo de extração. Corte o hex da codificação DER em desvios conhecidos e compare arrays de bytes

Com a cadeia de empréstimos corrigida, todas as cinco curvas coincidem byte a byte com os vetores de referência publicados, e o HotPDF já não bloqueia nenhuma delas. Se está a integrar assinatura baseada em certificados ou encriptação de lista de destinatários, a conclusão prática é que a escolha de curva é agora uma decisão de política em vez de uma questão de capacidade; os perfis e as armadilhas de ordem de bytes do lado da assinatura estão cobertos na explicação de assinatura PAdES. Os detalhes do componente e a matriz de algoritmos suportados estão na página de produto do HotPDF Delphi PDF component