February 23, 2023
#math #crypto

Diffie-Hellman

目录

CMU 18-631 S23 U2L2

感谢：Generate

为了方便浏览 题目在最底部 点击右侧目录即可跳转 结合此图来看(画板驱动掉了凑合看吧 网上有更清晰的版本) 

1
2
3
4
5
6
7

# N -> c = m ^ e mod n
# p
MODULUS = 12345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012281  

# m
# g
BASE = 4384165182867240584805930970951575013697

在 mitm_test.py 文件中的 alice 函数中的

1
2
3
4
5

# Start by generating a secret  
ALICE_SECRET = random.getrandbits(128) # 生成随机数

# Compute (base)^(secret) mod (modulus) and send it  
ALICE_SHARED = pow(BASE, ALICE_SECRET, MODULUS) # 计算公钥 = (base)^(secret) mod (modulus)

可以得出如下关系式

这个博客主题不支持带标签的数学公式 就用代码框框起来了

1
2
3
4
5

$$
\begin{align}
公钥 &= base ^ {secret} \pmod {modulus}
\end{align}
$$

替换为标准的加密

$$ c = m ^ e \pmod n $$

根据文件中声明的 MODULUS 和 BASE 替换为上述式子后我们可以知道其中的 m n 和 c ( c 在经过37行的代码后发送给 bob 时我们作为中间人可以监视到) 其中只有 secret 这个随机数未知

1
2

# Compute the shared secret  
SHARED_SECRET = pow(BOB_SHARED, ALICE_SECRET, MODULUS) # 计算密钥 = (公钥)^(secret) mod (modulus)
$$ {SHAREDSECRET} = BOB公钥 ^ {爱丽丝随机数} \pmod {MODULUS} $$

代码执行到此步时, SHARED_SECRET 为双方共享密钥 其中我们可知 BOB公钥 和 MOD值 以及 爱丽丝侧计算的共享密钥 (在后续代码中将发送给 BOB 我们可以监听) 未知数依旧仅为 爱丽丝随机数

到这里的时候已经不用看中间无用的尝试了 直接跳到底部看正解即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# send some data between the two parties to ensure data is being correctly transmitted  
print("[Alice] starting handshake...")  
  
send(encrypt("secret message 1", SHARED_SECRET))  
assert decrypt(recv(), SHARED_SECRET) == "secret message 2" # 断言 如果解密所接受的数据解密后不为"secret message 2" 则报错 
send(encrypt("secret message 3", SHARED_SECRET))  
send(encrypt("secret message 4", SHARED_SECRET))  
assert decrypt(recv(), SHARED_SECRET) == "secret message 5"  
assert decrypt(recv(), SHARED_SECRET) == "secret message 6"  
  
print("[Alice] sending flag...")  
  
# send the secret flag  
send(encrypt(f"Here is your flag {SECRET_FLAG} :)", SHARED_SECRET))  
  
send(encrypt("goodbye", SHARED_SECRET))  
  
print("[Alice] goodbye")

Diffie-Hellman 中 已知 pair(明文 ,密文) 和 盐 以及 Alice和Bob的公钥 ; 同时已知在计算双方公钥时形如 $c = m^e \pmod n$ 式 中的 m 和 n (或者说原根 g 和 质数 p )(双方在生成公钥时使用了同样的 m 和 n ; 未知的 e (用于计算公钥和计算共享密钥时的指数)均为双方各自早先生成的 128bit 随机数) 并且已知每次进入 encrypt 函数后的 nonce 值 如何非暴力方法求未加盐的 key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def encrypt(msg, key):  
    nonce = random.randint(int(1e10), int(1e11))  # 已知
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()  
    msg = msg.encode()  
    msg_enc = bytes([msg[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg))])  
    return str(nonce) + "+" + msg_enc.hex()  # msg_enc.hex() = 将字节转换为十六进制  
  
  
def decrypt(msg_enc, key):  
    nonce = int(msg_enc.split("+")[0])  
    msg_enc = bytes.fromhex(msg_enc.split("+")[1])  
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()  
    msg = [msg_enc[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg_enc))]  
    msg = bytes([x if x < 128 else ord(" ") for x in msg]).decode()  
    return msg

突破点

在与无需知晓随机数 128bit 暴力不现实 于是直接对其进行中间人攻击

1
2
3

    if '+' not in msg:
        new_msg = 1
        return new_msg

第一句是在判断是否为握手阶段 然后将双方交换的公钥改为1 后发送

1
2
3
4
5

import random
base = 1
secret = random.getrandbits(12888)
MODULUS = 12345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012281
print(pow(base, secret, MODULUS), len(bin(MODULUS)))

这时假的公钥进到双方的共享密钥生成函数中

1

SHARED_SECRET = pow(ALICE_SHARED, BOB_SECRET, MODULUS) # 共享密钥

由于 两人的 SHARED 字段 均为1 这时两人预先生成的幂数 SECRET 便会失效 可以测试下(没必要 因为底数已经为1了)

1
2
3
4
5
6

import random
import gmpy2
base = 1
secret = random.getrandbits(12888)
MODULUS = 12345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012281
print(pow(base, secret, MODULUS), len(bin(MODULUS)))

再用构造后的共享密钥来解密(和他们手里发送消息时用来加密的共享密钥是一致的)

1
2
3
4
5
6
7

# 这时的 key 已经是构造后的结果
    SHARED_SECRET = 1
    # 解密
    print(f"[MITM] start decrypt msg={msg}")
    msg_hack = decrypt(msg, SHARED_SECRET)
    print(f"[+] from hack msg={msg_hack}")
    return msg

需要检测flag的话只需要将 msg_hack 中的 flag 提取出来即可

1
2

    if 'flag' in msg_hack:
        print(f"[+] flag={msg_hack}")

题目

针对 Diffie-Hellman 实施中间人攻击 mitm_test.py 文件用于测试 无需也不能修改其内容，实践在 mitm.py 中的 mitm 函数中实现

  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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

# mitm_test.py
"""
Do not edit this file. Changing it may cause your solution to fail on the autograder.
Implement your solution in `mitm.py`
"""
import math
import sys
import threading
import queue
import random
import hashlib

# import the mitm.py file
from mitm import mitm

## The actual key-exchange in the autograder will also use the same modulus and base parameters
MODULUS = 12345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012281

BASE = 4384165182867240584805930970951575013697

SECRET_FLAG = "placeholder flag"

# This is the first user in the key-exchange
def alice():
    send, recv = bind(own_name="alice", remote_name="bob")  # 绑定两个用户

    """Complete a Diffie-Hellman key exchange"""
    print("[Alice] starting key exchange")

    # Start by generating a secret
    ALICE_SECRET = random.getrandbits(128)  # 生成随机数
    # print(f"[Alice] secret: {ALICE_SECRET}")

    # Compute (base)^(secret) mod (modulus) and send it
    ALICE_SHARED = pow(BASE, ALICE_SECRET, MODULUS)  # 计算公钥 = (base)^(secret) mod (modulus)
    send(str(ALICE_SHARED))  # 发送公钥
    # print(f"[Alice] shared: {ALICE_SHARED}")

    # Receive the other party's shared value
    BOB_SHARED = int(recv())  # 接收公钥
    # print(f"[Alice] received: {BOB_SHARED}")

    # Compute the shared secret
    SHARED_SECRET = pow(BOB_SHARED, ALICE_SECRET, MODULUS)  # 计算Alice 的共享密钥 = (公钥)^(secret) mod (modulus)

    # Now, SHARED_SECRET is a shared encryption key between the two parties.

    # send some data between the two parties to ensure data is being correctly transmitted
    print("[Alice] starting handshake...")

    send(encrypt("secret message 1", SHARED_SECRET))
    assert decrypt(recv(), SHARED_SECRET) == "secret message 2"  # 断言 如果解密所接受的数据解密后不为"secret message 2" 则报错
    # 个人猜测断言是为了防止中间人篡改和验证加密解密是否正常 不过预期数据存在server端 或许可以当蜜罐?
    send(encrypt("secret message 3", SHARED_SECRET))
    send(encrypt("secret message 4", SHARED_SECRET))
    assert decrypt(recv(), SHARED_SECRET) == "secret message 5"
    assert decrypt(recv(), SHARED_SECRET) == "secret message 6"

    print("[Alice] sending flag...")

    # send the secret flag
    send(encrypt(f"Here is your flag {SECRET_FLAG} :)", SHARED_SECRET))

    send(encrypt("goodbye", SHARED_SECRET))

    print("[Alice] goodbye")

# This is the second user in the key-exchange
def bob():
    send, recv = bind(own_name="bob", remote_name="alice")

    """Complete a Diffie-Hellman key exchange"""
    print("[Bob] starting key exchange")

    # Start by generating a secret
    BOB_SECRET = random.getrandbits(128)

    # Compute (base)^(secret) mod (modulus) and send it
    BOB_SHARED = pow(BASE, BOB_SECRET, MODULUS) # Bob的 公钥
    send(str(BOB_SHARED))

    # Receive the other party's shared value
    ALICE_SHARED = int(recv())

    # Compute the shared secret
    SHARED_SECRET = pow(ALICE_SHARED, BOB_SECRET, MODULUS) # Bob's 共享密钥

    # Now, SHARED_SECRET is a shared encryption key between the two parties.

    # send some data between the two parties to ensure data is being correctly transmitted
    print("[Bob] starting handshake...")

    send(encrypt("secret message 2", SHARED_SECRET))
    assert decrypt(recv(), SHARED_SECRET) == "secret message 1"
    send(encrypt("secret message 5", SHARED_SECRET))
    send(encrypt("secret message 6", SHARED_SECRET))
    assert decrypt(recv(), SHARED_SECRET) == "secret message 3"
    assert decrypt(recv(), SHARED_SECRET) == "secret message 4"

    print("[Bob] waiting for flag...")

    __FLAG = decrypt(recv(), SHARED_SECRET)

    assert decrypt(recv(), SHARED_SECRET) == "goodbye"

    print("[Bob] goodbye")

"""
Encrypt the message using the given numeric key, returning a string
This function may be useful as part of your attack.
"""

def encrypt(msg, key):
    nonce = random.randint(int(1e10), int(1e11))  # 盐
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()  # 加盐密钥 = sha512(盐+密钥)
    msg = msg.encode()  # 转换为字节
    msg_enc = bytes([msg[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg))])  # 加密 = 明文 ^ 加盐密钥
    return str(
        nonce) + "+" + msg_enc.hex()  # nonce is used to ensure that the same message encrypted with the same key will not be the same

"""
Decrypt the message using the given numeric key, returning a string
This function may be useful as part of your attack.
"""

def decrypt(msg_enc, key):
    nonce = int(msg_enc.split("+")[0])
    msg_enc = bytes.fromhex(msg_enc.split("+")[1])
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()
    msg = [msg_enc[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg_enc))]
    msg = bytes([x if x < 128 else ord(" ") for x in msg]).decode()
    return msg

"""
The code beyond this point is just the mechanics of the message passing through
the MiTM. It should not affect your solution.
"""
queues = {"alice": queue.Queue(), "bob": queue.Queue()}
mitm_queues = {"alice": queue.Queue(), "bob": queue.Queue()}

def send_internal(msg, src_name, dst_name):
    assert src_name in mitm_queues

    mitm_queues[src_name].put(msg)

def recv_blocking_internal(own_name):
    return queues[own_name].get(block=True, timeout=None)

def bind(own_name, remote_name):
    def send(msg): send_internal(msg, own_name, remote_name)

    def recv(): return recv_blocking_internal(own_name)[1]

    return send, recv

if __name__ == "__main__":
    alice_thread = threading.Thread(name="alice_thread", target=alice)  # 创建线程
    bob_thread = threading.Thread(name="bob_thread", target=bob)
    alice_thread.setDaemon(True)  # 守护
    bob_thread.setDaemon(True)
    alice_thread.start()  # 开始
    bob_thread.start()

    mitm(
        lambda msg: queues["alice"].put(("bob", msg)) if msg is not None else None,  # 如果msg不为空则将msg放入队列
        lambda msg: queues["bob"].put(("alice", msg)) if msg is not None else None,
        lambda: None if mitm_queues["alice"].empty() else mitm_queues["alice"].get(),  # 如果队列为空则返回None
        lambda: None if mitm_queues["bob"].empty() else mitm_queues["bob"].get(),
    )

    alice_thread.join()  # 等待线程结束 join()方法会阻塞调用线程，直到被调用线程结束为止
    bob_thread.join()

答题模板文件及正解

 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
90
91
92
93
94
95
96
97

# mitm.py
"""
Implement your solution in this file.
You should not need to use any libraries other than those imported below, but you are
allowed to use any Python builtin libraries if you need to
"""
p = 12345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012345679012281

g = 4384165182867240584805930970951575013697

import math, hashlib, random

"""
You are behaving as the man-in-the-middle. You can receive messages from either alice or bob, and send messages onward to alice or bob. You must ensure that all messages eventually get through (in the order sent) because there is a handshaking process before the secret flag will be sent.

To earn points, print the plaintext of all messages you see and decrypt.
If the secret flag that Alice sends to Bob is printed then you earn points.

The four arguments passed are non-blocking functions to send/receive, see
the provided code (which just passes all messages through) to see how they
are used.
"""

def encrypt(msg, key):
    nonce = random.randint(int(1e10), int(1e11))
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()
    msg = msg.encode()
    msg_enc = bytes([msg[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg))])
    return str(nonce) + "+" + msg_enc.hex()  # msg_enc.hex() = 将字节转换为十六进制

def decrypt(msg_enc, key):
    nonce = int(msg_enc.split("+")[0])  # split() 通过指定分隔符对字符串进行切片
    msg_enc = bytes.fromhex(msg_enc.split("+")[1])  # bytes.fromhex(s) 将十六进制字符串转换为字节
    enc_key = hashlib.sha512((str(nonce) + str(key)).encode()).digest()
    msg = [msg_enc[i] ^ enc_key[i % len(enc_key)] for i in range(len(msg_enc))]
    msg = bytes([x if x < 128 else ord(" ") for x in msg]).decode()
    return msg

def mitm_filter(msg):
    """
        if i < 2:  # 第1,2次传输信息为握手 其为直接明文传输 将其进行黑化 使得握手过程中的公钥都为1 这样他们生成的共享密钥也为1
        if i == 0:
            AtoB_SHARED_SECRET = msg  # Alice发送给Bob的Alice的公钥
            print(f"[MITM] SHARED from Alice to Bob msg={msg}")
            # 丢弃 构造黑化Alice的公钥
            new_msg = 1
            i += 1
            return new_msg
        if i == 1:
            BtoA_SHARED_SECRET = msg  # Bob发送给Alice的Bob的公钥
            print(f"[MITM] SHARED from Bob to Alice msg={msg}")
            # 丢弃 构造黑化Bob的公钥
            new_msg = 1
            i += 1
            return new_msg
    """
    # 避免使用计数器 直接对传输信息进行字符串识别处理 有'+'则为加密信息 无'+'则为明文信息
    if '+' not in msg:
        new_msg = 1
        return new_msg

    # 这时msg是单次加密的nonce及加密后再次进行十六进制化的密文 通过 '+' 分割
    # nonce = int(msg.split("+")[0])
    # msg_enc = bytes.fromhex(msg.split("+")[1])  # bytes.fromhex(s) 将十六进制字符串转换为字节
    # print(f"[MITM] MMM from Alice to Bob nonce={nonce} msg_enc={msg_enc}")
    # 这时的 key 已经是构造后的结果
    SHARED_SECRET = 1
    # 解密
    print(f"[MITM] start decrypt msg={msg}")
    msg_hack = decrypt(msg, SHARED_SECRET)
    print(f"[+] from hack msg={msg_hack}")
    return msg

    # 倒数第二次 为Alice发送给Bob的flag

def mitm(send_to_alice, send_to_bob, recv_from_alice, recv_from_bob):
    # pass through all messages unchanged
    while True:
        msg = recv_from_alice()  # 接受来自Alice的消息
        if msg is not None:
            print(f"[MITM] Message from Alice to Bob msg={msg}")

            # msg = mitm_filter(msg)  # 中间人分析函数
            # mitm_filter() 如果有返回值，则将返回值赋值给 msg
            # if mitm_filter(msg) is not None:
            #     msg = mitm_filter(msg)
            msg = mitm_filter(msg)

            send_to_bob(msg)

        msg = recv_from_bob()  # 接受来自Bob的消息
        if msg is not None:
            print(f"[MITM] Message from Bob to Alice msg={msg}")

            msg = mitm_filter(msg)

            send_to_alice(msg)
#math #crypto

Similar articles: