サルサ20

サルサ20

サルサのクォーターラウンド機能。4 つの平行コピーが 1 つのラウンドを形成します。
一般的な
デザイナー	ダニエル・J・バーンスタイン
初版	2007年（2005年設計）[1]
後継者	チャチャ
関連	ルンバ20
認証	eSTREAMポートフォリオ
暗号の詳細
キーサイズ	128 または 256 ビット
州の規模	512 ビット
構造	ARx
ラウンド	20
スピード	Intel Core 2 Duoでは3.91 cpb [2]
最高の公開暗号解読
2008年の暗号解読では、 231のキーストリームペアを使用して、 2251回の操作で20ラウンドのうち8ラウンドを解読し、256ビットの秘密鍵を復元しました。[3]

Salsa20とそれによく似たChaCha は、Daniel J. Bernsteinが開発したストリーム暗号です。オリジナルの暗号である Salsa20 は 2005 年に設計され、後にBernstein によってeSTREAM欧州連合暗号検証プロセスに提出されました。ChaCha は 2008 年に公開された Salsa20 の修正版です。拡散を増やし、一部のアーキテクチャでパフォーマンスを向上させる新しいラウンド関数を使用しています。^[4]

どちらの暗号も、32 ビットの加算、ビット単位の加算 (XOR)、回転の演算である加算- 回転 - XOR (ARX) 演算に基づく疑似乱数関数に基づいて構築されています。コア関数は、 256 ビットのキー、64 ビットのノンス、および 64 ビットのカウンターをキー ストリームの 512 ビット ブロックにマッピングします (128 ビットのキーを持つ Salsa バージョンも存在します)。これにより、Salsa20 と ChaCha は、ユーザーがキー ストリーム内の任意の位置を一定時間で効率的にシークできるという珍しい利点を得ています。Salsa20 は、最新のx86プロセッサ上でソフトウェアで1 バイトあたり約 4 ～ 14 サイクルの速度を提供し、 ^[5]ハードウェア パフォーマンスも妥当です。特許は取得されておらず、Bernstein は一般的なアーキテクチャ向けに最適化されたパブリック ドメイン実装をいくつか作成しています。 ^[6]

内部的には、暗号は16 個の 32 ビット ワードの内部状態に対して、ビット単位の加算 ⊕ (排他的論理和)、32 ビットの加算mod 2 ^{32 ⊞、および定数距離の回転演算 <<< を使用します。}加算、回転、排他的論理和演算のみを使用することで、ソフトウェア実装におけるタイミング攻撃の可能性を回避できます。内部状態は、4×4 マトリックスとして配置された 16 個の 32 ビット ワードで構成されています。

初期状態は8つのキーワード（ ）、ストリーム位置の2つの単語（ ）、2ワードのノンス（基本的には追加のストリーム位置ビット）（ ）、および4つの固定語（ ):

定数ワードは、ASCII で「expand 32-byte k」と表記されます (つまり、4 つのワードは「expa」、「nd 3」、「2-by」、「te k」です)。これは、何も隠していない数値QR(a, b, c, d)の例です。Salsa20 のコア操作は、4 ワードの入力を受け取り、4 ワードの出力を生成する 1/4 ラウンドです。

b ^= (a + d) <<< 7;
c ^= (b + a) <<< 9;
d ^= (c + b) <<< 13;
a ^= (d + c) <<< 18;

奇数ラウンドはQR(a, b, c, d)4×4 マトリックスの 4 つの列のそれぞれに適用され、偶数ラウンドは 4 つの行のそれぞれに適用されます。連続する 2 つのラウンド (列ラウンドと行ラウンド) を合わせてダブルラウンドと呼びます。

// 奇数ラウンド
QR( 0, 4, 8, 12) // 列1
QR( 5, 9, 13, 1) // 列2
QR(10, 14, 2, 6) // 列3
QR(15, 3, 7, 11) // 列4
// 均等丸め
QR( 0, 1, 2, 3) // 行1
QR( 5, 6, 7, 4) // 2行目
QR(10, 11, 8, 9) // 3行目
QR(15, 12, 13, 14) // 行4

C/C++ での実装を以下に示します。

#include <stdint.h> #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 ループ × 2 ラウンド/ループ = 20 ラウンドfor ( i = 0 ; i < ROUNDS ; i += 2 ) { // 奇数ラウンドQR ( x [ 0 ], x [ 4 ], x [ 8 ], x [ 12 ]); // 列 1 QR ( x [ 5 ], x [ 9 ], x [ 13 ], x [ 1 ]); // 列 2 QR ( x [ 10 ], x [ 14 ], x [ 2 ], x [ 6 ]); // 列 3 QR ( x [ 15 ], x [ 3 ], x [ 7 ], x [ 11 ]); // 列 4 // 偶数丸めQR ( x [ 0 ], x [ 1 ], x [ 2 ], x [ 3 ]); // 行 1 QR ( x [ 5 ], x [ 6 ], x [ 7 ], x [ 4 ]); // 行 2 QR ( x [ 10 ], x [ 11 ], x [ 8 ], x [ 9 ]); // 行 3 QR ( x [ 15 ], x [ 12 ], x [ 13 ], x [ 14 ]); // 行 4 } for ( i = 0 ;       
		  
	
	          
		
		       
		       
		      
		      
		
		        
		        
		      
		    
	
	    i < 16 ; ++ i )出力[ i ] = x [ i ] +イン[ i ]; }   
		    

最後の行では、混合配列が 1 ワードずつ元の配列に追加され、64 バイトのキー ストリーム ブロックが取得されます。混合ラウンドはそれ自体が可逆であるため、これは重要です。つまり、逆の操作を適用すると、キーを含む元の 4×4 マトリックスが生成されます。混合配列を元の配列に追加すると、入力を復元できなくなります。(この同じ手法は、MD4からSHA-2までのハッシュ関数で広く使用されています。)

Salsa20は入力に対して20ラウンドのミキシングを実行します。^[1]ただし、それぞれ8ラウンドと12ラウンドを使用する短縮版Salsa20/8とSalsa20/12も導入されています。これらのバリアントは、オリジナルのSalsa20を置き換えるのではなく補完するために導入されました。eSTREAMベンチマークではSalsa20よりも優れたパフォーマンスを発揮しますが^[注1]、セキュリティマージンはそれに応じて低くなります。

2008 年に、Bernstein は 192 ビットの nonce を持つ Salsa20 の変種である XSalsa20 を提案しました。^{[7] [8] [9]} XSalsa20 はSalsa20 が安全であれば安全であることが証明できますが、より長い nonce が必要なアプリケーションにより適しています。XSalsa20 は、キーと nonce の最初の 128 ビットを 1 つの Salsa20 ブロックに入力し (最後の加算は省略するか、標準の Salsa20 ブロックの後で減算できます)、最後の 64 ビットの nonce とストリームの位置を使用して、出力の 256 ビットを標準の Salsa20 のキーとして使用します。具体的には、使用される出力の 256 ビットは、入力の非秘密部分に対応するものであり、インデックス 0、5、10、15、6、7、8、および 9 です。

Salsa20/12は、 eSTREAMプロジェクトによってプロファイル1（ソフトウェア）のフェーズ3設計として選択され、フェーズ2の終了時にプロファイル1アルゴリズムの中で最も高い加重投票スコアを獲得しました。^[10] Salsa20は、eSTREAMプロジェクトによって、プロファイル1（ソフトウェア）のフェーズ2フォーカス設計として、およびプロファイル2（ハードウェア）のフェーズ2設計として以前に選択されていましたが、^[11] eSTREAMは、Salsa20が極端にリソースが制限されたハードウェア環境には適していないと判断したため、プロファイル2のフェーズ3には進みませんでした。^[12]

eSTREAM委員会は、「非常に優れた性能と十分な安全マージンを兼ね備えている」として、12ラウンドのバリエーションであるSalsa20/12の使用を推奨している。^[13]

2015年現在^{[アップデート]}、Salsa20/12またはSalsa20/20全体に対する攻撃は公開されていません。知られている最良の攻撃^[3]は、12ラウンドまたは20ラウンドのうち8ラウンドを破るものです。

2005年、ポール・クロウリーは推定時間複雑度が2165のSalsa20/5への攻撃を報告し^、「最も興味深いSalsa20暗号解読」としてバーンスタインの1000ドルの賞を受賞した。^{[14]この攻撃とその後のすべての攻撃は、}切り捨て差分暗号解読に基づいている。2006年、フィッシャー、マイヤー、ベルバイン、ビアス、ロブショウは推定時間複雑度が2177のSalsa20/6への攻撃と、推定時間複雑度が2217のSalsa20/7への関連鍵攻撃を報告し^た。 [ 15 ^]

2007年、津野らはSalsa20の暗号解読法を発表した。この解読法では、 ^{211.37個のキーストリームペアを使用して、 2255}回の演算で20ラウンドのうち8ラウンドを解読し、256ビットの秘密鍵を復元した。^[16]しかし、この攻撃はブルートフォース攻撃に匹敵するものではないようだ。

2008年、Aumasson、Fischer、Khazaei、Meier、Rechbergerは、Salsa20/7に対する暗号解読攻撃を2151の時間計算量で報告し^、 Salsa20/8に対する攻撃を推定時間計算量2251で報告した^。この攻撃は、切り捨て差分の確率的検出のための確率的中立鍵ビットという新しい概念を利用している。この攻撃は、128ビットの鍵でSalsa20/7を破るのに適応できる。^[3]

2012年に、Aumassonらによる攻撃はShiらによって改良され、Salsa20/7（128ビット鍵）に対する攻撃では時間計算量が2109に^、 Salsa20/8（256ビット鍵）に対する攻撃では時間計算量が²²⁵⁰にまで向上した。^[17]

2013年に、MouhaとPreneelは、15ラウンドのSalsa20が差分解析に対して128ビット安全であるという証明^{[18]を発表しました。（具体的には、 2-130}より高い確率で差分特性を持たないため、差分解析は128ビットの鍵枯渇よりも困難です。）

チャチャ

ChaCha の 1/4 ラウンド機能。4 つの平行コピーが 1 ラウンドを形成します。
一般的な
デザイナー	ダニエル・J・バーンスタイン
初版	2008
由来	サルサ20
関連	ルンバ20
暗号の詳細
キーサイズ	128 または 256 ビット
州の規模	512 ビット
構造	ARx
ラウンド	20
スピード	インテルCore 2 Duoで3.95 cpb [4] : 2

2008年に、Bernsteinは、同等かわずかに優れたパフォーマンスを達成しながら、ラウンドあたりの拡散を増やすことを目指した、密接に関連するChaCha暗号ファミリーを発表しました。 ^[19] Aumassonらによる論文でもChaChaを攻撃しており、1ラウンド少ないラウンド数（256ビットのChaCha6では複雑度2 ¹³⁹、ChaCha7では複雑度2 ²⁴⁸、128ビットのChaCha6では2 ¹⁰⁷以内）を達成しましたが、攻撃では128ビットのChaCha7を破ることができなかったと主張しています。^[3]

Salsa20と同様に、ChaChaの初期状態には、128ビットの定数、256ビットのキー、64ビットのカウンター、および64ビットのノンス（オリジナルバージョンでは。後述するように、RFC  7539のChaChaのバージョンは少し異なります）が含まれ、32ビットワードの4×4マトリックスとして配置されています。^[19]しかし、ChaChaは初期状態のいくつかのワードを再配置します。

定数は Salsa20 (「32 バイト 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;

このバージョンでは各単語を2回更新しますが、Salsa20のクォーターラウンドでは各単語を1回しか更新しないことに注意してください。さらに、ChaChaのクォーターラウンドは変更をより速く拡散します。平均して、1入力ビットを変更した後、Salsa20のクォーターラウンドは8出力ビットを変更しますが、ChaChaは12.5出力ビットを変更します。^[4]

ChaChaの1/4ラウンドは、Salsa20の1/4ラウンドと同じ数の加算、排他的論理和、ビット回転を持っていますが、回転のうち2つが8の倍数であるという事実は、x86を含むいくつかのアーキテクチャで小さな最適化を可能にします。^{[20]さらに、入力フォーマットは、Salsa20で発見された効率的な}SSE実装最適化をサポートするために再配置されました。列を下向きに丸めたり行を横切ったりするのではなく、列を下向きに対角線に沿って実行します。^{[4] : 4} Salsa20と同様に、ChaChaは16個の32ビットワードを4×4マトリックスに配置します。マトリックス要素を0から15までインデックスすると、

ChaCha のダブルラウンドは次のようになります。

// 奇数ラウンド
QR(0, 4, 8, 12) // 列1
QR(1, 5, 9, 13) // 列2
QR(2, 6, 10, 14) // 列3
QR(3, 7, 11, 15) // 列4
// 均等丸め
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はダブルラウンドを10回繰り返します。^[21] 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 ループ × 2 ラウンド/ループ = 20 ラウンドfor ( i = 0 ; i < ROUNDS ; i += 2 ) { // 奇数ラウンドQR ( x [ 0 ], x [ 4 ], x [ 8 ], x [ 12 ]); // 列 1 QR ( x [ 1 ], x [ 5 ], x [ 9 ], x [ 13 ]); // 列 2 QR ( x [ 2 ], x [ 6 ], x [ 10 ], x [ 14 ]); // 列 3 QR ( x [ 3 ], x [ 7 ], x [ 11 ], x [ 15 ]); // 列 4 // 偶数ラウンドQR ( x [ 0 ], x [ 5 ], x [ 10 ], x [ 15 ]); // 対角線 1 (主対角線) QR ( x [ 1 ], x [ 6 ], x [ 11 ], x [ 12 ]); // 対角線 2 QR ( x [ 2 ], x [ 7 ], x [ 8 ], x [ 13 ]); // 対角線 3 QR ( x [ 3 ], x [ 4 ], x [ 9 ], x [ 14 ]); // 対角線 4 } for ( i =       
		  
	
	          
		
		     
		     
		    
		    
		
		    
		    
		     
		     
	
	   0 ; i < 16 ; ++ i ) out [ i ] = x [ i ] + in [ i ]; }    
		    

ChaCha は、 NIST ハッシュ関数コンペティションのファイナリストであるBLAKE ハッシュ関数と、そのより高速な後継である BLAKE2 および BLAKE3の基礎となっています。また、16 個の 64 ビット ワード (1024 ビットの状態) と、それに応じて調整された回転定数を使用するバリアントも定義しています。

バーンスタインは発表していないが、XSalsa20 のセキュリティ証明は、類似のXChaCha暗号に直接拡張される。キーと nonce の最初の 128 ビット (入力ワード 12 から 15) を使用して ChaCha 入力ブロックを形成し、ブロック操作を実行する (最後の加算は省略)。出力ワード 0～3 と 12～15 (入力の非キーワードに対応するワード) は、通常の ChaCha で使用されるキー (最後の 64 ビットの nonce と 64 ビットのブロック カウンターを使用) を形成する。^[22]

Aumassonは2020年に、8ラウンドのChaCha（ChaCha8）は、おそらく同じセキュリティレベルで将来の暗号解読に対して十分な耐性を提供し、2.5倍の高速化をもたらすと主張しています。^[23]妥協案であるChaCha12（eSTREAMの12ラウンドのSalsaに基づく）^[24]も使用されています。^[25] eSTREAMベンチマークスイートには、ChaCha8とChaCha12が含まれています。^[19]

Googleは、 TLS over TCPの代替として意図されていたSPDYで、BernsteinのPoly1305メッセージ認証コードとともにChaCha20を選択しました。^[26]その過程で、彼らは両方のアルゴリズムを組み合わせた新しい認証暗号化構造を提案しました。これはChaCha20-Poly1305と呼ばれています。ChaCha20とPoly1305は現在、 SPDYの代替としてHTTP/3で使用されているQUICプロトコルで使用されています。^{[27] [28]}

GoogleがTLSを採用した直後、ChaCha20とPoly1305の両方のアルゴリズムがOpenSSHchacha20-poly1305@openssh.comの新しい暗号にも使用されました。^{[29] [30]}その後、これによりOpenSSHはコンパイル時のオプションを介してOpenSSLへの依存を回避できるようになりました。 ^[31]

ChaCha20は、FreeBSD ^{[32] 、} OpenBSD ^[33]、NetBSD ^[34]オペレーティングシステムarc4randomの乱数生成器にも使用され、壊れたRC4の代わりに使用されている。また、 DragonFly BSD ^[35]ではカーネルのCSPRNGサブルーチンに使用されている。 ^{[36] [37]}バージョン4.8以降、LinuxカーネルはChaCha20アルゴリズムを使用して、非ブロッキング/dev/urandomデバイスのデータを生成する。^{[38] [39] [40]} GolangではデフォルトのPRNGにChaCha8が使用されている。^[41] RustのCSPRNGはChaCha12を使用する。^[24]

ChaCha20は通常、CPUがAESアクセラレーション機能を備えていないシステム（ x86プロセッサのAES命令セットなど）では、より普及しているAdvanced Encryption Standard （AES）アルゴリズムよりも優れたパフォーマンスを発揮します。その結果、主にARMベースのCPUを使用するモバイルデバイスを含む特定のユースケースでは、ChaCha20がAESよりも好まれることがあります。 ^{[42] [43]} ChaCha20専用のハードウェアアクセラレータも、AESアクセラレータに比べて複雑ではありません。^[44]

ChaCha20-Poly1305（IETFバージョン、下記参照）は、プロトコルバージョン1以降、WireGuard VPNシステムで使用される独占アルゴリズムです。 ^[45]

ChaCha20の実装リファレンスはRFC  7539で公開されています。IETFの実装では、64ビットのノンスと64ビットのブロックカウンターを96ビットのノンスと32ビットのブロックカウンターに変更することで、Bernsteinの公開アルゴリズムを修正しました。[ ^46]アルゴリズムが変更されたときに名前は変更されませんでした。これは暗号的には重要ではないためです（どちらも暗号学者が128ビットのノンスとして認識するものを形成します）が、インターフェースの変更は開発者の混乱の原因になる可能性があります。ブロックカウンターが削減されたため、IETFのバリアントで安全に暗号化できるメッセージの最大長は、64バイトのブロック 2 ^32個（256 GiB）です。ファイルやディスクの暗号化など、これでは十分ではないアプリケーションの場合、RFC  7539では、64ビットのノンスを使用した元のアルゴリズムを使用することを提案しています。

IKEおよびIPsecでの ChaCha20 の使用は、RFC 7634で標準化されています 。TLS での使用の標準化は、RFC  7905 で公開されています。

2018年に、RFC 7539はRFC  8439によって廃止されました。RFC 8439ではいくつかのエラッタが統合され、追加のセキュリティ上の考慮事項が追加されました。^[47]

• Speck – NSA が開発した加算・回転・排他的論理和暗号
• ChaCha20-Poly1305 – ChaCha20とPoly1305 MACを組み合わせたAEADスキーム

• Snuffle 2005: Salsa20 暗号化機能
• Salsa20仕様（PDF）
• Salsa20/8 および Salsa20/12 (PDF)
• eSTREAM プロジェクト: Salsa20
• ストリーム暗号のChaChaファミリー
• Salsa20 の使用と展開
• CrypTool 2 における ChaCha 暗号ファミリーの実装と教育的視覚化