Wikipedia

Salsa20

Salsa20は、ダニエル・バーンスタインによって開発されたストリーム暗号である。

Salsa20
Salsaの1/4ラウンド関数。これを4つ並列に並べたものが1ラウンドを形成する。
一般
設計者 ダニエル・バーンスタイン
初版発行日 2007年 (2007) (設計は2005年 (2005))
後継 ChaCha
関連 Rumba20
認証 eSTREAM portfolio
暗号詳細
鍵長 128 or 256 bits
状態長 512 bits
構造 ARX
ラウンド数 20
速度 3.91 cpb on an Intel Core 2 Duo[1]
最良の暗号解読法
2008 cryptanalysis breaks 8 out of 20 rounds to recover the 256-bit secret key in 2251 operations, using 231 keystream pairs.[2]

32-bit addition、XORおよびキャリーなしローテートに基づく疑似乱数生成によって構成される。中心となる関数は、256ビットの鍵、64ビットのnonce、そして64ビットの（ストリームの位置を示す）カウンタを入力とし、512ビットの鍵ストリーム１ブロックを出力する（鍵長128ビットのバージョンも存在する）。これにより、Salsa20には、任意の位置のストリームを一定時間で探索することが可能となる。

Salsa20は特許で保護されておらず、設計者であるバーンスタインによっていくつかのアーキテクチャ向けの最適化実装がパブリックドメインで公開されている[3]。最近のx86プロセッサでは、ソフトウェア実装で4–14 cycles per byte程度の速度を示す[4]。

構造 編集

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

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

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

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

Initial state of Salsa20
Cons Key Key Key
Key Cons Nonce Nonce
Pos Pos Cons Key
Key Key Key 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 1
QR( 5,  9, 13,  1)	// column 2
QR(10, 14,  2,  6)	// column 3
QR(15,  3,  7, 11)	// column 4
// 偶数ラウンド
QR( 0,  1,  2,  3)	// row 1
QR( 5,  6,  7,  4)	// row 2
QR(10, 11,  8,  9)	// row 3
QR(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 rounds
	for (i = 0; i < ROUNDS; i += 2) {
		// Odd round
		QR(x[ 0], x[ 4], x[ 8], x[12]);	// column 1
		QR(x[ 5], x[ 9], x[13], x[ 1]);	// column 2
		QR(x[10], x[14], x[ 2], x[ 6]);	// column 3
		QR(x[15], x[ 3], x[ 7], x[11]);	// column 4
		// Even round
		QR(x[ 0], x[ 1], x[ 2], x[ 3]);	// row 1
		QR(x[ 5], x[ 6], x[ 7], x[ 4]);	// row 2
		QR(x[10], x[11], x[ 8], x[ 9]);	// row 3
		QR(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] それに応じてセキュリティマージンは小さくなる。

eSTREAM 選定 編集

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はおおよそ2165の試行でSalsa20/5を解読する方法を報告し、「Salsa20に対する最も興味深い攻撃法」としてBernsteinから1000ドルの賞金を獲得した。これは切詰差分解読法に基づいたものである。2006年、Fischer, Meier, Berbain, Biasse, and Robshawは、切詰差分解読法によって2177の試行でSalsa20/6を、関連鍵攻撃によって2217の試行でSalsa20/7を解読する方法を報告した[9]。

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

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

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

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

ChaCha 編集

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で2139、ChaCha7で2248の試行。128ビットのChaCha6で2107の試行。128ビットのChaCha7では攻撃に失敗[2]）。

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

Initial state of ChaCha
Cons Cons Cons Cons
Key Key Key Key
Key Key Key Key
Pos Pos Nonce Nonce

定数は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 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

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 rounds
	for (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
	}
	for (i = 0; i < 16; ++i)
		out[i] = x[i] + in[i];
}

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

ChaCha20 の採用 編集

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が推奨候補暗号リストに追加された。

脚注 編集

[脚注の使い方]

注釈 編集

  1. ^ 計算時間のほとんどはラウンド処理の繰り返しによるものなので、ラウンド数と処理速度は反比例する。つまり、ラウンド数を半分にすれば、パフォーマンスは約二倍になる。よって、ラウンド数を削減した変種は明らかに速い。

出典 編集

  1. ^ Daniel J. Bernstein. “Salsa 20 speed; Salsa20 software”. 2013年12月30日閲覧。
  2. ^ a b c d Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger, New Features of Latin Dances
  3. ^ Speed of Salsa20
  4. ^ Salsa20 home page
  5. ^ Daniel J. Bernstein (2007-12-24). The Salsa20 family of stream ciphers. https://cr.yp.to/snuffle/salsafamily-20071225.pdf. 
  6. ^ http://www.ecrypt.eu.org/stream/endofphase2.html
  7. ^ http://www.ecrypt.eu.org/stream/endofphase1.html
  8. ^ http://www.ecrypt.eu.org/stream/PhaseIIreport.pdf
  9. ^ Simon Fischer, Willi Meier, Côme Berbain, Jean-Francois Biasse, Matt Robshaw, Non-Randomness in eSTREAM Candidates Salsa20 and TSC-4, Indocrypt 2006
  10. ^ Yukiyasu Tsunoo, Teruo Saito, Hiroyasu Kubo, Tomoyasu Suzaki and Hiroki Nakashima (2007-01-02). Differential Cryptanalysis of Salsa20/8. http://www.ecrypt.eu.org/stream/papersdir/2007/010.pdf. 
  11. ^ Zhenqing Shi, Bin Zhang, Dengguo Feng, Wenling Wu (2012): „Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha“. Information Security and Cryptology – ICISC 2012. Springer Verlag, 2013, pp. 337-351
  12. ^ Nicky Mouha, Bart Preneel (2013). A Proof that the ARX Cipher Salsa20 is Secure against Differential Cryptanalysis. http://eprint.iacr.org/2013/328.pdf. 
  13. ^ a b c Bernstein, Daniel (28 January 2008), ChaCha, a variant of Salsa20, https://cr.yp.to/chacha/chacha-20080128.pdf 2018年6月3日閲覧。 
  14. ^ Neves, Samuel (2009-10-07), Faster ChaCha implementations for Intel processors, http://eden.dei.uc.pt/~sneves/chacha/chacha.html 2011年2月20日閲覧, "two of these constants are multiples of 8; this allows for a 1 instruction rotation in Core2 and later Intel CPUs using the pshufb instruction" 
  15. ^ Bernstein, D. J. (2008-01-28) (pdf), ChaCha, a variant of Salsa20, p. 4, Document ID: 4027b5256e17b9796842e6d0f68b0b5e, http://cr.yp.to/chacha/chacha-20080128.pdf 2011年2月20日閲覧。 
  16. ^ ChaCha20 and Poly1305 for IETF protocols, Internet-Draft , Y. Nir, Check Point, A. Langley, Google Inc., November 9, 2014
  17. ^ draft-ietf-tls-chacha20-poly1305 The ChaCha20-Poly1305 AEAD Cipher for Transport Layer Security
  18. ^ Google Swaps Out Crypto Ciphers in OpenSSL, InfoSecurity, April 24, 2014
  19. ^ Miller, Damien (2013年12月2日). “ssh/PROTOCOL.chacha20poly1305”. BSD Cross Reference, OpenBSD src/usr.bin/. 2014年12月27日閲覧。
  20. ^ Murenin, Constantine A. (2013年12月11日). Unknown Lamer: “OpenSSH Has a New Cipher — Chacha20-poly1305 — from D.J. Bernstein”. Slashdot. 2014年12月27日閲覧。
  21. ^ Murenin, Constantine A. (2014年4月30日). Soulskill: “OpenSSH No Longer Has To Depend On OpenSSL”. Slashdot. 2014年12月26日閲覧。
  22. ^ “ChaCha Usage & Deployment”. 2015年1月7日閲覧。
  23. ^ “arc4random - NetBSD Manual Pages”. 2015年1月7日閲覧。
  24. ^ Donenfeld, Jason A.. “Protocol & Cryptography - WireGuard” (英語). www.wireguard.com. 2020年4月21日閲覧。

外部リンク 編集

「https://ja.wikipedia.org/w/index.php?title=Salsa20&oldid=97837010」から取得