JinghuiWW/ecdsa-leakage-attack

# 基于格算法的 ECDSA Nonce 泄露攻击 本仓库包含使用基于格算法攻击 ECDSA nonce 泄露的 Python 源代码。具体算法在以下论文中详细说明： ** Yiming Gao, Jinghui Wang, Honggang Hu 和 Binang He, Attacking ECDSA with Nonce Leakage by Lattice Sieving: Bridging the Gap with Fourier Analysis-based Attacks. ** 在这篇[论文](https://eprint.iacr.org/2024/296)中，我们旨在为一个开放性问题提供解决方案：能否通过利用更多样本来增强基于格的攻击？使用本仓库，我们可以利用大约 $2^{25}$ 个 ECDSA 样本，通过 1 比特泄露攻破 160 比特的 ECDSA。此外，我们解决 HNP 的新算法被扩展以处理错误输入的情况，从而提高了基于格攻击的鲁棒性。 ## 针对 Nonce 泄露的 ECDSA 密钥恢复 您可以使用多个 CPU 核心对实例执行攻击。例如： ``` python solveECDSAfromLSB.py -n 256 -s 4 -m 65 -t 4 ``` 此命令将使用 4 个 CPU 线程解决一个 ECDSA (256, 4) 实例。 - -n 指定模数的比特大小。 - -s 表示泄露量。 - -m 是用于构建格的样本数。 - -t 定义要使用的 CPU 线程数。 要使用 GPU 加速攻击，请使用 -g 选项指定 GPU 数量。有关所有参数的详细信息，请运行： ``` python solveECDSAfromLSB.py -h ``` 另一个例子，要解决 ECDSA(128, 1) 实例，请运行： ``` python solveECDSAfromLSB.py -n 128 -s 1 -m 117 -x 15 -t 24 -g 2 -f 0 -f1 "Instances/128_1/lines.txt" -f2 "Instances/128_1/lsb.txt" -f3 "Instances/128_1/sk.txt" ``` 您还可以对公共数据集（例如 [minerva](https://github.com/crocs-muni/minerva/tree/master/data)）执行攻击。请注意，该数据集指示的是 nonce 的前导零比特数（即最高有效位）。例如： ``` python solveECDSAfromMSB.py -n 256 -s 3 -m1 90 -m4 512 -t 16 -f1 "minerva-data/athena/256_3/lines.txt" -f2 "minerva-data/athena/256_3/msb.txt" ``` 此命令将解决来自 Athena 数据集的一个 ECDSA 实例，其中： - -n 指定模数的比特大小。 - -s 表示泄露量。 - -m1 是用于构建格的样本数。 - -m4 是用于线性谓词的样本数。 - -t 定义要使用的 CPU 线程数。 - -f1 提供包含数据行（包括数据和公钥 (r, s)）的文件路径。 - -f2 提供 MSB 文件所在的路径。 为了方便起见，我们提供了两个 bash 脚本，autoRunECDSALSB.sh 和 autoRunECDSAMSB.sh。根据攻击目标，您可以修改相应脚本文件中的参数。 要执行针对 LSB 情况的攻击，请使用以下命令： ``` bash autoRunECDSALSB.sh ``` 要执行针对 MSB 情况的攻击，请使用以下命令： ``` bash autoRunECDSAMSB.sh ``` ## 环境 要进行攻击，请确保您的机器上已正确设置以下环境： - [FPLLL](https://github.com/fplll/fplll) 和 [FPyLLL](https://github.com/fplll/fpylll) 用于数据结构和 BKZ 算法。 - [G6K](https://github.com/fplll/g6k) 用于格筛。 - [G6K-GPU-Tensor](https://github.com/WvanWoerden/G6K-GPU-Tensor) 用于带有 GPU 加速的格筛。 ## 针对 ECDSA 的基于格攻击的新记录 我们取得了几项针对 ECDSA 的基于格攻击的新记录。为了便于复现，成功攻破的实例已存储在 Instances 文件夹中。这些攻击是使用 Intel Xeon Platinum 8480+ CPU 和四块 GeForce RTX 4090 GPU 进行的。有关时间和内存消耗的具体详细信息如下表所示： **4 比特泄露** | **Curve** | **Leakage** | **d** | **x** | **Expected Sample Size** | **Wall time** | **Mem GiB** | |------------------|-------------|---------|-----------|-------------|---------------|-------------| | brainpoolp512r1 | 4 | 130 | 0 | $2^{10}$ | 96min | 254 | **1 比特泄露** | **Curve** | **Leakage** | **d** | **x** | **Expected Sample Size** | **Wall time** | **Mem GiB** | |------------------|-------------|---------|-----------|-------------|---------------|-------------| | secp128r1 | 1 | 131 | 0 | $2^8$ | 72min | 294 | | secp128r1 | 1 | 118 | 15 | $2^{26}$ | 8min | 53 | | secp160r1 | 1 | 144 | 14 | $2^{25}$ | 824min | 1939 | | secp160r1 | 1 | 138 | 25 | $2^{36}$ | 279min | 850 | **小于 1 比特泄露** | **Curve** | **Error rate** | **d** | **x** | **Expected Sample Size** | **Wall time** | **Mem GiB** | |------------------|----------------|---------|-------------|-------------|---------------|-------------| |secp128r1 | 0.1 | 140 | 20 | $2^{31}$ | 370min | 1090 | | secp160r1 | 0.02 | 144 | 14 | $2^{25}$ | 1009min | 1960 | 请注意，此实现中 $x$ 的定义与论文中的定义略有不同。具体来说，实现中的 $2^{x}$ 对应于论文中的 $x$。 ## 致谢 本工作得到了国家自然科学基金（资助号：62472397）和量子科学与技术创新计划（资助号：2021ZD0302902）的支持。

标签：CTF安全工具, ECDSA, Hidden Number Problem, LSB泄露, MSB泄露, Python, 侧信道攻击, 傅里叶分析, 区块链安全, 基于格的密码分析, 密码分析, 密码学, 并行计算, 应用安全, 手动系统调用, 无后门, 格攻击, 椭圆曲线数字签名算法, 网络签名安全, 逆向工具, 随机数泄露, 隐藏数问题