市场上最安全的通信协议——Signal协议解析（上）之X3DH

X3DH协议

本文基本上是对Signal白皮书的翻译加上个人理解和最简代码示例。

1. 介绍

本文件描述了 "X3DH"（或 "扩展的三重 Diffie-Hellman"）密钥协议。X3DH在双方之间建立一个共享的秘密密钥，双方根据公开密钥相互验证。X3DH提供前向保密性和密码学上的不可否认性。

X3DH是为异步设置而设计的，其中一个用户（"Bob"）是离线的，但已经向服务器发布了一些信息。另一个用户（"Alice"）想使用该信息向Bob发送加密数据，并为未来的通信建立一个共享密匙。

2.准备工作

2.1. X3DH 参数

应用若要使用X3DH，则必须决定以下几个参数：
NameDefinitioncurveX25519 或 X448hash256或512位哈希函数 (比如 SHA-256 或 SHA-512)info用于识别应用的硬编码信息
例如，可以选择curve为X25519，hash为SHA-512，info为 "MyProtocol"。

应用程序必须另外定义一个编码函数Encode(PK)来将X25519或X448公钥PK编码为一个字节序列。推荐的编码包括一些单字节的常数来表示曲线的类型，然后是u坐标的小端序字节编码，如[1]中规定的那样。

2.2. 密码学符号

X3DH将使用以下符号。

• X || Y表示将X和Y字符串直接连起来，如X=”123”,Y=”456”，则X||Y表示“123456”。
• **DH(PK1, PK2)**表示一个字节序列，它是一个椭圆曲线Diffie-Hellman函数输出的共享密钥，该函数涉及由公钥PK1和PK2代表的密钥对。椭圆曲线Diffie-Hellman函数将是[1]中的X25519或X448函数，取决于curve参数。
• **Sig(PK, M)**代表一个字节序列，它是对字节序列M的XEdDSA签名，并用公钥PK进行验证，它是通过用PK相应的私钥签署M而产生的。XEdDSA的签名和验证功能在[2]中规定。
• **KDF(KM)**表示HKDF算法[3]的32个字节的输出、输入。
• HKDF input key material= F || KM，其中KM是一个包含密钥材料的输入字节序列，F是一个字节序列，如果曲线是X25519，则包含32个0xFF字节，如果曲线是X448，则包含57个0xFF字节。F用于XEdDSA[2]的加密域分离。HKDF salt = 一个零填充的字节序列，其长度等于哈希输出长度。HKDF info = 第2.1节中的信息参数。

2.3. 角色

X3DH协议涉及三个角色。Alice, Bob和Server。

Alice想用加密技术向Bob发送一些初始数据，并建立一个共享的秘密密钥，该密钥可用于双向通信。

Bob想让像Alice这样的另一方与他建立一个共享密钥，并发送加密数据。然而，当Alice试图这样做时，Bob可能是离线的。为了实现这一点，Bob与Server建立了关系。

该Server可以存储从Alice到Bob的信息，Bob随后可以检索这些信息。Server还让Bob发布一些数据，Server将把这些数据提供给Alice等另一方。对Server的信任程度在第4.7节中讨论。

在一些系统中，服务器的角色可能被划分为多个实体，但为了简单起见，我们假设只有一个服务器为Alice和Bob提供上述功能。

2.4.密钥

X3DH使用以下椭圆曲线公钥。
NameDefinitionIKAAlice的身份密钥EKAAlice的临时密钥IKBBob的身份密钥SPKBBob的预签名密钥OPKBBob的一次性预签名密钥
所有的公钥都有一个相应的私钥，但为了简化描述，我们将专注于公钥。

在X3DH协议运行中使用的公钥必须全部为X25519形式，或者全部为X448形式，这取决于曲线参数[1]。

每一方都有一个长期的身份公钥（Alice的IKA，Bob的IKB）。

Bob也有一个签名的预密钥SPKB，他将定期更改，还有一组一次性预密钥OPKB，它们分别用于一次X3DH协议的运行。("预密钥"之所以这样命名，是因为它们基本上是Bob在Alice开始协议运行之前向服务器发布的协议信息)。

在每个协议运行期间，Alice都会生成一个新的带有公钥EKA的临时密钥对。

在一次成功的协议运行后，Alice和Bob将共享一个32字节的秘密密钥SK。这个密钥可以在一些X3DH后的安全通信协议中使用，但要符合第4节中的安全考虑。

3. X3DH协议

3.1.概述

X3DH有三个阶段。

1. Bob将他的身份密钥和预密钥发布到一个服务器上。
2. Alice从服务器上获取一个 "预密钥包"，并使用它向Bob发送一个初始信息。
3. Bob收到并处理Alice的初始信息。

下面几节将解释这些阶段。

3.2. 发布公钥

Bob向服务器发布了一组椭圆曲线公钥，其中包含：

• Bob的身份密钥IKB
• Bob的签名预密钥SPKB
• Bob的预密钥签名 Sig(IKB, Encode(SPKB))
• 一组Bob的一次性预密钥（OPKB1, OPKB2, OPKB3, ...)

Bob只需要向服务器上传一次他的身份密钥。然而，Bob可以在其他时间上传新的一次性预密钥（例如，当服务器通知Bob，服务器的一次性预密钥存储量越来越少时）。

Bob也会在某个时间间隔（例如，每周一次，或每月一次）上传新的签名预密钥和预密钥签名。新的签名的预密钥和预密钥签名将取代以前的值。

在上传新的已签署的预密钥后，Bob可以在一段时间内保留与之前签名预密钥相对应的私钥，以处理使用它的信息在运输过程中被延迟的情况。最终，Bob应该删除这个私钥以保证前向保密性（一次性预密钥的私钥将在Bob收到使用它们的消息时被删除，见第3.4节）。

3.3. 发送初始消息

为了与Bob进行X3DH密钥协议，Alice联系服务器并获取一个包含以下数值的 "预密钥包"。

• Bob的身份密钥IKB
• Bob的已签名预密钥SPKB
• Bob的预密钥签名 Sig(IKB, Encode(SPKB))
• (可选择)Bob的一次性预密钥OPKB

如果Bob的一次性预密钥存在，服务器应该提供其中一个，然后删除它。如果服务器上所有Bob的一次性预密钥都已被删除，那么捆绑包将不包含一次性预密钥。

Alice验证预密钥的签名，如果验证失败，则终止协议。然后Alice用公钥EKA生成一个临时密钥对。

如果该捆绑物不包含一次性预密钥，她将计算：

DH1 = DH(IKA, SPKB) DH2 = DH(EKA, IKB) DH3 = DH(EKA, SPKB) SK = KDF(DH1 || DH2 || DH3)

如果捆绑包确实包含一个一次性预密钥，计算将被改为包括一个额外的DH：

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

下图显示了密钥之间的DH计算。请注意，DH1和DH2提供相互认证，而DH3和DH4提供前向保密性。

在计算完SK后，Alice删除了她的临时密钥和DH输出。

然后，Alice计算出一个"相关数据"字节序列AD，其中包含双方的身份信息：

AD = Encode(IKA) || Encode(IKB)

Alice可以选择向AD附加其他信息，如Alice和Bob的用户名、证书或其他识别信息。

然后，Alice向Bob发送一个初始消息，其中包含:

• Alice的身份密钥 IKA
• Alice的临时密钥 EKA
• 表明Alice使用了Bob的哪一个预置密钥的标识符
• 用一些AEAD加密方案[4]加密的初始密码文本，使用AD作为关联数据，并使用一个加密密钥，该密钥是SK或由SK键入的一些加密PRF的输出。

初始密码文本通常是一些后X3DH通信协议中的第一个消息。换句话说，这个密码文本通常有两个作用，作为一些后X3DH协议中的第一个信息，以及作为Alice的X3DH初始信息的一部分。

在发送之后，Alice可以继续在X3DH后协议中使用SK或由SK派生的密钥与Bob进行通信，但要遵守第4节中的安全考虑。

3.4. 接收初始信息

在收到Alice的初始消息后，Bob从消息中检索出Alice的身份密钥和临时密钥。Bob还加载了他的身份私钥，以及对应于Alice使用的任何签名预密钥和一次性预密钥（如果有的话）的私钥。

使用这些密钥，Bob重复上一节中的DH和KDF计算以得出SK，然后删除DH值。

然后，Bob使用IKA和IKB构建AD字节序列，如上节所述。最后，Bob试图用SK和AD来解密初始密码文本。如果初始密码文本解密失败，那么Bob就会终止协议并删除SK。

如果初始密码文本成功解密，那么对Bob来说，协议就完成了。Bob删除任何使用过的一次性预密钥的私钥，以实现前向保密。然后，Bob可以在X3DH后协议中继续使用SK或由SK派生的密钥与Alice进行通信，但要遵守第4节的安全考虑。

4. 安全考虑

4.1.认证

在X3DH密钥协议之前或之后，双方可以通过一些认证渠道比较他们的身份公钥IKA和IKB。例如，他们可以手动比较公钥的指纹，或通过扫描QR码。这样做的方法不在本文件的范围之内。

如果不进行认证，各方就不能得到关于他们与谁通信的加密保证。

4.2.协议重放

如果Alice的初始消息没有使用一次性预密钥，它可能被重放给Bob，他将接受它。这可能导致Bob认为Alice向他重复发送了相同的消息（或消息）。

为了缓解这种情况，后X3DH协议可能希望根据Bob的新的随机输入为Alice快速协商一个新的加密密钥。这就是基于Diffie-Hellman的棘轮协议的典型行为[5]。

Bob可以尝试其他的缓解措施，例如维护一个观察到的消息的黑名单，或更快地替换旧的签名预密钥。分析这些缓解措施已经超出了本文的范围。

4.3.重放和密钥重用

上一节讨论的重放的另一个后果是，一个成功重放的初始信息将导致Bob在不同的协议运行中得出相同的SK。

出于这个原因，任何后X3DH协议都必须在Bob发送加密数据之前将加密密钥随机化。例如，Bob可以使用一个基于DH的棘轮协议，将SK与新产生的DH输出结合起来，得到一个随机的加密密钥[5]。

如果不对Bob的加密密钥进行随机化，可能会导致灾难性的密钥重复使用。

4.4.不可否认性

X3DH并没有给Alice或Bob一个可公布的加密证明，证明他们的通信内容或他们通信的事实。

就像在OTR协议[6]中，在某些情况下，一个从Alice或Bob那里泄露了合法私钥的第三方可以得到一个看起来是Alice和Bob之间的通信记录，而这个记录只能是由其他一些能够接触到Alice或Bob合法私钥的人（即Alice或Bob自己，或者其他泄露了他们私钥的人）创建的。

如果任何一方在协议执行期间与第三方合作，他们将能够向这样的第三方提供他们的通信证明。这种对 "在线 "不可否认性的限制似乎是异步设置的内在因素[7]。

4.5.签名

观察相互认证和前向保密是通过 DH 计算实现的，并省略预密钥签名，可能是很诱人的。然而，这将允许 "弱前向保密性 "的攻击。一个恶意的服务器可以向Alice提供一个带有伪造预密钥的预密钥包，然后破坏Bob的IKB来计算SK。

另外，用身份密钥的签名来取代基于DH的相互认证（即DH1和DH2）可能是很诱人的。然而，这减少了可否认性，增加了初始信息的大小，并增加了在临时密钥或预密钥的私钥被破坏，或签名方案被破坏时造成的损失。

4.6.密钥泄露

一方私钥的妥协对安全有灾难性的影响，尽管使用临时密钥和预密钥提供了一些缓解。

一方的身份私钥被破坏后，就可以向其他人冒充该方。一方的预密钥私钥的妥协可能会影响较早或较新的SK值的安全，这取决于许多考虑。

对所有可能的妥协情况的全面分析超出了本文件的范围，但下面是对一些可信情况的部分分析。

如果在协议运行中使用一次性预密钥，那么在未来的某个时间，Bob的身份密钥和预密钥私钥的泄露将不会泄露较早的SK，前提是OPKB的私钥被删除。

如果一次性预密钥没有用于协议运行，那么该协议运行中的IKB和SPKB的私钥被泄露就会泄露先前计算的SK。频繁地更换签名的预密钥可以缓解这一问题，就像使用X3DH后棘轮协议一样，该协议迅速用新的密钥替换SK以提供新的前向保密性[5]。

预密钥私钥的破坏可能会使攻击延伸到未来，如被动计算SK值，以及将任意的其他方冒充给被破坏方（"密钥破坏冒充"）。这些攻击是可能的，直到被破坏的一方在服务器上替换他被破坏的预密钥（在被动攻击的情况下）；或删除他被破坏的已签名预密钥的私钥（在密钥破坏的冒充情况下）。

4.7. 服务器信任

恶意的服务器可能导致Alice和Bob之间的通信失败（例如，拒绝传递信息）。

如果Alice和Bob像第4.1节中那样互相认证，那么服务器唯一可用的额外攻击就是拒绝发放一次性预密钥，导致SK的前向保密性取决于签名预密钥的寿命（如上一节所分析）。

如果一方恶意消耗另一方的一次性预密钥，这种初始前向保密性的降低也可能发生，所以服务器应该试图防止这种情况，例如对获取预密钥包的速率进行限制。

7. 参考

[1] A. Langley, M. Hamburg, and S. Turner, “Elliptic Curves for Security.” Internet Engineering Task Force; RFC 7748 (Informational); IETF, Jan-2016. http://www.ietf.org/rfc/rfc7748.txt

[2] T. Perrin, “The XEdDSA and VXEdDSA Signature Schemes,” 2016. https://whispersystems.org/docs/specifications/xeddsa/

[3] H. Krawczyk and P. Eronen, “HMAC-based Extract-and-Expand Key Derivation Function (HKDF).” Internet Engineering Task Force; RFC 5869 (Informational); IETF, May-2010. http://www.ietf.org/rfc/rfc5869.txt

[4] P. Rogaway, “Authenticated-encryption with Associated-data,” in Proceedings of the 9th ACM Conference on Computer and Communications Security, 2002. http://web.cs.ucdavis.edu/~rogaway/papers/ad.pdf

[5] T. Perrin, “The Double Ratchet Algorithm (work in progress),” 2016.

[6] N. Borisov, I. Goldberg, and E. Brewer, “Off-the-record Communication, or, Why Not to Use PGP,” in Proceedings of the 2004 aCM workshop on privacy in the electronic society, 2004. Off-the-record communication, or, why not to use PGP | Proceedings of the 2004 ACM workshop on Privacy in the electronic society

[7] N. Unger and I. Goldberg, “Deniable Key Exchanges for Secure Messaging,” in Proceedings of the 22Nd aCM sIGSAC conference on computer and communications security, 2015. Deniable Key Exchanges for Secure Messaging | Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

[8] C. Kudla and K. G. Paterson, “Modular Security Proofs for Key Agreement Protocols,” in Advances in Cryptology - ASIACRYPT 2005: 11th International Conference on the Theory and Application of Cryptology and Information Security, 2005. PHP MySQL support not enabled

[9] S. Blake-Wilson, D. Johnson, and A. Menezes, “Key agreement protocols and their security analysis,” in Crytography and Coding: 6th IMA International Conference Cirencester, UK, December 17–19, 1997 Proceedings, 1997. CiteSeerX

[10] C. Cremers and M. Feltz, “One-round Strongly Secure Key Exchange with Perfect Forward Secrecy and Deniability.” Cryptology ePrint Archive, Report 2011/300, 2011. One-round Strongly Secure Key Exchange with Perfect Forward Secrecy and Deniability

[11] J. P. Degabriele, A. Lehmann, K. G. Paterson, N. P. Smart, and M. Strefler, “On the Joint Security of Encryption and Signature in EMV.” Cryptology ePrint Archive, Report 2011/615, 2011. On the Joint Security of Encryption and Signature in EMV

附录：X3DH的代码简易实现

 // server
 server := NewServer()
 // alice
 alice := NewX3DHKeyPairs(curve.GenerateKeyPair())
 alice.ResetSignedPreKeyPair()
 server.AddPubKeys("alice", alice.GetPublicKeys())

 // bob
 bob := NewX3DHKeyPairs(curve.GenerateKeyPair())
 bob.ResetSignedPreKeyPair()
 server.AddPubKeys("bob", bob.GetPublicKeys())

 // alice send message to bob
 bobPublicKeys := server.GetPubKeys("bob")
 sharedKey := alice.BuildSharedKey(bobPublicKeys)
 sendKeyPackage := alice.BuildSendKeyPackage(bobPublicKeys, sharedKey)

 sharedKey2 := bob.GetSharedKey(sendKeyPackage)
 t.Logf("equal: %v", bytes.Equal(sharedKey, sharedKey2))

以上代码就是一次代码交换的示例，可以看到服务端只存储了公钥包，也就是说服务端无法解析每个人消息体。

而且只需要发送端拉取一次公钥包，后续是不需要再跟该服务器进行交互的，也就是说服务器是不知道这两个人是否最终进行了通信的。

以下是根据协议梳理的go语言实现：

package main

type Server struct {
    pubKeys map[string]*X3DHPublicKeys
}

func NewServer() *Server {
    return &Server{
        pubKeys: make(map[string]*X3DHPublicKeys),
    }
}

func (s *Server) AddPubKeys(name string, pubKeys *X3DHPublicKeys) {
    s.pubKeys[name] = pubKeys
}

func (s *Server) GetPubKeys(name string) *X3DHPublicKeys {
    k, _ := s.pubKeys[name]
    return k
}

package main

import (
    "encoding/base64"
    "learnGo/learn/pprof/aes"
    "learnGo/learn/pprof/curve"
)

type X3DHKeyPairs struct {
    IdentityKeyPair   *curve.KeyPair
    EphemeralKeyPair  *curve.KeyPair
    SignedPreKeyPair  *curve.KeyPair
    OneTimePreKeyPair *curve.KeyPair
}

func NewX3DHKeyPairs(identityKey *curve.KeyPair) *X3DHKeyPairs {
    return &X3DHKeyPairs{
        IdentityKeyPair: identityKey,
    }
}

func (k *X3DHKeyPairs) ResetSignedPreKeyPair() {
    k.SignedPreKeyPair = curve.GenerateKeyPair()
}

type X3DHPublicKeys struct {
    IdentityKey       [32]byte
    SignedPreKey      [32]byte
    PreKeySignature   []byte
    OneTimePreKey     [32]byte
    haveOneTimePreKey bool
}

func (k *X3DHKeyPairs) GetPublicKeys() *X3DHPublicKeys {
    opk := [32]byte{}
    if k.OneTimePreKeyPair != nil {
        opk = k.OneTimePreKeyPair.PublicKey
    }
    return &X3DHPublicKeys{
        IdentityKey:       k.IdentityKeyPair.PublicKey,
        SignedPreKey:      k.SignedPreKeyPair.PublicKey,
        PreKeySignature:   []byte{},
        OneTimePreKey:     opk,
        haveOneTimePreKey: k.OneTimePreKeyPair != nil,
    }
}

func (k *X3DHKeyPairs) BuildSharedKey(peerPublicKeys *X3DHPublicKeys) []byte {
    k.EphemeralKeyPair = curve.GenerateKeyPair()

    dh1 := k.IdentityKeyPair.GenerateShareKey(peerPublicKeys.SignedPreKey)
    dh2 := k.EphemeralKeyPair.GenerateShareKey(peerPublicKeys.IdentityKey)
    dh3 := k.EphemeralKeyPair.GenerateShareKey(peerPublicKeys.SignedPreKey)
    sk := make([]byte, 0, 32*4)
    sk = append(sk, dh1[:]...)
    sk = append(sk, dh2[:]...)
    sk = append(sk, dh3[:]...)
    if peerPublicKeys.haveOneTimePreKey {
        dh4 := k.EphemeralKeyPair.GenerateShareKey(peerPublicKeys.OneTimePreKey)
        sk = append(sk, dh4[:]...)
    }
    k.EphemeralKeyPair.PrivateKey = [32]byte{}
    return sk
}

type SendKeyPackage struct {
    IdentityKey      [32]byte
    EphemeralKey     [32]byte
    OnetimeKeyNotice [32]byte
    Secret           []byte
}

func (k *X3DHKeyPairs) BuildSendKeyPackage(peerPublicKeys *X3DHPublicKeys, sharedKey []byte) *SendKeyPackage {
    b64 := base64.StdEncoding.EncodeToString(append(k.IdentityKeyPair.PublicKey[:], peerPublicKeys.IdentityKey[:]...))
    return &SendKeyPackage{
        IdentityKey:      k.IdentityKeyPair.PublicKey,
        EphemeralKey:     k.EphemeralKeyPair.PublicKey,
        OnetimeKeyNotice: peerPublicKeys.OneTimePreKey,
        Secret:           aes.Aes256GcmEncrypt([]byte(b64), sharedKey),
    }
}

func (k *X3DHKeyPairs) verify(keyPackage *SendKeyPackage, sk []byte) bool {
    b64 := base64.StdEncoding.EncodeToString(append(keyPackage.IdentityKey[:], k.IdentityKeyPair.PublicKey[:]...))
    _, err := aes.Aes256GcmDecrypt(keyPackage.Secret, sk, []byte(b64))
    if err != nil {
        return false
    }
    return true
}

func (k *X3DHKeyPairs) GetSharedKey(keyPackage *SendKeyPackage) []byte {

    dh1 := k.SignedPreKeyPair.GenerateShareKey(keyPackage.IdentityKey)
    dh2 := k.IdentityKeyPair.GenerateShareKey(keyPackage.EphemeralKey)
    dh3 := k.SignedPreKeyPair.GenerateShareKey(keyPackage.EphemeralKey)
    sk := make([]byte, 0, 32*4)
    sk = append(sk, dh1[:]...)
    sk = append(sk, dh2[:]...)
    sk = append(sk, dh3[:]...)
    if keyPackage.OnetimeKeyNotice != [32]byte{} {
        dh4 := k.OneTimePreKeyPair.GenerateShareKey(keyPackage.EphemeralKey)
        sk = append(sk, dh4[:]...)
    }
    if !k.verify(keyPackage, sk) {
        return nil
    }
    return sk
}

创作团队

作者：Darren

校对：Wayne、Yuki