Usuba：高级语言编译器优化比特切片加密算法的博士论文

136 浏览量更新于2024-06-18 收藏 16.09MB PDF 举报

该篇名为《优化的比特切片编译器：HAL多学科开放获取档案中的博士论文》的学术论文主要探讨了比特切片在密码学领域的应用和挑战。比特切片作为一种在对称加密算法中广泛应用的技术，能够实现高吞吐量、并行处理和常数时间复杂度，但其手动实现过程复杂且需要深入理解密码学原理、CPU微体系结构以及对抗侧信道攻击的知识。这种技术的实现工作通常涉及大量的手工编写、优化和保护，这导致编写的代码难以维护。为了简化这一过程，作者Darius Mercadier提出了一种高级领域特定语言——Usuba。Usuba的设计目标是让开发者能够编写高级密码规范，无需过多关注底层的并行实现细节。通过Usuba，开发人员可以直接表达他们的加密算法逻辑，编译器会负责将这些高级描述转化为高效的比特切片实现，从而减少手动优化的工作量，并提升代码的可读性和维护性。论文的核心贡献包括Usuba语言的设计与实现，以及它如何通过自动化的方式优化比特切片，降低复杂度，同时考虑了安全性的要求。此外，论文还可能包含了一些实验评估，展示了Usuba在实际加密算法中的性能提升和安全性的保障。这篇博士学位论文是在Sorbonne University完成的，作者在计算机科学，特别是电信和电子工程领域进行了深入的研究，并在2020年11月20日进行了答辩。论文的指导教师包括Gilles Muller、Pierre-Évariste Dagand、Karthik Bhargavan、Sandrine Lazy、Caroline Collange、Xavier Léroy、Thomas Pornin和Damien Vergnaud等专家，他们共同推动了比特切片编译器领域的进步。通过阅读这篇论文，读者不仅可以了解到比特切片技术的最新进展，还能学习到如何利用高级语言来简化密码学算法的实现和优化，这对于密码学研究者、软件工程师和安全专家来说是一份宝贵的参考资料。此外，该论文还体现了多学科开放获取档案馆HAL在促进科学研究传播中的重要作用。

movl $2000000000, %esi

.loop:

addl %edi, %r14d

addl %edi, %ecx

addl %edi, %eax

addl %edi, %r14d

addl %edi, %ecx

addl %edi, %eax

addq $-2, %rsi

jne .loop

The main loop of this code contains 7 additions and a jump. Since modern superscalar

Intel CPUs can execute 4 additions per cycles, or 3 additions and a jump, one could expect

the body of the loop to execute in 2 cycles. However, depending on the alignment of the

jump instruction

(jne .loop), the loop will execute in 3 cycles rather than 2.

In order to achieve the best throughputs possible, cryptographers resort to various

programming trick. One such trick, popularized by Matsui [206], is called interleaving.

To illustrate its principle, consider for instance the following imaginary block cipher,

written in C:

void cipher(int plaintext, int key[2], int

ciphertext) {

int t1 = plaintext ˆ key[0];

ciphertext = t1 ˆ key[1];

}

void encrypt_blocks(int

input, int key[2], int

output, int length) {

for (int i = 0; i < length; i++) {

cipher(input[i], key, &output[i]);

}

The cipher function contains two instructions. Despite the fact that modern CPUs are

superscalar and can execute several instructions per cycles, the second instruction (t1 ˆ

key[1]) uses the result of the ﬁrst one (t1 = plaintext ˆ key[0]) and thus cannot

be computed in the same cycle. The execution time of encrypt blocks can thus be

expected to be length ∗ 2 cycles. Matsui’s trick consists in unrolling once the main loop

and interleaving two independent instances of cipher:

void cipher_inter(int plaintext[2], int key[2], int ciphertext[2]) {

int t1_0 = plaintext[0] ˆ key[0];

int t1_1 = plaintext[1] ˆ key[0];

ciphertext[0] = t1_0 ˆ key[1];

ciphertext[1] = t1_1 ˆ key[1];

}

void encrypt_blocks_inter(int

input, int key[2], int

output, int length) {

for (int i = 0; i < length; i+=2) {

cipher_inter(&input[i], key, &output[i]);

}

This new code is functionally equivalent to the previous one. cipher inter computes

the ciphertexts of 2 plaintexts at the same time, and the main loop of encrypt blocks inter

thus performs twice less iterations. However, since the ﬁrst two (resp., last two) instruc-

tions of cipher inter have no data dependencies between them, they can be executed

See https://stackoverflow.com/q/59883527/4990392

16 CHAPTER 1. INTRODUCTION

during the same cycle. cipher inter thus takes as many cycles as cycle to be exe-

cuted, but computes two ciphertexts instead of one. Overall, encrypt blocks inter

is thus twice faster than encrypt blocks.

1.0.3 The Case for Usuba

Implementing high-throughput cryptographic primitives, or securing primitives against

side-channel attacks are complicated and tedious tasks. Both are hard to get right and

tend to obfuscate the code, thus hindering code maintenance. Trying to achieve both at

the same time, performance and side-channel protection, is a formidable task.

Instead, we propose Usuba [212, 211], a domain-speciﬁc programming language de-

signed to write symmetric cryptographic primitives. Usuba is a high-level program-

ming language, enjoying a straightforward formal semantics, allowing to easily reason

on program correctness. Usuba programs are constant-time by construction, and thus

protected against timing attacks. Furthermore, Usuba can automatically insert counter-

measures, such as Boolean masking, to protect against power-based side-channels. Fi-

nally, Usuba compiles to high-performance C code, exploiting SIMD extensions of mod-

ern CPUs when available (SSE, AVX, AVX512 on Intel), thus performing on par with

hand-tuned implementations.

The design of Usuba is largely driven by the structure of block ciphers. A block

cipher typically uses bit-permutations, bitwise operations, and sometimes arithmetic op-

erations, and can therefore be seen as a stateless circuit. These basic operations are com-

bined to form a round, and a block cipher is deﬁned as n (identical) rounds, each of them

taking the output of the previous round as well as a key as input. For instance, the

RECTANGLE [309] block cipher takes as input a 64-bit plaintext and 25 64-bit keys, and

produces the ciphertext through 24 rounds, each doing a xor, and calling two auxiliary

functions: SubColumn (a lookup table), and ShiftRows (a permutation). Figure 1.1a rep-

resents RECTANGLE using a circuit.

Usuba aims at providing a way to write an implementation of a cipher which is

as close to the speciﬁcation (i.e., the circuit) as possible. As such, RECTANGLE can be

straightforwardly written in Usuba in just a few lines of code, as shown in Figure 1.1b.

The code should be self-explanatory: the main function Rectangle takes as input the

plaintext as a tuple of 4 16-bit elements, and the key as a 2D vector, and computes 25

rounds, each calling the functions ShiftRows, described as 3 left-rotations, and SubColumn,

which computes a lookup in a table. This code is simple, and as close to the speciﬁca-

tion as can be. Yet, it compiles to a C code which is about 20% faster than the reference

implementation (Section 5.1), while being much simpler and more portable: whereas the

reference implementation explicitly uses SSE and AVX SIMD extensions, Usuba is not

bound to a speciﬁc SIMD extension.

One of the other main beneﬁts of Usuba is that the code it generates is constant-time

by construction. To write constant-time code with traditional languages (e.g., C) is to ﬁght

an uphill battle against compilers [27], which may silently rewrite one’s carefully crafted

program into one vulnerable to timing attacks, and against the underlying architecture

itself [216], whose undocumented, proprietary micro-architectural features may leak se-

crets through timing or otherwise. For instance, the assembly generated by Clang 9.0 for

the following C implementation of a multiplexer:

bool mux(bool x, bool y, bool z) {

return (x & y) | (˜x & z);

}

使用cmove指令，该指令不能保证是常量时间[259]。同样，一些整数乘法指令已知不是常量时间

，导致库出现问题

第1章引言

开发人员可以编写自己的软件级常量时间乘法实现[247]。这个问题是如此广泛，以至于传统用于

硬件评估的工具现在被用于分析软件实现[259]，将程序及其执行环境视为一个单一的黑盒，并测

量其执行时间是否具有足够高的概率保持恒定。大多数为密码学设计的现代编程语言都具有内置

机制来防止非常量时间操作。例如，HACL*

[310]具有不能分支的安全整数的概念，并禁止使用非常量时间操作，如除法或取模。另一方面，

FaCT

[99]认为HACL*过于低级，常量时间应该被视为编译问题：它提供了高级抽象，这些抽象被编译

成常量时间的习惯用法。采用另一种高级方法，Usuba通过采用（从开发人员的角度来看是透明

的）一种称为位切片的编程模型来强制常量时间。

Biham[72]首次引入了位切片作为加速D

ES软件实现的技巧。直观地说，位切片的思想是将n位值表示为n个寄存器中的1位。在64位寄存

器的情况下，每个寄存器因此还有63位的空位，可以通过其他独立值以相同的方式填充。为了操

作这样的数据，密码必须被减少为位逻辑操作（and，or，xor，not）。在64位机器上，位操作

实际上就像64个并行的1位操作一样有效。通过并行计算密码的64个实例，从而实现吞吐量。因

此，位切片特别擅长利用现代CPU的矢量扩展，这些扩展提供了大型寄存器（例如，Intel的128

位SSE，256位AVX和512位AVX-512）。位切片实现是通过设计实现的：没有数据相关的条件分

支或内存访问（实际上，根本不可能）。许多打破记录的块密码软件实现都利用了这种技术[189,

207,174,33]，现代密码算法现在从头开始设计时就考虑到了位切片[78,

309]。然而，位切片意味着代码复杂性的增加，使得手动编写高效的位切片代码变得困难，正如

以下几行由MatthewKwan[192]编写的DES实现的C代码所示：

s1（r31ˆk[47]，r0ˆk[11]，r1ˆk[26]，r2ˆk[3]，r3ˆk[13]，r4ˆk

[41]，＆l8，＆l16，＆l22，＆l30）;s2（r3ˆk[27]，r4ˆk[6]，r5ˆk[54]，r6ˆk[48]，r7ˆk

[39]，r8ˆk[19]，＆l12，＆l27，＆l1，＆l17）;s3（r7ˆk[53]，r8ˆk[25]，r9ˆk[33]，r10ˆk

[34]，r11ˆk[17]，r12ˆk[5]，＆l23，＆l15，＆l29，＆l5）;s4（r11ˆk[4]，r12ˆk[55]，r13ˆ

k[24]，r14ˆk[32]，r15ˆk[40]，r16ˆk[20]，＆l25，＆l19，＆l9，＆l0）;

完整的代码继续像这样进行了近300行，而Usuba的等效代码只有几行，非常类似于图1.1b中显示

的RECTANGLE代码。Usuba提供的简洁性不会带来任何性能损失：Kwan和Usuba的实现都具有

类似的吞吐量。

有时，位切片模型可能过于限制性，因为它禁止使用算术运算，并且可能无法提供最佳吞吐量，

因为它消耗了大量寄存器。为了克服这些问题，并借鉴K¨asper＆Schwabe的字节切片AES[174]

的启示，我们提出了一种称为m切片的位切片的泛化。m切片保留了位切片的恒定时间特性，同

时使用更少的寄存器，并允许使用SIMD打包算术指令（例如vpaddb，vmuldp）以及矢量排列

（例如vpshufb）。

剩余194页未读，继续阅读

cpongm

粉丝: 5
资源: 2万+

Usuba：高级语言编译器优化比特切片加密算法的博士论文

HAL：多学科开放获取档案库，存储与传播科研文献

HAL：多学科开放存取档案，存储与传播科研文献

基于代理的可视化模型：多学科开放获取研究档案深度解析

HAL：全球开放获取科研文献档案库

自动推理模型检测Web应用与协议漏洞：HAL开放存取档案的硕士论文

侧信道与故障分析：HAL开放获取档案库的防护下，工具、理论与实践

C#ASP.NET网络进销存管理系统源码数据库 SQL2008源码类型 WebForm

最新资源