蛇（暗号）

蛇

サーペントのリニアミキシングステージ
一般的な
デザイナー	ロス・アンダーソン、イーライ・ビハム、ラース・クヌーセン
初版	1998-08-21
由来	四角
認証	AESファイナリスト
暗号の詳細
キーサイズ	128、192、または256ビット
ブロックサイズ	128ビット
構造	置換順列ネットワーク
ラウンド	32
最高の公開暗号解読
公に知られている攻撃はすべて計算上不可能であり、32 ラウンドの Serpent 全体に影響を及ぼすものはありません。2011 年の攻撃では、11 ラウンドの Serpent (すべてのキー サイズ) を 2 116の既知平文、2 107.5 の時間、2 104 のメモリで破りました ( [1]で説明されているとおり)。同じ論文では、12 ラウンドの Serpent-256 を破る 2 つの攻撃についても説明しています。最初の攻撃では、2 118の既知平文、2 228.8 の時間、2 228 のメモリが必要です。もう 1 つの攻撃では、2 116の既知平文と 2 121 のメモリが必要ですが、2 237.5 の時間も必要です。

Serpentは対称鍵 ブロック暗号であり、 Advanced Encryption Standard (AES) コンテストでファイナリストとなり、Rijndaelに次いで2位となった。^{[2] Serpentは}、ロス・アンダーソン、イーライ・ビハム、ラース・クヌーセンによって設計された。^[3]

他のAES申請と同様に、Serpentはブロックサイズが128ビットで、128、192、または256ビットのキーサイズをサポートしています。 ^[4]この暗号は、 4つの32ビットワードのブロックで動作する32ラウンドの置換-置換ネットワークです。各ラウンドでは、8つの4ビットから4ビットのSボックスの1つを32回並列に適用します。Serpentは、32ビットスライスを使用して、すべての操作を並列に実行できるように設計されています。これにより並列性が最大化されるだけでなく、 DESで実行された広範な暗号解読作業も使用できるようになります。

Serpent はセキュリティに対して保守的なアプローチを取り、大きなセキュリティ マージンを選択しました。設計者は、既知の種類の攻撃に対しては 16 ラウンドで十分であると考えましたが、暗号解読における将来の発見に対する保険として 32 ラウンドを指定しました。^[5] AES 競争に関する公式の NIST レポートでは、Serpent はMARSやTwofishのように高いセキュリティ マージンを持ち、RC6 や Rijndael (現在の AES) の十分なセキュリティ マージンとは対照的であると分類されました。^[2]最終投票では、Serpent はファイナリストの中では最も否定的な票が少なかったものの、Rijndael の肯定的な票が大幅に多かったため、全体では 2 位になりました。決定的な要因は、Rijndael の方がはるかに効率的なソフトウェア実装を可能にしたことです。^[要出典]

Serpent暗号アルゴリズムはパブリックドメインであり、特許は取得されていません。^[6]参照コードはパブリックドメインソフトウェアであり、最適化されたコードはGPLの下でライセンスされています。^[7]その使用に関して制限や負担はありません。その結果、誰でもライセンス料を支払うことなく、ソフトウェア（またはハードウェア実装）にSerpentを自由に組み込むことができます。

Serpent キー スケジュールは、3 つの主要な段階から構成されます。最初の段階では、必要に応じてパディングを追加してキーを初期化します。これは、短いキーを 256 ビットの長いキーにマップするために行われます。短いキーの末尾に 1 つの「1」ビットが追加され、その後に「0」ビットが続き、短いキーが長いキー長にマップされます。^[4]

次のフェーズでは、以前に初期化されたキーを使用して「プレキー」が導出されます。32ビットのキー部分がXORされ、黄金比の分数であるFRACとラウンドインデックスがキー部分とXORされ、XOR演算の結果が11だけ左に回転されます。FRACとラウンドインデックスは、ラウンド中にキービットが均等に分散されるように追加されました。^[4]

最後に、「サブキー」は以前に生成された「プレキー」から派生します。これにより、合計33個の128ビットの「サブキー」が生成されます。^[4]

最後に、ラウンドキーまたは「サブキー」が「初期順列IP」に配置され、キービットが正しい列に配置されます。^[4]

#define FRAC 0x9e3779b9      // 黄金比の小数部
#define ROTL(A, n) ((A) << n | (A) >> 32-n)

uint32_t key [ 8 ]; // ユーザーが指定したキー uint32_t subkey [ 33 ][ 4 ]; // ラウンドキーconst uint8_t S [ 8 ][ 16 ] = {}; // Sボックス         
  
     

/* キースケジュール: 事前キーを取得 */ 
void get_pre ( uint32_t w [ 4 * 33 ], const uint32_t k [ 8 ]) { uint32_t x [ 4 * 33 + 8 ]; for ( int i = 0 ; i < 8 ; i ++ ) x [ i ] = k [ i ]; for ( int i = 8 ; i < 140 ; i ++ ) { x [ i ] = ROTL ( x [ i -8 ] ^ x [ i -5 ] ^ x [ i -3 ] ^ x [ i -1 ] ^ FRAC ^ ( i -8 ), 11 ); w [ i -8 ] = x [ i ]; } }      
     
            
          
             
                     
          
    


/* キースケジュール: サブキーを取得 */ 
void get_sk ( const uint32_t w [ 4 * 33 ], uint32_t ( * sk )[ 4 ]) {       

	uint8_t i 、p 、j 、s 、k ; i = 0 、i < 33 、i ++の場合{ p = 32 + 3 - i ; j = 0 、j < 4 、j ++の場合{ sk [ i ] [ j ] = 0 ; k = 0 、k < 32 、k ++の場合{ s = S [ p % 8 ] [ (( w [ 4 * i + 0 ] >> k ) & 0x1 ) << 0 | (( w [ 4 * i + 1 ] >> k ) & 0x1 ) << 1 | (( w [ 4 * i + 2 ] >> k ) & 0x1 ) << 2 | (( w [ 4 * i + 3 ] >> k ) & 0x1 ) << 3 ] ; for ( j = 0 ; j < 4 ; j ++ ) { sk [ i ][ j ] |= (( s >> j ) & 0x1 ) << k ; } } } }     
	
	        
		      
               
              
		        
			               
						            
						            
						            
			        
				        
			
		
	


void key_schedule () { uint32_t w [ 4 * 33 ]; get_pre ( w 、キー); get_sk ( w 、サブキー); }  
     
     
     

Serpent s-box は 4 ビットの順列であり、次の特性に従います。

• 1ビットの入力差が1ビットの出力差につながることは決してなく、差分特性の確率は1:4以下である。^[8]

• 線形特性の確率は1:2から1:4の間であり、入力ビットと出力ビットの線形関係の確率は1:2から1:8の間である。^[8]

• 入力ビットの関数としての出力ビットの非線形順序は3である。しかし、入力ビットの関数として2の順序しか持たない出力ビットも見つかっている。^[8]

Serpent s-boxはDES s-boxの32行に基づいて構築されています。これらはエントリを交換することで変換され、結果として得られる望ましいプロパティを持つ配列がSerpent s-boxとして保存されました。このプロセスは合計8つのs-boxが見つかるまで繰り返されました。このプロセスでは次のキーが使用されました。"sboxesforserpent"[ ^4]

最初の順列は、ビットを移動しながら一度に 128 ビットで実行されます。

iが0 .. 127の場合swap (ビット( i )、ビット(( 32 * i ) % 127 ) )     
           

最終的な順列は、ビットを移動しながら一度に 128 ビットで実行されます。

iが0 .. 127の場合swap (ビット( i )、ビット(( 4 * i ) % 127 ) )     
           

XOR、S-Box、ビット左シフト、ビット左回転操作で構成されます。これらの操作は、4 つの 32 ビット ワードに対して実行されます。

for ( short i = 0 ; i < 4 ; i ++ ) { X [ i ] = S [ i ][ B [ i ] ^ K [ i ]]; } X [ 0 ] = ROTL ( X [ 0 ], 13 ); X [ 2 ] = ROTL ( X [ 2 ], 3 ); X [ 1 ] = X [ 1 ] ^ X [ 0 ] ^ X [ 2 ]; X [ 3 ] = X [ 3 ] ^ X [ 2 ] ^ ( X [ 0 ] << 3 ); X [ 1 ] = ROTL ( X [ 1 ], 1 ); X [ 3 ] = ROTL ( X [ 3 ], 7 ); X [ 0 ] = X [ 0 ] ^ X [ 1 ] ^ X [ 3 ]; X [ 2 ] = X [ 2 ] ^ X [ 3 ] ^ ( X [ 1 ] << 7 ); X [ 0 ] = ROTL ( X [ 0 ], 5 ); X [ 2 ] = ROTL ( X [ 2 ], 22 ); for ( short i = 0 ; i < 4 ; i ++ )         
        

   
    
      
        
    
    
      
        
    
   
         { 
B [ i + 1 ] = X [ i ]; }        

Rijndaelは、キー サイズに応じて 10、12、または 14 ラウンドの置換線形変換ネットワークで、キー サイズは 128 ビット、192 ビット、または 256 ビットで個別に指定されます。Serpent は、32 ラウンドの置換順列ネットワークで、最適化された実装を簡素化するために、最初の順列と最後の順列が追加されています。Rijndael のラウンド関数は、非線形層、線形混合層、およびキー混合 XOR 層の 3 つの部分で構成されます。Serpent のラウンド関数は、キー混合 XOR、同じ 4×4 S ボックスの 32 回の並列適用、および線形変換で構成されますが、最後のラウンドでは、別のキー混合 XOR が線形変換に置き換わります。Rijndael の非線形層は 8×8 S ボックスを使用しますが、Serpent は 8 つの異なる 4×4 S ボックスを使用します。32 ラウンドは、Serpent の方が Rijndael よりもセキュリティ マージンが高いことを意味します。しかし、10ラウンドのRijndaelは小さなブロックに対してはより高速かつ簡単に実装できます。^[9]そのため、RijndaelがAESコンペティションの優勝者に選ばれました。

オリジナルの Serpent である Serpent-0 は、第 5 回高速ソフトウェア暗号化ワークショップで発表されました。しかし、若干調整されたバージョンの Serpent-1 が AES コンテストに提出されました。AES 提出論文では、キー スケジュールの違いを含む変更点について説明されています。

XSL攻撃が効果的であれば、 Serpent を弱体化できます (ただし、 AES となったRijndaelほど弱体化はしません)。ただし、多くの暗号解読者は、実装上の考慮事項を考慮すると、 XSL 攻撃はブルート フォース攻撃よりもコストがかかると考えています。^[要出典]

2000年にKohnoらが発表した論文では、Serpentの32ラウンドのうち6ラウンドに対するmeet-in-the-middle攻撃と、Serpentの32ラウンドのうち9ラウンドに対する増幅ブーメラン攻撃が提示されている。^[10]

2001年にイーライ・ビハム、オール・ダンケルマン、ネイサン・ケラーが行った線形暗号解読攻撃では、 ²¹¹⁸の既知の平文と²⁸⁹の時間でSerpent-128の32ラウンドのうち10ラウンドを破り、 ²¹¹⁸の既知の平文と²¹⁸⁷の時間でSerpent-192/256の11ラウンドを破った。^[11]

2009年の論文では、Serpent S-boxの非線形次数は設計者が主張した3次ではなく、4つの要素が2次であったことが指摘されている。^[8]

2011年にHongjun Wu、Huaxiong Wang、Phuong Ha Nguyenが行った攻撃では、線形暗号解読法も使用され、2116の^既知の平文、^2107.5の時間、^2104のメモリを使用して、Serpent-128の11ラウンドを解読しました。^[1]

同じ論文では、Serpent-256 の 12 ラウンドを破る 2 つの攻撃についても説明されています。最初の攻撃では、2 ^{118 個}の既知の平文、2 ^228.8の時間、2 ^{228 個のメモリが必要です。もう 1 つの攻撃では、2 116 個}の既知の平文と 2 ^{121 個の}メモリが必要ですが、2 ^{237.5 の}時間も必要です。

• Tiger – 同じ作者によるハッシュ関数

• Anderson, Ross; Biham, Eli; Knudsen, Lars (1998)。「暗号化 - 256 ビット暗号: リファレンス (AES 提出) 実装」。
• Biham, Eli. 「Serpent – AES 向けの新しいブロック暗号の提案」。2014 年 6 月 17 日時点のオリジナルよりアーカイブ。2013年1 月 15 日閲覧。
• ハルブフィンガー、デビッド・M (2008 年 5 月 5 日)。「ペリカーノ事件で盗聴技術の教訓」ニューヨーク・タイムズ。
• Stajano, Frank (2006 年 2 月 10 日)。「Serpent リファレンス実装」。ケンブリッジ大学コンピュータ研究所。

• 公式サイト
• 256 ビット暗号 – SERPENT リファレンス実装と派生コード