gKrypt を使用して瞬時にデータを保護する: 第 2 回

GPU 対応の gKrypt エンジンを使用してアプリケーションの暗号化を高速化する

データの暗号化に GPGPU (General-Purpose computation on Graphics Processing Units) を使用する世界初のパッケージである gKrypt エンジンについて理解しましょう。gKrypt エンジンは AES (Advanced Encryption Standard) ベースの 256 ビット・ブロック暗号を使用します。この記事は AES 暗号化と gKrypt エンジンについて説明する全 2 回からなる連載の第 2 回目です。第 1 回では、まず gKrypt を紹介し、続いて AES アルゴリズムの詳細と、AES の並列処理、そして CUDA (Compute Unified Device Architecture) を使用した大規模な GPU アーキテクチャーに AES の処理を割り当てる方法を説明しました。この第 2 回では CUDA 上に AES を実装する方法について説明します。

Jawad Masood, Lead Engineer, gKrypt Data Security Solutions

Photo of Jawad MasoodJawad Masood は新興企業 gKrypt Data Security Solutions の中心開発者です。gKrypt Data Security Solutions は、さまざまなマルチコア・プロセッサーやメニーコア・プロセッサーを使用してバルク・データ高速暗号化と圧縮性能向上を実現するコスト効果の高いセキュリティー・ソリューションを提供しています。



2012年 6月 07日

はじめに

この記事では、連載の第 1 回で説明した AES アルゴリズムを CUDA フレームワークを使用して並列実装する方法について説明します。最初に、すべての AES 変換とその逆変換を CUDA に実装する方法に焦点を当てます。続いて、基本的な実装のボトルネックについて、また GPU 専用の最適化を適用することによってボトルネックの影響を軽減する方法について説明します。記事の最後では、CUDA 対応の GPU を使用することにより、標準的な CPU を使用する場合よりも暗号化処理を高速化できることを示すベンチマークの結果を紹介します。

CUDA 上に AES を実装する方法を検証する前に、GPU で暗号化を行う方法についての概要から説明します。


GPU で暗号化を行う

汎用のグラフィック・ハードウェアを使用して暗号化ソリューションを高速化する方法についてはかなりの歴史があります。Gershon Kedem 氏と Yuriko Ishihara 氏は 1999年 8月、グラフィック・ハードウェアを使用して暗号化を行う方法に関する最初の論文を発表しました (「参考文献」を参照)。その論文で、著者らは 100 MHz で実行する PixelFlow グラフィック・エンジンを使用して UNIX パスワードの暗号化解読に成功したと報告しています。

しかし初期の汎用グラフィック・カードは、柔軟なプログラミング環境がなかったことや、整数をサポートできないというハードウェア上の欠陥があったことから、暗号アプリケーションにはあまり適していませんでした。それが最近、NVIDIA などのメーカーの最新グラフィック・カードが汎用の計算アプリケーションに柔軟に対応できるようになったことで、状況が変わってきました。CUDA、そしてオープンな並列プログラミング標準である OpenCLTM の登場により、GPU は並列計算アプリケーションのプラットフォームとして一層魅力的になりました。最近発表された何本かの論文は、CUDA を使用した NVIDIA の GPU で AES を実装する方法に焦点を絞って論じています。これらの論文はすべて、中心となる暗号アルゴリズムを GPU 上に実装し、鍵の拡張などのタスクを CPU で処理することで実装を単純化しています。しかし私達は最新ハードウェアの共有メモリーを利用して鍵スケジューリングも GPU で実行し、大きなパフォーマンスのオーバーヘッドを生じない方法について検討しました。


CUDA に AES を実装する

では、CUDA フレームワークを使用して AES を並列実装する方法と最適化する方法について説明します。最初に AES 変換の基本的な実装と、その実装に不可欠なインデックス化スキームについて説明し、その後でパフォーマンスを制限する要素について説明します。さらに、そうしたボトルネックを軽減するために考えられる最適化の方法を検討し、GPU の並列計算処理能力をフルに活用した効率的な暗号化カーネルを作成します。

AES の実装として、1 つの CUDA スレッドが 128 ビットの状態ブロックに対して演算処理を行う最も単純な場合を考えてみましょう。最初のステップは GPU デバイスのメモリーを割り当てることです。cudaMalloc を API 呼び出しとして使用し、入力テーブル、出力テーブル、拡張鍵テーブル、AES テーブルにメモリーを割り当てます。これらのバッファーは GPU のグローバル・メモリー、つまり D-RAM の中に作成されます。そして入力データ・テーブル、拡張鍵テーブル、AES テーブルは、cudaMemcpy を API 呼び出しとして使用してホストからデバイスにコピーされます。では AES カーネルを起動し、CUDA スレッドが暗号化および復号化プロセスのために実行したステップを分析しましょう。

入力配列を状態配列にコピーする

暗号化または復号化の最初で、入力配列はある規則に従って状態配列にコピーされます。その規則とは、S [ r , c ] = In [ r + 4c ] for 0 <= r < 4; and 0 <= c Nb というものです。サンプル・ケースの場合、Nb = 4 となります。この列メジャー・アクセス・パターンを示したものが図 1 です (図 1 をテキストとして表示したものを見るにはここをクリックしてください)。

図 1. 入力配列から状態配列へのコピー
この図は単一の値を持つ要素で構成される入力配列を 2 つの値を持つ要素で構成される状態配列に変換する方法を示しています

このインデックス化スキームを一般化し、複数スレッドに対応させるためには、実行中のスレッドを特定するための何らかのメカニズムが必要です。そこで、各スレッドのグローバル ID を CUDA ランタイムに照会する、idx という新しい変数を導入します。各スレッドが入力配列の 16 要素 (バイト) を処理するため、各スレッドの実質的なオフセットは 16*idx です。暗号化プロセスまたは復号化プロセスの完了後に出力配列にデータを書き出す場合もインデックス化スキームは同じです。

AES 変換

リソースを最も効率的に使用し、コードを読みやすくするために、AES 変換はすべてデバイス関数として実装されます。すべての AES 変換をインプレース変換として実行することはできないため、状態配列と同じ大きさの 2 つのブロックをレジスター・ファイルの中に作成します。ここでは変換の実装方法について、入力データを暗号化する順序に従って説明します。

  • AddRoundKey

    この変換を適用するためには、状態配列の各バイトと、それに対応する拡張鍵配列のバイトとを、ビット単位の XOR 演算を使用して組み合わせます。拡張鍵は GPU のグローバル・メモリー・バッファーの中にあります。この変換は各ラウンドに適用されますが、拡張鍵のどの部分が使用されるかはラウンド数によって異なります。AddRoundKey 変換は図 2 の式に従って適用されます。

    図 2. AddRoundKey 変換を適用する際に使われる式
    複雑な数式によって変換を行います

    各スレッドがランダムな場所からグローバル・メモリーに 16 回アクセスする必要があるため、メモリー転送はバラバラに行われます。グローバル・メモリーは GPU で最も帯域幅の狭いメモリーであり、キャッシュはありません。そのため、グローバル・メモリーにアクセスするたびに長い遅延が発生し、すべてのメモリー・アクセスが完了するまで、そのワープ全体の実行が実質的にブロックされます。

  • SubBytes

    この変換では、状態配列の各バイトの値が AES S-Box のインデックス値を示しており、そのインデックス値を持つ AES S-Box の要素によって状態配列のバイトが置換されます。例えば S0,0 = {64} の場合、この状態配列のバイトを置き換える S-Box の値はインデックス 6 の行とインデックス 4 の列が交差したところにある要素となります。S-Box は GPU のグローバル・メモリー内にある固定のテーブルです。この状況は AddRoundKey 変換の場合と似ています。ここまでの段階では、グローバル・メモリーへのアクセスが基本実装のパフォーマンスのボトルネックとなっています。

  • ShiftRows

    ShiftRows 変換では、2 行目、3 行目、4 行目の各バイトが、それぞれ 1 バイト、2 バイト、3 バイトのオフセットで左にシフトされます。この ShiftRows 変換はインプレース変換ではないため、新規状態 (n_state) 配列と状態 (state) 配列の両方を使用します。これを示したものが図 3 です。

    図 3. ShiftRows 変換の適用
    この図は ShiftRows 変換でのビットのシフト方法を示しています

    ShiftRows 変換ではグローバル・メモリーへのアクセスを行いません。状態配列も新規状態配列もレジスター内にあるため、最も広い帯域幅でアクセスすることができ、パフォーマンスの問題はありません。

    最初のラウンドは AddRoundKey 変換のみを適用します。中間のラウンドは SubBytes 変換で始まり、鍵の長さから計算される特定のラウンド数に従って、それぞれ ShiftRows 変換、MixColumns 変換、AddRoundKey 変換を適用します。最後のラウンドは SubBytes 変換と ShiftRows 変換を実行した後、AddRoundKey 変換を実行します。そして暗号化されたデータは、(次のセクションで説明するように) 状態配列からグローバルな出力バッファーにコピーされます。

状態配列を出力バッファーにコピーする

暗号化または復号化の最後で、状態配列はグローバル・メモリーの出力配列にコピーされます。これを示したものが図 4 です。このパターンの規則を定義すると、Out [ r + 4c ] = S [ r , c ] for 0 <= r < 4; and 0 <= c <Nb となります (図 4 をテキストとして表示したものを見るにはここをクリックしてください)。

図 4. 状態配列から出力配列へのコピー
この図は 2 つの値を持つ要素で構成される状態配列を 1 つの値を持つ要素で構成される出力配列にコピーする方法を示しています

逆 AES 変換

このセクションでは、逆 AES 変換についての概要と、逆 AES 変換を復号化プロセスに適用する順序について説明します。復号化プロセスでは、変換の方法、実行の順序、必要な AES テーブルを少し変更します。復号化プロセスで変換を適用する順序を示したものが図 5 です。

図 5. 逆 AES 変換のフロー
この図は暗号化されたテキストをさまざまな関数で処理することで平文のテキストに変換する方法を示しています

SubBytes 変換とは逆の変換を行う InvSubBytes 変換では、S-Box テーブルの代わりに逆 S-Box テーブルを使用してバイト置換を行う必要があります。置換ロジックは SubBytes 変換と同じです。

InvShiftRows 変換は ShiftRows 変換での左方向へのシフトとは逆に、2 行目、3 行目、4 行目の各バイトをそれぞれ 1 バイト、2 バイト、3 バイト右方向にシフトします。InvShiftRows 変換の適用方法を示したものが図 6 です。

図 6. InvShiftRows 変換
この図は InvShiftRows 変換のビット・シフト・パターンを示しています

残りの 2 つの変換、MixColumns 変換と AddRoundKey 変換は暗号化の場合と同じであり、変更はありません。


CUDA アーキテクチャー用に AES を最適化する

ここまでで説明した基本実装では、GPU のグローバル・メモリー (D-RAM) と、各スレッドのレジスター・メモリーを使用しました。コンスタント・メモリーや共有メモリーなど、GPU 上の他のメモリー空間に比べると、グローバル・メモリーのメモリー帯域幅は最も狭いことを思い出してください。カーネルのパフォーマンスを制限する 1 つの要素がグローバル・メモリーの帯域幅です。グローバル・メモリーの帯域幅が狭いことによる主な問題点として、アクセスに要する時間が長くなります。簡単な最適化方法として、各変換に必要なグローバル・メモリーへのアクセス回数を減らす方法があります。カーネルのパフォーマンスを低下させる 2 番目の要因は、デバイス使用率が低く、各スレッドが過度にレジスターを使用してしまうことです。compute capability 2.0 では、1 つの対称型マルチプロセッサー (Symmetric Multiprocessor: SM) に使用できるハードウェア・レジスターの最大数は 32768 に制限されています。レジスターが多用されると、各 SM が実行できるスレッド・ブロックの数が減り、計算リソースの使用率が低くなります。デバイス使用率を最大限に高めるためには、各スレッドが使用するレジスターを制限内に収め、より多くのスレッド・ブロックを各 SM が処理できるようにします。そのためには状態配列と新規状態配列を共有メモリーに移動します。

グローバル・メモリーへのアクセスを減らす

この記事の方式で AES を実装する場合、パフォーマンスを低下させる第 1 の要因はグローバル・メモリーへの頻繁なアクセスです。グローバル・メモリーにアクセスして取得されるデータには、固定の AES テーブルと拡張鍵があります。アクセスを高速化し、キャッシュを利用できるようにするために、こうした読み取り専用データを GPU のコンスタント・メモリーに移動します。

コンスタント・メモリーは GPU 上にあり、帯域幅の広い読み取り専用メモリーです。コンスタント・メモリーはカーネル内のすべてのスレッド・ブロックのスレッドから見えるため、読み取りアクセス専用の固定データを格納するためのメモリー空間として理想的です。ホスト・プロセッサーはコンスタント・メモリー空間にあるメモリー・オブジェクトの割り当てと初期化を行います。コンスタント・メモリーはキャッシュされているため、コンスタント・メモリーから連続的に読み出しても、グローバル・メモリーから読み出す場合のようにメモリー遅延が発生することはありません。いったんコンスタント・メモリーにデータが書き込まれると、すべてのスレッドがそのデータにアクセスして最小限の遅延で読み取り操作を実行することができます。現状のハードウェアではコンスタント・キャッシュのサイズは 64 KB に制限されています。AES の場合、読み取り専用の固定テーブルがカーネル内に 4 つあり、それぞれ logt、ilogt、sbox、isbox と呼ばれます。各テーブルのサイズは 256 バイトであり、4 つのテーブルで 1 KB です。そのため、すべてのテーブルをコンスタント・キャッシュに格納することができます。カーネル内にある別の読み取り専用データが拡張鍵です。拡張鍵のために、さらに 240 バイト必要ですが、コンスタント・キャッシュは容易にこの 240 バイトに対応することができます。

コンスタント・メモリーの割り当てと初期化はホスト・プロセッサーが行うため、カーネル・コードを変更する必要はありません。AES テーブルと拡張鍵をコンスタント・メモリーに移動すると、各スレッドからグローバル・メモリーへアクセスする回数を劇的に減らすことができるため、大幅にパフォーマンスを高めることができます。グローバル・メモリーへのアクセスは、入力バッファーから状態配列にデータをコピーする場合、そしてすべての変換が完了した後で出力バッファーにデータをコピーする場合のみになります。

共有メモリーを使用して、デバイス使用率と AES カーネルのパフォーマンスを高める

AES を最適化するための第 2 のステップは、デバイス使用率を高めることです。現状では、各スレッドが過度にレジスターを使用してしまうため、デバイス使用率が低くなっています。各スレッドは状態配列と同じ大きさ (16 バイト) の配列をレジスター・メモリー内に 2 つ保持し、グローバル・メモリーに結果を返さずに効率的に AES 変換の演算を行っています。大きなオーバーヘッドなしにレジスター・メモリーを節約するためには、これらの配列を、レジスターに匹敵するパフォーマンスを持つ適当なメモリー空間に移動します。この場合に共有メモリーが活躍します。

共有メモリーは GPU 上にある帯域幅の広いメモリーであり、同じスレッド・ブロックのスレッド間でデータを共有するために使用されます。compute capability 2.x を備えた NVIDIA の GPU は SM 当たり最大 48 KB の共有メモリーを持つことができます。共有メモリーの帯域幅は非常に広く、グローバル・メモリーの帯域幅よりも約 1 桁大きい帯域幅を実現します。共有メモリーのもう 1 つのメリットは分散アクセスを必要としない点です。いったんローカル・メモリーにデータがロードされると、そのデータに任意のパターンでアクセスすることができ、パフォーマンスも低下しないため、レジスター・メモリーの代わりとして理想的です。

レジスターを使用する代わりに、状態 (state) バッファーと新規状態 (n_state) バッファーを共有メモリーに配置します。こうすることで、スレッド・ブロック内のすべてのスレッドが状態バッファーと新規状態バッファーを共有することができます。各スレッドはグローバルな入力バッファーの 16 個の要素を指定のオフセットで共有メモリーの状態バッファーにロードします。この場合も共有メモリー内に 2 つのバッファーが必要です。すべての AES 変換をインプレース変換として実行することはできないからです。ただし、これが大きな問題になることはありません。SM 当たり 48 KB のローカル・メモリーを自由に使用することができ、各スレッド・ブロックはワークグループ・サイズが最大の 256 の場合も最大 8 KB を使用できるため、SM 当たり 6 つのスレッド・ブロックを処理することができるからです。

共有メモリーを使用するためにはインデックス化スキームを少し変更する必要があります。今度はスレッド・ブロック内のすべてのスレッドがローカルの状態バッファーを共同で使用しているため、各スレッドのローカル ID を追跡する必要があります。そこで、各スレッドのローカル ID を照会するための tid という新しい変数を導入します。

各スレッドは 16 個の要素を 16*tid というオフセットで状態配列に書き込みます。出力配列のインデックス化スキームも同じです。状態バッファーに共有メモリーを使用することで、各スレッドによるレジスター・ファイルの使用が少なくなり、デバイス使用率を高めることができます。その結果、より多くのワープを各 SM で同時に実行することができ、カーネル全体としてのパフォーマンスも高めることができます。

ループ展開

GPU は SIMD (Single Instruction Multiple Data) プロセッサーです。計算処理方式が SIMD モデルに近ければ近いほど、GPU で実現可能なスループットは高くなります。AES を実装する場合、各スレッドは 1 つの状態ブロック (16 バイト) を独立に処理します。つまり、さまざまなステップのサンプル・コードを見るとわかるように、すべての AES 変換は for ループを使用することで状態配列の 16 バイトをすべて処理します。GPU による実装ではループ展開を利用することができます。ループ展開により、実行時のインデックス計算に付随するオーバーヘッドが完全になくなります。

ループ展開は、各ループを手作業で展開することも、単純にループ処理の前に #pragma unroll ディレクティブを使用してコンパイラーにループ展開させることもできます。ループ展開によってスレッドが使用するレジスター数は増えますが、それでもスレッド・ブロック当たりで使用可能なレジスター数の 32768 という制限内に収めることができます。命令のオーバーヘッドが完全になくなり、カーネルが SIMD 処理モデルにより一層近くなるため、パフォーマンスはループ展開しない場合よりも高くなります。


GPU での鍵スケジューリング

AES の基本的な実装では、ホスト・プロセッサーで鍵を拡張し、拡張鍵を GPU のコンスタント・メモリーにコピーします。今度は、帯域幅の広い共有メモリーを使用して GPU 自体で鍵スケジューリングを実行する方法を検討します。複数のスレッド・ブロックから共有メモリーにアクセスすることはできないため、各スレッド・ブロック用に個別に鍵を拡張する必要があります。拡張前の暗号鍵はホストから GPU のコンスタント・メモリー・バッファーにコピーされます。各スレッド・ブロックで、拡張鍵と同じ大きさの配列が共有メモリーに作成されます。拡張鍵のサイズは使用される鍵の長さによって異なり、256 ビット鍵の場合は 240 バイトです。各スレッド・ブロックの最初のスレッド (tidx=0) は、この共有配列に暗号鍵をコピーし、鍵拡張関数を呼び出します。下記の図 7 は各スレッド・ブロックの実行パスを示しています。カーネルには、鍵の拡張が完了するまでスレッドが AES 変換を進めないようにするために、鍵拡張関数の後に障壁が設けてあります。

図 7. デバイス上での鍵スケジューリング
このフロー図は tidx がゼロではない場合に鍵の拡張がバイパスされる様子を示しています

GPU で鍵スケジューリングを実行することにより、スレッド・ブロック当たりで使用される共有メモリーが 240 バイト増加し、使用される共有メモリーは 8432 バイトになります。今度はデバイス使用率が共有メモリーによって制限されることになり、SM 当たり 5 つのスレッド・ブロックしか処理することができません。各スレッド・ブロックが使用するレジスター数はボトルネックではなくなります。レジスターの使用に関しては SM 当たり 6 つのスレッド・ブロックを処理できることに変わりはないからです。鍵の拡張は計算負荷の重い処理ではないため、各スレッド・ブロックに発生する計算処理のオーバーヘッドは大きなものではありません。

デバイス使用率が低下する結果、カーネル全体としてのパフォーマンスは低下します。デバイス使用率の低下に比較してパフォーマンスの低下は大幅ではなく、共有メモリー内の拡張鍵に比較的高速にアクセスできることで、ある程度埋め合わせされます。


結果

AES アルゴリズムは本質的に並列処理であり、データ・サイズが大きくなるほどパフォーマンスが高まるため、バルク暗号化に非常に適しています。ベンチマークを見ると、さまざまな入力サイズに対するパフォーマンスの結果を確認することができます。図 8 は Tesla C2050 と 2.8 GHz の Core i7 CPU のパフォーマンスを比較したもので、ファイルが大きくなると Intel のプロセッサーでは暗号化に要する時間が急激に増加するのに対し、NVIDIA のグラフィック・プロセッサーでは少し時間が増加するのみです。このグラフは横軸に入力サイズ (メガバイト) を、縦軸に 256 ビット AES をカーネルで実行した場合の時間 (ミリ秒) をとっています。

図 8. NVIDIA TESLA C2050 で AES を実行した場合のパフォーマンス
Intel のプロセッサーではファイルが大きくなると暗号化に要する時間が急激に増加するのに対し、NVIDIA のグラフィック・プロセッサーでは少し時間が増加するのみであることを折れ線グラフで示しています

AES カーネルを完全に最適化した場合、ハードウェアによってどのようなパフォーマンスが得られるかを比較したものが図 9 です。Core i7 CPU のベンチマークは OpenCLTM で 8 本のスレッドを使用した場合です。この結果から、Intel のプロセッサーの値は低いのに比べ、NVIDIA の値は 25 倍以上も高いことがわかります。

図 9. AES のパフォーマンスを比較する
棒グラフでパフォーマンスを比較しており、Intel の値は低く、NVIDIA の値は 25 倍以上高いことを示しています

まとめ

この連載では、CUDA に AES を実装する方法と、この実装を最適化するためのステップバイステップの手順について説明しました。この実装の結果から、現世代の Intel プロセッサーや汎用のグラフィック・カードに比べ、GPU は大幅にパフォーマンスを高めることができ、処理速度も大幅に高められることを示しました。これらの最適化手法を gKrypt アプリケーションや gKrypt エンジンに使用することで、計算負荷の高い暗号化処理を高速化することができます。これらの最適化手法によって gKrypt を容易に使用できるようになり、また幅広いプラットフォームで gKrypt をサポートできるため、コンシューマー向け製品に gKrypt を安全に使用できるようになります。

参考文献

学ぶために

製品や技術を入手するために

  • 最新の CUDA 対応ドライバーを NVIDIA から入手してください。
  • CUDA Occupancy Calculator をダウンロードしてください。このプログラムを利用すると、指定された CUDA カーネルごとに GPU のマルチプロセッサー占有率を計算することができます。
  • 皆さんに最適な方法で IBM 製品を評価してください。製品の試用版をダウンロードする方法、オンラインで製品を試す方法、クラウド環境で製品を使う方法、あるいは SOA Sandbox で数時間を費やし、サービス指向アーキテクチャーの効率的な実装方法を学ぶ方法などがあります。

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux, Open source
ArticleID=819316
ArticleTitle=gKrypt を使用して瞬時にデータを保護する: 第 2 回
publish-date=06072012