不经意传输

发表于 更新于 阅读次数： 本文字数： 5k 阅读时长 ≈ 9 分钟

owo

周末做到一道不经意传输的题，这也是个新知识点，总结学习一下。(ref:不经意传输 | Lazzaro)

概念

​ 不经意传输（Oblivious Transfer, OT）是一种可保护隐私的双方通信协议、接受者的隐私不被发送者所知道，使通信双方以一种选择模糊化的方式传送消息。抽象地讲，就是A给B发消息，A却不知道B收到的是啥，一般的思路就是A要多发一些消息然后让B去选择有需要的，如果是这样的话，同时还应该保证B不会多知道他本不应该知道的消息。不经意传输可以分为1选1、2选1、n选1、n选k多种不经意传输协议。

对于2选一的攻击，重点是以下攻击方式

O0TVxx.png

例题

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
import secrets
from Crypto.PublicKey import RSA

DEATH_CAUSES = [
	'a fever',
	'dysentery',
	'measles',
	'cholera',
	'typhoid',
	'exhaustion',
	'a snakebite',
	'a broken leg',
	'a broken arm',
	'drowning',
]

def run_ot(key, msg0, msg1):
	'''
	https://en.wikipedia.org/wiki/Oblivious_transfer#1–2_oblivious_transfer
	'''
	x0 = secrets.randbelow(key.n)
	x1 = secrets.randbelow(key.n)
	print(f'n: {key.n}')
	print(f'e: {key.e}')
	print(f'x0: {x0}')
	print(f'x1: {x1}')
	v = int(input('v: '))
	assert 0 <= v < key.n, 'invalid value'
	k0 = pow(v - x0, key.d, key.n)
	k1 = pow(v - x1, key.d, key.n)
	m0 = int.from_bytes(msg0.encode(), 'big')
	m1 = int.from_bytes(msg1.encode(), 'big')
	c0 = (m0 + k0) % key.n
	c1 = (m1 + k1) % key.n
	print(f'c0: {c0}')
	print(f'c1: {c1}')

if __name__ == '__main__':
	with open('flag.txt') as f:
		flag = f.read().strip()

	print('=== CHOOSE YOUR OWN ADVENTURE: Vorpal Sword Edition ===')
	print('you enter a cave.')

	for _ in range(64):
		print('the tunnel forks ahead. do you take the left or right path?')
		key = RSA.generate(1024)
		msgs = [None, None]
		page = secrets.randbits(32)
		live = f'you continue walking. turn to page {page}.'
		die = f'you die of {secrets.choice(DEATH_CAUSES)}.'
		msgs = (live, die) if secrets.randbits(1) else (die, live)
		run_ot(key, *msgs)
		page_guess = int(input('turn to page: '))
		if page_guess != page:
			exit()

	print(f'you find a chest containing {flag}')

首先根据攻击方式构造v=(scale^e * x0 - x1) / (scale^e - 1) mod n，分析服务端脚本不难发现只有当我们知道的信息是live的时候才能得到正确的page通过guess、而die的死亡信息是已知的，那么思路就很明确了，遍历死亡消息，并尝试两种可能情况，die在m1，求解m0 = (s + m1) // scale或者die在m0，求解m1 = scale$_$m0 - s。值得注意的是，在die在m0，求解m1 = scalem0 - s这种情况中m1可能为负，此时要加上n保证值为正。最后循环猜64次即可

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
import random

from pwn import *
import re

from tqdm import trange

context.log_level = 'error'
scale = random.getrandbits(100)
print(scale)

DEATH_CAUSES = [
    'a fever', 'dysentery', 'measles', 'cholera', 'typhoid',
    'exhaustion', 'a snakebite', 'a broken leg', 'a broken arm', 'drowning'
]
die_messages = [f'you die of {cause}.' for cause in DEATH_CAUSES]
die_ints = [int.from_bytes(msg.encode(), 'big') for msg in die_messages]


def extract_page(byte_data):
    """从字节流中提取页码"""
    try:
        decoded = byte_data.decode(errors='ignore')
        match = re.search(r'turn to page (\d+)', decoded)
        return int(match.group(1)) if match else None
    except:
        return None


def solve_round(conn):
    # 获取RSA参数和随机数x0, x1
    conn.recvuntil('n: ')
    n = int(conn.recvline().strip())
    conn.recvuntil('e: ')
    e = int(conn.recvline().strip())
    conn.recvuntil('x0: ')
    x0 = int(conn.recvline().strip())
    conn.recvuntil('x1: ')
    x1 = int(conn.recvline().strip())

    # 正确构造v的表达式：(scale^e * x0 - x1) / (scale^e - 1) mod n
    scale_e = pow(scale, e, n)
    denominator = (scale_e - 1) % n
    try:
        inv_denominator = pow(denominator, -1, n)
    except ValueError:
        return None  # 分母不可逆，概率极低
    v = (scale_e * x0 - x1) * inv_denominator % n


    # 发送v并获取密文c0, c1
    conn.sendlineafter('v: ', str(v))
    conn.recvuntil('c0: ')
    c0 = int(conn.recvline().strip())
    conn.recvuntil('c1: ')
    c1 = int(conn.recvline().strip())

    # 计算s = scale*m0 - m1
    s1=c0+c1
    s = (scale * c0 - c1) % n

    # 遍历死亡消息，尝试两种可能情况
    page = None
    # 情况1：die在m1，求解m0 = (s + m1) // scale
    for die_m1 in die_ints:
        m0_candidate = (s + die_m1)
        if m0_candidate % scale != 0:
            continue
        m0 = m0_candidate // scale
        m0_bytes = m0.to_bytes(128, 'big').lstrip(b'\x00')
        page = extract_page(m0_bytes)
        if page is not None:
            return page

    # 情况2：die在m0，求解m1 = scale*m0 - s
    for die_m0 in die_ints:
        m1_candidate = (scale * die_m0 - s)
        if m1_candidate < 0:
            m1_candidate += n
        m1_bytes = m1_candidate.to_bytes(128, 'big').lstrip(b'\x00')
        page = extract_page(m1_bytes)
        if page is not None:
            return page

    return page  # 未找到页码
def main():
    while True:
        conn = remote('dicec.tf', 31001)  # 替换为实际地址
        conn.recvuntil(b'you enter a cave.\n')
        kkk = 0
        for _ in trange(64):
            page = solve_round(conn)
            print(page)
            conn.sendlineafter(b'turn to page: ', str(page).encode())
            if page is None:
                print(kkk, "Failed")
                conn.close()
                time.sleep(1)
                break
            kkk += 1
        # 获取flag
        if kkk != 64:
            continue
        conn.recvuntil(b'you find a chest containing ')
        flag = conn.recvline().decode().strip()
        print(f'Flag: {flag}')
        conn.close()
        break


if __name__ == '__main__':
    main()