Cryptographic protocol Evaluation toward Long-Lived Outstanding Security Consortium

Key_Recovery_Attack_on_DH_small_subgroups_20160130J

[2016/1/30] 2016年1月28日に公表されたOpenSSLの脆弱性について

2015年1月28日(UTC)、OpenSSL.orgが、OpenSSL 1.0.2, 1.0.1に対するセキュリティアドイザリを発出しました [1]。 このセキュリティアドバイザリではSeverity がHighの脆弱性がひとつ含まれています。

  • DH small subgroups (CVE-2016-0701)

本脆弱性は、DHで使う素数のパラメータの中に安全(safe)でないものが含まれていたことが原因であり、攻撃者は安全でない素数(non-safe prime)を利用してprivate DH exponent(秘密鍵に相当)を入手できます。
この攻撃法では、例えば、TLSのサーバが ephemeral DH ciphersuites を利用して private DH exponent を使い回すか、static DH ciphersuiteを利用している場合に、サーバの private DH exponentを入手できます。
本脆弱性はRFC5114(安全でない素数が含まれている)をサポートしている
OpenSSL1.0.2のみに影響し、暗号のパラメータ選択に関する問題と考えられます。

non-safe primesについて

ここで、安全でない素数(non-safe prime)とは、素数p に対して(p-1)/2が多くの小さい因子(small factor)を持つ場合を指します。RFC5114に記載されている素数には、これに該当する素数が存在します [2] 。

攻撃の成立条件

本脆弱性では、同一のprivate DH exponentを複数回利用している場合に
攻撃が可能となります。これは static DHが該当しますが、OpenSSLでは、暗号スイートとしてDHEを指定している場合でも、オプションである SSL_OP_SINGLE_DH_USE のフラグがoffになっていれば、DH鍵生成を実行しません。また、デフォルトではSSL_OP_SINGLE_DH_USEがonではありませんでした。

OpenSSLにおける対策

今回公開された1.0.2fでは、reuse 対策として SSL_OP_SINGLE_DH_USEをデフォルトで on とし、(SSL_OP_SINGLE_DH_USE に拠らず)毎回異なるDHE鍵を生成するように変更されています。また、本攻撃を検知する簡単なパラメータチェックの仕組みを入れることで攻撃を無効化しています。

現時点では確認できていませんが、本攻撃はOpenSSL以外の実装においても有効です。さらに、SSL/TLSに拠らず他のセキュリティプロトコルにも起こりうる攻撃のため、IETFなどの標準をチェックする必要があるでしょう。

参考文献・リンク

[1] OpenSSL Security Advisory [28th Jan 2016],
https://www.openssl.org/news/secadv/20160128.txt

[2] OpenSSL Key Recovery Attack on DH small subgroups (CVE-2016-0701)
http://intothesymmetry.blogspot.jp/2016/01/openssl-key-recovery-attack-on-dh-small.html

付録:攻撃の詳細について (2/1に一部修正)

[攻撃シナリオ] RFC5114に載っているパラメータで、(p-1)/2がsmall factorを持っているものがある。このうち small factor部分を推定していく。

  • (1) 攻撃者Aはp-1/qの小さい素因数p_iを取り、ya=(g^xa)*R を送る(Rは位数がp_iの元)。サーバBはss_ba = ya^xbを計算し、これをshared secretとしてセッション鍵を生成する。ハンドシェイクの最後に、MAC(ss_ba, session_hash)を計算し、攻撃者Aに送信する。
  • (2) 攻撃者Aは ss_ab = yb^xa を計算する。
  • (3) 攻撃者Aは、R^j (0<=j<p_i)についてMACを計算しておき、MAC(ss_ab*R^j, session_hash) = MAC(ss_ba, session_hash) となるjを見つける。
  • (4) (1)から(3)で得られた方程式を基にChinese Remainder Theoremで解読。
    • x = c_i mod p_i (0<=i<m) <- (1)~(3)の繰り返しで得られた方程式
    • x = c_m mod (p-1)/(Πp_i) <- 同上だが、cの候補は総当りではない

reuseすることは,上記で p_i を変えてチャレンジできるためCRTに適用する際の各因子ごとの方程式を得られるためである。逆に考えると
reuseしないならば,この攻撃を防ぐことを意味する。

なお [2]に記載されている解読にかかる計算量2^44は以下に拠ると考えられる。RFC5114 2.2節に記載の "2048-bit MODP Group with 224-bit Prime Order Subgroup" において p-1/2 は多くの素因数を持つ。このうち、83501807020473429349とC489は分離せず(残りの small primes で137ビット) birthday attack を行うことから (224-137)/2 = 43.5が得られる。

最新の更新 RSS  Valid XHTML 1.0 Transitional