[推荐]看雪·安恒 2020 KCTF 春季赛 | 十一题设计思路及解析

2020-5-14 17:03 6246

[推荐]看雪·安恒 2020 KCTF 春季赛 | 十一题设计思路及解析

Editor

2020-5-14 17:03

6246

十一题《守株待兔》历时3天，已于5月11日中午12点关闭攻击通道。此题共有972人围观，最终仅有1支战队成功破解。

这道题难度较大，辣鸡战队的xym是唯一一个成功提交Flag的选手。

目前攻击方排名如下：

值得注意的是，在非洲看雪战队的gannicusx后来居上，拿到了十二题《白云苍狗》的一血，此前该战队只攻破了签到题，在三百多支队伍中默默蛰伏，一朝发力，就凭借十二题挤进防守方总排行的前十。

你还在犹豫什么？最后一题正在火热进行中！谁会是下一匹黑马？不到最后一切都有可能！冲刺吧！

赛题解析对于做题同样有用，是一个开阔思路和积累知识的好机会！接下来让我们一起看一下这道题的设计思路和详细解析吧。

出题团队简介

本题出题战队 ReadPage：

团队简介：

readyu的米兔安全小分队。

readyu，毕业于中国科学技术大学自动控制专业，从事软件开发多年。在软件保护技术、加密算法方面有一些深入的研究，编写了ECCTool（椭圆曲线加密工具），RDLP（RSA与离散对数实用工具）。曾在北京多看科技从事电子阅读加密技术的研究，现任职于小米AIoT安全实验室。

设计思路

说明：密码学题目， VC++ 编译的Win32程序。

1、序列号（flag）

这个程序默认只有一个SN，用户名内置为username。输入正确的SN提示good work，错误的SN提示bad code。

本题唯一序列号（SN）为一整行字符串：

flag{username-27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88-12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF}

就题目本身而言，本题是一个把椭圆曲线上和RSA结合来的公钥签名算法，简称KMOV。

格式为：flag{name-X-Y}

X，Y 都是大写字母的hex digit number，非0开头，每个name对应有1个key。

X-Y 是(name，hash) 的KMOV签名（公钥是小指数0x101，也就是257）。

这里用到的hash是 hmac_sha256(key,name)， key是modulus N，在题目中，是椭圆曲线的模：一个10进制字符串。

彩蛋（额外赠送的）进入方式：

(a) SN验证通过，再点击2下，可进入解锁模式，可针对不同的用户名验证SN。

(b) SN框内输入11个字符，点击check：////debugme

2、算法模型与解题分析

2.1 KMOV算法：在模N的椭圆曲线上实现RSA

本题实现了一个模N椭圆曲线上的RSA签名算法，算法名称是KMOV，（可以类比2019 Q3 模N的lucas序列上的RSA）。

算法的原始提出者是4个人，名字缩写是KMOV，论文简称为KMOV91：
《New Public-Key Schemes Based on Elliptic Curves over the Ring Zn》

Kenji Koyama , Ueli M. Maurer , Tatsuaki Okamoto , Scott A. Vanstone

说明：本题只用到这篇文章前5页的内容（6-13页不涉及到）。

这个算法模型，和传统的RSA可以对应，N是模，e是公钥，d是私钥，消息与签名编译为椭圆曲线的坐标x，y：

签名：
R(x,y) = d * G(x,y) mod N

验证：

G(x,y) = e * R(x,y) mod N

其中：N = p * q, p, q是两个素数，且 p, q = 2 mod 3 。用到椭圆曲线的一个定理，如下的特殊椭圆曲线，a = 0：
y^2 = x^3 + ax + b mod n
特殊地a = 0：
y^2 = x^3 + b mod n

它的周期是，欧拉phi函数：phi = (p+1)*(q+1) ，这个phi的含义类似RSA里面的(p-1)*(q-1)。

d是私钥（大指数）， e是公钥（小指数，可以取一个小素数，与phi互素的，比如257, 63357），对应地，有 e*d = 1 mod phi。

所以就可以把RSA的原理应用到模n的椭圆曲线上（n是一个rsa number，注意不是模p，或者模q）。

2.2 题目验证流程

step 1：从flag{username-X-Y} 里提取username， X， Y

题目用到：modulus=

"1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139"

如下处理：msg = "KXCTF2020.readyu.Catch.Rabbit:username"

然后取key=modulus 字符串，计算：
hash = hmac_sha256(key, msg)

我们有：
h = hmac_sha256(key, msg)=77C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58

h是32字节长度，然后在h前面固定地加上一个字节0x21（10进制为33）.

hash = 2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58

step 2：X，Y 作为椭圆曲线的坐标输入， R(X,Y)，计算 G(X,Y) = 257 * R(X,Y)

椭圆曲线的加法是这么计算的：
y^2 = x^3 + a*x + b

add point:
(x3,y3) = （x1，y1） + (x2, y2)
k = (y2 - y1)/(x2-x1)
x3 = k*k - x1 - x2
y3 = k*(x1 - x3) - y1

double point:
(x3,y3) = （x1，y1） + （x1，y1）
k = (3*x1*x1+a)/2*y1
x3 = k*k - x1 - x1
y3 = k*(x1 - x3) - y1

由于在题目里，e取257 = 2^8+1, 所以题目只实现一个小指数乘法 e*R(x,y) 。

椭圆曲线的基本运算是加法，题目就是用了8次double， 1次add。

G(X,Y) = 257 * R(X,Y) ，因为：257 = 2*2^7 + 1
所以：G = 2^7*(R+R) + R

static void encrypt_e(Big &x1, Big &y1, Big &n)
{
    int i;
    Big x2, y2, k;

    // 0x101 = 2^8 + 1
    
    // (x2, y2) = 2*(x1,y1)
    y2 = 3*x1*x1;
    x2 = 2*y1;   
    k = inverse(x2, n);
    k *= y2;
    x2 = (k*k - x1 - x1) % n;
    y2 = (k*(x1 - x2) - y1) % n;

    // 2^7 * (x2,y2)
    for(i = 0; i < 7; i++)
        dbl_point(x2, y2, x2, y2, n);

    add_point(x2, y2, x1, y1, n);

    return;
}

step 3：验证X，Y坐标分别是对应的签名：

X坐标：G.X = msg, 题目里其实是验证 hmac_sha256(modulus, G.X) = hmac_sha256(modulus, msg)

Y坐标：G.Y = hash

2.3 解题的Keygen流程

step1

modulus.key=

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
msg=KXCTF2020.readyu.Catch.Rabbit:username

hash=hmac_sha256(key, msg)=77C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58

如下生成G点坐标：

G.x = msg.bytes, G.y = 0x21 || hash,

那么：

G(x,y)=
4B58435446323032302E7265616479752E43617463682E5261626269743A757365726E616D65

2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58

step 2

计算：n = p*q (这个RSA-100是公开的)

RSA-100 = 37975227936943673922808872755445627854565536638199
* 40094690950920881030683735292761468389214899724061
e = 257

计算 phi = (p+1)*(q+1), 计算 d = e^-1 mod phi

step 3

计算 R=d*G(x,y)=

27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88
12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF

同时我们可以验证：
G(x,y)=e*R(x,y)=
4B58435446323032302E7265616479752E43617463682E5261626269743A757365726E616D65
2177C13E81BEACB06B6D544BDFCA684BB07F6939D887CEC1AFCE2CA10E099A1C58

可见X坐标是msg的字符串，而Y坐标是hash字符串。

G(x).str=KXCTF2020.readyu.Catch.Rabbit:username

于是，符合username的flag为：

flag{username-27D9A3DACA0B408853CBB1D79393864648F4DEA917066285C182C8B717A6822D9B67A541F173F75DB88-12C1975E404FA3E9356E6492BC2934E889F63FE98B623B83770CCFE519EFD5A9F5D0C1DB43A0F61D2BF}

3、keygen源代码

附件keygen源代码 keygenme2020q1_kmov_keygen ，VC++6 测试通过。

crackme只用到椭圆曲线的点加，而keygen要用到k倍加（点乘, R = k* G），所以要实现mul算法，参见源代码。

这里同样给出keygen的源代码，点加的方法和之前2019Q4的题目Edwards curve椭圆曲线类似。

但是本题椭圆曲线是最基本的类型，没有射影坐标变换，所以简单一些。

keygen用的是二进制展开法，这个方法最便于理解， k的展开如下描述：

// x2,y2 = k* x1,y1

// k = base2 : an | an-1 | ... | a1 | a0, ai = (0, 1)

// k = a0 + 2 * a1 + 4*a2 +...+ 2^n*an

点击链接下载附件：https://bbs.pediy.com/thread-258794.htm

解析过程

本题解题思路由辣鸡战队的xym提供：

1. 由题目给出两个定值求两个值猜测可能是椭圆曲线。

2. 发现重构代码里有一部分用于求取类似斜率的值，理解了题目是要求取点key的两个坐标值，其中(2^8+1)key=point，point是点，有两个坐标值且已知。

2.0 椭圆曲线更多知识参考https://www.cnblogs.com/qcblog/p/8998045.html

2.1 查找椭圆曲线（Elliptic curve）的加法定义，最先发现python实现的Elliptic curve代码如下（ref：https://gist.github.com/bellbind/1414867，这里还有mul的定义，后续求解key要用到）：

if p1.x == p2.x:

# p1 + p1: use tangent line of p1 as (p1,p1) line

l = (3 * p1.x * p1.x + self.a) * inv(2 * p1.y, self.q) % self.q#点p1==p2时，椭圆曲线定义的加法是该点切线与曲线的另一交点的对称点（或叫逆元）

pass

else:

l = (p2.y - p1.y) * inv(p2.x - p1.x, self.q) % self.q#点p1!=p2时，椭圆曲线定义的加法是p1与p2做直线与曲线的另一交点的对称点

pass

x = (l * l - p1.x - p2.x) % self.q

y = (l * (p1.x - x) - p1.y) % self.q

2.2 再利用重构代码通过两种方法实现4倍点的计算，一种是做两次倍点运算，一种是做一次倍点运算，再加两次本来的点，若相等，则可从另一个角度验证了就是椭圆曲线上的加法。

3. 虽然以上都说明该题目是椭圆曲线上的问题，但是该题目的模数p并不是素数，那么为求取key=((2^8+1)^(-1))*point有两个思路，一个是分解模数p，然后按照一般方法求取椭圆曲线的阶，另一个是尝试实现Schoof-Elkies-Atkin Algorithm，直接求取阶，可参考https://people.cs.nctu.edu.tw/~rjchen/ECC2009/30_SchoofElkiesAtkin.pdf。

幸运的是，在factdb.com网址里直接把320比特长的大数p给分解了。分解了p后，可以在sage上直接求取有限域下的Weierstrass equation的阶（ref：https://doc.sagemath.org/pdf/en/reference/curves/curves.pdf page:103；https://en.wikipedia.org/wiki/Elliptic_curve）

求取两个阶的最小公倍数视作我们这个题目的阶即可求取(2^8+1)^(-1)，再计算((2^8+1)^(-1))*point就可得到key，这里用到了int与点的乘法，上文提到了一种实现方式，这里也可以自己实现椭圆曲线下的倍乘程序（原理与快速幂乘一样）。

第二种方法暂时还没有实现。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏・0

点赞・0

打赏