Heartbleed bug による秘密鍵漏洩の現実性について

本稿では HeartBleed bug による秘密鍵漏洩の可能性を考察します。

OpenSSL で利用される RSA 秘密鍵のフォーマットは PKCS#1^[1]Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1 http://tools.ietf.org/html/rfc3447#section-3.2 で定められています。暗号化された暗号文の復号、もしくはデジタル署名を行う際に RSA の秘密鍵による操作が行われます。SSL/TLS サーバに https でアクセスした場合には、その両方の用途で秘密鍵が用いられます。そのため HSM などの仕組みが無い場合には秘密鍵がメモリ上に展開されている可能性が高いと言えます。実際 Cloudflare Challenge^[2]Heartbleed Challenge – CloudFlare Challenges https://www.cloudflarechallenge.com/heartbleed では、250万回や10万回の Heartbleed bug を利用したメモリアクセスを行うことで秘密鍵の奪取に成功しているとの報告がありました。

サーバ証明書として一般的に利用されている X.509 には、RSA 公開鍵として N, e という整数が格納されています。N はどでかい素数 p と q の積で、RSA 2048ビットと言った場合、この N の長さが2048ビットにあたります (p と q は1024ビット)。一方で PKCS#1 形式の秘密鍵には以下の情報が格納されています。

• 合成数 N
• 公開鍵 e
• 秘密鍵 d
• 素数 p
• 素数 q
• dP := d mod (p-1)
• dQ := d mod (q-1)
• qInv = q^{-1} mod p

実際には公開情報 N, e と秘密鍵 d を用いれば復号可能ですが、dP, dQ, qInv を用いた中国人の剰余定理(Chinese remainder theorem)^[3]N = pq (p と q は互いに素)、 n 以下の整数 x に対して xp = x (mod p), xq = x (mod q) を満たす xp, xq が一意に存在します。また qInv = q^{-1} mod p とおくと x = {qInv … Continue reading を利用することで、mod N 上ではなくその半分のビット長の mod 演算で済むことから、通常の実装方法よりも約1/4の計算量に抑えることができます。そのため OpenSSL などで利用される秘密鍵フォーマットには、これら高速化のための情報が付け加えられています。

このことからも Heartbleed bug を用いてメモリ情報にアクセスする場合には、PKCS#1 形式のデータ全てを取得する必要はなく、その一部の情報からでも秘密鍵が奪取できたと考えることができます。暗号研究者の間では秘密鍵の断片情報から秘密鍵を復元する手法が研究されており、もっと少ないメモリアクセスで秘密鍵を復元できると考えられます。CRYPTO2009 で公開された Heninger, Shacham の手法^[4]Nadia Heninger, Hovav Shacham, “Reconstructing RSA Private Keys from Random Key Bits” https://eprint.iacr.org/2008/510.pdf CRYPTO2009 での講演資料: … Continue readingでは、d, p, q, dP, dQ のうち 27% の断片情報から高確率で復元できるとの報告がなされています。その後この手法はさらに研究が進められており、日本からも貢献しています^[5]Noboru Kunihiro, Naoyuki Shinohara, Tetsuya Izu, “Recovering RSA Secret Keys from Noisy Key Bits with Erasures and Errors” https://eprint.iacr.org/2012/701.pdf 発表は昨年 3 … Continue reading。このような暗号学の成果を適用した秘密鍵復元事例が暗号研究者らによって近々公開されるのではないかと予想されます。

秘密鍵ファイル全体を復元するために膨大な数のアクセスを行うという力ずくな方法ではなく、実際にはもっと少ない試行回数で断片情報から秘密鍵が復元されてしまう可能性があります。そのため、SSL サーバへの Heartbleed bug を突いた攻撃回数が少ないからといっても安全とは言い切れません。当該バージョンの OpenSSL をリンクした SSL サーバを一旦外部に晒してしまった場合には、秘密鍵を作り直しサーバ証明書を再発行することをお勧めします。