かすみ

KASUMIは、 UMTS、GSM、GPRSモバイル通信システムで使用されるブロック暗号です。UMTSでは、KASUMIは機密性アルゴリズム（f8）と整合性アルゴリズム（f9）でそれぞれUEA1とUIA1という名前で使用されています。^[1] GSMでは、KASUMIはA5/3キーストリームジェネレーターで使用され、GPRSではGEA3キーストリームジェネレーターで使用されます。

KASUMIは、欧州標準化団体ETSIの一部門であるセキュリティアルゴリズム専門家グループ（SAGE）によって、UMTSセキュリティシステムで使用するために3GPP向けに設計されました。^[2] 3GPP標準化のスケジュール上のプレッシャーのため、新しい暗号を開発する代わりに、SAGEは3Gセキュリティのシステム側面（SA3）に関する3GPP技術仕様グループ（TSG）と合意し、すでに評価済みの既存のアルゴリズムをベースに開発を進めました。^{[2]彼らは、}三菱電機 が開発し^[3] 、特許を取得した^[4] 暗号アルゴリズムMISTY1を選択しました。元のアルゴリズムは、ハードウェア実装を容易にし、3Gモバイル通信セキュリティに設定された他の要件を満たすために若干変更されました。

KASUMI は、オリジナルのアルゴリズムMISTY1にちなんで名付けられました。霞 (ひらがな かすみ、ローマ字かすみ) は日本語の「霧」を意味します。

2010年1月、オー・ダンケルマン、ネイサン・ケラー、アディ・シャミールは、関連鍵攻撃と非常に控えめな計算リソースでKasumiを破ることができることを示す論文を発表しました。この攻撃はMISTY1には効果がありません。^[5]

KASUMIアルゴリズムは3GPP技術仕様で規定されています。^[6] KASUMIは128ビットの鍵と64ビットの入出力を持つブロック暗号です。KASUMIの核となるのは8ラウンドのFeistelネットワークです。メインのFeistelネットワークのラウンド関数は不可逆なFeistelのようなネットワーク変換です。各ラウンドでは、ラウンド関数は固定キースケジュールを使用して元の128ビットの鍵から派生した8つの16ビットのサブキーで構成されるラウンドキーを使用します。

128ビットのキーKは8つの16ビットのサブキーK _iに分割されます。

${\displaystyle K=K_{1}\|K_{2}\|K_{3}\|K_{4}\|K_{5}\|K_{6}\|K_{7}\|K_{8}\,}$

さらに、同様に 16 ビットのサブキーK' _iに分割された修正キーK'が使用されます。修正キーは、 0x123456789ABCDEFFEDCBA9876543210 ( 「秘密の」番号として選択) との XOR 演算によって元のキーから導出されます。

ラウンド キーは、指定された量だけ左にビット単位で回転することによってサブ キーから派生されるか、変更されたサブ キー (変更なし) から派生されます。

ラウンドキーは次のとおりです。

${\displaystyle {\begin{array}{lcl}KL_{i,1}&=&{\rm {ROL}}(K_{i},1)\\KL_{i,2}&=&K'_{i+2}\\KO_{i,1}&=&{\rm {ROL}}(K_{i+1},5)\\KO_{i,2}&=&{\rm {ROL}}(K_{i+5},8)\\KO_{i,3}&=&{\rm {ROL}}(K_{i+6},13)\\KI_{i,1}&=&K'_{i+4}\\KI_{i,2}&=&K'_{i+3}\\KI_{i,3}&=&K'_{i+7}\end{array}}}$

サブキー インデックスの追加は循環的であるため、i+jが 8 より大きい場合は、実際のサブキー インデックスを取得するために結果から 8 を減算する必要があります。

KASUMI アルゴリズムは、64 ビットのワードを 2 つの 32 ビットの左半分 ( ) と右半分 ( ) に分けて処理します。入力ワードは、第 1 ラウンドの左半分と右半分を連結したものです。 ${\displaystyle L_{i}}$${\displaystyle R_{i}}$

${\displaystyle {\rm {input}}=R_{0}\|L_{0}\,}$。

各ラウンドで右半分はラウンド関数の出力と XOR され、その後半分が交換されます。

${\displaystyle {\begin{array}{rcl}L_{i}&=&F_{i}(KL_{i},KO_{i},KI_{i},L_{i-1})\oplus R_{i-1}\\R_{i}&=&L_{i-1}\end{array}}}$

ここで、KL _i、KO _i、KI _iはi^番目のラウンドのラウンドキーです。

偶数ラウンドと奇数ラウンドのラウンド関数は若干異なります。いずれの場合も、ラウンド関数は2つの関数FL _iとFO _iの組み合わせです。奇数ラウンドの場合

${\displaystyle F_{i}(K_{i},L_{i-1})=FO(KO_{i},KI_{i},FL(KL_{i},L_{i-1}))\,}$

そして、均等なラウンドのために

${\displaystyle F_{i}(K_{i},L_{i-1})=FL(KL_{i},FO(KO_{i},KI_{i},L_{i-1}))\,}$。

出力は最後のラウンドの出力の連結です。

${\displaystyle {\rm {出力}}=R_{8}\|L_{8}\,}$。

FL関数とFO関数はどちらも、32 ビットの入力データを 2 つの 16 ビットの半分に分割します。FL関数は不可逆なビット操作ですが、FO関数は不可逆な 3 ラウンドの Feistel のようなネットワークです。

の32 ビット入力xは2 つの 16 ビットの半分に分割されます。まず、入力の左半分はラウンド キーを使用してビットごとに AND され、1 ビット左に回転されます。その結果は入力の右半分と XOR され、出力の右半分が得られます。 ${\displaystyle FL(KL_{i},x)}$${\displaystyle x=l\|r}$${\displaystyle l}$${\displaystyle KL_{i,1}}$${\displaystyle r}$${\displaystyle r'}$

${\displaystyle r'={\rm {ROL}}(l\wedge KL_{i,1},1)\oplus r}$

次に、出力の右半分をラウンド キーとビット単位で OR し、1 ビット左に回転させます。その結果を入力の左半分と XOR して、出力の左半分を取得します。 ${\displaystyle r'}$${\displaystyle KL_{i,2}}$${\displaystyle l}$${\displaystyle l'}$

${\displaystyle l'={\rm {ROL}}(r'\vee KL_{i,2},1)\oplus l}$

関数の出力は左半分と右半分の連結です。 ${\displaystyle x'=l'\|r'}$

の32ビット入力xは2つの16ビットの半分に分割され、Feistelネットワークの3ラウンドを通過します。 ${\displaystyle FO(KO_{i},KI_{i},x)}$${\displaystyle x=l_{0}\|r_{0}}$

3 つのラウンドのそれぞれ (値 1、2、3 を取る jでインデックス付けされます) で、左半分が変更されて新しい右半分が得られ、右半分が次のラウンドの左半分になります。

${\displaystyle {\begin{array}{lcl}r_{j}&=&FI(KI_{i,j},l_{j-1}\oplus KO_{i,j})\oplus r_{j-1}\\l_{j}&=&r_{j-1}\end{array}}}$

関数の出力は です。 ${\displaystyle x'=l_{3}\|r_{3}}$

関数FI は不規則な Feistel のようなネットワークです。

関数の16 ビット入力は、9 ビット幅と7 ビット幅 の2 つの部分に分割されます。${\displaystyle x}$${\displaystyle FI(Ki,x)}$${\displaystyle x=l_{0}\|r_{0}}$${\displaystyle l_{0}}$${\displaystyle r_{0}}$

左半分のビットは、まず 9 ビットの置換ボックス(S ボックス) S9によってシャッフルされ、その結果がゼロ拡張された右半分と XOR されて、新しい 9 ビットの右半分が生成されます。 ${\displaystyle l_{0}}$${\displaystyle r_{0}}$${\displaystyle r_{1}}$

${\displaystyle r_{1}=S9(l_{0})\oplus (00\|r_{0})\,}$

右半分のビットは7 ビットの S ボックスS7によってシャッフルされ、その結果は新しい右半分の最下位 7 ビット ( LS7 ) と XOR 演算されて、新しい 7 ビットの左半分が生成されます。 ${\displaystyle r_{0}}$${\displaystyle r_{1}}$${\displaystyle l_{1}}$

${\displaystyle l_{1}=S7(r_{0})\oplus LS7(r_{1})\,}$

中間ワードはラウンド キー KI と XOR 演算され、 7ビット幅と9 ビット幅になります。 ${\displaystyle x_{1}=l_{1}\|r_{1}}$${\displaystyle x_{2}=l_{2}\|r_{2}}$${\displaystyle l_{2}}$${\displaystyle r_{2}}$

${\displaystyle x_{2}=KI\oplus x_{1}}$

次に、右半分のビットは9 ビットの S ボックスS9によってシャッフルされ、その結果はゼロ拡張された左半分と XOR 演算されて、出力の新しい 9 ビットの右半分が得られます。 ${\displaystyle r_{2}}$${\displaystyle l_{2}}$${\displaystyle r_{3}}$

${\displaystyle r_{3}=S9(r_{2})\oplus (00\|l_{2})\,}$

最後に、左半分のビットは7 ビットの S ボックスS7によってシャッフルされ、その結果は出力の右半分の最下位 7 ビット ( LS7 ) と XOR され、出力の 7 ビットの左半分が得られます。${\displaystyle l_{2}}$${\displaystyle r_{3}}$${\displaystyle l_{3}}$

${\displaystyle l_{3}=S7(l_{2})\oplus LS7(r_{3})\,}$

出力は最終的な左半分と右半分の連結です。 ${\displaystyle x'=l_{3}\|r_{3}}$

置換ボックス( S ボックス) S7 と S9 は、仕様ではビット単位の AND-XOR 式とルックアップ テーブルの両方で定義されています。ビット単位の式はハードウェア実装を目的としていますが、現在では HW 設計でもルックアップ テーブルを使用するのが一般的です。

S7 は次の配列によって定義されます。

int S7 [ 128 ] = { 54 , 50 , 62 , 56 , 22 , 34 , 94 , 96 , 38 , 6 , 63 , 93 , 2 , 18 , 123 , 33 , 55 , 113 , 39 , 114 , 21 、67、65、12、47、73、46、27、25、111、124、81、53、9、121、79、52、60、58、48、101、127、40 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 120、104​​ 、70、71、43、20、122、72、61、23、109、13、100、77、1、16、7、82、10、105、98、117、116、76 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​11、89、106、0、125、118、99、86、69、30、57、126、87、112、51、17、5、95、14、90、84、91、8 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​35、103 、​​ 32、97、28、66、102、31、26 、​​​​​​​​​​​​   
                   
              
              
                
             
                  
     45、75、4、85、92、37、74、80、49、68、29、115、44、64、107、108、24、110、83、36、78、42、19​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、15 、41 、88 、119 、59 、3 };            
               

S9 は次の配列によって定義されます。

int S9 [ 512 ] = { 167 , 239 , 161 , 379 , 391 , 334 , 9 , 338 , 38 , 226 , 48 , 358 , 452 , 385 , 90 , 397 , 183 , 253 , 147 、331 、415 、340 、51 、362 、306 、500 、262 、82 、216 、159 、356 、177 、175 、241 、489 、37 、206 、17 、0 、333 、44、254、378、58、143、220、81、400、95、3、315、245、54、235、218、405、472、264、172、494、371​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​、290 、399 、76 、165 、197 、395 、121 、257 、480 、423 、212 、240 、28 、462 、176 、406 、507 、288 、223 、501 、407 、249 、265 、89 、186 、221 、428 、164 、74 、440 、196 、458 、421 、350 、163 、232 、   
       
    
         
       
   
    
  158 、134 、354 、13 、250 、491 、142 、191 、69 、193 、425 、152 、227 、366 、135 、344 、300 、276 、242 、437 、320、113、278、11、243、87、317、36、93、496、27、487、446、482、41、68、156、457、131、326 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 403、339 、​​ 20、39、115、442、124、475、384、508、53、112、170、479、151、126、169、73、268、279、321、168 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​364 、363 、292 、46 、499 、393 、327 、324 、24 、456 、267 、157 、460 、488 、426 、309 、229 、439 、506 、208 、271、349 、​​ 401 、434 、236 、16 、209 、359 、52 、56 、120 、199 、277 、465 、416 、252 、287 、246 、6  
       
  
      
    
    
     
    、83 、305 、420 ​​、345 、153 、502 、65 、61 、244 、282 、173 、222 、418 、67 、386 、368 、261 、101 、476 、291 、195 、430 、49 、79 、166 、330 、280 、383 、373 、128 、382 、408 、155 、495 、367 、388 、274 、107 、459 、417 、62 、454 、132 、225 、203 、316 、234 、14 、301 、91 、503 、286 、424 、211 、347 、307 、140 、374 、35 、103 、125 、427、19、214、453、146、498、314、444、230、256、329、198、285、50、116、78、410、10、205、510 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​171、231 、​​ 45、139、467、29、86、505、32、72、26、342、150、313、490、431、238、411、325 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​   
     
   
    
  
    
         
    149 、473 、40 、119 、174 、355 、185 、233 、389 、71 、448 、273 、372 、55 、110 、178 、322 、12 、469 、392 、369 、190 、1 、109 、375 、137 、181 、88 、75 、308 、260 、484 、98 、272 、370 、275 、412 、111 、336 、318 、4 、504 、492、259、304、77、337、435、21、357、303、332、483、18、47、85、25、497、474、289、100、269 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​296、478、270、106、31、104、433、84、414、486、394、96、99、154、511、148、413、361、409、255 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​162、215、302​​​​ 、201、266、351、343、144、441、365、108、298、251、34、182、509、138、210、335​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 
     
       
       
       
    
  
   、133、311、352、328、141、396、346、123、319、450、281、429、228、443、481、92、404、485、422 、
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 248、297、23、213、130、466、22、217、283、70、294、360、419、127、312、377、7、468、194、2、117​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​ 、295 、463、258、224、447、247、187、80、398、284、353、105、390、299、471、470、184、57、200、348、63 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​204、188、33、451、97、30、310、219、94、160、129、493、64、179、263、102、189、207、114、402 、​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​438 、477 、387 、122 、192 、42 、381 、5 、145 、118 、180 、449 、293 、323 、136 、380 、43 、66 、60 、   
     
       
     
      
     
     455 、341 、445 、202 、432 、8 、237 、15 、376 、436 、464 、59 、461 };