UMAC (暗号化)

暗号学において、ユニバーサルハッシュメッセージ認証コード（UMAC）は、ユニバーサルハッシュを使用して計算されるメッセージ認証コード（MAC）であり、秘密の（ランダムな）プロセスに従ってハッシュ関数のクラスからハッシュ関数を選択し、それをメッセージに適用します。結果のダイジェストまたはフィンガープリントは、使用されたハッシュ関数のIDを隠すために暗号化されます。この方式のバリエーションは、1999年に初めて公開されました。^[1]他のMACと同様に、UMACはデータの整合性とメッセージの信頼性の両方を同時に検証するために使用できます。シリアル化可能な従来のMACとは対照的に、UMACは並列で実行できます。したがって、マシンがより多くの並列処理機能を提供し続けると、UMACの実装速度が向上します。^[1]

特定のタイプの UMAC (一般に単に「UMAC」とも呼ばれる) は、2006 年 3 月に RFC 4418 として公開された情報 RFCで説明されています。このタイプの UMAC は、証明可能な暗号強度を持ち、通常、他の MAC よりも計算負荷が大幅に少なくなります。UMAC の設計は、 SIMD をサポートする 32 ビット アーキテクチャ向けに最適化されており、SIMD ありで 1 CPU サイクル/バイト (cpb)、SIMD なしの場合は 2 cpb のパフォーマンスを実現します。64 ビット アーキテクチャ向けに最適化された UMAC の関連バリアントとして、VMACがあります。VMAC は、2007 年 4 月に IETF にドラフトとして提出されました ( draft-krovetz-vmac-01 ) が、RFC として承認されるほどの注目を集めることはできませんでした。

ハッシュ関数は、メッセージを可能なメッセージ ダイジェストのセットである D にマッピングするハッシュ関数のクラス H から選択されるものとします。このクラスは、任意の異なるメッセージのペアに対して、それらを D の同じメンバーにマッピングする関数が最大で |H|/|D| 個ある場合、 ユニバーサルと呼ばれます。

つまり、攻撃者が 1 つのメッセージを別のメッセージに置き換えたい場合、攻撃者の観点からハッシュ関数が完全にランダムに選択されたとすると、UMAC が攻撃者の変更を検出しない確率は最大で 1/|D| になります。

しかし、この定義は十分に強力ではありません。考えられるメッセージが 0 と 1 で、D={0,1} であり、H が恒等演算で構成され、ではない場合、H は普遍的です。ただし、ダイジェストがモジュラー加算によって暗号化されている場合でも、攻撃者はメッセージとダイジェストを同時に変更することができ、受信者は違いに気付かないでしょう。

ハッシュ関数 H のクラスを適切に使用すれば、攻撃者がダイジェストcを持つメッセージaを傍受した後、偽のメッセージfの正しいダイジェストd を推測することが困難になります。言い換えると、

${\displaystyle \Pr _{h\in H}[h(f)=d|h(a)=c]\,}$

非常に小さくする必要があり、1/| D | が望ましいです。

Dが体である場合、ハッシュ関数のクラスを構成するのは簡単です。たとえば、| D | が素数である場合、すべての演算は| D | を法として行われます。メッセージa は、 D ( a ₁ , a ₂ , ..., a _n )上のn次元ベクトルとしてエンコードされます。 すると、 H は| D | ^{n +1 個}のメンバーを持ち、それぞれがD ( h ₀ , h ₁ , ..., h _n )上の( n + 1)次元ベクトルに対応します。

${\displaystyle h(a)=h_{0}+\sum _{i=1}^{n}{h_{i}}{a_{i}}}$

確率と組み合わせの法則を使って証明できる。

${\displaystyle \Pr _{h\in H}[h(f)=d|h(a)=c]={1 \over |D|}}$

すべてのダイジェストを適切に暗号化すれば（たとえば、ワンタイム パッドを使用して）、攻撃者はそこから何も学ぶことができず、2 者間のすべての通信に同じハッシュ関数を使用できます。ECB 暗号化では、2 つのメッセージが同じハッシュ値を生成する可能性が高いため、これは当てはまらない場合があります。その場合は、何らかの初期化ベクトルを使用する必要があります。これは、多くの場合nonceと呼ばれます。h 0 = f (nonce) に設定_するのが一般的な方法になっています。ここで、fも秘密です。

大量のコンピュータパワーを持っていても、攻撃者にとってはまったく役に立たないことに注意してください。受信者が偽造を検出するたびにスリープ状態にするなどして、受け入れる偽造の数を制限すると、| D | は 2 ³²以下になる可能性があります。

次のC関数は 24 ビットの UMAC を生成します。 はsecret24 ビットの倍数であり、msgより長くなくsecret、resultすでに 24 個の秘密ビット (例: f(nonce)) が含まれていることを前提としています。 に nonce が含まれている必要はありませんmsg。

/* 疑わしい: これは (おそらく長い) RFC 定義とは何の関係もないようです
。 * これはおそらく、UMAC の一般的な概念の例です。
* 2007 年の Nroets はいったい誰が例に 3 バイトを選んだのでしょうか? 
* 
* これを、str. uni. hash のより適切な定義と一緒に
uni. hash に移動する必要があります。 */ 
#define uchar uint8_t 
void UHash24 ( uchar * msg , uchar * secret , size_t len , uchar * result ) { uchar r1 = 0 , r2 = 0 , r3 = 0 , s1 , s2 , s3 , byteCnt = 0 , bitCnt , byte ; while ( len -- > 0 ) { /* 3 バイトごとに新しいシークレットを取得します。 */ if ( byteCnt -- == 0 ) { s1 = * secret ++ ; s2 = * secret ++ ; s3 = * secret ++ ; byteCnt = 2 ; } byte = * msg ++ ; /* msg の各バイトは、秘密のビットがハッシュに含まれるかどうかを制御します。     *      * 3 バイトのものでは、定義上、多項式の順序 0-23 のみを保持するため、順序を 24 未満に保つことの意味がわかりません     。 "sec" コードの     動作は同じですが、各ビットに対して依然として多くの作業を行っています。     */ for ( uchar bitCnt = 0 ; bitCnt < 8 ; bitCnt ++ ) { /* 最後のビットは、秘密ビットが使用されるかどうかを制御します。 */ if ( byte & 1 ) { r1 ^= s1 ; /* (秒 >> 16) & 0xff */ r2 ^= s2 ; /* (秒 >> 8) & 0xff */ r3 ^= s3 ; /* (秒 ) & 0xff */ }         

                   
  
      
    
        
        
        
        
           
    
      
    





             
      
          
           
           
           
      
      byte >>= 1 ; /* 次のビット。 */ /* secret を x (つまり 2) で乗算し、         必要に応じて多項式を減算 (XOR で) して、その次数を 24 (?!) 未満に保ちます。 */ uchar doSub = s3 & 0x80 ; s3 <<= 1 ; if ( s2 & 0x80 ) s3 |= 1 ; s2 <<= 1 ; if ( s1 & 0x80 ) s2 |= 1 ; s1 <<= 1 ; if ( doSub ) { /* 0b0001 1011 --> */ s1 ^= 0x1B ; /* x^24 + x^4 + x^3 + x + 1 [16777243 -- 素数ではありません] */ } } /* メッセージ内の各ビットについて */ } /* メッセージ内の各バイトについて */ *結果++ ^= r1 ; *結果++ ^= r2 ; *結果++ ^= r3 ; }   
      

           
        
            
        
            
        
          
           
      
     
   
    
    
    

#define uchar uint8_t 
#define swap32(x) ((x) & 0xff) << 24 | ((x) & 0xff00) << 8 | ((x) & 0xff0000) >> 8 | (x) & 0xff000000) >> 24) 
/* これは同じものですが、グループ化されています (より優れたアセンブリなどを生成しています)。
   これはまだ良くなく、なぜこれが強力にユニバーサルなのかを誰も説明していません。 */ 
void UHash24Ex ( uchar * msg , uchar * secret , size_t len , uchar * result ) { uchar byte , read ; uint32_t sec = 0 , ret = 0 , content = 0 ;         

    
           

  while ( len > 0 ) { /* チャンクで 3 つ読み取ります。 */ content = 0 ; switch ( read = ( len >= 3 ? 3 : len )) { case 2 : content |= ( uint32_t ) msg​​ [ 2 ] << 16 ; /* FALLTHRU */ case 1 : content |= ( uint32_t ) msg​​ [ 1 ] << 8 ; /* FALLTHRU */ case 0 : content |= ( uint32_t ) msg​​ [ 0 ]; } len -= read ; msg += read ;    
    
      
              
              
               
           
    
         

    /* 3バイトごとに新しいシークレットを取得します。 */ 
sec = ( uint32_t ) secret [ 2 ] << 16 | ( uint32_t ) secret [ 1 ] << 8 | ( uint32_t ) secret [ 0 ]; secret += 3 ;                 
      

    /* 優れたコンプレッサー。 */ 
for ( bitCnt = 0 ; bitCnt < 24 ; bitCnt ++ ) { /* 削除すべきハードなデータ依存性: 出力は       中間値に依存します。       * CRC バイトテーブルでは実際には機能しません。 */ if ( byte & 1 ) { ret ^= sec ; } byte >>= 1 ; /* 次のビット。 */ /* シフトレジスタ。 */ sec <<= 1 ; if ( sec & 0x01000000 ) sec ^= 0x0100001B ; sec &= 0x00ffffff ; } /* メッセージ内の各ビットに対して */ } /* メッセージ内の各 3 バイトに対して */ result [ 0 ] ^= ret & 0xff ; result [ 1 ] ^= ( ret >> 8 ) & 0xff ;結果[ 2 ] ^= ( ret >> 16 ) & 0xff ; }            
      


          
          
      
         
      
        
         
          
        
     
   
      
         
        

上記の無名^[要引用]の強力に普遍的なハッシュ関数ファミリーの関数は、 n 回の乗算を使用してハッシュ値を計算します。

NH ファミリは乗算回数を半分に減らし、実質的にはおよそ 2 倍の高速化につながります。^[2]速度に関しては、UMAC は NH ハッシュ関数ファミリを使用します。NH はSIMD命令を使用するように特別に設計されているため、UMAC は SIMD に最適化された最初の MAC 関数です。^[1]

次のハッシュファミリーはユニバーサルである: ^[1]${\displaystyle 2^{-w}}$

${\displaystyle \operatorname {NH} _{K}(M)=\left(\sum _{i=0}^{(n/2)-1}((m_{2i}+k_{2i}){\bmod {~}}2^{w})\cdot ((m_{2i+1}+k_{2i+1}){\bmod {~}}2^{w})\right){\bmod {~}}2^{2w}}$。

どこ

• メッセージMはw_ビットワード（m0 _、m1、m2、...、mn _{-1 ）の}n次元ベクトルとしてエンコードされます。
• 中間鍵 K は、wビットワード ( k ₀、k ₁、k ₂、 ...、k _n )のn+1次元ベクトルとしてエンコードされます。疑似乱数ジェネレーターは、共有秘密鍵から K を生成します。

実際には、NH は符号なし整数で実行されます。すべての乗算は mod 2^ w、すべての加算は mod 2^ w /2 で、すべての入力はハーフワード ( ビット整数) のベクトルです。アルゴリズムは次に乗算を使用します。ここで、 はベクトル内のハーフワードの数です。したがって、アルゴリズムは入力のワードごとに 1 回の乗算の「速度」で実行されます。 ${\displaystyle w/2=32}$${\displaystyle \lceil k/2\rceil }$${\displaystyle k}$

RFC 4418 は、UMAC の NH のラッピングを説明する情報 RFCです。全体的な UHASH (「ユニバーサル ハッシュ関数」) ルーチンは、ハッシュの 3 つのレイヤーすべてに必要な反復回数 (およびキーの合計長) に対応する可変長のタグを生成します。AES ベースのキー導出関数を複数回呼び出すことで、3 つのキー付きハッシュすべてにキーが提供されます。

• レイヤー 1 (1024 バイトのチャンク -> 8 バイトのハッシュが連結) は高速であるため NH を使用します。
• レイヤー 2 は、入力のサイズが大きくなるにつれて素数が変化する、素数係数演算を実行する POLY 関数を使用して、すべてを 16 バイトにハッシュします。
• レイヤー 3 は、16 バイトの文字列を 4 バイトの固定長にハッシュします。これが 1 回の反復で生成されるものです。

RFC 4418 では、NH は次の形式になるように再編成されています。

Y = 0
の場合(i = 0; i < t; i += 8)の場合終了
    ${\displaystyle {\begin{aligned}{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+0}+_{32}K_{i+0})*_{64}(M_{i+4}+_{32}K_{i+4}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+1}+_{32}K_{i+1})*_{64}(M_{i+5}+_{32}K_{i+5}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+2}+_{32}K_{i+2})*_{64}(M_{i+6}+_{32}K_{i+6}))}}\\{\mathtt {Y}}&={\mathtt {Y+_{64}((M_{i+3}+_{32}K_{i+3})*_{64}(M_{i+7}+_{32}K_{i+7}))}}\end{aligned}}}$

この定義は、プログラマが累積時に SIMD 命令を使用するように促すために設計されています。これは、4 つのインデックスが離れたデータだけが同じ SIMD レジスタに格納されない可能性が高いため、一括乗算が高速になるからです。仮想マシンでは、次のように簡単に変換できます。

movq $ 0 , regY ; Y = 0 movq $ 0 , regI ; i = 0 loop: add reg1 , regM , regI ; reg1 = M + i add reg2 , regM , regI vldr.4x32 vec1 , reg1 ; メモリ *reg1 から 4x32 ビット値を vec1 にロードvldr.4x32 vec2 , reg2 vmul.4x64 vec3 , vec1 , vec2 ; vec3 = vec1 * vec2 uaddv.4x64 reg3 , vec3 ; vec3 を reg3 に水平方向に合計add regY , regY , reg3 ; regY = regY + reg3 add regI 、regI 、$ 8 cmp regI 、regT jltループ             
             

            
           
           
    
      
          
            
           
          
         

• Poly1305、強力なユニバーサルハッシュに基づく別の高速MAC
• MMH-Badger MAC、もう一つの高速MAC

• Ted Krovetz。「UMAC: 高速かつ証明可能なセキュリティを備えたメッセージ認証」。

• Miller, Damien; Valchev, Peter (2007-09-03)。「SSH トランスポート層プロトコルにおける UMAC の使用: draft-miller-secsh-umac-01.txt」。IETF。