Salsa20

Salsa20は、16ワード（１ワードは32ビット）からなる初期状態に対して、ビットごとのXOR、32-bitの加算 mod 2³²、固定移動距離のローテートを行なう。XOR、加算、ローテーションのみを用いることで、ソフトウェア実装におけるタイミング攻撃を回避することができる。

内部状態は16ワードからなり、4×4の行列で表現される。

初期状態は、8ワードの鍵(Key)、2ワードのストリーム位置(Pos)、2ワードのnonce、4つの固定のワード(Cons)から、次のように決まる。

固定ワードは、"expand 32-byte k"をASCIIコードで表したもの (つまり、４つのワードはそれぞれ、"expa", "nd 3", "2-by", "te k"）であり、nothing up my sleeve number の一例である。

Salsa20の演算の中心は、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)は4×4行列の４行それぞれに適用され、偶数ラウンドでは４つの列それぞれに適用される。連続した２ラウンド（行ラウンドと列ラウンド）はdouble-roundと呼ばれる。

// 奇数ラウンドQR( 0,  4,  8, 12)// column 1QR( 5,  9, 13,  1)// column 2QR(10, 14,  2,  6)// column 3QR(15,  3,  7, 11)// column 4// 偶数ラウンドQR( 0,  1,  2,  3)// row 1QR( 5,  6,  7,  4)// row 2QR(10, 11,  8,  9)// row 3QR(15, 12, 13, 14)// row 4

C/C++ での実装は以下のとおり：

#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 roundsfor (i = 0; i < ROUNDS; i += 2) {// Odd roundQR(x[ 0], x[ 4], x[ 8], x[12]);// column 1QR(x[ 5], x[ 9], x[13], x[ 1]);// column 2QR(x[10], x[14], x[ 2], x[ 6]);// column 3QR(x[15], x[ 3], x[ 7], x[11]);// column 4// Even roundQR(x[ 0], x[ 1], x[ 2], x[ 3]);// row 1QR(x[ 5], x[ 6], x[ 7], x[ 4]);// row 2QR(x[10], x[11], x[ 8], x[ 9]);// row 3QR(x[15], x[12], x[13], x[14]);// row 4}for (i = 0; i < 16; ++i)out[i] = x[i] + in[i];}

最後の行で、かき混ぜられた配列x[i]を、ワードごとに元の配列in[i]に加えて、64バイトの出力ブロックout[i]とする。この操作は重要である。なぜなら、かき混ぜ操作自体は可逆だからである。つまり、この最後の操作が無かった場合、出力である鍵ストリームブロックにかき混ぜ操作を逆に施すことで（鍵を知らなくても可能であることに注意）、鍵を含む初期状態を復元できてしまう。かき混ぜられた配列を元の配列に加えることで、このように入力を復元することが不可能となる。（これと同様のテクニックは、MD4からSHA-2にいたるハッシュ関数の中で広く使われている。）

Salsa20は、入力に対して20ラウンドのかき混ぜ操作を行う。^[5]また、ラウンド数をそれぞれ8、12に削減したSalsa20/8 および Salsa20/12と呼ばれる変種も存在する。これらはSalsa20を補完するものであり、eSTREAMのベンチマークでは、オリジナルよりも良い性能を出しているが、^{[注釈 1]} それに応じてセキュリティマージンは小さくなる。

Salsa20は、eStreamプロジェクトにおいて、Profile 1（ソフトウェア）のPhase 3デザインに選定された（Phase 2においては、他のどのアルゴリズムよりも高いスコアを得た）^[6]。Profile 2（ハードウェア）のPhase 2デザインにも選出されていたが^[7]、こちらはPhase 3には進めなかった。これは、制約の多いハードウェア環境では十分な性能を発揮できないと判断されたためである^[8]。

2013年現在、Salsa20/12およびSalsa20/20の解読に成功した例はない。最良の攻撃法では、12あるいは20ラウンド中8ラウンドまで解読されている^[2]。

2005年、Paul Crowleyはおおよそ2¹⁶⁵の試行でSalsa20/5を解読する方法を報告し、「Salsa20に対する最も興味深い攻撃法」としてBernsteinから1000ドルの賞金を獲得した。これは切詰差分解読法に基づいたものである。2006年、Fischer, Meier, Berbain, Biasse, and Robshawは、切詰差分解読法によって2¹⁷⁷の試行でSalsa20/6を、関連鍵攻撃によって2²¹⁷の試行でSalsa20/7を解読する方法を報告した^[9]。

2007年、Tsunooらは、2^11.37の鍵とストリームのペアを用いて、2²⁵⁵の試行によってSalsa20の20ラウンド中8ラウンドまでの解読を報告したが^[10]、これは総当たり攻撃に近いものである。

2008年、 Aumasson, Fischer, Khazaei, Meier, and Rechbergerは2¹⁵³の試行によってSalsa20/7を解読し、2²⁵¹の試行によって初めてSalsa20/8を解読した^[2]

2012年、Aumassonらの手法はShiらによって改良され、128ビット鍵のSalsa20/7では2¹⁰⁹の試行で、256ビット鍵のSalsa20/8では2²⁵⁰の試行となった^[11]。

2013年、MouhaとPreneelは、差分解読法に対してSalsa20は15ラウンド目まで128ビットの安全性を有していることを示した^[12]。差分解読法での確率は2⁻¹³⁰より低く、これは128ビットの鍵を使い尽くすより困難である。

ChaCha

ChaChaの1/4ラウンド関数。これを4つ並列に並べたものが1ラウンドを形成する。
一般
設計者	ダニエル・バーンスタイン
初版発行日	2008年 (2008)
派生元	Salsa20
関連	Rumba20
暗号詳細
鍵長	128 or 256 bits
状態長	512 bits
構造	ARX
ラウンド数	20
速度	3.95 cpb on an Intel Core 2 Duo[13]

2008年、バーンスタインはChaChaと呼ばれる変種を発表した。これはラウンドごとの発散を大きくすることでパフォーマンスの向上を図ったものである。AumassonらはChaChaに対しても攻撃を試みたが、Salsa20よりも1ラウンド少ない結果となった（256ビットのChaCha6で2¹³⁹、ChaCha7で2²⁴⁸の試行。128ビットのChaCha6で2¹⁰⁷の試行。128ビットのChaCha7では攻撃に失敗^[2]）。

Salsa20と同様に、ChaChaの初期状態は128ビットの定数、256ビットの鍵、64ビットのカウンタ、64ビットのnonceを含む32ビットワードの4×4の行列であるが、並び順が変更されている。

定数はSalsa20と同じ"expand 32-byte k"である。ChaChaでは、Salsa20の1/4ラウンド関数QR(a,b,c,d)が

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の1/4ラウンド関数では各ワードが1回しか更新されないのに対し、ChaChaの関数では2回更新されることに注意。また、ChaChaの1/4ラウンド関数は、変化をよりすばやく拡散する。Salsa20の1/4ラウンド関数の入力の1ビットを変更すると、平均で出力の8ビットが変化するが、ChaChaの場合は12.5ビットが変化する。^[13]

さらに、ChaChaとSalsaとでは、1/4ラウンド関数中の加算、xor、ビットローテーションの数が同じであるが、ローテートのうち2つが8の倍数であることから、x86を含むいくつかのアーキテクチャでは、最適化が可能となる^[14]。加えて、SSE向けに最適化することが可能であることがSalsa20において発見されており、ChaChaではこれを利用できるように入力フォーマットが変更されている。^[15]　ラウンドごとに列方向と行方向を交互に繰り返すのではなく、列方向と角線方向を繰り返す。^[13]

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

ChaCha20ではこのdouble-roundを10回繰り返す^[16]。

C/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 void chacha_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 roundsfor (i = 0; i < ROUNDS; i += 2) {// Odd roundQR(x[0], x[4], x[ 8], x[12]); // column 0QR(x[1], x[5], x[ 9], x[13]); // column 1QR(x[2], x[6], x[10], x[14]); // column 2QR(x[3], x[7], x[11], x[15]); // column 3// Even roundQR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal)QR(x[1], x[6], x[11], x[12]); // diagonal 2QR(x[2], x[7], x[ 8], x[13]); // diagonal 3QR(x[3], x[4], x[ 9], x[14]); // diagonal 4}for (i = 0; i < 16; ++i)out[i] = x[i] + in[i];}

ChaChaはSHA-3選定の最終候補であったBLAKEの基礎となっている。

Googleは、共通鍵暗号としてChaCha20、メッセージ認証符号として同じくバーンスタインによるPoly1305を組み合わせたものを、RC4に代わるインターネットセキュリティで利用可能なストリーム暗号として提唱している^[17]。Google ChromeおよびGoogleのウェブサービスにおけるTLS/SSL通信 (https) においてChaCha20-Poly1305が実装されている^[18]。

GoogleによるTLSでの採用に続き、ChaCha20とPoly1305の組み合わせは chacha20-poly1305@openssh.com としてOpenSSHに採用された^[19][20]。これにより、OpenSSHがOpenSSLに依存する必要がなくなった^[21]。

ChaCha20は、脆弱性が指摘されているRC4に代わり、OpenBSD、NetBSD、DragonFly BSDにおける乱数生成器 arc4random に利用されている^[22][23]。

ChaCha20-Poly1305そのものが RFC 7539 、またInternet Key Exchange (IKE) およびIPSecでの利用が RFC 7634 、TLS/SSLでの利用が RFC 7905 として標準化された。

WireGuardはChaCha20-Poly1305を採用している^[24]。

2018年3月、CRYPTRECの「電子政府における調達のために参照すべき暗号のリスト」が改訂され、ChaCha20-Poly1305が推奨候補暗号リストに追加された。

• Salsa20 home page
• Specification (PDF)
• Salsa20/8 and Salsa20/12 (PDF)
• eStream page on Salsa20
• The ChaCha family of stream ciphers