解除Fiat-Shamir的安全隐患 - The Trail of Bits博客

Opal Wright
2024年6月24日
密码学, 工具发布

Fiat-Shamir变换是零知识证明（ZKPs）和多方计算（MPC）中的重要构建块。它允许基于交互式协议的零知识证明变为非交互式。本质上，它将对话转换为文档。这种能力是SNARKs和STARKs等强大技术的核心。非常有用！

但Fiat-Shamir变换，像几乎所有其他密码学工具一样，比看起来更微妙，出错会导致灾难性后果。由于这类错误频繁发生，Trail of Bits发布了一个名为Decree的新工具，帮助开发者指定他们的Fiat-Shamir转录本，并更轻松地包含上下文信息到转录本输入中。

Fiat-Shamir概述

许多零知识证明有一个常见的三步协议结构：

Peggy向Victor发送一组对某些值的承诺。
Victor回应一个随机挑战值。
Peggy回应一组值，这些值整合了步骤（1）中的承诺值和Victor的随机挑战值。

显然，步骤（1）和（3）的细节因协议而异，但步骤（2）相当一致。这也是Victor唯一需要贡献的部分。

如果我们能消除Victor选择随机挑战值并传输给Peggy的整个部分，事情会更高效。我们可以让Peggy选择，但这给了她太多权力：在大多数协议中，如果Peggy能选择挑战，她可以自定义挑战以适应她的承诺来伪造证明。更糟的是，即使Peggy不能选择挑战，但能预测Victor将选择的挑战，她仍然可以自定义她的承诺以适应挑战来伪造证明。

Fiat-Shamir变换允许Peggy生成挑战，但具有以下特性：

Peggy不能有意义地控制生成挑战的结果。
一旦Peggy生成了挑战，她不能修改她的承诺值。
一旦Victor有了承诺信息，他可以重现Peggy生成的相同挑战值。

Fiat-Shamir变换的基本机制是将证明的所有公共部分（称为证明的转录本）输入哈希函数，并使用哈希函数的输出来生成挑战。我们另一篇博客文章更详细地描述了这一点。

拥有完整的转录本对于安全生成挑战至关重要。这意味着实现者需要明确指定和执行转录本要求。

失败模式

我们在实践中看到几种Fiat-Shamir失败模式。

缺乏实现规范

我们经常观察到客户的转录本是临时构建的，仅由实现指定。添加到转录本的值列表、它们的包含顺序以及数据格式只能通过查看代码来确定。

对证明系统如此重要的组件如此松散是不良实践，但我们在代码审查中经常看到。

不正确的形式规范

描述新证明技术或MPC系统的论文必然引用Fiat-Shamir变换，但作者如何讨论该主题会对实现的安全性产生重大影响。

最优情况是作者提供安全挑战生成的详细规范。一个简单、明确的转录本值列表尽可能容易，并且对所有经验水平的实现者都可访问。假设作者没有在规范中犯错，实现者有很大机会避免弱Fiat-Shamir攻击。

当作者含糊其辞，只说“该协议可以使用Fiat-Shamir变换变为交互式”时，细节就留给实现者。对于精通文献并理解Fiat-Shamir变换微妙之处的聪明密码学家来说，这是劳动密集型的，但可行。然而，对于经验不足的开发者，这是灾难的配方。

最糟糕的情况是作者含糊其辞，但试图给出未经证明的例子。我们另一篇博客文章包括一个好例子：Bulletproofs论文。作者的原始论文引用了Fiat-Shamir变换，并建议了挑战生成可能的样子。许多密码学家使用该例子作为Bulletproofs实现的基础，结果证明是错误的。

缺乏执行

即使存在转录本规范，也很难验证规范是否被遵循。

今天使用的证明系统和协议极其复杂。对于某些zkSNARKs，Fiat-Shamir转录本可以包括在子程序的子程序的子程序中生成的值。协议可能要求Peggy生成满足特定属性的值，然后才能用于证明并因此集成到转录本中。这导致复杂的调用树和软件中的许多条件块。在“if”块中处理的转录本值很容易在相应的“else”块中被跳过。

此外，这些协议的复杂性可能导致复杂的架构和长函数。随着函数变长，很难验证所有期望值是否被包含在转录本中。转录本值通常是非常复杂计算的结果，并且通常在计算后不久添加到转录本中。这意味着与转录本相关的调用可能相隔几十行，或埋在完全不同模块的子程序中。错过的转录本值很容易在噪音中丢失。

不是凭法令，而是凭Decree

Trail of Bits发布一个Rust库来帮助开发者避免这些陷阱。该库名为Decree，旨在帮助开发者创建和执行转录本规范。它还包括一个新特质，旨在使转录本值更容易包含上下文信息，如域参数，这些有时被开发者和作者都错过。

Decree的第一个大特性是，在初始化Fiat-Shamir转录本时，它需要预先指定所需的转录本值以及期望的挑战列表。尝试在所有期望值提供之前生成挑战被标记为错误。尝试添加规范中未期望的值到转录本被标记为错误。尝试添加已定义的值到转录本被标记为错误。尝试乱序请求挑战……你懂的。

这种规范和执行机制由Decree结构体提供，它建立在 venerable Merlin 库之上。使用Merlin意味着底层哈希和挑战生成机制是可靠的。Decree旨在管理对底层Merlin转录本的访问，而不是替换其密码学内部。

例如，我们可以稍微修改我们实现Girault识别协议的集成测试。在我们修改的例子中，我们将首先进行以下调用：

1

let mut transcript = Decree::new("girault", &["g", "N", "h", "u"], &["e", "f"]);

这初始化Decree结构体，使其期望四个名为g、N、h和u的输入，以及两个名为e和f的输出。（对于Girault证明，我们只需要e；f包含纯粹为了说明目的。）

我们可以同时添加所有这些值到转录本，或者按计算顺序添加：

1
2
3
4


transcript.add_serial("h", &h)?;
transcript.add_serial("u", &u)?;
transcript.add_serial("g", &g)?;
transcript.add_serial("N", &n)?;

注意，我们添加值到转录本的顺序与声明中给出的顺序不匹配。Decree不会更新底层Merlin转录本，直到所有值都被指定，此时输入按字母顺序馈送到转录本中。改变Decree输入的顺序不会影响生成的挑战。

然后我们可以生成我们的挑战：

1
2
3
4


let mut challenge_e: [u8; 128] = [0u8; 128];
let mut challenge_f: [u8; 32] = [0u8; 32];
transcript.get_challenge("e", &mut challenge_e)?;
transcript.get_challenge("f", &mut challenge_f)?;

当我们生成挑战时，顺序确实重要：我们需要首先生成e，因为e在声明中列在f之前。

Decree结构体也不限于单步协议。一旦给定规范中的所有挑战都已生成，Decree转录本可以扩展以处理进一步的输入值和挑战，携带所有先前的状态信息。对于多阶段证明，扩展调用有助于划分协议阶段的开始和结束。

包含上下文信息的能力由Inscribe特质提供，该特质可派生用于具有命名成员的结构体。当派生Inscribe特质时，开发者可以指定一个提供相关上下文信息的函数，如椭圆曲线或有限域参数。该信息与结构体成员的确定性序列化一起包含。如果结构体成员支持Inscribe特质，那么其上下文信息也将被包含。

我们可以使用Inscribe特质简化Schnorr证明的处理：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/// Schnorr proof as a struct
#[derive(Inscribe)]
struct SchnorrProof {
    #[inscribe(serialize)]
    base: BigInt,
    #[inscribe(serialize)]
    target: BigInt,
    #[inscribe(serialize)]
    modulus: BigInt,
    #[inscribe(serialize)]
    base_to_randomized: BigInt,
    #[inscribe(skip)]
    z: BigInt,
}

在填充SchnorrProof结构体的base、target、modulus和base_to_randomized值后，我们可以简单地将其添加到我们的转录本，生成我们的挑战，并更新z值：

1
2
3
4
5
6
7


let mut transcript = Decree::new("schnorr proof", &["proof_data"], &["z_bytes"]).unwrap();
transcript.add("proof_data", &proof)?;

let mut challenge_bytes: [u8; 32] = [0u8; 32];
transcript.get_challenge("z_bytes", &mut challenge_bytes)?;
let chall = BigInt::from_bytes_le(Sign::Plus, &challenge_bytes);
let proof.z = (&chall * &log) + &randomizer_exp;

通过在z成员上设置#[inscribe(skip)]标志，我们设置结构体自动添加所有其他值到转录本；添加z到证明使其准备好发送给验证者。

简而言之，Decree结构体帮助程序员定义、执行和理解他们的Fiat-Shamir转录本，而Inscribe特质使开发者更容易确保重要上下文数据（如椭圆曲线标识符）默认包含。虽然仍然可能出错Fiat-Shamir规范，但至少更容易发现、测试和修复。

所以试试看，让我们知道你的想法。

1许多更复杂的证明系统有多个这种结构的实例。没关系；我们的想法扩展到那些系统。

如果你喜欢这篇文章，分享它：
Twitter LinkedIn GitHub Mastodon Hacker News

页面内容
Fiat-Shamir概述
失败模式
不是凭法令，而是凭Decree
最近帖子
我们构建了MCP一直需要的安全层
利用废弃硬件中的零日漏洞
Inside EthCC[8]：成为智能合约审计员
使用Vendetect大规模检测代码复制
构建安全消息传递很难：对Bitchat安全辩论的 nuanced 看法
© 2025 Trail of Bits.
使用Hugo和Mainroad主题生成。

解除Fiat-Shamir的安全隐患：Trail of Bits发布Decree工具

本文详细分析了Fiat-Shamir变换在零知识证明中的关键作用及常见实现错误，并介绍了Trail of Bits新开发的Rust库Decree，该工具帮助开发者规范和安全地处理证明转录本，避免密码学漏洞。