端对端加密通讯协议Signal protocol

2019 - 04 - 25

Posted by 靠谱华

Signal protocol是真正的端到端的通讯加密协议，号称是世界上最安全的通讯协议，任何第三方包括服务器都无法查看通讯内容，热门应用facebook messenger，whatsapp，singal app都采用的此协议。

signal protocol可应用在双方通讯，群组通讯中，能保证传输的消息，图片，音频，视频等文件的加密传输。即使某个消息的密钥泄露，黑客也无法解密以前的消息和之后的消息，所以signal protocol能提供前向安全和后向安全。

名词注解

FS 前向保密: 长期使用的主密钥泄漏不会导致过去的会话密钥泄漏

HMAC 散列消息认证码: 通过共享密钥和原始信息生成摘要，验证消息完整性以及源身份

KDF 密钥派生函数: 通过一个密钥派生出一个或多个密钥，多密钥通过参数添加 salt 实现

HKDF 基于HMAC的密钥派生函数: HKDF(key, salt, info) => T(0), T(1), T(2), T(..)

迪菲-赫尔曼密钥交换协议

迪菲-赫尔曼密钥交换协议（Diffie–Hellman key exchange，后文简称DH协议）可以使双方无需预先沟通，在不安全的网络中即可确定一个“协商密钥”，这个密钥可以在后续的通讯中作为对称密钥来加密消息内容。这样避免了双方网上协商密钥带来的泄露风险。假设Alice和Bob要确定一个消息密钥，DH协议的原理可以用下面的公式来表示：

DH（A的私钥，B的公钥） = 协商密钥S = DH（B的私钥，A的公钥）

DH协议算法需要2个参数：自己的私钥和对方的公钥。对于Alice和Bob来说，他们只需知道对方的公钥，计算出的密钥S就是一样的。

DH协议的应用流程如下：

1) Alice和Bob各自创建符合DH协议的密钥对，假设Alice密钥对为（私钥A，公钥A），Bob密钥对为（私钥B，公钥B）；

2) 双方发送自己的公钥给对方，即使有黑客监听，他只能得到公钥A，公钥B；

3) Alice用自己的私钥和Bob的公钥计算消息密钥为S，即DH（私钥A，公钥B）=密钥S；

4) Bob用自己的私钥和Alice的公钥计算消息密钥也为S；即DH（私钥B，公钥A）=密钥S；

5) 双方同时确定了协商密钥S，后续可以通过S衍生出消息密钥，进行加密通讯。

6) 黑客只知道公钥A和公钥B，因为不知道任意一方的私钥，所以无法计算出密钥S。

综上可知，2个密钥对可以安全地创建一个“协商密钥”。在加密通讯中使用DH协议创建密钥，是非常安全的方法。

X3DH

X3DH协议在DH协议的基础上支持离线，提供前向保密和可否认加密。

Roles  
Alice 想通过加密向 Bob 发送一些初始数据，并建立一个可用于双向通信的共享密钥
Bob 希望允许像 Alice 这样的各方与他建立共享密钥并发送加密数据。但是，当 Alice 尝试执行此操作时，Bob 可能处于离线状态。为了实现这一点，Bob 与某个服务器建立了关系。
服务器 存储从 Alice 到 Bob 的消息，Bob 以后可以查看这些消息。服务器还允许 Bob 发送一些数据，服务器将传递给 Alice 等各方
密钥对  
身份密钥对（Identity Key Pair） 一个长期的符合 DH 协议的密钥对，用户注册时创建，与用户身份绑定
已签名的预共享密钥（Signed PreKey） 一个中期的符合 DH 协议的密钥对，用户注册时创建，由身份密钥签名，并定期进行轮换，此密钥可能是为了保护身份密钥不被泄露
一次性预共享密钥（One-Time PreKeys） 一次性使用的 Curve25519 密钥对队列，安装时生成，不足时补充
临时密钥（Ephemeral Key） 临时密钥

PreKey: 即需要在Alice 发送消息之前 传送公钥至服务器 故此命名.

X3DH 三个阶段：

  1. Bob 将他的身份密钥和预密钥发布到服务器。

  2. Alice 从服务器获取“预密钥包”，并使用它向 Bob 发送初始消息。
  3. Bob 接收并处理 Alice 的初始消息。

发送到服务器的均为公钥

本地计算自己的均为私钥 对方的均为公钥

1.Bob 预先发送公钥包至服务器, 其中包含如下:
  • Bob’s identity key IK
  • Bob’s signed prekey SPK
  • Bob’s prekey signature Sig(IK, Encode(SPK))
  • A set of Bob’s one-time prekeys (OPK1, OPK2, OPK3, …)

Bob 还需定时补充一致性密钥OPK, 和周期性更新Prekey,以支持前向保密

2.Alice 准备发消息

从服务器获取的密钥包:

  • Bob’s identity key IK
  • Bob’s signed prekey SPK
  • Bob’s prekey signature Sig(IK, Encode(SPK))
  • (Optionally) Bob’s one-time prekey OPK

创建一个临时密钥对（Ephemeral Key）即 EK

若没有OPK, 则SK生成方式如下:

    DH1 = DH(IKA, SPKB)
    DH2 = DH(EKA, IKB)
    DH3 = DH(EKA, SPKB)
    SK = KDF(DH1 || DH2 || DH3)
    注:‘||‘ 代表连接符，比如 456||123=456123

若有OPK 则SK生成方式如下:

    DH4 = DH(EKA, OPKB)
    SK = KDF(DH1 || DH2 || DH3 || DH4)

DH1 和 DH2 提供相互认证，DH3 和 DH4 提供前向保密

然后 生成包含双方信息的 Associated Data

 AD = Encode(IKA) || Encode(IKB)
3.Alice 发给 Bob信息

其中包含:

  • Alice’s identity key IK
  • Alice’s ephemeral key EK
  • 如上 SPKB 和 OPKB
  • 以 SK 加 Key, 以 AD 为 Salt 加密的密文
4:Bob 收到信息后 走如上 相同流程进行解密

由上可知，X3DH实际是复杂版的DH协议，解决了在不安全的网络里如何确定消息密钥的问题。但是仍然不够安全，你可以想一下，一旦消息密钥被破解，那么Alice和Bob所有的消息就都能解密了，泄露一个密钥，所有的聊天就会被破解，这代价有些太大了。

如果可以做到每发一条消息，就换一次消息密钥，那么即使某个消息密钥被破解了，黑客也只能解密这一条消息，其它消息仍然无法解密。这样简直就完美了，于是，棘轮算法就诞生了。

棘轮算法

棘轮（ratchet）是一种特殊齿轮，这种齿轮有个特点，就是只能向一个方向旋转，而不能倒转。下图就是一个棘轮

Signal Protocol采用棘轮算法来生成消息密钥，使用1个棘轮算法，能实现每条消息使用不同的密钥，即使一条消息的密钥被破解了，只能推算后面消息的密钥，而不能向前推算之前消息的密钥，我们称之为前向安全。

如果再加上一个棘轮算法，就可以再前向安全的基础上保障后向安全，即一条消息的密钥被破解，之前和之后的消息密钥都无法推算，这种算法被称为“双棘轮算法”

Signal Protocol在双方通讯中采用的双棘轮算法是“KDF链棘轮”+“DH棘轮”。以保证消息的前向安全和后向安全。

KDF链棘轮

KDF是一种密钥导出函数，通过附加一些数据（数据被称为“盐”，附加数据又称“加盐”），将原始密钥导出新的密钥，提高原始密钥的保密性。公式表达为

KDF (原密钥，盐) = 导出密钥

KDF算法可用于更安全地保存用户密码，普通的密码管理方式是服务器保存用户密码的哈希值，以避免服务器被攻击后黑客拿到用户密码原文，但是一些简单密码的哈希值仍然可以通过少量的碰撞破解出来，比如123456的哈希值就很容易被碰撞出来。更加安全的做法是在用户哈希值附加其它信息（比如用户注册时间，用户住址等等），通过KDF算法导出，得出的密钥具有非常强的随机性，就很难被碰撞出来。比如原始密码是123456的哈希值为”abcdef”，使用KDF算法得出最终密钥

KDF（abcdef，用户注册时间）=最终密钥

服务器只保存最终密钥。这样的密码管理方式的好处是，不管用户设置的密码多么简单，服务器保存的密钥都是非常随机的，很难被碰撞出来。

“KDF链棘轮”就是运用KDF算法，设计出一种密钥不断变化的效果，的流程如下：

第一步里，将初始密钥使用KDF算法导出新的密钥，新的密钥被切成2部分，前半部分作为下一次KDF计算的输入，后半部分作为消息密钥。每迭代一次（也可以说 棘轮步进一次），就会生成新的消息密钥。

假设每发一条消息，就棘轮步进一次，那么每条消息的密钥都会不同，而且由于KDF算法的单向性，通过这条消息的密钥无法倒推出上一条消息密钥的。这就保证了密钥的前向安全。

但是这种设计不能保证后向安全，黑客一旦破解了某条密钥，并掌握了盐的内容，那么它就可以按照这种算法计算出以后所有的消息密钥。

所以，为了保证后向安全，就要设计一种算法，使每次迭代时引入的盐是随机的，从而保证每次的消息密钥是不可以向后推算的。Signal Protocol 通过增加“DH棘轮”来保证盐的随机性。

DH棘轮算法

“DH棘轮”算法能保证每次计算引入的盐的随机性。由前文可知，2对密钥对可以通过DH协议生成一个安全的协商密钥，如果更换其中一个密钥对，新的协商密钥也会变化。DH棘轮算法就是通过轮流更换一个密钥对，每次生成不同的协商密钥，作为KDF棘轮算法的盐。每进行一个消息轮回，DH棘轮就更新一次临时密钥对，盐就被更新，KDF棘轮算法生成的消息密钥就具有后向安全性。

在前文提过，Alice要给Bob发送消息，根据X3DH协议，Alice要创建一个临时密钥对（EK-A），用于创建初始消息密钥S。其实这个临时密钥对还有另外一个用途，就是用于生成第一个盐。

继续接前文Alice和Bob通过X3DH协议建立了会话，Bob要给Alice回复消息，那么DH棘轮大概的流程如下：

由上图可知，每当收到对方的消息，并回应时，自己都要新生成一个随机DH密钥对，用以生成新的DH密钥作为新盐。从而保证了每次生成的消息密钥都是完全随机的。

更复杂一点的情况，在上例中第三回合，假如Bob没有回复Alice，Alice又发了一条消息给Bob，此时消息密钥是如何计算的呢？此时因为消息还没有进行一次轮回（就像打乒乓球，球发过去了，但是对方没打回来，不算一个回合），DH密钥对不进行更新，也就是说KDF棘轮引入的盐不变，但是消息密钥仍然是变化的。流程如下

这种设计可以保证在乱序接收消息时，接收方仍能正确解密消息。篇幅有限，具体原因就不详述了。

综上所述，双棘轮算法提供加密的前向和后向安全。同时我们也知道，在Signal Protocol中，与每一个人的单独对话，都会保存单独的KDF链棘轮和DH棘轮，所以相对于普通会话，加密对话会消耗更多的运算和存储空间。

Signal Protocol在群组聊天中的设计又有所不同，由于群聊的保密性要求相对低一些，只采用了KDF链棘轮以保障加密的前向安全。

Signal Protocol 的群组聊天设计

Signal Protocol的群组聊天是通过KDF棘轮算法+公钥签名来进行加密通讯的。通讯流程是这样的，

(1) 每个群组成员都要首先生成随机 32 字节的KDF链密钥(Chain Key)，用于生成消息密钥，以保障消息密钥的前向安全性，同时还要生成一个随机Curve25519 签名密钥对，用于消息签名。

(2) 每个群组成员用向其它成员单独加密发送链密钥(Chain Key)和签名公钥。此时每一个成员都拥有群内所有成员的链密钥和签名公钥。

(3) 当一名成员发送消息时，首先用KDF链棘轮算法生成的消息密钥加密消息，然后使用私钥签名，再将消息发给服务器，由服务器发送给其它成员。

(4) 其它成员收到加密消息后，首先使用发送人的签名公钥验证，验证成功后，使用相应的链密钥生成消息密钥，并用消息密钥解密。

(5) 当群组成员离开时，所有的群组成员都清除自己链密钥和签名公钥并重新生成，再次单独发给每一位成员。这样操作，离开的成员就无法查看群组内的消息了。

由上可知，一个人在不同的群组里，会生成不同的链密钥和签名密钥对，以保障群组之间的隔离。在每个群组中，每个成员还要存储其它成员的KDF链和签名公钥，如果群组成员过多，加解密运算量非常大，会影响发送和接收速度，同时密钥管理数据库也会非常大，读取效率也会降低。所以，群组聊天使用signal Protocol协议，群人数不宜太多。

以上介绍了Signal Protocol在双方通讯和群组聊天中的加密设计，可以看出，Signal Protocol是真正端到端加密通讯协议，提供了消息的前向安全和后向安全，是最安全的加密协议之一。

本文参考来源

[1] 《双棘轮算法》,烂磁头，https://blog.lancitou.net/double-ratchet-algorithm/

[2] 《【翻译】WhatsApp 加密概述（技术白皮书）》, p农民伯伯q, http://www.cnblogs.com/over140/p/8683171.html

[3] 《The X3DH Key Agreement Protocol》，Moxie Marlinspike, Trevor Perrin (editor)，https://www.signal.org/docs/specifications/x3dh/

[4] 《The Double Ratchet Algorithm》，Trevor Perrin (editor), Moxie Marlinspike，https://www.signal.org/docs/specifications/doubleratchet/

Table of Contents