レインボー攻撃をC++で実装してみる

はじめに

レインボー攻撃、という言葉があります。

パスワードのハッシュ値を解析し、元のパスワードを特定する攻撃手法であり、「レインボーテーブル」というものを使って行われます。

レインボーテーブルは以下のように作成されます。

1. 適当な文字列をハッシュ化する
2. ハッシュ値から還元関数を用いてそのハッシュ値を持つ文字列を求める
3. その文字列からさらにハッシュ値を求める
4. 1-3を繰り返し、「チェイン」を作成する
5. このチェインをテーブルに保存し、別の文字列をスタート地点として新しいチェインを作成する
6. テーブルの最初と最後の文字列を保存し、それを「レインボーテーブル」に保存する
7. これを繰り返し、レインボーテーブルを拡大する

還元関数はチェイン内の各ステップで違うものを用いますが、異なるチェイン同士では同じものを同じ順番で使います。チェインは以下のような感じとなっています。

文字列1→ハッシュ関数→ハッシュ値1→還元関数1→文字列2→ハッシュ関数→・・・→ハッシュ値n→還元関数n→文字列n+1

ここで、パスワード認証のメカニズムを確認しておきましょう。まず、入力欄からパスワードを受け取り、それをもとにハッシュ関数でハッシュ化します。そして、そのハッシュ値をデータベースに保存されているハッシュ値と比較します。もし一致すれば、認証成功となります。データベースにはIDとパスワードのハッシュ値のペアしか保存されておらず、何らかの手段でIDとハッシュ値を入手したとしても、それを入力しただけでは別のハッシュ値となるため、パスワードを特定することはできません。

しかし、レインボーテーブルを使うことで、ハッシュ値から元のパスワードを特定することができます。仕組みは以下のようになります。

1. 入手したハッシュ値に還元関数nを適用する
2. その文字列がいずれかのチェインの末尾にあるかどうかを確認する
3. あったら、そのハッシュ値を作成した文字列をチェインを逆にたどって特定する
4. ない場合、上で言う還元関数n-1を入手したハッシュ値に適用し、新たな文字列を得て、さらに各チェインの末尾を1つ前に戻してから各チェインの探索をする

これをすることにより、記憶領域を節約しながら総当たりよりも効率的にパスワードの特定ができるというわけです。

実装

では、C++を用いてレインボー攻撃を実装してみましょう。

ハッシュ関数としてMD5を使うこととします。この方式では128ビットの長さを持つハッシュ値が計算されます。また、パスワードとして4文字の数字のみを使うことにします。パスワードとしては惰弱なもので、10000通りしかないので総当たりできそうですが、例なのでこのようにします。

コード全体は以下のようになっています。

#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <openssl/md5.h>
using namespace std;

const int PASSWORD_SPACE = 10000; // 0000 ~ 9999 の10,000通り
const int CHAIN_LEN = 100;        // チェインの長さ (t)
const int TABLE_SIZE = 300;       // テーブルの行数 (m)

// MD5ハッシュを計算して16進数文字列を返す関数
string md5(const string &str)
{
    unsigned char digest[MD5_DIGEST_LENGTH];
    MD5(reinterpret_cast<const unsigned char *>(str.c_str()), str.length(), digest);
    stringstream ss;
    for (int i = 0; i < MD5_DIGEST_LENGTH; i++)
    {
        ss << hex << setw(2) << setfill('0') << static_cast<int>(digest[i]);
    }
    return ss.str();
}

// ハッシュ文字列の先頭を数値に変換する補助関数
unsigned long long hash_to_long(const string &hash)
{
    stringstream ss;
    ss << hex << hash.substr(0, 16); // 先頭16文字(64ビット分)を切り出し
    unsigned long long val = 0;
    ss >> val;
    return val;
}

// 縮約関数 (Reduction Function: R_i)
// ハッシュ値と現在の「ステップ数」から、4桁の数字文字列を生成する
string reduce(const string &hash, int step)
{
    unsigned long long val = hash_to_long(hash);
    int num = (val + step) % PASSWORD_SPACE;
    stringstream ss;
    ss << setw(4) << setfill('0') << num;
    return ss.str();
}

// テーブルの1行(開始点と終着点のペア)
struct RainbowRow
{
    string start;
    string end;
};

// テーブルの事前生成
vector<RainbowRow> generate_table()
{
    vector<RainbowRow> table;
    for (int i = 0; i < TABLE_SIZE; ++i)
    {
        // 開始点がバラけるように等間隔で初期パスワードを生成
        int start_num = (i * (PASSWORD_SPACE / TABLE_SIZE)) % PASSWORD_SPACE;
        stringstream ss;
        ss << setw(4) << setfill('0') << start_num;
        string start_p = ss.str();
        string current_p = start_p;
        // チェインを最後まで伸ばす
        for (int step = 0; step < CHAIN_LEN; ++step)
        {
            string h = md5(current_p);
            current_p = reduce(h, step);
        }
        // 開始点と最終的な縮約結果を保存
        table.push_back({start_p, current_p});
    }
    return table;
}

// レインボーテーブルからの探索
string search_table(const string &target_hash, const vector<RainbowRow> &table)
{
    // ターゲットハッシュがチェインの「どの位置」にあるかを後ろから逆算していく
    for (int k = CHAIN_LEN - 1; k >= 0; --k)
    {
        string current_hash = target_hash;
        string current_p = "";
        // k番目のステップから最後のステップまでシミュレート
        for (int step = k; step < CHAIN_LEN; ++step)
        {
            current_p = reduce(current_hash, step);
            if (step < CHAIN_LEN - 1)
            {
                current_hash = md5(current_p);
            }
        }
        // シミュレートした末尾(current_p)がテーブルのendに存在するかチェック
        for (const auto &row : table)
        {
            if (row.end == current_p)
            {
                // ヒットしたら、その行の開始点(start)からチェインを再現して検証
                string recon_p = row.start;
                for (int step = 0; step < CHAIN_LEN; ++step)
                {
                    string recon_h = md5(recon_p);
                    if (recon_h == target_hash)
                    {
                        return recon_p; // パスワード復元成功
                    }
                    recon_p = reduce(recon_h, step);
                }
            }
        }
    }
    return ""; // テーブルのカバー範囲外で見つからなかった場合
}

int main()
{
    // g++ -O3 rainbow-attack.cpp -o rainbow-attack.out -lcrypto && ./rainbow-attack.out
    auto table = generate_table();
    string target_hash;
    cout << "Enter the target hash: ";
    cin >> target_hash;
    string result = search_table(target_hash, table);
    if (result.empty())
    {
        cout << "Password not found in the table." << endl;
    }
    else
    {
        cout << "Password found: " << result << endl;
    }
    return 0;
}

プログラムには何らかの手段で入手したハッシュ値を入力します。最初にgenerate_table関数でテーブルが新規作成されます。ここでは、等間隔で初期パスワードが生成され、それを左端としてチェインが伸ばされていきます。

search_table関数では作成されたレインボーテーブルから、入力されたハッシュがチェインのどこにあるのかを逆算していきます。位置が分かったら、そのチェインの最初から変換を試していくことで、元となった文字列が分かるという仕組みです。

コードは以下のリポジトリに上げているので、興味がある方は実行してみて下さい。

テスト

試しにパスワードを特定してみましょう。

「2026」というパスワードを設定したとします。これをMD5でハッシュ化すると「c92a10324374fac681719d63979d00fe」となります。このハッシュ値が漏洩したと考えましょう。

>>> from hashlib import md5
>>> print(md5("2026".encode()).hexdigest())
c92a10324374fac681719d63979d00fe

このハッシュ値を、先ほどのコードをコンパイルしたrainbow-attack.outに入力すると、、、

$ ./rainbow-attack.out
Enter the target hash: c92a10324374fac681719d63979d00fe
Password found: 2026

このように、しっかりとパスワードが復元できました。

おわりに

今回はレインボー攻撃を実装してみました。実際にこの方法を使ってパスワードを不正に特定することは違法行為なのでやってはいけませんが、セキュリティの観点からみて原理を知っておくことは良いことかな、と思います。

実際には、安全性を高めるためにハッシュ値を生成する際ソルトと呼ばれるランダムな文字列を付加し、同じパスワードでも異なるハッシュ値が計算されるようにしたり、ハッシュ値をさらにハッシュ関数にかけたりなどといった対策により、パスワード認証の安全性が高められています。

参考文献

ハッシュ化と暗号化の違いとは？ | サイバーセキュリティ情報局

レインボーテーブルを実装してみた - CTFと共に生きる