【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
楕円曲線暗号がわからないよ！という人は、こちらの動画で解説しているのでぜひ見てみてください。
このブログでは、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
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
このことから、
>>> 53192**2 % 65537
25500
確かに 53192 は 25500 のsqrtっぽい値になってますね。
内部的には Tonelli-Shanks algorithm というアルゴリズムが実装されています。今回の脆弱性に関係のある実装内容に関してはこのあと解説していきます。ここではなぜこのアルゴリズムを用いて mod_sqrt を求めることができるのかは省略します。日本語の記事もたくさんあるので調べてください。
楕円曲線暗号では、
という式において、証明書の形式によっては
BN_mod_sqrtが無限ループする条件とその箇所
drago-96 さんのPoCによると、
ソースコード上において、無限ループする箇所は、こちらの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 - 条件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 - 条件4:
b \not\equiv 1 \mod p - 条件5: 最初にループに到達したとき、
e \geq 3 e - 条件6:
y (y|p) = 0 (y|p) = -1 y
この6つの条件を満たすために、どのような
条件1と条件5を同時に成立させる。
条件1: ループ突入時に
e = 1
条件5: 最初にループに到達したとき、e \geq 3
条件1では
実はソースコードを見てみると、while(1) のループの中なので、もう一周させることで
条件1: 1周目の時点で、
ここで、条件1と条件4を合わせて考えてみると、1週目の時点では、
条件1: 1周目の時点で、
ゲェッ！複雑な式だ！と思う人がいるかも知れませんが、ここで冷静に
条件1:
簡単になりました。
条件5を成立させる
条件5: 最初にループに到達したとき、
e \geq 3
// 入力: p
// 出力: eとq
x = (p-1)
e = 0
while(x%2==0){
x/=2
e++ // 2で割った回数をカウント
}
q = a // 余ったものはq
ここで、
このことから、ある任意の0以上の奇数
とすると成立させることが可能です。したがって、条件5は以下のように言い換えることができます。
条件5:
条件3を成立させる
条件3:
と計算していっても結果が 1 にならない。 b^2 \mod p, b^4 \mod p, b^6 \mod p \cdots
実は、ここのロジックは正しく Tonelli-Shanks algorithm を利用している場合、必ず1になってしまいます。この条件を成立させないためには、Tonelli-Shanks algorithm では
条件3:
note: p
なぜ素数だと必ず1になってしまうのかというと、
ここで、
でした。(
になります。ここで、
でした。つまり、
となり、最終的に
が成立してしまいます。二週目以降もうまく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
つまり、
そのような
/* 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;
ここで
この値はほおっておいても勝手に
条件6を成立させる
条件6:
を2から22までインクリメントさせていったときに、 Kronecker symbol が一度も y にならず、なおかつ (y|p) = 0 となる (y|p) = -1 が存在している。 y
これは kronecker sybmol の計算方法を調べて実装しチェックするだけです。
条件を再整理する
以上条件を再整理すると、このようになります。
条件1:
条件3:
条件5:
条件6: 条件6:
ではPoCが刺さった
条件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;
}
無事に無限ループになりました。
修正内容
こちらのコミット で修正されています。
まとめ
このブログでは BN_mod_sqrt が無限ループになる条件を一つ求め、無限ループに陥るパラメータを作成するスクリプトを作成しました。攻撃原理理解に役に立てば幸いです。
ここまで見ていただきありがとうございます。この記事はこの放送で生配信しながら執筆したものになります。是非興味があれば見てみてください。
Discussion