关注网络安全
和行业未来

Go语言使用SIDH算法处理TLS1.3量子威胁

本文由Henry de Valence发布自cloudflare博客,详细介绍了如何使用SIDH算法处理TLS1.3量子威胁。相关开源算法代码:p751sidh

如今,大多数加密的目的是在敌对方巨大的计算能力的威胁下保证安全。这意味着要估算特定计算所需的工作量(例如对一个数字进行分解因子,或者找到一个离散的对数),并根据我们对破坏系统需要多少工作量的最佳估计来选择加密参数。

如果有可能建立一个大规模的量子计算机,那么会有很多问题不再难以解决,而我们原本是依靠这些问题的解决难度才确保安全的。虽然还不知道大型量子计算机的产生是否可能(这篇文章很好地概述了这一问题),但由于人们对发展量子对抗(或后量子)加密机制有广泛兴趣,这仍然是个足够大的风险。该加密机制应能在目前我们所拥有的普通计算机上运行,并在对抗可能出现的量子计算机时仍然能够确保安全。

在Cloudflare上,我们使用TLS来为客户的网站服务,并在后台为内部的数据中心之间的通信进行服务。在TLS环境下,我们希望在客户端和服务器之间创建安全连接。这里主要有三个加密方面的问题:

1、真实性:服务器需要向客户端证明它是真正的服务器(作为可选项,客户端可以向服务器证明它是真正的客户端);

2、关键一致:服务器和客户端需要在一个不安全的连接上达成一致,临时共享一个只有它们双方知道的密码;

3、对称加密:服务器和客户端需要使用他们的共享密码来加密他们想要通过安全连接发送的数据。

真实性可以保护网络不受主动攻击,但由于人们还不认为量子计算机存在,所以主要的风险是一种追溯性攻击:例如,一个国家层面的对手(比如,简单地说,NSA)可以记录加密的通信,等待建立量子计算机,然后尝试解密过去的通信。此外,量子算法似乎看起来只对对称加密提供了一个很小的加速,因此要解决的“关键”问题是第二个问题,即量子对抗密钥的一致。

这是一个活跃的研究领域,既包括新加密系统的设计,也包括它们的实现和部署。例如,去年,谷歌在Chrome浏览器上做了一个基于格的密钥交换的实验。基于格的加密系统是一种非常有前途的量子对抗算法。它们的安全性依赖于经过良好研究的计算问题,而且它们的计算效率很高。但是,它们的密钥很大,并且需要进行额外的通信(这就使得像TLS这样的协议需要额外的往返通信)。

另一个加密系统的家族是超奇异同源系统,特别是超奇异同源Diffie-Hellman(SIDH)算法。与基于格的系统相比,它们依赖于更加奇特的计算问题,而且计算成本更高。但是,它们的密钥要小得多,而且不需要额外的通信:SIDH完全适合于TLS 1.3的密钥一致机制。

TLS 1.3是TLS协议的最新版本。今年夏天,我一直在Cloudflare公司进行一项试验,这个试验是关于TLS 1.3协议的量子对抗版本的,它使用了X25519和超奇异同源Diffie-Hellman(SIDH)的混合密钥一致机制。为了实现这一点,我在Go(作为Cloudflare的tls-tris的一部分)中实现了一个TLS 1.3客户端,在amd64体系结构中实现了SIDH,并将SIDH实现与TLS 1.3密钥一致机制结合在一起,以执行一种量子对抗的TLS 1.3握手。这扩展了此前微软研究院在基于SIDH的TLS 1.2密钥交换方面的研究工作,下面我们将讨论微软的这项研究。

TLS 1.3中的Diffie-Hellman密钥一致机制

在TLS协议的最新版本TLS 1.3中,密钥一致机制(见第二部分)与身份验证机制(见第一部分)被区分得很清楚。而TLS 1.3通常通过一个椭圆曲线组使用“Diffie-Hellman”实现密钥一致性。在深入探讨量子对抗的版本之前,让我们先来回顾一下Diffie-Hellman(DH)是如何工作的,特别是在TLS 1.3的环境下它是如何工作的。

在Diffie-Hellman中,我们有通信的双方,爱丽丝和鲍勃,希望建立一个共同的密码。他们修复了主序p的一个阿贝尔群G,其书面写法是,G(基点)的一个生成器P。然后,爱丽丝在[0,p]区间内选择一个完全随机的整数a。这就确定了一个乘以a的映射,通常表示为[a] : G -> G。爱丽丝计算[a]P,即在她的地图下的基点的图像,然后把它发送给鲍勃。类似地,鲍勃在 [0,p]区间内中选择一个随机的整数b,确定映射[b],计算[b] p,并将其发送给爱丽丝。爱丽丝和鲍勃同意共享密码[ab] P,爱丽丝通过计算[a]([b]P)得到它,而鲍勃计算[b]([a]P):

DH diagram

(这里我用映射来描述这个过程,以便于稍后展示与SIDH的相似之处)。

在TLS 1.3环境下,它是这样工作的。客户端通过发送TLS的客户端问候信息ClientHello消息来发起连接,该消息包含由客户端支持的DH组列表(包含在其他数据中),以及这些组的一部分或全部的“密钥共享”(即:[a]P的值)。

服务器选择服务器和客户端双方都支持的一个DH组。在好的情况下,服务器会选择一个客户端提供密钥共享的组,然后将一个包含服务器密钥共享的服务器问候信息ServerHello发送回去。从这一刻开始,客户端和服务器之间的所有握手消息,例如证书、扩展等,都使用来源于密钥共享的的“握手密码”进行加密。(在不好的情况下,客户端没有提供可接受的密钥共享,服务器会请求客户机重试,并强制进行额外的往返通信)。

应用程序数据将在稍后通过来源于握手密码的一个密钥进行加密,其它数据也是如此,因此应用程序数据的安全性取决于密钥一致机制的安全性。然而,TLS中所有现有的DH组都很容易受到量子算法的攻击。

超奇异同源Diffie-Hellman算法

David Jao和Luca De Feo在2011年提出的SIDH是一项相对较晚的提议,即使用椭圆曲线来建立一个“量子对抗”的Diffie-Hellman方案。

粗略地说,SIDH在一个相关的“同源的”椭圆曲线家族中,而不是在一个椭圆曲线群中工作。

同源性是一个椭圆曲线的映射phi : E_1 -> E_2,它将源曲线E_1的标识元素发送到目标曲线E_2的标识。结果是,对于每一个映射phi: E_1 -> E_2,都有一个对应的映射psi: E_2 -> E_1,所以我们可以说,如果两条曲线由一个映射连接起来,那么可以说它们是同源的。

现在我们可以考虑一个同源图,它的边是同源,它的顶点是椭圆曲线。爱丽丝和鲍勃不选择乘以n映射的密码来沿着椭圆曲线内部移动,而是选择同源密码来沿着一个同源曲线族的内部来移动(例如:他们选择一条随机路径,穿过同源图),系统的安全性与在任意曲线之间计算同源的难度有关。

结果示意图稍微复杂一些,但在结构上与上面的图相似:

SIDH Diagram

这里到底发生了什么?

起始曲线E_0,以及点P_A、Q_A、P_B、Q_B,都是系统参数。

同源性是由它的核(同源映射到目标曲线的识别点的源曲线上的点的子群)确定的。为了选择一个同源密码phi_A,爱丽丝选择了标量密码m_A、n_A,这两者确定了一个点[m_A]P_A + [n_A]Q_A,该点产生了一个核的子群<[m_A]P_A + [n_A]Q_A>,因此确定了她的同源密码phi_A。爱丽丝在点P_B、Q_B上估算了phi_A,然后将E_A、phi_A(P_B)、phi_A(Q_B)发送给鲍勃,鲍勃进行相同的步骤,只是交换了A和B。

接下来,爱丽丝使用E_B、phi_B(P_A)、phi_B(Q_A)以核<[m_A]phi_B(P_A) + [n_A]phi_B(Q_A)>建立一个同源phi’_A,而鲍勃使用E_A、phi_A(P_B)、phi_A(Q_B)以核<[m_B]phi_A(P_B) + [n_B]phi_A(Q_B)>建立一个同源phi’_B。现在phi’_A映射到曲线E_AB上,而phi'_B映射到曲线E_BA上。曲线E_AB和E_BA是同构的。因为椭圆曲线是由一个叫做不变的j的数来分类的,而j(E_AB) = j(E_BA),所以这就是爱丽丝和鲍勃之间的共享密码。

我们可以在Luca De Feo、David Jao和Jérôme Plût的论文《SIDH的扩展》中找到这个过程的详细的技术说明(上面的示意图就是该论文的第一张图表)。而在Luca De Feo的这篇文章中可以找到关于飞船穿越超奇异时空的解释。瓷碗,Deirdre Connolly在2017年2月举行的Cloudflare密码学会议上发表了一段谈话。

2016年,Craig Costello、Patrick Longa和Michael Naehrig在微软研究院发表了一篇关于SIDH的高效算法的论文,将优化技术从高速ECC应用到最初的SIDH提案上。

他们还发布了用C语言和汇编语言编写的常数时间、优化的实现,以及OpenSSL的补丁,以创建用于TLS 1.2的SIDH密码套件。我的Go实现就是建立在他们的工作(包括算法和代码)基础之上,如下所述。

Go TLS中的SIDH密钥一致性

在p751sidh包中的SIDH实现由两个部分:一个包含SIDH功能的外部p751sidh包,和一个提供低端功能的内部p751toolbox包。

因为SIDH是在一个大的有限字段中实现的,所以字段的算法性能对协议的性能是至关重要的。不幸的是,这需要编写汇编语言,因为编写高性能的算法在Go中是不可能的——这根本不是该语言的设计目标(有几个原因,最值得注意的是,没有办法直接计算64位整数的128位乘积)。

该代码部分源自上面提到的微软研究院的研究工作。具体地说,字段的算法是从MSR汇编移植过来的,实现策略遵循它们的论文(我用AVX2做了一个字段算法的原型实现,但决定不使用它,因为它降低了可移植性、增加了计算能力的使用,只得到了相似的性能)。

最低级的字段算法的汇编语言代码面向固定大小的缓冲区的指针;这是用一个使用big.Int模块的Go API包装的。为了测试代码的行为是否正确,我使用Go的 testing/quick包来编写基于属性的测试,它生成随机的字段元素,并将不同操作的结果与使用big.Int进行相同操作的结果进行比较。

使用Go API实现了曲线和同源功能,并且与MSR实现相比,外部级别的SIDH功能达到了类似的性能。在粗略的基准测试中,Go实现看起来在MSR实现的2-6%之内。整个实现都是常数时间。

具体来说,在一台配备Skylake i7-6600u@2.6 GHz处理器的T460s计算机(不幸的是,联想计算机的BIOS并不允许禁用Turbo Boost功能)上,密钥的生成和共享密码的计算需要11-13毫秒。注意,与经典的Diffie-Hellman不同,爱丽丝和鲍勃的计算略有不同,所以他们有不同的时间。
BenchmarkAliceKeyGen                      11,709,778 ns/op

BenchmarkBobKeyGen                        13,073,380 ns/op

BenchmarkSharedSecretAlice                11,256,985 ns/op

BenchmarkSharedSecretBob                  12,984,817 ns/op

这比传统的ECDH或基于格的密钥一致性要昂贵得多。然而,从延迟的角度来看,这可能并不是那么糟糕。例如,12毫秒是巴黎和阿姆斯特丹之间的通信往返时间,因此一个需要额外通信的密钥一致性可以很容易地花费更长的时间,尽管计算的花费较低。

因为SIDH仍然是新事物且未经验证,所以TLS组合实现了一个混合密钥交换机制:它同时发送一个X25519密钥共享和一个SIDH密钥共享,同时执行X25519和SIDH共享密码计算,并将这两个共享密码都输入到TLS密钥派生机制中。这确保了即使在SIDH被破坏的情况下,密钥一致性至少与X25519一样安全。

TLS组件是作为tls-tris的一部分实现的,这是Go的crypto/tls包的Cloudflare分支,Go的crypto/tls包实现了TLS 1.3的一部分,即第18草案。由于tris不支持客户端功能,所以在研究SIDH之前,我实现了一个基本的TLS 1.3客户端。

混合密钥交换是使用组标识符0xFE24指定的。0xFE将其放置在私有使用的保留代码块0xFE00中,因为SIDH现在还远未实现标准化;之所以选择24这个数字,是因为它有很深的数学意义,而且与月光理论有联系。

整个的SIDH组合只需要不到100行代码。

不正确的Go汇编程序的危险

微软研究院的SIDH实现为字段算法提供了x64汇编程序,但Go的汇编程序使用了来自9号计划的定制语法,因此重新使用他们的汇编程序意味着将其一直到Go的汇编语言中。

当我第一次这样做时,代码产生了不正确的结果,即使所有的指令都是完全相同的。最终,我通过对生成的Go二进制代码进行反汇编,并与原来的汇编程序进行比较,找到了问题所在。

最初的汇编语句大致是这样的

  ...

  sbb    r10, rax

  movq   rax, 0

  sbb    rax, 0

  ...

sbb dst, src指令是“借位减”;这个指令读取进位标志CF,如果dst < src + CF,就设置dst = dst - (src + CF),CF=1。所以,如果第一个减法没有溢出,那么这段代码应该把rax寄存器设置为0,然后相反,就设置为1111...11(此值稍后将作为一个掩码用于计算)。但是,写成

...

  SBBQ    AX, R10

  MOVQ    $0, AX

  SBBQ    $0, AX

  ...

则不会有相同的结果。原因在于,Go汇编编译器会错误地把MOVQ $0, AX指令解释为xor eax, eax。这个指令的编码较短。不幸的是,它有不同的行为:它会清除进位标志,打断程序执行。

发生这种情况的原因是,在Go汇编程序中,MOV被声明为“伪指令”,这并不一定与字面上的mov指令相对应。不幸的是,没有规范说明什么指令是伪指令以及它们的行为是什么——在Go程序中,MOV被定义为删除的标志,但是这并没有在编译器之外记载。

为了解决这个问题,我们可以将文字字节放入指令流中。在本例中,我们写出

#define ZERO_AX_WITHOUT_CLOBBERING_FLAGS BYTE   $0xB8; BYTE $0; BYTE $0; BYTE $0; BYTE $0;

  ...

  SBBQ    AX, R10

  ZERO_AX_WITHOUT_CLOBBERING_FLAGS

  SBBQ    $0, AX

并将这些字节插入,以对mov eax, 0指令进行编码,该指令会保留进位标志。

源代码

这个实现仍然是实验性的,不应该在没有审核的情况下使用。SIDH的计算成本可能使它不适合生存期较短的客户端连接(至少在短期内是这样)。但是,它可能适合生存期较长的连接,例如跨数据中心连接,在这种连接中,握手的成本是在连接的长度上进行平摊的。

想要了解更多情况,可以在GitHub上找到SIDH实现,即p751sidh包。TLS组合可以在我的tls-tris的hdevalence/sidh分支中找到。

感谢Craig Costello、Diego Aranha、Deirdre Connolly、Nick Sullivan、Watson Ladd、Filippo Valsorda和George Tankersley的建议、评论和讨论。

评论 抢沙发