This is the next set of block cipher cryptography challenges (even the randomness stuff here plays into block cipher crypto).
This set is moderately difficult. It includes a famous attack against CBC mode, and a "cloning" attack on a popular RNG that can be annoying to get right.
We've also reached a point in the crypto challenges where all the challenges, with one possible exception, are valuable in breaking real-world crypto.
import base64
from math import prod
from random import randbytes, randint
import struct
import time
# From pyca/cryptography
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
def xor(x, y):
return bytes(xb^yb for xb, yb in zip(x, y))
def aes_128_ecb_encrypt(ptext, key):
# N.B.: performs no padding
encryptor = Cipher(algorithms.AES128(key), modes.ECB()).encryptor()
return encryptor.update(ptext) + encryptor.finalize()
def pad_pkcs7(text):
padder = padding.PKCS7(128).padder()
return padder.update(text) + padder.finalize()
def unpad_pkcs7(text):
unpadder = padding.PKCS7(128).unpadder()
return unpadder.update(text) + unpadder.finalize()
def aes_128_cbc_encrypt(ptext, key):
# Return (ctext, iv)
iv = randbytes(16)
encryptor = Cipher(algorithms.AES128(key), modes.CBC(iv)).encryptor()
return (encryptor.update(pad_pkcs7(ptext)) + encryptor.finalize(), iv)
def aes_128_cbc_decrypt(ctext, key, iv):
decryptor = Cipher(algorithms.AES128(key), modes.CBC(iv)).decryptor()
return unpad_pkcs7(decryptor.update(ctext) + decryptor.finalize())
def A(n):
return b"A"*n
This is the best-known attack on modern block-cipher cryptography.
Combine your padding code and your CBC code to write two functions.
The first function should select at random one of the following 10 strings:
MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc=
MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic=
MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw==
MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg==
MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl
MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA==
MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw==
MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8=
MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g=
MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93
... generate a random AES key (which it should save for all future encryptions), pad the string out to the 16-byte AES block size and CBC-encrypt it under that key, providing the caller the ciphertext and IV.
The second function should consume the ciphertext produced by the first function, decrypt it, check its padding, and return true or false depending on whether the padding is valid.
What you're doing here.
This pair of functions approximates AES-CBC encryption as it's deployed serverside in web applications; the second function models the server's consumption of an encrypted session token, as if it were a cookie.
It turns out that it's possible to decrypt the ciphertexts provided by the first function.
The decryption here depends on a side-channel leak by the decryption function. The leak is the error message that the padding is valid or not.
You can find 100 web pages on how this attack works, so I won't re-explain it. What I'll say is this:
The fundamental insight behind this attack is that the byte 01h is valid padding, and occurs in 1/256 trials of "randomized" plaintexts produced by decrypting a tampered ciphertext.
02h in isolation is not valid padding.
02h 02h is valid padding, but is much less likely to occur randomly than 01h.
03h 03h 03h is even less likely.
So you can assume that if you corrupt a decryption AND it had valid padding, you know what that padding byte is.
It is easy to get tripped up on the fact that CBC plaintexts are "padded". Padding oracles have nothing to do with the actual padding on a CBC plaintext. It's an attack that targets a specific bit of code that handles decryption. You can mount a padding oracle on any CBC block, whether it's padded or not.
What a fantastic attack! First, the requested functions:
inputs = [
base64.b64decode(s) for s in [
"MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc=",
"MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic=",
"MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw==",
"MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg==",
"MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl",
"MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA==",
"MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw==",
"MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8=",
"MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g=",
"MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93"
]
]
random_key = randbytes(16)
def fun1(ptext):
return aes_128_cbc_encrypt(ptext, random_key)
def fun2(ctext, iv):
try:
aes_128_cbc_decrypt(ctext, random_key, iv)
except ValueError as e:
if e.args[0] == "Invalid padding bytes.":
return False
else:
raise
else:
return True
# Test valid padding
ciphertext, iv = fun1(inputs[0])
print(fun2(ciphertext, iv))
# Test invalid padding
print(fun2(ciphertext[:-1] + bytes([99]), iv))
True False
Now for the solution. We rely on the following properties to be able to fully decrypt the messages:
To decrypt a message we start with the last byte of the last block. Let $C_i$, $D_i$, and $P_i$ denote the $i^{\rm th}$ ciphertext, decrypted, and plaintext bytes, respectively. Per the CBC algorithm, $D_i$ is computed from $C_i$ at the block level, uses the key in doing so, and is unknown to us; and $P_i = D_i \oplus C_{i-16}$. Let $l$ be the index of the last byte. So we have:
----------------------+------------------+
... C_{l-17} C_{l-16} | C_{l-15} ... C_l |
----------------------+------------------+
| |
| +------------------+
| | D_{l_15} ... D_l |
| +------------------+
| |
+-------------------(+)
|
----------------------+------------------+
| .... P_j ... P_l |
----------------------+------------------+
We find $C'_{l-16}$ such that:
As a consequence, it must be that $P'_l = 1$. From this we can compute $D_l = C'_{l-16} \oplus 1$ and from there $P_l$. First byte down. For the remaining bytes in the last block, we proceed right to left. To decrypt byte $j$, $l-16 < j < l$, let $n = l-j$. We use our knowledge of ${P_i}$ (and therefore ${D_i}$) for $i > j$ to set $P'_i = n+1$. We then find $C'_{j-16}$ such that the padding is valid, in which case it must be that $P'_j = n+1$, and from that we can deduce $P_j$.
To decrypt the next-to-last block, we simply remove the last block and repeat the process, and so forth. To decrypt the first block, we treat the initialization vector as the first block of ciphertext.
def decrypt_last_block(ctext, iv):
if len(ctext) == 16:
ctext = iv + ctext
ptext = bytearray()
# Determine last plaintext byte
for b in range(256):
a = bytearray(ctext)
a[-17] = b
ctext1 = bytes(a)
a[-18] ^= 1
ctext2 = bytes(a)
if fun2(ctext1, iv) and fun2(ctext2, iv):
ptext.append(ctext[-17]^(b^1))
break
# Now proceed leftward
for j in range(2, 17):
a = bytearray(ctext)
for i in range(1, j):
a[-i-16] = (ctext[-i-16]^ptext[-i])^j
for b in range(256):
a[-j-16] = b
if fun2(bytes(a), iv):
break
ptext.insert(0, ctext[-j-16]^(b^j))
return bytes(ptext)
def break_cbc_padding(ctext, iv):
ptext = bytes()
for l in range(len(ctext), 0, -16):
ptext = decrypt_last_block(ctext[:l], iv) + ptext
return unpad_pkcs7(ptext)
for i in inputs:
plaintext = break_cbc_padding(*fun1(i))
assert plaintext == i
print(plaintext)
b'000000Now that the party is jumping' b"000001With the bass kicked in and the Vega's are pumpin'" b'000002Quick to the point, to the point, no faking' b"000003Cooking MC's like a pound of bacon" b"000004Burning 'em, if you ain't quick and nimble" b'000005I go crazy when I hear a cymbal' b'000006And a high hat with a souped up tempo' b"000007I'm on a roll, it's time to go solo" b"000008ollin' in my five point oh" b'000009ith my rag-top down so my hair can blow'
The string:
L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==
... decrypts to something approximating English in CTR mode, which is an AES block cipher mode that turns AES into a stream cipher, with the following parameters:
key=YELLOW SUBMARINE
nonce=0
format=64 bit unsigned little endian nonce,
64 bit little endian block count (byte count / 16)
CTR mode is very simple.
Instead of encrypting the plaintext, CTR mode encrypts a running counter, producing a 16 byte block of keystream, which is XOR'd against the plaintext.
For instance, for the first 16 bytes of a message with these parameters:
keystream = AES("YELLOW SUBMARINE",
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00")
... for the next 16 bytes:
keystream = AES("YELLOW SUBMARINE",
"\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00")
... and then:
keystream = AES("YELLOW SUBMARINE",
"\x00\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00")
CTR mode does not require padding; when you run out of plaintext, you just stop XOR'ing keystream and stop generating keystream.
Decryption is identical to encryption. Generate the same keystream, XOR, and recover the plaintext.
Decrypt the string at the top of this function, then use your CTR function to encrypt and decrypt other things.
This is the only block cipher mode that matters in good code.
Most modern cryptography relies on CTR mode to adapt block ciphers into stream ciphers, because most of what we want to encrypt is better described as a stream than as a sequence of blocks. Daniel Bernstein once quipped to Phil Rogaway that good cryptosystems don't need the "decrypt" transforms. Constructions like CTR are what he was talking about.
input = base64.b64decode("L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==")
key = b"YELLOW SUBMARINE"
def bytes_8le(n):
# Return bytes of 8-byte integer in little endian order
return bytes.fromhex("%016x" % n)[::-1]
def aes_128_ctr_crypt(text, key, nonce=0):
# Symmetric encryption/decryption
n = (len(text)-1)//16+1
stream = b"".join(
aes_128_ecb_encrypt(bytes_8le(nonce) + bytes_8le(i), key)
for i in range(n)
)
return xor(text, stream[:len(text)])
print(aes_128_ctr_crypt(input, key))
b"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby "
Take your CTR encrypt/decrypt function and fix its nonce value to 0. Generate a random AES key.
In successive encryptions (not in one big running CTR stream), encrypt each line of the base64 decodes of the following, producing multiple independent ciphertexts:
SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ==
Q29taW5nIHdpdGggdml2aWQgZmFjZXM=
RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ==
RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4=
SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk
T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==
T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ=
UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==
QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU=
T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl
VG8gcGxlYXNlIGEgY29tcGFuaW9u
QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA==
QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk=
QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg==
QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo=
QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=
VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA==
SW4gaWdub3JhbnQgZ29vZCB3aWxsLA==
SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA==
VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg==
V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw==
V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA==
U2hlIHJvZGUgdG8gaGFycmllcnM/
VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w=
QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4=
VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ=
V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs=
SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA==
U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA==
U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4=
VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA==
QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu
SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc=
VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs
WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs=
SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0
SW4gdGhlIGNhc3VhbCBjb21lZHk7
SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw=
VHJhbnNmb3JtZWQgdXR0ZXJseTo=
QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=
(This should produce 40 short CTR-encrypted ciphertexts.)
Because the CTR nonce wasn't randomized for each encryption, each ciphertext has been encrypted against the same keystream. This is very bad.
Understanding that, like most stream ciphers (including RC4, and obviously any block cipher run in CTR mode), the actual "encryption" of a byte of data boils down to a single XOR operation. It should be plain that:
CIPHERTEXT-BYTE XOR PLAINTEXT-BYTE = KEYSTREAM-BYTE
And since the keystream is the same for every ciphertext:
CIPHERTEXT-BYTE XOR KEYSTREAM-BYTE = PLAINTEXT-BYTE (ie, "you don't say!")
Attack this cryptosystem piecemeal: guess letters, use expected English language frequence to validate guesses, catch common English trigrams, and so on.
Don't overthink it.
Points for automating this, but part of the reason I'm having you do this is that I think this approach is suboptimal.
We go ahead and just decrypt the messages using a statistical approach as we will be asked to do in the next challenge, using code from challenges 3 and 6 from set 1. It's amazing that we are able to perfectly decrypt using just a 1-gram probabilistic model.
inputs = [
base64.b64decode(s) for s in [
"SSBoYXZlIG1ldCB0aGVtIGF0IGNsb3NlIG9mIGRheQ==",
"Q29taW5nIHdpdGggdml2aWQgZmFjZXM=",
"RnJvbSBjb3VudGVyIG9yIGRlc2sgYW1vbmcgZ3JleQ==",
"RWlnaHRlZW50aC1jZW50dXJ5IGhvdXNlcy4=",
"SSBoYXZlIHBhc3NlZCB3aXRoIGEgbm9kIG9mIHRoZSBoZWFk",
"T3IgcG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==",
"T3IgaGF2ZSBsaW5nZXJlZCBhd2hpbGUgYW5kIHNhaWQ=",
"UG9saXRlIG1lYW5pbmdsZXNzIHdvcmRzLA==",
"QW5kIHRob3VnaHQgYmVmb3JlIEkgaGFkIGRvbmU=",
"T2YgYSBtb2NraW5nIHRhbGUgb3IgYSBnaWJl",
"VG8gcGxlYXNlIGEgY29tcGFuaW9u",
"QXJvdW5kIHRoZSBmaXJlIGF0IHRoZSBjbHViLA==",
"QmVpbmcgY2VydGFpbiB0aGF0IHRoZXkgYW5kIEk=",
"QnV0IGxpdmVkIHdoZXJlIG1vdGxleSBpcyB3b3JuOg==",
"QWxsIGNoYW5nZWQsIGNoYW5nZWQgdXR0ZXJseTo=",
"QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4=",
"VGhhdCB3b21hbidzIGRheXMgd2VyZSBzcGVudA==",
"SW4gaWdub3JhbnQgZ29vZCB3aWxsLA==",
"SGVyIG5pZ2h0cyBpbiBhcmd1bWVudA==",
"VW50aWwgaGVyIHZvaWNlIGdyZXcgc2hyaWxsLg==",
"V2hhdCB2b2ljZSBtb3JlIHN3ZWV0IHRoYW4gaGVycw==",
"V2hlbiB5b3VuZyBhbmQgYmVhdXRpZnVsLA==",
"U2hlIHJvZGUgdG8gaGFycmllcnM/",
"VGhpcyBtYW4gaGFkIGtlcHQgYSBzY2hvb2w=",
"QW5kIHJvZGUgb3VyIHdpbmdlZCBob3JzZS4=",
"VGhpcyBvdGhlciBoaXMgaGVscGVyIGFuZCBmcmllbmQ=",
"V2FzIGNvbWluZyBpbnRvIGhpcyBmb3JjZTs=",
"SGUgbWlnaHQgaGF2ZSB3b24gZmFtZSBpbiB0aGUgZW5kLA==",
"U28gc2Vuc2l0aXZlIGhpcyBuYXR1cmUgc2VlbWVkLA==",
"U28gZGFyaW5nIGFuZCBzd2VldCBoaXMgdGhvdWdodC4=",
"VGhpcyBvdGhlciBtYW4gSSBoYWQgZHJlYW1lZA==",
"QSBkcnVua2VuLCB2YWluLWdsb3Jpb3VzIGxvdXQu",
"SGUgaGFkIGRvbmUgbW9zdCBiaXR0ZXIgd3Jvbmc=",
"VG8gc29tZSB3aG8gYXJlIG5lYXIgbXkgaGVhcnQs",
"WWV0IEkgbnVtYmVyIGhpbSBpbiB0aGUgc29uZzs=",
"SGUsIHRvbywgaGFzIHJlc2lnbmVkIGhpcyBwYXJ0",
"SW4gdGhlIGNhc3VhbCBjb21lZHk7",
"SGUsIHRvbywgaGFzIGJlZW4gY2hhbmdlZCBpbiBoaXMgdHVybiw=",
"VHJhbnNmb3JtZWQgdXR0ZXJseTo=",
"QSB0ZXJyaWJsZSBiZWF1dHkgaXMgYm9ybi4="
]
]
letter_frequencies = {
"E": 0.1249,
"T": 0.0928,
"A": 0.0804,
"O": 0.0764,
"I": 0.0757,
"N": 0.0723,
"S": 0.0651,
"R": 0.0628,
"H": 0.0505,
"L": 0.0407,
"D": 0.0382,
"C": 0.0334,
"U": 0.0273,
"M": 0.0251,
"F": 0.0240,
"P": 0.0214,
"G": 0.0187,
"W": 0.0168,
"Y": 0.0166,
"B": 0.0148,
"V": 0.0105,
"K": 0.0054,
"X": 0.0023,
"J": 0.0016,
"Q": 0.0012,
"Z": 0.0009
}
def score(ptext):
def value(b):
c = chr(b).upper()
if c in letter_frequencies:
return letter_frequencies[c]
elif c.isprintable() or c in "\t\r\n":
return min(letter_frequencies.values())
else:
return 0
return prod(value(b) for b in ptext)
def brute_force_decrypt_xor(ctext):
# Return the highest-scored plaintext and its score
ptexts = [
bytes(b^key for b in ctext)
for key in range(256)
]
return max(
({"plaintext": pt, "score": score(pt)} for pt in ptexts),
key=lambda d: d["score"]
)
def break_ctr_repeated_nonce(ctexts):
cols = []
for i in range(len(ctexts[0])): # assuming all are of same length
col_ctext = bytes(ct[i] for ct in ctexts)
cols.append(brute_force_decrypt_xor(col_ctext)["plaintext"])
ptexts = [
bytes(cols[i][j] for i in range(len(cols)))
for j in range(len(ctexts))
]
return ptexts
def solve_and_verify():
minlen = min(map(len, inputs))
ciphertexts = [aes_128_ctr_crypt(i[:minlen], random_key) for i in inputs]
plaintexts = break_ctr_repeated_nonce(ciphertexts)
for i, pt in zip(inputs, plaintexts):
assert i[:minlen].upper() == pt.upper()
print(pt)
solve_and_verify()
b'I have met them at c' b'Coming with vivid fa' b'From counter or desk' b'Eighteenth-century h' b'I have passed with a' b'Or polite meaningles' b'Or have lingered awh' b'Polite meaningless w' b'And thought before I' b'Of a mocking tale or' b'To please a companio' b'Around the fire at t' b'Being certain that t' b'But lived where motl' b'All changed, changed' b'A terrible beauty is' b"That woman's days we" b'In ignorant good wil' b'Her nights in argume' b'Until her voice grew' b'What voice more swee' b'When young and beaut' b'She rode to harriers' b'This man had kept a ' b'And rode our winged ' b'This other his helpe' b'Was coming into his ' b'He might have won fa' b'So sensitive his nat' b'So daring and sweet ' b'This other man I had' b'A drunken, vain-glor' b'He had done most bit' b'To some who are near' b'Yet I number him in ' b'He, too, has resigne' b'In the casual comedy' b'He, too, has been ch' b'Transformed utterly:' b'A terrible beauty is'
In this file find a similar set of Base64'd plaintext. Do with them exactly what you did with the first, but solve the problem differently.
Instead of making spot guesses at known plaintext, treat the collection of ciphertexts the same way you would repeating-key XOR.
Obviously, CTR encryption appears different from repeated-key XOR, but with a fixed nonce they are effectively the same thing.
To exploit this: take your collection of ciphertexts and truncate them to a common length (the length of the smallest ciphertext will work).
Solve the resulting concatenation of ciphertexts as if for repeating-key XOR, with a key size of the length of the ciphertext you XOR'd.
inputs = [base64.b64decode(l.strip()) for l in open("20.in")]
solve_and_verify()
b'I\'m rated "R"...this is a warning, ya better void / P' b'Cuz I came back to attack others in spite- / Strike l' b"But don't be afraid in the dark, in a park / Not a sc" b'Ya tremble like a alcoholic, muscles tighten up / Wha' b'Suddenly you feel like your in a horror flick / You g' b"Music's the clue, when I come your warned / Apocalyps" b"Haven't you ever heard of a MC-murderer? / This is th" b'Death wish, so come on, step to this / Hysterical ide' b'Friday the thirteenth, walking down Elm Street / You ' b'This is off limits, so your visions are blurry / All ' b"Terror in the styles, never error-files / Indeed I'm " b'For those that oppose to be level or next to this / I' b"Worse than a nightmare, you don't have to sleep a win" b'Flashbacks interfere, ya start to hear: / The R-A-K-I' b'Then the beat is hysterical / That makes Eric go get ' b'Soon the lyrical format is superior / Faces of death ' b"MC's decaying, cuz they never stayed / The scene of a" b"The fiend of a rhyme on the mic that you know / It's " b'Melodies-unmakable, pattern-unescapable / A horn if w' b'I bless the child, the earth, the gods and bomb the r' b'Hazardous to your health so be friendly / A matter of' b"Shake 'till your clear, make it disappear, make the n" b"If not, my soul'll release! / The scene is recreated," b'Cuz your about to see a disastrous sight / A performa' b'Lyrics of fury! A fearified freestyle! / The "R" is i' b"Make sure the system's loud when I mention / Phrases " b'You want to hear some sounds that not only pounds but' b'Then nonchalantly tell you what it mean to me / Stric' b"And I don't care if the whole crowd's a witness! / I'" b'Program into the speed of the rhyme, prepare to start' b"Musical madness MC ever made, see it's / Now an emerg" b"Open your mind, you will find every word'll be / Furi" b"Battle's tempting...whatever suits ya! / For words th" b"You think you're ruffer, then suffer the consequences" b'I wake ya with hundreds of thousands of volts / Mic-t' b'Novocain ease the pain it might save him / If not, Er' b"Yo Rakim, what's up? / Yo, I'm doing the knowledge, E" b'Well, check this out, since Norby Walters is our agen' b'Kara Lewis is our agent, word up / Zakia and 4th and ' b"Okay, so who we rollin' with then? We rollin' with Ru" b'Check this out, since we talking over / This def beat' b'I wanna hear some of them def rhymes, you know what I' b"Thinkin' of a master plan / 'Cuz ain't nuthin' but sw" b'So I dig into my pocket, all my money is spent / So I' b"So I start my mission, leave my residence / Thinkin' " b'I need money, I used to be a stick-up kid / So I thin' b"I used to roll up, this is a hold up, ain't nuthin' f" b"But now I learned to earn 'cuz I'm righteous / I feel" b'Search for a nine to five, if I strive / Then maybe I' b"So I walk up the street whistlin' this / Feelin' out " b'A pen and a paper, a stereo, a tape of / Me and Eric ' b'Fish, which is my favorite dish / But without no mone' b"'Cuz I don't like to dream about gettin' paid / So I " b'So now to test to see if I got pull / Hit the studio,' b'Rakim, check this out, yo / You go to your girl house' b"'Cause my girl is definitely mad / 'Cause it took us " b"Yo, I hear what you're saying / So let's just pump th" b'And count our money / Yo, well check this out, yo Eli' b'Turn down the bass down / And let the beat just keep ' b'And we outta here / Yo, what happened to peace? / Pea'
You can get the pseudocode for this from Wikipedia.
If you're writing in Python, Ruby, or (gah) PHP, your language is probably already giving you MT19937 as "rand()"; don't use rand(). Write the RNG yourself.
Below is a fairly direct translation of the C code given in Wikipedia.
class MersenneTwister:
w = 32 # word size in bits
n = 624 # degree of recurrence; state size in words
m = 397 # middle word offset
r = 31 # upper/lower separation point within word
a = 0x9908b0df # coefficients of the rational normal form twist matrix
b = 0x9d2c5680 # tempering bitmasks
c = 0xefc60000
s = 7 # tempering bit shifts
t = 15
u = 11
l = 18
f = 1812433253 # seed multiplier
wmask = 2**w-1 # w-bit mask
umask = wmask << r # upper mask
lmask = wmask >> (w-r) # lower mask
def __init__(self, seed):
C = MersenneTwister
self.state_array = [seed]
for i in range(1, C.n):
seed = (C.f * (seed ^ (seed >> (C.w-2))) + i) & C.wmask
self.state_array.append(seed)
self.state_index = 0
def rand(self):
C = MersenneTwister
state = self.state_array
k = self.state_index
j = (k+1)%C.n
# Do some mysterious stuff
x = (state[k] & C.umask) | (state[j] & C.lmask)
xA = x >> 1
if (x & 1) != 0:
xA ^= C.a
j = (k - (C.n-C.m))%C.n
x = state[j] ^ xA # (*) new value x, noted for challenge 23
# Store new value
state[k] = x
self.state_index = (k+1)%C.n
# "Temper" new value and return
y = x ^ (x >> C.u)
y = y ^ ((y << C.s) & C.b)
y = y ^ ((y << C.t) & C.c)
z = y ^ (y >> C.l)
return z
# Try it out
mt = MersenneTwister(19650218)
print(mt.rand())
2325592414
Make sure your MT19937 accepts an integer seed value. Test it (verify that you're getting the same sequence of outputs given a seed).
Write a routine that performs the following operation:
You get the idea. Go get coffee while it runs. Or just simulate the passage of time, although you're missing some of the fun of this exercise if you do that.
From the 32 bit RNG output, discover the seed.
The code below is dumb, but it does illustrate the point of this challenge, that using the current time as the seed is easily guessed.
# Use the current time as the seed...
mt = MersenneTwister(int(time.time()))
r = mt.rand()
# Now "guess" the seed, pretending some time has elapsed
now = int(time.time())
for t in range(now-60, now+1):
if MersenneTwister(t).rand() == r:
print("seed =", t)
break
seed = 1722565313
The internal state of MT19937 consists of 624 32 bit integers.
For each batch of 624 outputs, MT permutes that internal state. By permuting state regularly, MT19937 achieves a period of 2**19937, which is Big.
Each time MT19937 is tapped, an element of its internal state is subjected to a tempering function that diffuses bits through the result.
The tempering function is invertible; you can write an "untemper" function that takes an MT19937 output and transforms it back into the corresponding element of the MT19937 state array.
To invert the temper transform, apply the inverse of each of the operations in the temper transform in reverse order. There are two kinds of operations in the temper transform each applied twice: one is an XOR against a right-shifted value, and the other is an XOR against a left-shifted value AND'd with a magic number. So you'll need code to invert the "right" and the "left" operation.
Once you have "untemper" working, create a new MT19937 generator, tap it for 624 outputs, untemper each of them to recreate the state of the generator, and splice that state into a new instance of the MT19937 generator.
The new "spliced" generator should predict the values of the original.
Stop and think for a second.
How would you modify MT19937 to make this attack hard? What would happen if you subjected each tempered output to a cryptographic hash?
On each call, the Mersenne Twister algorithm generates a value x (marked by (*) in the code above) from the seed array, stores the value in the next slot in the state array in circular order (the state array is not "permuted" as such), and then "tempers" the value before returning it. The state array is otherwise not modified. Thus if we generate 624 random numbers and untemper them and place those seed values in an array linearly, and set the current index to 0, we will have entirely replicated the generator's state.
That the tempering function is invertible is not at all obvious, particularly as it involves boolean ANDs. Inverting the last operation is the most straightforward. In the following, we use the notation $y_{b..a}$, $32 \ge b > a \ge 0$, to indicate bits $a$ (inclusive) through $b$ (exclusive) of $y$, and $x \parallel y$ to indicate the concatenation of two ranges of bits. Then for the last operation we have:
$$ \begin{eqnarray*} z &\gets& y \oplus ( y \gg 18 ) \\ &=& y \oplus ( 0_{18..0} \parallel y_{32..18} ) \\ &=& ( y_{32..14} \oplus 0_{18..0} ) \parallel ( y_{14..0} \oplus y_{32..18} ) \\ &=& y_{32..14} \parallel ( y_{14..0} \oplus y_{32..18} ) \end{eqnarray*} $$Observe that the high 18 bits of $z$ match those of $y$ and are correct. Further, the low 14 bits of $y$ can be recovered by XOR-ing $z$ with the high 14 bits of $y$, which as just noted we have in hand. In other words, the last operation is very neatly its own inverse:
$$ \begin{eqnarray*} z \oplus ( z \gg 18 ) &=& \\ z_{32..14} \parallel ( z_{14..0} \oplus z_{32..18} ) &=& \\ y_{32..14} \parallel ( ( y_{14..0} \oplus y_{32..18} ) \oplus y_{32..18} ) &=& y \end{eqnarray*} $$Inverting the other three operations is trickier because the number of initially correct bits is less than 16. We credit Nick Krichevsky for giving us the idea of recursively getting a few bits at a time. This process is most easily demonstrated by inverting the next simplest operation:
$$ \begin{eqnarray*} y &\gets& x \oplus ( x \gg 11 ) \\ &=& x \oplus ( 0_{11..0} \parallel x_{32..11} ) \\ &=& ( x_{32..21} \oplus 0_{11..0} ) \parallel ( x_{21..0} \oplus x_{32..11} ) \\ &=& x_{32..21} \parallel ( x_{21..0} \oplus x_{32..11} ) \end{eqnarray*} $$Similar to the previous operation, the high bits of $y$ match those of $x$ and are correct, but now only 11 bits are correct and we need 21 correct bits for an XOR to be able to recover the rest of $x$. But to expand:
$$ \begin{eqnarray*} y &\gets& x_{32..21} \parallel ( x_{21..0} \oplus x_{32..11} ) \\ &=& x_{32..21} \parallel ( x_{21..10} \oplus x_{32..21} ) \parallel ( x_{10..0} \oplus x_{21..11} ) \end{eqnarray*} $$Notice how the correct high 11 bits can be used to obtain the next 11 bits of $x$, and so on iteratively. This leads to the recursive formula:
$$ \begin{eqnarray*} y \oplus ( ( y \oplus ( y \gg 11 ) ) \gg 11 ) &=& \\ y \oplus ( ( y_{32..21} \parallel ( y_{21..0} \oplus y_{32..11} ) ) \gg 11 ) &=& \\ y \oplus ( 0_{11..0} \parallel y_{32..21} \parallel ( y_{21..11} \oplus y_{32..22} ) ) &=& \\ y_{32..21} \parallel ( y_{21..10} \oplus y_{32..21} ) \parallel ( y_{10..0} \oplus ( y_{21..11} \oplus y_{32..22} ) ) &=& \\ x_{32..21} \parallel ( x_{21..10} \oplus x_{32..21} ) \oplus x_{32..21} ) \parallel ( y_{10..0} \oplus ( y_{21..11} \oplus y_{32..22} ) ) &=& \\ x_{32..10} \parallel ( y_{10..0} \oplus ( y_{21..11} \oplus y_{32..22} ) ) &=& \\ x_{32..10} \parallel ( ( x_{10..0} \oplus x_{21..11} ) \oplus ( ( x_{21..11} \oplus x_{32..22} ) \oplus x_{32..22} ) ) &=& x \end{eqnarray*} $$This same approach works for the remaining operations, even with their use of left shifts and boolean ANDs. (It does feel like some conservation principle is being violated here. How can we parlay one bit of information into more bits?)
Regarding the question posed by this challenge, would hashing the output make this attack harder, it would indeed, and in fact the authors of the Mersenne Twister proposed just that and other approaches in their follow-on proposal for a Cryptographic Mersenne Twister (CryptMT).
def untemper(z):
C = MersenneTwister
def invert(z, n, inner_fn):
# Invert z = y ^ inner_fn(y) in which n bits of z are correct
num_correct_bits = n
v = z
while num_correct_bits < 32:
v = z ^ inner_fn(v)
num_correct_bits += n
return v
y = invert(z, C.l, lambda v: v >> C.l)
y = invert(y, C.t, lambda v: (v << C.t) & C.c)
y = invert(y, C.s, lambda v: (v << C.s) & C.b)
x = invert(y, C.u, lambda v: v >> C.u)
return x
# Create a random twister and put it in a random state
mt = MersenneTwister(randint(0, 2**32-1))
for _ in range(randint(1, 1000)):
mt.rand()
# Clone
clone = MersenneTwister(0)
clone.state_array = [untemper(mt.rand()) for _ in range(MersenneTwister.n)]
clone.state_index = 0
# Confirm equivalence
for _ in range(1000):
assert mt.rand() == clone.rand()
You can create a trivial stream cipher out of any PRNG; use it to generate a sequence of 8 bit outputs and call those outputs a keystream. XOR each byte of plaintext with each successive byte of keystream.
Write the function that does this for MT19937 using a 16-bit seed. Verify that you can encrypt and decrypt properly. This code should look similar to your CTR code.
Use your function to encrypt a known plaintext (say, 14 consecutive 'A' characters) prefixed by a random number of random characters.
From the ciphertext, recover the "key" (the 16 bit seed).
Use the same idea to generate a random "password reset token" using MT19937 seeded from the current time.
Write a function to check if any given password token is actually the product of an MT19937 PRNG seeded with the current time.
Both parts of this challenge are similar to Challenge 22 in that we're simply guessing what the seed is.
def prng_crypt(text, seed):
# Symmetric encryption/decryption
mt = MersenneTwister(seed)
n = (len(text)-1)//4+1
stream = b"".join(struct.pack("I", mt.rand()) for _ in range(n))
return xor(text, stream[:len(text)])
ciphertext = prng_crypt(
randbytes(randint(1, 100)) + A(14),
randint(0, 2**16-1)
)
for seed in range(2**16):
if prng_crypt(ciphertext, seed).endswith(A(14)):
print("found it")
found it