浅尝ECC 之 NCCIP attack-安全KER

前言

在刚结束的De1CTF中，遇到了自己不怎么常见的有关ECC问题的一道密码学的题目。由于自己之前没怎么接触过，再加上走了点弯路，自己肝了快一天才把这题做出来。做出来后觉得这个问题也挺有意思的，于是记此文章以记录，若有不当之处，还请大佬们斧正。

De1CTF – ECDH

赛题附件在这里，然后审计代码之后，可以把这个问题概括为：

题目用的是标准曲线：y^2 ≡ x^3 +ax + b (mod p)，并提供a,b,p
函数 Exchange：ECDH问题，生成共享密钥时你提供一个点P，他会用自己的私钥，secret*P生成协商密钥key
函数 Encrypt：用key加密你的输入，加密方式为将key的x和y拼接后于输入简单异或
函数 Backdoor：输入服务端secret值，返回flag

整体流程算是一个标准的ECDH，但在标准的ECDH中，一方应该是无法计算出另一方的私钥的，否则这个算法就GG了。而这一题的漏洞就在于，在密钥交换的过程中，服务端并没有检查你提供的点是否在规定好的曲线上。所以这里的攻击方式就是”No Correctness Check for Input Points” (NCCIP) attacks。

由有限域上椭圆曲线上整数点的加法计算式：

设：已知曲线 y^2 ≡ x^3 +ax + b (mod p) 和 P(x1,y1) 和 Q(x2,y2) ，我们计算R(x3,y3) = P + Q

x3 ≡ k2-x1 – x2 (mod p)

y3 ≡ k(x1-x3) – y1 (mod p)

若P = Q 则 k = (3*x2+a)/(2y1) mod p

若P ≠ Q，则k = (y2-y1)/(x2-x1) mod p

曲线的阶与b值有关，但是我们发现，在整个加法、乘法（从加法引申到乘法是一件极其自然的事）计算的过程中，点R却与曲线的b值无关，所以，如果更改b的值，生成一条新的曲线，且这个曲线的阶有一个很小的因子，比如只有7，那么这个曲线上一定会有阶为7的点。如果我们将这个点传给服务端。而服务端没有检查我们这个点的合法性，直接拿来计算生成key，会产生怎么样的后果呢？

我们假设点P的阶为7，即 7*P = O∞，再设secret值为31

那么服务端就会计算31*P ≡ 3P

由于阶很小，我们可以遍历得到 key = 3P，等价于，我们知道了secret % 7 = 3

所以，我们只要多找这么几个低阶点，多得到几条这样的同余式，最后利用CRT就可以恢复secret了。

【呃，再简要说明一下我们的操作叭，我们更改了b的值，造了一条新的曲线，并且在上面找了一个低阶点。而这个点拿去服务端运算，运算只需要这个点的x坐标，y坐标和曲线的a值，所以可以理解为，因为服务端没有检查输入点的合法性，导致，服务端用的曲线被我们窜改了。】

step1-找到有低阶点的曲线

我们要找到低阶点，我们就先要找到一条阶有小因子的曲线。

由于sympy分解大数速度似乎有点慢，于是我们直接更改b的值，生成一条新的曲线，然后计算、再去在线平台分解这条曲线的阶，看看是否有小因子。

有一条曲线，但是上面的生成元点怎么找呢？这里我们改一改，先确定一个点，然后再去确定b值从而确定曲线，然后去计算、分解这个点的阶。

x = 0xb55c08d92cd878a3ad444a3627a52764f5a402f4a86ef700271cb17edfa739ca
y = 20
q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa

for _ in range(60):
    y+=1
    b = (y**2 - x**3- a*x)%q
    ecc = EllipticCurve(GF(q), [a,b])
    G = ecc(x,y)
    print(y)
    print(G.order())

step2-找到低阶点

有一条阶有小因子的线了，有上面的一个点G，且知道它的阶了，低阶点怎么找呢？

这里有一个很简单的道理，我们知道，77，可以等于7乘以11，也可以等于11乘以7。所以，如果我们这个点G的阶是77，那么，7*P的阶就是11，11*P的阶就是7了。

这里，我们通过上面的脚本得到一个阶为2 * 3 * 5^2 * 83 * 13313 * 45413 *6654245328558174325218919079449691616264872121315671061356825923的点G，从而我们可以得到阶分别为2，3，5，83，13313的点（后面的就不要了，阶太大，之后遍历耗时也太长了，大概一万左右的是我们可以接受的。）

下面的脚本就可以得到一个阶为83的点P

x = 0xb55c08d92cd878a3ad444a3627a52764f5a402f4a86ef700271cb17edfa739ca
q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
y = 314

b = (y^2 - x^3- a*x)%q
ecc = EllipticCurve(GF(q), [a,b])
G = ecc(x,y)
print(G  * 2 * 3 * 5^2  * 13313 * 45413 *6654245328558174325218919079449691616264872121315671061356825923)

step3-计算协商密钥

我们将这个点P当做我们的公钥传给服务端，他会用secret*P 计算协商密钥key

需要说明的是，由于我们破坏了规则，导致服务端的公钥已经不能用了，况且，其实我们自己也不知道自己的私钥是啥。所以这个协商密钥我们还得利用加密函数来获取。

具体操作见下面交互脚本

sh.recvuntil("choice:n")
sh.sendline("Encrypt")
sh.recvuntil("hex):n")
mess = "a"*512
sh.sendline(mess)
sh.recvuntil("The result is:n")
res = sh.recvuntil("n")[:-1]
key = int(mess,16)^int(res,16)
x , y = key >> q.bit_length() , key & ((1 << q.bit_length()) - 1)
G = (x,y)

由于q是256位的，所以key是512位，所以我们传个512位的明文过去。然后异或回来，分离一下，我们就可以得到secret*P这个点了。

step4-计算secret的一个剩余

知道key了，我们就可以遍历计算secret关于这个低阶的剩余了

G = (x,y)    #key
Q = (int(each[0]),int(each[1]))        #我们找到的低阶点Q
for i in range(1,int(each[2])):
    if mul(i,Q) == G:
        reslist.append(i)    #secret的剩余
        N.append(int(each[2]));print (i,int(each[2]))     #secret的剩余对应的阶
        break

step5-利用CRT计算secret

def CRT(mi, ai):
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M / m) * inverse(M / m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

secret = CRT(N, reslist)

完整exp放在这里了。