From A to Z: Projective coordinates leakage in the wild: research data and tooling

Description

This dataset and software tool are for reproducing the research results related to CVE-2020-10932 and CVE-2020-11735, resulting from the article "From A to Z: Projective coordinates leakage in the wild" (to appear at CHES 2020). The data was used to carry out the attack in Section 6 of the article.

Data format

txt files

The [int].txt files contain an encoded page-fault trace prefixed by trace:.

A trace represents the sequence of tracked memory pages that were executed during the generation of an ECDSA signature. The trace is encoded using ASCII characters for better visualization.

The encoding follows this table:

| Functions | Symbol | Page offset |
| ---------------------- |:------:|:-------:|
| _gcry_ecc_ecdsa_sign | T | 0xa1000 |
| _gcry_mpi_invm | . | 0xcf000 |
| _gcry_mpi_set | S | 0xd5000 |
| _gcry_mpi_add | A | 0xcd000 |
| _gcry_mpih_sub_n | - | 0xd8000 |
| _gcry_mpih_rshift | - | 0xd8000 |

_gcry_ecc_ecdsa_sign is the highest level function tracked in the attack. This allows to differentiate different calls to the _gcry_mpi_invm function which contains an insecure version of a Binary Extended Euclidean Algorithm (BEEA).

Using these pages it is possible to locate the execution of _gcry_mpi_invm corresponding to the computation of Z mod p during projective to affine coordinates conversion (see preprocess_trace function).

It can be seen, that _gcry_mpih_sub_n and _gcry_mpih_rshift shares a page. However, they can be differentiated using mainly the caller memory page. This sharing, instead of being a drawback, allows a straightforward recovery of BEEA execution flow (see extract_Zi and extract_Xi functions in recover_z.py).

dat files

The format of the [int].dat files is as follows.

# X [hex]: Ground truth projective output of scalar multiplication, before affine conversion

# Y [hex]: Ground truth projective output of scalar multiplication, before affine conversion

# Z [hex]: Ground truth projective output of scalar multiplication, before affine conversion

# curve_name [str]: The curve (P256)

# h [hex]: Hash of the message to be signed

# k [hex]: Ground truth ECDSA nonce

# q [hex]: Curve order

# r [hex]: First component of the ECDSA signature

# s [hex]: Second component of the ECDSA signature

# x [hex]: Ground truth ECDSA private key

# y [hex] [hex]: Public key coordinates

# leak_pad [int],[int],[int]: Leakage recovered during backtracking. Example: 0,4,15 => 0 = k % 2**4 = k & 15

Tooling

The recover_z.py script

Loads a trace.

Recovers the corresponding Z coordinate from the trace data.

verifies the recovered Z matches the ground truth Z.

Example

Unpack the data:

tar xf traces.tar.gz

Run the tooling on trace index 123:

$ python2 recover_z.py 123
INFO:recovered Z:65b9b7006bc7b030218bef1b6e569f9f7acaee059b53d669388c6b860f67e213
INFO: real Z:65b9b7006bc7b030218bef1b6e569f9f7acaee059b53d669388c6b860f67e213

The output demonstrates the recovered Z coordinate is correct, i.e. matches the ground truth.

Credits

Authors

Alejandro Cabrera Aldaya (Tampere University, Tampere, Finland)

Cesar Pereida García (Tampere University, Tampere, Finland)

Billy Bob Brumley (Tampere University, Tampere, Finland)

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 804476).

License

This project is distributed under MIT license.

## 数据集说明

本数据集与配套软件工具用于复现与CVE-2020-10932及CVE-2020-11735相关的研究成果，该成果来自论文《From A to Z: Projective coordinates leakage in the wild》（已被CHES 2020收录）。本数据集用于开展论文第6节中的攻击实验。

## 数据格式

### 文本文件（.txt）
`[整数].txt` 文件包含以`trace:`为前缀的编码后页错误跟踪记录。

一条跟踪记录代表椭圆曲线数字签名算法（ECDSA, Elliptic Curve Digital Signature Algorithm）签名生成过程中，被跟踪的内存页执行序列。为便于可视化，该跟踪记录采用ASCII字符编码。

其编码规则遵循如下映射表：

| 函数名 | 符号 | 页偏移量 |
| ----------------------- |:----:|:-------:|
| _gcry_ecc_ecdsa_sign | T | 0xa1000 |
| _gcry_mpi_invm | . | 0xcf000 |
| _gcry_mpi_set | S | 0xd5000 |
| _gcry_mpi_add | A | 0xcd000 |
| _gcry_mpih_sub_n | - | 0xd8000 |
| _gcry_mpih_rshift | - | 0xd8000 |

_gcry_ecc_ecdsa_sign是本次攻击中跟踪的最高层级函数，借此可区分对_gcry_mpi_invm函数的不同调用——该函数包含一个存在安全隐患的二进制扩展欧几里得算法（Binary Extended Euclidean Algorithm, BEEA）版本。

利用上述内存页，可定位到射影坐标转仿射坐标过程中计算Z mod p时对应的_gcry_mpi_invm执行流程（详见preprocess_trace函数）。

需注意，_gcry_mpih_sub_n与_gcry_mpih_rshift共享同一内存页，但可通过调用者所在的内存页加以区分。这种内存共享非但未构成障碍，反而可直接恢复BEEA的执行流（详见recover_z.py中的extract_Zi与extract_Xi函数）。

### 数据文件（.dat）
`[整数].dat` 文件的格式如下：

# X [hex]：仿射转换前，标量乘法的基准射影输出结果
# Y [hex]：仿射转换前，标量乘法的基准射影输出结果
# Z [hex]：仿射转换前，标量乘法的基准射影输出结果
# curve_name [str]：所用椭圆曲线（P256）
# h [hex]：待签名消息的哈希值
# k [hex]：基准ECDSA随机数（Nonce）
# q [hex]：椭圆曲线的阶数
# r [hex]：ECDSA签名的第一分量
# s [hex]：ECDSA签名的第二分量
# x [hex]：基准ECDSA私钥
# y [hex] [hex]：公钥坐标
# leak_pad [int],[int],[int]：回溯过程中恢复的侧信道泄漏信息。示例：0,4,15 表示 0 = k % 2**4 = k & 15

## 工具集

### recover_z.py 脚本

该脚本具备如下功能：
1. 加载页错误跟踪数据
2. 从跟踪数据中恢复对应的Z坐标
3. 验证恢复得到的Z坐标与基准Z值是否一致

## 示例

### 解压数据
bash
tar xf traces.tar.gz

### 运行工具（对索引为123的跟踪文件）
bash
$ python2 recover_z.py 123
INFO: recovered Z:65b9b7006bc7b030218bef1b6e569f9f7acaee059b53d669388c6b860f67e213
INFO: real Z:65b9b7006bc7b030218bef1b6e569f9f7acaee059b53d669388c6b860f67e213

上述输出表明，恢复得到的Z坐标与基准值完全匹配，验证结果正确。

## 致谢

### 作者

Alejandro Cabrera Aldaya（芬兰坦佩雷大学，坦佩雷）
Cesar Pereida García（芬兰坦佩雷大学，坦佩雷）
Billy Bob Brumley（芬兰坦佩雷大学，坦佩雷）

## 资助

本项目获得欧洲研究委员会（ERC, European Research Council）资助，隶属于欧盟《地平线2020》研究与创新计划（协议编号：804476）。

## 许可

本项目采用MIT许可证分发。