HAL Id: tel-03133456https://theses.hal.science/tel-03133456v2Darius Mercadier0提交日期：2021年10月19日0HAL是一个多学科开放获取档案，用于存储和传播科学研究文献，无论其是否已发表。这些文献可能来自法国或国外的教育和研究机构，或者来自公共或私人研究中心。0多学科开放档案馆 HAL旨在存储和传播研究水平的科学文献，无论其是否已发表，这些文献来自法国或国外的教育和研究机构，公共或私人实验室。0Usuba, 优化的比特切片编译器0引用此版本：0Darius Mercadier. Usuba, 优化的比特切片编译器. 密码学与安全 [cs.CR]. Sor- bonne Université, 2020.英文. �NNT : 2020SORUS180�. �tel-03133456v2�Sp´ecialit´eDarius MERCADIERdevant le jury compos´e de :0SORBONNE UNIVERSIT ´ E博士学位论文0计算机科学0´Ecole doctorale Informatique, T´el´ecommunications et ´Electronique (巴黎)0由以下人员提交0获得以下学位：0SORBONNE UNIVERSIT ´ E 博士学位0论文题目：0Usuba, 优化的比特切片编译器0于2020年11月20日（希望如此）进行答辩0导师：Gilles M ULLER， Pierre- ´ Evariste DAGAND， Karthik B HARGAVAN， Sandrine BLAZY， Caroline C OLLANGE， Xavier L EROY，Thomas P ORNIN， Damien V ERGNAUDAbstract30比特切片是密码学中常用的一种技术，用于实现高吞吐量、并行和恒定时间的对称加密算法。然而，手动编写、优化和保护比特切片实现是一项繁琐的任务，需要对密码学、CPU微体系结构和侧信道攻击有深入的了解。由于其高复杂性，结果程序往往难以维护。为了解决这些问题，我们提出了Usuba，一种高级领域特定语言，用于编写对称加密算法。Usuba允许开发人员编写高级密码规范，而不必担心实际的并行化：Usuba程序是对密码算法的标量描述，Usuba编译器Usubac会自动生成矢量化的比特切片代码。当针对高端IntelCPU时，Usubac应用了几种领域特定的优化，如交错和自定义指令调度算法。因此，我们能够与手动调优的汇编和C实现的几种广泛使用的密码算法的吞吐量相匹配。此外，为了保护嵌入式设备上的密码实现免受侧信道攻击，我们通过两种方式扩展了我们的编译器。首先，我们将最先进的高阶掩蔽技术集成到Usubac中，以生成经过验证安全的抗功耗分析攻击的实现。其次，我们为SKIVA实现了一个后端，SKIVA是一种定制的32位CPU，可以组合抵御基于功耗和基于时序的泄漏以及故障注入的对策。R´esum´e50比特切片是一种常用的密码学技术，用于实现高吞吐量、并行和恒定时间的对称加密算法。然而，手动编写、优化和保护比特切片实现是一项繁琐的任务，需要对密码学、CPU微体系结构和侧信道攻击有深入的了解。为了解决这些问题，我们提出了Usuba，一种高级领域特定语言，用于编写对称加密算法。Usuba允许开发人员编写高级规范，而不必担心实际的并行化：Usuba程序是对密码算法的标量描述，Usuba编译器Usubac会自动生成比特切片和矢量化的代码。为了针对高端IntelCPU生成高效的代码，Usubac应用了多种领域特定的优化，例如交错和自定义指令调度算法。因此，我们的编译器生成的代码可以与手动优化的汇编和C实现的多种广泛使用的密码算法的吞吐量相匹配。此外，为了保护嵌入式设备上的密码实现免受侧信道攻击，我们通过两种方式扩展了我们的编译器。首先，我们将最先进的高阶掩蔽技术集成到Usubac中，以生成经过验证安全的抗功耗分析攻击的实现。其次，我们为SKIVA实现了一个后端，SKIVA是一种定制的32位CPU，可以组合抵御基于功耗和基于时序的泄漏以及故障注入的对策。Contents1Introduction111.1Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .191.2Background. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .201.3Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .452Usuba, Informally472.1Data Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .482.2Syntax & Semantics, Informally . . . . . . . . . . . . . . . . . . . . . . . . .492.3Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .522.4Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .582.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .663Usuba, Greek Edition713.1Syntax. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .723.2Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .743.3Monomorphization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .763.4Semantics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .793.5Usuba0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .813.6Translation to PseudoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .823.7Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .884Usubac894.1Frontend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .894.2Backend. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .944.3Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1215Performance Evaluation1235.1Usuba vs. Reference Implementations . . . . . . . . . . . . . . . . . . . . .1235.2Scalability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1285.3Polymorphic Cryptographic Implementations. . . . . . . . . . . . . . . .1305.4Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1326Protecting Against Power-based Side-channel Attacks1336.1Masking. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1346.2Tornado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1346.3Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1386.4Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1457Protecting Against Fault Attacks and Power-based Side-channels Attacks1497.1Fault Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1497.2SKIVA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1507.3Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15677.4Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1598Conclusion1618.1Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162Bibliography173Appendix A Backend optimizations193List of Figures1.1The RECTANGLE cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .171.2Skylake’s pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.3Some SIMD instructions and intrinsics . . . . . . . . . . . . . . . . . . . . . . .231.4Our benchmark code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .251.5Bitslicing example with 3-bit data and 4-bit registers . . . . . . . . . . . . . . .261.6The AVX-512 vpandd instruction . . . . . . . . . . . . . . . . . . . . . . . . . .271.7Some common modes of operation . . . . . . . . . . . . . . . . . . . . . . . . .281.8ECB vs. CTR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .291.9Piccolo’s round permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .311.10 Optimized transposition of a 4 × 4 matrix . . . . . . . . . . . . . . . . . . . . .341.11 Data layout of vsliced RECTANGLE . . . . . . . . . . . . . . . . . . . . . . . . .361.12 Data layout of hsliced RECTANGLE . . . . . . . . . . . . . . . . . . . . . . . . .371.13 A left-rotation using a shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . .381.14 Slicing layouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .391.15 Circuits for some adders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .411.16 Comparison between bitsliced adder and native addition instructions . . . . .421.17 Scaling of bitsliced adders on SIMD. . . . . . . . . . . . . . . . . . . . . . . .432.1DES’s initial permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .472.2AES’s MixColumns matrix multiplication . . . . . . . . . . . . . . . . . . . . .482.3RECTANGLE’s sliced data layouts . . . . . . . . . . . . . . . . . . . . . . . . . .492.4Usuba’s type-classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .542.5Usuba implementation of AES . . . . . . . . . . . . . . . . . . . . . . . . . . . .592.6AES’s ShiftRows step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .602.7Usuba implementation of ASCON . . . . . . . . . . . . . . . . . . . . . . . . . .612.8ACE’s step function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .622.9Usuba implementation of ACE. . . . . . . . . . . . . . . . . . . . . . . . . . .632.10 Usuba implementation of CHACHA20 . . . . . . . . . . . . . . . . . . . . . . .642.11 Usuba implementation of SERPENT . . . . . . . . . . . . . . . . . . . . . . . . .653.1Usuba’s formal pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .713.2Syntax of Usubacore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .733.3Elaboration of Usuba’s syntactic sugar to Usubacore . . . . . . . . . . . . . . .743.4Validity of a typing context. . . . . . . . . . . . . . . . . . . . . . . . . . . . .753.5Type system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .763.6Monomorphization of Usubacore programs . . . . . . . . . . . . . . . . . . . .7783.8Syntax of PseudoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .833.9PseudoC’s semantics elements. . . . . . . . . . . . . . . . . . . . . . . . . . .843.10 Semantics of PseudoC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .843.11 Translation rules from Usuba0 to PseudoC . . . . . . . . . . . . . . . . . . . .864.1Usubac’s pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .894.2Impact on throughput of fully inlining msliced ciphers. . . . . . . . . . . . .974.3Impact on throughput of fully inlining bitsliced ciphers . . . . . . . . . . . . .984.4Spilling in Usuba-generated bitsliced ciphers . . . . . . . . . . . . . . . . . . .1014.5Performance of the bitsliced code scheduling algorithm . . . . . . . . . . . . .1054.6Performance of the msliced code scheduling algorithm. . . . . . . . . . . . .1074.7Impact of interleaving on general-purpose registers . . . . . . . . . . . . . . .1144.8Impact of interleaving on Serpent . . . . . . . . . . . . . . . . . . . . . . . . . .1174.9Impact of interleaving on general-purpose registers . . . . . . . . . . . . . . .1195.1Scaling of Usuba’s implementations on Intel SIMD . . . . . . . . . . . . . . . .1295.2Comparison of RECTANGLE’s monomorphizations . . . . . . . . . . . . . . . .1316.1Tornado’s pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1356.2ISW gadgets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1366.3PYJAMASK matrix multiplication node . . . . . . . . . . . . . . . . . . . . . . .1377.1Bitslice aggregations on a 32-bit register, depending on (D,Rs). . . . . . . . . .1517.2SKIVA’s tr2 instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1527.3SKIVA’s subrot instructions. . . . . . . . . . . . . . . . . . . . . . . . . . . .1537.4SKIVA’s redundancy-related instructions. . . . . . . . . . . . . . . . . . . . .1557.5SKIVA’s redundant and instructions . . . . . . . . . . . . . . . . . . . . . . . .1567.6Time-Redundant computation of a bitsliced AES . . . . . . . . . . . . . . . . .1578.1Intel pdef u64 instruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1638.2Left-rotation by 2 after packing data with pdef u64. . . . . . . . . . . . . .1638.3CHACHA20’s round. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1648.4vslice CHACHA20’s double round. . . . . . . . . . . . . . . . . . . . . . . . .1658.5CHACHA20 in hybrid slicing mode . . . . . . . . . . . . . . . . . . . . . . . . .1668.6AES’s first round in CTR mode. . . . . . . . . . . . . . . . . . . . . . . . . . .1688.7Bitsliced DES scaling on Neon, AltiVec and SSE/AVX2/AVX512 . . . . . . . .1698.8Pipeline of a semantics-preserving Usuba compiler. . . . . . . . . . . . . . .17090表格列表02.1 运算符实例...5504.1 一些密码的交错影响...111 4.2 A SCON的交错影响...116 4.3 C LYDE的交错影响...11605.1 Usuba代码与优化的参考实现的比较...125010 表格列表05.2 Usuba代码与未优化的参考实现的比较...12706.1 评估Tornado所选原语的概述...139 6.2 在Intel上比较Usuba与参考实现...140 6.3 Tornadom sliced掩码实现的性能...142 6.4 Tornado bitsliced掩码实现的吞吐量...144 6.5手动在汇编中实现密钥例程所获得的加速比...14507.1 A ES设计空间的详尽评估...158 7.2 模拟指令跳过的实验结果...1580A.1 完全内联msliced密码的影响...193 A.2 m slice调度算法的性能（使用Clang7.0.0编译）...193 A.3 完全内联bitsliced密码的影响...194 A.4 bitslice调度算法的性能...194110第1章0介绍0密码学，源自古希腊语kryptos“隐藏”和graphein“写”，是通过将通信内容（明文）转换为不可理解的文本（密文）来保护通信安全的实践，使用的算法称为密码，通常还需要一个只有加密和解密通信的人才知道的秘密密钥作为额外输入。密码学的首次使用可以追溯到公元前1900年的古埃及。将近2000年后，尤利乌斯∙凯撒以使用密码来保护他对将军的命令而闻名，他使用的是后来被称为凯撒密码的方法，该方法是将每个字母替换为另一个字母，使得字母表的第i个字母被替换为第（n +i）个字母（其中n是1到25之间的固定值），在字母表末尾循环。在历史上，军队将继续使用密码来保护他们的通信，著名的例子是纳粹德国在第二次世界大战期间使用的恩尼格玛。如今，在我们日益数字化和越来越互联的世界中，密码学无处不在，保护敏感数据（例如密码、银行数据）并通过互联网进行数据传输，使用各种密码。现代密码学的基本模块称为密码学原语，可以分为三个主要类别：0•非对称（或公钥）密码，它使用两个不同的密钥进行加密和解密：一个是公钥，用于加密，而另一个是私钥，用于解密。常用的非对称密码的例子包括RSA[265]和椭圆曲线，如Curve25519 [59]。0• 对称（或秘密密钥）密码，它使用相同的（秘密）密钥进行加密和解密，并分为两类：0- 流密码，它生成一个伪随机比特流并与明文进行异或运算。在软件中最常用的流密码是CHA C HA 20 [61]。0–块密码，一次只加密一个固定大小的数据块。当明文长度大于块长度时，块密码会使用一种称为操作模式的算法将其转换为流密码，该算法描述了如何重复调用块密码直到整个明文被加密。最常用的块密码是高级加密标准[230]（AES），它取代了现已过时的数据加密标准[229]（D ES）。0•哈希函数，不需要密钥，也不可逆。它们通常用于提供数据完整性或不可逆地加密密码。MD5 [264]和SHA-1 [283]是两个著名的哈希函数。int check_password(char* provided, char* expected, int length) {for (int i = 0; i < length; i++) {if (provided[i] != expected[i]) {return 0;}}return 1;}int check_password(char* provided, char* expected, int length) {int flag = 1;for (int i = 0; i < length; i++) {if (provided[i] != expected[i]) {flag = 0;}}return flag;}0第1章 引言01.0.1 安全实现0密码分析专注于发现密码原语中的弱点，无论是在其算法还是在其实现中。例如，前面介绍的凯撒密码很容易被尝试将密文的所有字母按照每个可能的n（1到25之间）进行移位，直到产生一个有意义的文本的方法破解。更高级攻击的例子包括相关密钥攻击[79, 176,54]，它包括观察使用不同密钥的密码器为给定明文产生的密文中的相似性，以及差分密码分析[73,194]，其中加密了多个明文，并且攻击者试图在产生的密文中找到统计模式。如果没有实际攻击存在，即在合理的时间内无法进行攻击或以合理的成本进行设置，则认为密码是算法上安全的。即使在密码学上无法破解密码的算法级别上，其实现可能容易受到侧信道攻击的影响，侧信道攻击依赖于物理上监视密码执行以恢复秘密数据。侧信道攻击利用密码运行的体系结构的物理漏洞：执行密码需要时间，消耗功率，引起内存传输等，所有这些都可能成为攻击向量。一个典型的例子是定时攻击[185, 95,58]，它利用密码的执行时间由于依赖于秘密数据的条件分支而产生的变化。例如，考虑以下检查提供的密码是否与期望的密码匹配的C代码：0如果提供的输入和期望的输入以不同的字符开头，那么这个函数将快速返回0。然而，如果提供的输入和期望的输入以相同的10个字符开头，那么这个函数将循环十次（因此需要更长的时间）才返回0，从而通知监视此函数执行时间的攻击者他们已经正确猜到了前几个字符。这个漏洞可以通过将执行时间与秘密输入解耦，使其成为常量时间来修复：0在没有基于秘密数据的条件执行的情况下，定时攻击也可能是可能的：在现代计算机上从内存中读取某些数据所需的时间严重依赖于这些数据是否在缓存中。因此，攻击者可以设计一种缓存定时攻击，即基于缓存访问模式的定时攻击。通过监视密码的功耗，攻击者可以进行功耗分析[186,213]，以获取秘密数据的知识：功耗可以与晶体管切换状态的数量相关联，而晶体管切换状态本身可能取决于秘密数据的值[187]。13char* get_secret_data(int pin_code) {if (pin_code != expected_pin_code) {return NULL;}return secret_data;}int lookup(int index) {int table[4] = { 3, 0, 1, 2 };return table[index];}int lookup_ct(int index) {0与其被动地（即观察执行而不干扰），攻击者可以主动地在计算中注入故障[75, 32,20]（例如使用电离辐射、电磁脉冲或激光）。考虑以下C代码，如果提供的PIN码正确，则返回一些秘密数据：0攻击者可以在执行此代码期间注入故障，以跳过返回NULL指令，这将导致该函数在提供错误的PIN码时返回秘密数据。0保护代码免受故障的影响需要对硬件和现有攻击有深入的了解。例如，让我们考虑一个名为lookup的函数，它以2位整数索引作为输入，并返回私有数组table中相应索引处的2位整数：0此代码易受缓存时间攻击的影响（或者更确切地说，如果在缓存行宽度为4字节的CPU上执行），因为table[index]可能在缓存中命中或未命中，这取决于index的值。为了使lookup对此类攻击具有韧性，我们可以进行转换，消除表格，只进行恒定时间的位操作：0// 提取索引的2位 bool x0 = (index >> 1) & 1;bool x1 = index & 1;0// 通过位操作计算查找结果 bool r1 = ˜x1; bool r0 = ˜(x0 ˆ x1);0// 将结果的位重新组合 return (r0 << 1) | r1; }0lookup_ct在功能上等同于lookup。它的代码不依赖于秘密数据进行任何内存访问，因此对缓存时间攻击具有韧性。0然而，lookup_ct仍然容易受到功耗分析攻击的影响：例如，计算˜x1可能会根据x1是0还是1消耗不同的功率。为了防止基于功耗的攻击，我们可以使用布尔掩码，即通过n个随机位（称为共享）来表示秘密数据的每个位b，使得它们的异或等于原始秘密位：b =b1ˆb2ˆ...ˆbn对于每个秘密位b。这个想法是，为了知道单个秘密位的值，攻击者需要确定n位数据的值，这会以指数方式（随n增加）增加攻击的成本。将此保护添加到lookup_ct将产生以下代码（假设index已经被掩码处理，因此现在是一个共享数组）：int* lookup_ct_masked(int index[NUMBER_OF_SHARES]) {1.0.2High-Throughput ImplementationsA paramount requirement on cryptographic primitive is high throughput. Ideally, cryp-tography should be completely transparent from the point of view of the end users. How-ever, the increasing complexity of CPU microarchitectures makes it hard to efficientlyimplement primitives. For instance, consider the following C code:int a, b, c, d;for (int i = 0; i < 2000000000; i++) {a = a + d;b = b + d;c = c + d;}An equivalent x86 assembly implementation is:0第14章 引言0// 提取索引的2位 bool x0[NUMBER_OF_SHARES],x1[NUMBER_OF_SHARES]; for ( int i = 0; i > 1) & 1; x1[i] =index[i] & 1; }0// 计算查找结果 bool r0[NUMBER_OF_SHARES],r1[NUMBER_OF_SHARES]; // r1 = ˜x1 r1[0] = ˜x1[0]; for ( int i = 1;i < NUMBER_OF_SHARES; i++) { r1[i] = x1[i]; } // r0 = ˜(x0 ˆ x1)r0[0
我的内容管理
展开
