イカれたCBORのデコード - PHP編

created: 2019/01/19 21:36

ということなので、暇を見つけて各種処理系のCBORのデコーダーの実装を眺めていこうと思います。

そもそもCBORって何?

JSONのように、数値、文字列、配列、マップのようなデータをバイト列にエンコード、
あるいは逆にデコードするためのデータフォーマットの仕様です。
大きくJSONと異なるのはその構造で、JSONの場合はエンコード後のそれはUTF-8の文字列となりますが、
CBORの場合ビット単位で意味が規定されたバイナリデータとなります。

何でデコーダーの実装を見るの?

最近WebAuthnという認証技術の仕様策定が進んでおり、CBORはその中で使用されています。
個人的にWebAuthnには流行ってもらいたく、是非パスワードを潰滅させてほしいところです。

が、正直CBORはすごくマイナーなデータフォーマットだと思っており、
そのデコーダーの実装にもあんまり人の目が入っておらず、バグが残ったままになってるんじゃないかなぁというのを気にしています。
自分はCBORのデコーダーを実装したこともあるので、探せば見つけられるかも、というのが動機になっています。

あるとすれば、どんな問題がありそうなの?

CBORは、まず保持している文字列の文字列長や配列の要素数を表す数バイトのバイト列が先にあり、
その後に実際のデータが続くような構造になっています。

例えば7A 00 00 00 03 41 42 43というバイト列をCBORとして解釈すると、
1バイト目は、後続のバイト列は文字列でその文字列長を後続の4バイトで表現すること、
次の4バイトで文字列長が3であること、残りの3バイトで文字列の内容が"ABC"であるこを示しています。
試しにRubyのCBORデコーダーでデコードしてみると、以下のようになります。

Cborb.decode "\x7A\x00\x00\x00\x03\x41\x42\x43"
=> "ABC"

(CBORで文字列長が3であることを表現するために4バイトも使うことは通常ありませんが)

さて、上記の例は正しいCBORなので、どのようなデコーダーでデコードする場合でも特に留意する点はありません。
が、デコード対象のCBORが常に仕様に準拠してくれているとは限りませんよね。
(WebAuthnのような、不特定多数のユーザーからCBORを受信しデコードするようなユースケースでは特にそうでしょう)

例えば9A FF FF FF FFのような、5バイトの不正なCBORについて考えてみましょう。
これは、1バイト目で後続のバイト列は配列で、その配列長を後続の4バイトで表現すること、
次の4バイトで配列長が4294967295であることを示しています。

このCBORは実際にはそれほどの大きな配列を表現してはいませんから、もちろん仕様に準拠してはいません。
デコーダーに対してはエラーや例外を発生させることが期待されますが、実装によっては「4294967295個の要素数の配列の開始」を表現された時点で、
何らかの初期化処理(例えばメモリ割り当て等)を行うような実装になってしまっている可能性は十分にあるでしょう。
その場合、CBOR自体は高々5バイトであるにも関わらず過剰にメモリを消費したり、
ループを回し始めてCPUのリソースを消費したりするハメになります。

(このようなCBORにも対処する必要性があることは、一応仕様にも記載されています: https://tools.ietf.org/html/rfc7049#section-8)

実際の実装

というわけで、実際に世にあるCBORのデコーダーは、そのようなCBORを安全に処理することができるのかどうかというのが、
この文章のモチベーションなわけです。
処理系ごとの実装についてはある程度 http://cbor.io/impls.html に列挙されているので、
このあたりから適当なものを見繕って見ていこうと思います。

PHP編

PHPのCBORのデコーダーは https://github.com/2tvenom/CBOREncode 1つだけが記載されており、
気分的に手を付けやすかったのでこれから見ていこうと思います。
composerにも対応しており、README通りに作業することで実際に動作させることも難しくなかったので、
実際に不正なCBORを入力して挙動を試してみることにします。
ちなみに環境はPHP 7.2.10-0ubuntu0.18.04.1です。ConoHaでメモリ512MBのVPSを借り、その上で実行しています。

一通りREADME通りにセットアップしたら以下のようなPHPのコードを書き、decode.phpとして保存した後実行してみます。

<?php
include("vendor/autoload.php");

$cbor = hex2bin("9A0FFFFFFF");
\CBOR\CBOREncoder::decode($cbor);

9A 0F FF FF FFは要素数が268435455の配列の開始を表現しているだけの不正なCBORです。
エラーや例外が発生することを期待しますが、どうでしょう?

$ time php decode.php

mmap() failed: [12] Cannot allocate memory
PHP Fatal error: Out of memory (allocated 1075843072) (tried to allocate 2147483656 bytes) in /root/php/vendor/2tvenom/cborencode/src/CBOR/CBOREncoder.php on line 162

real    0m31.700s
user    0m24.621s
sys 0m1.931s

(◞‸◟)

まぁ、最終的にはエラーになるのですが、その結果を得るまでに何十秒もかかってしまっています。
仮にこれがWebサーバーのプロセス上で実行されていると考えれば、この挙動は問題になる場合があるでしょう。

実装を見てみると、入力1バイトを取得しデータ型を判別するためのビット演算を行うのですが、
https://github.com/2tvenom/CBOREncode/blob/bfb28caca22ca7a5782177e7db8aa249d42e01ac/src/CBOR/CBOREncoder.php#L105
https://github.com/2tvenom/CBOREncode/blob/bfb28caca22ca7a5782177e7db8aa249d42e01ac/src/CBOR/CBOREncoder.php#L112
既に処理するべきCBORが無く、先頭1バイト取得のためのsubstrarray_shiftNULLを返していたとしても、
後続のビット演算でそれが数値の0に変換され、有効なCBORとして扱われてしまっているようです。
(CBORにおいて、001バイトは0を表す整数として正しい表現です)

実際、このデコーダーに空の文字列を入力すると、int(0)を返します。

php > include("vendor/autoload.php");
php > $cbor = "";
php > var_dump(\CBOR\CBOREncoder::decode($cbor));
int(0)

配列のデコード時には指定の回数だけループし、残りのバイト列を引数に同様のデコードを行いますが、
https://github.com/2tvenom/CBOREncode/blob/bfb28caca22ca7a5782177e7db8aa249d42e01ac/src/CBOR/CBOREncoder.php#L155
「空の文字列を与えても有効なCBORとして解釈しint(0)を返す」という挙動のために、
デコードするべきバイト列が残っていない状態でも処理が継続されてしまうようです。

終わりに

というわけで、http://cbor.io/impls.html に挙げられているような実装でも、全てに万全というわけではなさそうです。
また暇があったら、他の処理系の実装も見てみようと思います。
自分が使っているCBORの実装が気になる方は、文章内で触れたような不正なCBORを試しに入力してみるのもありかもしれませんね。