Microsoft PowerPoint - tanaka

Size: px

Start display at page:

Download "Microsoft PowerPoint - tanaka"

あまめたかにし
6 years ago
Views:

1 九州大学大学院システム情報科学府情報学専攻田中哲士西出隆志堀良彰櫻井幸一

2 GPGPU とは GPU による暗号実装 AES 暗号の実装研究 RSA 暗号の実装研究 GPU による暗号解析 GPU によるパスワードクラックまとめ 2

3 General-Purpose computing on Graphics Processing Units の略称. GPU を画像処理以外の一般目的の演算に応用する技術. GPU の並列性を利用して問題を解決する. 応用例エンコーダ機械学習物理シミュレータ NVIDIA GeForce 6600 GT ( Graphics_Processing_Unit) 3

4 CPU よりも高い演算性能. FLOPS:1 秒間に浮動小数演算を行える回数. 4

5 当事者にのみデータの内容が理解できるように, データの内容を変換する方式. 共通鍵暗号暗号化, 復号化に同じ鍵を用いる暗号方式. DES 暗号, AES 暗号, RC4 暗号等. 公開鍵暗号暗号化, 復号化に用いるカギが異なる暗号方式. 安全性の根拠に, 数学問題の計算量困難性を利用している. 問題は必ず解けるが莫大な時間を必要とする. RSA 暗号, ElGamal 暗号, ECC 暗号 ( 楕円曲線暗号 ) 等. 5

6 GPU を用いた暗号の実装目的暗号化及び復号化の高速実装. 共通鍵暗号 : 暗号アルゴリズムの実装を行う. 公開鍵暗号 : 暗号アルゴリズムの演算の実装を行う. GPU を用いた暗号の解析目的 GPU の演算能力を暗号解析に利用する. パスワード等の短い鍵を総当たり的に解く. 既存の解読用アルゴリズムを GPU で実装させる. 6

7 2001 年に規格化されたアメリカの標準暗号化方式. 以前準暗号化方式として採用されていた DES 暗号の後継. 56 ビット +8 ビットの長さを持つ鍵を利用するブロック暗号. 16 回の Feistel 構造によるデータ変換を繰り返し暗号化する. コンピュータの発展により現在では DES 暗号は安全ではない. Rijndael アルゴリズムが採用されている. 128, 196, 256 ビット長の鍵を使用できる. 繰り返しは行うが Feistel 構造は使用しない. SPN 構造を使用している. 128 ビットなら 10 回, 256 ビットなら 14 回繰り返す. 7

8 8

9 CryptoGraphics: Secret Key Cryptography Using Graphics Cards. [CIKJ05, RSA Conf. LNCS3376] GPU を用いた暗号の実装における最初の研究. 目的 CPU が負担する暗号化の計算を GPU で肩代わりする. 使用 CPU 及び GPU 使用 GPU GPU 年代使用 CPU NVIDIA GeForce 3 Ti Intel Pentium Ⅳ 1.8 GHz ATI Radeon Intel Pentium Centrino 1.3 GHz NVIDIA Riva TNT Intel Pentium Ⅲ 800 MHz 使用 API OpenGL. 9

10 実装結果 [CIKJ05, RSA Conf. LNCS3376] 32 ビットの XOR の実行レート使用 GPU GPU 年代使用 CPU 実装結果 CPU 結果 GPUによる高速化 NVIDIA GeForce 3 Ti Intel Pentium Ⅳ 1.8 GHz 105.0MBps 139MBps ATI Radeon Intel Pentium Centrino 1.3 GHz 41.5MBps 93.9MBps NVIDIA Riva TNT Intel Pentium Ⅲ 800 MHz 32.8MBps 56MBps AES 暗号におけるそれぞれの暗号化レート使用 GPU GPU 年代使用 CPU 実装結果 CPU 結果 GPUによる高速化 NVIDIA GeForce 3 Ti Intel Pentium Ⅳ 1.8 GHz 1.53Mbps 3.5Mbps ATI Radeon Intel Pentium Centrino 1.3 GHz 278.3Kbps 2.52Mbps NVIDIA Riva TNT Intel Pentium Ⅲ 800 MHz 732Kbps 1.68Mbps CPU 使用率 CPU 実装, GPU 実装ともに 100% の CPU 使用率. 10

11 CUDA compatible GPU as an efficient hardware accelerator for AES encryption. [Manavski07, IEEE ICSPC 07] 目的 GPU を利用した効率的な暗号実装の実現. 使用 CPU Intel Pentium Ⅳ 3.0 GHz 使用 GPU 及び API 使用 GPU GPU 年代使用 API NVIDIA GeForce 8800 GTX 2006 CUDA ATI Radeon X OpenGL 11

12 実装結果 [Manavski07, IEEE ICSPC 07] AES 256 による 8MB の入力ファイルの暗号化時間使用 GPU NVIDIA GeForce 8800 GTX ATI Radeon X1900 GPU 年代使用 API 2006 CUDA 2005 OpenGL GPU 実行時間 CPU 実行時間 GPU による高速化暗号化 9.39ms 合計時間 27.3ms ms 暗号化 120ms 1.23 合計時間 804ms AES 128 による 8MB の入力ファイルの暗号化時間使用 GPU NVIDIA GeForce 8800 GTX GPU 年代使用 API 2006 CUDA GPU 実行時間 CPU 実行時間 GPU による高速化暗号化 7.55ms ms 合計時間 25.0ms

13 その他の AES 暗号実装 [HW07, CHES 2007, LNCS4727], [KS09], [JHHMP10, SIGCOMM 2010] 文献使用 GPU GPU 年代使用 CPU 使用 API 実装結果 GPU による高速化論文年代備考 [HW07] NVIDIA GeForce 6600GT 2004 AMD CPU 2GHz OpenGL PBO 44.89MBps CPU 使用率 13.25% [HW07] NVIDIA GeForce 7900GT 2006 AMD CPU 2GHz OpenGL PBO MBps CPU 使用率 25.16% [KS09] NVIDIA GPU 不明不明 CUDA 1.211GBps [JHHMP10] NVIDIA GeForce GTX Intel Xeon X5550 CUDA 1.130GBps CBC モード CBC(Cipher Block Chain) モード前のブロックの結果を次のブロックに利用する. 13

14 GPU で実装する事で CPU よりも高速に実装できている. [Manavski07, IEEE ICSPC 07] の倍の高速化は驚異的. 動作全体の高速化は 5.92 倍に留まる. CPU と GPU のデータのやり取りによる遅延. 世代が若干異なっている. Intel Pentium Ⅳ 3.00 GHz, 2002 年 1 月 ~2006 年 1 月 NVIDIA GeForece 8800GTX, 2006 年 11 月 Intel Core2 Extreme X GHz, 2006 年 7 月 CBC モードでの GPU による暗号化の高速実装は難しい. 前のブロックの暗号化の結果が必要なため, 並列化が困難. 復号時は並列に行うことができる. 14

Rivest, Shamir, Adleman が発明した公開鍵暗号. 安全性の根拠桁数が大きい合成数の素因数分解問題の困難性.

15 Rivest, Shamir, Adleman が発明した公開鍵暗号. 安全性の根拠桁数が大きい合成数の素因数分解問題の困難性. 例 :RSA-170(563 ビット ) [BK10] = 実用上では, 最低でも合成数を 1024 ビットにする必要がある. RSA 暗号で使用される演算べき剰余算 15

16 Toward acceleration of RSA using 3D graphics hardware. [MPS07, IMACC 2009, LNCS 4887] 目的べき剰余算を GPU 上で実装し, RSA 暗号の高速化を図る. 使用 CPU 及び GPU AMD GHz NVIDIA GeForce 7800 GTX 実装言語 GLSL(OpenGL シェーディング言語 ) 16

17 Public Key Cryptography on Modern Graphics Hardware. [HW09, EUROCRYPT 2009] 目的べき剰余算を GPU 上で実装し, RSA 暗号の高速化を示す. 使用する GPU NVIDIA GeForce 8800GTX. 使用 API CUDA. 17

18 Accelerating SSL with GPUs. [JHHMP10, SIGCOMM 2010] 目的 Web サーバに対する SSL プロキシを GPU で実装し, 高いスループットと低いレイテンシを実現する. 使用 CPU 及び GPU Intel Xeon X5550 NVIDIA GeForce GTX480 使用 API CUDA 18

19 実装結果 1024 ビットのべき剰余算の実行結果 [MPS07, IMACC 2009, LNCS 4887], [HW09, EUROCRYPT 2009] 文献使用 GPU GPU 年代実装言語使用 API 実装結果 CPU 結果 GPUによる高速化 [MPS07] NVIDIA GeForce 7800GTX 2005 GLSL OpenGL 5.7 ms/op 17.0 ms/op 3.77 [HW09] NVIDIA GeForce 8800GTX 2006 CUDA 0.27 ms/op 0.68 ms/op 2.52 RSA 暗号のスループット [JHHMP10, SIGCOMM 2010] 使用 CPU 1024-bit 2048-bit 4096-bit CPU スループット Intel Xeon X5550 7,268 msg/s 1,160 msg/s 164 msg/s GPU スループット NVIDIA GeForce GTX ,970 msg/s 9,995 msg/s 1,348 msg/s GPUによる高速化

20 べき剰余算は GPU 上で実装してもあまり高速化できていない. GPU はシリアルな処理は得意ではない. べき乗算は乗算の繰り返し. RNS(Residue Number System: 剰余数系 ) の基数拡張が計算のコストになっている. [JHHMP10, SIGCOMM 2010] は高速化に成功している. 多倍長整数の乗算を CPU でネイティブな整数の集団に変換. k ビットの整数を並列に O(k) で解決する乗算を利用している. 20

21 Comparison of Modular Arithmetic Algorithms on GPUs. [GIT09, ParCo 09] GPU Accelerated Elliptic Curve Cryptography in. [CP10, IEEE MWSCAS 2010] ECC(Elliptic Curve Cryptosystem: 楕円曲線暗号 ) の基本演算を実装している. Speed records for NTRU. [HVB10, RSA Conf. LCNS5985] NTRU 暗号の暗号化, 復号化を共に実装している. 21

22 Brute force attack on UNIX passwords with SIMD computer. [KI99, Security 99] GPU を用いた最初の暗号分野の研究. PixelFlow を巨大な 8 ビットの SIMD マシンとして考え, そのマシンパワーを利用してパスワードを解く. PixelFlow ノースカロライナ大学チャペルヒル校が開発したグラフィックエンジン. あらゆる UNIX のパスワードをブルートフォースアタック ( 総当たり攻撃 ) により 1 日, 2 日で解読可能. 同様にあらゆる 56 ビットの暗号を解読可能. 辞書攻撃, ブルートフォースアタックに耐性のあるパスワードスキームの提案. 22

23 近年, GPU に対応したパスワードクラックツールが市場に流通するようになった. 市販 GPU を使ってパスワードを高速クラック. [ElcomSoft07] GPUs Used To Crack WiFi Passwords Faster. [ElcomSoft09] GPU の演算性能の発展がセキュリティの基準に影響を与えつつある. パスワードは最低でも 12 文字必要となる. [TeraFlops10] 23

24 GPU-based password cracking. [BJ10] GPU を用いて複数のパスワードクラックツールで, 様々なパスワードハッシュ関数にクラッキングを仕掛けている. 使用 CPU 及び GPU Intel Core i7 975 NVIDIA GeForce GT295 使用ツール Elcomsoft Extreme GPU Bruteforcer IGHASHGPU BarsWF bruteforce 24

25 実験結果 [BJ10] ハッシュ関数使用ツール性能 (Million password / s) MD5 Elcomsoft 1750 Extreme GPU Bruteforcer 2260 IGHASHGPU 2770 BarsWF bruteforce 3200 BarsWFx64(Intel core i7 975 EE) 358 NTLM Extreme GPU Bruteforcer 3050 IGHASHGPU 3050 EnTibr0.1(Intel core i7 975 EE) 233 DCC Extreme GPU Bruteforcer 1556 IGHASHGPU 1565 MDCrack1.8.3(Intel core i7 975 EE) 162 Oracle 11g IGHASHGPU

26 GPU で実装することにより高速なクラックが可能. ブルートフォースアタックは各試行が独立して行える. GPU の並列性を用いた実装が有効. MD5 で 3200 Million password/s 5 文字以内のパスワードを 2.32 秒で探索可能. 8 文字のパスワードは 22 日で探索可能. 12 文字のパスワードは探索に 471 万年かかる. 26

27 ECM on Graphics cards. [BCCLY09, EUROCRYPT 2009 LNCS5479] ECM(Elliptic Curve Method: 楕円曲線法 ) の最大公約数による判定を GPU で実装している. CPU と GPU2 枚を使用して, curves/s を実現. GPU1 枚の場合, curves/s. Parallel Shortest Lattice Vector Enumeration on Graphics Cards. [HSBVP10, AFRICACRYPT 2010, LNCS6055] ENUM 法を GPU で実装している. 高次元のラティスでは,GPU は CPU より 5 倍高速に動作する. 27

28 Factorization of RSA-170. [BK10] RSA-170 チャレンジ解決までの技術レポート. 一般数体篩法で素因数分解を行っている. GPU は篩で用いる多項式の選択に使用される. Cryptanalysis of the DECT Standard Cipher. [NTW10, FSE 2010, LNCS6147] DECT 標準暗号を現実的に解読する手法を提案. DECT(Digital Enhanced Cordless Telecommunications) デジタルコードレス電話規格. 30 個の方程式, 個のキーストリームを用いて50% 程度の割合で, 実行時間内に暗号に暗号の秘密鍵を取得できる. GPUを用いることで,6.2 倍程度高速化できる. 28

29 実験的な研究が多い. 既存の暗号の GPU 実装. GPU で実装した攻撃法の性能実験. 実用上での問題点はないのか. 消費電力はどの程度になるのか. ミドルエンド, ローエンドの GPU でも対応できるのか. 誰が恩恵を受けるのか. 29

30 GPU を用いた暗号の高速実装. GPU で暗号を実装する目的が重要. 高速化することで何を達成できるか. e.g. 公開鍵暗号が高速化された. 公開鍵暗号のみで実用的に通信できるようになった. GPU を用いた暗号の解析実践的な解析の研究を行うべきである. 暗号解析の結果は安全性の指標となる. GPU は攻撃者にも容易に入手可能. 安価な攻撃道具として使用される可能性がある. 30

31 GPU を利用した暗号の高速実装及び, 解析に関する論文を調査した. GPU を利用することにより暗号化, 解析ともに高速に処理を行うことができる. 現状の研究は実用に関する言及が少ない. 実践的な研究が行われるべきである. 31

32 [BCCLY09, EUROCRYPT 2009 LNCS5479] D. J. Bernstein, T.-R. Chen, C.-M. Chen, T. Lange and B.-Y. Yang, ECM on Graphics Cards. In EUROCRYPT 2009, LNCS, vol. 5479, pp , Springer, April 26-30, [BJ10] M. Bakker and R. Jagt, GPU-based password cracking. University of Amsterdam System and Network Engineering, February 5, [BK10] D. Bonenberger and M. Krone, Factorization of RSA-170, Fachhochschule Braunschweig / Wolfenbüttel University of Applied Sciences, March 8, [CP10, IEEE MWSCAS 2010] A. E. Cohen and K. K. Parhi, GPU Accelerated Elliptic Curve Cryptography in GF( ). In the 53rd IEEE International Midwest Symposium on Circuits and Systems, pp , IEEE, August 1-4,

33 [CIJL05, RSA Conf. LNCS3376] D. Cook, J. Ioannidis, A. Keromytis and J. Luck, CryptoGraphics: Secret Key Cryptography Using Graphics Cards. In the Cryptographer s Track at the RSA Conference 2005, LNCS, vol. 3376, pp , Springer, February 14-18, [GIT09, ParCo 09] P. Giorgi, T. Izard and A. Tisserand, Comparison of modular arithmetic algorithms on GPU. In International Conference on Parallel Computing, September 1-4, [ElcomSoft07] 市販 GPUを使ってパスワードを高速クラック. 33

34 [ElcomSoft09] GPUs Used To Crack WiFi Passwords Faster. [HSBVP10, AFRICACRYPT 2010, LNCS6055] J. Hermans, M. Schneider, J. Buchmann, F. Vercauteren and B. Preneel, Parallel Shortest Lattice Vector Enumeration on Graphics Cards. In Africacrypt 2010, LNCS, vol. 6055, pp , Springer, May 3-5, [HVB10, RSA Conf. LCNS5985] J. Hermans, F. Vercauteren and B. Preneel, Speed Records for NTRU. In the Cryptographer s Track at the RSA Conference, 2010, LCNS, vol. 5985, pp , Springer, March 1-5,

35 [HW07, CHES 2007, LNCS4727] O. Harrison and J. Waldron, AES Encryption Implementation and Analysis on Commodity Graphics Processing Units. In 9 th Workshop on Cryptographic Hardware and Embedded Systems, LNCS, vol. 4727, pp , Springer, September 10-13, [HW09, EUROCRYPT 2009] O. Harrison and J. Waldron, Public Key Cryptography on Modern Graphics Hardware. Booklet of posters, Eurocrypt 2009, April 26-30, [JHHMP10, SIGCOMM 2010] K. Jang, S. Han, S. Han, S. Moon and KS. Park, Accelerating SSL with GPUs. In ACM SIGCOMM Computer Communication Review, vol. 40, issue 4, pp , poster, August 30-September 3,

36 [KI99, Security 99] G. Kedem and Y. Ishihara, Brute Force Attack on UNIX Passwords with SIMD Computer. In the 8 th USENIX Security Symposium, vol. 8, pp , USENIX, August 25-26, [KS09] M. Kipper, J. Slavkin and D. Denisenko, Implementing AES on GPU Final Report. University of Toronto, April 20, 2009 [Manavski07, IEEE ICSPC 07] S. Manavski, CUDA compatible GPU as an efficient hardware accelerator for AES cryptography. In 2007 IEEE International Conference on Signal Processing and Communications, pp.65-68, IEEE, November 24-27,

[MPS07, IMACC 2007, LNCS 4887] A. Moss, D. Page and N. Smart, Toward Acceleration of RSA Using 3D Graphics Hardware. In Eleventh IMA International Conference on Cryptography and Coding, LNCS, vol.

37 [MPS07, IMACC 2007, LNCS 4887] A. Moss, D. Page and N. Smart, Toward Acceleration of RSA Using 3D Graphics Hardware. In Eleventh IMA International Conference on Cryptography and Coding, LNCS, vol. 4887, pp , Springer, December 18-20, [NTW10, FSE 2010, LNCS6147] K.Nohl, E. Tews and R.-P. Weinmann, Cryptanalysis of the DECT Standard Cipher, In the 17 th International Workshop on Fast Software Encryption, LNCS, vol. 6147, pp Springer, February 7-10, [TeraFlops10] Teraflop Troubles: The Power of Graphics Processing Units May Threaten the World s Password Security System. Power-Graphics-Proccessing-Units-GPUs-Password- Security-System 37

1 GPU GPGPU GPU CPU 2 GPU 2007 NVIDIA GPGPU CUDA[3] GPGPU CUDA GPGPU CUDA GPGPU GPU GPU GPU Graphics Processing Unit LSI LSI CPU ( ) DRAM GPU LSI GPU

1 GPU GPGPU GPU CPU 2 GPU 2007 NVIDIA GPGPU CUDA[3] GPGPU CUDA GPGPU CUDA GPGPU GPU GPU GPU Graphics Processing Unit LSI LSI CPU ( ) DRAM GPU LSI GPU GPGPU (I) GPU GPGPU 1 GPU(Graphics Processing Unit) GPU GPGPU(General-Purpose computing on GPUs) GPU GPGPU GPU ( PC ) PC PC GPU PC PC GPU GPU 2008 TSUBAME NVIDIA GPU(Tesla S1070) TOP500 29 [1] 2009 AMD