Breaking Half of The Telegram Contest

int i;
for (i = 0; i < 64; i++) {
    *(((int *)random) + i) ^= mrand48 ();
}

int x[3];
x[0] = CODE_ping;
*(long long *)(x + 1) = lrand48 () * (1ll << 32) + lrand48 ();
encrypt_send_message (c, x, 3, 0);

import hashlib
from Crypto.Cipher import AES
import sys
import string

def xor(a, b):
	return "".join(map(chr, [ord(x) ^ ord(y) for (x,y) in zip(a,b)]))

key1 = """5e a6 0d a2 9c 90 8e f4 36 d5 48 fe 76 a3 11 f6 66 13 4e 94 bb 11 32 d6 cf fd b0 2f 7b 77 bb 01 d7 42 a4 22 d3 04 e7 d2 fc 5b 32 48 d6 71 eb 18 51 19 99 76 49 46 1a 43 d8 cf cd 8a e2 fe 42 2c 36 d7 05 8b 0c 5e 00 8a 5a bc 35 4f ec 75 b4 10 e1 84 bb cb af ec e3 d6 fd 59 fd 01 83 ef 8b dd 13 50 24 5b 80 09 75 7e c3 c3 08 ba 59 f4 ec c0 87 71 ba 9f 45 8c 15 df 2a cd a5 bc 81 a9 20 fe 42 e2 65 78 02 77 80 11 0e e4 67 f3 40 cf 72 be fc c2 8d 0b ad d9 9e 6e 1a c3 03 71 39 be b9 dd df 7c 63 a6 27 45 ee 8e 00 5e 12 51 51 6c 6a 10 a6 73 3a 10 5d d8 f3 b6 c5 70 fe 91 c2 64 4b d0 74 2d 47 e7 4e 00 cf d5 d3 65 15 2b 48 9c 75 eb a8 96 aa ce 09 49 9b 5e ea 76 06 19 f3 b3 e7 7b af df 5d 68 5e 80 10 48 ec 00 35 90 d3 e5 96 c6 59 a7 44 d8 20 a8 a2 b6 93 64 4f 98 44 23 8e fd""".replace(" ", "").decode('hex')
key2 = """63 ab 0d b7 98 e1 78 ef 5f 05 9c e4 84 3b 53 b3 4f 6e d1 d3 8a 6d 59 19 32 26 73 60 c2 e2 fe ee d3 2d 74 35 18 08 ba 04 87 cf 7f d9 87 4b 64 d5 80 06 05 f5 01 56 6d c2 66 7e 2d ef f6 a3 82 3d 31 0e ed 6b 46 4c 11 d5 ec 0f 7b be 64 79 26 87 a9 d3 34 27 d8 8b aa b5 36 8b 95 2f a7 c7 2a a6 bf a9 44 51 c5 c8 06 04 78 d2 64 87 e8 13 f3 f0 9b c9 8c bc 29 01 55 a2 80 e1 e8 4e 74 53 7e 05 22 1b 51 3d 1a c5 61 b3 04 98 c2 2f 71 e3 76 2e 31 bd d8 55 15 4b 3e 34 ed 84 b2 56 d0 bd c6 9a 1a 2a 4b 2f fc 68 8e c4 e3 81 23 6f 07 3f 3a 6b 56 f6 ee 31 e6 aa 0d 49 36 6a 51 79 25 bf b6 40 64 8c e2 14 c8 70 37 cb 70 ad a1 83 ed 1f b9 78 b9 93 0c 7c 0c ed 6d c6 aa c2 d0 da 51 ce ae cf 99 8f 65 eb 5a 42 e6 ff 4a 51 a9 97 da 6e ac e5 63 c1 05 a9 fe d0 da da 43 e3 50 14 fc b1 46 ea""".replace(" ", "").decode('hex')
key3 = """16 0c be 58 e1 74 74 f5 f9 8f f8 82 71 ed 57 84 20 49 bd da 17 0e 00 a8 a4 24 71 79 86 1f ef 3e 41 70 31 de c9 c2 19 23 37 fd ec 2f fa 9e 89 29 4f a2 af 69 cf 24 3a 6e 44 5d 89 d2 8b 50 45 26 3c ff e3 d4 4d 7d b4 88 54 8c 87 09 c5 ac 09 5c e6 62 43 73 b5 3e 96 ea f3 62 76 58 1b fd 8a 36 45 65 4a fc 7b ee 7b 13 06 e5 2f 9d 8f cb b9 a7 6f 76 00 f4 9a ab 50 fb 91 e0 2b ce 28 db 95 02 a0 62 33 bb e7 41 13 7b 2c 7e ba 7c d5 87 12 33 de 44 8d 4b 76 af 59 cc 80 42 02 69 56 90 8a 5d 95 0b 3e 8b ef 65 17 fc 79 62 b4 69 1b 21 aa 89 5b 22 f6 33 67 80 d0 22 f7 76 f2 6c 4b af 69 07 0f 2c 3a af 67 6b 74 c0 7f 8c 83 85 85 8e 47 b7 55 42 c1 3d 70 33 9d 87 60 7c f6 8b 99 96 1d af 82 b8 d2 37 c7 a3 fc ac 25 fe 77 f0 29 4d 82 a4 15 89 cb c2 27 ae 4f 16 d6 b8 4c cb de 2a 59 d7""".replace(" ", "").decode('hex')
key4 = """b4 aa dc bc 8e e5 6a f4 9f 7b 65 de cd 1c 28 3d f1 58 f6 03 e1 34 9d 63 54 b0 15 a7 b8 a6 45 4e de dd cd e4 1a 54 d7 9b fe 46 05 c7 62 19 d9 7a c0 00 6b e6 72 83 3d 15 00 99 d9 9b 97 c0 4a a8 85 e7 85 3c 3f a4 2f 6a 57 0b 3c b0 2a 97 65 6f bf 4e 0d 93 f7 55 3b 3a 39 a1 1a 0f db 9d 7a df 5b c6 9b 45 9a ea e4 27 92 8c c3 d2 75 53 66 e4 1c 29 f1 14 fc fd e8 c0 c8 12 47 ee 5a 92 f1 bf 1f 6f 8e 95 a5 90 81 37 d6 5d bd 5c 4c 41 61 29 6e 4f 7e 83 e1 b9 ef 00 00 de 25 33 f4 df 1a 94 f0 e7 1c fd 35 c0 75 65 88 ef c5 aa b5 c9 7d 0e e4 6d b7 9f 10 ca 4b f0 c9 c7 2d 30 20 e9 e1 b8 03 de a2 60 4e 3f 59 dc 36 a2 50 f8 52 5e 32 c8 c1 84 87 84 d6 54 42 dd ab b4 1b d6 fe e4 29 d3 70 4e 3e 48 ba 86 80 39 b7 94 3c 31 18 f8 bd 7b d8 89 6b 32 77 5c 89 4a a1 ca 18 ba 1e 6a 87 6a""".replace(" ", "").decode('hex')
key5 = """4c 76 1f 87 08 53 54 cb 12 fd 01 bd bd e6 42 d2 6b 47 4b d8 0b 6a eb 9f 24 8b ee 77 1f 8b a5 3f f5 f1 c7 80 05 80 2c 20 29 7c 3c 14 59 2b 5e 7f 69 58 3b 7e 07 37 25 67 3d 18 ac f2 28 43 63 8f a5 41 c1 ba 53 dd eb 3d 36 0d 7b d3 14 f7 f9 83 aa 0c 81 20 89 e0 c7 d7 e9 ef 11 aa 43 ca 54 2a 9f 69 0f 1d 99 ef f6 55 14 71 6d a3 1e c2 75 fb 1c 88 f7 c0 21 64 5d 34 db 3f a4 e7 a9 f0 af 9f 9d 14 a4 3a 49 7c 50 e6 45 24 3a cb a4 a6 2a 35 dd 6c 9c ce 87 24 d1 ff 13 19 15 43 89 a4 8c 39 66 a2 22 df 4e 94 76 e1 89 b5 03 7a 2b 34 e7 39 09 f9 22 5d cb 36 4e ce 37 e7 cf 7d ab b5 8b db 81 c6 c8 f4 c7 7c 3a 22 59 fc e6 32 19 aa 46 d2 95 96 61 61 e6 cc 57 f0 0e 87 5c 7d 5b 87 e7 64 28 c6 03 38 3c 0b a6 5e 4a 21 a3 67 af e5 b3 88 cc 9d 03 98 33 ac c6 87 b4 b6 82 42 c4 41 33 39""".replace(" ", "").decode('hex')

keys = dict()

# build a dict for the key_ids
for key in [key1, key2, key3, key4, key5]:
	m = hashlib.sha1()

	m.update(key)

	key_id = m.hexdigest()[-16:]
	keys[key_id] = key

# only these 4 messages are needed
ping = """1387395163.10 73 OUT 116.51.22.2:443 12 25 5d 0b 4a 41 17 51 ee b0 54 b7 a7 62 9d 8b 50 d9 9e 03 ed 77 1f f1 ce 97 60 be 2d 82 2a 41 00 cf 20 c3 58 d7 c3 9a 81 7d 8b 0d db db 65 0b 65 a3 bb 63 d4 c5 be c5 54 85 7b 77 22 40 0e ef 98 3b ad 39 9c fc 8b 8e 7a"""
dh_params = """1387395172.80 604 IN 174.140.142.6:443 7f 96 00 00 8d f7 8b 84 76 9f e9 98 e0 99 b0 cc 6b c3 e5 42 31 c2 98 65 0c c1 b8 13 31 f9 da cd 80 49 87 88 91 98 2e 65 ce 16 98 b4 8c 1b d4 ef 49 13 cc e4 94 55 64 2b 93 65 14 d7 b9 cb f5 a5 8b cb c4 34 c7 77 2f c9 8c 74 5f b2 8b de cc c2 3d b6 9e a6 84 92 ac 55 e9 74 8d 29 77 5e 0e f5 b5 e5 8e b7 bc 08 e1 f5 02 ef a9 44 db 64 53 40 d8 10 62 07 86 f1 95 a7 2b 3f eb 68 ee 11 e0 7b 70 bc c1 ef 46 ae 9c 30 3d ed 4f 2a b9 d6 21 d0 6d c1 66 03 90 72 5c 2d 1c c8 9e 15 bd a3 c2 7b 19 1b f5 41 a3 54 8b d3 77 54 ec 74 5c 7b f3 3d 54 7f 8f cc 08 83 df c1 09 fd 72 9c 9c 94 74 2a 95 df 52 78 33 86 9e 67 fa 78 42 f4 63 43 3d cb e3 bd df 1e d1 c8 c0 41 84 6f 47 c3 6d bf 22 eb c5 2c 83 de af b0 70 4b e8 9b a0 d8 dd 85 d7 87 31 a4 f2 f4 5c d7 65 15 c4 42 7d 61 80 4e 09 03 3d 1f 82 26 3b 9a ed c8 3d 28 4c 57 57 b5 9a 38 ef d2 11 23 7c 55 f1 04 4d f0 c1 c9 43 81 ae 78 62 4f c9 25 b1 a3 02 5a d0 58 c5 79 5e 93 e2 47 31 a3 d1 fb 7c 20 64 d9 1b 9b 44 d1 dc f4 2d 51 fe 36 1f 55 7f d9 f1 0b cc c4 9a 9c 65 b9 dd a2 5e 65 c6 37 32 55 6c e2 c6 1d 88 24 aa 27 05 0f 43 b7 62 50 65 3c 4a 60 a9 ae 00 59 dd c6 b9 23 97 c4 a3 34 18 fb 3b 62 8e ed 0d 93 e9 c3 ec 25 e6 8b d5 f9 5a ec 54 86 76 92 fa 37 2d 8e d6 1c d2 9f b9 1b 97 ed 90 b3 3e 20 d5 7a db bf 03 51 4a b5 ca 6f 2e 08 2b 52 94 9f 57 11 68 d6 74 89 a8 59 4e 1c fa 69 26 18 70 e7 e3 53 e4 dd 0a 01 74 7a 4a 5e ed a0 11 de 9f 95 02 cb f1 15 92 33 11 60 05 4a 8d 00 37 d9 cc 7c 79 80 57 dc f9 e6 15 18 24 a6 17 4c 30 b5 64 d8 bc cb 74 44 07 34 c4 f4 5b 71 a5 10 25 3e 46 64 38 ad 62 1f 72 b1 71 b4 58 e6 6b aa b2 57 0f a9 44 0a 47 cf fd 82 b6 e9 7c e1 9e cc 92 51 bd 73 5f c2 97 fc 99 00 3f 01 f8 76 e5 e3 26 f5 92 72 b6 15 3a b5 60 06 8e 7f 90 e1 73 7e db ff 63 80 bc e3 c3 8d bd ea 19 e5 a4 55 6f c2 c8 9d 3c bf 60 3f ea 8e 36 99 55 10 cf f9 d8 68 8a c6 d8 72 95 5a"""
create_secret_chat = """1387395172.81 345 OUT 174.140.142.6:443 56 8d f7 8b 84 76 9f e9 98 e7 a3 98 6b 82 27 c9 0e e4 65 2f 79 af 8d 7c c6 b4 c8 d4 43 d0 70 a1 66 ae 48 92 d7 cf 4b ef e0 bd be 1a 27 90 a7 92 3e 33 de 74 82 0f ab f3 4a 81 ad de df ff aa e1 0c a0 c2 3b 60 1a 7c 30 e5 2c 00 93 79 2f 6b 99 24 45 76 7d 59 82 90 0b e5 9d 1b 49 99 2a c1 d8 ba a1 36 e0 37 26 43 1d 44 b3 54 63 41 d5 6e 5f ec 49 c1 1d a6 35 07 4a 58 57 8f d4 63 e2 d2 44 54 30 fd 8f 48 b9 38 b1 be 74 0d 44 36 1e b3 45 eb a9 1e 91 24 07 f2 0d d6 97 68 de 00 32 30 2b ac c5 83 0d d0 f6 1b 3b 89 be f4 f1 8b b4 93 39 21 dd 2f 9c 57 4f e8 4a e1 3f 03 9f e3 e7 5e d6 2d fb 44 2c df 28 80 4e d5 33 7b 9f f0 14 19 b8 1c 35 6c 31 f4 12 24 64 19 5e 3b e7 a4 3c 6a b2 6b 46 93 ae 8b b5 0c 2c 36 4c ca 07 7b 82 e2 5a fe 6f d6 1d d4 4b d8 4f 9b bf 9a 69 af ed d9 c0 70 6c 31 01 65 c6 e9 46 70 12 ba 95 1e 7e f2 ae de be 02 12 0c ba d4 a7 1c 7b d2 94 c3 43 29 f5 88 19 81 78 2b 44 04 4c 10 6c a3 75 d9 3d 31 29 f9 38 55 5b 8e ad c3 39 68 fd b4 a0 2c 64 2e 2c 80 37 35 86 fd 30 b2 78 1b 49 4a ca c0 30 c3 31 f9 74 a2 d4 35 16 54 db 29"""
secret_chat_response = """1387395173.70 780 IN 174.140.142.6:443 7f c2 00 00 8d f7 8b 84 76 9f e9 98 7e cf b0 9c c0 14 31 a5 d8 68 cd 35 ac 0d c9 f7 69 61 7c 93 cc b8 4a 4f 18 44 bd 25 c3 c8 ff 43 12 02 b5 54 09 18 bd 00 5e b4 c8 54 92 65 a8 9c 6b a2 43 b5 3a 32 6b 38 ed 92 86 c3 14 1d ee d8 31 b7 8a c7 5f 19 33 88 07 96 e0 a9 de b6 77 8b 3f 4c d5 46 29 d1 55 05 ca ec 30 f9 4c 3a ff 68 fe 7f 53 b6 f8 14 43 84 3c d7 14 65 60 bb 6c 97 01 89 1d 49 a5 c4 89 16 ff e6 9e 0e 71 02 ff d9 43 8a 47 47 45 00 3b 1c 4a 94 1d f8 8b 08 6a 2e 96 3c e3 7b 68 e9 e9 32 a5 e1 6e ab c4 9a 16 a9 89 41 39 69 b9 b0 25 8a 4e 98 26 78 f8 cf ee 48 2a 91 c4 e8 4b e2 25 f0 2a 89 53 cf a9 68 08 49 81 c2 66 be d3 d0 61 54 9a 36 0d 30 b7 f9 17 4d 0d f8 b8 33 fe 5b b1 6c 07 a6 82 cd a0 95 e9 08 3d 06 c1 0d af 76 9c 1a 7b a7 d6 dc e7 09 81 e0 9a 3c 87 82 0c ae 54 08 c0 08 57 c7 36 bf a8 19 de 29 9e ab 93 01 5e 36 a5 0d 34 61 9a c2 fe 68 d1 5d 78 9f 3a 8e 9b 4f d6 42 a7 7d b6 2e b7 cf 89 df 8c 21 f4 82 11 7a b7 3b 52 41 1f e3 ec c6 6e f3 de 8d 91 fe 0e 44 5f c9 93 7b 4b bd c0 12 ef 12 44 49 2e 46 97 d0 90 01 37 cd 04 fb 65 2d 6b 1e 3f f5 0c 43 a1 06 fd d5 48 c4 e2 51 b0 a5 9e 9d fa f3 6b 37 3e d8 81 5c 56 02 b2 a1 a4 63 78 16 02 3c 85 5c 0f 45 ff 57 a7 ca d0 6d 13 5c 2e ec c3 31 b6 44 58 2c cb 01 b1 86 00 0e 5b e4 03 90 a9 d7 ca fc 0a 77 f5 22 fd 77 b1 e8 ed 39 c3 59 7e a1 58 61 b8 e5 1d 86 28 0d f3 3c 3c 40 1b 2a 7c 24 90 c4 85 0c df 68 fd 5c c4 3e 93 ed b6 0b 1c 85 d2 83 30 c1 02 fd b6 0b 6b 05 4d 8f 0c 47 84 54 23 3c 56 5b 85 02 19 24 ff 66 7a 7c 60 5a 36 9d 36 98 78 59 f3 75 8f 2f 94 02 4c cb fc a8 9c 0c 48 08 00 ba 28 8d 8b 2e 14 0e 9b b1 39 71 20 31 6c bb ba ec cc 04 f1 3c ae 1b 54 76 f7 4e 04 dc 8f eb c6 84 2b c5 e9 56 93 dc c6 cc 5b f9 2c da 61 9d 23 2c 64 96 21 d6 f5 63 a5 5a d6 8d 9a 50 c4 e6 24 4a 1c 6e 41 45 79 92 23 db 20 c1 66 e1 cc 8d 9c 4b 0e 48 93 e9 38 05 bf f9 e0 2e cc 86 89 8f 2d 75 c1 fe ae 6c 62 ac da 07 49 2b ae f1 a4 0e a7 6e e1 61 e8 9e 8d 58 66 1f 8e 08 1c 97 07 77 cc 07 ba 11 b5 d3 31 ec 34 d3 80 41 86 87 10 a7 15 ec da 5c a0 71 f7 f2 70 84 02 ba 5e 1f 1b fb 93 cb 84 37 ca 10 07 90 b3 fe 54 3e c1 7f c2 46 7a 08 27 1f 6f 70 46 69 53 52 a3 1a 97 b8 c5 be 66 21 ee 94 77 17 91 69 23 42 74 d3 e8 bc 45 69 51 d4 bd 53 f1 9d 04 0c a6 75 a6 27 09 44 3c 17 9d b7 23 fc 5a f0 bf f1 02 e4 a7 50 01 76 6a 3f cd 35 b4 2f bb 43 14 b8 bb e7 d0 fb a4 df 8f b6 4b a8 1c 19 15 06 ce 66 05 2b"""

def decrypt(message):
	message = string.split(message, " ", 4)
	if message[2] == "IN":
		x = 8
	else:
		x = 0
	
	message = message[4].replace(" ", "").replace("\n", "").decode('hex')

	# Skip the length, we don't care
	if ord(message[0]) == 0xef:
		message = message[2:]
	elif ord(message[0]) == 0x7f:
		message = message[4:]
	else:
		message = message[1:]

	auth_key_id = message[0:8].encode('hex')

	if not auth_key_id in keys:
		print("Auth key not found: %s" % auth_key_id)
		return None

	key = keys[auth_key_id]

	msg_key = message[8:24]
	message = message[24:]

	sha1_a = hashlib.sha1(msg_key + key[x:32+x]).digest()
	sha1_b = hashlib.sha1(key[32+x:48+x] + msg_key + key[48+x:64+x]).digest()
	sha1_c = hashlib.sha1(key[64+x:96+x] + msg_key).digest()
	sha1_d = hashlib.sha1(msg_key + key[96+x:128+x]).digest()

	aes_key = sha1_a[0:8] + sha1_b[8:20] + sha1_c[4:16]
	aes_iv = sha1_a[8:20] + sha1_b[0:8] + sha1_c[16:20] + sha1_d[0:8]

	obj = AES.new(aes_key, AES.MODE_ECB)

	dec = xor(aes_iv[0:16], obj.decrypt(xor(aes_iv[16:32], message[0:16])))
	plain = dec
	
	for i in range(16, 16 * int((len(message) / 16)), 16):
		dec = xor(message[i - 16:i], obj.decrypt(xor(dec, message[i:i + 16])))

		plain = plain + dec
	
	return plain

ping_d = decrypt(ping)

# Find the rand48 outputs
r1 = ping_d[36:40]
r2 = ping_d[40:44]

# We have the upper 31 bits of the state, brute force the rest
start = int(r2[::-1].encode('hex'), 16) << 17
end = (int(r2[::-1].encode('hex'), 16) + 1) << 17

state = None

expected = int(r2[::-1].encode('hex') + r1[::-1].encode('hex'), 16)

for i in range(start, end):
	first = i
	# Constants from rand48
	second = (first * 0x5deece66d + 0xb) & 0xffffffffffff
	r = (first >> 17) * (1 << 32) + (second >> 17)

	if r == expected:
		state = i
		break

dh_params_d = decrypt(dh_params)
# Find p, assume g = 2 and the server-supplied randomness
p = int(dh_params_d[56:56+256].encode('hex'), 16)
g = 2
random = dh_params_d[320:320+256]

create_secret_chat_d = decrypt(create_secret_chat)
# Find the g_a value that was sent
g_a = int(create_secret_chat_d[60:60+256].encode('hex'), 16)

a = None

for i in range(0, 20):
	pr = ""
	j = state
	# Values from rand48
	state = (state * 0x5deece66d + 0xb) & 0xffffffffffff
	for i in range(0, 64):
		j = (j * 0x5deece66d + 0xb) & 0xffffffffffff
		next = j >> 16

		pr = pr + ("%02x%02x%02x%02x" % ((next >> 24) & 0xff, (next >> 16) & 0xff, (next >> 8) & 0xff, next & 0xff)[::-1])

	a = xor(random, pr.decode('hex')).encode('hex')

	new_g_a = pow(g, int(a, 16), p)

	if new_g_a == g_a:
		break

secret_chat_response_d = decrypt(secret_chat_response)

g_b = int(secret_chat_response_d[80:80+256].encode('hex'), 16)
nonce = secret_chat_response_d[340:340+256]

print(xor(nonce, ("%x" % pow(g_b, int(a, 16), p)).decode('hex')).encode('hex'))