Salsa20
Salsa20は、16ワード(1ワードは32ビット)からなる初期状態に対して、ビットごとのXOR、32-bitの加算 mod 2、固定移動距離のローテートを行なう。XOR、加算、ローテーションのみを用いることで、ソフトウェア実装におけるタイミング攻撃を回避することができる。
内部状態は16ワードからなり、4×4の行列で表現される。
初期状態は、8ワードの鍵(Key)、2ワードのストリーム位置(Pos)、2ワードのnonce、4つの固定のワード(Cons)から、次のように決まる。
固定ワードは、"expand 32-byte k"をASCIIコードで表したもの (つまり、4つのワードはそれぞれ、"expa", "nd 3", "2-by", "te k")であり、nothing up my sleeve number の一例である。
Salsa20の演算の中心は、1/4ラウンド関数QR(a,b,c,d)であり、これは4つの入力ワードから4つの出力ワードを以下のように生成する。
奇数ラウンドではQR(a,b,c,d)は4×4行列の4行それぞれに適用され、偶数ラウンドでは4つの列それぞれに適用される。
Salsa20は、ダニエル・バーンスタインによって開発されたストリーム暗号である。
32-bit addition、XORおよびキャリーなしローテートに基づく疑似乱数生成によって構成される。中心となる関数は、256ビットの鍵、64ビットのnonce、そして64ビットの(ストリームの位置を示す)カウンタを入力とし、512ビットの鍵ストリーム1ブロックを出力する(鍵長128ビットのバージョンも存在する)。これにより、Salsa20には、任意の位置のストリームを一定時間で探索することが可能となる。
Salsa20は特許で保護されておらず、設計者であるバーンスタインによっていくつかのアーキテクチャ向けの最適化実装がパブリックドメインで公開されている。最近のx86プロセッサでは、ソフトウェア実装で4–14 cycles per byte程度の速度を示す。
連続した2ラウンド(行ラウンドと列ラウンド)はdouble-roundと呼ばれる。
C/C++ での実装は以下のとおり:
最後の行で、かき混ぜられた配列x[i]を、ワードごとに元の配列in[i]に加えて、64バイトの出力ブロックout[i]とする。この操作は重要である。なぜなら、かき混ぜ操作自体は可逆だからである。つまり、この最後の操作が無かった場合、出力である鍵ストリームブロックにかき混ぜ操作を逆に施すことで(鍵を知らなくても可能であることに注意)、鍵を含む初期状態を復元できてしまう。かき混ぜられた配列を元の配列に加えることで、このように入力を復元することが不可能となる。(これと同様のテクニックは、MD4からSHA-2にいたるハッシュ関数の中で広く使われている。)
Salsa20は、入力に対して20ラウンドのかき混ぜ操作を行う。 また、ラウンド数をそれぞれ8、12に削減したSalsa20/8 および Salsa20/12と呼ばれる変種も存在する。これらはSalsa20を補完するものであり、eSTREAMのベンチマークでは、オリジナルよりも良い性能を出しているが、 それに応じてセキュリティマージンは小さくなる。