The 72nd character of BCrypt is NULL character? / PHP: password_hash()の72文字目の正体

　本稿は昨年からずっと下書き状態で、なかなか検証の手が回らず、もどかしい思いをしていました。あまりあたためてても仕方がないので、現状のまま投稿に踏み切りました。誤りや盛大な勘違い等があるかと思われますが、ご遠慮なくご指摘願えればと存じます。

f:id:reinforchu:20190514000517j:plain

●概要

　みなさまお久しぶりです。いつもの枕詞ですが、私の独自調査の結果と見解を示すものですので、ある一つの考え方として受け止めていただければと存じます。内容の誤りや不備、追加情報がありましたら、是非コメントやTwitterやメール等にお寄せください。

　今回は、PHPのパスワードハッシュを作成するpassword_hash()とpassword_verify()の72文字制限について話題にします。PASSWORD_BCRYPTアルゴリズムの72文字制限は過去に言及されていますが、掘り下げて調べてみると、どうやら真実は少し違うようでした。厳密には、72文字で切り詰められるのは間違いないですが、その仕様に誤解がありました。

●password_hashの72文字制限

　72文字制限についてはPHPのリファレンスに記載されているように、周知の事実と思われますので特段言及しませんが、簡単に解説しましょう。password_hashのPHPのリファレンスによると、このような重要な一文が記載されています。

PASSWORD_BCRYPT をアルゴリズムに指定すると、 password が最大 72 文字までに切り詰められます。

PHP: password_hash - Manual

　この書き方では、PASSWORD_BCRYPT が悪者のように読み取れますが、PASSWORD_DEFAULT と PASSWORD_BCRYPT どちらを指定しても、記事執筆時点は同じBCryptですので差はありません。つまり、上記の警告文はpassword_hash()を使用する限りは、この制約の影響を受けます。

　BCrypt(Blowfish暗号)の詳細に関してはここでは解説しませんが、BCryptはパスワード文字列に72文字までの制限があり、より長い文字列(73文字目以降)は切り詰められる挙動をします。つまり、73文字以上のパスワードハッシュを求めた結果は、72文字分までのハッシュ値となるため、password_verify()で検証した際に、困ったことが起こります。その挙動を下記のコードで検証してみましょう。

◆検証コード 01_hash.php

<?php
$password_hash = str_repeat('a',72);
$password_input = str_repeat('a',72) . "badpassword";
$hash = password_hash($password_hash, PASSWORD_DEFAULT);
$ret = password_verify($password_input, $hash);
var_dump($ret); // output: bool(true)

　outputはbool(true)となります。期待される結果はfalseを返すべきです。なぜなら、文字列「aaa...(aが72回続く)」と後方に任意の文字列を結合した「aaa...aabadpassword」は異なる文字列ですから、パスワードの検証においては一致すべきではないでしょう。しかし、72文字制約のため後方の「badpassword」の部分が切り詰められるため、文字列A「aaa...(aが72回続く)」と文字列B「aaa...(aが72回続く)」の比較となり、その結果同等であるため、trueを返却します。

●72文字目の正体と興味深いコード

　追記(5/14 AM)：下記はコードと主張に誤りがある指摘があり、お調べ中です

　さて本題となりますが、この72文字制限に関して非常に興味深いコードを発見しました。mit.eduで公開されているcrypt-blowfish.cのコードです。次の部分を着目してください。

crypt-blowfish.c

/* strlen() returns a size_t, but the function calls

* below result in implicit casts to a narrower integer

* type, so cap key_len at the actual maximum supported

* length here to avoid integer wraparound */

key_len = strlen(key);

if (key_len > 72)

key_len = 72;

key_len++; /* include the NUL */

　要するに最後の文字はNULL文字であることを意味していると、私は解釈しました。つまり、72文字目はNULL文字が必ず挿入されるものではないでしょうか。

※ソースコード

bcrypt.c,v 1.29 2014/02/24 19:45:43

http://web.mit.edu/freebsd/head/secure/lib/libcrypt/crypt-blowfish.c

　追記(5/14 PM)：これはコード(実装)が違うのかも。

　Twitter から「72文字を詰めてNULL文字を結合させた73文字であるコードです。」という指摘を受け、頭の整理をし直しました。

　結果的には、提示できるコードは下記であまり変わりはありません。

crypt-blowfish.c

/* We dont want the base64 salt but the raw data */
    decode_base64(csalt, BCRYPT_MAXSALT, (const u_int8_t *) salt);
    salt_len = BCRYPT_MAXSALT;
    if (minr <= 'a')
        key_len = (u_int8_t)(strlen(key) + (minr >= 'a' ? 1 : 0));
    else {
        /* strlen() returns a size_t, but the function calls
         * below result in implicit casts to a narrower integer
         * type, so cap key_len at the actual maximum supported
         * length here to avoid integer wraparound */
        key_len = strlen(key);
        if (key_len > 72)
            key_len = 72;
        key_len++; /* include the NUL */
    }

http://web.mit.edu/freebsd/head/secure/lib/libcrypt/crypt-blowfish.c

　問題と考えたのが、昨今のBlowfishの原型と言うと語弊があるかもしれませんが、Original paperの仕様によると次の通りです。また、派生も複数あるので、全てを追いきれてませんが、USENIXのペーパーを示します。(下部に出典元を記載しています。)

Eksblowfish Algorithm

Finally, the key argument is a secret encryption key, which can be a user-chosen password of up to 56 bytes (including a terminating zero byte when the key is an ASCII string).

　その他にも72文字に起因する仕様の記述がありましたが、まだ理解が追いついておらず言及できませんでしたが、終端文字(NULL文字)を結合した72文字が、いわゆる作者が想定した“72文字”のkeyなのではないかと考えております。つまり、論文(仕様)と実装は乖離していて、key_lenが73というのは誤った実装ではないのでしょうか。

●パスワードの文字数制限は71文字であるべきか

　ここで一つの疑問が出てきます。71文字 + ヌルバイト文字 = 72文字 が本来の仕様であるなら、その仕様に合わせた実装を推奨されるのではないでしょうか。同時に、結局のところ72文字目で切り詰められるため、ヌルバイト文字が切り捨てられようと、終端文字として含まれようと、パスワードハッシュとして期待した結果を返すので72文字でも良いではないか、とも思えます。主観的ですが、私なら暗黙的に切り詰めるような動作をさせないような実装をします。

●怪談

　もし、終端にマルチバイト文字が入った場合、問答無用で切り詰められるので……

●出典

　本稿にあたり、閲覧および参考にしたドキュメントやペーパーです。

www.usenix.org

www.schneier.com

●参考情報

　私の疑問・違和感に近しいDiscussionがありました。こちらもご参照ください。

security.stackexchange.com