GSE R 34.12 '15 SSE2、または悪いバッタではない

Habréでは、ブロック暗号化の新しい国内標準GOST R 34.12 2015「Grasshopper」の少なくとも2倍が言及され 、 ru_cryptは彼の投稿で新しい標準の基本的なメカニズムと変換を調べ、 sebastian_mgは基本的な変換の段階的なトレースに従事しました。 しかし、多くの質問は未回答のままでした。 新しいGOSTの速度はどれくらいですか？ ハードウェアの最適化、効率的な実装、高速化は可能ですか？

標準GOST R 34.12 '15について

2015年6月19日の注文番号749により、GOST R 34.12 2015はブロック暗号化の新しい標準として承認されました。この標準は、標準化技術委員会26「暗号情報セキュリティ」によって導入されたInfoTeKS OJSCの参加により、ロシアのFSBの情報セキュリティおよび特別通信センターによって開発されました。 2016年1月1日に発効しました。

標準の公式pdf版をここからダウンロードし、参照実装をここからダウンロードします （両方のリンクはTC 26の公式ウェブサイトにつながります）。

この標準には、2つのブロック暗号の説明が含まれています。ブロック長が64ビットの「Magma」と、ブロック長が128ビットの「Grasshopper」です。 同時に、「Magma」は古い、よく知られているブロック暗号GOST 28147 '89の新しい名前です（実際、まったく新しいものではありません。古いブロック暗号標準が1994年まで開発されたのはこのコード名でした）。 。 「最後に、歴史は私たちに何かを教えてくれました」とあなたは言います、そしてあなたは正しいでしょう。

この記事では、ブロック長が128ビットで、コード名がGrasshopperである別の暗号について説明します。 都市の土地によれば、コードの名前は緑の昆虫とはまったく関係がありませんが、このコードの作者の名前の最初の音節、Kuz'min、Nechaev 、および会社によって形成されます。

バッタの説明

「Grasshopper」と「Magma」の違い

新しい暗号は、古い暗号とは大きく異なり、その主な利点は区別できます

• ブロックの長さの2倍（ 128ビット、または16バイト 、 64ビット、または8バイト ）、
• 非自明なキースケジュール（ Feistelネットワークに対するキースケジュールとして 秘密キーの一部を循環キーとして使用する ）、
• サイクル数の削減（ 10サイクルに対して 32サイクル ）、
• 暗号自体の根本的に異なるデバイス（ LSX暗号 Feistelネットワーク ）

基本的な変換

暗号はLSX暗号のクラスに属します。その基本的な変換（ブロック暗号化機能）は、連続する変換L （線形変換）、 S （置換）、 X （循環キーとの混合）の10サイクルで表されます。

完全な基本的な変換サイクル

代数的に、暗号文Cは次のように平文Pに依存します。

つまり、9つの完全なサイクルの後に最後の不完全なキーが続きます（キーとの混合のみ）。 変換Xは、2を法とする単純加算により、次のサイクルの中間テキストを対応する循環キーと混合します。

変換Sは同じ固定置換を適用します 中間テキストの各バイトに：

変換Lは 、既約多項式を使用して構築された体GF（256）上の線形形式で表すことができます。

中間テキストのベクトル行にこのフィールドの上のマトリックスを掛けることになります（テキストとマトリックスの各バイトは、その係数で表されるフィールドの多項式です）。

キースケジュール

実際、脆弱なキースケジュールなど、古い暗号の開発中に行われた多くの間違いは修正されました。 GOST 28147 '89暗号では、256ビットの秘密キーの8つの32ビット部分が、1番目から8番目、9番目から16番目、17番目から24番目の暗号化サイクルで循環キーとして直接使用されました。 そして、25から30秒までのサイクルでは逆の順序で：

そして、まさに非常に弱いキースケジュールであるため、完全なGOSTへのリフレクションで攻撃を実行できるようになり、その耐久性が256ビットから225ビットに低下しました（すべての交換ノードについて、1つのキーの2 ^ 32マテリアルから、この攻撃についてはここで読むことができます ）。

新しい標準では、循環キーの生成はFeistelスキームに従って実行され、最初の2つの循環キーは256ビットの秘密キーの半分であり、次の各循環キーペアは、Feistel変換の8サイクルを前の循環キーペアに適用することによって取得されます。基本的な変換と同じLSX変換が使用され、回路の循環キーとして定数の固定セットが使用されます。

交換ユニットデバイス

標準では、置換ノードは値の表によって定義されます。 暗号開発者は、このテーブルは、線形プロパティと差分プロパティの要件を考慮して、値のランダムテーブルを並べ替えることによって取得されると主張しています。

置換レイヤー、S変換

ただし、すべての秘密は遅かれ早かれ明らかになり、交換ノードを選択する方法も例外ではありません。 Alex Biryukov率いるルクセンブルグの暗号作成者チームは、交換ノードの統計的特性にある種のパターンを検出し、その結果、受信方法を復元することができました。 この方法の詳細については、iacr.orgで公開されている記事をご覧ください。

置換ノードの秘密構造

アルゴリズム最適化

InfoTeKS OJSCの研究者チーム、特にMikhail BorodinとAndrey Rybkinは、AES（Rijndael）暗号の高速実装からベクトル列乗算のアルゴリズム最適化を借りることができました。これにより、フィールドでのO（n ^ 2）乗算の従来の実装を置き換えることができますO（n）は、事前に計算されたテーブルを使用して長さO（n）の2つのベクトルを法として加算し、2014年にRusCrypto会議で報告されました。

要するに、最適化は次のようになります。あるベクトルUの積の結果として、

行列A上

ベクトルVが判明しました。

このベクトルの成分を計算する従来の方法は、ベクトルUの行に行列Aの列を順次スカラーで乗算することです。

ベクトルVの n個の各コンポーネントの計算は、フィールドでの乗算のn演算と2を法とするn-1加算演算を意味するため、すべての成分の計算の複雑さはO（n ^ 2）です。 はい、もちろん、毎回フィールドで乗算することはできません。対数と指数のテーブルを事前計算できます。 マトリックス要素のすべての可能なバイトの積を事前計算することもできます（マトリックスは固定されており、暗号化中に変化しません）。256バイトの作品を256個まで保存できます。 行列は同じ要素を持っていますか？ さて、テーブルの数は減らすことができますが、漸近的な複雑さは変わりません。

そして、あなたは他の方法で行くことができます。 製品ベクトルの各成分をn個のシングルバイトパッセージの合計として計算する代わりに、ベクトルに行列を掛ける機能を使用して、ベクトルのすべての成分をn個のベクトルの合計としてすぐに計算します。

変更されたように見えるでしょうか？ 同じ操作ですが、順序は異なります。 ただし、まず、1バイトからnバイトまでの項の容量が増加し、そのような合計は長いレジスターで計算できます（また、そうすべきです）。次に、各項はベクトルの1（！）バイトの展開積です。固定行マトリックス上。

詳細は次のとおりです。フォームの製品を事前計算できます

つまり、行列Aの既知の行iにベクトルUのバイトiのすべての可能な値を乗算し、次のバイトにこの行を乗算する代わりに、単にテーブルから製品を読み取ります。 次に、ベクトルに行列を乗算すると、事前に計算されたテーブルから製品のn行を読み取り、これらの行をビット単位で加算して結果のベクトルVを取得することになります。 したがって、非常に簡単に言えば、ベクトルの加算が基本演算と見なされる場合、ベクトルと行列のO（n）への乗算を大幅に単純化できます。

GOST R 34.12 '15 n = 16の場合、ベクトルは16バイトまたは128ビット長であり、長いXMMレジスターに非常によく適合し、追加するための追加のプロセッサー命令（たとえば、 pxor



）が提供されます。

すべてが非常にクールですが、交換ノードはどうですか？ 読者は確かに、一般的にベクトル化されないバイト置換ノードが存在する場合、そのようなL変換計算のアルゴリズム上の利点はすべて、変換前にベクトルをレジスターにロードし、変換後にアンロードするコストによって相殺されることに気付くでしょう。 いい質問です。

素晴らしく、非常にエレガントに解決されました。 交換ノードはL変換で単純に「接着」でき、事前に計算された製品ラインを

に

次に、完全な暗号化サイクルが1つになります

• キー（ pxor
  
  
  
  ）との混合、
• LS接着トランスフォームの適用（最良の場合、これはキャッシュから128ビットのベクターを16ダウンロードし、 pxor
  
  
  
  を15追加することpxor
  
  
  
  ）。

もちろん、そのような最適化は無料ではありません。その使用のために、まず、それぞれが256 * 16 * 16バイト、または64 KBを含む製品ラインを持つ2つのテーブルのいずれかを一度に計算してキャッシュする必要があります。 なぜ2つのテーブルがあるのですか？ 復号化に使用される逆変換では、 Lの逆行列による乗算が必要になるため、新製品が必要になります。

第二に、置換ノードをマトリックスで乗算して接着することは、最初にブロックに置換と乗算を適用した場合にのみ可能であるため、復号化アルゴリズムをわずかに変更する必要があります。 スキーム全体を単純に逆にすることで、暗号文からクリアテキストが取得されます（すべての変換は可逆です）。

「額」を復号化するとき、逆行列による乗算が最初に中間テキストに適用され、次に置換アクションが適用されることに注意してください。したがって、ここでこれらの変換を接着するには、復号化アルゴリズムを並べ替える必要があります。

変換の構成に注意してください

構成と同一

変換Lの線形性のため その後、復号化は次のように実行できます。

ここで、 SLに逆の各変換は、検討されたものと同様のスキームに従って実行できます。 製品ラインの計算されたテーブルは投稿しません。ネタバレには大きすぎます。 それらは、たとえばここにあります 。

SSE2を使用した最適化

原則として、基本的な変換では、すべてが明確であり、これらの最適化をすべてasmに置くことが残っています。

ブロックを操作するには、SSE2命令のセットを使用することをお勧めしますmovdqu



およびmovdqa



を使用して、データをレジスターにロードおよびアンロードします。

はい、GOST R 34.12 '15の実装には別の微妙な点があります。 上記のような一般的なアルゴリズムの最適化に加えて、パフォーマンスをさらに加速するには、アセンブラの機能とスケジューラの機能を考慮する必要があります。これらの機能は、異なる実行デバイスで並列実行の命令を配置できます。

アドレス演算の機能の説明

アルゴリズムの実装の最初の機能は、事前に計算されたテーブルの構造とオフセット付きの間接インデックスのアドレス指定を考慮しない場合、コンパイル時に次の製品ラインで追加の次の排気出力が得られることです。

 pextrb xmmX, eax, i ;   i (SSE 4.1)  32--  eax movzxd rcx, eax ;     64--  rcx add rcx, rcx ;    pxor xmmY, [rbx + 8*rcx + 0xi000] ;    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

レジスタは以下を保存します：

• rbx
  
  
  
  には、テーブルのベースオフセットのアドレスが含まれます。
• xmmX
  
  
  
  には入力ブロックが含まれ、
• xmmY
  
  
  
  には出力単位（バッテリー、量）が含まれます。
• eax
  
  
  
  とrcx
  
  
  
  は、オフセットバイトの割り当てと2 rcx
  
  
  
  に使用されます。

事前に計算されたテーブルは次のように配置されることに注意してください。

 uint8_t table[16][256][16],
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、製品ラインの値はこのテーブルに連続して格納され、外部インデックスiはL変換行列のi番目の行に対応し、平均インデックスjは入力ブロックのi番目のバイトに等しく、内部インデックスkは次の項のバイトインデックスに対応します：

 Xi = table[i][input[i]][0] ... [16]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、次の項Xi



最初のバイトのアドレスは次のように表されます。

 [Xi] = rbx + (0x1000 * i) + (16 * input[i]),
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どこで

• (0x1000 * i)
  
  
  
  は現在の行のオフセットに対応しtable[i]
  
  
  
  （ table[i]
  
  
  
  ）。
• (16 * input[i])
  
  
  
  は、現在の項Xi
  
  
  
  オフセットに対応しtable[i][input[i]]
  
  
  
  （ table[i][input[i]]
  
  
  
  ）。

そのため、現在のバイトの値に16を掛ける必要がありますが、アドレス演算では8に等しい係数係数の最大値を使用できます。 したがって、コンパイラーはバイト値をrcx



にシフトし、それを2倍にして、 Xi



アドレスを計算する必要があります。

このような過剰を回避するために、SIMDのイデオロギーを使用して、アドレス演算ではなく、事前に指定された変位を計算できます。

( Xi



)

0..15 , 00



FF



.

00FF 00FF 00FF 00FF 00FF 00FF 00FF 00FF



pand



pandn



; c psrlw



psllw



( 16) , .

, L - :

 pand xmmR, xmmZ ;    pandn xmmL, xmmZ ;    psllw xmmR, 4 ;    psrlw xmmL, 4 ;   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

xmmZ



. Xi



:

 pextrw eax, i ;    i pxor xmmY, [rbx + rax + 0xi000] ;        
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Intel AMD , , , , , .

, , , . LS - 128- Xi



, , , ( ) : .

おわりに

; , Intel Core i7-2677M Sandy Bridge @ 1.80 GHz, 120 / SSE 1.3 / .

— , :

• ( , );
• , , .

34.12 '15 , . C99, , . CMake 3.2.1+ , C99. , ( compact ), , SIMD ( optimised ) SSE2 ( SIMD ).

Travis CI , ( , ) CTest std::chrono



C++11.