Adobeサイトから漏えいした暗号化パスワードはなぜ解読されたか

Adobe社のサイトの不正アクセス（参照、参照）によって、少なくとも3800万人のIDと暗号化されたパスワードが漏えいしたと言われています。既に報告したように、私のアカウントも漏えいしていました。
その後、『Adobeの情報流出で判明した安易なパスワードの実態、190万人が「123456」使用』というニュースが流れてきました。安易なパスワードが使われている統計は今までもあり、「パスワードの実態」に関しては「そんなものだろうな」と思いましたが、問題は、どうやって「暗号化パスワード」を解読したかです。
別の報道では、Adobeサイトがパスワードの暗号化に用いていたアルゴリズムはトリプルDESだったということです。トリプルDESは電子政府推奨暗号リストの今年の改訂でもしぶとく生き残り広く使われている暗号化アルゴリズムです。そんなに簡単に解読されたのでは問題ですが、実際には、「トリプルDESが解読された」わけではないようです（良かったw）。

先の報道および参照元によると、暗号鍵を解析して復号したのではなく、別の方法でパスワードそのものを推測したということです。しかし、方法はともかく、平文パスワードを取得されてしまっては暗号化の意味がありません。そこで、なぜ平文パスワードを解読されてしまったかを調べて見ました。
謎を解く鍵は、以下のコメントにあります。

集計できた理由としてSCGのジェレミ・ゴスニー最高経営責任者（CEO）は、「Adobeがハッシュよりも対称鍵暗号を選び、ECBモードを選択し、全てのパスワードに同じ鍵を使っていたことや、ユーザーが平文で保存していたパスワード推測のヒントがあったおかげ」だと説明している。
Adobeの情報流出で判明した安易なパスワードの実態、190万人が「123456」使用より引用

以下、順に説明します。

ECBモードで暗号化されていた

Adobeサイトのパスワードはブロック暗号化モードとしてECBが選択されていたということですが、これを言い換えると、「元のパスワードが同じであれば、暗号化されたパスワードも同じになる」ということです。「当たり前じゃないか」と思う人がいるかもしれませんが、同じパスワードが常に同じ暗号結果になると、平文（元パスワード）推測の大きなヒントになります。
なぜなら、暗号化パスワードの中に、出現数の非常に多いものがあれば、「passwordや123456などよく使われる安易なパスワード」である可能性が高いことになります。仮に暗号文からの解読ができないにしても、元のサイトに対して辞書攻撃を掛ければ、元パスワードが判明する可能性が高くなります。
「アカウントロックで防げないか?」という疑問が生じますが、単純なアカウントロックでは防げません。たとえば、yamada、tanaka、sato…のIDが同じパスワードを使っていることが分かったとして、以下の表のように、IDとパスワードを共に変えながらパスワードを試す攻撃ができます。（今回の解読に使われた方法ではありません）。

ID	パスワード
yamda	password
tanaka	qwerty
sato	123456
...	...

※ yamada, tanaka, sato ... は同じパスワードを使っていることが分かっているとする

ここで、sato:123456が認証成功したとすると、satoだけでなく、yamada、tanakaもパスワードが123456であることが分かります。

この問題はハッシュ値でパスワードを保存する場合にも生じます。このため、ハッシュ値でパスワードを保存する場合はソルト(salt)を用いて、同じパスワードでもハッシュ値が別々になるようにするわけてすが、暗号化の場合はソルトではなく、初期化ベクトル(IV)とブロック暗号化モードいうものを用いて、暗号結果がばらばらになるようにします。詳しくは、暗号の参考書をご覧下さい。
以上のように、Adobeサイトのパスワード暗号化の方法には重大な問題があったことになります。

パスワードの「ヒント」が平文保存されていた

Adobeサイトには、過去、パスワードのヒントというものを保存することができたようです。現在のAdobeサイトにはこの機能は削除されていますが、Adobeサイトのヘルプやヘルプのアーカイブをあさると、「パスワードのヒント」という機能があったことが伺えます。

先の記事や参照元を見ると、このヒントは平文でデータベースに保存され、暗号化パスワードとともに漏えいしたようです。そして、ヒントにパスワードそのものを保存していたり、容易にパスワードが推測できる文が書かれていたりしたとのことです。下記は、その例を示すゴスニー氏のツイートです。

hints for WqflwJFYW3+PszVFZo1Ggg==: old company name, not adobe, before adobe, bought by adobe, it's macromedia, macromedia is the password
— Jeremi Gosney (@jmgosney) November 2, 2013

「旧社名、アドビでなく、アドビの前、アドビに買収された」というヒントから、パスワードはmacromediaだと推測しています。アドビに買収された会社は他にもありますが、このパスワードをつけている人は54,651人もいて全体の16位ですから、他のユーザのヒントや、「アドビの買収した会社の中でも有名な会社」、パスワードの長さ、などから確定としたのでしょう。暗号化したパスワードは可変長なので、1～7文字、8～15文字という単位（トリプルDESは64ビットブロック暗号なので）でおおよそのパスワード長が分かります。

結局パスワードの保存はどうすればよいか

Adobeサイトのパスワード保存方法の問題点（推測）について説明しました。現在パスワードの保存方法のベストプラクティスはソルト付きハッシュ + ストレッチングということになっいるので、それに従うのが無難かと思います。PHPの場合は、PHP5.5から password_hash という便利な関数が追加されたので、これでパスワードを保存するのがよいでしょう。同じ仕様の関数がpassword_compatライブラリ(PHP5.3.7以降)として公開されていますので、PHP5.5未満のPHPからも利用できます。

まとめ

• AdobeサイトのパスワードはトリプルDESで暗号化されていたが、実装の不備により平文パスワードが推測されてしまった
• 初期化ベクトルを使わないために同一パスワードが同一暗号文となる
• パスワードのヒントが暗号化されずに保存されていた
• そもそもパスワードのヒントという仕様がよくない（現在は削除されている）
• パスワードの保存にはソルト付きハッシュ + ストレッチングを使おう
• 暗号化の際は、適切なブロック暗号化モードと初期化ベクトルを用いること

参考:

• 本当は怖いパスワードの話
• Webアプリでパスワード保護はどこまでやればいいか
• いまさら聞けないパスワードの取り扱い方