生涯未熟

生涯未熟

プログラミングをちょこちょこと。

Goのあるコードを発端とした衝撃の結末

はい、というわけで今回はGoのあるコードから紡がれるストーリーに纏わるお話です。

一体何が起こったのか？

発端はこのツイートでした。

むむー、一体なんじゃらほい？とGoの当該ソースコードを見たら一目で分かりました。

// Bug compatibility with C bcrypt implementations. We only encode 23 of
// the 24 bytes encrypted.
hsh := base64Encode(cipherData[:maxCryptedHashSize])
return hsh, nil

github.com

うおー！たしかに Bug compatibility with C bcrypt implementations. って書いてあるー！
"24バイトから23バイト分を暗号化するよ"ってな感じですね。

ここから旅は始まる

まずはこのコードが生まれたところから遡ってみました。
どうやらGo1以前に実装されたようで、ここらへんで実装された様子が伺えます。

Issue 4964078: code review 4964078: crypto/bcrypt: new package - Code Review

うーーーーーん、どうやら「bcrypt実装を書いてみたぜ！」って感じでガバっとPR投げられてますね・・・
ここのレビュー等で件の24バイトから23バイトへ切り詰めている話は特にされてない雰囲気を感じ取ったので、ソースコードから意図を読み取るのを早々に諦めました。

bcryptについて調べる

次に「bcryptの実装上そうなってるのだろうか？」と思い、bcrypt自体を調べることに。

bcrypt - Wikipedia

安心と信頼のwikipediaですね。
幸いにもアルゴリズムに基づいた実装例があったので読んでみると、

Function bcrypt
   Input:
      cost:     Number (4..31)                      log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
      salt:     array of Bytes (16 bytes)           random salt
      password: array of Bytes (1..72 bytes)        UTF-8 encoded password
   Output: 
      hash:     array of Bytes (24 bytes)

   //Initialize Blowfish state with expensive key setup algorithm
   state 
  
    
    {\displaystyle \gets }
  
\gets EksBlowfishSetup(cost, salt, password)   

   //Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
   ctext 
  
    
    {\displaystyle \gets }
  
\gets "OrpheanBeholderScryDoubt"  //24 bytes ==> three 64-bit blocks
   repeat (64)
      ctext 
  
    
    {\displaystyle \gets }
  
\gets EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode

   //24-byte ctext is resulting password hash
   return Concatenate(cost, salt, ctext)

うーん、どうやら24bytesを特に切り詰めずにそのまま使ってるな・・・🤔
wikiが段々信用できなくなってきたので、ここは愚直にbcryptの提唱者であるNiels Provos & David Mazieresによる文献を読んでみましょう。

www.usenix.org

1999年の資料らしいのですが、こういうのがネット上に残ってるというのは改めてありがたいことですね。
で、アルゴリズムのところとか読んでみたのですが、ここにも特に言及しているところは無く・・・残念。

「こりゃもうダメかもしれんね」って感じで、半ば諦めつつ広大なネットの海を漂うことにしました。

驚きの記事が

「bcrypt 23bytes 24bytes」とか思考停止状態で検索していると、以下のような記事を見つけました。

hackernoon.com

ここに来るまでにかなりの数の記事を読んでいて、これもきっと書いてないんだろうなと白目になりながら見てたら衝撃の記載が。

Issue 2: Using 23 byte instead of the full 24 byte hash

オッ

As stated before, nearly all bcrypt implementations output a 23 byte long hash. The bcrypt algorithm however generates a 24 byte password hash by encrypting three 8 byte blocks using a password-derived blowfish key. The original reference implementation however choose truncate the hash output, it is rumored the reason is to cap it to a more manageable length of 60 character limit (a strange reason if you ask me). The consensus seems to be that the issue of cutting a hash byte off is not a meaningful degradation in security, so it stays an oddity inherited from the reference implementation.

米語なのでGoogle翻訳様に頼ってみましょう。

前述のように、ほぼすべてのbcrypt実装では、23バイトの長さのハッシュが出力されます。 しかし、bcryptアルゴリズムは、パスワード由来のブローキーを使用して3つの8バイトブロックを暗号化することによって、24バイトのパスワードハッシュを生成します。 しかし、元のリファレンス実装では、ハッシュ出力を切り捨てることを選択します。理由は、それが60文字の制限（あなたが私に尋ねると奇妙な理由）の管理しやすい長さにキャップすることです。 合意は、ハッシュバイトを切り捨てることの問題はセキュリティの意味のある劣化ではないので、参照実装から継承された奇妙なままであると考えられます。

ん？？？？

24バイトのパスワードハッシュを生成します。 しかし、元のリファレンス実装では、ハッシュ出力を切り捨てることを選択します。

え？？？？？

理由は、それが60文字の制限（あなたが私に尋ねると奇妙な理由）の管理しやすい長さにキャップすることです。

マジで？？？？？？

ありがたいことにHacker Newsのリンクが貼ってあったので、そちらも一応見てみましょう。

A possible flaw in open-source bcrypt implementations | Hacker News

私はpy-bcryptの作者です。py-bcryptは、それを記述している論文の著者（ProvosとMazieres）のbcryptの元の参照実装の周りの薄いラッパーです。ハッシュの長さの差異は完全に無害です（衝突の可能性は2 ^ -186となります）、リファレンス実装に含まれていました。私はハッシュが少し切り捨てられている理由を正確にはわかりませんが、DavidやNielsは60文字のハッシュが扱いやすい長さだと思っていたと思います。

ほげ〜〜〜〜〜〜〜〜〜〜〜

そして、リファレンス実装を見てみると・・・

cvsweb.openbsd.org

encode_base64((u_int8_t *) encrypted + strlen(encrypted), ciphertext,
    4 * BCRYPT_BLOCKS - 1);

( д) ﾟ ﾟ

なんで・・・なんで-1しとるんや・・・
ということで無事、衝撃の結末に辿り着きました。

まとめ

どうやらGoだけではなく、PythonやJavaで実装されているbcryptライブラリも、殆どがこのリファレンス実装に従っているみたいですね。
一体どうしてこうなったのかは完全に謎ですが、なんとかハラオチできる結論に辿り着いたのでヨシとしましょう。

現場からは以上です。

[追記]