Fetching...

-

Just a minute...

Updated on project competition auroralab

关键词：DH密钥交换协议，Coppersmith攻击，混合密码通信，rsa及aes编程。

题目

image-20200404204929407

出题思路

由于是战队考核，这次的题目应出得相对综合，也更考验同学们的知识面和对各方面加密的理解和把握能力。同时，题目应当结合密码学的实际应用，有生动的背景和场景。

出题前，我在网上做了两三道rsa和aes的题目，觉得出题点还是比较单一，于是联想了一下之前做过的一些印象深刻的密码学题目，于是我想到了把密码学实验和aes，rsa结合起来，出一次改进版的中间人攻击，作为密码学实验的补充。之所以要和aes，rsa结合，是因为通过混合密码通信的安全性更高，效率也更好。我们段老师的PPT是这么说的：

image-20200402112220312

但是，如果rsa加密过程中存在某些问题呢？假如rsa私钥部分泄露呢？那面对中间人的攻击，这种通信方法也难以保证它的安全性。见如下参考论文:

7

在题目环境中，我就让私钥最低位的一半比特泄露出来，这是足够解对称密码私钥的了。根据等式：
$$
e * d == 1 mod phi(N)
$$
我们引入常数k，使得:
$$
e * d - k * phi(N) == 1
$$
由于e模phi的逆：

1
d = gmpy2.invert(e,phi)

所以对于上述等式，有：

$$
phi(N) > d
$$

那么就有：
$$
k<e
$$
由于e一般在16位以下（题目中不超过1024），所以k是可爆破的。

我们对等式两边都模上2的1050次方，并化简：
$$
(e * d - k * phi(N)) mod 21050 == 1 mod 21050
$$

$$
((e mod 21050) * (d mod 21050) - k * phi(N) ) mod 21050 == 1 mod 21050
$$

$$
(e * d0 - kphi(N)) mod 2*1050 == 1 mod 2**1050
$$

$$
e * d0 - kphi(N) == 1 mod 2*1050
$$

方程两边同乘q，并代入等式：
$$
phi(N)==(p-1)(q-1)
$$
以及
$$
N==pq
$$
可以得到：
$$
ed0*p - k(np-pp-n+p) == p mod 2**1050
$$
所以只需要对k进行遍历，然后对每一个k通过sage解同余方程即可。

获取了对称密码的私钥以后，消息明文便不难获取了。同时，和密码学实验一样，我们假设中间人有着足够的能力完成近乎实时的通信，在没有认证机制的DH通信协议中，他就可以冒充通信双方进行欺骗。这里为了保证实时性，本来应该进行时间限制的，这样大家就只能通过python的pwntools工具来进行交互了。但是考虑到考点比较综合，任务量大，在12小时之内能写出这么多脚本的可能性不太大，所以就不限制时间了。

考察点

AES(CBC和ECB）加解密， 铜匠攻击，DH通信协议，中间人攻击，base64加解密

出题过程

首先，还是建立两个文件，Arica.py和conversation.py，保存一些不想公布的变量值:

1
2
3
#Arica.py
key=b'grzu7KTaDuiiBVWL'
flag=b'ACTF{You_have_got_the_flag!That_is_impossible!}'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#conversation.py
questions = [
    b"Who are you?",
    b"Oh my dear Brooke, I miss you so much!",
    b"Brooke, I was so lonely during the outbreak of Novel coronavirus!",
    b"Brooke, do you mind me asking you a few more question?",
    b"What can I do for you?"]
answer = [
    b"I'm Brooke.",
    b"I miss you too.",
    b"Me too! I wanna go out for dance!",
    b"Not at all.",
    b"Nothing."]
fake_answer=b"I want to get my AES-key."
saying_key=b"Here is the key: "

然后在windows上写了针对key的加密函数(aes-cbc)和针对flag的加密函数(泄露私钥的rsa函数)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#encryption.py
from Cryptodome.Cipher import AES
from Arica import key,flag
import base64
import gmpy2

from Cryptodome.Util.number import (
    bytes_to_long,
    long_to_bytes,
    str2long,
    long2str,
    getPrime
)
from Cryptodome.Random.random import (
    getrandbits,
    randint
)

p = 217534615279223294476101434763509239207
g = 2

def encrypt_flag():
    global flag
    aes = AES.new(key, AES.MODE_ECB)
    flag = adaptmessage(flag)
    c = aes.encrypt(flag)
    print("Here is the encrypted flag: "+str(base64.b64encode(c)))
    #b'gTAmtDzEDIYdzs6j55csresodxpsKJlOVMOmzLq8/39Vm0lJZvnrGtPBW6IKUpML'
def encrypt_key():
    e = 1667
    p = getPrime(700)
    q = getPrime(1400) 
    n = p*q
    print("""+------------------------------------------------------+
|Attension! Through soical engineering, you got this: |
+------------------------------------------------------+""")
    phi = (p-1)*(q-1)
    d = gmpy2.invert(e,phi)
    print("n = "+str(n))
    #print(d)
    print("Brooke's partial d: "+ str(int(d) % (2**1050)))
    enc = pow(bytes_to_long(key), e, n)
    return enc

def generateDH(exp):
    return pow(g, exp, p)

def adaptmessage(message):
    return message.ljust(16-len(message)%16+len(message), b"\x00")

def aricaSay(*args):
    print("""+-------------------+
|    Arica said:    |
+-------------------+""")
    print(" ".join(map(str,args)))

def brookeSay(*args):
    print("""+--------------------+
|    Brooke said:    |
+--------------------+""")
    print(" ".join(map(str,args)))

def say2arica(*args):
    print("""+---------------------+
|    Say to Arica:    |
+---------------------+
"""+ " ".join(map(str,args)), end="")
    return input()

def say2brooke(*args):
    print("""+----------------------+
|    Say to Brooke:    |
+----------------------+
""" + " ".join(map(str,args)), end="")
    return input()

然后把DH通信的脚本和题目情景写好：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#server.py
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from encryption import *
from conversation import *

banner = """
+--------------------------------------------------+
|HELLO CHALLENGER!                                 |
|                                                  |
|Have you ever seen movies like MISSION IMPOSSIBLE?|
|Unfortunately, You have got a mission that seemed |
|impossible to finish!                             |
|                                                  |
|In the task, you are required to decrypt the      |
|'Most secret' message of Arica, the bank clerk.   |
|                                                  |
|Fortunately, after social engineering you have    |
|hacked in her communication with her boyfriend    |
| Brooke and you have got Brooke's partial         |
|RSA-private-key.                                  |
|                                                  |
|To get the message, you must first establish      |
| communication with Arica through 'DH key exchange|
| protocol', chat with her by saying what Brooke   |
|said, but you need to send the message            |
| "I want to get my AES-key." and the timestamp    |
| after Arica said "What can I do for you?",       |
|then she will give the AES-key encrypted with her |
| RSA-public-key，this message should be start with|
| "Here is the key:".                              |
+--------------------------------------------------+
"""

def main():
    print(banner)
    encrypt_flag()
    enc = encrypt_key()
    expA = getrandbits(128)
    expB = getrandbits(128)
    A = generateDH(expA)
    B = generateDH(expB)
    aricaSay("A:", A)
    AC = int(say2brooke("A: "))
    brookeSay("B:", B)
    BC = int(say2arica("B: "))
    keyC = pow(AC, expB, p)
    keyS = pow(BC, expA, p)
    keyC = long_to_bytes(keyC).rjust(16, b"\x00")
    keyS = long_to_bytes(keyS).rjust(16, b"\x00")
    cipherC = AES.new(keyC, AES.MODE_ECB)
    cipherS = AES.new(keyS, AES.MODE_ECB)
    for _i in range(5):#5
        index=_i
        randomnum = randint(0, 256)
        messageA = questions[index]
        messageA = adaptmessage(messageA)
        cS = bytes_to_long(cipherS.encrypt(messageA))
        aricaSay("A:", "{:032x}".format(cS))
        s = int(say2brooke("A: "), 16)
        s = long_to_bytes(s)
        q = cipherC.decrypt(s)
        if q != messageA:
            print("Brooke does't get your words and realize something, U FAILED...")
            exit(0)
        randomnum = randint(0, 256)
        messageB = answer[index]
        messageB = adaptmessage(messageB)
        cC = bytes_to_long(cipherC.encrypt(messageB))
        brookeSay("B:", "{:032x}".format(cC))
        s = int(say2arica("B: "), 16)
        s = long_to_bytes(s)
        a = cipherS.decrypt(s)
        if(_i==4):
            messageB = fake_answer
            messageB = adaptmessage(messageB)
        if a != messageB:
            print("Arica does't get your words and realize something, U FAILED...")
            exit(0)
        
    randomnum = randint(0, 256)
    messageA = saying_key+long_to_bytes(enc)
    messageA = adaptmessage(messageA)
    cS = bytes_to_long(cipherS.encrypt(messageA))
    aricaSay("A:", "{:032x}".format(cS))

if __name__ == "__main__":
    main()

在出题过程中，根据自己的测试又稍微对题目更改了一下。

首先，在对aes私钥进行rsa加密的时候，一开始的e比较大，在1500左右，在测试中发现对于不同的d0值和n值，脚本的运行时间需要10分钟-3个小时，而3个小时在12个小时比赛时间里面所占比例太大，所以把e限制在1024以内，且设置为动态可变的数值。但是为了不增加难度，aeskey是固定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def encrypt_flag():
    global flag
    aes = AES.new(key, AES.MODE_ECB)
    flag = adaptmessage(flag)
    c = aes.encrypt(flag)
    print("Here is the encrypted flag: "+str(base64.b64encode(c)))
    #b'gTAmtDzEDIYdzs6j55csresodxpsKJlOVMOmzLq8/39Vm0lJZvnrGtPBW6IKUpML'
def encrypt_key():
    #e = 1667
    p = getPrime(700)
    q = getPrime(1400) 
    n = p*q
    print("""+------------------------------------------------------+
|Attension! Through soical engineering, you got this: |
+------------------------------------------------------+""")
    phi = (p-1)*(q-1)
    while(1):
        e=getPrime(10)
        if(phi%e!=0):
            print("e = "+str(e))
            break
    d = gmpy2.invert(e,phi)
    print("n = "+str(n))
    #print(d)
    print("Brooke's partial d: "+ str(int(d) % (2**1050)))#d有问题
    enc = pow(bytes_to_long(key), e, n)
    return enc

另外由于DH的g为2，所以公钥应当为大于0的整数(不管你是1或者g**y%p，都不可能是0)，所以加入了一段代码检验：

1
2
3
4
5
6
7
8
9
#之所以要做出这个判断，是因为公钥真的不可能为0或负数
if(AC <=0):
    brookeSay("You are not Arica! Her public key should not be:", AC)
    exit(0)
brookeSay("B:", B)
BC = int(say2arica("B: "))
if(BC <=0):
    aricaSay("You are not Brooke! His public key should not be:", BC)
    exit(0)

另外，为了考察大家有没有细读message里面的内容，我在每条message后面都附带一个随机timestamp。每一次都需要更改这个timestamp，使得newtimestamp = (oldtimestamp+1)%256，程序里加上相应举例与提示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
+---------------------------------------------------------+
| PS:                                                     |
| All message should be followed with new timestamp!!!    |
| newtimestamp = (oldtimestamp+1)%256                     |
| Please don't stuck with it:(                            |
| For example, when you decrypt what Arica said like this:|
| +--------------------+                                  |
| |    Brooke said:    |                                  |
| +--------------------+                                  |
| I'm Brooke.                                             |
| timestamp:112                                           |
| You should encrypt this message to Arica:               |
| +---------------------+                                 |
| |    Say to Arica:    |                                 |
| +---------------------+                                 |
| I'm Brooke.                                             |
| timestamp:113                                           |
+---------------------------------------------------------+

请大家不要太纠结timestamp的意义，这个机制是Arica和Brooke确保不被中间人攻击的机制，假设Arica和Brooke的时戳是同步的，对话中每次附加一个时戳值，通过验证时戳与当前时间是否相同来过关。但是如果是采用真正的时间的话，攻击成功的概率就更小了，所以简化一下，就生成一个固定的256位随机数。同时，中间人修改信息需要时间，并把修改后的时间替换发给另一方。这时候我们假设中间人接收并重发消息的时间代价为1s，所以我们要将时戳加一。举例代码如下：

1
2
3
#server.py
messageA = questions[index]+b"\ntimestamp:"+bytes(str((randomnum+1)%256),encoding='utf-8')
messageA = adaptmessage(messageA)

Writeup样例

首先，改编server.py为client.py，和服务器进行交互。这里由于交互程序变动较大，我直接通过手动输入把Arica和Brooke的密文信息传进去，等到解出明文以后手动修改timestamp。另外为了方便起见，我传递过去的公钥为1(即私钥为0)，这样的话和Brooke以及Alice的会话密钥都是1，就比较简单了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from encryption import *

def main():
    keyC = 1
    keyS = 1
    keyC = long_to_bytes(keyC).rjust(16, b"\x00")
    keyS = long_to_bytes(keyS).rjust(16, b"\x00")
    cipherC = AES.new(keyC, AES.MODE_ECB)
    cipherS = AES.new(keyS, AES.MODE_ECB)
    for _i in range(0):#5
        #Arica说话了
        s = int(say2brooke("A: "), 16)#输入Arica说的话
        s = long_to_bytes(s)
        q = cipherC.decrypt(s)
        print(q)
        #这里还是直接从外头输入吧
        messageA = bytes(input(),encoding='utf-8')
        messageA += b"\n"
        messageA += bytes(input(),encoding='utf-8')
        messageA = adaptmessage(messageA)

        s=cipherC.encrypt(messageA)
        print(hex(bytes_to_long(s))[2:])#对Brooke说的话

        #Brooke说话了
        s = int(say2arica("B: "), 16)#输入Brooke说的话
        s = long_to_bytes(s)
        a = cipherS.decrypt(s)
        print(a)
        #这里还是直接从外头输入吧
        messageB = bytes(input(),encoding='utf-8')
        messageB += b"\n"
        messageB += bytes(input(),encoding='utf-8')
        messageB = adaptmessage(messageB)
        
        s=cipherS.encrypt(messageB)
        print(hex(bytes_to_long(s))[2:])#对Arica说的话
        
        
    #Arica说出key了
    s = int(say2brooke("A: "), 16)#输入Arica说的话
    s = long_to_bytes(s)
    q = cipherC.decrypt(s)
    key = q[17:]
    for i in range (len(key)):
        if(key[i:i+10]==b'\ntimestamp'):
            key=key[:i]
            break
    print(q)
    print(key)
    print(bytes_to_long(key))#key

if __name__ == "__main__":
    main()

然后开始运行，运行截图如下：

首先收到服务器的消息:

这些就是rsa的公钥，模数和泄露的私钥，先保存住，然后开始通信。

首先，传递的公钥都为1。然后把Arica said的内容decryption，修改timestamp后把输出给回say to Brooke。

服务器端界面：

2

decryption.py运行界面：

image-20200402131956740

一直运行下去：

3

直到最后得到key:

4

把key的部分截取下来，转换为数字，然后根据已有的e，n，partial d来解出aeskey：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
e=863
n = 100518394843898371534434468452366727877002363101196571557097132988734353726584916462381290904798733002716305256677572628142627545744681541293793069726231800754314572981168235829239563613754713724345581918566947492170647540708428013292098065584617876680109166595710006367308500341766024651457023537770009981295726110940010220082434490215229951191714998895277291076151298363584672162765486380515325199053994651202708865071379999942193926154807059329464291992287421875356468218685095369057734586073271903432589401520355996027480658214090147502829069822606753125953586123331154015992246394834867237734405963056883227552074835515815968441
c=86032824638305503499105979004374728344861493802341583733786447138684660694449673826205271902766363026345759436852747743967254218765160248630402258125202844303276381357264903281385470521070161164325276902001627351570675438339067652784355957225763207341000628151024518554862922220201109512940053316358078220681816224518400117972877854801506805929902506832781106133167532327833813179558969694268634413548545525533605595649634856393268111552838570383386406869870266457914799472663817890880697043874427042958587244568923338441053981863674366842769379075373006984522023718553749977766836594738859315852333132093474709715377682153430675891
d0=8429433927120666131169351623736961178529851960373209550653840828920672665447032524933438956407503522388445988812739437427277858013428300926608147855795349674824173869269407061090165202002106353884034590344852857623737262477675587193006629765892565228448265429521617733861051151345083787592170864896543517637252788111

d = 0
for k in range(0,e):
    print k
    X = var('X')
    results = solve_mod([e*d0*X - k*(n*X-X*X-n+X) == X], 2**1050)
    for x in results:
        p0 = ZZ(x[0])
        if is_prime(p0) and gcd(n,p0)!=1:
            print p0
            q0 = n//p0
            phi=(q0-1)*(p0-1)
            d = inverse_mod(e,phi)
            break
    if(d!=0):
        break
print d
m = pow(c,d,n)
print m

运行结果如图：

5

得到aeskey以后解密flag，脚本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Cryptodome.Cipher import AES
import base64
from Cryptodome.Util.number import (
    bytes_to_long,
    long_to_bytes,
)
key_in_num = 137504889148498708381160600835355727692
encryptedflag = b'gTAmtDzEDIYdzs6j55csresodxpsKJlOVMOmzLq8/39Vm0lJZvnrGtPBW6IKUpML'
c = base64.b64decode(encryptedflag)
key = long_to_bytes(key_in_num)
print(key)
aes = AES.new(key, AES.MODE_ECB)
flag = aes.decrypt(c)
print("Here is the decrypted flag: "+str(flag))

最终得到flag

6

参考资料：

[1]王小云,刘明洁.格密码学研究[J].密码学报,2014,1(01):13-27.

Related post
Comment
Share
To Top
  • Coppersmith攻击方式小结

    三月 29日, 2020

    关键词：rsa，coppersmith攻击。 CopperSmith攻击的种类真的很多，以下是我归纳的几种常见形式： 一道新的例题——p的高位和地位泄露摘自：Securinets CTF Quals 2020 - Destructio...

    Coppersmith攻击方式小结
  • ACTF新人赛密码学部分考察点与题解

    二月 16日, 2020

    关键词：密码学，CTF出题，题解。 具体的题目，考点，题解请见项目链接。 新生赛是我进入实验室以来参与出题的第一场比赛。为了这个比赛，我在平时还是做了一些积累，只有有灵感，我就着手开始写出题脚本和解题脚本，然后有一道自己完成不了的题目...

    ACTF新人赛密码学部分考察点与题解
  • ACTF2020密码学部分writeup

    六月 5日, 2020

    编写的项目文件请参考项目链接。同时欢迎大家访问ACTF2020的所有赛题。喜欢的话请多多资瓷一下，给我们实验室的项目加个Star或者Fork，谢谢。 为了保护服务器的同时不给选手带来更多困难，密码学部分的交互题开了pow算力检测，我也...

    ACTF2020密码学部分writeup
  • 通过python脚本自动插入汇编反调试代码

    五月 20日, 2020

    研究背景在之前OLLVM项目的研究过程中，我们发现反调试技术对反混淆脚本有一定的干扰作用，如果可以在OLLVM的中间代码中自动化插入反调试代码，那么就可以给OLLVM的代码混淆增加一层保障。 方案分析探讨多种方案以后，我认为最适合在汇...

    通过python脚本自动插入汇编反调试代码
  • 答辩顺序抽签小程序

    五月 14日, 2020

    最近比较喜欢动手编写小程序和脚本。晚上有同学和我讨论对答辩队伍进行公平抽签的方案，所以打算编写一个很简单的小脚本，并做到尽量减少计算量。 脚本思路按照一定根据给各个队伍排序，然后初始化抽签序号池，每次随机获取池内的一个值，交给其中一支...

    答辩顺序抽签小程序
  • 课堂记录小助手

    五月 7日, 2020

    作为一名课代表，我需要每天记录同学在QQ群的签到和回答问题情况。开始我是直接把记录复制到word里面手动提取有用的消息，最后我决定解放双手编写一个自动化处理脚本。 这个脚本需要一些什么功能呢？1.最基础的，就是从漫长的聊天记录中提取专...

    课堂记录小助手
  • 基于门限方案的条形码保密及容错技术

    四月 30日, 2020

    关键词：门限方案，条形码保密，条形码容错，条形码认证与防伪造。 经历过初期两个小项目的探索，我们项目团队积累了一定的项目研究经验，在老师和16级学长的帮助下，我们把研究方向转到了门限方案的实际应用上。结合市面上用9张合并的条形码提高条...

    基于门限方案的条形码保密及容错技术
  • 2020新年原创脚本-其中的小把戏你清楚吗

    四月 26日, 2020

    关键词：随机数素数生成，新年祝福小程序。 脚本创作这是我在大年三十写的一个程序，当时我正准备去伯克利交流，但由于疫情的缘故，出国变数增大，所以我就打算通过随机数“未卜先知”。以下就是我的脚本： 12345678910111213141...

    2020新年原创脚本-其中的小把戏你清楚吗
  • 基于CRT的物流信息安全处理方案

    四月 15日, 2020

    关键词：中国剩余定理，密钥分发技术，隐私保护。 引言在2018年11月份的时候，段老师在密码学课上讲到了密钥分发协议，我当时就觉得这个协议很有意思也很有应用前景。后来老师还很主动地分享了一下它的idea，其中一部分就是有关物流单上的信...

    基于CRT的物流信息安全处理方案
  • 基于CRT的新型群文件共享系统

    四月 13日, 2020

    关键词：隐私保护，权限管理，身份认证，中国剩余定理，密钥分发，密钥更新。 这个项目的是在2019年寒假期间进行的，4月份在中南大学信息安全作品赛答辩，但是由于功能只实现了主体部分，加之我在台上比较胆怯紧张，所以只获得团队三等奖，但是当...

    基于CRT的新型群文件共享系统
Please check the parameter of comment in config.yml of hexo-theme-Annie!
ESC