Salsa20

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
Salsa20
Salsa round function.svg
Salsaのラウンド関数の1/4。この4つのコピーが1ラウンドを形成する。
一般
設計者 ダニエル・バーンスタイン
関連 Rumba20, ChaCha
認証 eSTREAM portfolio
暗号詳細
鍵長 256 bits
状態長 512 bits
ラウンド数 20, 12
速度 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]

Salsa20は、ダニエル・バーンスタインによって開発されたストリーム暗号である。32-bit addition、XORおよびキャリーなしローテートに基づく疑似乱数生成によって構成され、256ビットの鍵長、64ビットのnonce、512ビットの状態長を持つ(128ビットの鍵長のバージョンも存在する)。これにより、Salsa20には、ユーザが決まった時間で出力されるストリームの任意の位置を探索することが可能となる。最近のx86プロセッサでは、ソフトウェア実装で4–14 cycles per byte程度の速度を示す[3]。Salsa20は特許で保護されておらず、設計者であるバーンスタインによっていくつかのアーキテクチャ向けの最適化実装がパブリックドメインで公開されている[4]

構造[編集]

Salsa20は、XOR、32-bit addition mod 232、32ビット長のワード16個のローテートを用いる。これにより、ソフトウェア実装におけるタイミング攻撃を回避することができる。

初期状態は8ワードの鍵、2ワードのストリーム位置、2ワードのnonce、4つの固定長のワードである。20ラウンドを経て、16ワードのストリーム出力を得る。

それぞれのラウンドは、4つの1/4ラウンド操作で構成され、4×4マトリックスからなる16ワードの行、列のいずれかとなる。2ラウンドごとにパターンは繰り返される。2ラウンドごとの疑似関数は以下の通りである。ここで ⊞ は addition modulo 232、<<< は左ローテート操作、^ は排他的論理和である。x ^= yx = x ^ y の略記である。

x[ 4] ^= (x[ 0] ⊞ x[12])<<<7;    x[ 9] ^= (x[ 5] ⊞ x[ 1])<<<7;
x[14] ^= (x[10] ⊞ x[ 6])<<<7;    x[ 3] ^= (x[15] ⊞ x[11])<<<7;
x[ 8] ^= (x[ 4] ⊞ x[ 0])<<<9;    x[13] ^= (x[ 9] ⊞ x[ 5])<<<9;
x[ 2] ^= (x[14] ⊞ x[10])<<<9;    x[ 7] ^= (x[ 3] ⊞ x[15])<<<9;
x[12] ^= (x[ 8] ⊞ x[ 4])<<<13;   x[ 1] ^= (x[13] ⊞ x[ 9])<<<13;
x[ 6] ^= (x[ 2] ⊞ x[14])<<<13;   x[11] ^= (x[ 7] ⊞ x[ 3])<<<13;
x[ 0] ^= (x[12] ⊞ x[ 8])<<<18;   x[ 5] ^= (x[ 1] ⊞ x[13])<<<18;
x[10] ^= (x[ 6] ⊞ x[ 2])<<<18;   x[15] ^= (x[11] ⊞ x[ 7])<<<18;

x[ 1] ^= (x[ 0] ⊞ x[ 3])<<<7;    x[ 6] ^= (x[ 5] ⊞ x[ 4])<<<7;
x[11] ^= (x[10] ⊞ x[ 9])<<<7;    x[12] ^= (x[15] ⊞ x[14])<<<7;
x[ 2] ^= (x[ 1] ⊞ x[ 0])<<<9;    x[ 7] ^= (x[ 6] ⊞ x[ 5])<<<9;
x[ 8] ^= (x[11] ⊞ x[10])<<<9;    x[13] ^= (x[12] ⊞ x[15])<<<9;
x[ 3] ^= (x[ 2] ⊞ x[ 1])<<<13;   x[ 4] ^= (x[ 7] ⊞ x[ 6])<<<13;
x[ 9] ^= (x[ 8] ⊞ x[11])<<<13;   x[14] ^= (x[13] ⊞ x[12])<<<13;
x[ 0] ^= (x[ 3] ⊞ x[ 2])<<<18;   x[ 5] ^= (x[ 4] ⊞ x[ 7])<<<18;
x[10] ^= (x[ 9] ⊞ x[ 8])<<<18;   x[15] ^= (x[14] ⊞ x[13])<<<18;

Salsa20は20ラウンドの操作を行い、最終アレイを元のアレイに加えて64バイトの出力ブロックとする[5]。また、ラウンド数をそれぞれ8、12に削減したSalsa20/8 および Salsa20/12と呼ばれる変種も存在する。これらはSalsa20を補完するものであり、ラウンド数の削減によってセキュリティマージンが小さくなる。

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[編集]

2008年、バーンスタインはChaChaと呼ばれる変種を発表した。これはラウンドごとの発散を大きくすることでパフォーマンスの向上を図ったものである。AumassonらはChaChaに対しても攻撃を試みたが、Salsa20よりも1ラウンド少ない結果となった(ChaCha6で2140の試行、ChaCha7で2231の試行)[2]

ChaChaでは、Salsa20のラウンド原始関数 R(a,b,c,k)

b ⊕= (a ⊞ c) <<< k;

b ⊞= c;
a ⊕= b;
a <<<= k;

と置き換えている。

ローテートも改良されている。1/4のラウンド関数は以下の通りとなる。

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

ChaChaではSalsa20よりも高速化、最適化が行われている[13][14]

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

脚注[編集]

  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. ^ Salsa20 home page
  4. ^ Speed of Salsa20
  5. ^ http://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. ^ 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" 
  14. ^ 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日閲覧。 

外部リンク[編集]