ストリーム暗号chachaをC++で実装した

卒業研究でchachaの平文回復攻撃についてやっています。そのためchahcaを実装しなければなりません。

調べてみると、誰かが書いたコードが転がっていますが、私が書き慣れているC++で書かれているものはなかったので、他のコードを参考にしつつ実装してみました。

chachaとは？

chahcaはストリーム暗号の一つで、 Salsa20から派生した暗号です。

更にchachaをベースとして、暗号学的ハッシュ関数であるBLAKEに発展しています。

Inital Stateについて

chahcaの初期状態は以下のようになっています。初期状態のことをInital Stateと呼びます。

1ワード32bitで、全体として512bitあります。

Consは定数で、 ”expand 32-byte k “をASCIIコードに変換したものを、32bitずつに切って4ワードとし、Inital Stateに代入します。

Keyは秘密鍵で、設定可能です。

Posはストリーム位置です。一個のInital Stateで暗号化できる平文は64バイトなので、それ以上の平文の場合は、Posを1ずつ増やしてInital Stateを変えていきます。

Nonceは、使い捨ての値のことです。これも設定可能です。

Quarter Roundについて

Inital Stateをかき混ぜる操作をします。

Salsa20との違いは、ビットシフトのみです。C言語の表記だと、以下の通り。

a ⊞= b; d ⊕= a; d <<<= 16;
c ⊞= d; b ⊕= c; b <<<= 12;
a ⊞= b; d ⊕= a; d <<<= 8;
c ⊞= d; b ⊕= c; b <<<= 7;

⊞は2^32を法とする加算のことです。要するに

\[(x + y) mod 2^{32} \]

を表します。

⊕はXOR、<<<=は左ビットシフトを表します。

そして、chachaにおいては、Stateに以下の操作を加えます。

これは全体で2roundsあるのでdouble-roundと呼ぶらしいです。

// 奇数ラウンド
QR ( 0, 4, 8, 12)     // 1st column
QR ( 1, 5, 9, 13)     // 2nd column
QR ( 2, 6, 10, 14)    // 3rd column
QR ( 3, 7, 11, 15)    // 4th column
// 偶数ラウンド
QR ( 0, 5, 10, 15)    // 対角線1 (主対角線）
QR ( 1, 6, 11, 12)    // 対角線2
QR ( 2, 7, 8, 13)     // 対角線3
QR ( 3, 4, 9, 14)     // 対角線4

chachaではこれを10回繰り返します。つまり、chachaは20ラウンドあります。

暗号化手順

最後に暗号化手順を示します。

1. Inital Stateにkeyとnonceを代入する。
2. Inital StateをQRに通し、出力されたStateをQRに通し・・・というものを10回繰り返す。
3. 最終的に出力されたStateとInital Stateを2^32を法とする加算をする。これがkey streamとなる。
4. key streamと平文をXORすると暗号文ができる。

C++での実装

参考にしたコードは以下の2つです。

[blogcard url=”http://sonickun.hatenablog.com/entry/2016/04/03/183220″]

こちらはpythonで書かれたもの。CTFの問題を解くために書かれたものです。

[blogcard url=”https://asecuritysite.com/encryption/chacha”]

こちらは鍵とnonceを設定するとkey streamを出力してくれるサイト。下にjavascriptで書かれたコードがあります。

そして、自分で書いたコードは以下の通り。

github:https://github.com/ateruimashin/chacha.git

chacha自体の実装はchacha関数です。

main関数内は、keyを作成したり、後々解析するためにファイル出力をしたりしています。

多分これでちゃんと動きますが、提案者論文内にtest vectorがないのでどうなんだろうという感じ。多分合ってるはず。

おまけ:実装各所の説明

来年の私のためにも実装各所の説明を書いていきます。大体はコメントに書いたとおりです。

10行目~17行目

[cpp] //出典:https://boringssl.googlesource.com/boringssl/+/master/crypto/chacha/chacha.c #define ROTL(a,b) (((a) << (b)) | ((a) >> (32 – (b)))) #define QR(a, b, c, d) ( \ a += b, d ^= a, d = ROTL(d,16), \ c += d, b ^= c, b = ROTL(b,12), \ a += b, d ^= a, d = ROTL(d, 8), \ c += d, b ^= c, b = ROTL(b, 7)) #define ROUNDS 20 [/cpp]

QRの実装とROUND数を設定しています。

ROTLは左ビットシフトさせたあと、はみ出た左側のビットを、左ビットシフトさせたものにORしています。これでぐるっと一周してビットシフトできます。

19行目~21行目

[cpp] uint32_t plus32(uint32_t x,uint32_t y){ return (x+y) & 0xffffffff; } [/cpp]

2^32を法とする加算を関数化したものです。uint32_tは32bit符号なし整数です。

[blogcard url=”https://cpprefjp.github.io/reference/cstdint/uint32_t.html”]

23行目~35行目

[cpp] array<uint32_t,32> make_array_key(string s){ array<uint32_t,32> key; int count = 0; for(int i=0;i<s.size();i+=2){ string tmp; tmp += s[i]; tmp += s[i+1]; key[count] = stoi(tmp, nullptr, 16); count++; tmp.clear(); } return key; } [/cpp]

keyをstring型から16進数整数に変換する関数です。chachaの実装とは関係ありません。

このコードを書いていたときは、文字列sを入力として、文字列sから2文字ずつ取り出し、それを文字列tmpとして、stoi関数で16進数整数に変換しています。

最後に16進数整数に変換した文字を配列に入れて、配列を戻り値としています。

Cでは配列自体を戻り値にできませんが、C++ではarrayを用いることで配列を戻り値にすることができます。

ただし、C++でも生配列(int a[ ]みたいに宣言する配列)の場合は、戻り値とできないので、ポインタを渡さないといけません。私はポインタを使いたくないので、arrayを使いました。array使ったほうが便利。

[blogcard url=”https://torini.hateblo.jp/entry/2015/02/26/%E7%94%9F%E9%85%8D%E5%88%97%E3%82%88%E3%82%8A%E3%82%82std%3A%3Aarray%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%9F%E6%96%B9%E3%81%8C%E8%89%AF%E3%81%84%E7%90%86%E7%94%B1″]

37行目~49行目

[cpp] array<uint32_t,8> make_array_nonce(string s){ array<uint32_t,8> key; int count = 0; for(int i=0;i<s.size();i+=2){ string tmp; tmp += s[i]; tmp += s[i+1]; key[count] = stoi(tmp, nullptr, 16); count++; tmp.clear(); } return key; } [/cpp]

上のkeyを16進数整数に変換するのと同じ。本当は上のと一緒にしたかったけど、出力長が違うので分けた。引数で設定できる？

51行目~69行目

[cpp] string key_generate(int a, int b, int c, int d){ string sub_key; int bc[4] = {a, b, c, d}; for(int i = 0; i < 4; i++){ char c; if(bc[i] < 10){ c = bc[i] + ‘0’; }else{ if(bc[i] == 10) c = ‘a’; if(bc[i] == 11) c = ‘b’; if(bc[i] == 12) c = ‘b’; if(bc[i] == 13) c = ‘d’; if(bc[i] == 14) c = ‘e’; if(bc[i] == 15) c = ‘f’; } sub_key.push_back(c); } return sub_key; } [/cpp]

これもkeyやnonceを作成する部分の一部。

書いた当時は4wordsごとに切ったsub_keyと名付けたものを16個集めてkeyにする予定だった。

その時、sub_keyを予め作成しておこうと考えていたので、こういう関数ができた。

整数値から16進数文字に変換する方法がわからなかったので、愚直にif文で書いています。これはSwitch文のほうが良かったと思います。

74行目~82行目

[cpp] array<uint32_t,64> in = {101, 120, 112, 97, 110, 100, 32 , 51, 50, 45, 98 , 121, 116, 101, 32, 107}; //↑はconstを2進数にしたものをInital Stateに代入している //次の3つはkey,block_count,nonceの配列を作成している。 array<uint32_t,32> k(make_array_key(key)); array<uint32_t, 8> block_count = {0, 0, 0, 0, 0, 0, 0, 0}; array<uint32_t, 8> n(make_array_nonce(nonce)); [/cpp]

各値を設定してます。inはInital Stateのことで、64要素あります。そのうち、0~15番目まで、Consの値で予め初期化しています。

この各値については、 expand 32-byte kを一つずつ整数に変換したものです。

Inital Stateが64要素あるのは、こっちのほうが代入しやすいからです。あとでこれを4*4行列に変換します。

また、 先にexpand 32-byte kを4文字ずつ区切って、4*4行列のInital Stateに代入する場合は、1634760805,857760878,2036477234,1797285236を順に代入します。どっちも同じことです。

それ以外はコメント通りです。

85行目~93行目

[cpp] for(int i = 16; i < 64; i++){ if(i >= 16 && i < 48){ in[i] = k[i – 16]; }else if(i >= 48 && i < 56){ in[i] = block_count[i – 48]; }else{ in[i] = n[i – 56]; } } [/cpp]

Cons以外の要素をInital Stateに代入します。

95行目~101行目

[cpp] /*4*4のInital Stateに変換する。64要素あるInital Stateを4要素ずつ取り出し、リトルエンディアンに変換して4*4行列に代入する。 この時、4*4行列ではなく、QRの計算のために1*16行列にする。つまり、このあと計算するのはIn[]ではなく、x[]である。 また、これはリトルエンディアンにしている。*/ uint32_t x[16]={}; for(int i = 0; i < 64; i+=4){ x[i / 4] = in[i] | (in[i+1] << 8) | (in[i+2] << 16) | (in[i+3] << 24); } [/cpp]

1*64行列のInital Stateを、1*16行列のInital Stateに変換します。

変換は、1*64行列のInital Stateの4要素ずつを取り出し、リトルエンディアンに変換した上で1*16行列のInital Stateに代入していきます。

リトルエンディアンにする理由としては、Intel CPUに最適化するためだと思います。

最初、私はx[i/4]としなければならないところを、x[i]と書いてて、出力されたkey streamが4ブロック以降は0となるバグを作っていました。

103行目~108行目

[cpp] //QR前のx[]をコピーする。 uint32_t cp[16]={}; for(int i = 0; i < 16; i++){ cp[i] = x[i]; } [/cpp]

コメント通り。arrayをコピーする関数がなかったので、一個ずつコピーしています。

110行目~122行目

[cpp] //x[]をQRに通す for(int i = 0; i < ROUNDS; i += 2){ // Odd round QR(x[0], x[4], x[ 8], x[12]); // column 0 QR(x[1], x[5], x[ 9], x[13]); // column 1 QR(x[2], x[6], x[10], x[14]); // column 2 QR(x[3], x[7], x[11], x[15]); // column 3 // Even round QR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal) QR(x[1], x[6], x[11], x[12]); // diagonal 2 QR(x[2], x[7], x[ 8], x[13]); // diagonal 3 QR(x[3], x[4], x[ 9], x[14]); // diagonal 4 } [/cpp]

コメント通り。これで2roundなので、for文のループ更新式に注意。

124行目~127行目

[cpp] //QR前x[]とQR後x[]を2^32を法とする加算を行う。 for(int i = 0; i < 16; i++){ x[i] = plus32(x[i], cp[i]); } [/cpp]

コメント通り。初期状態と20ラウンド後のStateを加算している部分。

129行目~136行目

[cpp] //リトルエンディアンを逆変換する uint32_t result[64]={}; for(int i = 0; i < 64; i +=4){ result[i] = (x[i/4] & 0xff); result[i+1] = ((x[i/4] >> 8) & 0xff); result[i+2] = ((x[i/4] >>16) & 0xff); result[i+3] = ((x[i/4] >> 24) & 0xff); } [/cpp]

また1*64行列に戻すので、リトルエンディアンを逆変換しています。

138行目~146行目

[cpp] //16進数のstring型に変換する。これがkey_steam。 string key_stream; for(int i = 0; i < 64; i++){ stringstream ss; ss << hex << result[i]; key_stream += ss.str(); } return key_stream; } [/cpp]

整数を16進数文字列に変換します。これがkey streamになります。

整数を16進数に変換するとき、マニピュレータを使います。競技プログラミングでたまに使いますね。

[blogcard url=”https://chakku.hatenablog.com/entry/2016/02/15/155106″]

147行目~191行目

[cpp] int main(int argc, char const *argv[]) { string key="0000000000000000000000000000000000000000000000000000000000000000", nonce="0000000000000000"; string key_stream; long long int count = 1; vector<string> mini_key; bool flag = 0; //mini_key作成のループ抜ける用 //4wordsのmini_keyを作成。これを16個あつめてkeyを作る(予定) while(1){ for(int i = 0; i < 16; i++){ for(int j = 0; j < 16; j++){ for(int k = 0; k < 16; k++){ for(int l = 0; l < 16; l++){ // cout<<"i,j,k,l="<<i<<","<<j<<","<<k<<","<<l<<","<<"mini_key="<<key_generate(i , j , k ,l)<<endl; mini_key.push_back(key_generate(i , j , k ,l)) ; if(i == 15 && j == 15 && k == 15 && l == 15) flag = 1; } } } } if(flag == 1) break; } cout<<"Writing…Please wait…"<<endl; //実行中何も表示されないと寂しいので //keytを作成して、chacha関数からkey_streamを受け取り、ファイルに出力する。 for(int i = 0;i < 65536; i++){ for(int j = 0; j < 4; j++){ key[j] = mini_key[i][j]; } key_stream = chacha(key, nonce); //ファイル出力 string filename = "key_stream_result.txt"; ofstream writing_file; writing_file.open(filename, ios::app); writing_file << key_stream << endl; if(count % 1000 == 0) cout<<"Now,count is"<<count<<endl; //暇つぶし count++; } cout<<dec<<count<<endl; return 0; } [/cpp]

main関数全部。key作成して、chahca関数に投げて、key streamを受け取って、それをファイルに出力しています。

ファイル入出力はatcoderではあまり使わないので、なにげに苦戦しました。

[blogcard url=”https://qiita.com/NickTominaga/items/7e01b7eb0b67ac791ec6″]

countに関するものは、コードが正常に動いているのかを確認するためのものです。標準出力はコードの実行速度が低下する原因になるので、消したほうがいい。

65536個のkey streamを作成しましたが、だいたい実行時間は2分ぐらいでした。ちゃんと測っていないので、正確な時間はわかりませんが・・・。

まとめ

とりあえずchachaをC++で実装してみました。

本当はpythonのコードを読むときに考えたことなども書こうとしましたが、力尽きたので自分のコードの解説だけになりました。

chahchaを実装しても卒研は終わらないので、卒研頑張っていきましょう。

｡оО(｡´•ㅅ•｡)Оо｡がんばっていこう・・・