ユーマック

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

UMAC の特定のタイプ (一般にUMACとも呼ばれる) は、RFC 4418 で指定されており、証明可能な暗号強度を持ち、通常、他の MAC よりも計算負荷がはるかに少ないです。UMAC の設計は、SIMD をサポートする 32 ビット アーキテクチャ向けに最適化されており、SIMD ありで 1 CPU サイクル/バイト (cpb)、SIMD なしの場合は 2 cpb のパフォーマンスを実現します。UMAC に密接に関連し、64 ビット アーキテクチャ向けに最適化されたバリアントがVMACです。これは 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 の各バイトは、秘密のビットがハッシュに含まれるかどうかを制御します。     *      * 順序を 24 未満に保つことの意味がわかりません。3 バイトのものでは     、定義上、0 から 23 の多項式しか保持できないからです。"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 は、NH をラップして優れた UMAC にするために多くのことを行います。全体的な 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}}}$

この定義は、4 つのインデックスが離れたデータだけが同じ SIMD レジスタに格納されない可能性が高いため、プログラマが累積時に 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 ; 4x32 ビット値をメモリ *reg1 から 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 は、強力なユニバーサル ハッシュに基づくもう 1 つの高速 MAC です。

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

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