【CVE-2022-0778】OpenSSLの無限ループの脆弱性の原因解説！

この記事の内容

この記事では、主にOpenSSLで生じた脆弱性の原理について解説し、以下の内容を取扱います。

• OpenSSLのどの関数が原因で無限ループに陥ってしまったのか、それはどのような関数なのか
• どのような引数を渡せば無限ループに陥るのか
• なぜその無限ループに陥るのか

逆に、以下の内容は取り扱いません（実はまだわかってません）。

• 楕円曲線暗号ベースの証明書を渡すと無限ループになる可能性があると言っているが、具体的にどの証明書を、どのように渡せば無限ループになるのか

脆弱性の概要

この脆弱性は BN_mod_sqrt に特定の値を渡すと無限ループに陥ってしまうものになっています。

影響を受けるバージョンは OpenSSLのアドバイザリ によると、1.0.2, 1.1.1, 3.0 だそうです。

PoCは drago-96さんが上げており、手元で実行した結果、OpenSSL3.0 でビルド を利用したものにおいて、実際に無限ループをすることを確認しました。

修正方法はOpenSSLのアドバイザリによると 1.0.2 のものは 1.0.2zd, 1.1.1 のものは 1.1.1n、3.0 のものは 3.0.2 にバージョンを上げることで修正されるようです。実際に3.0.2でPoCを動かした結果、無限ループをせずに終了することが確認されました。以下がアドバイザリ原文です。

OpenSSL 1.0.2 users should upgrade to 1.0.2zd (premium support customers only)
OpenSSL 1.1.1 users should upgrade to 1.1.1n
OpenSSL 3.0 users should upgrade to 3.0.2

この関数は楕円曲線などの証明書をパースする際などに用いられているらしく、悪意のある証明書をパースすることで影響を受ける可能性があります(こちらはkurenaifはまだ未検証です。また余裕ができた際に調査します)。
その他以下のシチュエーションにおいて影響を受けるそうです。

• TLS clients consuming server certificates

• TLS servers consuming client certificates
• Hosting providers taking certificates or private keys from customers
• Certificate authorities parsing certification requests from subscribers
• Anything else which parses ASN.1 elliptic curve parameters

楕円曲線暗号がわからないよ！という人は、こちらの動画で解説しているのでぜひ見てみてください。

https://www.youtube.com/watch?v=jxmN8LqyTR4

このブログでは、BN_mod_sqrt 関数のみに焦点を当て、なぜ無限ループに陥るのかを解説したいと思います。

環境準備(手元で動かしたい人向け)

これからOpenSSLの環境を使って無限ループであったり、関数の挙動を確かめたりします。手元で動かしたい場合は opensslのgithub からリポジトリをcloneし、 ./Configure して make -jn して make install してください。

libcrypto.so にパスが通ってないよみたいなエラーが出る可能性があるので、その際はいい感じにパスを通してください。もし動かない場合はご連絡ください（ドキュメントを充実させます。）

BN_mod_sqrt関数とはなにか

この章ではBN_mod_sqrt関数は何を実装しているものなのか、内部ではどういったアルゴリズムを利用しているのかの解説をします。

BN_mod_sqrt関数はその関数名の通り、modの下でsqrt(平方根)を求める関数になっています。具体的には、以下のような挙動をします。

---

• 入力: $a$ と $p$
• 出力: $r$
  ここで、$r$は以下の式を満たす値

$$r^2 \equiv a \mod p$$

---

$r$ は $a$ の平方根っぽいものになっていますね。実際に以下のソースコードで実験してみましょう。

int main() {
    BN_CTX *ctx;
    ctx = BN_CTX_new();
    BIGNUM *res, *a, *p;
    res = BN_CTX_get(ctx);
    a = BN_CTX_get(ctx);
    p = BN_CTX_get(ctx);

    BN_dec2bn(&a, "25500");
    BN_dec2bn(&p, "65537");

    printf("p = %s\n", BN_bn2dec(p));
    printf("a = %s\n", BN_bn2dec(a));

    BIGNUM* check = BN_mod_sqrt(res, a, p, ctx);
    printf("%s\n", BN_bn2dec(res));

    return 0;
}

コンパイルし、実行すると以下のような結果を得ることができます。

$ gcc main.c -lcrypto
$ ./a.out
p = 65537
a = 25500
53192

このことから、$a=25500$, $p=65537$ の値を入れて計算をしてみると、$r=53192$ という結果が出てくることがわかりました。ではここで $r$ を 二乗してみると

>>> 53192**2 % 65537
25500

確かに 53192 は 25500 のsqrtっぽい値になってますね。

内部的には Tonelli-Shanks algorithm というアルゴリズムが実装されています。今回の脆弱性に関係のある実装内容に関してはこのあと解説していきます。ここではなぜこのアルゴリズムを用いて mod_sqrt を求めることができるのかは省略します。日本語の記事もたくさんあるので調べてください。

楕円曲線暗号では、

$$y^2 \equiv x^3 + ax + b (\mod p)$$

という式において、証明書の形式によっては $x$ から $y$ を求める必要があるケースがあり、その際に平方根が用いられるなどする可能性が高く、悪意のある値が挿入された場合はここで無限ループに陥る可能性があると思っています（推測です）

BN_mod_sqrtが無限ループする条件とその箇所

drago-96 さんのPoCによると、 $a=696$, $p=697$ の値を渡すことで、無限ループになるそうです。

ソースコード上において、無限ループする箇所は、こちらのwhile文になっております。 (コメントはkurenaifが追記)

// b=1 であれば終了する
if (BN_is_one(b)) {
    if (!BN_copy(ret, x))
        goto end;
    err = 0;
    goto vrfy;
}
i = 1;
if (!BN_mod_sqr(t, b, p, ctx)) // t = b*b % p
    goto end;
while (!BN_is_one(t)) { 
    // tが1じゃなかったらループをし続ける　
    // ここの中で無限ループするよ！
    i++;
    if (i == e) {
        // i == e となった場合は何かがおかしいので終了する。
        ERR_raise(ERR_LIB_BN, BN_R_NOT_A_SQUARE);
        goto end;
    }
    if (!BN_mod_mul(t, t, t, p, ctx)) // t = t*t % p の意味
        goto end; // 計算にエラーがあった場合はエラー終了（ここにはめったに来ない。）
}

このコードに、以下の6つの条件を満たした状態で突入すると無限ループに陥ります。（各変数の説明は追って行います。ソースコード中の変数と紐付いています。）

• 条件1: ループ突入時に$e = 1$ (iは2以上になるので、eが1であればループを終了する条件に当てはまらない。)
• 条件2: $b^2 \not\equiv 1 \mod p$ (この条件を満たさないとループに突入しない)
• 条件3: $b^2 \mod p, b^4 \mod p, b^8 \mod p, b^{16} \mod p \cdots$ と計算していっても結果が 1 にならない。 (この条件を満たさないと、外側のwhileを抜けてしまう。)
• 条件4: $b \not\equiv 1 \mod p$ (この条件を満たさないと goto endをしてしまう)
• 条件5: 最初にループに到達したとき、$e \geq 3$ (小さな$e$だと別のアルゴリズムがあたってしまうため。e=1の場合, e=2の場合)
• 条件6: $y$ を2から22までインクリメントさせていったときに、 Kronecker symbol が一度も $(y|p) = 0$ にならずに $(y|p) = -1$ となる $y$ が存在している。（一度-1になればその後0があってもOK） (存在しない場合、ここで落ちる)

この6つの条件を満たすために、どのような $a$ と $p$ にどのような値を渡せばよいか整理していきましょう。

条件1と条件5を同時に成立させる。

条件1: ループ突入時に$e = 1$
条件5: 最初にループに到達したとき、$e \geq 3$

条件1では $e=1$ を要求しているのに対し、条件5では$e \geq 3$ を要求しています。これでは矛盾してしまうので、解決しましょう。

実はソースコードを見てみると、$e$はここで再代入されています。そしてここは、while(1) のループの中なので、もう一周させることで $e=1$ の条件を実現することができます。$i$ の 初期値は 1 であることから、条件1は以下のように言い換えられます。

条件1: 1周目の時点で、$b^2 \equiv 1 \mod p$。

ここで、条件1と条件4を合わせて考えてみると、1週目の時点では、$b\neq1$ を満たし、さらに $b^2 =1$ を満たす必要がある事がわかります。このような $b$ は $-1$ しかありません。法 $p$ の下では $-1$ は $p-1$ で表すことができます。

条件1: 1周目の時点で、$b \equiv -1 \mod p$。

$b=-1$ を満たすためには、どのような $a$ と $p$ 入力をすればよいかを考えていきましょう。 $b$ はソースコード中で、以下のように求められています。

$$\begin{aligned} x &= a^{(q-1)/2} \\ b &= a x^2 \end{aligned}$$

ゲェッ！複雑な式だ！と思う人がいるかも知れませんが、ここで冷静に $a=-1$ を代入してみてください。 $x=1 \mathrm{\ or\ } -1$ になるのですがその後 $x^2$ を求めているので、 必ず $b=-1$ になります。なので、さらに条件1を書き換えると、以下のようになります。

条件1: $a = p-1$

簡単になりました。

条件5を成立させる

条件5: 最初にループに到達したとき、$e \geq 3$

$e$の初期値は3以上でなければなりません。ここで、$e$の生成方法を知る必要があります。$e$ は $p$ を入力として、以下のようなアルゴリズムで生成されています。

// 入力: p
// 出力: eとq

x = (p-1)
e = 0
while(x%2==0){
 x/=2
 e++ // 2で割った回数をカウント
}
q = a // 余ったものはq

ここで、$p$, $q$, $e$ の関係は以下のようになります。

$$p-1 = 2^e q$$

このことから、ある任意の0以上の奇数 $n$ を入力として、 $e$ は $3$ 以上であれば良いので、

$$p = 2^3 n + 1 = 8n + 1$$

とすると成立させることが可能です。したがって、条件5は以下のように言い換えることができます。

条件5: $p = 8n + 1$ で求められている。(nは奇数でなければならない。)

条件3を成立させる

条件3: $b^2 \mod p, b^4 \mod p, b^6 \mod p \cdots$ と計算していっても結果が 1 にならない。

実は、ここのロジックは正しく Tonelli-Shanks algorithm を利用している場合、必ず1になってしまいます。この条件を成立させないためには、Tonelli-Shanks algorithm では $p$ に 素数が求められているので、その前提条件を壊してあげる必要があります。結論を言うと、こうすると良いです。

条件3: $p$ は素数ではない（ただしこの条件を満たしても確率的に失敗することもある）

note: $p$が素数だといけないのか？

なぜ素数だと必ず1になってしまうのかというと、$p$が素数の場合、フェルマーの小定理より、以下が成立します。

$$a^{p-1} \equiv 1 \mod p$$

ここで、$b$を思い出してみると、

$$\begin{aligned} x &= a^{(q-1)/2} \\ b &= a x^2 \end{aligned}$$

でした。($q$は2で割り続けた残りのやつです)つまり、

$$b = a (a^{(q-1)/2})^2 = a^{q-1+1} = a^q$$

になります。ここで、$q$の関係式を思い出してみると、

$$p-1 = 2^e q$$

でした。つまり、$a^q$を二乗し続けることにより、

$$a^q, a^{2q}, a^{4q}, \cdots, a^{2^e q}$$

となり、最終的に

$$a^{2^e q} \equiv a^{p-1} \equiv 1 \mod p$$

が成立してしまいます。二週目以降もうまく1になるようになっています。

条件4を成立させつつ、条件2も成立させる

条件2: $b^2 \not\equiv 1 \mod p$
条件4: $b \not\equiv 1 \mod p$

二週させるという話だったので、条件2は二周目に成立していれば良いです。
そして、条件1を思い出してみると、以下のように書き直したのでした。

条件1: 1周目の時点で、$b \equiv -1 \mod p$。
条件1: $a = p-1$

つまり、$a$の値も決まっていて、その結果、$b$ の値も一周目では $-1$ であることは必要条件となってしまっています。

そのような $b$ を与えた場合、二週目の $b$ はどうなるのでしょうか？更新処理はこちらで行っています。最終的に得られる$b$ が 次の週の $b$ となります。

        /* t := y^2^(e - i - 1) */
        if (!BN_copy(t, y))
            goto end;
        for (j = e - i - 1; j > 0; j--) {
            if (!BN_mod_sqr(t, t, p, ctx))
                goto end;
        }
	
        if (!BN_mod_mul(y, t, t, p, ctx)) // y = t*t % p
            goto end;
        if (!BN_mod_mul(x, x, t, p, ctx)) // x = x*t % p
            goto end;
        if (!BN_mod_mul(b, b, y, p, ctx)) // b = b*y % p
            goto end;
        e = i;

ここで $y$ は条件6を満たすランダムな値です。
この値はほおっておいても勝手に $b$ が 1 や -1 になることはあまりなかったので、無視して大丈夫です。

条件6を成立させる

条件6: $y$ を2から22までインクリメントさせていったときに、 Kronecker symbol が一度も $(y|p) = 0$ にならず、なおかつ $(y|p) = -1$ となる $y$ が存在している。

これは kronecker sybmol の計算方法を調べて実装しチェックするだけです。

条件を再整理する

以上条件を再整理すると、このようになります。

条件1: $a = p-1$
条件3: $p$ は素数ではない（ただしこの条件を満たしても確率的に失敗することもある）
条件5: $p = 8n + 1$ で求められている。(nは奇数でなければならない。)
条件6: 条件6: $y$ を2から22までインクリメントさせていったときに、 Kronecker symbol が一度も $(y|p) = 0$ にならずに $(y|p) = -1$ となる $y$ が存在している。（一度-1になればその後0があってもOK）

$a$と$p$に関する条件だけになりました。

ではPoCが刺さった $a=696$, $p=697$ はこの条件を満たしているのでしょうか？

条件1: 明らかに成立している。
条件2: 697 = 17 * 41
条件5: 697 = 8*87 + 1
条件6: (2|697) = 1, (3|697) = 1, (4|697) = 1, (5|697) = -1 (https://www.wolframalpha.com/input?i=Jacobi+symbol(5%2F697)&lang=ja)

満たしていそうです。ではこのパラメータを満たす別の値を生成してみましょう。以下がそれっぽい数を生成するコードになっています。

from Crypto.Util.number import isPrime
from sympy.ntheory import jacobi_symbol
import random
import sys

# param1 is odd
def check(param1):
    assert param1 % 2 == 1

    # 条件5
    p = (2**3 * param1) + 1
    # 条件3
    if isPrime(p):
        return False, "error 3"
    q = param1
    a = p-1

    isOk = False
    for y in range(2,22):
        # 条件6
        res = jacobi_symbol(y, p)
        if res == 0:
            return False, "error 6"
        if res == -1:
            isOk = True
            break

    if not isOk:
        return False, "error 6"

    return True, (a,p)

for i in range(100):
    ok,res = check(i*2+1) // 条件5 の nは素数
    if ok:
        print(res)

このような結果になりました。

(184, 185)
(216, 217)
(328, 329)
(376, 377)
(424, 425)
(472, 473)
(552, 553)
(648, 649)
(664, 665)
(696, 697)
(712, 713)
(792, 793)
(904, 905)
(1000, 1001)
(1080, 1081)
(1144, 1145)
(1176, 1177)
(1240, 1241)
(1272, 1273)
(1336, 1337)
(1384, 1385)
(1416, 1417)
(1512, 1513)
(1528, 1529)
(1576, 1577)

適当な値で検証してみます。

#include <openssl/bn.h>


int main() {
    BN_CTX *ctx;
    ctx = BN_CTX_new();
    BIGNUM *res, *a, *p;
    res = BN_CTX_get(ctx);
    a = BN_CTX_get(ctx);
    p = BN_CTX_get(ctx);

    BN_dec2bn(&a, "904");
    BN_dec2bn(&p, "905");

    printf("p = %s\n", BN_bn2dec(p));
    printf("a = %s\n", BN_bn2dec(a));

    BIGNUM* check = BN_mod_sqrt(res, a, p, ctx);
    printf("%s\n", BN_bn2dec(res));

    return 0;
}

無事に無限ループになりました。

修正内容

こちらのコミット で修正されています。 $i=e$ となったときに終了するのではなく、 $i<e$ で終了するようになっており、$e=1, i=2$ となっても終了できるようになっていますね。

まとめ

このブログでは BN_mod_sqrt が無限ループになる条件を一つ求め、無限ループに陥るパラメータを作成するスクリプトを作成しました。攻撃原理理解に役に立てば幸いです。

ここまで見ていただきありがとうございます。この記事はこの放送で生配信しながら執筆したものになります。是非興味があれば見てみてください。

https://www.youtube.com/watch?v=FUMeoYncAd8

https://www.youtube.com/watch?v=R2YiasPDZnY&feature=youtu.be