アーキテクチャー：レインボーテーブル

なるほどー。

あとできちんと咀嚼しよう。

===

レインボーテーブルは、２カラムのデータストアで、カラムAはASCIIの文字列、カラムBはカラムAに対するハッシュ関数の結果が入っている。

もしユーザーのパスワードが何か？を特定したい場合や、パスワードのハッシュにアクセスしたい場合、カラムBに対するハッシュを比較する必要がある。ハッシュが一致すれば、ユーザのパスワードはカラムAの値であることがわかる。

レインボー攻撃( rainbow attack)とは、ハッシュ値に変換されたパスワードを解析する攻撃手法。あらかじめハッシュ値となりうる文字列のハッシュをレインボーテーブルに保持しておくことで、ターゲットとなるパスワードのハッシュ値から本来のパスワードを推測する手段である。

ASCII文字列のすべての組み合わせに対してハッシュを生成するコストは高いので、負荷を分散するためにコミュニティができた。継続的にハッシュ計算を行い、レインボーテーブルに追加するプロジェクトがいくつかある。 Free Rainbow Tables プロジェクトは、主要なハッシュをカバーしており、1～25文字のすべての文字の組み合わせを可能にしている。

信じられないことに、現在のプロジェクトは、1～25文字でできるすべての組み合わせの文字列をseedとして、1～25文字の文字列の組み合わせの再計算を行なっている。

Free Rainbow Tablesのレインボーテーブルは、圧縮されたハッシュで5.7TBになっている。

Free Rainbow Tablesは、分散処理にBONICを使っている。

アクティブマシン：3486台
オンラインマシン：2296台
CPUパワー： 16925 GIOPS
スピード： 1400億 link/秒
直近24時間：193億チェイン
直近24時間のデータ増加：288.1GB

変更せずに塩漬け(salting)で放置しているパスワードは攻撃対象になりやすい。レインボー攻撃から守るには、認証プロトコル層で防ぐか、辞書の用語よりも強いパスワードを選ぶ（長いパスワードは辞書にない事が多く、それがレインボーテーブルを始める切っ掛けでもある）か、26個のアルファベットの組み合の代わりに、ASCII-256やUTF-8空間を使う。

GPUコンピューティング界隈でもレインボーテーブルは興味深いらしい。

http://project-rainbowcrack.com/

また、SSDを使ったりするらしい

http://www.ciozone.com/index.php/Security/Cracking-14-Character-Complex-Passwords-in-5-Seconds.html

EC2のGPU インスタンス数の上限を設定しているのは、このような処理をさせないことも理由の一つである。