探讨 Poseidon 延展性攻击，可影响零知识证明应用的安全性

背景

此前我们在一文中探讨过哈希函数的长度扩展攻击，指出了 md5/sha1/sha2 算法存在的延展性问题和可能带来的安全风险。

近日，有开发者在 X 上披露了存在于 Iden3 密码学库的一个哈希延展性问题。

(https://x.com/vdWijden/status/1877046148386451732)

慢雾安全团队对此问题展开了深入研究。

什么是 Poseidon

Poseidon 是一种专为零知识证明系统优化设计的密码学哈希函数。它具有以下主要特点：

在有限域上运行，特别适合于基于算术电路的零知识证明系统
计算效率高，gas 消耗低
主要用于 Merkle 树构建和数据承诺方案
被广泛应用于 zkRollup、身份验证等区块链应用场景

例如在目前流行的 Snark 编程语言 Circom 中，就广泛使用了 Poseidon 算法。

Poseidon 的延展性

Poseidon 哈希本身不具有延展性或长度扩展攻击(Length Extension Attack) 问题，这得益于 Poseidon 海绵构造的填充方式(Sponge Padding)[1]:

先在消息字符串后添加单个元素 1
然后根据需要添加足够多的 0 元素
直到消息长度是 (t-c) 的整数倍
其中 t 是状态宽度，c 是容量

与具有延展性的哈希对比（如 SHA256）：

SHA256(具有延展性):message -> [原始消息 | 填充长度] -> 迭代压缩函数 -> hash值攻击者可以继续使用最终状态继续添加数据Poseidon(不具有延展性):message -> [固定t-1长度] -> 置换函数 -> hash值无法从hash值恢复内部状态

但 Iden3 实现的 Poseidon 库与标准算法却有一些区别，主要体现在它的数据填充方案不同，这也导致了它出现延展性问题。

我们来分析一下它的代码实现[2]：

// HashBytes returns a sponge hash of a msg byte slice split into blocks of 31 bytesfunc HashBytes(msg []byte) (*big.Int, error) {  // not used inputs default to zero  inputs := make([]*big.Int, spongeInputs)  for j := 0; j < spongeInputs; j++ {    inputs[j] = new(big.Int)  }  dirty := false  var hash *big.Int  var err error  k := 0  for i := 0; i < len(msg)/spongeChunkSize; i++ {    dirty = true    inputs[k].SetBytes(msg[spongeChunkSize*i : spongeChunkSize*(i+1)])    if k == spongeInputs-1 {      hash, err = Hash(inputs)      dirty = false      if err != nil {        return nil, err      }      inputs = make([]*big.Int, spongeInputs)      inputs[0] = hash      for j := 1; j < spongeInputs; j++ {        inputs[j] = new(big.Int)      }      k = 1    } else {      k++    }  }  if len(msg)%spongeChunkSize != 0 {    // the last chunk of the message is less than 31 bytes    // zero padding it, so that 0xdeadbeaf becomes    // 0xdeadbeaf000000000000000000000000000000000000000000000000000000    var buf [spongeChunkSize]byte    copy(buf[:], msg[(len(msg)/spongeChunkSize)*spongeChunkSize:])    inputs[k] = new(big.Int).SetBytes(buf[:])    dirty = true  }  if dirty {    // we haven't hashed something in the main sponge loop and need to do hash here    hash, err = Hash(inputs)    if err != nil {      return nil, err    }  }  return hash, nil}

HashBytes 函数用于对给定的字节切片 msg 进行海绵哈希(sponge hash)，并将其分割成 31 字节的块。首先，函数初始化了一个 inputs 切片，长度为 spongeInputs，并将每个元素设置为新的大整数 big.Int。这些未使用的输入默认设置为零。

假设有一个消息需要填充：

标准 Poseidon: [消息] + [1] + [0,0,0...]Iden3 实现: [消息] + [0,0,0...]

这种填充方案的区别看似微小，但在密码学中是很关键的。标准 Poseidon 通过添加 1 再补 0 的方式可以确保不同长度的输入消息会产生不同的哈希值，而纯补 0 的方式却会导致安全隐患。

漏洞危害

Iden3 Poseidon 的延展性有哪些具体的危害，让我们写一个示例演示一下：

msg1 := []byte("9")hash1, _ := poseidon.HashBytes(msg1)fmt.Printf("Hash of 1: %sn", hash1.String())fmt.Println("Value: ", new(big.Int).SetBytes(msg1))msg2 := []byte("9x00x00x00x00")hash2, _ := poseidon.HashBytes(msg2)fmt.Printf("Hash of 9\x00\x00\x00\x00: %sn", hash2.String())fmt.Println("Value: ", new(big.Int).SetBytes(msg2))

运行输出：

Hash of 9: 11642804437010365980265264676069673149904017141487814048230421306886008365708Value:  57Hash of 9x00x00x00x00: 11642804437010365980265264676069673149904017141487814048230421306886008365708Value:  244813135872

基于代码示例的结果，我们可以看到这个漏洞可能带来以下危害：

哈希碰撞：利用延展性漏洞构造的不同输入值（57 和 244813135872）产生了相同的哈希值，这可能导致在零知识证明系统中出现验证绕过
数据完整性问题：由于 Iden3 的实现采用了纯补 0 的填充方案，攻击者可能通过构造特定的输入来生成碰撞，从而破坏系统的安全性验证

这在实际应用中可能会影响：

zkRollup、身份验证等依赖 Poseidon 哈希的区块链应用
使用 Circom 编写的智能合约

总结

本文探讨了 Poseidon 哈希函数在 Iden3 密码学库中存在的延展性问题。Poseidon 是一种为零知识证明系统优化的哈希函数，虽然标准 Poseidon 不具有延展性，但 Iden3 的实现由于采用了纯补 0 的填充方案而非标准的填充方式，导致可能出现哈希碰撞问题，这对依赖 Poseidon 哈希的 zkRollup、身份验证等区块链应用以及使用 Circom 编写的智能合约都可能造成安全隐患。

参考资料

[1] https://eprint.iacr.org/2019/458.pdf

[2] https://github.com/iden3/go-iden3-crypto/blob/master/poseidon/poseidon.go

作者 | Johan

编辑 | Liz