por: Johan

fundo

A vulnerabilidade Frozen Heart "Bingxin" foi nomeada pela equipe Trail of Bits, onde Frozen significa provas de conhecimento FoRging Of ZERO e Heart se refere à transformação Fiat-Shamir, que é o núcleo de muitos sistemas de prova. Esta vulnerabilidade refere-se ao problema de segurança que ocorre quando uma transformação "Fiat-Shamir fraca" é aplicada, que faz hash apenas de parte da mensagem do provador sem fazer hash das informações públicas (como parâmetros, entrada pública, etc.).

A seguir faremos uma análise abrangente desta vulnerabilidade. Vamos primeiro falar sobre o que é a transformação Fiat-Shamir.

Transformada Fiat-Shamir

A transformação Fiat-Shamir, também chamada de Heurística Fiat-Shamir ou Paradigma Fiat-Shamir, é uma transformação proposta por Fiat e Shamir em 1986 para transformar protocolos interativos de prova de conhecimento zero em protocolos não interativos de prova de conhecimento zero. Ele consegue essa transformação substituindo desafios aleatórios no protocolo pela saída de uma função hash. Dessa forma, o provador pode gerar uma prova e enviá-la ao verificador sem desafio e resposta interativos.

A prova de Schnorr é um protocolo interativo de prova de conhecimento zero que permite ao provador provar ao verificador que uma determinada afirmação é verdadeira sem revelar os detalhes da afirmação, e o verificador pode conduzir uma verificação interativa. Normalmente é usado quando o provador conhece um valor secreto, mas não revela o valor secreto.

As provas interativas de Schnorr podem ser transformadas em não interativas usando a transformação Fiat-Shamir.

Schnorr pode ser implementado em campos finitos ou curvas elípticas (EC). As especificações técnicas são basicamente as mesmas, apenas o grupo cíclico subjacente é diferente. Abaixo descrevemos principalmente esses dois processos na forma de campos finitos [1]:

* Descrição do símbolo:

  • Alice: A identidade presumida do provador no protocolo

  • Bob: A identidade assumida do validador no protocolo

  • a | b: a divide b

  • uma || b: conexão entre a e b

  • [a, b]: intervalo inteiro, incluindo a e b

  • t: O número de bits no desafio selecionado por Bob

  • H: Função hash criptográfica segura

  • p: um grande número primo

  • q: um grande fator primo de p-1, ou seja, q |

  • Zp*: grupo multiplicativo de inteiros módulo p

  • Gq: um subgrupo de Zp* com ordem prima q

  • g: gerador de Gq

  • g ^ d: g elevado à potência d

  • um mod b: um módulo b

  • Fp: um corpo finito de p elementos, onde p é um número primo

Implementação baseada em campos finitos

1. Interativo

Primeiro, Alice calcula A = g^a mod p, onde a chave privada a assume o valor [0, q-1], e então divulga a chave pública A;

Então, Alice prova a Bob que conhece a chave privada a correspondente a A sem revelar a:

Se a verificação for verdadeira, então pode ser provado que Alice conhece a.

A razão pela qual Bob precisa gerar um c aleatório aqui é porque se o invasor souber esse valor antes de revelar A, ele poderá forjar a prova sem conhecer o a real. O atacante forja (A, V, r) da seguinte forma:

1) Gere um valor aleatório r

2) O método de cálculo de V permanece inalterado, seja

Após o Verifier receber esses três parâmetros e substituí-los na fórmula de verificação, ele poderá passar na verificação. Mas prestemos atenção ao processo de geração de alguns parâmetros, que nada têm a ver com o valor secreto a a ser provado.
2. Não interativo

A transformação não interativa também é muito fácil. Com base na interativa, altere o processo de geração aleatória de c de Bob para a forma de parâmetros Hash:

Implementação baseada em curvas elípticas

Primeiro, Alice calcula A = G x [a], onde a chave privada a assume o valor [0, n-1], e então divulga a chave pública A;

Então, Alice prova a Bob que conhece a chave privada a correspondente a A sem revelar a:

Se a verificação for verdadeira, então pode ser provado que Alice conhece a.

O método de implementação não interativo é igual ao método de implementação mencionado acima, baseado em campos finitos, e não será descrito em detalhes.

Transformada Fiat-Shamir Fraca

No processo de implementação não interativo acima, números aleatórios:

É uma forma correta e segura de gerar, mas infelizmente, em alguns artigos anteriores, esse processo não foi estritamente descrito, mas simplesmente descrito como:

Há um problema de segurança, chamamos isso de transformação Fiat-Shamir fraca, que pode ser usada para falsificar a prova e enganar o verificador pré-computando A.

Reconstrua os parâmetros (A, r) usando:

1. Gere um valor aleatório

2. Calcule a=(v-r)/c, o método de cálculo permanece inalterado

3. Cálculo

Podemos ver que A se torna um parâmetro que não tem nada a ver com a e é substituído na equação de verificação:

pode ser igual a V.

Isso significa que um invasor pode passar na verificação do protocolo sem saber o valor do segredo.

Existem também alguns artigos [3] que descrevem este processo da seguinte forma:

O conteúdo expresso é o mesmo.

Brecha Bingxin

A equipe Trail of Bits publicou um artigo [2] apontando que a implementação do Fiat-Sharmir em sistemas ZKP como Bulletproofs e Plonk possui vulnerabilidades, permitindo que usuários mal-intencionados forjem provas para declarações aleatórias.

Tomando o Plonk como exemplo, o algoritmo Fiat-Shamir é usado para gerar números aleatórios nas Rodadas 2, 3, 4 e 5 geradas pela prova.

No artigo [3], muitas implementações de código aberto de sistemas modernos de prova de conhecimento zero foram investigadas e descobriram que 36 usavam transformações Fiat-Shamir fracas, incluindo Bulletproofs, Plonk, Spartan e VDF de Wesolowski, etc. Um invasor pode gerar uma prova que passe na verificação sem conhecer o segredo da prova válida.

Exemplo de vulnerabilidade

1. gnark

Aqui fs é uma instância de cálculo Fiat-Shamir. Quando a prova Round2 calcula o parâmetro z(X), a informação da prova pode ser forjada porque a entrada pública não está vinculada ao desafio.

2. sarcástico

Também porque publicSignals não está incluído, as informações de certificação podem ser falsificadas.

Resumir

A partir do conteúdo divulgado, podemos ver a versatilidade e extensão desta vulnerabilidade. Ela causará sérios danos às provas de conhecimento zero. Em aplicações práticas, precisamos prestar atenção para revisar a correção da implementação do Fiat-Shamir e adicionar dados de testemunhas públicas. a ele. Durante a geração de números aleatórios, o invasor pode evitar falsificar provas.

Por fim, gostaríamos de agradecer à Safeheron, fornecedora líder de serviços de autocustódia de ativos digitais, por fornecer consultoria técnica profissional.

Documentos de referência:

[1]. https://datatracker.ietf.org/doc/html/rfc8235

[2]. https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/

[3]. https://eprint.iacr.org/2023/691.pdf