Đây là một bài trong series Cùng giải Cryptopals!.
Các bạn nên tự làm hoặc vừa đọc vừa làm thay vì đọc lời giải trực tiếp.
Challenge 49: CBC-MAC Message Forgery
Chúng ta viết code server trước vì nó dễ (xin lỗi các bạn không có GUI đâu vì đến lúc tấn công thì cũng đâu có ai dùng GUI). Trong server có bao gồm một hàm chuyên đi ký, chỉ dành cho những người có quyền (hiện tại là tất cả mọi người, nên nếu ai clone code này về làm server nhớ sửa nhé). /s
from flask import Flask, request
from utils import generate_key, AES_encrypt
import re
app = Flask(__name__)
key = generate_key(16)
@app.route('/sign', methods=['POST'])
def sign():
# some sick authorization here
if False: return 'NG', 403
try:
data = request.json()
msg = f"from={data['acc_from']}&to={data['acc_to']}&amount={data['amount']}".encode()
except:
return 'NG', 400
iv = generate_key()
mac = AES_encrypt(key, msg, 'cbc', iv)[-16:]
return msg + iv + mac
@app.route('/send', methods=['POST'])
def send_monii():
data = request.data
if len(data) <= 32: return 'NG', 400
mac = data[-16:]
iv = data[-32:-16]
msg = data[:-32]
if AES_encrypt(key, msg, 'cbc', iv)[-16:] != mac:
return 'NG', 400
try:
# the three vals returned are acc_from, acc_to, and amount
re.match(r'^from=(\d+)&to=(\d+)&amount=(\d+)$', msg.decode()).groups()
except:
return 'NG', 400
return 'OK', 200
if __name__ == '__main__':
app.run(port=9000, debug=True)
Giả sử ban đầu attacker có 2 account với IDs là 6 và 9 (nice), và account cần hack có ID là 8. Tin nhắn chúng ta có MAC là
from=6&to=9&amou
nt=1000000\x06\x06\x06\x06\x06\x06
Tin nhắn chúng ta cần MAC là
from=8&to=9&amou
nt=1000000\x06\x06\x06\x06\x06\x06
Đến hẹn lại lên, như các bài trước, đây là biểu đồ encryption của CBC:
Nhìn qua giản đồ chúng ta có thể thấy để ciphertext không đổi gì, ta chỉ cần sửa các bit ở "plaintext" block 1 để ra payload chúng ta muốn, và sửa IV để ciphertext của block 1 không thay đổi. Ở đây, chúng ta cần thay đổi byte thứ 6 từ \x36
(ord('6')
) thành \x38
(ord('8')
).
valid = requests.post('http://localhost:9000/sign', json={
'acc_from': 6, 'acc_to': 9, 'amount': 1000000
}).content
assert requests.post('http://localhost:9000/send', data=valid).status_code == 200
payload = list(valid)
payload[5] = ord('8')
payload[5 + 16 * 2] ^= ord('6') ^ ord('8')
payload = bytes(payload)
assert payload[:-32] == b'from=8&to=9&amount=1000000'
assert requests.post('http://localhost:9000/send', data=valid).status_code == 200
Để ý rằng tấn công này chỉ hoạt động nếu
from
vàto
nằm trong cùng block đầu tiên- Tổng số chữ số của
from
vàto
giữa cũ và mới không thay đổi
Gói gọn cả 2 yêu cầu trên, block 2 trở đi phải không thay đổi.
Cho phần 2 của bài này, chúng ta lại viết thêm code server:
@app.route('/sign2', methods=['POST'])
def sign2():
# some sick authorization here
if False: return ('NG', 403)
try:
data = request.json
msg = f"from={data['acc_from']}&txlist=" + \
';'.join([f'{x[0]}:{x[1]}' for x in data['txlist'].items()])
msg = msg.encode()
except:
return 'NG', 400
mac = AES_encrypt(key, pkcs7_pad(msg), 'cbc')[-16:]
return msg + mac
@app.route('/send2', methods=['POST'])
def send2():
data = request.data
if len(data) <= 16: return 'NG', 400
mac = data[-16:]
msg = data[:-16]
if AES_encrypt(key, pkcs7_pad(msg), 'cbc')[-16:] != mac:
return 'NG', 400
try:
# learn regex, it's fun
re.match(rb'^from=(\d+)&txlist=([^:;]+):([^;]+)(?:;([^:;]+):([^;]+))*$', msg).groups()
except:
return 'NG', 400
return 'OK', 200
Các bạn có thể thấy code regex đã được sửa từ việc bắt số sang thành bắt tất cả mọi thứ (và phó mặc sanitization sau). Có 2 lý do:
- Ban đầu mình giả thiết là số tiền là một số nguyên, nhưng thực thế không chắc là như vậy. Mình có thể viết thêm regex để handle phần lẻ đằng sau, nhưng thôi.
- Đề bài hướng dẫn sử dụng MAC làm IV cho tin nhắn extension. Điều đó đòng nghĩa với việc cách tấn công này sẽ không thể xoá được padding đang lưu trong các transaction cũ của nạn nhân, và sẽ trở thành byte rác. Nếu server auto reject request lúc nhận được rác thì attack này sẽ không thành.
Quay lại đề bài, chúng ta intercept được tin nhắn của người dùng như sau: nạn nhân ID 8 gửi 123 thiên hà đồng đến account ID 7:
from=8&txlist=7:
123\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d
Request này kẻ tấn công nhận được, và lấy được kết quả .
Attacker có thể lấy được MAC cho tin nhắn sau (do những account đó họ quản lý):
from=6&txlist=0:
1;9:1000000\x05\x05\x05\x05\x05
Đây sẽ là MAC của payload cuối cùng.
Chúng ta sẽ sử dụng tấn công này trên Wikipedia (thú thực bài này khó quá mình đã phải đọc thay vì tự nghĩ ra).
Chúng ta sẽ sửa "plaintext" của chúng ta thành
from=8&txlist=7:
123\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d\x0d
[ 16 bytes rác ] <- from=6&txlist=0: XOR MAC_0
1;9:1000000\x05\x05\x05\x05\x05
Nhắc lại cái diagram thần thánh của CBC:
Để ý ở block 3 của payload plaintext, block 1 của attacker XOR sẽ được encrypt với IV là , chính là ciphertext của block trước (block 2 của victim). Điều này tương đương với block 1 của attacker's plaintext được encrypt với IV 0, khiến ciphertext không đổi. Hệ quả là block 4 encrypted với cùng IV như bên attacker, và MAC của payload sẽ giống với MAC của attacker.
victim_mac = requests.post('http://localhost:9000/sign2', json={
'acc_from': 8,
'txlist': {
7: 123
}
}).content
assert requests.post('http://localhost:9000/send2', data=victim_mac).status_code == 200
# get victim's MAC
victim_content = victim_mac[:-16]
victim_mac = victim_mac[-16:]
# get attacker's MAC
attacker_mac = requests.post('http://localhost:9000/sign2', json={
'acc_from': 6,
'txlist': {
0: 1,
9: 1000000
}
}).content
assert requests.post('http://localhost:9000/send2', data=attacker_mac).status_code == 200
attacker_content = attacker_mac[:-16]
attacker_mac = attacker_mac[-16:]
# craft payload
payload = pkcs7_pad(victim_content) + stream_xor(attacker_content[:16], victim_mac) + attacker_content[16:] + attacker_mac
assert requests.post('http://localhost:9000/send2', data=payload).status_code == 200
# make sure payload sends me 1M bucks
params = dict(map(lambda x: x.split(b'='), payload.split(b'&')))
assert params[b'from'] == b'8' and b'9:1000000' in params[b'txlist']
Để tránh bị tấn công kiểu này, có 2 cách chống (lấy từ Wiki nốt):
- Bao gồm độ dài tin nhắn ở đầu chuỗi cần MAC.
- Mã hoá MAC đầu ra bằng một key khác.
Challenge 50: Hashing with CBC-MAC
Đầu tiên là tạo hàm hash cái đã:
def hash_cbc(msg: bytes) -> bytes:
return AES_encrypt(b"YELLOW SUBMARINE", pkcs7_pad(msg), 'cbc')[-16:]
Các block của XSS gốc là
alert('MZA who w
as that?');\n\x04\x04\x04
Làm gần như tương tự bài trước, chúng ta sẽ tạo payload
alert('Ayo, the[space]
Wu is back!');//
alert('MZA who w XOR hash(above)
as that?');\n\x04\x04\x04
Thay vì việc block thứ 3 có IV là cipher của block thứ 2, chúng ta sẽ XOR nó với cipher đó để tương ứng với 0 IV (giống block đầu của chuỗi gốc).
original = b"alert('MZA who was that?');\n"
assert hexlify(hash_cbc(original)) == b'296b8d7cb78a243dda4d0a61d33bbdd1'
modified = b"alert('Ayo, the Wu is back!');//"
modified += \
stream_xor(
original[:16],
AES_encrypt(b"YELLOW SUBMARINE", modified, 'cbc')[-16:]
) + original[16:]
print(hexlify(hash_cbc(modified)), b'296b8d7cb78a243dda4d0a61d33bbdd1')
Mình sẽ không làm extra credit vì lười Và thực tế thì cũng có vẻ không cần dùng đến.
Easter egg: MZA là Method-Man, một thành viên của nhóm rap nổi tiếng Wu-Tang Clan. XSS string trong bài
MZA who was that?
và
Ayo, the Wu is back!
là 2 câu trong lời bài hát Wu-Tang Clan Ain’t Nuthing ta Fuck Wit của Wu-Tang Clan.
Challenge 51: Compression Ratio Side-Channel Attacks
Trước hết, chúng ta viết compression oracle:
- Cho phiên bản dùng CTR/Streaming XOR: độ dài chuỗi sẽ được giữ nguyên.
def compression_oracle(P: bytes):
req = f'POST / HTTP/1.1\nHost: hapless.com\nCookie: sessionid={sessionid}\nContent-Length: {len(P)}\n'.encode() + P
return len(AES_encrypt(generate_key(), compress(req), 'ctr', generate_key(8)))
- Cho phiên bản dùng CBC: độ dài chuỗi sẽ bị pad đến bội số của 16 tiếp theo.
def compression_oracle(P: bytes):
req = f'POST / HTTP/1.1\nHost: hapless.com\nCookie: sessionid={sessionid}\nContent-Length: {len(P)}\n'.encode() + P
return len(AES_encrypt(generate_key(), pkcs7_pad(compress(req)), 'cbc', generate_key(16)))
Và code này sẽ giải được cả 2 phiên bản:
payload_prefix = 'sessionid='
charset = ascii_letters + digits + '+='
candidates = ['']
final_candidate = None
while not final_candidate:
min_compressed = None
min_candidates = []
for prefix, char in product(candidates, charset):
if '=' in prefix and char != '=': continue
sessid = prefix + char
payload = (payload_prefix + sessid).encode()
compressed_size = [compression_oracle(b'\n'.join([payload] * 2 ** i)) for i in range(4)]
if min_compressed is None:
min_compressed = compressed_size
min_candidates = [sessid]
elif min_compressed >= compressed_size:
if min_compressed == compressed_size:
min_candidates.append(sessid)
else:
min_compressed = compressed_size
min_candidates = [sessid]
# filter the candidates
candidates = []
for candidate in min_candidates:
if '=' in candidate:
if len(min_candidates) < 50:
final_candidate = b64encode(b64decode(candidate + '==')).decode()
break
else:
candidates.append(candidate)
assert sessionid == final_candidate
Về cơ bản thì nội dung code giống như trong hướng dẫn đề bài. Tuy nhiên, để ý rằng hiện tại trong code mình có một số nâng cấp theo các heuristics:
- Chỉ chấp nhận đáp án nếu số trường hợp cần xem xét tiếp theo ít hơn 50. Con số 50 ở đây được chọn bừa, nó thấp hơn 63 ký tự có thể thử mỗi chữ cái.
- Thử lấy compressed size với nhiều khả năg lặp lại. Với mỗi string, code sẽ lấy kết quả compressed size với các payload bao gồm 1/2/4/8 chuỗi session ID lặp lại. Chúng ta biết được rằng ở settings nào thì size của chuỗi đúng cũng bé hơn hoặc bằng chuỗi sai; và làm thế sẽ giúp chúng ta giảm được sai số khi nén bit level bị làm tròn theo byte và làm tròn lên bội số của 16 bytes khi sử dụng CBC.
- Dừng ở
=
vì base64 thường có padding. Nếu chuỗi ban đầu không cần padding thì có thể sẽ không trả về kết quả (vì chúng ta có luôn có thể điền tiếp chữ cái để tạo ra chuỗi base64 mới).
Easter egg: Cookie sau khi đã decode từ base64 là
Never reveal the Wu-Tang Secret!
là lyrics bài You Don't Want To Fuck With Me của Ol' Dirty Bastard.
Challenge 52: Iterated Hash Function Multicollisions
Đầu tiên là các hàm tạo hash sử dụng AES-128: Trong đó, hàm f
tạo ra hash dài 16 bit, và hàm tạo hash dài 24 bit. Ngoài ra, do mỗi vòng lặp sẽ ra được hash mới dài 128 bit, hash trong quá trình sẽ bị cắt từ bên trái vào, và pad từ bên phải qua, lúc cần thiết.
def f(msg: bytes, h: bytes = b'\x06\x09'):
# output is 16 bit/2 bytes
assert len(h) == 2
assert len(msg) % 16 == 0
for i in range(0, len(msg), 16):
# pads on the right, truncate the left
h = AES_encrypt(msg[i:i+16], pkcs7(h, 14))[-2:]
return h
def g(msg: bytes, h: bytes = b'\x04\x02\x00'):
# output is 24 bit/3 bytes
assert len(h) == 3
assert len(msg) % 16 == 0
for i in range(0, len(msg), 16):
# pads on the right, truncate the left
h = AES_encrypt(msg[i:i+16], pkcs7(h, 13))[-3:]
return h
Tạo ra các counter để xem chúng ta phải thử mất bao nhiêu lần:
f_count = 0
g_count = 0
Generate ra các hash collision cho f
:
# generate 2^12 hash collisions (i.e. 12 blocks)
fragments = []
hashes = [b'\x06\x09']
for i in range(12):
found = {}
for block in product(range(256), repeat=16):
f_count += 1
block = bytes(block)
hash_ = f(block, hashes[i])
if hash_ in found:
found[hash_].append(block)
fragments.append(found[hash_])
hashes.append(hash_)
break
else:
found[hash_] = [block]
print('Generating 2^12 f-collisions took', f_count, 'tries.')
Và check từng chuỗi một xem có collide dưới g
không. Chú ý, với các khác nhau thì sau khi ghép blocks đầu tiên lại ra các f
-hash khác nhau, nên khi check collision dưới g
nhớ reset danh sách hash mỗi lần thêm block.
# check for g collisions
found = False
trials = [b'']
for i in range(12):
for j in range(len(trials)):
trials.append(trials[j] + fragments[i][0])
trials[j] += fragments[i][1]
g_hashes = {}
for msg in trials:
g_count += 1
g_hash = g(msg)
if g_hash in g_hashes:
msg_ = g_hashes[g_hash]
found = True
break
else:
g_hashes[g_hash] = msg
if found: break
if found:
print('Found collision!')
assert f(msg) == f(msg_) and g(msg) == g(msg_)
print('Total calls to check for g-collisions:', g_count)
Và nếu không chạy thì chúng ta thử tiếp:
else:
print('Collision for g not found. Generating more...', g_count)
i = 12
while not found:
# generate new f
found = {}
for block in product(range(256), repeat=16):
f_count += 1
block = bytes(block)
hash_ = f(block, hashes[i])
if hash_ in found:
found[hash_].append(block)
fragments.append(found[hash_])
hashes.append(hash_)
break
else:
found[hash_] = [block]
# recheck g collisions
for j in range(len(trials)):
trials.append(trials[j] + fragments[i][0])
trials[j] += fragments[i][1]
g_hashes = {}
for msg in trials:
g_count += 1
g_hash = g(msg)
if g_hash in g_hashes:
msg_ = g_hashes[g_hash]
found = True
break
else:
g_hashes[g_hash] = msg
if found:
print('Found collision!')
assert f(msg) == f(msg_) and g(msg) == g(msg_)
print('Total calls to generate f-collisions:', f_count, 'tries.')
print('Total calls to check for g-collisions:', g_count)
else:
# life goes on
i += 1
Kết quả chúng ta có (không có random nên bạn có thể reproduce được):
Generating 2^12 f-collisions took 3454 tries.
Found collision!
Total calls to check for g-collisions: 4593
Lý do tại sao g
dễ ra collision như vậy là bởi vì một tấn công có tên là Birthday Attack. Khái niệm này đọc 1-2 lần có thể vẫn hơi khó hiểu, có gì bạn có thể để nó ngấm một chút nha. Đại khái ý tưởng chính là như sau: trong một lớp học (tầm 30-40 người?), tìm được một người cùng ngày sinh với mình rất khó (vì chốt ngày sinh của họ), nhưng tìm hai người có cùng ngày sinh với nhau thì dễ hơn rất nhiều (vì ngày sinh đó không bị cố định). Tìm hai chuỗi có cùng hash cũng vậy.
Challenge 53: Kelsey and Schneier's Expandable Messages
Có một điều bạn nên nhớ: padding của bài này không giống như challenge 52 (PKCS5/7), mà là padding của Merkle-Damgard hash — nghĩa là, padding có phụ thuộc vào độ dài tin nhắn, và yêu cầu second preimage của chúng ta phải có độ dài giống với tin nhắn ban đầu. Vì vậy, cho dù có thể implement tấn công này với MD4/5/SHA-1, chúng ta sẽ tấn công với hàm hash đồ chơi từ challenge trước, nhưng với block size là 8 bytes và output là 4 bytes cho nhanh (vì block của MD5/SHA-1 đều rất lớn: 64 bytes).
Đầu tiên chúng ta implement lại hàm hash: mình có chỉnh sửa là nếu hash một tin nhắn đầy đủ (partial=False
) thì sẽ trả về tất cả các state của hash từ đầu đến cuối.
# given block_size, hash_size, original_state
assert 16 % block_size == 0
def toy_hash(msg: bytes, h: bytes = original_state, partial=True):
assert len(h) == hash_size
if partial:
assert len(msg) % block_size == 0
else:
msg = pkcs7(msg, block_size - (len(msg) % block_size))
states = []
for i in range(0, len(msg), block_size):
# pads on the right, truncate the left
h = AES_encrypt(msg[i : i + block_size] * (16 // block_size),
pkcs7(h, 16 - hash_size))[-hash_size:]
if not partial:
states.append(h)
if partial:
return h
else:
return states
Hàm kiếm hash collision từ 2 state khác nhau:
def get_collision(state1, state2):
hashes1 = {}
hashes2 = {}
for block in product(range(256), repeat=block_size):
block = bytes(block)
hash1 = toy_hash(block, state1)
hash2 = toy_hash(block, state2)
if hash1 in hashes1: continue
else: hashes1[hash1] = block
if hash2 in hashes2: continue
else: hashes2[hash2] = block
union = hashes1.keys() - hashes2.keys()
if len(union) >= 1:
state = union.pop()
return hashes1[state], hashes2[state], state
Tạo tin nhắn cần collide dài blocks (+ ít dư):
# given msg_log_len
# if msg_log_len = 10, then it's 1024 blocks + less than a block
original = generate_key(2 ** msg_log_len * block_size + randint(1, block_size - 1))
states = dict((v, k) for k, v in enumerate(toy_hash(original, partial=False)) if msg_log_len <= k < 2 ** msg_log_len)
Tạo ra các block để nối lại thành expandable message:
# build the expandable message
state = original_state
messages = []
for i in range(msg_log_len):
prefix = generate_key(2 ** (msg_log_len - i - 1) * block_size)
state2 = toy_hash(prefix, state)
msg1, msg2, state = get_collision(state, state2)
messages.append([msg1, prefix + msg2])
Tìm block cầu nối: đây là phần sẽ chiếm nhiều thời gian nhất, vì tìm được collision hay không phụ thuộc rất nhiều vào nhân phẩm. Lúc tìm được block cầu nối, code sẽ nối các phần cần thiết để trả về luôn chuỗi cùng hash:
# find the connector block
for block in product(range(256), repeat=block_size):
block = bytes(block)
hash_ = toy_hash(block, state)
if hash_ in states:
block_count = states[hash_]
# get the expandable message of desired length
crafted = b''
crafted_block_count = block_count - msg_log_len
for i, (c1, c2) in enumerate(messages):
if crafted_block_count < 2 ** (msg_log_len - i - 1):
crafted += c1
else:
crafted += c2
crafted_block_count -= 2 ** (msg_log_len - i -1)
crafted += block + original[block_size * (block_count + 1):]
break
Và check xem code chúng ta có chạy đúng không:
assert original != crafted and len(original) == len(crafted) and \
toy_hash(original, partial=False)[-1] == toy_hash(crafted, partial=False)[-1]
Challenge 54: Kelsey and Kohno's Nostradamus Attack
Về cơ bản thì tấn công này khá giống với challenge 52, chỉ khác ở chỗ là chúng ta có thể chọn được prefix ban đầu: ở challenge 52, tin nhắn đều nhìn như rác do ngẫu nhiên, nhưng ở đây các tin nhắn sẽ có khoảng đầu có nghĩa (được chọn). Sử dụng các primitives có sẵn từ challenge 53 ở trên, bài này sẽ trở nên rất dễ:
# for some fixed k
k = 10
# and some initial messages of the same length filling a whole block
msgs = [...]
lens = map(len, msgs)
assert len(msg) == 2 ** k and max(lens) == min(lens) and min(lens) % block_size == 0
msgs = [msgs]
hashes = [list(map(hash_fn, msgs))]
tails = []
for i in range(k):
tail = []
states = []
for j in range(0, 2 ** i, 2):
msg1, msg2, state = get_collision(hashes[i][j], hashes[i][j+1])
tail.append(msg1)
tail.append(msg2)
states.append(state)
tails.append(tail)
hashes.append(states)
# then do things with hashes[-1][-1]
Challenge 55: MD4 Collisions
Chúng ta implement trước vài hàm giúp đỡ, trong đó có
- Lấy một bit tại một vị trí nào đó trong một số nguyên,
- Sửa các bit theo yêu cầu; yêu cầu đó là một
dict
lưu vị trí cần sửa và giá trị mới tại vị trí đó, - Tính state mới sau 1 loop round 1,
- Sửa block tin nhắn để state mới đúng với yêu cầu của thuật toán.
def bit_at(num, i):
# 0 is least significant
return (num >> i) & 1
def correct(num, rules):
# rules is dict({idx, bit_value})
for idx, val in rules.items():
assert val in (0, 1)
if val == 0:
num ^= (bit_at(num, idx) << idx)
else:
num |= (1 << idx)
return num
def round1(a, b, c, d, lrot, m):
return leftrotate((a + F(b, c, d) + m) & 0xFFFFFFFF, lrot)
def fix1(a, b, c, d, lrot, old_a):
return (leftrotate(a, 32 - lrot) - old_a - F(b, c, d)) % 0x100000000
Do không implement toàn bộ các điều kiện nên code chỉ đơn giản thế này thôi — trong đó hiện tại đã xóc đĩa song song để tăng tốc bruteforce:
from multiprocessing import Process, cpu_count, Value
count = Value('i', 0)
print('Running attack', end='', flush=True)
def search_thread():
global count
while True:
with count.get_lock():
if count.value == -1 or count.value > 2 ** 30: break
count.value += 1
if count.value % (1 << 16) == 0: print('.', end='', flush=True)
if count.value % (9 << 19) == 0: print()
original = generate_key(64)
a, b, c, d = 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476
m = list(struct.unpack("<16I", original))
# condition the collided msg
# rule 1
old_val = a
a = round1(a, b, c, d, 3, m[0])
a = correct(a, {
6: bit_at(b, 6)
})
m[0] = fix1(a, b, c, d, 3, old_val)
# rule 2
old_val = d
d = round1(d, a, b, c, 7, m[1])
d = correct(d, {
6: 0,
7: bit_at(a, 7),
10: bit_at(a, 10)
})
m[1] = fix1(d, a, b, c, 7, old_val)
# rule 3
old_val = c
c = round1(c, d, a, b, 11, m[2])
c = correct(c, {
6: 1,
7: 1,
10: 0,
25: bit_at(d, 25)
})
m[2] = fix1(c, d, a, b, 11, old_val)
# rule 4
old_val = b
b = round1(b, c, d, a, 19, m[3])
b = correct(b, {
6: 1,
7: 0,
10: 0,
25: 0
})
m[3] = fix1(b, c, d, a, 19, old_val)
# rule 5
old_val = a
a = round1(a, b, c, d, 3, m[4])
a = correct(a, {
7: 1,
10: 1,
25: 0,
13: bit_at(b, 13)
})
m[4] = fix1(a, b, c, d, 3, old_val)
# rule 6
old_val = d
d = round1(d, a, b, c, 7, m[5])
d = correct(d, {
13: 0,
18: bit_at(a, 18),
19: bit_at(a, 19),
20: bit_at(a, 20),
21: bit_at(a, 21),
25: 1
})
m[5] = fix1(d, a, b, c, 7, old_val)
# rule 7
old_val = c
c = round1(c, d, a, b, 11, m[6])
c = correct(c, {
12: bit_at(d, 12),
13: 0,
14: bit_at(d, 14),
18: 0,
19: 0,
20: 1,
21: 0
})
m[6] = fix1(c, d, a, b, 11, old_val)
# rule 8
old_val = b
b = round1(b, c, d, a, 19, m[7])
b = correct(b, {
12: 1,
13: 1,
14: 0,
16: bit_at(c, 16),
18: 0,
19: 0,
20: 0,
21: 0
})
m[7] = fix1(b, c, d, a, 19, old_val)
# rule 9
old_val = a
a = round1(a, b, c, d, 3, m[8])
a = correct(a, {
12: 1,
13: 1,
14: 1,
16: 0,
18: 0,
19: 0,
20: 0,
22: bit_at(b, 22),
21: 1,
25: bit_at(b, 25)
})
m[8] = fix1(a, b, c, d, 3, old_val)
# rule 10
old_val = d
d = round1(d, a, b, c, 7, m[9])
d = correct(d, {
12: 1,
13: 1,
14: 1,
16: 0,
19: 0,
20: 1,
21: 1,
22: 0,
25: 1,
29: bit_at(a, 29)
})
m[9] = fix1(d, a, b, c, 7, old_val)
# rule 11
old_val = c
c = round1(c, d, a, b, 11, m[10])
c = correct(c, {
16: 1,
19: 0,
20: 0,
21: 0,
22: 0,
25: 0,
29: 1,
31: bit_at(d, 31)
})
m[10] = fix1(c, d, a, b, 11, old_val)
# rule 12
old_val = b
b = round1(b, c, d, a, 19, m[11])
b = correct(b, {
19: 0,
20: 1,
21: 1,
22: bit_at(c, 22),
25: 1,
29: 0,
31: 0
})
m[11] = fix1(b, c, d, a, 19, old_val)
# rule 13
old_val = a
a = round1(a, b, c, d, 3, m[12])
a = correct(a, {
22: 0,
25: 0,
26: bit_at(b, 26),
28: bit_at(b, 28),
29: 1,
31: 0
})
m[12] = fix1(a, b, c, d, 3, old_val)
# rule 14
old_val = d
d = round1(d, a, b, c, 7, m[13])
d = correct(d, {
22: 0,
25: 0,
26: 1,
28: 1,
29: 0,
31: 1
})
m[13] = fix1(d, a, b, c, 7, old_val)
# rule 15
old_val = c
c = round1(c, d, a, b, 11, m[14])
c = correct(c, {
18: bit_at(d, 18),
22: 1,
25: 1,
26: 0,
28: 0,
29: 0
})
m[14] = fix1(c, d, a, b, 11, old_val)
# rule 16
old_val = b
b = round1(b, c, d, a, 19, m[15])
b = correct(b, {
18: 0,
25: 1,
26: 1,
28: 1,
29: 0
})
m[15] = fix1(b, c, d, a, 19, old_val)
# edit old msg to have desired conditions
msg1 = struct.pack("<16I", *m)
# craft the collision
m[1] = (m[1] + (1 << 31)) % 0x100000000
m[2] = (m[2] + (1 << 31) - (1 << 28)) % 0x100000000
m[12] = (m[12] - (1 << 16)) % 0x100000000
msg2 = struct.pack("<16I", *m)
if MD4(msg1).hexdigest() == MD4(msg2).hexdigest():
print('\nFound a collision!')
print(msg1)
print(msg2)
with count.get_lock():
count.value = -1
break
procs = [Process(target=search_thread) for _ in range(cpu_count())]
for p in procs:
p.start()
for p in procs:
p.join()
Trong code, mình có implement 16 rules đầu tiên, vì nó chỉ đụng vào round đầu tiên. Round thứ 2 khi sửa sẽ đụng vào các phần của tin nhắn đã sửa từ round 1 nên phức tạp và mình không làm Đằng nào cũng nhiều gấp 16 lần số rule trong hướng dẫn rồi.
Sau 3 tiếng chạy code trên 3 server khoẻ hơn Phạm Văn Mách cùng lúc:
Found a collision!
b'\x07\xa1"\x1c\x10\xba(#\xc3\x1d?\xbb\xf9:K\x18\x0c\xa2\x9f\x8d\xa3\x9d\xf9\xb9\x04\x0f\xcf\xa7!zi\x90\x8d\xaeS\xba\xd9\x0b\xa0~\xe9p\xcckg\xa0\x8e,*\xdc\xa9\x8eX5\xf5<\xa3\x80\xce\xd3\x81\x89}\x00'
b'\x07\xa1"\x1c\x10\xba(\xa3\xc3\x1d?+\xf9:K\x18\x0c\xa2\x9f\x8d\xa3\x9d\xf9\xb9\x04\x0f\xcf\xa7!zi\x90\x8d\xaeS\xba\xd9\x0b\xa0~\xe9p\xcckg\xa0\x8e,*\xdc\xa8\x8eX5\xf5<\xa3\x80\xce\xd3\x81\x89}\x00'
Taken 33350994 trials.
Tầm cú xóc đĩa.
Thêm một kết quả khác cho dân chơi:
Found a collision!
b"'N]\xb7\x81Cr\x8c\n\xb4\x8a\x83\xecx\xf1\nC\x90\xc1\x9d \x0e>\x95_\xae\x8a\xd1dp\x9d\x10\xf2\xf1\x86\x06\xbe\xe0\xed@\xf0\xca\x14\xd0\x07\xcc\xdc\x0fo&\xfb\x13\x8eLa_\x80\xb7\xb7\xb4\xa0D\x9fF"
b"'N]\xb7\x81Cr\x0c\n\xb4\x8a\xf3\xecx\xf1\nC\x90\xc1\x9d \x0e>\x95_\xae\x8a\xd1dp\x9d\x10\xf2\xf1\x86\x06\xbe\xe0\xed@\xf0\xca\x14\xd0\x07\xcc\xdc\x0fo&\xfa\x13\x8eLa_\x80\xb7\xb7\xb4\xa0D\x9fF"
Taken 70199882 trials.
Xấp xỉ lần quay vòng nhân phẩm.
Debug với chờ kết quả mấy cái này làm mình nghĩ lại về việc làm về crypto...
Challenge 56: RC4 Single-Byte Biases
Bài này thực tế mình cũng có chạy song song hoá (chứ không thì bao giờ mới xong...) Nhưng mà, để cho đơn giản và dễ hiểu thì mình chỉ đưa code tuyến tính thôi.
Đầu tiên là xây dựng oracle:
from Crypto.Cipher import ARC4
cookie = b64decode('QkUgU1VSRSBUTyBEUklOSyBZT1VSIE9WQUxUSU5F')
def oracle(msg: bytes):
return ARC4.new(generate_key()).encrypt(msg + cookie)
Mỗi lần query oracle là chúng ta sẽ có một/hai ứng cử viên cho chữ cái ở một vị trí nào đó. Chúng ta lưu lại số lần mỗi ứng cử viên xuất hiện để sau chọn giá trị có tần suất cao nhất:
msglen = len(oracle(b''))
choice = []
for i in range(msglen):
row.append([0] * 256)
Và query lần tổng cộng:
for padlen in range(32):
for _ in range(2 ** 27):
encrypted = oracle(b'A' * padlen)
idx = 15 - padlen
if 0 <= idx < msglen:
choice[idx][encrypted[15] ^ 240] += 1
idx = 31 - padlen
if 0 <= idx < msglen:
choice[idx][encrypted[31] ^ 224] += 1
Tái tạo chuỗi gốc và confirm thôi:
bytes_ = []
for freq in choice:
bytes_.append(freq.index(max(freq)))
assert cookie == bytes(bytes_)
Easter egg: Không liên quan đến Hip-Hop nữa, nhưng là một historical trivia khá hay. Các bạn có thể (bắt đầu) tìm hiểu thêm ở link Wikipedia này.