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

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

データの暗号化に GPGPU (General-Purpose computation on Graphics Processing Units) を使用する世界初のパッケージである gKrypt エンジンについて理解しましょう。gKrypt エンジンは情報セキュリティーの重要なツールであり、AES (Advanced Encryption Standard) ベースの 256 ビット・ブロック暗号を使用することで堅牢なセキュリティーを実現しています。この記事は全 2 回からなる連載の第 1 回目として、AES についての詳細、Rijndael アルゴリズムを Linux 用に GPU へポーティングする方法、AES アルゴリズムの並列化、そして NVIDIA ベースの GPU 用 CUDA をサポートする gKrypt エンジンの使用について説明します。

2012年 5月 01日 ― 「はじめに」、「まとめ」に第 2 回へのリンクを囲み記事として追加し、「参考文献」の項目にも第 2 回へのリンクを追加しました。

Jawad Masood, Lead Engineer, gKrypt Data Security Solutions

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



2012年 5月 24日

はじめに

今日の世界では、さまざまな人々や組織が、あらゆる種類の情報を保管し、電子的に処理し、頻繁にローカル・ネットワークまたはインターネットへ送信しています。その結果、こうした情報に不正アクセスされるリスクが飛躍的に高まっており、情報セキュリティーの課題が増大しています。不正アクセスによって伝送データをインターセプトされることにより、慎重に扱うべき個人情報や組織の機密である財務情報が漏洩し、深刻なセキュリティー侵害が発生する恐れがあります。ビジネスの場合、セキュリティー侵害が発生すると、巨額の金銭的被害、高額の訴訟、評価の失墜やビジネスの機会損失などにつながるケースがほとんどです。個人の場合には、セキュリティー侵害によって ID の盗難につながったり、収支の履歴の漏えいや信用格付けの毀損につながったりするかもしれません。そうした情報侵害からの回復には何年もかかる場合や、巨額のコストがかかる場合があります。暗号化は、個人の極めて重要な情報や組織の機密情報を情報侵害から保護するための効果的なソリューションであるため、データ・セキュリティー・システムに不可欠の要素となりつつあります。

バルク暗号化技術は、大量のデータを保管あるいは送信する際に暗号化するための手段です。しかし最近では、同時に暗号化する必要のある機密情報の量の増加が CPU の計算処理能力の向上を上回っています。現状では、バルク暗号化に必要な処理能力を満たすためには、暗号化アクセラレーターという形の特殊なハードウェアが必要です (「参考文献」を参照)。DES (Data Encryption Standard) や AES (Advanced Encryption Standard) など、大部分の暗号アルゴリズムは本質的にデータ並列処理のレベルや計算密度が高いため、GPU での並列実装に適しており、専用ハードウェアによる暗号化ソリューションを実質的に置き換えつつあります (「参考文献」を参照)。


gKrypt エンジン

gKrypt エンジンは既製の暗号化モジュールであり、GPU で Rijndael AES を使用するための単純な API が用意されています (「参考文献」を参照)。gKrypt エンジンはベースとなるグラフィック・カードや計算プロセッサーなどの並列ハードウェアを利用することにより、計算負荷の高い暗号化ワークロードを軽減しています。gKrypt は単純な C/C++ インターフェースを持ち、Java インターフェースと C# インターフェースにバインドすることもできるため、CUDA や OpenCL などの並列言語について最低限の知識しか持たない開発者が GPU ソリューションをデプロイしたいと考えている場合に、大きなメリットをもたらしてくれます。

gKrypt フレームワークは AMD ベースの GPU と NVIDIA ベースの GPU の両方をサポートし、マルチコア CPU もサポートしているため、並列プロセッサーのメリットを容易に生かすことができます。次のセクションでは、AES の並列処理を各フェーズに分け、基礎となっている手法について説明します。


AES (Advanced Encryption Standard) アルゴリズム

AES (Advanced Encryption Standard) は NIST (National Institute of Standards and Technology: 米国立標準技術研究所) に承認された暗号化標準であり、Rijndael 暗号化をベースにしています (「参考文献」を参照)。Rijndael 暗号化は NIST が行った AES 選定プロセスに対してベルギーの暗号学者である Joan Daemen 氏と Vincent Rijmen 氏が提案した対象鍵ブロック暗号化方式です (「参考文献」を参照)。Rijndael 暗号化は NIST によって 2001年 11月に AES (Advanced Encryption Standard) として承認され、古い DES (Data Encryption Standard) に対する実質的な置き換えとなりました。AES 標準は鍵の長さが 128、192、256 ビットのブロック暗号で構成され、それぞれ同じ 128 ビットのデータ・ブロックを持っています。そのため、それぞれ AES-128、AES-192、AES-256 と呼ばれます。

AES ブロック暗号は、状態配列 (状態 (state) の頭文字を取って「s」で表されます) と呼ばれる 2 次元のバイト配列に対して演算を行います。状態配列の大きさは 16 バイト (128 ビット) であり、4 行 4 列で構成されます。これを Nb = 4 と表現し、4 は基本的に状態配列の列の数です。AES でサポートされている鍵の長さは 128、192、256 ビットであり、それぞれ Nk = 4、6、8 と表されます。AES はバイト指向変換 (一般的には AES 変換と呼ばれます) を適用することによって、状態配列の暗号化と復号化を行います。これらの変換が、鍵の長さによって異なる特定のラウンド回数 Nr だけ適用されます。鍵の長さが 128、192、256 ビットの場合、Nr はそれぞれ 10、12、14 です。

AES アルゴリズムのさまざまなフェーズを示したものが以下の図 1 です。

図 1. AES アルゴリズムのフェーズ
AES アルゴリズムのフェーズを示す図

AES 変換を開始する前に、ユーザーが提供した暗号化鍵を Rijndael 鍵スケジュールを使用して拡張します。図 1 の「Key expansion (鍵拡張)」ステップは Rijndael 鍵スケジュールを実行し、この後のステージのすべてのラウンドで使用する拡張鍵を生成します。拡張鍵の長さは Nb(Nr + 1) で計算され、これは 32 ビット・ワードの数 (列) です。各ラウンドの A different portion of the expanded key is used in the AddRoundKey ステップでは、この拡張鍵のそれぞれ別の部分が使用されます。

AES 暗号化プロセスの最初のステップは AddRoundKey 変換です。この変換では、ビット単位の排他的論理和 (XOR) 演算を使用して状態配列の各バイトをラウンド鍵と組み合わせます。この演算式を定義したものが図 2 です。

図 2. AES 暗号化プロセスの最初のステップ
AES 暗号化プロセスの最初のステップを示す式

この式を構成する要素を以下の図 3 に示します。「State (状態)」、「New State (新しい状態)」、「Round Key (ラウンド鍵)」はすべて 4x4 のバイト (128 ビット) 配列として Nb = 4 と表されます。このバイト・データは 16 進ワード形式です。

図 3. AddRoundKey 変換
AddRoundKey 変換を示す図

AES の次のフェーズでは、4 つの変換がすべて、Nr = 1 から Nr - 1 まで図 3 の順番で Nr - 1 回繰り返されます。これらの変換のそれぞれについて、変換が適用される順に説明します。

SubBytes 変換は非線形のバイト置換ステップであり、状態配列の各バイトは S-Box と呼ばれるルックアップ・テーブルに従って置き換えられます。状態配列のすべてのバイトは、置換対象となるバイトの 16 進値と同じインデックスを持つ S-Box のエントリーによって置き換えられます。このプロセスは図 4 を見るとよくわかります。

図 4. SubBytes 変換
非線形のバイト置換ステップを示す図

この場合、状態配列の最初のバイトは 16 進値を持っています。置き換えられる値は、インデックス 1 の行とインデックス 9 の列が交差する位置の値によって決まります。同様に、バイト {be} は、S-Box の行インデックス b、列インデックス e の位置にあるバイトで置き換えられます。

ShiftRows 変換では、状態配列の各行が図 5 の等式の規則に従って異なるオフセットでサイクリックにシフトされます。

図 5. 状態配列の各行が異なるオフセットでサイクリックにシフトされる様子
状態配列の各行が異なるオフセットでサイクリックにシフトされる様子を示す図

シフト値 shift(r, Nb) は行番号 r に依存します。この関係を示したものが図 6 の式です。

図 6. シフト値が行番号に依存する様子
シフト値が行番号に依存することを示す等式の図

各行に対して上記の等式を解決すると、最初の行はシフトされませんが、2 番目、3 番目、4 番目の行の各バイトは、それぞれ左に 1 バイト、2 バイト、3 バイトのオフセットでシフトされます。各行がどのようにシフトされるか、またシフト後の新しい状態配列がどのようになるかを示したものが以下の図 7 です。

図 7. ShiftRows 変換
ShiftRows 変換を示す図

このシフト・パターンは、各行のバイト要素を左方向 (若番方向) へ移動し、最も若いバイト要素は行の一番右の要素 (最老番要素) へ戻すもの、と考えることができます。

MixColumns 変換は状態配列の列に対して操作を行い、各列を GF(28) 上の 4 項多項式として扱います。次に各列は、図 8 の係数多項式によってモジュロ (x4 + 1) 乗算が実行されます。

図 8. 係数多項式
係数多項式を示す図

この演算結果は、状態配列の各列を、その列と係数行列との行列乗算で置き換えたものと等価です。これを示したものが図 9 です。

図 9. MixColumns 変換
MixColumns 変換を示す図

CUDA アーキテクチャー用に AES アルゴリズムを並列化する

ここまでで、AES 暗号化アルゴリズムを多少なりとも理解することができたと思うので、CUDA フレームワークを使用した実装を開始することができます。以下のセクションでは、CUDA フレームワークについて簡単に説明し、続いて設計方式と実装メカニズムについて詳細に説明します。これから説明する内容は、この連載の第 2 回で説明するサンプルを実行するための準備作業です。

CUDA アーキテクチャー

2006年に導入された CUDA は NVIDIA が開発した並列コンピューティング・アーキテクチャーであり、NVIDIA の GPU の能力を活用することで計算処理性能を高めています (「参考文献」を参照)。市場のマシンに搭載された 1 億を超える GPU が CUDA をサポートしているため、CUDA 上で実行されるアプリケーションの潜在ユーザー・ベースは既に膨大です。CUDA がリリースされて以来、開発者達は数え切れないほどのアプリケーションで大幅に処理速度を向上させており、特に画像処理や HD 動画再生に関連したアプリケーションで大きな成果を上げています (図 10 を参照)。

図 10. CUDA のスレッド・モデル
2 つの CPU シリアル・コードと 2 つの GPU 並列カーネルを使用した CUDA のスレッド・モデルの図

CUDA プログラミング・モデルの考え方は、Single Program Multiple Data (SPMD) 方式で実行する何千ものスレッドを生成し、各スレッドが小さなデータ・ブロックを並列処理する、というものです。GPU のコア数は CPU のコア数よりも多いため (ただし GPU コアは CPU コアよりもはるかに処理能力が劣ります)、小さなデータ・ブロックを計算処理する何千ものスレッドを並列実行するには理想的です。これらのスレッドはブロックとグリッドで構成され、ブロックはスレッドの集合であり、グリッドはブロックの集合です。CUDA アーキテクチャーについては、そのすべての機能およびメモリー階層構造と併せて、さらに詳細な説明が必要ですが、この記事ではそれらについては説明しません。

設計の方式

先ほど触れたように、AES は 128 ビットのデータ・ブロック (状態) に対して独立して演算を行うブロック暗号化アルゴリズムです。AES 暗号化では、すべての状態ブロックに対してブロック間に依存関係を持つことなく同じ演算を行うため (ECB モード)、高度なデータ並列処理を実現することができます。この AES ブロック暗号におけるデータ・レベルの並列処理を活用するために、私はフォーク/ジョイン方式を実装しました。この方式では複数の状態ブロックを同時に暗号化することができる (1 つのスレッドが 1 つの状態ブロックを暗号化する) ため、高いスループットを実現することができます。データ・サイズが大きくなるに従って並列処理レベルも高められるため、GPU はより効率的にバルク暗号化を実行することができます。

図 11 はホストとデバイスの作業区分を示し、AES を構成する各種要素の性質を表しています。この図を見るとわかるように、AES で実行される直列演算は鍵スケジューリングのみです。この演算により、その後の AES ラウンドで使用するラウンド鍵が提供されます。AES 変換はすべて 128 ビットの状態ブロックごとに独立して適用されるため、どの変換も高度な並列処理として実行することができます。従って変換処理を CPU ホスト・プロセッサーと GPU デバイスとの間で分割することにより、この実装から最大のスループットを引き出すことができます。つまり鍵スケジューリングは CPU デバイスで 1 度だけ実行され、カーネル引数として GPU デバイスに渡されます。AES アルゴリズムの中核、つまり AES 変換を CUDA を使用して実装することで、GPU の並列コンピューティング・リソースをフルに活用することができます。

図 11. ホストとデバイスの作業区分
ホストとデバイスの作業区分を示す図

この連載の第 2 回で説明する実装では、各 CUDA スレッドが 1 つの状態ブロック (16 バイト) を入力引数に取り、特定のラウンド回数だけバイト指向 AES 変換を適用することにより、その状態ブロックを暗号文に変換します。つまり 128 ビットの1 つの状態を暗号化するための処理は直列処理のままです。しかしループ展開など GPU 特有の最適化手法を使用することで、コードを最適化することができます。入力データにアクセスする場合や暗号化されたデータを書き戻す場合、各 CUDA スレッドには実質的に 16 バイト (1 つの状態ブロック) のオフセットがあります。この実装でのスレッド間の作業区分、そしてスレッド割り当てモデルを示したものが図 12 です。

図 12. CUDA のスレッド割り当て
CUDA のスレッド割り当てを示す図

CUDA デバイスでスレッドを実行する

すべてのスレッドは同時に動作するため、皆さんは理論的に、100 MB のデータの暗号化に必要な時間は 128 ビットの暗号化に必要な時間と同じだと思うかもしれませんが、そうではありません。先ほど、スレッドがブロックにまとめられ、それらのブロックが CUDA デバイスで実行されることを説明しました。最新世代の CUDA アーキテクチャーでは、実行リソース (コア) はストリーミング・マルチプロセッサー (Streaming Multiprocessor: SM) に分割され、それぞれの SM が一度に 112 ブロックを実行します (図 13 を参照)。デバイスの SM が 14 の場合 (各 SM が 32 コアを持つ Tesla C2050 の場合など)、他に何も制約要因がない場合でも一度に 16 ブロックしか実行することができません。ブロックの数が 16 よりも多い場合には、それらのブロックは実行される順番が来るまで待たなければなりません。これはデバイス上で実行されるスレッドの様子を最も単純化した場合の話ですが、他にも SM ごとのワープの数、各スレッドのレジスターの使用状況、各ブロックで共有されるメモリーなど、多くの要素が影響します。CUDA アーキテクチャーでスレッド・ブロックがどのように SM に割り当てられるかについての詳細は、CUDA GPU Occupancy Calculator を参照してください (「参考文献」を参照)。

図 13. ストリーミング・マルチプロセッサー (SM) へのスレッド・ブロックの割り当て
ストリーミング・マルチプロセッサー (SM) へスレッド・ブロックを割り当てる様子を示す図

スレッド・ブロックはストリーミング・マルチプロセッサーに割り当てられると、さらにワープに分割されます。各ワープは、進化を続ける最新世代 CUDA アーキテクチャーのスレッドを 32 本集めたものです。これらのワープも並列に実行されるとは限りませんが、ワープは非常に効率的な方式で実行されます。例えば、1 つのワープがメモリー転送を待っている間に、次のワープが同じコア上でデータに対する処理を実行します。複数のワープが実行可能状態になっている場合には、ドライバーがワープ間の優先メカニズムを設定します。カーネル内で起動されるスレッドの数よりもコアの数の方が少ないかもしれませんが、CUDA アーキテクチャーとドライバーはすべてのハードウェア・リソースを活用し、最大のパフォーマンスを実現します。


Linux で CUDA を構成する

CUDA フレームワークはベースとなる並列ハードウェアを活用して高いパフォーマンスを実現するために、NVIDIA ベースの GPU (Graphics Processing Unit) を必要とします。CUDA ランタイムには NVIDIA 開発者用のビデオ・ドライバーが含まれています。CUDA 対応のグラフィック・カードを使用するための第一歩は、基本となるビデオ・ドライバーを再構成することです。ターミナル・ソフトウェアを開き、コマンド $ sudo apt-get --purge remove nvidia* を実行します。

次のステップは、CUDA 開発者ドライバーと競合するデフォルトの nouveau ドライバーをブラックリストに含めることです。/etc/modprobe.d で新しいファイルを作成し、リスト 1 のコマンドを挿入します。

リスト 1. CUDA 開発者ドライバーと競合するデフォルトの nouveau ドライバーをブラックリストに含める
# /etc/modprobe.d/blacklist-nouveau.conf 
blacklist nvidiafb 
blacklist nouveau 
blacklist rivafb 
blacklist rivatv 
blacklist vga16fb 
options nouveau modeset=0

カーネル・ファイルを更新するために、コマンド $ sudo update-initramfs -u を実行します。

次にシステムをリブートし、変更を有効にします。システムが再起動されると、CUDA 開発者ドライバーをインストールする準備ができたことになります。

CUDA ドライバーをインストールする

CUDA 対応の最新ドライバーの公式リリースを NVIDIA から直接ダウンロードすることができます (「参考文献」を参照)。インストールを進める前にグラフィック・ディスプレイ・マネージャーを無効にする必要があります。コンソール・モードに切り換えるためには、CTRL+ALT+F2 を押します。これで、コンソールから $ sudo sh devdriver_4.1_linux_32_285.05.32.run と入力することで、ドライバー・ファイルの自動インストールを開始することができます。

ドライバーのインストールが完了したら、単純にシステムをリブートし、現在インストールされている GPU を表示している管理メニューから、X サーバーが実行されていることを確認します。

これで、この連載の第 2 回で説明する最適化手法を実行する準備が整いました。


まとめ

gKrypt エンジンには、C/C++ ベースのプロジェクトとの統合方法を示すプラットフォーム・バイナリーとコード・スニペットがバンドルされています。当然ですが、システム・リソースを適切に使用することが不可欠です。考え方としては、最適化されたプラグインを使用することで、互換性や使いやすさを犠牲にすることなく瞬時にパフォーマンスを高めることができます。第 2 回では、最適化手法の詳細について説明し、実際に AES を実装して実行した例を示します。

参考文献

学ぶために

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

  • 皆さんのアプリケーションで 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=816695
ArticleTitle=gKrypt を使用して瞬時にデータを保護する: 第 1 回
publish-date=05242012