Zenn
🐺

ChaCha20を理解したい（実装編）

2024/01/03に公開
crypto
ChaCha20
tech

はじめに

RC4に続き、共通鍵暗号を理解したいシリーズの第２弾です。今回は、ストリーム暗号のChaCha20に挑戦します。

ChaCha20は2008年に開発されたストリーム暗号であり、Salsa20というストリーム暗号の内部状態やQuater-Round関数を変更（改良）したものとなります。メッセージ認証符号（MAC）と組み合わせた認証暗号ChaCha20-Poly1305として見かけることが多く、2024年1月時点ではCRYPTREC暗号リストに含まれています。今回は、RFC 8439を参照しながら、ChaCha20-Poly1305ではなくChaCha20のみを扱います。

前回と同じく、ChaCha20のアルゴリズムを紹介し、これをC言語で実装してみます。（まだRC4もできていませんが、）Ghidraでのリバースエンジニアリングもできればと思っています。

  • 🐺が勉強としてやっているだけなので、参考程度に見てください。
  • この記事は予告なく加筆・修正される場合があります

ChaCha20のアルゴリズム

ChaCha20は、256\ \text{bits}の鍵（Key）、96\ \text{bits}のNonce、32\ \text{bits}のカウンタ（Counter）を入力とし、512\ \text{bits}の鍵ストリームを出力します。暗号化したい平文のサイズが512\ \text{bits}以上の場合は、Counterをインクリメントして必要な分の鍵ストリームを生成することになります。
なお、鍵が128\ \text{bits}だったり、Nonceとカウンタの両方が64\ \text{bits}だったりなこともあるようです。

今回は、なんとなく次のようなChacha20構造体を定義します[1]。

typedef struct {
    uint32_t state[16];
} Chacha20;

内部状態の初期化

ChaCha20の内部状態（State）は、16\ \text{words}（1 \text{word}=32\text{bits}）の値で構成され、4\times 4行列で表されます（左の図）。これに入力と定数（Const）を当てはめて、初期値とします（右の図）。

Constは文字列"expand 32-byte k"と決められており、これを32\ \text{bits}\times 4に分割します。また、すべてリトルエンディアンにする必要があるそうです。つまり、Constであれば

  • Const[0] = 0x61707865 (expa)
  • Const[1] = 0x3320646E (nd 3)
  • Const[2] = 0x79622D32 (2-by)
  • Const[3] = 0x6B206574 (te k)

となります。

この部分は、愚直に次のように実装しました。

// 内部状態を初期化する関数
// 内部状態を初期化する関数
void init_state(Chacha20* chacha20, const uint8_t* key, const uint8_t* nonce, uint32_t counter) {
    chacha20->state[0] = 0x61707865;  // "expa"（リトルエンディアン）
    chacha20->state[1] = 0x3320646e;  // "nd 3"（リトルエンディアン）
    chacha20->state[2] = 0x79622d32;  // "2-by"（リトルエンディアン）
    chacha20->state[3] = 0x6b206574;  // "te k"（リトルエンディアン）
    chacha20->state[4] = ((uint32_t*)key)[0];
    chacha20->state[5] = ((uint32_t*)key)[1];
    chacha20->state[6] = ((uint32_t*)key)[2];
    chacha20->state[7] = ((uint32_t*)key)[3];
    chacha20->state[8] = ((uint32_t*)key)[4];
    chacha20->state[9] = ((uint32_t*)key)[5];
    chacha20->state[10] = ((uint32_t*)key)[6];
    chacha20->state[11] = ((uint32_t*)key)[7];
    chacha20->state[12] = counter;
    chacha20->state[13] = ((uint32_t*)nonce)[0];
    chacha20->state[14] = ((uint32_t*)nonce)[1];
    chacha20->state[15] = ((uint32_t*)nonce)[2];
}

内部状態の攪拌（ブロック関数）

初期化した内部状態は、Quarter-Roundと呼ばれる関数に入れられます。Quarter-Round関数は、4\ \text{words}の組(a,b,c,d)を入力とし、図のような処理を行います。"\boxplus"は2^{32}を法とする加算、"\oplus"はビット単位のXOR、"<<<\ n"はn\ \text{bits}の巡回左シフトを表します。

Quarter-Round関数を4つ並列して1ラウンドとし、20ラウンドを実行します[2]。ラウンドによってQuarter-Round関数への入力(a,b,c,d)が異なり、奇数ラウンドでは列の要素（左の図）、偶数ラウンドでは対角の要素（右の図）を組み合わせます。

最後に、内部状態の各要素に初期値を加算します。この一連の処理をまとめて、ChaCha20のブロック関数というそうです[3]。

この部分は、次のように実装しました。

// 巡回左シフトする関数
uint32_t ROTL32(uint32_t value, int shift) {
    return (value << shift) | (value >> (32 - shift));
}

// ChaCha20のQuarter-Round関数
void quarter_round(uint32_t* a, uint32_t* b, uint32_t* c, uint32_t* d) {
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 16);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 12);
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 8);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 7);
}

// 巡回左シフトする関数
uint32_t ROTL32(uint32_t value, int shift) {
    return (value << shift) | (value >> (32 - shift));
}

// ChaCha20のQuarter-Round関数
void quarter_round(uint32_t* a, uint32_t* b, uint32_t* c, uint32_t* d) {
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 16);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 12);
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 8);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 7);
}

// ChaCha20のブロック関数
void chacha20_block(Chacha20* chacha20) {
    uint32_t initial_state[16];

    for (int i = 0; i < 16; i++) {
        initial_state[i] = chacha20->state[i];
    }

    for (int i = 0; i < ROUNDS / 2; i++) {
        // 奇数ラウンド
        quarter_round(&chacha20->state[0], &chacha20->state[4], &chacha20->state[8], &chacha20->state[12]);
        quarter_round(&chacha20->state[1], &chacha20->state[5], &chacha20->state[9], &chacha20->state[13]);
        quarter_round(&chacha20->state[2], &chacha20->state[6], &chacha20->state[10], &chacha20->state[14]);
        quarter_round(&chacha20->state[3], &chacha20->state[7], &chacha20->state[11], &chacha20->state[15]);

        // 偶数ラウンド
        quarter_round(&chacha20->state[0], &chacha20->state[5], &chacha20->state[10], &chacha20->state[15]);
        quarter_round(&chacha20->state[1], &chacha20->state[6], &chacha20->state[11], &chacha20->state[12]);
        quarter_round(&chacha20->state[2], &chacha20->state[7], &chacha20->state[8], &chacha20->state[13]);
        quarter_round(&chacha20->state[3], &chacha20->state[4], &chacha20->state[9], &chacha20->state[14]);
    }

    for (int i = 0; i < 16; i++) {
        chacha20->state[i] = (chacha20->state[i] + initial_state[i]) & 0xFFFFFFFF;
    }

XOR

攪拌後の内部状態をバイト列に直し、鍵ストリームとします。この鍵ストリームと平文をXORして、暗号文となります。

前述のとおり、上記の処理を1回実行するごとに512\ \text{bits}の鍵ストリームを得られるため、Counterの値をインクリメントしながら必要な回数だけ実行する必要があります。この際、鍵とNonceは毎回同じものを使用します。余ったキーストリームは破棄すればよく、平文の長さが512\ \text{bits}の整数倍である必要はありません。

実装

ほとんどの部分が再掲となりますが、今回の実装はこんな感じになりました。ところどころ、特にchacha20_cipher関数はもっとうまく実装できる気がしますが、とりあえずこれでよいでしょう。

本来は不要ですが、確認のために内部状態を表示するようにしています。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define ROUNDS 20
#define BLOCK_SIZE 64

typedef struct {
    uint32_t state[16];
} Chacha20;

// 内部状態を初期化する関数
void init_state(Chacha20* chacha20, const uint8_t* key, const uint8_t* nonce, uint32_t counter) {
    chacha20->state[0] = 0x61707865;  // "expa"（リトルエンディアン）
    chacha20->state[1] = 0x3320646e;  // "nd 3"（リトルエンディアン）
    chacha20->state[2] = 0x79622d32;  // "2-by"（リトルエンディアン）
    chacha20->state[3] = 0x6b206574;  // "te k"（リトルエンディアン）
    chacha20->state[4] = ((uint32_t*)key)[0];
    chacha20->state[5] = ((uint32_t*)key)[1];
    chacha20->state[6] = ((uint32_t*)key)[2];
    chacha20->state[7] = ((uint32_t*)key)[3];
    chacha20->state[8] = ((uint32_t*)key)[4];
    chacha20->state[9] = ((uint32_t*)key)[5];
    chacha20->state[10] = ((uint32_t*)key)[6];
    chacha20->state[11] = ((uint32_t*)key)[7];
    chacha20->state[12] = counter;
    chacha20->state[13] = ((uint32_t*)nonce)[0];
    chacha20->state[14] = ((uint32_t*)nonce)[1];
    chacha20->state[15] = ((uint32_t*)nonce)[2];

    // 内部状態の初期値を確認
    printf("内部状態の初期値:\n");
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%08X ", chacha20->state[4 * i + j]);
        }
        printf("\n");
    }
    printf("\n");
}

// 巡回左シフトする関数
uint32_t ROTL32(uint32_t value, int shift) {
    return (value << shift) | (value >> (32 - shift));
}

// ChaCha20のQuarter-Round関数
void quarter_round(uint32_t* a, uint32_t* b, uint32_t* c, uint32_t* d) {
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 16);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 12);
    *a = (*a + *b) & 0xFFFFFFFF; *d ^= *a; *d = ROTL32(*d, 8);
    *c = (*c + *d) & 0xFFFFFFFF; *b ^= *c; *b = ROTL32(*b, 7);
}

// Chacha20ブロック関数
void chacha20_block(Chacha20* chacha20) {
    uint32_t initial_state[16];

    for (int i = 0; i < 16; i++) {
        initial_state[i] = chacha20->state[i];
    }

    for (int i = 0; i < ROUNDS / 2; i++) {
        // 奇数ラウンド
        quarter_round(&chacha20->state[0], &chacha20->state[4], &chacha20->state[8], &chacha20->state[12]);
        quarter_round(&chacha20->state[1], &chacha20->state[5], &chacha20->state[9], &chacha20->state[13]);
        quarter_round(&chacha20->state[2], &chacha20->state[6], &chacha20->state[10], &chacha20->state[14]);
        quarter_round(&chacha20->state[3], &chacha20->state[7], &chacha20->state[11], &chacha20->state[15]);

        // 偶数ラウンド
        quarter_round(&chacha20->state[0], &chacha20->state[5], &chacha20->state[10], &chacha20->state[15]);
        quarter_round(&chacha20->state[1], &chacha20->state[6], &chacha20->state[11], &chacha20->state[12]);
        quarter_round(&chacha20->state[2], &chacha20->state[7], &chacha20->state[8], &chacha20->state[13]);
        quarter_round(&chacha20->state[3], &chacha20->state[4], &chacha20->state[9], &chacha20->state[14]);
    }

    for (int i = 0; i < 16; i++) {
        chacha20->state[i] = (chacha20->state[i] + initial_state[i]) & 0xFFFFFFFF;
    }

    printf("攪拌後の内部状態:\n");
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            printf("%08X ", chacha20->state[4 * i + j]);
        }
        printf("\n");
    }
    printf("\n");
}

void xor_encrypt(uint8_t* key_stream, const char* plaintext, unsigned char* ciphertext, size_t text_length) {
    for (size_t i = 0; i < text_length; i++) {
        ciphertext[i] = plaintext[i] ^ key_stream[i];
    }
}

// Chacha20暗号化/復号化関数
void chacha20_encrypt(uint8_t* key, uint8_t* nonce, uint32_t* counter, const char* plaintext, unsigned char* ciphertext) {
    Chacha20 chacha20;
    size_t message_len = strlen(plaintext);
    int blocks = (message_len + BLOCK_SIZE - 1) / BLOCK_SIZE;

    for (int i = 0; i < blocks; i++) {
        init_state(&chacha20, key, nonce, *counter + i);
        chacha20_block(&chacha20);
        if (i == blocks - 1) {
            xor_encrypt((uint8_t*)&chacha20.state, plaintext + i * BLOCK_SIZE, ciphertext + i * BLOCK_SIZE, message_len % BLOCK_SIZE);
        }
        else {
            xor_encrypt((uint8_t*)&chacha20.state, plaintext + i * BLOCK_SIZE, ciphertext + i * BLOCK_SIZE, BLOCK_SIZE);
        }
    }
}

int main() {
    // 数値の例
    uint8_t key[32] = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f };
    uint8_t nonce[12] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x4a, 0x00, 0x00, 0x00, 0x00 };
    uint32_t counter = 1;
    const char* plaintext = "Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it.";
    size_t message_len = strlen(plaintext);
    unsigned char* ciphertext = (unsigned char*)malloc(strlen(plaintext) * sizeof(unsigned char));

    chacha20_encrypt(key, nonce, &counter, plaintext, ciphertext);
    printf("Ciphertext: ");
    for (size_t i = 0; i < message_len; i++) {
        printf("%02x", ciphertext[i]);
    }
    printf("\n");

    free(ciphertext);

    return 0;
}

出力は次のとおりでした。

内部状態の初期値:
61707865 3320646E 79622D32 6B206574
03020100 07060504 0B0A0908 0F0E0D0C
13121110 17161514 1B1A1918 1F1E1D1C
00000001 00000000 4A000000 00000000

攪拌後の内部状態:
F3514F22 E1D91B40 6F27DE2F ED1D63B8
821F138C E2062C3D ECCA4F7E 78CFF39E
A30A3B8A 920A6072 CD7479B5 34932BED
40BA4C79 CD343EC6 4C2C21EA B7417DF0

内部状態の初期値:
61707865 3320646E 79622D32 6B206574
03020100 07060504 0B0A0908 0F0E0D0C
13121110 17161514 1B1A1918 1F1E1D1C
00000002 00000000 4A000000 00000000

攪拌後の内部状態:
9F74A669 410F633F 28FECA22 7EC44DEC
6D34D426 738CB970 3AC5E9F3 45590CC4
DA6E8B39 892C831A CDEA67C1 2B7E1D90
037463F3 A11A2073 E8BCFB88 EDC49139

Ciphertext: 6e2e359a2568f98041ba0728dd0d6981e97e7aec1d4360c20a27afccfd9fae0bf91b65c5524733ab8f593dabcd62b3571639d624e65152ab8f530c359f0861d807ca0dbf500d6a6156a38e088a22b65e52bc514d16ccf806818ce91ab77937365af90bbf74a35be6b40b8eedf2785e42874d

内部状態の初期値は、想定したとおりになっていますね。ちゃんと暗号化できているか、CyberChefで確認しておきます。

大丈夫そうですね。

おわりに

今回は共通鍵暗号を理解したいということで、ストリーム暗号ChaCha20のアルゴリズムを紹介し、C言語で実装しました。ChatGPTさまにもご協力いただき、なんとかなったはずです。現役の共通鍵暗号がﾁｮｯﾄﾜｶｯﾀと思うので、今回もやってよかったです。せっかくなので、Poly1305とChaCha20-Poly1305もそのうち勉強しようと思います。

脚注

  1. メンバが1つなので、こんなの定義しなくてよいと思います。 ↩︎

  2. 8ラウンドや12ラウンドもあり、20ラウンドの場合を特にChaCha"20"呼ぶそうです。 ↩︎

  3. ブロック暗号とは関係ありません。 ↩︎

Discussion