自宅のレインボーテーブル

情報セキュリティの観点から見ると、先週は例外的に「成功」​​したことが判明しました。LinkedInハッシュベースがネットワークにリークしたか、 last.fmハッシュのいずれかです。 そして、すべての議論において、何らかの形で、彼らはレインボーテーブルについて言及しています。

ほとんどの人がそれらについて聞いたが、自分の手で作った人はほとんどいなかった。



ハッシュとは何か、また、原則として、レインボーテーブルやその他の事前計算が必要な理由について再話するのは賢明ではないと思います。 白い斑点をなくすには、このトピックを読むことをお勧めします。



今日のレインボーテーブルの分野では、知的な突破口は計画されていませんが、レインボーテーブルは難しくないことを伝えたいので、簡単なもの、つまりPHPについて書きます。 テーブルをMySQLに保存します。



すべてのコードはGoogleCodeで入手できますが、私が考えなければならなかった、実装する必要がある主なポイントについて説明します。



最初に、入力アルファベットについて話す必要があります。 テーブルのすべてのASCII文字がパスワードセットに参加するわけではなく、PCまたはモバイルデバイスのキーボードで不必要なトリックなしで入力できる文字のみがパスワードセットに含まれます。 入力アルファベットが小さいほど、レインボーテーブルはより速く生成されますが、指定されたハッシュのパスワードは少なくなります。 この例では、大文字と小文字のラテンアルファベットの数字と文字の入力アルファベットを使用します。

$ALPHABET = array_merge(range(0, 9), range('A', 'Z'), range('a', 'z')); $LAST_SYMBOL = count($ALPHABET) - 1; //    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

レインボーテーブルを作成するには、チェーンを使用します。チェーンの先頭は、固定長のランダムパスワードです。 明らかに、入力アルファベットの文字からランダムパスワードを生成する関数が必要です。

 define('WORD_LENGTH', 6); //  ,      function getWord($newRandom = false) { global $ALPHABET, $LAST_SYMBOL; if($newRandom) { mt_srand(); } $word = $ALPHABET[mt_rand(0, $LAST_SYMBOL)]; for($i = 1; $i < WORD_LENGTH; ++$i) { $word .= $ALPHABET[mt_rand(0, $LAST_SYMBOL)]; } return $word; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

チェーン内では、ハッシュ関数が交互に適用され、次にリダクション関数が適用されます。 ハッシュ関数を使用すると、すべてが明確になります-これはMD5、SHA1、またはその他（この場合、MD5を使用します）です。 リダクション機能を使用すると、明瞭さが低下します。 まず、入力でハッシュを受け取ったリダクション関数は、入力アルファベットの文字からパスワードを生成する必要があります。 次に、リダクション関数は1つだけでなく、リダクション関数の順序付きセットが必要であり、このセットのパワーはチェーンの長さに等しくなります。



もちろん、2つまたは3つのリダクション関数を独立して書くこともできますが、チェーンの長さが100または1000の場合はできません。さらに、チェーンの長さを定数に格納して、手のわずかな動きに置き換えることができます。



かなり明白な解決策が思い浮かびます： 疑似乱数ジェネレーター （PRNG）を使用する必要があります。 特定のリダクション関数ごとに、入力に入力されたハッシュの特定のビットセットでPRNGを初期化し、getWord（）呼び出しを使用してパスワードを取得します。



原則として、個々のビットのレベルで動作する必要はありません。 PRNCは、int型の数で初期化する必要があります。私のプラットフォームでは、32ビットまたは4バイトです。 MD5は16バイトで構成され（PHPのmd5関数の2番目のパラメーターを見てください）、可能な割り当ての数は16です！ /（16-4）！ = 43680-チェーンの長さが1000であっても、マージンがあれば十分です。



すぐに言ってやった：

 define('CHAIN_LENGTH', 1000); //       define('HASH_LAST_BYTE', 15); //    ,   0 ( MD5 – 15) $reductions = array(); // ,         mt_srand(CHAIN_LENGTH); //    ,                 $i = 0; while($i < CHAIN_LENGTH) { $positions = array(); $positions[] = mt_rand(0, HASH_LAST_BYTE); for($j = 1; $j < 4; ++$j) { do { $ind = mt_rand(0, HASH_LAST_BYTE); if(!in_array($ind, $positions)) { $positions[] = $ind; break; } } while(true); } if(!in_array($positions, $reductions)) { //    $reductions[] = $positions; ++$i; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハッシュとチェーン内の現在のステップの番号を取得するリダクション関数自体は次のようになります。

 function reduction($hash, $step) { global $reductions; $pos = $reductions[$step % CHAIN_LENGTH]; mt_srand(ord($hash[$pos[0]]) | ord($hash[$pos[1]]) << 8 | ord($hash[$pos[2]]) << 16 | ord($hash[$pos[3]]) << 24); return getWord(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記を考えると、チェーンの開始時の終了を計算する機能は簡単です。

 function getEndOfChain($word, $startStep = 0, $length = CHAIN_LENGTH) { for($i = $startStep; $i < $length; ++$i) { $hash = md5($word, true); $word = reduction($hash, $i); } return $word; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おめでとうございます、私たちは素晴らしい仕事をしました、そして、あなたが話す必要がある与えられたハッシュのパスワードを見つけることの1つの側面だけがありました。



クラシックバージョンでは、ハッシュから最後のn番目のリダクション関数が取得され、レインボーテーブルで結果のパスワードが検索されます。何も見つからない場合、n-1リダクションが取得され、ハッシュが計算され、次にn番目のリダクションがテーブルで検索されます。パスワードがあります。 MySQLを使用する場合、これは同じタイプのn個のSELECT（最悪の場合）をもたらす可能性があります-初心者のWebプログラマーでさえ、手に入れることができるものを知っています！ もちろん、1つのSELECTで1つのパスワードを検索するには十分ですが、このためには、一度に検索するためにすべてのパスワードを生成する必要があります。

 function getWordsInChain($hash) { $words = array(); //        100, 99, 98   for($i = 0, $n = CHAIN_LENGTH; $i < $n; ++$i) { $wordStart = reduction($hash, $i); $wordEnd = getEndOfChain($wordStart, $i + 1); $words[] = $wordEnd; } return $words; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

他のすべてのMySQL操作は、レインボーテーブルに直接関連していないため、ソースコードの他の部分は説明なしで理解できると思います。



そして最後に、軟膏のハエ。 PHPとMySQLは、プロトタイプを急いで作成するのに非常に優れていますが、PHPは実際には最速の言語ではなく、汎用リレーショナルDBMSにレインボーテーブルを保存することは最も効果的なソリューションではありません。 i3-330UMベースのラップトップは、200万レコードのうち1000文字のチェーン長を持つ6文字のパスワード用のMD5のレインボーテーブルで、8時間以上生成されました。 理想的には、結果のテーブルは2 * 10 ^ 9のハッシュを逆にすることができますが、この数は6文字のパスワードの総数とは一致しません。選択した入力アルファベットの56.8 * 10 ^ 9です。



これもまた、特定の問題を解決するための適切なツールを選択することがいかに重要であるかを示しています。

それでも私は、PHPとともにレインボーテーブルを実装する原理を明確に示す問題を解決できたと思います。



ご清聴ありがとうございました。