考虑 rust 逆向难度较高，加上交互的逻辑不太简单，为了减小逆向工作量，将 server 的源码给出，于是逆向核心工作量在于 IBE 密码算法实现，即下述函数：

保留符号的 Rust 逆上述实现，能对应上 pairing-ce 库的 api ，核心加密算法的逻辑就相对简单了。本题给出了提示 Identity Based Encryption，加上 pairing-ce 库函数，去 Google 一下现有的 IBE 体制，就能找到最著名的一篇实现 Identity-Based Encryption from the Weil Pairing，本题即实现了 BF-IBE 密码算法。

完整源码见附件 chlallenge-src.zip，感兴趣的密码师傅可以直接当成 crypto 题目来做，看雪往年貌似都没有纯 crypto 赛道的题，所以这题最终还是加了逆向的东西在里面，至于题目分类到 pwn 方向，是因为题目部署时用的 pwn 题目框架，自动归类到 pwn。

基于身份的加密（Identity-Based Encryption abbr. IBE），传统的公钥加密需要的公钥文件和用户真实身份往往没有直接的关联，并且公钥为二进制文件，用户难以记住，只能用其他方式保存和发送，比如 PGP 邮件加密服务，需要先获知对方的公钥，才能进行加密传输，实际使用复杂。

公钥即身份是 IBE 的核心理念例如在 PGP 服务中，任意用户的公钥就是其邮箱地址例如 alice@example.com，同一公钥基础设施下的用户将可以直接发送加密邮件。这将大大简便公钥加密使用的便捷性。赛题实现了一个简单的 IBE 公钥系统，提供邮件注册、登录、恢复等功能，IBE 加密基于安全的 BLS12-381 曲线，使用 rust 实现。

完整漏洞利用过程：

Hmac 伪哈希碰撞：hmac 的 key 是会有预填充以及可能的预哈希操作的，因此题目提供的注册服务可能导致其他用户能够注册得到 admin 的私钥。比如 admin 公钥后面填充若干 0 字节，能够得到 admin 的等价私钥，经过认证即可越权操作。

BLS12-381 曲线的子群攻击（Subgroup Attack）：blind recovery 服务提供了潜在的 BLS12-381 子群上 DH 的交互。加之 rust 标准实现没有检查子群，因此可以恢复出 PKG 设施的部分私钥。

RSA-LSB-Oracle ：可以通过 system reset 功能巧妙转换得到一个类似 RSA 低位解密泄露的 Oracle 场景，进而恢复出更多信息，最终能够通过 BSGS 求解离散对数恢复出完整的 PKG 私钥，从而破解整个系统的安全性。

基于身份的加密（identity based encryption）是一类绑定加密者身份的加密。Boneh 和 Franklin 在 2001 年第一次提出了用双线性映射构造 IBE 密码体制。IBE 的特点是公钥可以是任意字符串，例如电子邮件地址、电话号码等，这消除了传统公钥基础设施（PKI）中证书管理的需要。但是同时引入了一个中心的信任方，称之为 PKG ，他负责所有密钥的产生和分发。本题基于 BLS12-381 曲线实现了一个标准的 BF-IBE 加密。该加密体制流程如下。

公开参数：给定一个素数阶群 $G$G ，阶为 $p$p ，存在双线性映射 $e:G\times G\mapsto$e:G×G↦Gt​ ，令 $g\in G$g∈G 是生成元，记 $=e(g,g)\in$g^​=e(g,g)∈Gt​ ，记哈希函数 $:\{,{\}}^{\ast }\to G$h1​:{0,1}∗→G ，$:\to \{,{\}}^{\ast }$h2​:Gt​→{0,1}∗ 。

初始化（Setup） ：PKG 随机选择 $s$s←RZp​ ，生成 PKG 的公钥为 $g^s$gs 。

密钥提取（Extarct）：Alice 和 Bob 可以向 PKG 获取他们的私钥：

$=(s,)=({)}^s=(s,)=({)}^s$Sa​=MakeKey(s,’Alice’)=h1​(’Alcie’)sSb​=MakeKey(s,’Bob’)=h1​(’Bob’)s

加密（Encryption）：Alice 向 Bob 发送加密消息 $m$m ，随机选择 $r$r←RZp​ ，然后计算密文：

Encrypt (g,gs, ’Bob’, m)​=(gr,m⊕h2​(e(h1​( ’Bob’ ),gs)r)=(ugr​​,vm⊕h2​(e(h1​( ’Bob’ ),g)rs​​))​

解密（Decryption）：给定加密消息 $(u,v)=(g^r,m\oplus \left(e{\left(\right(),g)}^{rs}\right)$(u,v)=(gr,m⊕h2​(e(h1​( ’Bob’ ),g)rs) ， Bob 的私钥为 $w=({)}^s$w=h1​(’Bob’)s ，则解密算法为：$(u,v,w)=v\oplus \left(e\right(w,u\left)\right)$ Decrypt (u,v,w)=v⊕h2​(e(w,u)) 。

解密验证如下：

Decrypt (u,v,w)=v=m=m=m​⊕h2​(e(w,u))⊕h2​(e(h1​( ’Bob’ ),g)rs)⊕h2​(e(h1​( ’Bob’ )s,gr))⊕h2​(e(h1​( ’Bob’ ),g)rs)⊕h2​(e(h1​( ’Bob’ ),g)rs)​

上述加解密的核心在于理解 pairing/bilinear map 的特征：

$e(u^a,v^b)=e(u,v{)}^{ab}$e(ua,vb)=e(u,v)ab

对于双线性映射感兴趣的读者可以参考我的另一篇博客 Intro to bilinear map。本题的密码算法主体实现基本与标准的 BF-IBE 算法一致，区别在于

哈希映射：使用了 hmac2g1 ，即使用了 hmac 函数，而不是一般的哈希函数。

密钥生成：增加一个 make_key_blind 函数，类似盲分发密钥，限制了只有 admin 才能调用这个函数。

上述两个函数是本题逆向的两个关键函数。

hmac 的函数如下：

首先比较明显的误用在于 hmac2g1(uname, pkg.gs) ，根据注册函数给出的逻辑，这个 uname 是用户可控的任意字符串（邮箱），但是不能多次注册同一个 uname，以及禁掉了 admin@pubkey.com 的注册。用户想要获取 admin 的权限，必须拿到 admin 的私钥。那么是否能够找到两个字符串 a 和 b 使得上述 hmac2g1(a, pk) 与 hmac2g1(b, pk) 得到相同的值，从而生成一样的私钥？

注意到使用 uname 作为 hmac 函数的密钥输入，是不安全的。根据 hmac 的一般框架

其中 K' 是从秘密密钥 K 推导出的分组长度（blocksize）的密钥（本题 sha256 的 blocksize 是 64 字节），

在 K 小于分组长度时：通过用 0 向右填充直至 blocksize，得到 K'

在 K 大于分组长度时，通过先哈希到小于或等于块大小，然后用 0 向右填充。

因此，容易知道下述情况会生成伪 hmac 碰撞，这种碰撞不是 hash 函数本身的问题，而在于密钥的等价性：

uname 长度小于分组长度时：形如 uname 和 uname + \x00 形式的字符串是等价密钥。

uname 长度大于分组长度时：形如uname 与 H(uname) 的字符串也会生成等价密钥。

回到本题， admin@pubkey.com 与 admin@pubkey.com\x00 会生成相同的私钥，因此只需要注册一个 admin@pubkey.com\x00 字符串的账号，就能拿到 admin@pubkey.com 的私钥以及 credential （私钥的哈希）。从而认证后获得 admin 权限。

BLS12-381 曲线是标准的安全曲线，常用于 pairing-based cryptography 和零知识证明协议。BLS12-381 曲线存在 256 比特的一个素数阶子群，具有 128 比特的安全性，且支持高效配对（pairing）。在 pairing-ce 库中，本身实现是没有任何问题的， 所有运算都是基于这个 256 比特的素数阶子群来操作的。但是，一旦我们在这个库上使用用户自定义的点，就可能导致恶意的子群攻击（Subgroup Attack）。关于 BLS12-381 曲线的更多信息，请参考 BLS12-381 For The Rest Of Us。

首先在 sagemath 上简单测试 BLS12-381 曲线的阶：

可以得到：

BLS12-381 曲线上的确存在光滑子群，其阶大概 126 比特。但是其群结构不是循环群，即必须有两个生成元才能生成整个群。因此我们能够找到的最大阶光滑子群的最大阶是

$p=\ast \ast \ast \ast$p=3∗11∗10177∗859267∗52437899

只有 64 比特。那么我们能否将题目中 IBE 的交互迁移到光滑子群呢？注意到 make_key_blind 的相关逻辑：

在 blind_recovery 函数中，admin 控制输入参数 $x$x 作为 BLS12-381 曲线上的点的 x-坐标。 Server 虽然会检查曲线上是否存在该点，但并不会检查该点是否仍然落在 256 比特的素数阶群内，最终会输出点 $\left[d\right]G$[d]G 的哈希，其中 $d$d 是 PKG 的私钥。

因为返回值只有哈希，不能使用 Pohlig-Hellman 算法求解离散对数，但是子群足够光滑，分为三次，进行简单的爆破也能恢复出 $d$d 的 64 比特信息，发送下述三个子群的生成元：

​G1​,∣G1​∣=3∗11∗10177G2​,∣G2​∣=859267G3​,∣G3​∣=452437899​

然后本地计算哈希表，查找返回的哈希值，我们最终能够得到 $\ell =dmodp$ℓ=dmodp。但是这还远远不够，真实的私钥长度 $d\approx {}^{}$d≈2256 。

交互中可以重置整个 system 的 PKG，即

记 256 比特的素数阶为：

$r=$r=52435875175126190479447740508185965837690552500527637822603658699938581184513

重置过程将 $d^{\prime }=m\cdot dmodr$d′=m⋅dmodr ，并且根据 $d^{\prime }$d′ 生成新的 PKG。这意味利用上节的子群攻击，我们又能继续得到泄露值：

$\ell =(m\cdot dmodr)modp\left(L\right)$ℓ=(m⋅dmodr)modp(L)

乍一看这似乎是一个 Hidden Number Problem，但是基于 Lattice 求解 HNP 在这里行不通，因为我们最多只能重置两次系统，从而最多只能得到三个 $\left(L\right)$(L) 等式，不能完全恢复 $d$d。

与 HNP 问题不同的是，在这里 $m$m 是可控的，可以转换成类似 RSA-LSB-Leak 的场景。将私钥 $d$d 进行 $p$p 进制展开：

d=x0​+x1​p1+x2​p2+⋯xk​pk,pk<r

第一次利用子群攻击，我们恢复出 $=dmodp$x0​=dmodp 。那么次我们第一次重置系统时令 $=p^{-}modr$m1​=p−1modr ，则 PKG 的私钥值为：

d1​​=m1​dmodr=p−1(x0​+x1​p1+x2​p2+⋯xk​pk)modr=p−1x0​+x1​+p1U1​≤pk−2≪r(x2​+⋯)​​modr=p−1x0​+x1​+pU1​modr​

因为 $\le p,p\le p^{k-}\ll r$xi​≤p,pU1​≤pk−1≪r， 在模 $r$r 后，上式极大概率可以在整数环上表示为：

$=\left(p^{-}modr\right)++p$d1​=(p−1x0​modr)+x1​+pU1​

因此重置后得到的新的泄露值为：

ℓ1​​=d1​modp=(p−1x0​modr)+x1​modp​

而 $p^{-}$p−1x0​ 的值在上一步中已知，进而我们可以恢复出 $$x1​ 的值：

$=(-(p^{-}modr\left)\right)modp$x1​=(ℓ1​−(p−1x0​modr))modp

不难通过数学归纳法得出，通过每次乘以 $=p^{-i}modr$mi​=p−imodr ，我们可以依次恢复出 $,,\cdots$x0​,x1​,⋯ ，从而恢复出全部的信息。即使恢复不了全部信息，我们能够尽可能恢复出：

$=dmod{p}^i$di​=dmodpi

在这题中，我们最多恢复出：

$=dmod{p}^{}$d3​=dmodp3

进而：

d​=d3​+k3​p3=prefix+y​

其中 prefix 是已知 $d$d 的前两个字节为 KX 对应的值，$y\le {-}^{}$y≤2256−16 ，从而我们还知道

$=-mod{p}^{}⟹y=+k{p}^{}$y0​=d3​−prefixmodp3⟹y=y0​+kp3

其中 $k\le {-}^{}/p^{}\approx {}^{}$k≤2256−16/p3≈248 ，整个系统重置前的 PKG 公钥满足：

P​=[d]G=[prefix+y0​+kp3]G​

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！