后量子加密算法的硬件实现综述

2022-01-04吴彦泽谢浩东乔云凯姚恩义

信息安全学报 2021年6期

关键词：密码学公钥密钥

曹元, 陆旭, 吴彦泽, 谢浩东, 乔云凯, 姚恩义, 陈帅, 叶靖

1 物联网工程学院河海大学常州中国 213000

2 微电子学院华南理工大学广州中国 511442

3人工智能与数字经济广东省实验室(广州) 广州中国 511442

4 磐石安全实验室常州中国 213000

5 计算机体系结构国家重点实验室中国科学院计算技术研究所北京中国 100190

1 介绍

密码学是研究与信息安全相关的数学技术科学。它可以保证通信的机密性、数据的完整性、认证实体和数据源[1]。其密码体制可分为对称密码与非对称密码, 非对称密码也称公钥密码。现有的密码体制大多基于RSA (Rivest-Shamir-Adleman)、ECC (Elliptic Curve Cryptography)等公钥密码体制, 在信息安全系统中实现密钥交换、数字签名和身份认证等, 有其独特的优势, 其安全性分别依赖于解决整数分解问题(Integer Factorization Problem, IFP)和离散对数问题(Discrete Logarithm Problem, DLP)的难度[2]。

然而, 基于量子计算机特殊的计算能力, Shor等人[3]给出了基于模幂运算的量子求阶算法: 一个用于整数分解和离散对数计算的多项式时间算法, 依赖于合适的能用量子计算机实现的量子傅里叶变换, 由此产生计算机处理能力爆炸性增长, 可成功解决整数分解和离散对数等困难问题, 而这些问题则是几大著名公钥体制RSA、ECC等的理论基础, 这意味着量子计算机可以对这几大著名的公钥体制形成致命的攻击, 即与目前的二进制计算机相比, 大大缩短了其密钥的破解时间[4]。另外, Grover等人[5]提出的量子搜索算法可对非结构化搜索问题进行二次加速, 尽管这种加速不会使加密技术过时, 但即使在对称加密的情况下, 它也会导致人们不得不采用更大的密钥以确保安全性。表1总结了量子计算机对密码算法的影响, 量子计算机的出现使RSA等公钥密码不再安全。

表1 量子计算机对密码算法的影响Table 1 The influence of quantum computer on cryptographic algorithms

这促使研究人员设计能够抵抗量子计算机攻击的密码: 后量子密码(Post Quantum Cryptography, PQC), 又称抗量子密码。所谓“后”, 是指在实用级量子计算机实现后, 现有的绝大多数公钥算法将会被足够大且稳定的量子计算机攻破, 而能够抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来。这些后量子密码算法有两个共同特点: 1)即使假设全规模量子计算机的可用性, 也没有已知的攻击能够破解这些密码系统; 2)所有的后量子密码算法都可以使用传统的计算平台, 基于标准半导体技术, 如微处理器(Central Processing Unit, CPU)和现场可编程逻辑门阵列(Field Programmable Gate Array,FPGA)。

为了实现在应用上的安全性、可靠性, 后量子密码学针对量子计算的特点, 结合传统密码学的优势, 设计了能够抵御量子计算机攻击的密码方案[6]。目前, 表现良好的PQC方案有基于哈希的、基于编码的、基于格的、基于多变量等。目前的研究尚不明确这些方案中哪一个会成为未来的标准。此外, 尽管大规模量子计算攻击仍在现代工程能力的范围之外, 但开发抵抗量子攻击的替代方案的工作已经在国内外积极的开展[7]。

本文的其余部分组织如下: 第2节概述了NIST PQC第2、3轮算法征集; 第3节介绍了4种后量子加密算法; 第4节提出了PQC算法在硬件的实现以及挑战; 第5节分析了PQC算法中的侧信道攻击, 最后给出了总结。

2 NIST后量子密码算法征集

2009年, 国家标准与技术研究所 (National Institute of Standards and Technology, NIST)启动了PQC计划来标准化一个或多个抗量子密码方案[8]。NIST是一个负责开发技术、标准和指导方针的非监管的政府机构, 以帮助联邦机构满足联邦信息安全现代化法案(Federal Information Security Modernization Act, FISMA)[9]的要求。NIST还负责根据FISMA制定联邦信息处理标准(Federal Information Processing Standards, FIPS)。

2015年4月, 美国国家标准与技术研究所(NIST)举办了“后量子世界的网络安全研讨会”, 讨论了后量子密码系统未来可能的标准化, 同年8月, 美国国家安全局(NSA)就“在不久的将来过渡到量子稳定算法”的计划发表了一份重要声明。2016年, NIST宣布了NIST PQC算法征集, 邀请来自世界各地的研究者提交候选抗量子密码学方案进行评估和最终标准化。NIST打算从中挑出多个算法[10], 将选出的候选算法进行标准化, 并将增强联邦信息处理标准(FIPS) 186-4[11]中指定的密码算法。

在PQC算法征集中, 经过筛选的算法将被指定为最终的候选算法。进入最终一轮的方案更有可能被考虑标准化, 而候补方案则是有一些方案被标准化的可能性很小。

提交的算法被正式分为两类, 公钥加密、密钥封装方案, 以及数字签名方案。除了上述分类之外, 候选算法又可以根据它们构造密码方案所依赖的底层数学难题类型不同分为多个类别, 这些类别是: 1)基于哈希的密码学; 2)基于编码的密码学; 3)基于格的密码学; 4)基于多变量的密码学。

2016年2月, NIST发布了《后量子密码学报告》, 强调信息安全系统需要部署后量子密码学[12]。NIST于2017年开始后量子密码学标准化, 有69种公钥加密、密钥封装和数字签名候选算法在2017年12月20日被接受为第一轮候选算法, 标志着NIST应对量子计算机发展的后量子密码标准化进程的第一轮行动的开始[13]。

NIST组织一场大型比赛对后量子密码算法进行选择, 这个类似竞争的过程被称为NIST PQC标准化过程[14]。问题是这些算法目前还很新, 我们不知道哪个(些)最终会赢得比赛, 所以还需要付出很多努力来了解这些后量子算法。想使用这些算法并不简单, 用新的算法替换不再安全的RSA等公钥密码算法, 在评估过程中需要考虑多方面的因素, 同时进行标准化。

PQC标准化过程是NIST对量子计算机发展进步的回应。这些机器利用量子力学原理来解决传统计算机难以解决的数学问题。如果大规模量子计算机建成, 它们将能够破解目前由NIST标准化的公钥密码系统[14]。

在NIST PQC标准化过程中评估算法的标准主要涉及3个方面: 1)安全性; 2)成本和性能; 3)算法和实现特征。具体如下:

1) 安全性: 与过去的AES[15]和SHA-3[16]竞赛一样, 安全性是评估候选后量子算法时最重要的因素。NIST目前的密码标准已经被广泛使用, 如传输层安全协议(Transport Layer Security, TLS)、安全外壳协议(Secure Shell, SSH)、网络密钥交换协议(Internet Key Exchange, IKE)、互联网安全协议(Internet Protocol Security, IPsec)和域名系统安全扩展协议(Domain Name System Security Extensions, DNSSEC)等互联网协议。需要用新的标准来为这些应用程序提供安全性保证。NIST认识到在评估后量子候选算法的安全强度时存在重大的不确定性, 因此定义了5种安全类别, 以便更好地比较提交算法的安全强度等级。NIST还提到了其他可取的安全特性, 如完美的前向保密, 抗侧信道和多密钥攻击, 以及抗误用等。

2) 成本和性能: 将成本确定为评估候选算法时的第二重要标准。在这种情况下, 成本包括计算效率和内存需求。这包括:

• 公钥、密文和签名的大小。

• 密钥生成的计算效率, 以及公钥和私钥操作的计算效率。

• 解密失败的概率。

计算效率本质上是指算法的速度。NIST希望候选算法能够提供与目前标准化的公钥密码算法相当或更好的性能。内存要求是指软件实现的代码大小和随机存取内存(Random Access Memory, RAM)的要求, 以及硬件实现的门数。

所有提交者需提供NIST参考平台的性能评估, NIST参考平台是Intel x64, 运行Windows或Linux, 并支持GNU Compiler Collection (GCC) 编译器。NIST在参考平台上进行了初步的效率分析, 但也邀请公众在其他平台上进行类似的测试。

3) 算法与实现特征: NIST PQC标准化过程中收到了许多新的、有趣的候选算法, 它们具有当前NIST标准化公钥算法所没有的独特特征。具有更大灵活性的候选算法可能优先于其他算法。这包括能够在各种平台上高效运行以及使用并行性或指令集扩展来实现更高性能的算法。此外, 简单优秀的设计能更好地反映了设计团队的理解和信心, 鼓励进一步分析。最后, NIST将考虑任何可能阻碍和促进算法实现的因素。

2019年1月, 基于对其安全性、性能、密钥长度等特征的评估、分析, 26种算法进入第2轮进一步分析[17]。17个公钥加密、密钥封装算法, 9个数字签名算法如表2所示。2020年7月, 有15个进入第3轮, 其中7个是候选算法, 8个是备选算法[18], 如表2所示。图1显示了第3轮候选算法及其在各种算法类别中的位置。在第3轮决赛中, 基于格的方案是最常见的。因为格密码的数学原理相似, 因此容易受到类似的攻击, 很可能最多会选择一个基于格的算法来标准化。基于格的方案由于其相对简单的结构和即使在最坏的情况下也可以提供很好的安全性而成为热门的候选方案。

图1 NIST PQC比赛第3轮决赛算法按类别分组Figure 1 NIST PQC competition round 3 finals algorithm grouped by category

NIST预计再需要两年左右的时间对最终入选算法进行标准制定, 在2022—2024年间公布抗量子密码的标准化草案; 另一方面, 我国对于抗量子密码算法标准化的工作预计将于2022年左右展开, 并于2025年左右完成商业化。完成抗量子加密标准化进程后, 新的密码体系将替代现有的密码体系以应对量子计算机发展带来的威胁。这种可以抵御量子计算机攻击的密码体系将运用在SSL, TLS等现有通信安全协议上, 为保密信息、证明信息、软件升级、信息访问、签名等应用提供安全性、授权控制并保证信息的可鉴别性、完整性和不可否认性。

3 后量子加密算法概述

量子计算机是依靠量子级现象来运行的计算机, 而量子计算机中的比特, 我们称之为量子比特, 它是一个最简单的量子系统, 一个量子比特不仅可以用0和1来表示, 而且还可以处于0和1的叠加状态[19], 从计算的方式来看, 比经典计算机更为复杂。这些计算机将能够做很多有趣的事情, 帮助我们解决某些难以用经典计算机解决的问题, 但从安全的角度来看, 它们有一个“副作用”, 我们每次建立TLS 连接[20]时都会在客户端和服务器之间的网络上使用现有的密码学, 以保护用于签名的数据等, 对于信息安全来说非常重要。但是如果我们建造一个位数足够多的量子计算机, 可以在可接受时间内破解现有的密码体制[21]。因此, 我们需要准备好应对当大型量子计算机可以构建后带来的副作用, 需要更换现有的密码学, 特别是公钥密码学。

公钥密码学在电子商务中用于身份验证(签名)和安全通信(加密)。正如前文所提到的大规模量子计算机的构建将使许多此类公钥密码系统变得不安全, 特别是那些安全性是基于整数分解问题难度或基于离散对数问题难度的公钥密码系统。相比之下, 对对称密钥系统的影响不会那么巨大[22]。因此, 对于那些被认为能够抵抗来自量子计算机的攻击算法的研究, 主要集中在基于非对称加密的公钥密码算法上。我们简要概述目前后量子密码学的主要实现方法[23]。

3.1 基于哈希(Hash)的公钥密码学

图2给出了基于哈希的签名方案的分类, 表3给出了图2涉及的缩略语及其解释, 基于哈希的签名方案的安全性来源于Hash函数的安全性[25], 典型方案为默克尔(Merkle)签名方案, 由一次性签名方案OTS (One Time Signature)[26]演变而来的, 并结合了Merkle的哈希树认证机制, 共同构造出一个完全的二叉树来实现数字签名。哈希树的根是公钥, 一次性的认证私钥是树中的叶子节点。

表3 基于哈希签名方案缩略语及其解释Table 3 Abbreviations and explanations of Hash-based signature schemes

图2 基于哈希签名方案的分类Figure 2 Classification of Hash-based signature schemes

一次签名方案主要优势在于: 每对公私钥只能用于一条消息的签名。防止了重放攻击(Replay Attack), 即如果使用了同一个公私密钥对来签署两个不同的消息, 那么消息很容易被攻击者伪造。

Merkle哈希树是一种典型的二叉树结构, 包括一个根节点、一组中间节点和一组叶节点。为了获得唯一一个根节点, 许多的叶节点使用二进制Merkle树将其简化[24]。在二叉树的每一层上, 相邻的节点成对碰撞, 形成上一层的一个节点, 以此类推, 最终形成公钥的一个根节点。XMSS是扩展的Merkle签名方案, 图3介绍了XMSS树的结构。

图3 XMSS树结构[24]Figure 3 XMSS tree structure[24]

因为该体制的安全性不依赖于大整数分解和离散对数这两类困难问题, 所以被认为是可以抵抗量子密码分析。其优点是签名和验证效率高, 缺点为签名和密钥较长, 产生密钥的代价较大。目前面临的挑战是有状态性和参数优化。

3.2 基于编码的公钥密码学

基于编码理论构造的公钥体制, 其理论基础是解码问题的困难性, 换句话说就是在已知生成矩阵的情况下, 在码空间寻找一个码字与已知码的Hamming距离最短。如果已知码为0则问题就是最小权重问题。它的任意线性码的译码问题是NP完全问题[27]。

表4给出了基于编码的家族以及何时被提出和破坏的, 从本质上来说, 基于编码的密码系统有两种类型。第一个系统是McEliece密码系统, 第二个系统是Niederreiter密码系统。McEliece密码系统是Robert J. McEliece在1978年提出的, 利用二进制Goppa代码开发的基于编码的公钥密码系统[28]。Goppa码成为McEliece密码系统的主要选择有以下两个原因。其一, Goppa码采用了快速多项式时间解码算法。其二, Goppa码“易于生成但很难找到”: 有限域 (2)m F上的任何不可约多项式都可以用来创建Goppa码, 但是Goppa码的生成矩阵几乎是随机的。

表4 基于编码的家族Table 4 Code-based family

下面简单描述McEliece密码系统的加密解密过程[29], 假设通信双方分别为Alice和Bob。

第一步: 密钥对生成

(1) Alice选择一个能够纠正t个错误的二进制[n, k] Goppa码的生成器矩阵G, 其大小为k×n。

(2) 再选择一个kk× 矩阵S(可逆矩阵), 还有一个nn× 矩阵P(可置换阵, 这意味着P的每行每列都只有一个1)。

(3) 定义 1G= × ×SGP。

(4) 她公开了她的公钥G1。

(5) 她保留了自己的私钥 (S,G,P)。

第二步: 假设Bob必须向Alice发送加密消息

(1) Bob有一个长度为k的明文m。

(2) 他加载Alice的公钥G1。

(3) 他生成一个Hamming权重为t的n位向量e。

(4) Bob计算密文c=mG1+e并发送给Alice。

第三步: 假设Alice收到了密文c, 她将收到的密文解密

(1) Alice使用她的私钥计算P–1。

(2) 计算

(3) 最后, Alice使用Goppa码的解码算法(Patterson算法)来确定m值。

尽管该算法运行速度非常快, 但是大多数基于编码的方案密钥量大, 签名效率低[30]。因此, 如何降低密钥量, 提高效率成为该算法研究领域的热点问题。

3.3 基于格的公钥密码学

格公钥密码体制是在大维数的格上, 基于最短向量问题SVP (Shortest Vector Problem)和最近向量问题CVP (Closest Vector Problem)等数学难题而构造的公钥密码体制。SVP问题是指在大维数格中寻找长度最短的非零向量, 而CVP是指在大维数格中寻找和固定向量距离最近的向量, 这两个问题都是NP难问题[31]。

目前基于格的公钥实现分为三类[32]: 一类是对NTRU以及其改进算法的实现研究; 二是对基于 LWE (Learning With Errors) 问题或者其变形问题的格公钥密码体制方案的实现研究, LWE问题的高效和简洁性使得基于LWE问题的格公钥密码体制实现效率较高; 第三类是对基于格上特殊性质算法的实现研究。

基于格的算法的安全性依赖于求解格中问题的困难性[33]。在达到相同(甚至更高)的安全强度时, 基于格的算法的公私钥尺寸更小, 计算速度更快, 且能被用于构造多种密码学原语, 因此更适用于真实世界中的应用。缺点是参数往往较大。目前该领域的挑战为参数优化和提升效率。近年来, 基于LWE问题和RLWE (Ring-LWE) 问题的格密码学构造发展迅速, 被认为是最有希望被标准化的后量子加密技术路线之一。

3.4 基于多变量的公钥密码学

基于多变量的算法使用有限域上具有多个变量的二次多项式组构造加密、签名、密钥交换等算法。它的安全性来源于求解有限域上随机生成的多变量非线性多项式方程组。该问题被证明为非确定性多项式时间困难。目前没有已知的经典和量子算法可以快速求解有限域上的多变量方程组[34]。

多变量密码系统的研究, 最早是在1988年Matsumoto和Imai提出了著名的MI密码体制, 这是多变量公钥密码史上的一个里程碑, MI密码体制的提出开启了多变量公钥密码研究和发展的大门。Patarin在1995年提出的线性化方程攻破了MI密码体制并在1996年提出了隐藏域方程(Hidden Field Equation, HFE)方案。 Kipnis和 Shamir 分析证明了HFE方案的不安全性。Patarin又在1997年利用线性化方程攻击的思想, 设计了OV (Oil-Vinegar) 签名算法, Kipnis和 Shamir 进一步改进该方案提出了UOV ( Unbalance Oil Vinegar)方案。

基于多变量的方案效率较高, 但缺点是公钥量大, 并且安全性不稳定。目前该方案的挑战为可证明的密码安全体制以及降低密钥量。

表5总结了后量子密码学的研究方向对比。以上这些算法, 当参数选择恰当, 目前没有已知的经典和量子算法可以快速求解这些问题。事实上, 这些算法的安全性都依赖于有没有可以快速求解其底层数学问题或直接对算法本身的高效攻击算法, 这也正是量子计算机对于现有公钥密码算法存在很大威胁的原因。

表5 后量子密码学的研究方向对比Table 5 Comparison of research directions of post-quantum cryptography

4 PQC算法在硬件上实现及挑战

PQC算法在硬件实现上的挑战一是算法规范的数学复杂性, 这些规范通常是由密码学家编写的, 关注的重点是其安全性而非实现的效率。理解这些规范需要具备以下能力: 扎实的数论、抽象代数、编码理论和相关学科的背景知识, 而工程方面的硬件工作者往往对这些充斥着复杂公式和高级数学运算的规范无法理解[35]。在标准化的进程中剩下的候选对象属于5个不同的类, 每个类又可以分为各个子类。例如基于格的候选方案分为结构化格(随机格)和非结构化格(理想格)。每个类甚至子类都需要不同的数学背景, 涉及不同的基本操作数。

二是在硬件实现上需要存储大型公钥、私钥和内部状态, 这可能会导致不能实现真正的轻量级, 而且会影响硬件实现的效率[36]。例如, 作为早期PQC标准采用的主要候选算法之一Classic McEliece, 其三个主要参数集的公钥大小分别超过1/4 MB、1/2 MB和1 MB, 其安全级别相当于各种AES变体。对于传统公钥密码而言, RSA的公钥大小为256~ 512 B(2048~4096位), ECC的公钥大小为32~64 B (256~512位)。NIST第2轮PQC候选算法属于基于非结构化格的子类有第二大的密钥大小集, 在4096~8192 B的范围内。

大型公钥可能会不利于物联网低面积低功耗的实现, 还会增加加密的总时间。而解密的失败, 会造成更多的时间消耗, 从而增加最坏和平均的解密时间。另一方面, 随机数被用于加密、签名生成和密钥封装。使用随机采样器可能需要访问真随机数生成器, 以及不同分布的随机值之间的转换。这类电路很少应用于其他数字系统, 可能需要从头开始开发。这些电路也很难验证, 并且可能是相当大的侧通道泄漏的来源[37]。

解决上述问题首先是对PQC硬件应用程序编程接口(Application Programming Interface, API )[38]的开发。这个新的硬件API旨在满足后量子密码系统的各种需求, 包括: 最低遵从标准、接口、通信协议和PQC核支持的时间特性。PQC核接口的总体思路如

图4所示。该接口由六大数据总线组成: 公共数据输入(Public Data Inputs, PDI), 私密数据输入(Secret Data Inputs, SDI), 随机数据输入(Random Data Inputs, RDI), 公共数据输出(Public Data Outputs, PDO), 私密数据输出(Secret Data Outputs , SDO)和外部内存输入/输出(External Memory Inputs/Outputs, MEM), 表6显示了公钥加密、数字签名和密钥封装机制所需的数据总线。

表6 PQC核数据总线Table 6 Data bus for PQC cores

图4 PQC接口Figure 4 PQC interface

这6根总线中的前5根伴随着相应的握手控制信号, 命名为valid 和 ready。valid信号表明数据已在源端就绪, 而ready信号表明目的地已准备好接收它们。

外部存储器输入/输出有一组不同的伴随端口。内存控制信号支持多种内存配置。mem_addr信号用于指定内存地址, mem_do和mem_di信号分别用于从内存发送和接收数据。可以通过使用多个mem_wr信号写入多个内存块。当一个状态码在PDO端口是可用的, status_ready信号是高电平。

有两种方法可以用来减少开发时间。第一种是软硬件协同设计, 二是使用高级综合(High Level Synthesis, HLS)[39]。PQC加密算法的硬件实现既可以通过传统RTL实现, 也可以通过基于HLS来实现[40]。HLS之所以被更多地使用, 一是因为验证被加速。通常可以使用软件验证工具来验证设计的行为, 该软件验证工具比RTL仿真工具更容易使用。此外, HLS工具的RTL输出可以使用原始的行为测试台进行验证, 因为该工具可以检查两个模型的结果是否相同。二是因为设计空间探索(Design Space Explorer, DSE)更快[40]。可以通过在HLS工具中进行选择来探索微体系结构, 这些选择几乎不需要修改代码。因此, 可以在数小时内探索几种转换, 例如流水线化和各种循环展开因子[41]。这是对RTL方法论的巨大改进, 在原RTL方法论上, 此类更改将需要对源代码进行重大修改。

为了提高设计数字硬件组件的效率, HLS被视为提高设计抽象水平的下一步方向。接下来简单描述基于HLS的PQC算法设计流程, 如图5。C代码设计是HLS设计流程的输入, 接下来, 我们对C代码执行HLS, 使用Xilinx Vivado HLS生成RTL。之后进行预期值与输出的对比来决定是否需要优化, 如果需要优化, 则不断调整指令再次进行HLS, 如果不需要优化, 则输出最终的RTL。

图5 基于HLS的PQC算法设计过程Figure 5 HLS-based design exploration of PQC algorithms

将HLS应用于后量子密码加速器设计是在文献[40,42]中首次提出的, Basu等人研究的目的是提供一个基于硬件的NIST PQC加密算法(其中7种是密钥封装算法, 6种是数字签名算法)的比较, 这些算法在Xilinx Virtex-7 FPGA上实现, 使用高级C规范映射到FPGA和ASIC设计流程来找到功率、面积、速度和安全性(PASS)的最优点, 还开发了两种PQC算法: qTESLA和Crystals Dilithium的ASIC设计。这是第一个硬件基准测试, 并使用一个通用的评估框架来研究区域、性能和安全之间的权衡。[43]主要研究PQC算法的优化来提高性能, 利用HLS为PQC算法提供了面积优化和速度优化的解决方案。这些解决方案创建了高效和恒定时间的PQC设计保证了硬件的安全性, 防止了定时侧通道攻击。优化后的PQC算法提供了一种高效、安全的硬件实现。实验结果表明, 与传统RTL实现相比, 使用HLS生成Kyber512的面积和延迟分别减少了2倍和3倍。[44]对基于HLS对数论变换(Number Theoretic Transform, NTT)的设计方法进行了深入研究。NTT 是基于格的后量子密码系统的核心数学函数。NTT常被环型和模块型LWE PQC算法使用, 例如: Kyber和NewHope。通过使用Vivado HLS 工具展示了对 NTT 的快速而广泛的设计空间探索, 分析了优化配置的缺点和挑战, 与传统RTL的硬件设计相比, HLS提供了更低的设计成本。

对于任何资源受限的应用程序来说, 对PQC加密算法的高效实现是迫切需要的[45]。但是关于PQC标准候选硬件实现的出版物数量仍然相对较少, 由于假设和优化目标的不同, 报告的结果很难进行比较。因此, 对于在硬件平台上实现这些方案的最佳方法仍未有结论, 但目标是优化各个方面, 如最小面积、最大速度等。Nejatollahi等人在文献[46]中提出了基于格的加密算法实现的趋势、挑战和需求, 在此基础上进一步研究, 描述了基于格的密码在软件和硬件实现方面的挑战, 以及它们在身份验证、密钥交换和数字签名方面的应用, 使用软件、硬件、软件/硬件协同设计和数字信号处理(Digital Signal Processing, DSP)技术实现了基于格的密码方案[47]。Wang等人[48]提出了在Stratix V FPGA上实现经典McEliece, 介绍了基于二进制Goppa码的Niederreiter密码系统FPGA实现, 包括加密、解密和密钥生成模块。Karmakar等人[49]研究了SABER在ARM Cortex-M系列资源受限微控制器上的实现, 并将速度优化和内存优化的SABER实现与其他已报道的基于格的方案在ARM Cortex-M微控制器上的实现进行比较。Hülsing等人[50]在ARM CORTEX-M3处理器实现了无状态的哈希签名方案SPHINCS, 证明了在嵌入式微处理器上实现无状态的哈希签名方案是可行的。在[51]中, 现有的加密协处理器被重新用于Kyber KEM, 并与其他PKE或KEM方案在不同微控制器平台上的时钟周期比较。Ferozpuri等人[52]介绍了Rainbow的高速FPGA实现。该设计支持许多参数集, 这些参数集需要在GF(16)和GF(256)字段中进行操作。为了使基准测试更容易和更公平, 该设计遵循通用的PQC硬件API, 允许与其他后量子签名方案进行比较。这个设计是开源的, 来增加透明度和加速进一步的优化。Huang等人[53]在XilinxFPGA上实现CRYSTALS-Kyber算法的纯硬件实现, NTT模块采用了高效的并行和流水线计算。通过仿真和综合结果的分析, 发现该方法具有频率高、执行时间短的优点。该方案在Xilinx Artix-7和Virtex-7 FPGA上分别工作在155 MHz和192 MHz频率。与嵌入式Cortex-M4处理器相比, 硬件实现加密、解密的最大加速可达129倍。Tian等人[54]提出了一种基于超低延迟乘法器、加法器和减法器的SIKE算法的快速FPGA实现。使用Verilog语言编写代码, 并将其集成到SIKE库中。在Xilinx Virtex-7 FPGA上的实现结果表明, 对于SIKEp751, 该设计成本仅为9.3 ms, 频率为155.8 MHz, 比最先进的速度快2倍, 并实现了现有工作中最好的面积优化。特别是, 模块化乘法器只需要16个时钟周期, 将延迟减少了近一个数量级。

大多数PQC算法还处在审查阶段, 大家的工作重点都在算法层面的优化以及安全性(如抗测信道攻击)的评估, 在这基础上硬件实现相对较少。目前只有少量PQC方案(LMS、XMSS)已经被NIST标准化并开源了相关代码, 所以硬件实现与优化也更多集中在这一方向。在对XMSS研究的初始阶段, XMSS计算的加速主要是通过指令集架构的软件优化来实现的[55-57]。通常, 它们的性能往往取决于CPU的性能。设计[24,45,58]通过构造专用硬件加速器的方式加速XMSS计算。在2018年, Wang等人[24]提出了软硬协同的工作架构, 用于在RISC-V嵌入式处理器上高效实现XMSS, 其中最密集的SHA-256操作被放到几个硬件优化特定XMSS的SHA-256加速器上来加速计算。Prashanthet等人[58]将流水线思想应用到SHA256硬件加速器中, 使得SHA256具有更快的工作频率。他们在文中列出了SHA256以及pipe-SH256在FPGA和ASIC下各自的功耗、速度以及面积等性能, 为硬件进一步实现与优化提供了参考。这些设计极大的加速了XMSS计算速度, 并将其应用范围扩大到了资源受限的嵌入式设备, 然而还是无法满足在个别应用领域的需求, 如汽车芯片通信中的验签速度。文献[59]是对XMSS的全硬件实现, 包括了密钥生成、签名生成和签名验证三个部分。该设计完全还原了XMSS计算过程, 在28 nm 的Xilinx XC7A200T-2FBG676I FPGA芯片上进行了综合、验证和物理实现, 并在Xilinx Artix-7系列评估板上进行测试。FPGA平台上的评估结果表明, 作者的实现将密钥生成和签名生成的速度分别提高了20%和50%左右, 而且也优于文献[45]中FPGA中签名验证最快的硬件实现。与XMSS相比, 在相同的安全级别下, LMS需要进行更多的计算。密钥生成是LMS中最耗时的过程, 大约是平均时间的一半[60]。因此, 加速密钥生成过程可以有效地提高全部实现过程的速度。Song等人[61]提出了一种高效的密钥生成硬件加速器。该体系结构经过精心设计, 具有可扩展性, 可以支持所有的参数集。设计并行性来获得低延迟。作者使用Verilog语言编写代码, 并在Xilinx Zynq UltraScale+ FPGA上实现。实验结果表明, 与在Intel(R) Core(TM) i7-6850K 3.60GHz CPU上启用线程的优化软件实现相比, 该设计在不同参数配置下实现了55~2091倍的加速。

5 PQC算法中的侧信道攻击分析

后量子密码通过数学理论保证了其算法的安全性, 但是由于其在具体实现和应用中易受到侧信道攻击而对安全性和性能有着不可忽视的影响, 因此需要对侧信道攻击进行分析, 从而进行防御。侧信道攻击可以通过来自目标设备泄露的这些信息(在执行密码算法时所用的时间、消耗的能量或者发射的电磁波等)来提取密码设备的密钥。这些可能源于设备的时间或功率轨迹, 或者是设备产生的错误输出。典型的侧信道攻击方法包括冷启动攻击、故障攻击、定时攻击和功率分析等[62]。

冷启动攻击(Cold Boot Attack, CBA)[63]是一种新型的旁路攻击(Side Channel Attack)。PQC方案也被证明容易受到冷启动攻击。在这种攻击中, 攻击者针对动态随机存储器(Dynamic Random Access Memory, DRAM)可以使用液氮或压缩空气冷冻来减缓其信息衰减的速度。利用冷启动攻击, 攻击者可以对其进行物理访问正在运行的计算机执行冷启动操作以绕过其软硬件防护机制, 获取正在运行的计算机的内存快照, 并进一步从快照中提取出密钥等敏感信息。文献[64]演示了一种针对NTT的冷启动攻击, 文中提出两种编码方式, 第一种是将多项式系数直接存储在内存中, 该方式分析证实在非常低的位翻转率下容易受到冷启动攻击。第二种编码是在存储密钥之前执行NTT, 对Kyber 参数的冷启动攻击的需要操作243次, 提高了实现的效率。

时间攻击(Timing Attack, TA)[65]: 是通过分析在不同的输入上处理密码算法所需的时间不同, 并使用这些数据恢复密钥的信息来完成的, 时间攻击是另一种提取密钥信息的常见方法。针对这种攻击的主要对策是在恒定时间内实现算法。然而, 这可能会给算法带来很大的开销。时间攻击已经被发现对许多PQC算法有效, 包括FrodoKEM, HQC和FALCON。

能量分析攻击(Power Analysis Attack, PA)[66]: 密码设备的功耗可以提供有关发生的操作和相关参数的大量信息, 通过这些功耗信息可以获取与功耗相关的操作和数据信息。简单能量分析攻击(Simple Power Analysis Attack, SPA)[67]是侧信道能量分析攻击中最简单的一种攻击。在大多数情况下, 这类攻击需要直接分析观察到的能量痕迹[68]。简单一点说, 就是把能量轨迹显示出来之后用眼睛“看”, 当然, 也有很多辅助看的方法, 比如模板碰撞[69]。简单能量分析攻击的优点是需要的能量轨迹少, 缺点是需要泄露比较明显, 对噪音的敏感性大。差分能量攻击(Differential Power Analysis Attack, DPA)[70]: 它需应用额外的分析技术, 如统计相关或设备处理和模板[71]。分析是在几个甚至数以千计的轨迹上执行的, 同时深入了解算法的内部工作原理。能量分析攻击比其他类型的侧信道攻击更广泛、更多样。差分能量攻击的优点是即使泄露较小, 也可以有效识别, 有天然的对噪音的过滤, 缺点是需要的能量轨迹很多。DPA的基本想法就是, 通过大量的能量轨迹计算能量轨迹和数据的依赖性。能量分析攻击比其他类型的侧信道攻击更广泛、更多样。

另一种用于从加密设备中提取机密信息的常见攻击方法是故障攻击(也称故障注入攻击)(Fault Attack, FA)[72]。这种攻击的操作方式是让攻击者在加密设备中诱发错误, 导致意外的操作泄露可能导致密钥恢复的密钥信息。

近年来, 一些后量子密码算法的侧信道攻击与防御的研究学者进行了相关的调研工作。在2016年, Bindel和Buchmann等人[73]分析了基于格的签名方案BLISS、ring-TESLA和GLP方案以及它们在故障攻击方面的实现, 考虑了多种不同类型(随机化、归零和跳过)的一阶故障攻击, 而为了提高签名方案的安全性, 针对发现的六种攻击又提出了相应的防御对策。在2017年, 文献[74]调查了在FHEW 和HElib 两个基于格的密码库中的定时攻击和故障攻击并针对定时攻击提出了一种利用填充来实现消息恒定时间加密的方法的防御对策。在2018年, Khalid和Rafferty等人[75]调查了基于格的加密技术中一个关键组件——错误采样器, 针对侧信道攻击的漏洞和相关对策, 给出了错误采样器建议以实现基于格的加密技术的实用性、安全性和未来的广泛部署。在2018年, 文献[76]调查了基于格的侧信道攻击(SCA)方面的研究情况, 包括入侵攻击和被动攻击并提出了防御的方案, 但是这些方案在多个实施平台上的成本、实用性和有效性仍未得到充分研究。同年, 文献[77]系统地探讨了R-LWE加密对故障攻击的抵御能力, 讨论这些攻击的实用性并且根据攻击点和手段的分析, 提出了加强R-LWE的防御对策。在2020年, Ravi等人[78]针对基于格的多种密码算法进行了选择密文攻击, 其主要攻击目标是纠错码, 在ARM Cortex-M4微控制器上运行的开源PQM4库中的进行了实验验证。该攻击可以在几分钟内完成所有目标方案的密钥恢复, 从而显示攻击的有效性。在2020年, Danner等人[79]描述了使用二进制不可约Goppa码和Niederreiter公钥密码系统解密算法的故障攻击, 随后又提出了两种防御对策, 一是通过检查解码后输出值的权重来发现故障注入, 二是给出检测故障攻击的另一种方法——重新加密输出。针对NIST一再强调SCA的重要性及对策, 表7给出了NIST PQC候选人的攻击总结。一直以来, 能够以最小代价抵抗侧信道攻击的方案受到欢迎, 最新的PQC总结文件(NISTIR 8309)中指出: “NIST希望在第三轮测试中看到更多更好的数据, 有更多的对时间攻击、能量分析攻击、故障攻击等侧信道攻击的防御对策。”

表7 对NIST PQC候选人的攻击总结Table 7 A summary of the attacks on NIST PQC candidates

针对不同的攻击以及不同应用应当考虑不同的防御对策。对于高速硬件和硬件/软件实现(用于高端服务器的加速器), 防止定时攻击可能就足够了, 因为潜在的攻击者不会对加速器进行物理访问。对于轻量级实现, 目标是受约束的环境和移动设备, 攻击者被假定在设备的常规操作期间易于物理访问设备。因此, 对电磁攻击的额外保护是可以预期的。而任何嵌入式软件实现, 特别是针对多个用户共享公共资源的平台, 可能需要防止缓存泄漏。

针对侧通道攻击的大多数防御对策都是特定于算法的, 但大多数PQC加密算法都尚未得到研究。它们的开发和实验验证可能需要相当长的时间, 包括大量修改和扩展实验框架。即使是保护高速和轻量级实现免受强大的定时攻击所必需的恒定时间实现, 对于许多PQC算法的开发也是非常重要的。

同样重要的是防止故障攻击, 在这种攻击中, 攻击者在硬件实现的特定单元或特定计算阶段引发故障。攻击者对故障的确切性质、位置(时间和空间)和结果的控制越强, 就越难防范这些攻击。