OktaのAD/LDAP DelAuthでユーザー名が52文字以上だとパスワード不要で認証できてしまう脆弱性があったそうです。
Oktaはある程度背景を説明してくれてます。
キャッシュ キーの生成には Bcrypt アルゴリズムが使用され、userId + username + password の組み合わせ文字列がハッシュ化されます。特定の状況下では、これにより、以前の成功した認証の保存されたキャッシュ キーを持つユーザー名のみを提供することで、ユーザーが認証できる可能性があります。
注意:この脆弱性の前提条件は、ユーザーに対してキャッシュ キーが生成されるたびに、ユーザー名が 52 文字以上である必要があることです。
https://trust.okta.com/security-advisories/okta-ad-ldap-delegated-authentication-username/
この問題は bcrypt というハッシュアルゴリズムの利用方法が原因でした。この記事ではどのように bcrypt が振る舞うのかを解説します。後半では bcrypt 考案者の論文から72文字になった理由や、時代背景の考察を行います。なおあちこちで chatGPT, Google Translate を使って書いてます。
bcrypt とは？
bcryptは 1999年に発表 され、今なお現役のパスワードハッシュ化アルゴリズムです。パスワードごとにソルトを変えれたり、計算コストを調整できるなど現在求められるセキュリティ、実装基準を満たしているため広く利用されています。もちろんさらにセキュアな Argon2 などのハッシュアルゴリズムはありますが、bcrypt 自体が危険とはされていません。OpenBSDに初めて採用され、php の password_hash() などでも用いられているそうです(by chatGPT)
bcrypt の 72 bytes 制限とは？
bcrypt では、入力できる文字数が 72 bytes に制限されています。これは、bcryptが内部で72バイトに文字列をトリム（切り詰め）して処理するためです。72 bytes を超える部分は無視されるため、たとえば 73 bytes 以上のパスワードでも、最初の 72 bytes が一致していれば同じハッシュが生成されます。
72文字と73文字で同じハッシュを生成する例 - saltが同じver
saltが同じなら、72, 73文字の異なる入力に対して全く同じハッシュが出てきます。
python bcrypt の実装だとこうです。hashpw() の1行目でガッツリ切り取られてます。
fn hashpw<'p>(
...
let password = &password[..password.len().min(72)]; <------
https://github.com/pyca/bcrypt/blob/main/src/_bcrypt/src/lib.rs#L80
↓ 実際に試してみました。72/73文字で同じハッシュができました。
import bcrypt
salt = bcrypt.gensalt() # 同じsaltを使ってみます
pw_72_chars = "1234567890" * 7 + "12" # 72文字のパスワード
hashed_72 = bcrypt.hashpw(pw_72_chars.encode('utf-8'), salt) # ハッシュにする
pw_73_chars = "1234567890" * 7 + "123" # 73文字のパスワード
hashed_73 = bcrypt.hashpw(pw_73_chars.encode('utf-8'), salt) # ハッシュにする
print(hashed_72) # b'$2b$12$yZzgLmsvOnJa2ZlxbRVnJOTSkbn9U3a2YVu7fY6MnZ6IuEX0W6oBa'
print(hashed_73) # b'$2b$12$yZzgLmsvOnJa2ZlxbRVnJOTSkbn9U3a2YVu7fY6MnZ6IuEX0W6oBa'
print(hashed_72 == hashed_73) # True
72文字と73文字で同じハッシュを生成する例 - saltが違うver
saltが異なるので、ハッシュ文字列は異なるものが出力されます。しかし、ハッシュの中身を bcrypt.checkpw() で比較すると同じものとして認識されます。72文字までしか比較されないので、同じことです。
import bcrypt
pw_72_chars = "1234567890" * 7 + "12"
hashed_72 = bcrypt.hashpw(pw_72_chars.encode('utf-8'), bcrypt.gensalt())
pw_73_chars = "1234567890" * 7 + "123"
hashed_73 = bcrypt.hashpw(pw_73_chars.encode('utf-8'), bcrypt.gensalt())
print(hashed_72)
print(hashed_73)
print("strings are the same?", hashed_72 == hashed_73) # False - 文字列としては異なる
print("hashes are the same?", bcrypt.checkpw(pw_73_chars.encode('utf-8'), hashed_72)) # True - ハッシュとしては同じもの
result
b'$2b$12$p0cHAFafVpfs4LjpkoK..eJDHNx9esJp7NUcKGQ.nJyrqARs/qLJC'
b'$2b$12$.mBbCMFqjiMa/WIud/663.sBpe1vUobH/x0UoNKO2gDYQj1dEIPhK'
strings are the same? False
hashes are the same? True
Oktaの実装をシミュレートしてみる
hash_user_data() は user_id, user_name, password を繋げてハッシュにします。前方にあるuser_id, user_nameが72文字を超えると password はハッシュに対して何の影響も及ぼさなくなります。
<user_id(10文字)><user_name(62文字)><password(1文字) で試してみます。
def hash_user_data(user_id, user_name, password):
# ユーザーID、ユーザー名、パスワードを結合してUTF-8でエンコード
combined = f"{user_id}{user_name}{password}".encode('utf-8')
# bcryptでハッシュ化
hashed = bcrypt.hashpw(combined, bcrypt.gensalt())
return hashed
user_id = "1234567890" # 10 chars
user_name = "1234567890" * 6 + "12" # 62 chars
password1 = "1"
password2 = "2"
# ハッシュ化
hashed1 = hash_user_data(user_id, user_name, password1)
hashed2 = hash_user_data(user_id, user_name, password2)
print("Hashed data:", hashed1)
print("Hashed data:", hashed2)
print("strings are the same?", hashed1 == hashed2)
print("hashes are the same?", bcrypt.checkpw(f"{user_id}{user_name}{password2}".encode('utf-8'), hashed1))
result
当然ですがpasswordが異なった入力でも、同じハッシュとして判定されました。このような実装によりキャッシュヒットした場合は認証がバイパスされたものと思われます。
Hashed data: b'$2b$12$htt1.xGR3W46dAOxHvIvo.UPXI5PyfrNp.vGRywT1A4w0HLR7ctZ.'
Hashed data: b'$2b$12$0fhT.zfkKbasX5XKvF1BleTDFf8PVN3dwNL/.4bV1sHXsx/RzXg3a'
strings are the same? False
hashes are the same? True
ただ、件のリリースが "52" 文字以上になってる理由はよくわかりませんでした。user id の最低長は 20文字以下だと思うので(72-52=20) 、もしかするとuser idは最低20文字にパディングされる、またはbcryptに入れる前に50数文字で trim されていたのかもしれません。
Deep Dive
bcrypt 考案時の時代背景
bcrypt 考案者の Niels Provos and David Mazières の論文 A Future-Adaptable Password Scheme では、DES, MD5 と bcrypt の比較の中に当時の思想を垣間見ることができます。
現在では、パスワード空間の制限、ソルト空間の小ささ、実行コストの一定性という 3 つの重大な制限があることがわかっています。これに対し、bcryptでは、より長いパスワードが許可され、常に一意となるのに十分な大きさのソルトがあり、コストも適応可能です。したがって、これらの制限は bcryptには適用されません。(Provos & Mazières, 1999)
https://www.usenix.org/legacy/publications/library/proceedings/usenix99/provos/provos_html/node9.html#SECTION00061100000000000000
bcryptは当時よく使われていたDESよりも長い文字列をハッシュにできたようです。
MD5 cryptではパスワードのサイズに実質的に制限がありませんが、 bcryptでは最大 55 バイトです。ただし、 これはbcryptの重大な制限とは考えていません。ユーザーがこのような長いパスワードを選択する可能性は低いだけでなく、選択した場合、 MD5 cryptの 128 ビットの出力サイズがセキュリティの制限要因になります。ブルート フォース攻撃者は、実際のパスワードを推測するよりも、ユーザーのパスワードと同じ値にハッシュされる短い文字列を見つける方が簡単です。最後に、DES cryptと同様に、 MD5 crypt には固定コストがあります。(Provos & Mazières, 1999)
https://www.usenix.org/legacy/publications/library/proceedings/usenix99/provos/provos_html/node10.html#SECTION00061200000000000000
bcrypt は MD5 より短い文字列しかハッシュにできませんでしたが、そもそも長い文字列に使われることを想定していませんでした。それよりも性能を重視していたことが読み取れます。さらに入力値が小さいにも関わらず MD5 より長い 192 bit を出力するため、MD5 よりセキュアだとしています。
ところで、この論文では最大 55 bytes と書いてありますね？ 72 bytes じゃなかったっけ？
72文字になった理由
python bcrypt の source code を見るとヒントがありました。
#[pyo3::pyfunction]
fn hashpw<'p>(
py: pyo3::Python<'p>,
password: &[u8],
salt: &[u8],
) -> pyo3::PyResult<pyo3::Bound<'p, pyo3::types::PyBytes>> {
// bcrypt originally suffered from a wraparound bug:
// http://www.openwall.com/lists/oss-security/2012/01/02/4
// This bug was corrected in the OpenBSD source by truncating inputs to 72
// bytes on the updated prefix $2b$, but leaving $2a$ unchanged for
// compatibility. However, pyca/bcrypt 2.0.0 *did* correctly truncate inputs
// on $2a$, so we do it here to preserve compatibility with 2.0.0
let password = &password[..password.len().min(72)];
https://github.com/pyca/bcrypt/blob/main/src/_bcrypt/src/lib.rs#L67C1-L81C1
翻訳
bcryptには元々オーバーフローによるバグがありました：
http://www.openwall.com/lists/oss-security/2012/01/02/4
このバグは、OpenBSDソースコードにおいて、入力を72バイトに切り詰める
ことで修正されました。修正は新しい接頭辞$2b$で行われましたが、
後方互換性のために$2a$はそのまま残されています。
しかし、pyca/bcrypt 2.0.0 では $2a$ に対しても正しく入力を切り詰めていたため、
ここでも2.0.0との互換性を維持するために同様に処理を行います。
72文字の切り詰めは互換性 + 性能維持 のためだった
手抜きchatGPTです。
簡単にいうと、bcryptが72バイトに制限している主な理由は、性能や効率性を向上させるためです。
- Blowfish暗号の特性
bcryptはBlowfish暗号に基づいて設計されており、Blowfishのキー構造には長さ制限があります。具体的には、Blowfishのキーは最大で448ビット（56バイト）までしかサポートしていません。bcryptは、このBlowfishを使用しているため、最初から長い入力データを扱うのが得意ではありませんでした。
これは論文の 55 bytes 制限とは直接関係ないようですが、blowfishの不得意な点がbcryptを短い文字列に制限したと言っても良さそうです。bcryptを長い文字列に対応させることもできますが、そうしなかった理由は性能でしょう。
bcryptが72バイトに制限している主な理由は、性能や効率性を向上させるためです。具体的には、以下のような理由があります：
計算効率: bcryptは内部でBlowfish暗号を使用しており、入力サイズを72バイトに制限することで、効率的にハッシュ計算がされ全体のパフォーマンスが向上します。
メモリ使用量の管理: 大きな入力を扱うとメモリ使用量が増加し、システムリソースに対する負担が大きくなります。72バイトに制限することで、一定のメモリ使用量に収束させ、より安定した動作を実現しています。
セキュリティのバランス: 長すぎるパスワードは、ハッシュ衝突のリスクを高める可能性があります。72バイトに制限することで、セキュリティとパフォーマンスのバランスを取っているとも考えられます。
これは納得ですね。
- 互換性維持
bcryptが広く利用されるようになると、古いシステムや実装と互換性を保つ必要が生じました。そのため、72バイトの制限が公式仕様の一部として確立され、現在でも多くのbcrypt実装においてこの制限が保持されています。この互換性を維持することで、異なるシステム間でbcryptハッシュの移行がスムーズに行えるようになっています。
異なるプログラミング言語間でもハッシュを維持できるのはめちゃくちゃ魅力的ですね。それだと、確かに変更を加えるのは難しそう。
72 bytes 制限への対策
一般的な対策としてはそもそも 72 bytes 以上の文字列が入らない実装をすることが考えられます。まず文字数のvalidationを追加する。user id + password が必ず 72 bytes 以下であればそうできるでしょう。Oktaが username までハッシュの対象にしていたのは何か理由があると思います。（例えばuser idを変更できる機能があるなど) 今回の例であれば、passwordを先頭にして連結するだけでも問題を防げました。 password -> user id -> user name にしていればよかった。悔やまれる。
個人的には、bcyprt libraryが73文字以上をエラーにする実装をしてくれればと感じます。アルゴリズム自体の定義を尊重することも、1999年当時の状況も、互換性も理解できますが、今となってはこういう問題が起きますし各ライブラリ独自の判断でエラーにする & エラーを出さないオプションを用意してもいいのではと感じます。
感想
bcryptは安全なハッシュ関数ですが、72文字までという制限を知らなければ容易に起こってしまうバグです。bcrypt libraryが何のwarningも出さないので事前知識がなければ防げません。三日後に私も同じことをしていそうです。
今回の脆弱性については、あくまでアクティブな認証キャッシュがなければ成功しないのでどれくらい被害があったのかは想像し難いです。52文字のユーザ名という時点でなかなかの確率が必要ですし・・何とも言えませんね。
大学院でハッシュ関数の授業をやったばかりだったので、めちゃくちゃタイムリーに勉強できてラッキーでした。特にこの論文のconclusionにはあらゆるハッシュ関数の将来についての一文があり興味深かったです。
ユーザーが選択するパスワードの長さとエントロピーは一定です。対照的に、ハードウェアは常に改良され攻撃者の計算能力は増大しています。その結果、パスワード方式は、オフラインのパスワード推測攻撃に耐えられなくなっています。
この論文では、「ユーザーが選択したパスワードと同じくらい優れた」パスワード スキームの概念を形式化し、そのようなスキームの計算コストはハードウェアの速度とともに必然的に増加することを示します(Provos & Mazières, 1999)
これはつまり、時と共にハッシュ計算を複雑にしていく必要があるという警鐘です。ハッシュ関数の良し悪しは性能や衝突確率で判断されます。bcryptが現在どれくらいの性能、安全性を持っているのか私は知りませんが、もしかしたら長い命ではないのかもしれないなと感じましたとさ。
おしまい。
Reference
Provos, N., & Mazières, D. (1999, June). A future-adaptable password scheme. In 1999 USENIX Annual Technical Conference (USENIX ATC 99). USENIX Association. https://www.usenix.org/conference/1999-usenix-annual-technical-conference/future-adaptable-password-scheme
追伸
著者はセキュリティの専門家ではありません。言葉の悪い苦情は優しい説明ブログに変換してご発信ください