Py（暗号）

Py は、 Eli BihamとJennifer SeberryによってeSTREAMに提出されたストリーム暗号です。一部のプラットフォームでは 1 バイトあたり約 2.6 サイクルで、eSTREAM 候補の中でも最速の暗​​号の 1 つです。構造はRC4に少し似ていますが、バイトの順列を使用してインデックス付けされた 260 個の 32 ビット ワードの配列を追加し、各ラウンドで 64 ビットを生成します。

著者らは、この暗号がオーストラリアに起源を持つことにちなんで、この名前は「ルー」と発音すべきだと主張している。つまり、「Py」の文字をラテン文字ではなくキリル文字(Ру) で読むということである。このややひねくれた発音は、Advanced Encryption Standardとして採用された暗号のRijndael という発音しにくい名前に対する、冗談めいた返答であると理解されている。

• 2005 年 4 月の最初の提案には、暗号 Py と、その簡略化されたバージョンの Py6 が含まれていました。後者は、最大出力長が短くなる代わりに、一部の内部テーブルのサイズを縮小し、キーのスケジュール コストを大幅に削減します。
• 2006 年 6 月、著者らはオプションのより強力な変種として Pypy (さらに紛らわしいことに、半分キリル文字の Pyру で、「Pyroo」と発音されます) を説明しました。これは、Py の各反復から出力単語の 1 つを省略するため、Py の半分強の速度で動作します (実際には約 0.6 倍)。
• 2007 年 1 月に、キー スケジュール アルゴリズムが変更され、「調整された」バリアント TPy、TPypy、TPy6 が作成されました。正確には、最初の (キー依存) フェーズは変更されていませんが、2 番目の (IV セットアップ) フェーズではエラーが修正されています。出力を生成するために使用されるラウンド関数は同一です。
• Indocrypt 2007 で、Gautham Sekar、Souradyuti Paul、Bart Preneel は、それぞれ Pypy と Py の設計原理に基づいた 2 つの新しい暗号 RCR-32 と RCR-64 を提案しました。これらは Py の可変回転を固定回転に置き換え、攻撃を排除し、暗号をわずかに高速化します。TPy キー スケジュールは変更されずに使用されます。

2006年現在^{[アップデート]}、Pyに対する最良の暗号解読攻撃（Hongjun WuとBart Preneelによる）は、状況によっては（例えばIVが鍵よりもはるかに長い場合）、 2 ^{24個の選択されたIVの部分的な}キーストリームが与えられた場合に鍵を復元することができる[1]。

攻撃者の観点からより困難なシナリオでは、選択された平文ではなく既知の平文のみが与えられた場合、約 2 ⁷²バイトの出力と同程度の時間を必要とするキーストリームに対する特徴的な攻撃(Paul Crowley による) もあります。これは、 2 ^{88バイトを必要とする Gautham Sekar、} Souradyuti Paul、およびBart Preneelによって提示された攻撃の改良版です。これらの攻撃が Py の学術的な破りを構成するかどうかはまだ議論があります。攻撃者は、上記の攻撃は Py の設計仕様に基づく網羅的な検索よりも少ない作業負荷で構築できるため、明らかに理論上の暗号破りであると主張しますが、設計者は Py のセキュリティ境界により、あらゆる場所のすべてのキーストリームにわたる攻撃者の合計出力が 2 ⁶⁴バイトに制限されるため、これらの攻撃を除外します。Paul、Preneel、Sekar の論文 の最近の改訂版では、第 9 節でこの問題に関する詳細な議論が含まれています。Wu と Preneel の攻撃の正当性については疑いの余地はありません。

PyはeSTREAMプロジェクト[2]によってプロファイル1（ソフトウェア）のフェーズ2フォーカス候補として選ばれましたが、WuとPreneelが選択したIV攻撃によりフェーズ3に進みませんでした。[3]

2007 年 1 月、上記の攻撃を排除するために、TPy、TPypy、TPy6 という 3 つの新しい暗号が Py の設計者によって提案されました。TPy は、鍵スケジュールに依存しないPaulら (複雑度 2 ⁸⁸ ) および Crowley (複雑度 2 ⁷² ) による上記の識別攻撃に対して依然として脆弱です。Py ファミリの暗号の中で最も強力であると推測される TPypy に対するこれまでの最良の攻撃は、Sekar らによるデータ複雑度 2 ²⁸¹の識別攻撃です。この攻撃は、TPypy の鍵サイズが 281 ビットより長い場合にのみ意味を持ちます。

TPy と TPypy への攻撃を排除するために、Sekar、Paul、Preneel はIndocrypt 2007 で 2 つの新しい暗号 RCR-32 と RCR-64 を提案しました。今のところ、RCR-32 と RCR-64 に対する攻撃はありません。

Py は「スライディング配列」という考え方に基づいています。配列は開始ポインターを基準としてインデックス付けされ、開始ポインターは各ラウンドで 1 ワードずつ進みます。モジュロ インデックス付けが可能な場合 (ハードウェア、および多くのデジタル信号プロセッサ)、これらは循環バッファとして実装できます。ソフトウェアでは、これらは大きな配列として実装するのが最も簡単です。配列の末尾に達すると、作業部分が先頭にコピーされ、操作が続行されます。

256 バイトの P 配列には 256 エントリの順列 (各バイトは 1 回だけ出現) が含まれ、Y 配列には 260 個の 32 ビット ワードが含まれます。

#include <stdint.h> 
#ROTL32(x, s) を定義します ((x)<<(s) | (x)>>(32-(s)))
uint8_t * P ; // P[0]からP[255]がアクティブ      
uint32_t * Y ; // Y[-3]からY[256]がアクティブ     
uint32_t s ; 
uint32_t *出力; 

while (出力ワード-- ) {  
        Y [ 185 ] % 256 ;​​​     
        P [ 256 ] = P [ i ]; // これは実質的にP[0]とP[i]を入れ替える       
        P [ i ] = P [ 0 ]; // 次にP[0]をP[256]にコピーします         
        P ++ ; // 以前のP[1]は新しいP[0]、書き込まれたばかりのP[256]は新しいP[255]  

        s += Y [ P [ 72 ]] - Y [ P [ 239 ]];    
        s = ROTL32 ( s 、( P [ 116 ] + 18 ) % 32 );       

        *出力++ = ( ROTL32 ( s , 25 ) ^ Y [ 256 ]) + Y [ P [ 26 ]]; // この行は Pypy と TPypy では省略されています         
        *出力++ = ( s ^ Y [ -1 ] ) + Y [ P [ 208 ]];                   
        Y [ 257 ] = ( ROTL32 ( s , 14 ) ^ Y [ -3 ] ) + Y [ P [ 153 ]];           
        Y ++ ; // 以前のP[-2]は新しいP[-3]、今書き込まれたP[257]は新しいP[256]  
}

バイト出力が必要な場合、Py は出力ワードがリトルエンディアンに変換されることを指定します。

Pypy、Tpypy、RCR-32 では 17 行目が省略されています。

RCR-32 と RCR-64 は、15 行目が 19 ビットの固定左回転に変更されることを除いて、上記と同じです。

Py6 の構造は同じですが、P 配列と Y 配列はそれぞれ 64 バイトと 68 ワードに短縮されています。P エントリは 6 ビット長のみで、この節約は専用ハードウェアで活用できます。もちろん、P[]およびへのさまざまなオフセットはY[]変更され、内部ループが作成されます。

while (出力ワード-- ) {  
        整数i = Y [ 43 ] % 64 ;     
        P [ 64 ] = P [ i ];  
        P [ i ] = P [ 0 ];  
        Ｐ++ ；

        s += Y [ P [ 18 ]] - Y [ P [ 57 ]];    
        s = ROTL32 ( s 、( P [ 26 ] + 18 ) % 32 );       

        *出力++ = ( ROTL32 ( s , 25 ) ^ Y [ 64 ]) + Y [ P [ 8 ]];       
        *出力++ = ( s ^ Y [ -1 ]) + Y [ P [ 21 ]];                  
        Y [ 65 ] = ( ROTL32 ( s , 14 ) ^ Y [ -3 ]) + Y [ P [ 48 ]];           
        Y ++ ;
}

• Eli Biham、Jennifer Seberry、Py 仕様 ( PostScript )
• Eli Biham、Jennifer Seberry、ストリーム暗号 Py ファミリーの IV 設定の調整 - 暗号 TPy、TPypy、および TPy6
• Py の eStream ページ
• ポール・クロウリー、Pyの暗号解読
• Souradyuti Paul、Bart Preneel、Gautham Sekar、ストリーム暗号 Py に対する攻撃の区別、FSE 2006。
• Gautham Sekar、Souradyuti Paul、Bart Preneel、「ストリーム暗号 TPypy および TPy の疑似ランダム ビット生成アルゴリズムの弱点」、IACR-ePrint レポート。
• Souradyuti Paul、Bart Preneel、「配列とモジュラー加算に基づくストリーム暗号の安全性 (非安全性) について (完全版)」、Asicrypt 2006。
• Gautham Sekar、Souradyuti Paul、Bart Preneel、「Py ファミリーの暗号に対する関連キー攻撃と弱点を修復するためのアプローチ」、Indocrypt 2007。
• Rijndael ページ - 「Rijndael FAQ」は、Py 仕様の付録 B で軽くパロディ化されています。