[关闭]
@1qaz 2016-03-01T01:42:37.000000Z 字数 1956 阅读 315

Practical Invalid Curve Attacks on TLS-ECDH

ECC ECDH


Tibor Jager, J¨org Schwenk, and Juraj Somorovsky,Ruhr University Bochum,ESORICS’15

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

Introduction

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

TLS-ECDH
ecdh

Invalid Curve Attacks on ECC

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

ADD Double
add-dbl
prf


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 算法计算s*G,并返回s*G的x坐标。oracle并不检查输入的点是否在曲线上。返回x坐标的原因是在ECC中key通常来自点的x坐标。

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

已知曲线(F,a,b) 和曲线的阶q
1. 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

2. 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,使得 [s*Gi]x = [t*Gi]x. s = t mod pi, 或者 -s = t mod pi. s2 = t2 mod pi 得到s2mod 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,使得[s*G]x = [t*G]x,并计算出master secret,如果猜测正确,ClientFinished将被server接收并返回ServerFinihed,否则server会alert并结束连接。

oracle

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注