MS-CHAPv2 is Obsoleted - JULY’s diary

DEFCON で、PPTP の認証方式として一番ポピュラーな MS-CHAPv2 をクラックするツールが登場した事が、大きな話題になりました。

DEFCON参加の専門家、「MS-CHAP v2」をクラックするツールを発表 - CNET Japan

DEFCON というと、一介のエンジニアには遠い存在で、自分が理解できるような話はない、と思っていたのですが、この話は、思いの外、簡単な話でした。

わかりやすい解説が、英語のブログ記事ででています。

https://www.cloudcracker.com/blog/2012/07/29/cracking-ms-chap-v2/

書いてある中身が分かると、「なんで誰も気がつかなかった？」と思えるほど、単純なことでした。

MS-CHAPv2 とは

PPTP で最もよく使われる、チャレンジ・レスポンス型の認証方式で、PPTP 以外にも、無線 LAN の認証機構としても使われる事があるそうです。

チャレンジ・レスポンス型、というのは、サーバ側がチャレンジ・コードと呼ばれる、その場限りの乱数をクライアントに送り、クライアント側は、その乱数とパスワードを使った計算を行い、その結果をサーバ側に返します。こうすることで、通信上にはパスワードそのものが流れる事がない上に、クライアント側から送られるレスポンスが、毎度違う物になるため、「パスワードそのものは分からないけど、この情報をサーバに渡せば認証が通る」といった事が起きなくなります。割と有名なのは、POP サーバへ繋ぐときの APOP も、このチャレンジ・レスポンス型になります。

レスポンスの計算方法

前述の英語のブログで、「The Protocol」の章にある絵を見ると、クライアント側がユーザのパスワードから、どんな方法でレスポンスを計算するのかが分かります。

クライアントは、サーバからチャレンジ・コード（ServerChallenge）を受け取ります。それが、図ではサーバからクライアントへの矢印が引かれて「Random 16 Byte Server Challenge」と書かれているところです。

その下に書かれた、クライアント側の手順を順に追うと、下記のようなになります。

16 Byte の乱数を生成する。
（Generate 16 Byte ClientChallenge）
自分が生成した乱数と、サーバから送られてきた乱数と、アカウント名をつなげ、それに対する SHA1 のハッシュ値を計算する。
（ChallengeHash = SHA1(ClientChallenge || ServerChallenge || UserName)[0::8]）
ユーザのパスワードに対する MD4 のハッシュ値を計算する。
（NTHash = MD4(UserPassword)）
２番目の手順で計算したハッシュ値（ChallengeHash）に対して、３番目の手順で計算したハッシュ値（NTHash）を鍵として、DES による暗号化を行う。このとき、NTHash の値を３つの値に分割して３つの鍵を作り、３つの鍵それぞれで暗号化した結果をつなげる。
（ChallengeResponse = DES_{NTHash[00:07]}(ChallengeHash) || DES_{NTHash[07:14]}(ChallengeHash) || DES_{NTHash[14:21]}(ChallengeHash)）

この手順の中をよく見ると、ユーザのパスワードが直接分からなくても、３番目の手順で計算した NTHash の値が分かれば、「詰み」な事が分かります。

クライアントから送られるレスポンスの内容は、図で上記の処理を列挙した後に、クライアント側からサーバ側へ引かれた矢印の線の上に「24 Byte ChallengeResponse, 16 Byte ChallengeHash, UserName」と書かれています。ChallengeResponse を計算するための入力値になる物は、ChallengeHash と NTHash で、ChallengeResponse と ChallengeHash はネットワーク上を流れているデータなので、隠された値ではないです。という事は、ChallengeResponse と ChallengeHash の値から、NTHash が逆算できれば、ユーザのパスワードそのものが分からなくても、ChallengeResponse の値を計算する事ができます。

NTHash の値を逆算するには

NTHash の値は、MD4 で計算された値なので、128 bit の数値です。一方、DES の鍵長は 56 bit 固定です。128 bit の値を３つに分けて、56 bit の鍵を３つ作るのですが、ここが実にお粗末です。

「Divide And Conquer」の章の下の図でも説明されていますが、この図を見る前に「どうやって、128 bit の鍵から 56 bit の鍵を３つ作るんだ？」という疑問をもって、MS-CHAPv2 の RFC を読みました。

RFC 2759: Microsoft PPP CHAP Extensions, Version 2

上記ページの「8.5. ChallengeResponse()」を読むと、下記のように書かれています。

Set ZPasswordHash to PasswordHash zero-padded to 21 octets

「zero-padded」つまり、ゼロで穴埋めしています。

という事は、56 bit の３つの鍵のうち、最初の２つは NTHash の 128 bit で賄えますが、最後の鍵は、余った 128 - 56 × 2 = 16 bit に、40 bit のゼロが続く鍵、という事になります。たかだか 2¹⁶ = 65,536 の鍵候補を調べれば良いことになります。

残り２つの鍵は 2⁵⁶ = 72,057,594,037,927,936 通りの鍵を調べれば見つかります。見つけるべき鍵が２つだから、この倍を調べる必要があるように一瞬思いますが、１つの鍵候補に対して、その鍵候補が１つ目の鍵なのか、２つ目の鍵なのか、といった判断をすれば良いので、計算量としては 2⁵⁶で変わりません。

DES の安全性

今時はほとんど AES で、「DES なんて古い暗号は...」と思われがちですが、実は、それほど脆い物でもありません。少なくとも、数分で解けてしまうような穴がある訳ではありません。

http://ja.wikipedia.org/wiki/DES_(%E6%9A%97%E5%8F%B7)

理論的には、2⁵⁶より少ない計算量で解ける方法は考案されていますが、あらかじめ平文と対応する暗号文がある程度集まっている時に、鍵の候補を絞れる、というもので、単純に暗号文だけがある状態から解ける訳ではありません。

それでも、DES の安全性に疑問が付き、それに換わる AES を作ることになったのは、2⁵⁶という鍵長が、十分に長いとは言えなくなってきたためです。

先の Wikipedia での記述にもありますが、1999 年に 22 時間で DES が解けた話が載っています。ただし、25 万ドル掛けた専用マシンに、インターネットで募った 10 万台の PC を使って、ですが、個人ではともかく、組織がお金を掛けて解けば１日足らずで解ける、という状況になった訳です。しかも、13 年前。

ということで、DES 自体には欠陥らしい欠陥は無いのですが、56 bit という鍵長は今時、短すぎるので使われなくなった、といったところです*1。ちなみに AES は最短の鍵長でも 128 bit です。

まとめ

ということで、MS-CHAPv2 の問題は、

クライアントから送られるレスポンスを解析するのに必要な計算量は、56 bit の DES を解くのと同等。

ということになります。

私はこの記事を読んだとき、LM Hash の問題を思い出しました。LM ハッシュの問題はWindows のパスワード強度理論編 - JULYの日記でも書きましたが、パスワード文字列を分割してから、それぞれにハッシュ値を計算しているところです。これも、３つの DES の結果をつなぎ合わせるのではなく、Triple DES の様に、「DES の結果をさらに DES にかける」という事をしていれば問題は無かったのに、と思います。この「分割してから計算」というのが、いかにも Microsoft らしいと思ってしまいました。

*1:DES を三回繰り返すことで、強度を高めた Triple DES は今でも見かけます。三回の暗号化処理で鍵を変えることで、使える鍵長を長くしています。１回目と３回目は同じ鍵を使う 112 bit 鍵の場合と、３回とも別の鍵を使う 168 bit 鍵の物があります。Triple DES に対して、１回だけのものを Single DES と呼ぶこともあります。