TLDR; There is a horrible lag issue with spotify, spotify didn't fix it yet, so basically I profile the app, detect the bug slowing it down, add some code to force hardware acceleration using the translate3d(0,0,0) trick, also add some perfomance hints using willChange.
before & after:
The performance issue makes using spotify so horrible that I considered switching to Tidal. Spotify knows about this, since many users complained in the forums, but they didn't fix it yet, I love this app and don't want to switch to Tidal, so I take matters in my own hands.
here is a video (i don't delve into the technical details too extensively here, since the video is made for normal spotify users to help them fix the issue):
BsidesSF had really really good reverse engineering challenges, but I loved two challenges. One windows reverse challenge called chameleon and another esp32 firmware reverse challenge called smart-locky which I didn't manage to solve in time.
The challenge
Problem statement
We are given two files chameleon.exe and flag.png.enc, this looks trivial enough we need to reverse the encryption algorithm to give us the original flag.png.
The problem statment also says that file was encrypted in the last months.
Reading the statment it looked like a simple challenge where you brute force the seed of a default mt19937 implementation, but the problem had only two solves, so I thought there must be some twist.
First glance at the binary
When you first execute the binary it gives you two options, to encrypt or decrypt files.
All right looks simple enough, here are the algorithm steps:
call to CryptAcquireContextA, this is like an encryption algorithm factory in windows
call to a function that I called mersenne_twister
sets some values in pbData
call to CryptImportKey
call to CryptEncrypt
If you read this tutorial you can understand how CryptImportKey works.
This is an example key blob from the page above:
BYTEDesKeyBlob[] = {
0x08,0x02,0x00,0x00,0x01,0x66,0x00,0x00, // BLOB header
0x08,0x00,0x00,0x00, // key length, in bytes
0xf1,0x0e,0x25,0x7c,0x6b,0xce,0x0d,0x34 // DES key with parity
};
We can see that our example also uses DES using CBC mode of operation, we also see that the DES key is passed as the last 8 bytes (with byte of parity) of the array.
Ok so the bread and butter of this problem is knowing how the mersenne twister works.
Reversing mersenne_twister
This is what the code looks like:
We can see that there are two loops.
Here is the decompiled code, it looks really clean after some type changes
Looks like a normal getrandom function from mt19937 but the thing is, it is not. Because the length of the array is 351, this is called mt11213.
Putting it all together
After looking on the internet for some constants I found this page, maybe we can work with that.
The only difference with the program was the factor, also I had to change from long to int because this was written for a 32 bit machine (I spent two hours debugging this lol).
I wrote a program to generate all possible keys from october 2019 to february 2020.
#include<math.h>#include<stdio.h>#defineRAND_MASK 0x3FFFFFFF
#defineN 351
#defineM 175
#defineR 19
#defineTEMU 11
#defineTEMS 7
#defineTEMT 15
#defineTEML 17
#defineMATRIX_A 0xE4BD75F5
#defineTEMB 0x655E5280
#defineTEMC 0xFFD58000
staticunsignedintmt[N];
staticintmti=N;
externvoidset_seed (intseed) {
unsignedints = (unsignedint)seed;
for (mti=0; mti<N; mti++) {
// s = s * 29943829 - 1;
s = s * 29945647 - 1;
mt[mti] = s;
}
return;
}
voiddump() {
for (inti = 0; i < N; i++) {
printf("%x\n", mt[i]);
}
}
intgenrandom () {
unsignedinty;
if (mti >= N) {
constunsignedintLOWER_MASK = (1u << R) - 1;
constunsignedintUPPER_MASK = -1 << R;
intkk, km;
for (kk=0, km=M; kk < N-1; kk++) {
y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
mt[kk] = mt[km] ^ (y >> 1) ^ (-(y & 1) & MATRIX_A);
if (++km >= N) km = 0;
}
y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ (-(unsignedint)(y & 1) & MATRIX_A);
mti = 0;
}
y = mt[mti++];
y ^= y >> TEMU;
y ^= (y << TEMS) & TEMB;
y ^= (y << TEMT) & TEMC;
y ^= y >> TEML;
return y&0xff;
}
intmain(void) {
for (intt = 1569888000 /*1546300800*/; t < 1582583270; t++) {
set_seed(t);
for (inti = 0; i<8; i++) {
printf("%x", genrandom() ^ 0x55);
}
printf("\n");
}
}
This generates a 263 MiB file:
gcc bruteforce.c && ./a.out > keys.txt
Then I wrote a little program in python to try to brute force the key, since we know that the file is png, and the first 8 bytes are fixed.
from Crypto.Cipher import DES
cipher = "cd0c8716e99ae841".decode("hex")
withopen("keys.txt") as myfile:
lines = myfile.read().splitlines()
p = 0.01
pas = p
l = float(len(lines))
for i, key inenumerate(lines):
if i / l >= p:
print("{}%".format(p * 100))
p += pas
keyh = key
key = key.zfill(16).decode("hex")
out = DES.new(key).decrypt(cipher)
if out[0] == chr(0x89) and out[1] == chr(0x50) and out[2] == chr(0x4e) and out[3] == chr(0x47) and \
out[4] == chr(0x0d) and out[5] == chr(0xa) and out[6] == chr(0x1a) and out[7] == chr(0x0a):
print("FOUND .....")
print(keyh)
exit(0)
After 5 minutes I find the key, and I decrypt the image:
from Crypto.Cipher import DES
key = "a051b8a16f8542da".decode("hex")
withopen("flag.png.enc") as myfile:
image= myfile.read()
content = DES.new(key, DES.MODE_CBC, IV="\x00" * 8).decrypt(image)
withopen("flag.png", "w") as myfile:
myfile.write(content)
In this challenge, I implemented the mersenne twister
classMT19937(object):
W, N, M, R = 32, 624, 397, 31
A = 0x9908B0DF
U, D = 11, 0xFFFFFFFF
S, B = 7, 0x9D2C5680
T, C = 15, 0xEFC60000
L = 18
F = 1812433253
LOWER_MASK = (1 << R) - 1
UPPER_MASK = (~LOWER_MASK) & 0xffffffff
def__init__(self, seed):
self.mt = []
self.mt.append(seed)
for i inrange(1, self.N):
self.mt.append(self.F * (self.mt[i - 1] ^ (self.mt[i - 1] >> (self.W - 2))) + i& 0xffffffff)
self.index = self.N
defextract_number(self):
ifself.index == self.N:
self.twist()
y = self.mt[self.index]
y ^= (y >> self.U) & self.D
y ^= (y << self.S) & self.B
y ^= (y << self.T) & self.C
y ^= (y >> self.L)
self.index += 1
return y & 0xffffffff
deftwist(self):
for i inrange(self.N):
x = (self.mt[i] & self.UPPER_MASK) + (self.mt[(i + 1) % self.N] & self.LOWER_MASK)
xA = x >> 1
if x & 1 != 0:
xA ^= self.A
self.mt[i] = self.mt[(i + self.M) % self.N] ^ xA
self.index = 0
Challenge 22
This challenge teaches why you shouldn't see your MT19937 with curent time
from set3 import MT19937
defbreak_mt19937_seeded_time(timestamp, num, lim=1000):
for i inrange(timestamp-lim, timestamp):
obj = MT19937(i)
num2 = obj.extract_number()
if num2 == num:
return i
returnNone
Challenge 23
Given enough consecutive outputs, you can clone the mersenne twister, 624 in the case of MT19937:
from set3 import MT19937
defclone_mt19937(numbers):
T, C = 15, 0xEFC60000
L = 18
U, D = 11, 0xFFFFFFFF
S, B = 7, 0x9D2C5680
mt = []
for number in numbers:
y = number
y ^= (y >> L)
y ^= (y << T) & C
for _ inrange(S):
y ^= (y << S) & B
for _ inrange(U):
y ^= (y >> U) & D
mt.append(y & 0xffffffff)
obj = MT19937(0)
obj.mt = mt
obj.index = obj.N
return obj
If you think about how to protect this, the weak link is the temper function which can be easily "untempered", so you can implement one way functions like hashing functions, which will render untempering, computationally unfeasible.
Challenge 24
Recovering a 16 bit seed used for encryption:
from set3 import MT19937
from Crypto.Util.strxor import strxor
from Crypto.Random import random
from Crypto.Util.number import long_to_bytes
classMT19937Cipher(MT19937):
def__init__(self, seed):
super(MT19937Cipher, self).__init__(seed & 0xffff)
defgen_8_bit_val(self):
returnself.extract_number() & 0xff
defmt19937_cipher_oracle(ciphertext, key):
obj = MT19937Cipher(key)
randlen = random.choice(range(10))
ciphertext += long_to_bytes(random.getrandbits(randlen * 8))
s = ""for i inrange(len(ciphertext)):
s += long_to_bytes(obj.gen_8_bit_val())
return strxor(s, ciphertext)
defbreak_mt19937_cipher(ciphertext, plaintext):
for i inrange(0xffff):
obj = MT19937Cipher(i)
s =""for _ inrange(len(ciphertext)):
s += long_to_bytes(obj.gen_8_bit_val())
if plaintext in strxor(s, ciphertext):
return i
Tests
#!/usr/bin/env pythonimport unittest
from base64 import b64decode
from test import support
from set3 import produce_ciphertext, break_cbc_padding_oracle, cbc_padding_oracle, form_nonce, aes_ctr_encrypt_decrypt,\
break_ctr_reused_nonce_substitutions, MT19937, break_mt19937_seeded_time, clone_mt19937,\
mt19937_cipher_oracle, break_mt19937_cipher
from set2 import encryption_get_oracle_func, generate_random_key
from set1 import unpadpkcs7
from Crypto.Random import random
classSet3(unittest.TestCase):
deftest_ch17(self):
key = generate_random_key()
oracle = encryption_get_oracle_func(key, cbc_padding_oracle)
lst = ["MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc=",
"MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic=",
"MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw==",
"MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg==",
"MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl",
"MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA==",
"MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw==",
"MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8=",
"MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g=",
"MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93"]
for plaintext in lst:
#test funcsciphertext = produce_ciphertext(plaintext, key)
self.assertTrue(oracle(ciphertext))
self.assertEqual(unpadpkcs7(break_cbc_padding_oracle(oracle, ciphertext)), plaintext)
deftest_ch18(self):
cipher = b64decode("L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==")
key = "YELLOW SUBMARINE"nonce = form_nonce(0)
self.assertEqual(aes_ctr_encrypt_decrypt(cipher, key, nonce),
"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby ")
deftest_ch19(self):
# this is a many time pad problemplaintexts = []
ciphertexts = []
key = generate_random_key(16)
withopen('static/19.txt', 'r') as myfile:
for line in myfile.read().splitlines():
plaintexts.append(b64decode(line))
for plaintext in plaintexts:
nonce = form_nonce(0)
ciphertexts.append(aes_ctr_encrypt_decrypt(plaintext, key, nonce))
break_ctr_reused_nonce_substitutions(ciphertexts)
raiseNotImplementedErrordeftest_ch20(self):
plaintexts = []
ciphertexts = []
key = generate_random_key(16)
withopen('static/19.txt', 'r') as myfile:
for line in myfile.read().splitlines():
plaintexts.append(b64decode(line))
for plaintext in plaintexts:
nonce = form_nonce(0)
ciphertexts.append(aes_ctr_encrypt_decrypt(plaintext, key, nonce))
raiseNotImplementedErrordeftest_ch21(self):
obj = MT19937(1337)
self.assertEqual(obj.extract_number(), 1125387415)
deftest_ch22(self):
import time
time.sleep(random.choice(range(1, 10)))
time_now = int(time.time())
orig_seed = time_now
obj = MT19937(time_now)
num = obj.extract_number()
time.sleep(random.choice(range(1, 10)))
i = break_mt19937_seeded_time(int(time.time()), num)
self.assertEqual(i, orig_seed)
deftest_ch23(self):
for randseed in [random.choice(range(100000)) for _ inrange(10)]:
obj = MT19937(randseed)
numbers = []
for i inrange(624):
f = obj.extract_number()
numbers.append(f)
obj2 = clone_mt19937(numbers)
self.assertEqual(obj.extract_number(), obj2.extract_number())
deftest_ch24(self):
randseed = random.choice(range(0xffff))
plaintext = "A" * 14
cipher = mt19937_cipher_oracle(plaintext, randseed)
self.assertEqual(randseed, break_mt19937_cipher(cipher, plaintext))
if__name__ == "__main__":
support.run_unittest(Set3)
This could also be done with a side channel attack because CBC needs an IV, it could be fixed by getting the IV generation out of the branch.
defcheck_block_mode(oracle=encryption_oracle):
out, result = oracle("\xff" * 48)
if out[16:32] == out[32:48]:
return AES_ECB_MODE, result
else:
return AES_CBC_MODE, result
Yeah this is lame.
defcheck_block_mode_decoupled(oracle=encryption_oracle):
""" Lame but I need the ret value of the other one """out = oracle("\xff" * 48)
if out[16:32] == out[32:48]:
return AES_ECB_MODE
else:
return AES_CBC_MODE
Challenge 12
from set2 import aes_ecb_encrypt
from set1 import paddpkcs7
from string import printable
import base64
defencryption_oracle(plaintext, key):
buff = "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg\aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq\dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg\YnkK"return aes_ecb_encrypt(paddpkcs7(plaintext + base64.b64decode(buff), 16), key)
This tries to generate 2 consecutive blocks, if the goal is found stop, that's the block size.
defguess_block_size(oracle):
""" Only works for ecb mode """prevblock = Nonefor i inrange(2, 40):
block = oracle("\xff" * i)[:i]
if prevblock:
if block[:i-1] == prevblock:
returnlen(block) - 1
prevblock = block
raiseException
Added the prefix to use the attack for the harder challenge.
defbreak_ecb_oracle(oracle, blocksize, prefix="", startindex=0):
found = ""bl = startindex // blocksize
while 1:
lookup = {}
bts = prefix + "A" * ((blocksize - (len(found) % blocksize)) - 1)
for c in printable:
lookup[oracle(bts + found + c)[startindex:blocksize * (len(found) // blocksize+1+bl)]] = c
try:
found += lookup[oracle(bts)[startindex:blocksize * (len(found) // blocksize+1+bl)]]
exceptKeyError:
breakreturn found
Challenge 13
import urlparse
from collections import OrderedDict
from set2 import aes_ecb_encrypt, paddpkcs7, aes_ecb_decrypt
from set1 import unpadpkcs7
defkey_value_parse(s):
d = {}
for k, v in urlparse.parse_qs(s).items():
d[k] = v[0]
return d
defprofile_for(email):
email = email.replace('=', '').replace('&', '')
d = OrderedDict()
d['email'] = email
d['uid'] = '10'd['role'] = 'user'return'&'.join(map(lambda x: x[0] + '=' + x[1], d.items()))
defencryption_oracle(cleartext, key):
return aes_ecb_encrypt(paddpkcs7(profile_for(cleartext), 16), key)
defdecryption_oracle(cipher, key):
return key_value_parse(unpadpkcs7(aes_ecb_decrypt(cipher, key)))
The attack is straight forward as the name implies:
