この投稿では、Habrユーザーに暗号アルゴリズムプログラミングの基本的なルールを紹介します。 「暗号化コーディング標準」と呼ばれるこのルールセットは、2013年に現代暗号の達人の1人であるJean-Philippe Omassonの主導で作成されました。 ここで説明されているアプローチは、セキュリティシステムの開発に専門的に携わっている人々にはよく知られているにもかかわらず、初心者や学生にとっては、サイトcryptocoding.netからの一連のルールの翻訳である提案されたテキストに精通することは興味深いと思います。

1.一定時間で秘密データの行を比較する

問題

文字列のバイト比較を使用して、プログラムの実行時間に関する情報を使用する攻撃（いわゆるタイミング攻撃）を実装して、たとえばMACメッセージの認証コードを偽造することができます（ Google Keyczar暗号化ライブラリの脆弱性を参照）。



memcmp関数、Arrays.equals（Java）メソッド、または==（Python）演算子などの比較機能の組み込み実装は、通常一定時間で実行されません。 たとえば、 Microsoft CRTからの[memcmp]の実装を検討してください。

EXTERN_C int __cdecl memcmp(const void *Ptr1, const void *Ptr2, size_t Count) { INT v = 0; BYTE *p1 = (BYTE *)Ptr1; BYTE *p2 = (BYTE *)Ptr2; while(Count-- > 0 && v == 0) { v = *(p1++) - *(p2++); } return v; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

解決策

NaCLライブラリで提供されるような、一定の時間にわたって実行される比較関数を使用します。

 int crypto_verify(const unsigned char *x,const unsigned char *y) { unsigned int differentbits = 0; #define F(i) differentbits |= x[i] ^ y[i]; F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) F(10) F(11) F(12) F(13) F(14) F(15) return (1 & ((differentbits - 1) >> 8)) - 1; /* returns 0 if equal, 0xFF..FF otherwise */ }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

同じアプローチのより一般的なバージョンは次のとおりです。

 int util_cmp_const(const void * a, const void *b, const size_t size) { const unsigned char *_a = (const unsigned char *) a; const unsigned char *_b = (const unsigned char *) b; unsigned char result = 0; size_t i; for (i = 0; i < size; i++) { result |= _a[i] ^ _b[i]; } return result; /* returns 0 if equal, nonzero otherwise */ }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

固定時間で実行される32ビット値の比較関数とテストの実装例を検討してください。

 #include <stdint.h> /*    */ /*  1   , 0   */ int ct_isnonzero_u32(uint32_t x) { return (x|-x)>>31; } int ct_iszero_u32(uint32_t x) { return 1 ^ ct_isnonzero_u32(x); } int ct_neq_u32(uint32_t x, uint32_t y) { return ((xy)|(yx))>>31; } int ct_eq_u32(uint32_t x, uint32_t y) { return 1 ^ ct_neq_u32(x, y); } int ct_lt_u32(uint32_t x, uint32_t y) { return (x^((x^y)|((xy)^y)))>>31; } int ct_gt_u32(uint32_t x, uint32_t y) { return ct_lt_u32(y, x); } int ct_le_u32(uint32_t x, uint32_t y) { return 1 ^ ct_gt_u32(x, y); } int ct_ge_u32(uint32_t x, uint32_t y) { return 1 ^ ct_lt_u32(x, y); } /*    */ /*  1   , 0   */ int ct_isnonzero_s32(uint32_t x) { return (x|-x)>>31; } int ct_iszero_s32(uint32_t x) { return 1 ^ ct_isnonzero_s32(x); } int ct_neq_s32(uint32_t x, uint32_t y) { return ((xy)|(yx))>>31; } int ct_eq_s32(uint32_t x, uint32_t y) { return 1 ^ ct_neq_s32(x, y); } int ct_lt_s32(uint32_t x, uint32_t y) { return (x^((x^(xy))&(y^(xy))))>>31; } int ct_gt_s32(uint32_t x, uint32_t y) { return ct_lt_s32(y, x); } int ct_le_s32(uint32_t x, uint32_t y) { return 1 ^ ct_gt_s32(x, y); } int ct_ge_s32(uint32_t x, uint32_t y) { return 1 ^ ct_lt_s32(x, y); } /* Generate a mask: 0xFFFFFFFF if bit != 0, 0 otherwise */ uint32_t ct_mask_u32(uint32_t bit) { return -(uint32_t)ct_isnonzero_u32(bit); } /*  x  y      bit*/ /* : return bit ? x : y */ uint32_t ct_select_u32(uint32_t x, uint32_t y, uint32_t bit) { uint32_t m = ct_mask_u32(bit); return (x&m) | (y&~m); /* return ((x^y)&m)^y; */ }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらのアプローチは何の保証も与えません：CおよびC ++は、 「as if」ルールを使用します。これにより、プログラムの観察された動作（ランタイムは両方の言語で観察可能な動作とは見なされません）がコンパイラーに任意に実装できるようになります。 たとえば、次のct_​​select_u32オプションを検討してください。

 uint32_t ct_select_u32(uint32_t x, uint32_t y, _Bool bit) { uint32_t m = ct_mask_u32(bit); return (x&m) | (y&~m); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

パラメータclang-3.5 -O2 -m32 -march = i386でこのコードをコンパイルすると、結果が得られます。

 ct_select_u32: mov al, byte ptr [esp + 12] test al, al jne .LBB0_1 lea eax, dword ptr [esp + 8] mov eax, dword ptr [eax] ret .LBB0_1: lea eax, dword ptr [esp + 4] mov eax, dword ptr [eax] ret
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

条件分岐命令の実行速度は不均一であるため、このコードは選択されたシークレット値を明らかにする可能性があります。 コンパイラは、さまざまな時間に実行できるコードを生成する際にほぼ無限の自由があるため、一定時間実行される最終アセンブリを確認する必要があります。

秘密のプログラムの分岐を避ける

問題

プログラムの条件付き分岐（if、switch、while、for）がシークレットデータに依存する場合、実行可能コードとその実行時間はシークレットデータに依存します。



この脆弱性を悪用する典型的な例は、2乗と乗算（または楕円曲線を使用するアルゴリズムの2倍と加算）に基づく指数アルゴリズムのタイミング攻撃です。



この問題の特定のケースは、カウンターの境界値が秘密の値に依存するサイクルです。

解決策

プログラムの実行時間のリークは、プログラムの実行に固定時間を保証するために、プログラムの分岐にダミー操作を挿入することで対処できます。 ただし、条件付きステートメントを簡単なプログラムとして実装するなどして、分岐を完全に回避する方がはるかに信頼性が高くなります。 たとえば、2つの入力の選択| a | および| b | 制御ビットに応じて|ビット| 次のように実装できます。

 unsigned select (unsigned a, unsigned b, unsigned bit) { /* -0 = 0, -1 = 0xff....ff */ unsigned mask = - bit; unsigned ret = mask & (a^b); ret = ret ^ a; return ret; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Intelプロセッサの場合、 CMOV条件分岐命令の使用に基づく、より高速なソリューションが可能です。

秘密の機密データテーブルへのアクセスを避ける

問題

テーブル要素へのアクセス時間は、そのインデックスの値によって異なります（たとえば、要素がキャッシュにない場合）。 この効果は、AESの多くのキャッシュ攻撃で使用されました。

解決策

テーブルコールを、たとえばビットスライス技術を使用して、一定の実行時間を持つ一連の論理演算に置き換えます。

カウンターの制限値が秘密の値に依存するサイクルを避けます

問題

秘密の値に依存するカウンター境界値を持つループは、実行時による攻撃に対してプログラムを直接脆弱にします。 たとえば、OpenSSL 0.9.8oでのMontgomeryラダー（指数アルゴリズム）の実装により、対数（秘密の乱数）がECDSAアルゴリズムで漏洩し、TLSサーバーの秘密鍵の取得に使用される可能性がありました。 対応するプログラムコードを以下に示します。 ここ|スカラー| 秘密の乱数であり、| scalar-> d | -そのビットの配列へのポインタ：

 /* find top most bit and go one past it */ i = scalar -> top - 1; j = BN_BITS2 - 1; mask = BN_TBIT ; while (!( scalar -> d[i] & mask )) { mask >>= 1; j --; } mask >>= 1; j - -; /* if top most bit was at word break , go to next word */ if (! mask ) { i - -; j = BN_BITS2 - 1; mask = BN_TBIT ; } for (; i >= 0; i - -) { for (; j >= 0; j - -) { if ( scalar ->d[ i] & mask ) { if (! gf2m_Madd ( group , & point ->X , x1 , z1 , x2 , z2 , ctx )) goto err ; if (! gf2m_Mdouble ( group , x2 , z2 , ctx )) goto err ; } else { if (! gf2m_Madd ( group , & point ->X , x2 , z2 , x1 , z1 , ctx )) goto err ; if (! gf2m_Mdouble ( group , x1 , z1 , ctx )) goto err ; } mask >>= 1; } j = BN_BITS2 - 1; mask = BN_TBIT; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

解決策

すべてのループの反復回数が定数（または少なくとも分類されていない変数）によって制限されていることを確認してください。



特に、可能な限り、カウンター値がこれらの制限を超えたり、それらに達しないサイクルと状況の境界がユーザー制御の入力データに依存しないことを確認します（誰もあなた自身のHeartbleedを必要としませんか？）。



続行するには...