现代密码学 实验二

题目一

题目地址：https://www.mysterytwisterc3.org/en/challenges/level-2/aes-key--encoded-in-the-machine-readable-zone-of-a-european-epassport

1.MTC3 AES key — encoded in the machine readable zone of a European ePassport

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
import base64
import hashlib
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


def recover_mrz_character(mrz):
    weights = (7, 3, 1)
    values = {str(i): i for i in range(10)}
    values.update({chr(ord("A") + i): 10 + i for i in range(26)})
    values["<"] = 0

    def checksum(text):
        return sum(values[char] * weights[index % 3] for index, char in enumerate(text)) % 10

    for digit in "0123456789":
        candidate = mrz.replace("?", digit, 1)
        if checksum(candidate[21:27]) == int(candidate[27]):
            return digit
    raise ValueError("missing MRZ character not found")


def set_odd_parity(byte):
    masked = byte & 0xFE
    return masked | (0 if bin(masked).count("1") % 2 else 1)


def aes_cbc_decrypt(data, key, iv):
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
    decryptor = cipher.decryptor()
    return decryptor.update(data) + decryptor.finalize()


def strip_bac_padding(data):
    suffix = data.rstrip(b"\x00")
    if suffix.endswith(b"\x01"):
        return suffix[:-1]
    return data


mrz_partial = "12345678<8<<<1110182<111116?<<<<<<<<<<<<<<<4"
recovered_digit = recover_mrz_character(mrz_partial)
mrz_full = mrz_partial.replace("?", recovered_digit, 1)
mrz_info = mrz_full[:10] + mrz_full[13:20] + mrz_full[21:28]

k_seed = hashlib.sha1(mrz_info.encode()).digest()[:16]
raw_key = hashlib.sha1(k_seed + (1).to_bytes(4, "big")).digest()[:16]
key_enc = bytes(set_odd_parity(byte) for byte in raw_key)

ciphertext = base64.b64decode(
    "9MgYwmuPrjiecPMx61O6zIuy3MtIXQQ0E59T3xB6u0Gyf1gYs2i3K9Jx"
    "aa0zj4gTMazJuApwd6+jdyeI5iGHvhQyDHGVlAuYTgJrbFDrfB22Fpil2N"
    "fNnWFBTXyf7SDI"
)
plaintext = strip_bac_padding(aes_cbc_decrypt(ciphertext, key_enc, b"\x00" * 16)).decode()

print(recovered_digit)
print(mrz_info)
print(key_enc.hex())
print(plaintext)

题目二

题目地址：http://www.cryptopals.com/sets/2

1.Implement PKCS#7 padding

题目地址：https://www.cryptopals.com/sets/2/challenges/9

1
2
3
4
5
6
def pkcs7_pad(data, block_size):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


print(pkcs7_pad(b"YELLOW SUBMARINE", 20))

2.Implement CBC mode

题目地址：https://www.cryptopals.com/sets/2/challenges/10

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
import base64
import requests
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


def bytesxor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


def aes_ecb_decrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    decryptor = cipher.decryptor()
    return decryptor.update(data) + decryptor.finalize()


def aes_cbc_decrypt(data, key, iv):
    out = b""
    last = iv
    for i in range(0, len(data), 16):
        block = data[i : i + 16]
        out += bytesxor(aes_ecb_decrypt(block, key), last)
        last = block
    return out


def pkcs7_unpad(data):
    return data[: -data[-1]]


data = base64.b64decode(requests.get("https://cryptopals.com/static/challenge-data/10.txt").text)
plain = pkcs7_unpad(aes_cbc_decrypt(data, b"YELLOW SUBMARINE", b"\x00" * 16)).decode(errors="ignore")
print("\n".join(plain.splitlines()[:4]))

3.An ECB/CBC detection oracle

题目地址：https://www.cryptopals.com/sets/2/challenges/11

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
import random
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


random.seed(20260515)


def randbytes(n):
    return bytes([random.getrandbits(8) for _ in range(n)])


def pkcs7_pad(data, block_size=16):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


def aes_ecb_encrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    encryptor = cipher.encryptor()
    return encryptor.update(data) + encryptor.finalize()


def bytesxor(a, b):
    return bytes([x ^ y for x, y in zip(a, b)])


def aes_cbc_encrypt(data, key, iv):
    data = pkcs7_pad(data)
    out = b""
    last = iv
    for i in range(0, len(data), 16):
        block = bytesxor(data[i : i + 16], last)
        last = aes_ecb_encrypt(block, key)
        out += last
    return out


def detect_ecb(data, block_size=16):
    blocks = [data[i : i + block_size] for i in range(0, len(data), block_size)]
    return len(blocks) != len(set(blocks))


def oracle(data):
    key = randbytes(16)
    data = randbytes(random.randint(5, 10)) + data + randbytes(random.randint(5, 10))
    if random.randint(0, 1) == 0:
        return aes_ecb_encrypt(pkcs7_pad(data), key), "ECB"
    else:
        return aes_cbc_encrypt(data, key, randbytes(16)), "CBC"


cnt = 0
for _ in range(100):
    x, mode = oracle(b"A" * 64)
    guess = "ECB" if detect_ecb(x) else "CBC"
    if guess == mode:
        cnt += 1

print(cnt)

4.Byte-at-a-time ECB decryption (Simple)

题目地址：https://www.cryptopals.com/sets/2/challenges/12

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
import base64
import random
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


random.seed(20260515)


def randbytes(n):
    return bytes([random.getrandbits(8) for _ in range(n)])


def pkcs7_pad(data, block_size=16):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


def aes_ecb_encrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    encryptor = cipher.encryptor()
    return encryptor.update(data) + encryptor.finalize()


def block_size(oracle):
    n = len(oracle(b""))
    for i in range(1, 64):
        m = len(oracle(b"A" * i))
        if m > n:
            return m - n


unknown = base64.b64decode(
    b"Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg"
    b"aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq"
    b"dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg"
    b"YnkK"
)
key = randbytes(16)


def oracle(data):
    return aes_ecb_encrypt(pkcs7_pad(data + unknown), key)


bs = block_size(oracle)
ans = b""

for _ in range(len(oracle(b""))):
    pad = b"A" * (bs - 1 - len(ans) % bs)
    block_id = len(ans) // bs
    target = oracle(pad)[block_id * bs : (block_id + 1) * bs]
    d = {}
    for i in range(256):
        x = oracle(pad + ans + bytes([i]))[block_id * bs : (block_id + 1) * bs]
        d[x] = i
    if target not in d:
        break
    ans += bytes([d[target]])

print(ans.decode().rstrip("\x01"))

5.ECB cut-and-paste

题目地址：https://www.cryptopals.com/sets/2/challenges/13

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
import random
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


random.seed(20260515)
key = bytes([random.getrandbits(8) for _ in range(16)])


def pkcs7_pad(data, block_size=16):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


def pkcs7_unpad(data):
    return data[: -data[-1]]


def aes_ecb_encrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    encryptor = cipher.encryptor()
    return encryptor.update(data) + encryptor.finalize()


def aes_ecb_decrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    decryptor = cipher.decryptor()
    return decryptor.update(data) + decryptor.finalize()


def profile_for(email):
    email = email.replace("&", "").replace("=", "")
    return f"email={email}&uid=10&role=user".encode()


def encrypt_profile(email):
    return aes_ecb_encrypt(pkcs7_pad(profile_for(email)), key)


def decrypt_profile(data):
    s = pkcs7_unpad(aes_ecb_decrypt(data, key)).decode()
    print(s)


admin_block = encrypt_profile("A" * 10 + "admin" + chr(11) * 11)[16:32]
base = encrypt_profile("A" * 13)
decrypt_profile(base[:32] + admin_block)

6.Byte-at-a-time ECB decryption (Harder)

题目地址：https://www.cryptopals.com/sets/2/challenges/14

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
import base64
import random
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


random.seed(20260515)


def randbytes(n):
    return bytes([random.getrandbits(8) for _ in range(n)])


def pkcs7_pad(data, block_size=16):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


def aes_ecb_encrypt(data, key):
    cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
    encryptor = cipher.encryptor()
    return encryptor.update(data) + encryptor.finalize()


def block_size(oracle):
    n = len(oracle(b""))
    for i in range(1, 64):
        m = len(oracle(b"A" * i))
        if m > n:
            return m - n


unknown = base64.b64decode(
    b"Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg"
    b"aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq"
    b"dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg"
    b"YnkK"
)
key = randbytes(16)
prefix = randbytes(random.randint(5, 32))


def oracle(data):
    return aes_ecb_encrypt(pkcs7_pad(prefix + data + unknown), key)


bs = block_size(oracle)
pos = None

for i in range(bs * 2):
    x = oracle(b"A" * i + b"B" * (bs * 2))
    blocks = [x[j : j + bs] for j in range(0, len(x), bs)]
    for j in range(len(blocks) - 1):
        if blocks[j] == blocks[j + 1]:
            pos = (i, j)
            break
    if pos is not None:
        break

pad_len, block_id = pos
pad = b"A" * pad_len
ans = b""

for _ in range(len(oracle(b""))):
    short = bs - 1 - len(ans) % bs
    now_block = block_id + len(ans) // bs
    target = oracle(pad + b"A" * short)[now_block * bs : (now_block + 1) * bs]
    d = {}
    for i in range(256):
        x = oracle(pad + b"A" * short + ans + bytes([i]))[now_block * bs : (now_block + 1) * bs]
        d[x] = i
    if target not in d:
        break
    ans += bytes([d[target]])

print(block_id * bs - pad_len)
print(ans.decode().rstrip("\x01"))

7.PKCS#7 padding validation

题目地址：https://www.cryptopals.com/sets/2/challenges/15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def pkcs7_unpad(data):
    pad = data[-1]
    if pad < 1 or pad > 16 or data[-pad:] != bytes([pad]) * pad:
        raise ValueError
    return data[:-pad]


print(pkcs7_unpad(b"ICE ICE BABY\x04\x04\x04\x04"))

try:
    print(pkcs7_unpad(b"ICE ICE BABY\x05\x05\x05\x05"))
except ValueError:
    print("ValueError")

try:
    print(pkcs7_unpad(b"ICE ICE BABY\x01\x02\x03\x04"))
except ValueError:
    print("ValueError")

8.CBC bit flipping attacks

题目地址：https://www.cryptopals.com/sets/2/challenges/16

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
import random
import sys
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes


random.seed(20260515)


def randbytes(n):
    return bytes([random.getrandbits(8) for _ in range(n)])


def pkcs7_pad(data, block_size=16):
    pad_len = block_size - len(data) % block_size
    return data + bytes([pad_len]) * pad_len


def pkcs7_unpad(data):
    return data[: -data[-1]]


def aes_cbc_encrypt(data, key, iv):
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
    encryptor = cipher.encryptor()
    return encryptor.update(pkcs7_pad(data)) + encryptor.finalize()


def aes_cbc_decrypt(data, key, iv):
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
    decryptor = cipher.decryptor()
    return decryptor.update(data) + decryptor.finalize()


key = randbytes(16)
iv = randbytes(16)
prefix = b"comment1=cooking%20MCs;userdata="
suffix = b";comment2=%20like%20a%20pound%20of%20bacon"


def encrypt(user_data):
    user_data = user_data.replace(b";", b"%3B").replace(b"=", b"%3D")
    return aes_cbc_encrypt(prefix + user_data + suffix, key, iv)


def decrypt(data):
    return pkcs7_unpad(aes_cbc_decrypt(data, key, iv))


pad_len = (16 - len(prefix) % 16) % 16
payload = b"A" * (pad_len + 16)
c = bytearray(encrypt(payload))

block_id = (len(prefix) + pad_len) // 16
target = b";admin=true;AAAA"

for i in range(len(target)):
    c[(block_id - 1) * 16 + i] ^= 0x41 ^ target[i]

plain = decrypt(bytes(c))
if hasattr(sys.stdout, "reconfigure"):
    sys.stdout.reconfigure(encoding="utf-8")
print(b";admin=true;" in plain)
print(plain.decode("latin1"))