0x00 前言

咳咳,总想着得发点啥。最近在家不是打CODE VEIN就是下自走棋。这样8太行的样子
之前写了2019年的总结。一方面最近打算去考个英语的证书,另一方面得提升一下自己的专业技能。感觉大半年没摸信安,好多东西都忘了。不要慌,慢慢的会捡起来。

有位写飞机的同志让我了解一下ChaCha20-poly1305算法,我上谷歌搜了搜感觉这算法(或者说它的相关知识)谷歌于2014年在Chrome中部署了新的TLS密码套件,而某些小飞机软件逐渐开始支持这一船新的算法。于是就有了下文。

0x01 ploy 1305 与 ChaCha20

Refer:
https://libsodium.gitbook.io/doc/advanced/stream_ciphers/chacha20
https://tools.ietf.org/html/rfc7539

ChaCha20-Poly1305 加密套件使用了两种算法,其中 Chacha20 是指对称加密算法,Poly1305 是指身份认证算法

ChaCha20

chacha密码家族是 Salsa密码家族的变种,发明者都是 Bernstein。以ChaCha20为例

ChaCha20的一轮运算

其初始状态包括了包括一个128位常量(Constant,常量的内容为 0x61707865, 0x3320646e,0x79622d32, 0x6b206574.),一个256位密钥(Key),一个64位计数(Counter)和一个64位随机数(Nonce),一共64B。排列成4*4的32位字矩阵如下所示:(实际运算为小端)

| Cons | Cons | Cons  | Cons  |
| Key  | Key  | Key   | Key   |
| Key  | Key  | Key   | Key   |
| Pos  | Pos  | Nonce | Nonce |

备注:此处的Pos是指块的位置,ChaCha20的块大小是64B。因此32bit的计数器可以容纳256GB数据。Pos的初值设定为0或1。

ChaCha20的四分之一加密轮次的算法为QR(a,b,c,d),其过程包括

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;
// a <<<= b 是旋转运算。发明者定义这个旋转运算为
// (((a) << (b)) | ((a) >> (32 - (b))))

ChaCha20对一个块的加密包括20轮运算(这也是20的含义),一轮的操作根据是该轮次为奇数和偶数而不同,如下所示。

// Odd round
QR(0, 4,  8, 12)    // 1st column
QR(1, 5,  9, 13)    // 2nd column
QR(2, 6, 10, 14)    // 3rd column
QR(3, 7, 11, 15)    // 4th column
// Even round
QR(0, 5, 10, 15)    // diagonal 1 (main diagonal)
QR(1, 6, 11, 12)    // diagonal 2
QR(2, 7,  8, 13)    // diagonal 3
QR(3, 4,  9, 14)    // diagonal 4

ChaCha20的加密与解密过程

将需要加密的信息(明文)与密钥流按位异或即得到密文,由于计数器是32位,理论上可以生成2 ^ 512 bit(256GB)的密钥流。如果希望加密的信息是256位的整数倍(考虑采用了填充算法),那过程应该如下所示。个人理解画了个流程图如下所示,如有不正确还请指正。(pos也可以从0开始,参考了RFC上的样例)

ChaCha20-poly1305 与 AEAD-ShaoBaoBaoEr's Blog

在实际的过程中,如果仅仅考虑将一个256bit的秘钥和64bit的nouce映射为512bit的密钥流,只需要执行核心的chacha20_block(key,counter,nonce)即可。

Poly1305

Poly1305是Daniel J. Bernstein创建的快速Carter-Wegman MAC算法。
Poly1305最初是与AES结合定义的,但是现在最常与ChaCha20和XChaCha20结合使用。

Poly1305的过程

Poly1305的输入是

  • 任意长度的消息
  • 256 bit 的一次性秘钥,应该有两个部分(r,s),每部分长都是128bit
    • 该秘钥在Poly-AES的组合中是128bit的AES秘钥和一个128bit的nonce。实际上只要是一个16B的字符串即可。
    • 该秘钥在Poly-ChaCha的组合中就是ChaCha20最后输出的512bit(64B)密文的前32B。其中32B再均分为两个部分,第一部分r,第二部分为s。生成的过程如下所示,
      poly1305_key_gen(key,nonce):
         counter = 0
         block = chacha20_block(key,counter,nonce)
         return block[0..31]
         end

其输出是一个 128bit的TAG。其过程不赘述。可以看RFC文档。

0x03 AEAD

参考
https://juejin.im/entry/5c08ff2d6fb9a049e6600c77
https://tools.ietf.org/html/rfc7539
https://en.wikipedia.org/wiki/Authenticated_encryption

Why AEAD

近几年,Google、Baidu、Facebook 等互联网巨头,不谋而合地开始大力推行HTTPS,国内外的大型互联网公司很多也都已启用全站 HTTPS,这也是未来互联网发展的趋势;

认证加密模式(authenticated encryption,AE)可以保证消息的完整性和机密性。广泛运用于HTTPS中,其加密方式包括了Encrypt-and-MAC,MAC-then-Encrypt,Encrypt-then-MAC三种。具体实现方法可以看Wikipeida。

而带有关联数据的认证加密(authenticated encryption with associated data,AEAD)是一种能够同时保证数据的保密性、 完整性和真实性的一种加密模式。相比之下AE,它拥有了能够检查其他相关联数据完整性的能力,比如说地址,端口,序列号,协议版本号。这些信息可以合并为ADD字段。

AEAD_CHACHA20_POLY1305 过程与实例

AEAD_CHACHA20_POLY1305是带有关联数据的认证加密。AEAD_CHACHA20_POLY1305的输入为:

  • 256位密钥
  • 96位随机数(每次使用相同密钥的其值均不同)
  • 任意长度的纯文本
  • 任意长度的其他已认证数据(AAD)

其过程如下所示:

  • 第一步,将256位的秘钥和随机数用于生成Poly1305的一次性秘钥。(POS=0)
  • 第二步,ChaCha20的加密函数,采用相同的秘钥和随机数,设置POS=1。按照上面的方法加密明文
  • 第三步,构造如下的内容
    • ① ADD
    • ② padding1 (将ADD的长度填充到16字节的整数倍)
    • ③ 密文(第二步得到的密文)
    • ④ padding2 (将密文的长度填充到16字节的整数倍)
    • ⑤ ADD的长度(以8字节为单位,小端存储)
    • ⑥ 密文的长度(以8字节为单位,小端存储)
    • 之后用第一步生成的一次性秘钥加密内容。作为消息验证。

综上所述,该过程可以得到两个内容,一个是ChaCha20加密完的内容,另一个是消息验证,它由Poly1305加密数据得到。

按照RFC文档的例子,可以更好的理解。

定义数据如下

Plaintext:
000  4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c  Ladies and Gentl
016  65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73  emen of the clas
032  73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63  s of '99: If I c
048  6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f  ould offer you o
064  6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20  nly one tip for
080  74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73  the future, suns
096  63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69  creen would be i
112  74 2e                                            t.
AAD:
000  50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7              PQRS........

Key:
000  80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f  ................
016  90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f  ................

IV:
000  40 41 42 43 44 45 46 47                          @ABCDEFG

32-bit fixed-common part:
000  07 00 00 00

第一步,将256位的秘钥和随机数用于生成Poly1305的一次性秘钥。(假定 pos=7)

步骤如下

nonce = pos | iv // 此处的IV 
otk = poly1305_key_gen(key, nonce) // 本质上是chacha20的20轮次

最初装载,准备进行ChaCha20运算的内容为【小端】

61707865  3320646e  79622d32  6b206574 // ChaCha 常量
83828180  87868584  8b8a8988  8f8e8d8c
93929190  97969594  9b9a9998  9f9e9d9c // 秘钥(小端)
00000000  00000007  43424140  47464544 // pos|iv (小端)

经过ChaCha 20轮次运算后得到poly1305一次性秘钥如下所示

252bac7b  af47b42d  557ab609  8455e9a4 //Poly1305 r(实际要把小端存储变回去)
73d6e10a  ebd97510  7875932a  ff53d53e//Poly1305 s(实际要把小端存储变回去)
decc7ea2  b44ddbad  e49c17d1  d8430bc9
8c94b7bc  8b7d4b4b  3927f67d  1669a432 //最后的部分舍弃

第二步,ChaCha20的加密函数,采用相同的秘钥和随机数,设置POS=1。按照上面的方法加密明文

ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)

ChaCha20-poly1305 与 AEAD-ShaoBaoBaoEr's Blog
经过上述流程后,能够得到密文

Ciphertext:
000  d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2  ...4d.`.{...S.~.
016  a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6  ...Q)n......6.b.
032  3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b  =..^..g....i..r.
048  1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36  .q.....)....~.;6
064  92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58  ....-w......(..X
080  fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc  ..$...u.U...H1..
096  3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b  ?....Kz..v.e...K
112  61 16                  

第三步,构造 ADD|PADDING1|CIPHER_TEXT|PADDING2 并计算MAC

mac_data:

000  50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 00 00 00 00  PQRS............ 
// ADD 长度为 12B(0x0C);填充4B
016  d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2  ...4d.`.{...S.~.
032  a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6  ...Q)n......6.b.
048  3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b  =..^..g....i..r.
064  1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36  .q.....)....~.;6
080  92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58  ....-w......(..X
096  fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc  ..$...u.U...H1..
112  3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b  ?....Kz..v.e...K
128  61 16 00 00 00 00 00 00 00 00 00 00 00 00 00 00  a...............
// Cipher_text长度为114B(0x72);填充14B
144  0c 00 00 00 00 00 00 00 72 00 00 00 00 00 00 00  ........r.......
// 把长度写上去

用刚刚得到的otk,计算mac_tag与密文。完成。

tag = poly1305_mac(mac_data, otk) //此处为poly1305
return (ciphertext, tag)