no-image

ハッシュ化されたパスワードをJavaScriptで解析してみよう

インターネットを利用する上で常について回るのがセキュリティの話です。特にパスワードに関するセキュリティの話題は毎日尽きません。私たちは「このパスワードで大丈夫か」「破られはしないか」という不安を抱きながら、眠れない夜を過ごすことになります。

そこでちょっと気分転換をしてみましょう。今日だけはパスワードを破られる側ではなく、破る側に回ってみるのです。いろいろなことが学べますし、きっと楽しいはずです。

パスワードの保存形式

パスワードがどういう形式で保存されているかご存知でしょうか?パスワードは、一般的にはハッシュという形で保存されています。元のパスワードは保存せずに、ハッシュ関数というものを用いて、パスワードからハッシュへと変換してから保存します。

しかし、いったいなぜそんなことをするのでしょう?

03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
88d4266fd4e6338d13b845fcf289579d209c897823b9217da3e161936f031589
3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b

実は、パスワードをハッシュに変換してしまうと、ほとんどの場合、元のパスワードには戻せません。つまり、パスワードからハッシュには変換できますが、ハッシュからパスワードには変換できないのです。この一方通行な性質から、ハッシュ関数は一方向性関数と呼ばれます。

こうしてワンクッション置くことで、ハッシュが流出してもパスワードが悪人にバレずに、高いセキュリティを維持することができるのです。

サービス提供側はハッシュを保存しているので、あなたのパスワードのことを全く知りません。あなたがパスワードを忘れた時にもパスワードを教えてくれずに、自分で再設定するハメになるのもこのためです。パスワードがあっているかどうかを見るときには、入力されたパスワードをハッシュに変換して、保存されたハッシュと照合します。

しかしハッシュも万能無敵ではありません。ハッカーたちも、それを破ろうと日夜努力しています。

ハッシュへの攻撃

ハッシュも万能ではない……とは言ってもハッシュからパスワードを復号するのは簡単ではありません。一方向性関数なのですから、簡単に逆変換というわけにはいかないからです。それでも、様々な攻撃方法が考案されています。

最も簡単な攻撃方法は、総当たり(力づく)方式です。最も単純な総当たり方式では、例えば「a」をハッシュ化し、ハッシュとあっているか照合します。次に「b」をハッシュ化して照合します。そして「c」「d」……「z」まで行ったら次は「aa」「ab」と次々に試していきます。「一生やってろ」と言いたくなるようなバカバカしさですが、近年のコンピュータは高性能なので案外バカにはできません。しかし時間がかかりすぎるのも事実なので、実際にはもう少し賢い方法がとられます。

総当たり攻撃をもう少し賢くしたのが辞書攻撃です。ユーザはランダムな文字列ではなく英単語を用いる傾向があるので、辞書の単語を使って解析してみようという試みです。例えば「applebanana」というパスワードは総当たり方式ではとてつもない時間がかかりますが、辞書攻撃ならたった2単語なのであっさり終わってしまいます。

他にもレインボーテーブルという手法もあります。これは攻撃の時に逐一ハッシュ関数で計算するのではなく、あらかじめハッシュ化したリストを持っておき、その中から参照するという手法です。もちろん事前計算に時間はかかりますし、高度に計算されたハッシュには通じにくい手法ですが、単純なハッシュに対しては非常に高速に解析することができます。

JavaScriptでハッシュを解析してみる

ハッシュの仕組みと攻撃の理屈はわかりました。それでは実際にJavaScriptで攻撃を行ってみましょう!今回解析するのは以下の3つのハッシュです:

03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4
88d4266fd4e6338d13b845fcf289579d209c897823b9217da3e161936f031589
3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b

今回環境として使うのはGoogle Chromeです。できるだけ新しいChromeを用意してください。また、攻撃方法としては最も単純である総当たり方式を採用します。解析時間はかかりますが、実装は単純になります。

HTMLファイルは以下のものを使います:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Password Cracking</title>
    <script src="main.js" defer></script>
  </head>
  <body>
  </body>
</html>

あとはmain.jsに処理を書いていきましょう。

今回は簡単のためパスワードに使用する文字を数字と小文字のアルファベットのみに絞ります。また、総当たり方式は非常に時間がかかる処理なので、Web Workersを用いて並列処理を実装します。Web Workersについては「Web Workersを用いてJavaScriptをマルチスレッド化する」をご覧ください。

main.jsは以下のようにします:

// これから解析するハッシュのリスト
const passwordHashList = [
  '03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4',
  '88d4266fd4e6338d13b845fcf289579d209c897823b9217da3e161936f031589',
  '3a7bd3e2360a3d29eea436fcfb7e44c735d117c42d1c1835420b6b9942dd4f1b'
];

// 使用する文字のリスト
// 今回は0-9とa-zのみ
const characters = [
  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
  'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
  'u', 'v', 'w', 'x', 'y', 'z'
];

// 使用するスレッド数。CPUコア数*2 程度にしておく
// 例えばCore i7なら4*2
const MAX_THREADS = 8;

// 1スレッドあたり担当する頭文字の数
// 頭文字で分割することでジョブを均等に分けることができる(はず……)
// 例えば3スレッドなら「頭文字が0からb」「頭文字がcからn」「頭文字がoからz」
// で綺麗に分割できる、と思う……
const LENGTH_PER_THREAD = Math.ceil(characters.length / MAX_THREADS);

// 処理中...と表示
const indicator = document.createElement('div');
indicator.innerText = '処理中...';
document.body.appendChild(indicator);

// MAX_THREADS個のWorkerを起動して計算させる
for(let i = 0; i < MAX_THREADS; i++) {
  // 頭文字の開始インデックス
  const startCharacterIndex = LENGTH_PER_THREAD * i;

  // 頭文字の終了インデックス
  // 次のスレッドのstartIndexと被らないようにするため1を引いておく
  const endIndexTmp = (LENGTH_PER_THREAD * (i + 1)) - 1;

  // charactersのlengthを超えてる場合lengthのほうを採用する
  const endCharacterIndex = Math.min(endIndexTmp, characters.length - 1);

  // パスワードの最長文字数
  const maxLength = 8;

  // Workerを起動してパラメータを投げる
  const worker = new Worker('cracker.js');
  worker.postMessage({
    passwordHashList,
    characters,
    startCharacterIndex,
    endCharacterIndex,
    maxLength
  });

  // workerからメッセージが来たらbody要素に表示する
  worker.addEventListener('message', (message) => {
    const div = document.createElement('div');
    div.innerText = `${message.data.hash} -> ${message.data.password}`;
    document.body.appendChild(div);
  });
}

main.jsの内容はシンプルです。実際に解析処理を行うcracker.jsをWorkerとして起動し、Workerに必要なパラメータを渡します。あとはWorkerから解析結果が届くのを待ち、届いたら表示するだけです。このWorkerをMAX_THREADS個起動します。

各Workerにはできるだけ均等に仕事を割り振りたいので、担当する頭文字を決めます。例えば3スレッドなら各Workerの担当する頭文字は「0-b」「c-n」「o-z」になります。

そして実際に解析を担当するcracker.jsは以下のようにします:

// SHA-256でハッシュを生成する関数
async function sha256(str) {
  const encoder = new TextEncoder('utf-8');
  const strBuffer = encoder.encode(str);

  // WebCrypto APIを使用してSHA-256のダイジェストを生成
  const hashBuffer = await crypto.subtle.digest('SHA-256', strBuffer);
  const hashArray = Array.from(new Uint8Array(hashBuffer));

  // 16進数に変換して、1桁なら0埋め。全部繋いで文字列にする
  const hashHex = hashArray.map((value) => value.toString(16).padStart(2, '0')).join('');
  return hashHex;
}

// charactersのstartIndexからendIndexまでの文字を頭文字とするフレーズを生成する関数
// 再帰的に実行するのでlengthがあまり長いとスタックオーバーフローになるので注意
function* generatePhrase(characters, startIndex, endIndex, length) {
  // 長さが1未満のときは終了する
  if(length < 1) {
    yield '';
    return '';
  }

  // それより長いときは再帰的に実行して文字をつなげる
  for(let i = startIndex; i <= endIndex; i++) {
    // 二文字目以降は全文字(0からcharcters.length - 1)の中から選ぶ
    for(const part of generatePhrase(characters, 0, characters.length - 1, length - 1)) {
      yield characters[i] + part;
    }
  }
}

// パスワードを生成する関数
function* generatePassword(characters, startIndex, endIndex, maxLength) {
  for(let length = 1; length <= maxLength; length++) {
    for(const phrase of generatePhrase(characters, startIndex, endIndex, length)) {
      yield phrase;
    }
  }
}

// メインスレッドからパラメータを渡されたら処理を開始する
self.addEventListener('message', async (message) => {
    const hashList = message.data.passwordHashList;
    const characters = message.data.characters;
    const startIndex = message.data.startCharacterIndex;
    const endIndex = message.data.endCharacterIndex;
    const maxLength = message.data.maxLength;

    // 生成した各パスワードごとにハッシュを計算して
    // リストに一致するものがあればメインスレッドに送る
    for(const phrase of generatePassword(characters, startIndex, endIndex, maxLength)) {
      const shaHash = await sha256(phrase);
      if(hashList.includes(shaHash)) {
        self.postMessage({
          hash: shaHash,
          password: phrase
        });
      }
    }
});

cracker.jsは少し複雑な構造をしています。まずSHA-256という方式でハッシュを作るsha256関数があります。これはWeb Crypto APIを使うだけなので簡単です。

次に指定された長さの英数字のフレーズを順番に生成するgeneratePhrase関数があります。function*という見慣れない関数宣言が見えますが、これはジェネレータを返すジェネレータ関数です。大雑把に説明すると、ジェネレータ関数は一度yieldで値を返した後、またその続きから実行できる関数です。詳しくは「JavaScriptのIteratorとGeneratorを使って反復処理を書く」をご覧ください。

その次にgeneratePassword関数があります。これもジェネレータ関数です。これは1文字〜maxLengthについてgeneratePhraseするだけの関数です。要は「0」「1」「2」…「z」「00」「01」と順番に文字列を返してくれる関数です。

これらを用いてハッシュの解析をします。main.jsからパラメータを受け取ったら処理を開始します。与えられたハッシュ値と合致するフレーズがあれば、そのフレーズをパスワードとしてmain.jsに送信します。

あとはmain.jsが結果を表示してくれます。

さて、これを実際に実行してみましょう!結果が表示されるまでしばらく待ってください。

ハッシュからパスワードを解析することができました!元のパスワードは「abcd」と「1234」と「apple」ですね。「abcd」と「1234」はすぐに出てくると思いますが、「apple」は5桁なので解析に10分ぐらいかかるので、気長に待ってください。

と、こんな感じでパスワードの解析を簡単に体験することができます。こうやってみると、短いパスワードはすぐに解析できて危ないということがわかりますね。また、4文字から5文字になるだけでも解析時間が大幅に増えることから、長いパスワードは非常に有効だということもわかります。

ほんのお遊びですが、パスワードについていろんなことがわかりますね。興味があれば、もっと色々なことを勉強してみましょう。

おまけ:攻撃への対策

こんなに簡単に破られてしまうのならハッシュ化する意味はないのでは?と思うかもしれません。もちろん、実際にはこんな単純なハッシュ関数は使いません。現実には攻撃に対する何かしらの対策が施されています。

攻撃に対する対策の一つは、ソルトと呼ばれる文字列をふりかける手法です。元のパスワードに、ユーザごとに生成したソルト文字列を付与してからハッシュにすることで、元のパスワードよりも強固なものにします。例えばソルトが32文字なら、パスワード「1234」は4文字ではなく、32文字足して36文字のパスワードと同等のハッシュになるのです!

また、ストレッチングと呼ばれる手法もあります。これはパスワードに対してハッシュ関数を何回も、何百回も繰り返しかける手法です。何度も繰り返す分だけ計算時間はかかりますが、単純ながら効果のある方法になります。

セキュリティ専門家たちは、日夜努力して様々な防衛手段を考案しています。こんなお遊び程度のプログラムで破られるほど世の中は単純ではないので、今夜も安心してお眠りください。