August 17, 2023

Salsa20 X ChaCha20

本文基本都是 ctrl + cv，用于学习记录，由于历史遗留问题发至博客记录。

Salsa20

Salsa20是一种流加密算法，它使用一个称为Salsa20核心的函数来加密或解密数据。下面是Salsa20算法的详细解释，包括加密和解密流程。

  1. Salsa20算法的核心函数

Salsa20核心函数是一个置换函数，它将输入的128位密钥和随机的64位初始向量（IV）作为输入，然后生成一个256位的密钥流。密钥流是通过对128位输入块进行加密和异或操作生成的。下面是Salsa20核心函数的数学表达式：

Salsa20核心函数输入：密钥K（128位）、初始向量IV（64位）、计数器C（64位）。

Salsa20核心函数输出：密钥流（256位）。

Salsa20核心函数的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
Salsa20(K, IV, C)
    state[16] = constants
    state[1:4] = K[0:3], K[4:7], K[8:11], K[12:15]
    state[11:14] = IV[0:3], IV[4:7], C[0:3], C[4:7]
    for i = 0 to 9 do
        state = QuarterRound(state[0], state[4], state[8], state[12])
        state = QuarterRound(state[5], state[9], state[13], state[1])
        state = QuarterRound(state[10], state[14], state[2], state[6])
        state = QuarterRound(state[15], state[3], state[7], state[11])
    end for
    output = state + constants + K[0:3] + IV[4:7] + C[0:3] + C[4:7]
    return output

其中，constants是一个常量数组，QuarterRound是一个四元运算函数，它对输入的四个32位数进行加密和异或操作，生成四个32位数作为输出。

  1. Salsa20算法的加密流程

Salsa20算法使用密钥流对明文进行加密。加密流程可以分为以下步骤：

（1）将明文分成若干个128位的块。

（2）对每个块进行密钥流加密，使用异或操作将密钥流和明文块进行混合。

（3）将加密后的密文块组合在一起，形成加密后的数据。

下面是Salsa20算法加密流程的数学表达式：

Salsa20加密流程输入：明文M（n * 128位）、密钥K（128位）、初始向量IV（64位）。

Salsa20加密流程输出：密文C（n * 128位）。

Salsa20加密流程的伪代码：

1
2
3
4
5
6
7
8
Salsa20Encrypt(M, K, IV)
    C = []
    C[0] = Salsa20(K, IV, 0)
    for i = 1 to n do
        C[i] = M[i] xor C[i-1]
        C[i] = Salsa20(K, IV, i) xor C[i]
    end for
    return C

其中，n表示明文块的数量，M[i]表示第i个明文块，C[i]表示第i个密文块。

  1. Salsa20算法的解密流程

Salsa20算法使用密钥流对密文进行解密。解密流程可以分为以下步骤：

（1）将密文分成若干个128位的块。

（2）对每个块进行密钥流解密，使用异或操作将密钥流和密文块进行混合。

（3）将解密后的明文块组合在一起，形成解密后的数据。

下面是Salsa20算法解密流程的数学表达式：

Salsa20解密流程输入：密文C（n * 128位）、密钥K（128位）、初始向量IV（64位）。

Salsa20解密流程输出：明文M（n * 128位）。

Salsa20解密流程的伪代码：

1
2
3
4
5
6
7
8
9
Salsa20Decrypt(C, K, IV)
    M = []
    M[0] = Salsa20(K, IV, 0)
    for i = 1 to n do
        M[i] = C[i]
        M[i] = Salsa20(K, IV, i) xor M[i]
        M[i] = M[i] xor C[i-1]
    end for
    return M

其中，n表示密文块的数量，C[i]表示第i个密文块，M[i]表示第i个明文块。

综上所述，Salsa20算法是一种高效、安全的流加密算法，它可以用于数据通信、数据存储等多种场景。在实际应用中，需要注意密钥的生成、密钥流的保密性等问题，以确保数据的安全性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#include <stdint.h> // we use 32-bit words

// rotate x to left by n bits, the bits that go over the left edge reappear on the right
#define R(x,n) (((x) << (n)) | ((x) >> (32-(n))))

// addition wraps modulo 2^32
// the choice of 7,9,13,18 "doesn't seem very important" (spec)
#define quarter(a,b,c,d) do {\
    b ^= R(d+a, 7);\
    c ^= R(a+b, 9);\
    d ^= R(b+c, 13);\
    a ^= R(c+d, 18);\
} while (0)

void salsa20_words(uint32_t* out, uint32_t in[16]) {            //chacha20_quarterround(x, 0, 4,  8, 12);
                                                                //chacha20_quarterround(x, 1, 5,  9, 13);
                                                                //chacha20_quarterround(x, 2, 6, 10, 14);
                                                                //chacha20_quarterround(x, 3, 7, 11, 15);
                                                                ////even round 
                                                                //chacha20_quarterround(x, 0, 5, 10, 15);
                                                                //chacha20_quarterround(x, 1, 6, 11, 12);
                                                                //chacha20_quarterround(x, 2, 7,  8, 13);
                                                                //chacha20_quarterround(x, 3, 4,  9, 14);   其实这俩的置换是一模一样的 
    uint32_t x[4][4];
    int i;
    for (i = 0; i < 16; ++i) 
        x[i / 4][i % 4] = in[i];

    for (i = 0; i < 10; ++i) { // 10 double rounds = 20 rounds
        // column round: quarter round on each column; start at ith element and wrap
        quarter(x[0][0], x[1][0], x[2][0], x[3][0]);
        quarter(x[1][1], x[2][1], x[3][1], x[0][1]);
        quarter(x[2][2], x[3][2], x[0][2], x[1][2]);
        quarter(x[3][3], x[0][3], x[1][3], x[2][3]);
        // row round: quarter round on each row; start at ith element and wrap around
        quarter(x[0][0], x[0][1], x[0][2], x[0][3]);
        quarter(x[1][1], x[1][2], x[1][3], x[1][0]);
        quarter(x[2][2], x[2][3], x[2][0], x[2][1]);
        quarter(x[3][3], x[3][0], x[3][1], x[3][2]);
    }
    for (i = 0; i < 16; ++i) 
        out[i] = x[i / 4][i % 4] + in[i];
}

// inputting a key, message nonce, keystream index and constants to that transormation
void salsa20_block(uint8_t* out, uint8_t key[32], uint64_t nonce, uint64_t index) {
    static const char c[16] = "expand 32-byte k"; // arbitrary constant

#define LE(p) ( (p)[0] | ((p)[1]<<8) | ((p)[2]<<16) | ((p)[3]<<24) )

    uint32_t in[16] = { LE(c),            LE(key),    LE(key + 4),        LE(key + 8),
                       LE(key + 12),       LE(c + 4),    nonce & 0xffffffff, nonce >> 32,
                       index & 0xffffffff, index >> 32,  LE(c + 8),          LE(key + 16),
                       LE(key + 20),       LE(key + 24), LE(key + 28),       LE(c + 12) };
    uint32_t wordout[16];
    salsa20_words(wordout, in);
    int i;
    for (i = 0; i < 64; ++i) 
        out[i] = 0xff & (wordout[i / 4] >> (8 * (i % 4)));
}

// enc/dec: xor a message with transformations of key, a per-message nonce and block index
void salsa20(uint8_t* message, uint64_t mlen, uint8_t key[32], uint64_t nonce) {
    int i;
    uint8_t block[64];
    for (i = 0; i < mlen; i++) 
    {
        if (i % 64 == 0) salsa20_block(block, key, nonce, i / 64);
        message[i] ^= block[i % 64];
    }
}


int main(void){
    uint8_t key[32] = { 0 };
    uint64_t nonce = 0;
    uint8_t msg[64] = { 0 };            // 密文        

    salsa20(msg, sizeof(msg), key, nonce);
    int i; 

    for (i = 0; i < sizeof(msg); ++i) 
        printf("%02X ", msg[i]); printf("\n");

    return 0;
}

但感觉这代码怪怪的，和文章看到的不太一样，没找到个喜欢的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Cipher import Salsa20

plaintext = b'Attack at dawn'
secret = b'*Thirty-two byte (256 bits) key*'
cipher = Salsa20.new(key=secret)
msg = cipher.nonce + cipher.encrypt(plaintext)


from Crypto.Cipher import Salsa20

secret = b'*Thirty-two byte (256 bits) key*'
msg_nonce = msg[:8]
ciphertext = msg[8:]
cipher = Salsa20.new(key=secret, nonce=msg_nonce)
plaintext = cipher.decrypt(ciphertext)

ChaCha20

一、简介

Chacha20流密码经常和Poly1305消息认证码结合使用，被称为ChaCha20-Poly1305,由Google公司率先在Andriod移动平台中的Chrome中代替RC4使用,由于其算法精简、安全性强、兼容性强等特点，目前Google致力于全面将其在移动端推广

二、初始化矩阵

ChaCha20加密的初始状态包括了包括了

1、一个128位常量(Constant)

常量的内容为0x61707865,0x3320646e,0x79622d32,0x6b206574.)

2、一个256位密钥(Key)

3、一个64位计数(Counter)

4、一个64位随机数(Nonce)

一共64字节其排列成4 * 4的32位字矩阵如下所示：（实际运算为小端)

![image-20230818132802555](Salsa20 X ChaCha20/image-20230818132802555.png)

ChaCha20.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#pragma once

#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#ifdef __cplusplus 
extern "C" {
#endif

	struct chacha20_context
	{
		uint32_t keystream32[16];
		size_t position;

		uint8_t key[32];
		uint8_t nonce[12];
		uint64_t counter;

		uint32_t state[16];
	};

	void chacha20_init_context(struct chacha20_context* ctx, uint8_t key[], uint8_t nounc[], uint64_t counter);

	void chacha20_xor(struct chacha20_context* ctx, uint8_t* bytes, size_t n_bytes);

#ifdef __cplusplus 
}
#endif

ChaCha.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include "ChaCha20.h"


static uint16_t rotl32(uint16_t x, int n)
{
	return (x << n) | (x >> (32 - n));
}


static uint32_t pack4(const uint8_t* a)
{
	uint32_t res = 0;
	res |= (uint32_t)a[0] << 0 * 8;
	res |= (uint32_t)a[1] << 1 * 8;
	res |= (uint32_t)a[2] << 2 * 8;
	res |= (uint32_t)a[3] << 3 * 8;
	return res;
}


static void unpack4(uint32_t src, uint8_t* dst) {
	dst[0] = (src >> 0 * 8) & 0xff;
	dst[1] = (src >> 1 * 8) & 0xff;
	dst[2] = (src >> 2 * 8) & 0xff;
	dst[3] = (src >> 3 * 8) & 0xff;
}


static void chacha20_init_block(struct chacha20_context* ctx, uint8_t key[], uint8_t nonce[])
{
	memcpy(ctx->key, key, sizeof(ctx->key));
	memcpy(ctx->nonce, nonce, sizeof(ctx->nonce));

	const uint8_t* magic_constant = (uint8_t*)"expand 32-byte k";
	ctx->state[0] = pack4(magic_constant + 0 * 4);
	ctx->state[1] = pack4(magic_constant + 1 * 4);
	ctx->state[2] = pack4(magic_constant + 2 * 4);
	ctx->state[3] = pack4(magic_constant + 3 * 4);
	ctx->state[4] = pack4(key + 0 * 4);
	ctx->state[5] = pack4(key + 1 * 4);
	ctx->state[6] = pack4(key + 2 * 4);
	ctx->state[7] = pack4(key + 3 * 4);
	ctx->state[8] = pack4(key + 4 * 4);
	ctx->state[9] = pack4(key + 5 * 4);
	ctx->state[10] = pack4(key + 6 * 4);
	ctx->state[11] = pack4(key + 7 * 4);
	// 64 bit counter initialized to zero by default.
	ctx->state[12] = 0;
	ctx->state[13] = pack4(nonce + 0 * 4);
	ctx->state[14] = pack4(nonce + 1 * 4);
	ctx->state[15] = pack4(nonce + 2 * 4);

	memcpy(ctx->nonce, nonce, sizeof(ctx->nonce));
}


static void chacha20_block_set_counter(struct chacha20_context* ctx, uint64_t counter)
{
	ctx->state[12] = (uint32_t)counter;
	ctx->state[13] = pack4(ctx->nonce + 0 * 4) + (uint32_t)(counter >> 32);
}


static void chacha20_block_next(struct chacha20_context* ctx) {
	// This is where the crazy voodoo magic happens.
	// Mix the bytes a lot and hope that nobody finds out how to undo it.
	for (int i = 0; i < 16; i++) ctx->keystream32[i] = ctx->state[i];

#define CHACHA20_QUARTERROUND(x, a, b, c, d) \
    x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 16); \
    x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 12); \
    x[a] += x[b]; x[d] = rotl32(x[d] ^ x[a], 8); \
    x[c] += x[d]; x[b] = rotl32(x[b] ^ x[c], 7);
	
	for (int i = 0; i < 10; i++)
	{
			CHACHA20_QUARTERROUND(ctx->keystream32, 0, 4, 8, 12)
			CHACHA20_QUARTERROUND(ctx->keystream32, 1, 5, 9, 13)
			CHACHA20_QUARTERROUND(ctx->keystream32, 2, 6, 10, 14)
			CHACHA20_QUARTERROUND(ctx->keystream32, 3, 7, 11, 15)
			CHACHA20_QUARTERROUND(ctx->keystream32, 0, 5, 10, 15)
			CHACHA20_QUARTERROUND(ctx->keystream32, 1, 6, 11, 12)
			CHACHA20_QUARTERROUND(ctx->keystream32, 2, 7, 8, 13)
			CHACHA20_QUARTERROUND(ctx->keystream32, 3, 4, 9, 14)
	}

	for (int i = 0; i < 16; i++) ctx->keystream32[i] += ctx->state[i];

	uint32_t* counter = ctx->state + 12;
	// increment counter
	counter[0]++;
	if (0 == counter[0])
	{
		// wrap around occured, increment higher 32 bits of counter
		counter[1]++;
		// Limited to 2^64 blocks of 64 bytes each.
		// If you want to process more than 1180591620717411303424 bytes
		// you have other problems.
		// We could keep counting with counter[2] and counter[3] (nonce),
		// but then we risk reusing the nonce which is very bad.
		assert(0 != counter[1]);
	}
}


void chacha20_init_context(struct chacha20_context* ctx, uint8_t key[], uint8_t nonce[], uint64_t counter)
{
	memset(ctx, 0, sizeof(struct chacha20_context));

	chacha20_init_block(ctx, key, nonce);
	chacha20_block_set_counter(ctx, counter);

	ctx->counter = counter;
	ctx->position = 64;
}


void chacha20_xor(struct chacha20_context* ctx, uint8_t* bytes, size_t n_bytes)
{
	uint8_t* keystream8 = (uint8_t*)ctx->keystream32;
	for (size_t i = 0; i < n_bytes; i++)
	{
		if (ctx->position >= 64)
		{
			chacha20_block_next(ctx);
			ctx->position = 0;
		}
		bytes[i] ^= keystream8[ctx->position];
		ctx->position++;
	}
}

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdint.h>
#include <string.h>
#include <stdio.h> 
#include "ChaCha20.h"


int main(void)
{
	struct chacha20_context ctx;

	uint8_t buffer[] = "12345678123456781234567812345678";

	uint8_t key[] = "abcd1234abcd1234abcd1234abcd1234";

	uint8_t nonce[] = "1234ABCDabcd";
	// 看原理 nonce 只占了 64bit，但是看大家代码都是用 96 bit

	uint64_t counter = 1;

	int i;
	size_t size_of_buffer = (size_t)32;

	printf("Encrypt: ");
	chacha20_init_context(&ctx, key, nonce, counter);
	chacha20_xor(&ctx, buffer, size_of_buffer);
	for (i = 0; i < 32; i++)
		printf("0x%X, ", buffer[i]);
	
	printf("\n\n");
	printf("Decrypt: ");
	chacha20_init_context(&ctx, key, nonce, counter);
	chacha20_xor(&ctx, buffer, size_of_buffer);
	for (i = 0; i < 32; i++)
		printf("0x%X, ", buffer[i]);

	return 0;
}

测试结果

1
2
3
Encrypt: 0x9A, 0x66, 0x7F, 0x13, 0xB8, 0xF2, 0x4A, 0xA2, 0x74, 0x8C, 0x1C, 0x63, 0xAC, 0xF0, 0x4A, 0x32, 0xD0, 0x48, 0x50, 0x50, 0x84, 0x54, 0x4, 0xC, 0xD0, 0x48, 0x50, 0x50, 0x84, 0x54, 0x4, 0xC,

Decrypt: 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import json
from base64 import b64encode
from Crypto.Cipher import ChaCha20
from Crypto.Random import get_random_bytes

plaintext = b'Attack at dawn'
key = get_random_bytes(32)
cipher = ChaCha20.new(key=key)
ciphertext = cipher.encrypt(plaintext)

nonce = b64encode(cipher.nonce).decode('utf-8')
ct = b64encode(ciphertext).decode('utf-8')
result = json.dumps({'nonce':nonce, 'ciphertext':ct})
print(result)



import json
from base64 import b64decode
from Crypto.Cipher import ChaCha20

# We assume that the key was somehow securely shared
try:
    b64 = json.loads(result)
    nonce = b64decode(b64['nonce'])
    ciphertext = b64decode(b64['ciphertext'])
    cipher = ChaCha20.new(key=key, nonce=nonce)
    plaintext = cipher.decrypt(ciphertext)
    print("The message was ", plaintext)
except (ValueError, KeyError):
    print("Incorrect decryption")

开摆，等哪题碰到这种题再测

Reference

https://www.cnblogs.com/lordtianqiyi/articles/16822639.html

https://openprompt.co/conversations/1861

https://pycryptodome.readthedocs.io/en/latest/src/cipher/salsa20.html

https://pycryptodome.readthedocs.io/en/latest/src/cipher/chacha20.html

DASCTF X SU
🍬
HFCTF2022
🍪

About this Post

This post is written by P.Z, licensed under CC BY-NC 4.0.