Salsa20

2. 구조

Salsa20은 비트 단위 XOR 연산(⊕), 32비트 덧셈 (mod 2³², ⊞), 고정 거리 회전 연산(<<<)을 사용하는 ARX (add-rotate-xor) 구조를 기반으로 한다.

Salsa20의 내부 상태는 16개의 32비트 워드로 구성되며, 4x4 행렬로 표현된다. 초기 상태는 8 워드의 키, 2 워드의 스트림 위치, 2 워드의 nonce, 그리고 4개의 고정 워드로 구성된다. 고정 워드는 "expand 32-byte k"를 ASCII 코드로 표현한 것이며, NAMS의 한 예이다.

Salsa20의 핵심 연산은 4개의 워드 입력을 받아 4개의 워드 출력을 생성하는 1/4 라운드 함수 `QR(a, b, c, d)`이다.

```

b ⊕= (a ⊞ d) <<< 7;

c ⊕= (b ⊞ a) <<< 9;

d ⊕= (c ⊞ b) <<< 13;

a ⊕= (d ⊞ c) <<< 18;

```

홀수 라운드에서는 `QR(a, b, c, d)`가 4x4 행렬의 4개 열에 각각 적용되며, 짝수 라운드에서는 4개 행에 각각 적용된다. 연속된 두 라운드(행 라운드와 열 라운드)를 double-round라고 한다. Salsa20은 입력에 대해 20 라운드의 혼합 연산을 수행하며, 마지막에 초기 상태와 혼합된 배열을 더하여 64바이트 키 스트림 블록을 얻는다. 이 과정은 혼합 라운드 자체가 가역적이기 때문에 보안에 중요하다.^[6] 8라운드 및 12라운드를 사용하는 축소 라운드 변형인 Salsa20/8 및 Salsa20/12도 존재한다.^[7]

C/C++ 구현 예시는 다음과 같다.

```c

#include

#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))

#define QR(a, b, c, d)( \

b ^= ROTL(a + d, 7), \

c ^= ROTL(b + a, 9), \

d ^= ROTL(c + b,13), \

a ^= ROTL(d + c,18))

#define ROUNDS 20

void salsa20_block(uint32_t out[16], uint32_t const in[16])

{

int i;

uint32_t x[16];

for (i = 0; i < 16; ++i)

x[i] = in[i];

// 10 loops × 2 rounds/loop = 20 rounds

for (i = 0; i < ROUNDS; i += 2) {

// Odd round

QR(x[ 0], x[ 4], x[ 8], x[12]); // 열 1

QR(x[ 5], x[ 9], x[13], x[ 1]); // 열 2

QR(x[10], x[14], x[ 2], x[ 6]); // 열 3

QR(x[15], x[ 3], x[ 7], x[11]); // 열 4

// Even round

QR(x[ 0], x[ 1], x[ 2], x[ 3]); // 행 1

QR(x[ 5], x[ 6], x[ 7], x[ 4]); // 행 2

QR(x[10], x[11], x[ 8], x[ 9]); // 행 3

QR(x[15], x[12], x[13], x[14]); // 행 4

}

for (i = 0; i < 16; ++i)

out[i] = x[i] + in[i];

}

2. 1. Salsa20

초기 상태는 8개의 키 워드, 2개의 스트림 위치 워드, 2개의 nonce 워드(본질적으로 추가적인 스트림 위치 비트), 그리고 4개의 고정 워드로 구성된다.

고정 워드는 ASCII로 "expand 32-byte k"를 나타낸다(즉, 4개의 워드는 "expa", "nd 3", "2-by", "te k"이다). 이것은 nothing-up-my-sleeve number의 예이다. Salsa20의 핵심 연산은 4개의 워드 입력을 받아 4개의 워드 출력을 생성하는 quarter-round 함수 `QR(a, b, c, d)`이다.

```

b ⊕= (a ⊞ d) <<< 7;

c ⊕= (b ⊞ a) <<< 9;

d ⊕= (c ⊞ b) <<< 13;

a ⊕= (d ⊞ c) <<< 18;

```

홀수 라운드는 4×4 행렬의 4개 열 각각에 `QR(a, b, c, d)`를 적용하고, 짝수 라운드는 각 4개 행에 적용한다. 두 개의 연속적인 라운드(열 라운드와 행 라운드)를 함께 이중 라운드라고 한다.

```c

// 홀수 라운드

QR( 0, 4, 8, 12) // 열 1

QR( 5, 9, 13, 1) // 열 2

QR(10, 14, 2, 6) // 열 3

QR(15, 3, 7, 11) // 열 4

// 짝수 라운드

QR( 0, 1, 2, 3) // 행 1

QR( 5, 6, 7, 4) // 행 2

QR(10, 11, 8, 9) // 행 3

QR(15, 12, 13, 14) // 행 4

```

C/C++로 구현한 예는 다음과 같다.

```c

#include

#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))

#define QR(a, b, c, d)( \

b ^= ROTL(a + d, 7), \

c ^= ROTL(b + a, 9), \

d ^= ROTL(c + b,13), \

a ^= ROTL(d + c,18))

#define ROUNDS 20

void salsa20_block(uint32_t out[16], uint32_t const in[16])

{

int i;

uint32_t x[16];

for (i = 0; i < 16; ++i)

x[i] = in[i];

// 10 loops × 2 rounds/loop = 20 rounds

for (i = 0; i < ROUNDS; i += 2) {

// Odd round

QR(x[ 0], x[ 4], x[ 8], x[12]); // 열 1

QR(x[ 5], x[ 9], x[13], x[ 1]); // 열 2

QR(x[10], x[14], x[ 2], x[ 6]); // 열 3

QR(x[15], x[ 3], x[ 7], x[11]); // 열 4

// Even round

QR(x[ 0], x[ 1], x[ 2], x[ 3]); // 행 1

QR(x[ 5], x[ 6], x[ 7], x[ 4]); // 행 2

QR(x[10], x[11], x[ 8], x[ 9]); // 행 3

QR(x[15], x[12], x[13], x[14]); // 행 4

}

for (i = 0; i < 16; ++i)

out[i] = x[i] + in[i];

}

```

마지막 줄에서 혼합된 배열은 단어별로 원래 배열에 더해져 64바이트 키 스트림 블록을 얻는다. 이는 혼합 라운드 자체가 ''가역적''이기 때문에 중요하다. 다시 말해, 역연산을 적용하면 키를 포함하여 원래의 4×4 행렬이 생성된다. 혼합된 배열을 원래 배열에 더하면 입력을 복구하는 것이 불가능해진다. (이와 동일한 기술은 MD4부터 SHA-2까지 해시 함수에서 널리 사용된다.)

Salsa20은 입력에 대해 20 라운드의 혼합을 수행한다.^[6] 하지만, 8라운드 및 12라운드를 각각 사용하는 축소 라운드 변형인 Salsa20/8 및 Salsa20/12도 도입되었다. 이러한 변형은 원래의 Salsa20을 대체하기 위한 것이 아니라 보완하기 위해 도입되었으며, Salsa20보다 eSTREAM 벤치마크에서 더 나은 성능을 보이지만^[7], 보안 수준은 그에 따라 낮다.

2. 2. ChaCha

상수는 Salsa20과 동일하게 "expand 32-byte k"이다. ChaCha는 Salsa20의 쿼터 라운드 함수 `QR(a, b, c, d)`를 다음과 같이 대체한다.^[21]

:a += b; d ^= a; d <<<= 16;

:c += d; b ^= c; b <<<= 12;

:a += b; d ^= a; d <<<= 8;

:c += d; b ^= c; b <<<= 7;

Salsa20의 쿼터 라운드는 각 단어를 한 번만 업데이트하지만, ChaCha 쿼터 라운드는 각 단어를 두 번 업데이트하여 변경 사항을 더 빠르게 확산시킨다. 1비트 입력을 변경했을 때 Salsa20 쿼터 라운드는 평균 8비트 출력을 변경하는 반면, ChaCha는 평균 12.5비트 출력을 변경한다.^[62]

ChaCha 쿼터 라운드는 Salsa20 쿼터 라운드와 동일한 수의 덧셈, XOR, 비트 회전을 가지지만, 두 회전이 8의 배수이기 때문에 x86을 포함한 일부 아키텍처에서 최적화가 가능하다.^[63] 또한, 입력 형식이 Salsa20에서 발견된 효율적인 SSE 구현 최적화를 지원하도록 재배열되었다.^[64]

Salsa20은 열과 행을 교대로 회전하지만, ChaCha는 열과 대각선을 따라 회전한다.^[64]

ChaCha의 더블 라운드는 다음과 같다.

:// 홀수 라운드

:QR(0, 4, 8, 12) // 열 1

:QR(1, 5, 9, 13) // 열 2

:QR(2, 6, 10, 14) // 열 3

:QR(3, 7, 11, 15) // 열 4

:// 짝수 라운드

:QR(0, 5, 10, 15) // 대각선 1 (주 대각선)

:QR(1, 6, 11, 12) // 대각선 2

:QR(2, 7, 8, 13) // 대각선 3

:QR(3, 4, 9, 14) // 대각선 4

ChaCha20은 더블 라운드를 10번 반복한다.^[22]

IETF 표준 (, )에서는 96비트 논스와 32비트 블록 카운터를 사용하도록 수정되었다.^[47] 블록 카운터가 감소했기 때문에 IETF 변형으로 안전하게 암호화할 수 있는 최대 메시지 길이는 2³²개의 64바이트 블록(256 GiB)이다. 이 길이가 충분하지 않은 경우, 64비트 논스를 사용하는 원래 알고리즘을 사용할 것을 제안한다.

ChaCha는 BLAKE 해시 함수의 기반이 되었다.

2. 2. 1. XChaCha