2024 KCTF 大赛 | 第五题《废弃星球》设计思路及解析

2024 KCTF 大赛 | 第五题《废弃星球》设计思路及解析
2024-8-26 18:3:13 Author: mp.weixin.qq.com(查看原文) 阅读量:3 收藏

2024 KCTF 大赛于8月15日正式开赛！比赛设置了多维度的评分体系，包括难度值、火力值和精致度积分，旨在引导竞赛的难度和趣味度，使其更具挑战性和吸引力。同时，也为参赛选手提供了更加公平、有趣的竞赛平台。

今天中午12点，第五题《废弃星球》已截止答题，无战队成功提交flag。据参赛选手反馈，本题确实有一定的难度，一起来看看设计思路和题解吧。

*注意：签到题《逐光启航》持续开放，整个比赛期间均可提交答案获得积分

出题战队：98k

战队成员ID：GreatIchild（队长）、c10v3r、tl2cents

设计思路

参赛题目类别：Crypto + Reverse

题目类型：远程环境（docker） + 附件

题目相关主题：IBE，PKC，Pairing，Rust。相关描述如：convenient public key service。

出题人：tl2cents

1、题目设计思路/背景

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

**公钥即身份，是 IBE 的核心理念。**例如在 PGP 服务中，任意用户的公钥就是其邮箱地址例如 [email protected]，同一公钥基础设施下的用户将可以直接发送加密邮件。这将大大简便公钥加密使用的便捷性。

2、赛题实现和漏洞

赛题实现了一个简单的 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 私钥，从而破解整个系统的安全性。

赛题提供的完整的交互信息提示，其外在逻辑是非常简单的，发现漏洞点需要先逆向定位到关键逻辑，再结合密码分析找到漏洞。

详细利用见赛题 EXP。

3、exp 运行截图

rust 环境下，在 exp 目录执行：

cargo run --release

赛题解析

由于本题无战队提交flag，以下解析由出题者【tl2cents】给出思路。

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

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

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

1、Writeup

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

公钥即身份是 IBE 的核心理念例如在 PGP 服务中，任意用户的公钥就是其邮箱地址例如 [email protected]，同一公钥基础设施下的用户将可以直接发送加密邮件。这将大大简便公钥加密使用的便捷性。赛题实现了一个简单的 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 私钥，从而破解整个系统的安全性

2、Identity Based Encrytion

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

该加密体制流程如下：

解密验证如下：

对于双线性映射感兴趣的读者可以参考我的另一篇博客 Intro to bilinear map（https://blog.tanglee.top/2024/08/24/Intro-to-Bilinear-Map.html）。本题的密码算法主体实现基本与标准的 BF-IBE 算法一致，区别在于：

哈希映射：使用了 hmac2g1 ，即使用了 hmac 函数，而不是一般的哈希函数。
密钥生成：增加一个 make_key_blind 函数，类似盲分发密钥，限制了只有 admin 才能调用这个函数。

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

3、HMAC 伪碰撞

hmac 的函数如下：

pub fn hmac2g1<T>(msg: &str, pk: &T) -> G1Affinewhere    T: Hashable,{    let data = pk.hash();    let mut keyed_hmac = <HmacFunc as Mac>::new_from_slice(msg.as_bytes()).unwrap();    keyed_hmac.update(&data);    let result = keyed_hmac.finalize().into_bytes();    let result = result.as_slice();    let x = BigUint::from_bytes_be(result);    let xr = Fr::from_str(&x.to_string()).unwrap();    G1::one().into_affine().mul(xr).into_affine()}

首先比较明显的误用在于 hmac2g1(uname, pkg.gs) ，根据注册函数给出的逻辑，这个 uname 是用户可控的任意字符串（邮箱），但是不能多次注册同一个 uname，以及禁掉了 [email protected] 的注册。用户想要获取 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) 的字符串也会生成等价密钥。

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

4、BLS12-381 曲线子群攻击

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

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

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaabK = GF(p)a = K(0x00)b = K(0x04)E = EllipticCurve(K, (a, b))G = E(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB, 0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)# E.set_order(0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001 * 0x396C8C005555E1568C00AAAB0000AAAB)full_order = E.order()print(factor(full_order))

可以得到：

3 * 11^2 * 10177^2 * 859267^2 * 52437899^2 * 52435875175126190479447740508185965837690552500527637822603658699938581184513

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

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

pub fn make_key_blind(&self, x: Fq) -> Option<PrivateKey> {        if let Some(g) = get_point_from_x(x, false) {            Some(PrivateKey::new(self.pk, g.mul(self.x).into_affine()))        } else {            None        }    }
fn blind_recovery(&self, x: Fq) -> Option<Hash> {        // only server_admin can do this        if let Some(sk) = self.pkg.make_key_blind(x) {            Some(sk.gx.hash())        } else {            None        }    }

在 blind_recovery 函数中，admin 控制输入参数 xx 作为 BLS12-381 曲线上的点的 x-坐标。Server 虽然会检查曲线上是否存在该点，但并不会检查该点是否仍然落在 256 比特的素数阶群内，最终会输出点

的哈希，其中 d 是 PKG 的私钥。

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

5、LSB Leak Oracle

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

fn reset_system(&mut self, mul: &Fr) -> Option<bool> {        // not 1 or 0        if mul == &Fr::from_str("1").unwrap() || mul == &Fr::from_str("0").unwrap() {            return Some(false);        }        let mut super_x = self.pkg.x.clone();        super_x.mul_assign(mul);        let pkg = PKG::new(super_x);        let admin_sk = pkg.make_key(&self.admin);        let user_store: UserStore = Mutex::new(HashMap::new());        {            let mut muser_store = user_store.lock().unwrap();            muser_store.insert(self.admin.clone(), admin_sk.gx.hash());        }        self.pkg = pkg;        self.user_store = user_store;        Some(true)    }

记 256 比特的素数阶为：

乍一看这似乎是一个 Hidden Number Problem，但是基于 Lattice 求解 HNP 在这里行不通，因为我们最多只能重置两次系统，从而最多只能得到三个

等式，不能完全恢复 d。

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

离散对数求解

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

进而：

注记

今日中午12点，第六题异星文明

正式开赛

球分享

球点赞

球在看

点击阅读原文查看更多

文章来源: https://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458569599&idx=1&sn=22667956afd6d4b6df564a898e9ba62d&chksm=b18dfbf586fa72e39a67cac219c4d5c636a949d18f0288f1b0aa52f7c4b5be4b8fd379470624&scene=58&subscene=0#rd
如有侵权请联系:admin#unsafe.sh