ストリーム暗号ChaCha20よる擬似乱数生成のRust実装について
近況
お久しぶりです。iPXのTCDの砂子です。 社員が増えてきたためかブログの記 事当番がなかなかまわってこないようなきがします。 以前に書いたのが 2018/07/29になるので半年ぶりになるのですね。
前回の記事を書いた時点では栃木在住だったのですが、本社勤務が決まった関 係で現在は東京都に引越しをしました。都内だとIT関連の勉強会なども通いや くすなり有益なことがおおいです。
さて、前回に引続きRust言語の話題となります。書籍なども一通り読み終え たのでかねてより目標にしていた疑似乱数生成の実装を行なってみました。
ChaCha20 stream cipher
どの疑似乱数生成器の実装しようかと考えているうちにGoogleの暗号化規格 「Andiantum」の記事が目にとまりました。
記事を読んでいるとその規格の一部にストリーム暗号ChaCha20が使用されて いることが分かります。ChaCha20はTLSの暗号方式にも採用されているようです。
ストリーム暗号とは音声通信や動画配信などを暗号化するために用 いられます。逐次発生するデータをその都度暗号化して流すので\"ストリーム\" が冠されていると覚えれば分かりやすいかと。
ちなみにブロック暗号はファイルなど大きさの定まったまとまりを暗号化す る暗号方式です。AESなどがこれにあたります。
疑似乱数にストリーム暗号が関係あるのか?となりますが、ストリーム暗号 はその実装で疑似乱数を発生するものがあります。そのためWikipediaのペー ジにもありますが疑似乱数を作るさいにストリーム暗号を利用ることがあり ます。
RFC8439 実装
開発者のサイトなどでC言語でかかれた参考ソースコードなどがありますが、 それをそのまま移植しては少々おもしろくありません。
そこでChaCha20の仕様はRFC8439 を参考にしました。途中までObsoleteされた RFC7539を参照していましたが、別記事などをみて間違いに気付きました。
ちなみにRFC8439の全部を実装するのではなく下記2章の途中までの実装しま す。
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Conventions Used in This Document . . . . . . . . . . . . 5
2. The Algorithms . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. The ChaCha Quarter Round . . . . . . . . . . . . . . . . 5
2.1.1. Test Vector for the ChaCha Quarter Round . . . . . . 6
2.2. A Quarter Round on the ChaCha State . . . . . . . . . . . 6
2.2.1. Test Vector for the Quarter Round on the ChaCha State 7
2.3. The ChaCha20 Block Function . . . . . . . . . . . . . . . 7
2.3.1. The ChaCha20 Block Function in Pseudocode . . . . . . 9
2.3.2. Test Vector for the ChaCha20 Block Function . . . . . 10
2.4. The ChaCha20 Encryption Algorithm . . . . . . . . . . . . 11
2.4.1. The ChaCha20 Encryption Algorithm in Pseudocode . . . 12
2.4.2. Example and Test Vector for the ChaCha20 Cipher . . . 12
今回はrustで開発するにあたりひとつのファイルでテストまで済ませていま す。再利用可能にするにはもうすこしモジュール構成などをしっかりしたほ うがよいのですが次の課題とします。
2.1. The ChaCha Quarter Round
これがこの暗号方式のキモになるラウンド関数です。ビット演算で情報を でたらめな状態にする関数です。
使われているビット演算は加算、排他的論理和(XOR)、回転(rotate)になり ます。
加算と回転はC言語での表現と異なるので注意が必要です。 加算は
overflow_add を使います。戻値は加算した値とくりあがりのタプルになっ
ているので0番目を指定します。因みに + をつかって実装すると
実行時にオーバーフローによるエラーとなります。循環シフトは符号無し
32bitにメソッドが予め存在するため特に問題ありません。
// 2.1. The ChaCha Quarter Round
// The basic operation of the ChaCha algorithm is the quarter round. It
// operates on four 32-bit unsigned integers, denoted a, b, c, and d.
// The operation is as follows (in C-like notation):
// 1. a += b; d ^= a; d <<<= 16;
// 2. c += d; b ^= c; b <<<= 12;
// 3. a += b; d ^= a; d <<<= 8;
// 4. c += d; b ^= c; b <<<= 7;
fn quarter_round(mut a: u32, mut b: u32, mut c: u32, mut d: u32) -> (u32, u32, u32, u32) {
a = a.overflowing_add(b).0;
d ^= a;
d = d.rotate_left(16);
c = c.overflowing_add(d).0;
b ^= c;
b = b.rotate_left(12);
a = a.overflowing_add(b).0;
d ^= a;
d = d.rotate_left(8);
c = c.overflowing_add(d).0;
b ^= c;
b = b.rotate_left(7);
(a, b, c, d)
}
2.2. A Quarter Round on the ChaCha State
こちらは2.1で実装したラウンド関数を16ワードの配列に適用する実装です。 chacha20のラウンド関数は4x4=16ワードの入力にたいして複数回適用します。こ の実装は16ワードのうち4ワードを指定してラウンド関数を実行します。
2.1でも関数で実装しましたが、関数呼出や配列ののコストなどが問題にな るためマクロ機能で実装したいのですが今回は対応しませんでした。
// 2.2. A Quarter Round on the ChaCha State
// The ChaCha state does not have four integer numbers: it has 16. So
// the quarter-round operation works on only four of them -- hence the
// name. Each quarter round operates on four predetermined numbers in
// the ChaCha state. We will denote by QUARTERROUND(x,y,z,w) a quarter-
// round operation on the numbers at indices x, y, z, and w of the
// ChaCha state when viewed as a vector. For example, if we apply
// QUARTERROUND(1,5,9,13) to a state, this means running the quarter-
// round operation on the elements marked with an asterisk, while
// leaving the others alone:
// 0 *a 2 3
// 4 *b 6 7
// 8 *c 10 11
// 12 *d 14 15
fn apply_quarter_round(x: usize, y: usize, z: usize, w: usize, words_16: Vec<u32>) -> Vec<u32> {
let old_a = words_16[x];
let old_b = words_16[y];
let old_c = words_16[z];
let old_d = words_16[w];
let (new_a, new_b, new_c, new_d) = quarter_round(old_a, old_b, old_c, old_d);
let mut ret = vec![0; 16];
ret[..16].clone_from_slice(&words_16[..16]);
ret[x] = new_a;
ret[y] = new_b;
ret[z] = new_c;
ret[w] = new_d;
ret
}
2.3. The ChaCha20 Block Function
このセクションは3つに関数を分割しました。
- setup~key~
- block~function~
- serialized
setup~keyは鍵~、カウンタ、Nonceから内部で使用する16ワードを鍵を作り ます。実装ではビット演算にmemクレートのtrasmuteを使用している箇所が あります。これは組み込みデータ型間でビット単位での変換を実現してい ます。4つの符号無し8bitのデータ型u8を1つの符号無し32bitに変換してい ます。これはpremitiveな操作になるためunsafeブロックで囲みます。
fn setup_key(key: Vec<u8>, counter: u32, nonce: Vec<u8>) -> Vec<u32> {
// The ChaCha20 state is initialized as follows:
let mut state: Vec<u32> = vec![0; 16];
// o The first four words (0-3) are constants: 0x61707865, 0x3320646e,
// 0x79622d32, 0x6b206574.
state[0] = 0x6170_7865;
state[1] = 0x3320_646e;
state[2] = 0x7962_2d32;
state[3] = 0x6b20_6574;
// o The next eight words (4-11) are taken from the 256-bit key by
// reading the bytes in little-endian order, in 4-byte chunks.
for i in 0..8 {
let idx_state = i + 4;
let idx_key = 4 * i;
unsafe {
state[idx_state] = mem::transmute::<[u8; 4], u32>([
key[idx_key],
key[idx_key + 1],
key[idx_key + 2],
key[idx_key + 3],
]);
}
}
// o Word 12 is a block counter. Since each block is 64-byte, a 32-bit
// word is enough for 256 gigabytes of data.
state[12] = counter;
// o Words 13-15 are a nonce, which should not be repeated for the same
// key. The 13th word is the first 32 bits of the input nonce taken
// as a little-endian integer, while the 15th word is the last 32
// bits.
for i in 0..3 {
let idx_state = 13 + i;
let idx_nonce = 4 * i;
unsafe {
state[idx_state] = mem::transmute::<[u8; 4], u32>([
nonce[idx_nonce],
nonce[idx_nonce + 1],
nonce[idx_nonce + 2],
nonce[idx_nonce + 3],
]);
}
}
state
}
block~functionはラウンド関数をsetupkeyで作成された16ワードに8回適~ 用します。そして、適用後の値と適用前の値を排他的論理和を取得します。
fn block_function(key: Vec<u8>, counter: u32, nonce: Vec<u8>) -> Vec<u32> {
// The ChaCha20 state is initialized as follows:
let mut state = setup_key(key, counter, nonce);
let mut working_state = state.clone();
for _ in 1..=10 {
working_state = apply_quarter_round(0, 4, 8, 12, working_state);
working_state = apply_quarter_round(1, 5, 9, 13, working_state);
working_state = apply_quarter_round(2, 6, 10, 14, working_state);
working_state = apply_quarter_round(3, 7, 11, 15, working_state);
working_state = apply_quarter_round(0, 5, 10, 15, working_state);
working_state = apply_quarter_round(1, 6, 11, 12, working_state);
working_state = apply_quarter_round(2, 7, 8, 13, working_state);
working_state = apply_quarter_round(3, 4, 9, 14, working_state);
}
for i in 0..16 {
state[i] = state[i].overflowing_add(working_state[i]).0;
}
state
}
最後にserializedを行ないます。
fn serialized(arr32: Vec<u32>) -> Vec<u8> {
let mut serialized: Vec<u8> = vec![0; arr32.len() * 4];
for i in 0..16 {
unsafe {
let arr8 = mem::transmute::<u32, [u8; 4]>(arr32[i]);
serialized[i * 4] = arr8[0];
serialized[i * 4 + 1] = arr8[1];
serialized[i * 4 + 2] = arr8[2];
serialized[i * 4 + 3] = arr8[3];
}
}
serialized
}
2.4. The ChaCha20 Encryption Algorithm
前述の3つの節の関数を使用して暗号化を実装します。
平文を64ワード毎に8ワードの鍵、4ワードのカウンタと4ワードのナンスで 生成した疑似乱数をXOR演算で暗号化してゆきます。
fn chacha20_encrypt(key: Vec<u8>, counter: u32, nonce: Vec<u8>, plaintext: Vec<u8>) -> Vec<u8> {
let mut encrypted_message = vec![0; plaintext.len()];
for j in 0..(plaintext.len() / 64) {
let key_stream = serialized(block_function(
key.clone(),
counter + j as u32,
nonce.clone(),
));
let block = &plaintext[j * 64..=(j * 64 + 63)];
for k in 0..64 {
encrypted_message[j * 64 + k] = block[k] ^ key_stream[k];
}
}
if plaintext.len() % 64 != 1 {
let j = plaintext.len() / 64;
let key_stream = serialized(block_function(
key.clone(),
counter + j as u32,
nonce.clone(),
));
let block = &plaintext[j * 64..plaintext.len()];
for k in 0..plaintext.len() % 64 {
encrypted_message[j * 64 + k] = block[k] ^ key_stream[k];
}
}
}
疑似乱数生成
さて、実装も一通りすんだところで疑似乱数の生成に取り掛かります。上記 のRFC8439では暗号化の仕様を定めています。疑似乱数生成の仕様ではあり ません。
疑似乱数を生成する方法はrustのrandクレートを参考にすることにしました。 また、この機能で生成した乱数を実装が正しくできたかの確認につかいます。
- impl BlockRngCore for ChaChaCore
- impl SeedableRng for ChaChaCore
ChaCha20の暗号処理で使用する下記3つの変数をそれぞれ下記のように割り 当てます。
- Key == Seed
- Nonce == 0
- conter == 乱数を生成でインクリメント
先ず、randクレートで正解の乱数を作成します。
use rand::{ChaChaRng, Rng, SeedableRng};
fn main() {
//let seed: &[_] = &[1, 2, 3, 4, 5, 6 , 7 ,8, 9, 10, 11, 12,13 ,14,15,16];
let seed: [u8; 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,
];
let mut rng: ChaChaRng = SeedableRng::from_seed(seed);
for _ in 0..40 {
println!("{}", rng.gen::<u32>());
}
}
結果は下記になります。
2100034873 1780073945 1996733837 1229642936 1876440458 3429555900 1283312818 2451892952 3888915243 2871222434 1777274431 1686095930 3929375269 765720497 2690787266 205609800 826456088 3517376173 1633444115 659440559 4126388728 1549512161 318568684 1551185194 1829242994 1564274385 609780125 1006636644 1593221275 3461963230 2135566861 3445265713 3693998658 3583134375 4018841452 997363241 914301792 3082742343 815587571 3806560462
同一のseedを使用して自作のChaCha20の実装で乱数を発生させます。
#[test]
fn test_generate_rng() {
let seed: Vec<u8> = vec![
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,
];
let nonce: Vec<u8> = vec![
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
];
let expected: Vec<u32> = vec![
2100034873, 1780073945, 1996733837, 1229642936, 1876440458, 3429555900, 1283312818,
2451892952, 3888915243, 2871222434, 1777274431, 1686095930, 3929375269, 765720497,
2690787266, 205609800, 826456088, 3517376173, 1633444115, 659440559, 4126388728,
1549512161, 318568684, 1551185194, 1829242994, 1564274385, 609780125, 1006636644,
1593221275, 3461963230, 2135566861, 3445265713, 3693998658, 3583134375, 4018841452,
997363241, 914301792, 3082742343, 815587571, 3806560462,
];
let r = block_function(seed.clone(), 0, nonce.clone());
for i in 0..16 {
assert_eq!(expected[i], r[i]);
}
let r = block_function(seed.clone(), 1, nonce.clone());
for i in 0..16 {
assert_eq!(expected[i + 16], r[i]);
}
}
結果が一致しました。
まとめ
なんとかRustでまとまったコーディングをすることができました。しかし、 RFCのセクション毎の実装をクリアすることに集中したため引数などのリス トをクローンしたりと及第点とは到底いえない状態です。
先ず、次の点を課題として認識しもう少し実装を磨こうと思います。
- マクロ機能
- ビット演算
- モジュール構成
クレートとして公開するようなことはないでしょうが、公開の方法などを調 べて整えるまでできれば言語の学習としては一段落でしょうか？
大学の卒業研究で暗号学的ハッシュ関数MD5の後継であるMD6の高階差分解析 がテーマでした。卒業から4年程たったときに当時の研究室に連絡を入れ、 自分が作成した卒業論文を入手して続きを研究しようと考えました。その時 は転職や転居などがあり結局それは有耶無耶になりました。
現在も暗号とはそれほど関係ない業務ですが、FPGA等を触る機会があります。 そのような技術で当時の卒業研究のテーマをやったらどの程度のことができ たのかと考えることがあります。その度にあの時から勉強を続けていたら よかったなと後悔することもあります。
長期に渡る知見を蓄えた場合にどのような世界が見えるのか？いまから始め るのは遅い気もしますが、一つのテーマに腰を据え知見を蓄えその状態に到 達したいとそう思います。
