ChaCha20をRustで実装してみた

はじめに

暗号シリーズ
今回は疑似乱数で一番有名なChaCha20を解説していく
以下のような人向け

1. ChaCha20ってなに
2. ChaCha20は知っているけどアルゴリズムは知らない
3. 疑似乱数の基本を知りたい

Rustで実装していく。

ソースコードはここ

https://github.com/watason/angou-rs

ChaCha20とは

djb作共通鍵暗号アルゴリズムSalsa20の後継。
普通に共通鍵暗号として使用されることはほとんどなく
（..多分ないけど有ったら教えてほしい）、
実用上では疑似乱数アルゴリズムとして使用されている。

追記：SSHやTLS、IPSecでちゃんと使用されている とご教授頂いた。
AES-GCMに勝ってるのすげ～。
ちゃんと現役のアルゴリズムなので訂正。

ハードウェアのサポートなしのソフトウェアアルゴリズムのみで言えば、AESよりも高速らしい共通鍵暗号アルゴリズム。
（AESが気になる人はここで解説してるので見て）

アルゴリズム部分では共通鍵暗号として解説していき、その後、疑似乱数アルゴリズムとしての利用方法の説明を行う。
疑似乱数アルゴリズムとしての利用では、Linuxで使用されている。
（Linux疑似乱数アルゴリズムの調査は別記事で作成する）

疑似乱数

疑似乱数とは、ざっくり言えば
入力が同じであれば、出力は同じになる乱数らしきもの
である。
それだけ聞くと、乱数とは程遠いものに思えるが現代ではそれを乱数として利用できている。

なぜなら実運用上では、真正乱数と言われる計算に時間がかかるが完全に予測できない乱数を作成し、その値を基にして疑似乱数を作成するから。
つまり、

1. 真正乱数（=完全に推測不可能な乱数）作成　←超重要処理！！
2. 疑似乱数生成器を作成
3. それを乱数生成器に入力する
4. 値を出力

という流れになる。

現状速度面を考慮すると、大体のPCで同じ手順を行っている。
なので実質、乱数＝疑似乱数と考えて良い。

勘のいい人は理解していると思うが、真正乱数が判明したら全ての暗号、ハッシュ等が無意味になったと思っていい。
それだけ真正乱数部分は重要になる。

最後に少しだけ同じ乱数を発生させる実験を行うので、興味がでたら読んでほしい。

アルゴリズム

以下ではChaChaで使用される暗号化アルゴリズムについて解説していく。RFC7539を読んで解説する。

パラメータ

暗号系あるあるだが、事前にいくつかパラメータが設定されている。

変数	データサイズ	説明
Word	4Byte	最小単位
Block	64Byte	暗号化アルゴリズムの入力最大単位。データが大きい場合、ブロック数が増える
Key	32Byte	秘密鍵　データ一つにつき一つ
nonce	12Byte	適当な定数　同上
counter	1Byte	ブロック用カウンター
const	12Byte	ブロック初期化用定数

ざっくりとした説明だが、これで読み進められると思う。

定数

初期化設定の際、
constは以下の値を使用する。

const

    block[0] = 0x61707865; 
    block[1] = 0x3320646e; 
    block[2] = 0x79622d32; 
    block[3] = 0x6b206574; 

これは"expand 32byte-k"のASCIIコードを4分割したもの。
暗号系では設計者がバックドアを仕掛けることが容易なので、それに対して種も仕掛けもない定数を決めておく必要がある。


ただ、定数を使用するというのはバックドアの危険性が消えるわけではないので、
論文が言っているから信じよう、
この人が言っているから信じよう、
とかではなく仕組みを理解して信じる必要がある。


できれば、

• 無意味な文字列
• 素数のルート
• 無理数の何桁目

等。


今回で言えば、"expand 32byte-k"を見て完全に無意味な文字列であるからバックドアではなく安心できる、みたいな話。
特にセキュリティ関係の人は、気にしすぎて困ることはないから覚えておいてほしい。

ちなみに、上記ですらバックドアの可能性があるらしい
...もうどうしろと？

まぁここまで言っておいてなんだけど、大体は大丈夫だとは思う。
なぜなら、自分より暗号学で優れた人たちが審査しているからね！


...人で判断してたわ。
うん　次に進もう。

QUARTERROUND

ChaChaの最も重要な部分。
他の暗号系で言えば混合関数にあたる。
4wordの入力をぐちゃぐちゃに混ぜる関数。

quarter

fn quarter_round(state: &mut [u32], i: usize, j: usize, k: usize, l: usize) {
    /*
    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;
    */
    //let rot32 = |x: u32, n: u32| x << n | x >> (32 - n);
    let mut a = state[i];
    let mut b = state[j];
    let mut c = state[k];
    let mut d = state[l];
    a = a.wrapping_add(b);
    d ^= a;
    d = d.rotate_left(16);
    c = c.wrapping_add(d);
    b ^= c;
    b = b.rotate_left(12);
    a = a.wrapping_add(b);
    d ^= a;
    d = d.rotate_left(8);
    c = c.wrapping_add(d);
    b ^= c;
    b = b.rotate_left(7);寄与
    state[i] = a;
    state[j] = b;
    state[k] = c;
    state[l] = d;
  }

基礎であり、奥義みたいな存在。
処理内容自体を観察してみると、

1. a,cをb,dを足して上書き変更
2. それを使ってd,bをマスク
3. d,bをシフト
   となっている。

あえて処理工程を偏らせることで、より攪拌する感じだと思う。
以外にも処理の簡単さに比べてちゃんと混ざる。

init

初期化処理
細かなことは色んなサイトや論文内で書かれているから省略。
ざっくり言えば、

$$Block_i(=64Byte) = const | key |counter | nonce$$

それぞれ、

const = 先に説明したやつ。ブロック毎で同じ
key = 真正乱数。ブロック毎で同じ。
counter = ブロックのインデックス。変更可能。デフォルトは0から順にインクリメントする
nonce = なんか適当な数。ブロック毎で同じ。

実装したものがこれ

init

fn init(key: &[u32], counter: u32, nonce: &[u32]) -> Block {
    /*
    The ChaCha20 state is initialized as follows:

    o  The first four words (0-3) are constants: 0x61707865, 0x3320646e,
       0x79622d32, 0x6b206574.

    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.

    o  Word 12 is a block counter.  Since each block is 64-byte, a 32-bit
       word is enough for 256 gigabytes of data.

    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.

        cccccccc  cccccccc  cccccccc  cccccccc
        kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
        kkkkkkkk  kkkkkkkk  kkkkkkkk  kkkkkkkk
        bbbbbbbb  nnnnnnnn  nnnnnnnn  nnnnnnnn

        c=constant k=key b=blockcount n=nonce */

    /*const 0x61707865, 0x3320646e,
      0x79622d32, 0x6b206574.
    */
    if !(key.len() == 8 && nonce.len() == 3) {
      panic!("block key size or nonce is not varid");
    }
    let mut block: Block = [0; 16];
    block[0] = 0x61707865;
    block[1] = 0x3320646e;
    block[2] = 0x79622d32;
    block[3] = 0x6b206574;

    (0..key.len()).into_iter().for_each(|i| {
      block[4 + i] = key[i];
    });
    block[12] = counter;

    (0..nonce.len()).into_iter().for_each(|i| {
      block[13 + i] = nonce[i];
    });

    println!("block init is {:x?}", block);
    block
  }

...気が付いた人いる？
実は、ブロック毎で違いはcounterのみ。
つまり初期化処理のみではブロック毎の値はほぼ同じになってしまうんだな～これ

論文から抜粋

   First block setup:
       61707865  3320646e  79622d32  6b206574
       03020100  07060504  0b0a0908  0f0e0d0c
       13121110  17161514  1b1a1918  1f1e1d1c
       00000001  00000000  4a000000  00000000

   Second block setup:
       61707865  3320646e  79622d32  6b206574
       03020100  07060504  0b0a0908  0f0e0d0c
       13121110  17161514  1b1a1918  1f1e1d1c
       00000002  00000000  4a000000  00000000

いやいやいや　同じすぎでしょ！


見ての通りカウンターの部分のみ違うだけ、残りはすべて同じ。
なんならカウンターの値ですら、2bitしか違いがない。


めちゃくちゃ不安になったでしょう。
安心してほしい、ちゃんとめちゃくちゃになるから。
実装していてめちゃくちゃ不安になって手が止まったのは内緒

BLOCK FUNCTION

初期化処理を行ったブロックに対して、
QUARTERROUND関数8セットを10回回す。
4セット部分は縦列で、後半4セットは斜めを対象に攪拌を行う。
最後に初期値とのXORを取る。

Block

  fn block(key: &[u32], counter: u32, nonce: &[u32]) -> Block {
    let init = ChaCha::init(key, counter, nonce);
    let mut state = init;
    let inner_block = |state: &mut Block| {
      /*
       inner_block (state):
        Qround(state, 0, 4, 8,12)
        Qround(state, 1, 5, 9,13)
        Qround(state, 2, 6,10,14)
        Qround(state, 3, 7,11,15)
        Qround(state, 0, 5,10,15)
        Qround(state, 1, 6,11,12)
        Qround(state, 2, 7, 8,13)
        Qround(state, 3, 4, 9,14)
        end
      */
      //
      ChaCha::quarter_round(state, 0, 4, 8, 12);
      ChaCha::quarter_round(state, 1, 5, 9, 13);
      ChaCha::quarter_round(state, 2, 6, 10, 14);
      ChaCha::quarter_round(state, 3, 7, 11, 15);

      ChaCha::quarter_round(state, 0, 5, 10, 15);
      ChaCha::quarter_round(state, 1, 6, 11, 12);
      ChaCha::quarter_round(state, 2, 7, 8, 13);
      ChaCha::quarter_round(state, 3, 4, 9, 14);
    };

    for i in 0..10 {
      inner_block(&mut state);
    }
    state
      .iter_mut()
      .enumerate()
      .for_each(|(i, block)| *block = (*block).wrapping_add(init[i]));
    state
  }

1ブロック単位で言えばこれで暗号化は完了。

不安に思っていた初期ブロックはこれを通すとこうなる。

   First block after block operation:
       f3514f22  e1d91b40  6f27de2f  ed1d63b8
       821f138c  e2062c3d  ecca4f7e  78cff39e
       a30a3b8a  920a6072  cd7479b5  34932bed
       40ba4c79  cd343ec6  4c2c21ea  b7417df0

   Second block after block operation:
       9f74a669  410f633f  28feca22  7ec44dec
       6d34d426  738cb970  3ac5e9f3  45590cc4
       da6e8b39  892c831a  cdea67c1  2b7e1d90
       037463f3  a11a2073  e8bcfb88  edc49139

...たった2bitの違いだけでほとんど別物になっている
凄いな～　
混ぜ方と回転方向でちゃんとシャッフルされるんだから。

少しの違いで値が別物になると聞いたら何か思いつかないだろうか？
そう　ハッシュ関数。
ここでの攪拌をそのままハッシュ関数として利用したものが、Blakeというハッシュ関数になる。
気になった人は、その後継であるBlake2の記事を書いているので参考にしてほしい。

SERIALIZE

暗号バイトをリトルエンディアンに変換する。

to_LE

  pub fn serialize(state: &[u32]) -> Vec<u8> {
    state
      .iter()
      .flat_map(|x| x.to_le_bytes())
      .collect::<Vec<u8>>()
  }

論文で書かれていたから作成したけど、内部で変換しているから実装では使っていない。
rustではそのままto_le_bytesを使えば良し！

ChaCha20_Encrypt

上記の関数等を使用してバイト列を暗号にしていく。
少しだけ処理が加わっているが処理内容に変わりはない。


一言で言えばバーナム暗号^[1]を入力バイト列分行っていく感じ。
やっぱりバーナム暗号は最強！

論文から抜粋

     chacha20_encrypt(key, counter, nonce, plaintext):
        for j = 0 upto floor(len(plaintext)/64)-1
           key_stream = chacha20_block(key, counter+j, nonce)
           block = plaintext[(j*64)..(j*64+63)]
           encrypted_message +=  block ^ key_stream
           end
        if ((len(plaintext) % 64) != 0)
           j = floor(len(plaintext)/64)
           key_stream = chacha20_block(key, counter+j, nonce)
           block = plaintext[(j*64)..len(plaintext)-1]
           encrypted_message += (block^key_stream)[0..len(plaintext)%64]
           end
        return encrypted_message
        end

処理の流れを簡単に説明すると、

1. 入力バイト列を64バイト毎に秘密鍵を作成
2. 秘密鍵と入力バイト列をXOR
3. リトルエンディアンで出力

となる。

chacha20_encrypt

fn encode(key: &[u32], counter: u32, nonce: &[u32], plain_text: &[u8]) -> Vec<u8> {
    let mut encrypt_message = plain_text
      .chunks(64)
      .enumerate()
      .flat_map(|(i, chunk)| {
        println!("encrypt chunk size is {}", chunk.len());
        let key_stream = ChaCha::block(key, counter + i as u32, nonce)
          .iter()
          .flat_map(|x| x.to_le_bytes())
          .collect::<Vec<u8>>();
        let mut chunk = chunk.clone().to_vec();
        println!("key stream is {:x?}", key_stream);
        println!("chunk {} is {:x?}", i, chunk);
        for (a, b) in chunk.iter_mut().zip(key_stream.iter()) {
          *a ^= b;
        }
        println!("{} block result is {:x?}", i, chunk);
        chunk
      })
      .collect::<Vec<u8>>();
    encrypt_message
  }

実装に関しては、
最後の暗号ブロックで64バイトに足りなくなる可能性があるけど、Rustのchunksを利用すれば最大バイト分持ってきてくれるので便利！
（134バイトなら134 = 64 + 64 + 6 となりブロック3個で、最後のブロックは6バイトになる）
あとは、zip関数が入力バイトと鍵バイトを揃えてくれるから簡単！

テスト

RFCに記載されているテストベクターを参考にテストする。
QUARTERROUNDのテスト、
1ブロックのテスト、
ストリーム暗号のテスト
を記載している。
テストベクターが用意されているのありがてぇ！
感謝！！

test

#[cfg(test)]
mod test {
  use rand_chacha::{rand_core::SeedableRng, ChaCha20Rng, ChaChaRng};

  use super::*;

  #[test]
  fn quarter_test() {
    /*
    o  a = 0x11111111
    o  b = 0x01020304
    o  c = 0x9b8d6f43
    o  d = 0x01234567
    o  c = c + d = 0x77777777 + 0x01234567 = 0x789abcde
    o  b = b ^ c = 0x01020304 ^ 0x789abcde = 0x7998bfda
    o  b = b <<< 7 = 0x7998bfda <<< 7 = 0xcc5fed3c




    o  a = 0xea2a92f4
    o  b = 0xcb1cf8ce
    o  c = 0x4581472e
    o  d = 0x5881c4bb
    */

    let mut state: [u32; 4] = [0x11111111, 0x01020304, 0x9b8d6f43, 0x01234567];
    let ans: [u32; 4] = [0xea2a92f4, 0xcb1cf8ce, 0x4581472e, 0x5881c4bb];
    ChaCha::quarter_round(&mut state, 0, 1, 2, 3);
    assert_eq!(state, ans);
  }

  #[test]
  fn block_test() {
    /*

    For a test vector, we will use the following inputs to the ChaCha20
    block function:

    o  Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:
       14:15:16:17:18:19:1a:1b:1c:1d:1e:1f.  The key is a sequence of
       octets with no particular structure before we copy it into the
       ChaCha state.

    o  Nonce = (00:00:00:09:00:00:00:4a:00:00:00:00)

    o  Block Count = 1.

    After setting up the ChaCha state, it looks like this:

    ChaCha state with the key setup.

        61707865  3320646e  79622d32  6b206574
        03020100  07060504  0b0a0908  0f0e0d0c
        13121110  17161514  1b1a1918  1f1e1d1c
        00000001  09000000  4a000000  00000000

    After running 20 rounds (10 column rounds interleaved with 10
    "diagonal rounds"), the ChaCha state looks like this:

    ChaCha state after 20 rounds

        837778ab  e238d763  a67ae21e  5950bb2f
        c4f2d0c7  fc62bb2f  8fa018fc  3f5ec7b7
        335271c2  f29489f3  eabda8fc  82e46ebd
        d19c12b4  b04e16de  9e83d0cb  4e3c50a2

    Finally, we add the original state to the result (simple vector or
    matrix addition), giving this:

    ChaCha state at the end of the ChaCha20 operation

        e4e7f110  15593bd1  1fdd0f50  c47120a3
        c7f4d1c7  0368c033  9aaa2204  4e6cd4c3
        466482d2  09aa9f07  05d7c214  a2028bd9
        d19c12b5  b94e16de  e883d0cb  4e3c50a2
     */
    let le_to_u32 = |x: &[u8]| {
      let mut ret = 0u32;
      //println!("le is {:x?} ", x);
      for x in x.iter().enumerate() {
        ret ^= (*x.1 as u32) << (8u32 * x.0 as u32);
      }
      ret
    };
    let be_to_u32 = |x: &[u8]| {
      let mut ret = 0u32;
      for x in x.iter().enumerate() {
        ret += (*x.1 as u32) << (8u32 * (3 - x.0 as u32));
      }
      ret
    };

    let key = hex::decode("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f")
      .expect("key is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let nonce = hex::decode(b"000000090000004a00000000")
      .expect("nonce is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let counter = 1u32;
    let ans: Vec<u32> = "e4e7f110  15593bd1  1fdd0f50  c47120a3
            c7f4d1c7  0368c033  9aaa2204  4e6cd4c3
            466482d2  09aa9f07  05d7c214  a2028bd9
            d19c12b5  b94e16de  e883d0cb  4e3c50a2"
      .split_whitespace()
      .map(|x| {
        let x = hex::decode(x).expect("ans decode fail");
        let ret = u32::from_be_bytes(x.try_into().unwrap());
        ret
      })
      .collect();
    //println!("ans is {:x?}", ans);
    println!(
      "key is {:x?} , nonce is {:x?} , counter is {}",
      key, nonce, counter
    );
    let chacha = ChaCha::block(&key, counter, &nonce);
    println!("block vec is {:x?}", chacha);
    assert_eq!(ans, chacha);
    println!("serialize block is {:x?}", ChaCha::serialize(&chacha));
  }

  #[test]
  fn encode_test() {
    /*
         For a test vector, we will use the following inputs to the ChaCha20
       block function:

       o  Key = 00:01:02:03:04:05:06:07:08:09:0a:0b:0c:0d:0e:0f:10:11:12:13:
          14:15:16:17:18:19:1a:1b:1c:1d:1e:1f.

       o  Nonce = (00:00:00:00:00:00:00:4a:00:00:00:00).

       o  Initial Counter = 1.

       We use the following for the plaintext.  It was chosen to be long
       enough to require more than one block, but not so long that it would
       make this example cumbersome (so, less than 3 blocks):

      Plaintext Sunscreen:
      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.





    Nir & Langley                 Informational                    [Page 11]

    RFC 7539                   ChaCha20 & Poly1305                  May 2015


       The following figure shows four ChaCha state matrices:

       1.  First block as it is set up.

       2.  Second block as it is set up.  Note that these blocks are only
           two bits apart -- only the counter in position 12 is different.

       3.  Third block is the first block after the ChaCha20 block
           operation.

       4.  Final block is the second block after the ChaCha20 block
           operation was applied.

       After that, we show the keystream.

       First block setup:
           61707865  3320646e  79622d32  6b206574
           03020100  07060504  0b0a0908  0f0e0d0c
           13121110  17161514  1b1a1918  1f1e1d1c
           00000001  00000000  4a000000  00000000

       Second block setup:
           61707865  3320646e  79622d32  6b206574
           03020100  07060504  0b0a0908  0f0e0d0c
           13121110  17161514  1b1a1918  1f1e1d1c
           00000002  00000000  4a000000  00000000

       First block after block operation:
           f3514f22  e1d91b40  6f27de2f  ed1d63b8
           821f138c  e2062c3d  ecca4f7e  78cff39e
           a30a3b8a  920a6072  cd7479b5  34932bed
           40ba4c79  cd343ec6  4c2c21ea  b7417df0

       Second block after block operation:
           9f74a669  410f633f  28feca22  7ec44dec
           6d34d426  738cb970  3ac5e9f3  45590cc4
           da6e8b39  892c831a  cdea67c1  2b7e1d90
           037463f3  a11a2073  e8bcfb88  edc49139

       Keystream:
       22:4f:51:f3:40:1b:d9:e1:2f:de:27:6f:b8:63:1d:ed:8c:13:1f:82:3d:2c:06
       e2:7e:4f:ca:ec:9e:f3:cf:78:8a:3b:0a:a3:72:60:0a:92:b5:79:74:cd:ed:2b
       93:34:79:4c:ba:40:c6:3e:34:cd:ea:21:2c:4c:f0:7d:41:b7:69:a6:74:9f:3f
       63:0f:41:22:ca:fe:28:ec:4d:c4:7e:26:d4:34:6d:70:b9:8c:73:f3:e9:c5:3a
       c4:0c:59:45:39:8b:6e:da:1a:83:2c:89:c1:67:ea:cd:90:1d:7e:2b:f3:63






    Nir & Langley                 Informational                    [Page 12]

    RFC 7539                   ChaCha20 & Poly1305                  May 2015


       Finally, we XOR the keystream with the plaintext, yielding the
       ciphertext:

      Ciphertext Sunscreen:
      000  6e 2e 35 9a 25 68 f9 80 41 ba 07 28 dd 0d 69 81  n.5.%h..A..(..i.
      016  e9 7e 7a ec 1d 43 60 c2 0a 27 af cc fd 9f ae 0b  .~z..C`..'......
      032  f9 1b 65 c5 52 47 33 ab 8f 59 3d ab cd 62 b3 57  ..e.RG3..Y=..b.W
      048  16 39 d6 24 e6 51 52 ab 8f 53 0c 35 9f 08 61 d8  .9.$.QR..S.5..a.
      064  07 ca 0d bf 50 0d 6a 61 56 a3 8e 08 8a 22 b6 5e  ....P.jaV....".^
      080  52 bc 51 4d 16 cc f8 06 81 8c e9 1a b7 79 37 36  R.QM.........y76
      096  5a f9 0b bf 74 a3 5b e6 b4 0b 8e ed f2 78 5e 42  Z...t.[......x^B
      112  87 4d                                            .M

         */
    let le_to_u32 = |x: &[u8]| {
      let mut ret = 0u32;
      //println!("le is {:x?} ", x);
      for x in x.iter().enumerate() {
        ret ^= (*x.1 as u32) << (8u32 * x.0 as u32);
      }
      ret
    };
    let be_to_u32 = |x: &[u8]| {
      let mut ret = 0u32;
      for x in x.iter().enumerate() {
        ret += (*x.1 as u32) << (8u32 * (4 - x.0 as u32));
      }
      ret
    };

    let key = hex::decode("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f")
      .expect("key is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let nonce = hex::decode(b"000000000000004a00000000")
      .expect("nonce is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let counter = 1u32;
    let plain_text = b"Ladies and Gentlemen of the class of '99: If I could offer you only one tip for the future, sunscreen would be it.";
    let ans = hex::decode("6e2e359a2568f98041ba0728dd0d6981e97e7aec1d4360c20a27afccfd9fae0bf91b65c5524733ab8f593dabcd62b3571639d624e65152ab8f530c359f0861d807ca0dbf500d6a6156a38e088a22b65e52bc514d16ccf806818ce91ab77937365af90bbf74a35be6b40b8eedf2785e42874d").expect("stream ans is error");
    //let ans = ans.chunks(4).map(le_to_u32).collect::<Vec<u32>>();
    println!("plain text is {:x?} ", plain_text);
    let encode_text = ChaCha::encode(&key, counter, &nonce, plain_text);
    println!("encode text is {:x?}", encode_text);
    assert_eq!(ans, encode_text);
  }
}

ChaChaを用いた乱数生成

さて、ここまで読んでくれたということは、ChaChaか暗号系にかなり興味があるんでしょうね。
...無くても読めるものなんだろうか？
もし無くても、ここまで読んで少しでも興味が出てくれたら嬉しい。

どちらにしても、読んでもらえたなら書いたかいがある！
感謝！


閑話休題

ChaChaを用いた乱数生成の処理について検証していく。
手順は

1. ライブラリの内容を把握
2. 同様のパラメータで実装&出力
3. テストで両方を比較

で行っていく。
参考にしたライブラリはrandcrate。

先に書いておくと、1Block_functionを以下のパラメータで実行する。

key(=seed) =固定の乱数値。バレたら終わりの値
counter = 0
nonce = 0 

rand

rustのrand_chachaというクレートが存在するので、そちらの実装を覗き見してみると、ChaCha20Rngというstructが存在する。
randに関してはここを読むと良い。

https://rust-random.github.io/book/

特にここでChaCha20Rngの説明をしている

https://docs.rs/rand_chacha/latest/rand_chacha/struct.ChaCha20Rng.html

読むと、SeedableRngで初期化すると乱数のみ初期化される。
実装を見てみると、seedを入れた場合他を全て0初期化したものと同じみたい。
これは実質counter,nonceをゼロ初期化したものと同義。

https://docs.rs/rand_chacha/latest/src/rand_chacha/chacha.rs.html#100-106

サンプルを実行してみる。

rand_chacha20

    use rand::{Rng, SeedableRng};
    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 ans: ChaCha20Rng = SeedableRng::from_seed(seed);
    let ans = (0..16)
      .into_iter()
      .map(|x| ans.gen::<u32>())
      .collect::<Vec<u32>>();

シードはテストベクターに使ったもの、
出力バイト数は1ブロックの16個にしておく。

実装

2つの実装を合わせる。
ライブラリのほうは配列だけど、それ以外は違いなし。

#[test]
  fn pseudorandom_test() {
    let le_to_u32 = |x: &[u8]| {
      let mut ret = 0u32;
      //println!("le is {:x?} ", x);
      for x in x.iter().enumerate() {
        ret ^= (*x.1 as u32) << (8u32 * x.0 as u32);
      }
      ret
    };



    use rand::{Rng, SeedableRng};
    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 ans: ChaCha20Rng = SeedableRng::from_seed(seed);
    let ans = (0..16)
      .into_iter()
      .map(|x| ans.gen::<u32>())
      .collect::<Vec<u32>>();



    let key = hex::decode("000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f")
      .expect("key is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let nonce = hex::decode(b"000000000000000000000000")
      .expect("nonce is invalid")
      .chunks(4)
      .map(le_to_u32)
      .collect::<Vec<u32>>();
    let counter = 0u32;

    let pseudo = ChaCha::block(&key, counter, &nonce);
    assert_eq!(ans, pseudo);
  }

無事通っている。
逆に言えば初期乱数が分かっていれば...

怖いね。

ちなみにそれら真正乱数はエントロピーと言うものが使用されており、rand_chacha（Linux上）では、/dev/random^[2]の乱数をエントロピーとして使用されている。

Linuxでの真正乱数...と言われているけど、/dev/random内部ではChaChaが使われているので、実際はさらに内部の乱数がエントロピーを担当している。


と思いきや、
さらにさらに、それすらもBlake2sハッシュ関数のハッシュで作成されているので、その入力がエントロピーを担当している。

...マトリョーシカかな？

そのエントロピーは、ハードウェアのノイズとかを使用しており、できる限りわかり難くされている。

Linuxの乱数についても調査しており、長くなるので別の記事にする。

まとめ

ChaChaの実装自体はかなり簡単にできた。
データの攪拌部分も複雑ではなく、非常にシンプルなものになっている。
暗号を試しに実装する場合、非常におすすめだと思う！

一応、勘違いしないでほしいのだが、（AESもそうだけど）
簡単に作れる=強度や仕組みが弱い、という意味ではない。
効率的で無駄がないから簡単にすることができている、と考えてほしい。

混合関数に関してもChaChaを基にした暗号系やハッシュはたくさんある。
簡単にランダムな数が生成できるなら使ったほうが良いに決まっているし、そこに古さは関係ない。

ただ欠点もある。
それを参考にして作ったものは、同じ脆弱性を抱える可能性が高くなるという点。
さながら、同じ遺伝子の生物は同じ感染病にかかりやすいように、脆弱性には常に気を付ける必要はある。

...まぁそんなこと作っている人たちはわかっているから、気にしなくても推奨されているやつ使えばいいと思うけどね。

..zennではじめてちゃんと記事書いたけど、悪くないな。

参照文献

感謝！

https://datatracker.ietf.org/doc/html/rfc7539

https://docs.rs/rand_chacha/latest/src/rand_chacha/chacha.rs.html

脚注

1. 乱数をXORするだけの暗号

2. Linuxの真正乱数として使われている