Acceleration of Generating Rainbow Tables by MPI Parallelized Processing

IPSJ

Bibliographic Information

Other Title
  • MPI並列処理によるレインボーテーブル生成の高速化

Description

本稿では，PC クラスタと MPI を用いた並列処理によるレインボーテーブル生成の高速化手法を提案する．レインボーテーブルはパスワードクラックにおける辞書攻撃に使用する辞書を圧縮した特殊なテーブルであり，平文とハッシュ値のペアを複数接続して先頭の平文と末尾のハッシュ値を取り出すことで生成される．ペアを接続するためにはハッシュ値から平文を還元する必要があるが，異なるハッシュ値から同じ平文が還元される衝突の可能性があるため，衝突判定処理が必要である．この衝突判定処理に多くの計算時間を要する．衝突判定処理を MPI 並列化によって負荷分散させることで高速化を図る．本稿では英小文字 2，3，4 文字のパスワードすべてを含むレインボーテーブルを実際に生成し，高速化の効果を示す．

In this paper, we propose a method to parallelize rainbow table generation using MPI. Rainbow table is a special compressed dictionary to be used for password cracking. This table consists of connected pairs of password and its hash value. When connecting pairs, we have to detect collisions of reduced password because different hash values may be reduced to the same password. We aim to achieve load balancing and speed up this heavy collision detection process by parallelizing with MPI. We apply our proposed method to generate rainbow tables containing all passwords composed of 2, 3 or 4 lowercase letters for showing the effect of speeding up.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top