Group of Software Security In Progress

GoSSIP @ LoCCS.Shanghai Jiao Tong University

Practical Invalid Curve Attacks on TLS-ECDH

论文下载

Abstract

椭圆曲线密码学(ECC)是基于群的运算,在做密码学运算之前都应该检查群元素的合法性。但是在实际使用中,有些密码学库忽略了“点是否位于曲线上”这一检查,从而导致使用TLS-ECDH的服务器可能被攻击者获得私钥。

Introduction

ECC y2 = x3 + a*x + b 生成元,曲线的阶数,点的阶数, C = (F,a,b)

TLS-ECDH

Fig

Invalid Curve Attacks on ECC

Crypto 2000, Biehl et al.: Differential fault attacks on elliptic curve cryptosystems

ADD Double

Fig

def mul(n,P):
    R = INF
    while n!=0:
        if n&1 ==1:
            R += P
        P += P
        n >>=1
    return R

注意到加法和乘法运算都没有使用b!

如果不检查点的合法性,运算就可能在另外一条曲线上(a相同,b不同)。

Oracle: “在曲线(F,a,b)上运算,随机私钥s,对于输入的点G,使用double-and-add 算法计算sG,并返回sG的x坐标。oracle并不检查输入的点是否在曲线上。返回x坐标的原因是在ECC中key通常来自点的x坐标。

攻击的整体思路: 寻找不同的b’,使得新曲线(F,a,b’)的阶可被小素数pi整除(2,3,5,7…),这样新曲线上就存在阶数为pi的点G’,假设存在oracle可以将 sG’ 作为结果返回, 有t < pi, sG’ = t*G’.就得到s mod pi的值。使用足够多的小素数pi,利用中国剩余定理,就可计算出s的值。

已知曲线(F,a,b) 和曲线的阶q

Offline Precomputations

第一步: p1,p2,…,pn 为前n个素数,其积大于q2.随机选取bi,使得曲线(F,a,bi)的阶能被某个pi整除。

n是很小的,O(log q*log log q).

  • NIST P-192,q < 2192, n = 60, pn = 283.
  • NSIT P-256,q < 2256, n = 76, pn = 383.

第二步:曲线(F,a,bi)就存在某个点Gi,其阶为pi。(small subgroup attack。 how?)

2.3 GHz CPU, 4GB RAM, 90 minutes for NIST P-192, 5 hours for NIST P-256

Online Attack

计算出(bi,Gi,pi)后

第一步:攻击者将Gi输入给oracle,oracle返回s*Gi的横坐标。oracle认为自己在曲线(F,a,b)上运算,但由于double-and-add算法与b无关,因此实际上oracle是在曲线(F,a,bi)上运算。

第二步: 攻击者计算t,t < (pi+1)/2,使得 [sGi]x = [tGi]x. s = t mod pi, 或者 -s = t mod pi. s2 = t2 mod pii 得到s2 mod pi的值。

第三步:对所有的i,i=1,…,n, 获得s2 = ti2 mod pi ,而且s2 < q2. 利用中国剩余定理,计算出s2,从而得到s。

Invalid Curve Attacks on TLS-ECDH

实际的TLS server有一点不符合之前oracle,TLS server并不会将s*G的值返回给客户端。

oracle非常聪明的在ClientKeyExchange的时候将Gi发送给TLS server,猜测t,使得[sG]x = [tG]x,并计算出master secret,如果猜测正确,ClientFinished将被server接收并返回ServerFinihed,否则server会alert并结束连接。

Fig

Practical Evaluation & Analysis

不检查点合法性的密码库: Bouncy Castle Java 1.50,SunEC Security Provider 1.8,WolfSSL 3.4.6(embeded)

JSSE Elliptic Curve # of oracle queries # of server queries Duration [sec] secp256r1 74 3300 155

CVE-2015-6924 Hardware Security Modules:crypto storage device

ECDH is less used than ECDHE, ephemeral

Check the point! Old attacks still applicable, we can learn a lot from them

https://github.com/mimoo/socat_backdoor