from sage.all import * from Crypto.Cipher import AES import os, json, itertools from pwn import * normal_deck = [''.join(card) for card in itertools.product("23456789TJQKA", "chds")] x = GF(2)["x"].gen() gf2e = GF(2 ** 128, name="y", modulus=x ** 128 + x ** 7 + x ** 2 + x + 1) def _to_gf2e(n): return gf2e([(n >> i) & 1 for i in range(127, -1, -1)]) p = int(""" FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE45B3D C2007CB8 A163BF05 98DA4836 1C55D39A 69163FA8 FD24CF5F 83655D23 DCA3AD96 1C62F356 208552BB 9ED52907 7096966D 670C354E 4ABC9804 F1746C08 CA237327 FFFFFFFF FFFFFFFF""".replace(' ', '').replace('\n', ''), 16) def shuffle(l): return [x for x in sorted(l, key=lambda x: int.from_bytes(os.urandom(2),byteorder='big'))] def encrypt(msg, e): return pow(msg, e, p) def decrypt(msg, d): return pow(msg, d, p) def _from_gf2e(p): n = p.integer_representation() ans = 0 for i in range(128): ans <<= 1 ans |= ((n >> i) & 1) return ans def inverse_ghash(key, vals): p = _to_gf2e(0) key = int.from_bytes(key, 'big') k = _to_gf2e(key) inv_k = 1/k p *= inv_k p -= _to_gf2e(8 * 16) p *= inv_k iv = _from_gf2e(p) iv = iv.to_bytes(16, 'big') result = [] for i in vals: i ^= key p = _to_gf2e(i) p *= inv_k p -= _to_gf2e(((8 * 16) << 64)) p *= inv_k result.append(_from_gf2e(p).to_bytes(16, 'big')) return iv, result def ghash(data, key, iv): cipher = AES.new(key, AES.MODE_GCM, nonce=iv) cipher.update(data) _, tag = cipher.encrypt_and_digest(b'') result = int.from_bytes(tag, byteorder='big') if result < 1 << 127: result += 1 << 128 return result ** 2 def find_order(encs): quotients = {} for i in encs: for j in encs: if i == j: continue q = i*pow(j, -1, p) % p if q in quotients: quotients[q] += 1 else: quotients[q] = 1 keys = [i for i in quotients] keys.sort(key=lambda x : quotients[x], reverse=True) q1 = keys[0] q2 = keys[1] maps = {} for c in encs: a = None b = None for o in encs: if c == o: continue if c*pow(o, -1, p) % p == q1: a = o elif c*pow(o, -1, p) % p == q2: b = o if a is not None or b is not None: maps[c] = {'a': a, 'b': b} starts = [] for m in maps: if maps[m]['a'] is None: starts.append(m) orders = [] for start in starts: order = [start] next = maps[start]['b'] while next is not None: order.append(next) next = maps[next]['b'] orders.append(order) orders.sort(key=lambda x: len(x), reverse=True) order = [] for o in orders: order.extend(o) return order def decrypt_cards(card, my_key, opp_key, safely_hashed_deck): opp_key = int(opp_key, 16) decrypted = decrypt(decrypt(int(card, 16), opp_key), my_key) if decrypted not in safely_hashed_deck: raise ValueError("Your key does not decrypt correctly!") return safely_hashed_deck[decrypted] vars = [ 190734863281250000000000000000000000000, 194549560546875000000000000000000000000, 198440551757812500000000000000000000000, 202409362792968750000000000000000000000, 206457550048828125000000000000000000000, 210586701049804687500000000000000000000, 214798435070800781250000000000000000000, 219094403772216796875000000000000000000, 223476291847661132812500000000000000000, 227945817684614355468750000000000000000, 232504734038306642578125000000000000000, 237154828719072775429687500000000000000, 241897925293454230938281250000000000000, 246735883799323315557046875000000000000, 251670601475309781868187812500000000000, 256704013504815977505551568750000000000, 261838093774912297055662600125000000000, 267074855650410542996775852127500000000, 272416352763418753856711369170050000000, 277864679818687128933845596553451000000, 283421973415060871512522508484520020000, 289090412883362088942772958654210420400, 294872221141029330721628417827294628808, 170145034790039062500000000000000000000, 173547935485839843750000000000000000000, 177018894195556640625000000000000000000, 180559272079467773437500000000000000000, 184170457521057128906250000000000000000, 187853866671478271484375000000000000000, 191610944004907836914062500000000000000, 195443162885005993652343750000000000000, 199352026142706113525390625000000000000, 203339066665560235795898437500000000000, 207405847998871440511816406250000000000, 211553964958848869322052734375000000000, 215785044258025846708493789062500000000, 220100745143186363642663664843750000000, 224502760046050090915516938140625000000, 228992815246971092733827276903437500000, 233572671551910514588503822441506250000, 238244124982948724880273898890336375000, 243009007482607699377879376868143102500, 247869187632259853365436964405505964550, 252826571384905050432745703693616083841, 170145034790039062499999960937500000000, 173547935485839843749999960156250000000, 177018894195556640624999959359375000000, 180559272079467773437499958546562500000, 184170457521057128906249957717493750000, 187853866671478271484374956871843625000, 191610944004907836914062456009280497500, 195443162885005993652343705129466107450, ] io = process(["python3", "chall.py"]) # io = remote("ctf.umasscybersec.org", 7002) io.recvuntil(b'I commit to this key: ') hash_key_enc = bytes.fromhex(io.recvuntil(b'\n').decode().strip()) io.recv() iv, cards = inverse_ghash(hash_key_enc, vars) hex_cards = [i.hex() for i in cards] io.sendline(iv.hex().encode()) io.sendline(json.dumps(hex_cards).encode()) io.recvuntil(b"Give me a deck of cards: Here's the deck we're using: ") safely_hashed_deck_keys = [int(i,16) for i in json.loads(io.recvuntil(b'\n').decode().strip())] safely_hashed_deck = {k: v for k, v in zip(safely_hashed_deck_keys, normal_deck)} safely_hashed_deck_reverse = {v : k for k, v in zip(safely_hashed_deck_keys, normal_deck)} io.recvuntil(b"You can check that the key I used matches my commitment: ") hash_key = bytes.fromhex(io.recvuntil(b'\n').decode().strip()) orig_ghashes = [x**2 for x in vars] io.recvuntil("Now, let's shuffle the deck!\n") shuffled_deck = json.loads(io.recvuntil(b'\n').decode().strip()) shuffled_deck = [int(i,16) for i in shuffled_deck] ordered = find_order(shuffled_deck) ordered_known = ordered[:] ordered.extend([i for i in shuffled_deck if i not in ordered]) encrypted_deck_mappings_reverse = {a:safely_hashed_deck[b] for a,b in zip(ordered_known, orig_ghashes)} encrypted_deck_mappings = {safely_hashed_deck[b]:a for a,b in zip(ordered_known, orig_ghashes)} cards_ordered = [ encrypted_deck_mappings["Td"], encrypted_deck_mappings["Jd"], encrypted_deck_mappings["Ac"], encrypted_deck_mappings["Ah"], encrypted_deck_mappings["As"], encrypted_deck_mappings["Ad"], encrypted_deck_mappings["Qd"], encrypted_deck_mappings["Kd"], ] cards_ordered.extend([encrypted_deck_mappings[i] for i in encrypted_deck_mappings if encrypted_deck_mappings[i] not in cards_ordered]) guessed_deck_order = [encrypted_deck_mappings_reverse[i] for i in cards_ordered] hexed_ordered_deck = json.dumps([hex(i) for i in cards_ordered]) io.sendline(hexed_ordered_deck.encode()) io.recvuntil(b"Here's my deck now, along with the hashes of the encryption: \n") new_enc = io.recvuntil(b'\n').strip() io.recv() io.sendline(new_enc) io.recv() my_hashes = [hex(ghash(hex(i).encode(), hash_key, iv)) for i in [1]*52] io.sendline(json.dumps(my_hashes).encode()) io.recvuntil(b'Here are the keys to your cards: ') opp_keys = [hex(i) for i in [1]*52] keys_0_1 = [i for i in json.loads(io.recvuntil(b'\n').strip().decode())] encrypted_deck = [i for i in json.loads(new_enc.decode())] io.recv() io.sendline(json.dumps(opp_keys[:2]).encode()) io.recvuntil(b'Give me my street keys: ') io.sendline(json.dumps(opp_keys[:5]).encode()) io.recvuntil(b'Give me your first two keys: ') io.sendline(json.dumps(opp_keys[:2]).encode()) io.interactive()