この大会は2019/3/24 1:00(JST)～2019/3/25 1:00(JST)に開催されました。
今回もチームで参戦。結果は5582点で436チーム中42位でした。
自分で解けた問題をWriteupとして書いておきます。
HIDDEN (Misc)
証明書が有効になっていないので、証明書を見てみる。
発行者にフラグが入っていた。
Securinets{HiDDeN_D@tA_In_S3lF_S3iGnEd_CeRtifICates}
MAZE (Crypto)
101個の公開鍵と1個の暗号ファイルがある。この公開鍵の1つで暗号化されたと思われる。この101個の中の2個のnで共通の素数を持っていないかを探し、復号してみる。
from Crypto.PublicKey import RSA from Crypto.Util.number import * import itertools def egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q, r = b//a, b%a m, n = x-u*q, y-v*q b,a, x,y, u,v = a,r, u,v, m,n gcd = b return gcd, x, y def is_printable(s): for c in s: if ord(c) < 32 or ord(c) > 126: return False return True n_list = [] e_list = [] for i in range(101): file = 'chall/pub%d.pem' % i with open(file, 'r') as f: pub_data = f.read() pubkey = RSA.importKey(pub_data) n_list.append(pubkey.n) e_list.append(pubkey.e) e = e_list[0] for n_pair in list(itertools.combinations(n_list, 2)): p = egcd(n_pair[0], n_pair[1])[0] if p > 1: ps = [p] qs = [n_pair[0]/p, n_pair[1]/p] ns = [n_pair[0], n_pair[1]] with open('chall/cipher.txt', 'r') as f: c = int(f.read()) for i in range(len(ns)): phi = (ps[0] - 1) * (qs[i] - 1) d = inverse(e, phi) m = pow(c, d, ns[i]) flag = long_to_bytes(m) if is_printable(flag): print flag
結果、2つの公開鍵で共通する素数があったので、両方で復号してみると、片方がフラグになった。
securinets{rs4_1s_g00d_s0m3t1m3s!}
Useless Admin (Crypto)
Many Time Pad Attackのコード
https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py
を流用して、解読する。
#!/usr/bin/env python import string import collections import sets # XORs two string def strxor(a, b): # xor two strings (trims the longer input) return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)]) # 12 unknown ciphertexts (in hex format), all encrpyted with the same key c1 = "1b0605000e14000d1b524802190b410700170e10054c11480807001806004e4f1f4f01480d411400531158141e1c100016535a480c000c031a000a160d421e004113010f13451e0c0100100a020a1a4e165f500d0c1e041a090b001d0515521c0a0410000a4f4b4d1d1c184d071600071c0a521d1706540940" c2 = "1e10524e001f11481c010010070b13024f0704590903094d0c000e4f0711000615001911454217161a1a45040149000a5218404f1e0012060b1b590a1048171741140c01174c0d49174f0c8d4fc7520211531b0b0c1e4f" c3 = "1d0c04451352001a000154431b014109450a0a0b000045490403520a1d16490008535848085942071c0d0c57101c0045111c40430c4e111c0b1b1c451d4f071712010508475518061d00060a1b0a1a4c165d" c4 = "160d074300061d071b524e06190b134e450a0b0a4d4c12411d004f014045491b4649074804001100011d4504520612451e165d53064e164e1d060d0d44541a0041031b0b06540d1a070004001d4b074800531c04101d4f" c5 = "1a1d524912521548120045021b4e1506490a0859150345531d12521b4e094909030003011148420453074d161e05540b071e4c451b000a084a1d1c04084c0b45060b060a4742070618534218070210484512020043100e191e5956111a1c001c1f0b5c" c6 = "1a1d5248000154041a1c47430d0b04000005015900140c4f04534f094e08490103000000045442111b11001b1b1d000917535a48004e021d4a0e0b0044491c03080a001a024c11490748074f02040054451a1d150c1b150d020d0e" c7 = "1a1d5249125215481613500a1b0f0d4e4d0d1c0d000700001d1c001b06004f1d0f5a11480745040a011100181c0c540d13000e44085404404a061716014e010c0308104e084e0d4911450506011853540a5304120a1a154c0a1843001b45541c481607051b431f480d001e0400000c531d01011d00124441010200190d0800000000000e54060001100a1b4d0b040d105347" c8 = "0a0607000913020d551300041d0f0f0a0003061f154c034f1b53530602004e0c030c541f0454110a1d5a001e0649190419165d00104f104e1b1a101101001b0b1705051b0642040c5341114f0e4b104f0803110b0a060f42" c9 = "160d074300061d071b524e06190b134e450a0b0a4d4c12411d004f014045491b4649074804001100011d4504520612451e165d53064e16424a1810110c00060d04440e1c02411c0c00544209001953540d165009021a1542" c10 = "1e10524e001f11481c010010070b13024f0704590903094d0c000e4f0711000615001911454217161a1a45040149000a5218404f1e0012060b1b590a1048171741140c01174c0d49174f4201001f534b0b1c074b" c11 = "1a49134d4113540a0713490d434e160f541700174f4c11480c53520a1d1100000000190d4549114512544d12000c540402034b4e0d491d40" c12 = "1a4905410f06110c55064f430a00054e540c0a591603174c0d5f000d1b110006414c1848164516111f1100111d1b54001c17474e0e001c011f1d0a4b" ciphers = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12] # The target ciphertext we want to crack target_cipher = "1a1d5249125215481613500a1b0f0d4e4d0d1c0d000700001d1c001b06004f1d0f5a11480745040a011100181c0c540d13000e44085404404a061716014e010c0308104e084e0d4911450506011853540a5304120a1a154c0a1843001b45541c481607051b431f480d001e0400000c531d01011d00124441010200190d0800000000000e54060001100a1b4d0b040d105347" # To store the final key final_key = [None]*150 # To store the positions we know are broken known_key_positions = set() # For each ciphertext for current_index, ciphertext in enumerate(ciphers): counter = collections.Counter() # for each other ciphertext for index, ciphertext2 in enumerate(ciphers): if current_index != index: # don't xor a ciphertext with itself for indexOfChar, char in enumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts # If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one) if char in string.printable and char.isalpha(): counter[indexOfChar] += 1 # Increment the counter at this index knownSpaceIndexes = [] # Loop through all positions where a space character was possible in the current_index cipher for ind, val in counter.items(): # If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher! if val >= 7: knownSpaceIndexes.append(ind) #print knownSpaceIndexes # Shows all the positions where we now know the key! # Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back! xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150) for index in knownSpaceIndexes: # Store the key's value at the correct position final_key[index] = xor_with_spaces[index].encode('hex') # Record that we known the key at this position known_key_positions.add(index) # Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string) final_key_hex = ''.join([val if val is not None else '00' for val in final_key]) # Xor the currently known key with the target cipher output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex')) # Print the output, printing a * if that character is not known yet print ''.join([char if index in known_key_positions else '*' for index, char in enumerate(output)]) ''' Manual step ''' # From the output this prints, we can manually complete the target plaintext from: # The secuet-mes*age*is: Wh** usi|g **str*am cipher, nev***use th* k*y *ore than onc* # to: # The secret message is: When using a stream cipher, never use the key more than once # We then confirm this is correct by producing the key from this, and decrpyting all the other messages to ensure they make grammatical sense target_plaintext = "it is a capital mistake to theorize before one has data. insensibly one begins to twist facts to suit theories, instead of theories to suit facts." print target_plaintext key = strxor(target_cipher.decode('hex'),target_plaintext) for cipher in ciphers: print strxor(cipher.decode('hex'),key)
最終的な結果は上記のコードで、結果は以下の通り。
*t is a capixal m**toke *o theorn*e*before one has d*t*. *n}en*i*l* o***begins*vo*t*i************************************************************* it is a capital mistake to theorize before one has data. insensibly one begins to twist facts to suit theories, instead of theories to suit facts. how often have i said that when you have excluded the impossible whatever remains, however improbable, must be the truth. my name is sherlock holmes. it is my business to know what other people don・ｬ!"t know. never trust to general impressions, my boy, but concentrate yourself upon details. education never ends, watson. it is a series of lessons with the greatest for the last. it is a great thing to start life with a small number of really good books which are your very own. it has long been an axiom of mine that the little things are infinitely the most important. it is a capital mistake to theorize before one has data. insensibly one begins to twist facts to suit theories, instead of theories to suit facts. you have a grand gift for silence, watson. it makes you quite invaluable as a companion. education never ends, watson. it is a series of lessons, with the greatest for the last. my name is sherlock holmes. it is my business to know what other people do not know. i am a brain, watson. the rest of me is a mere appendix. i wanted to end the world, but i'll settle for ending yours.
Securinets{i wanted to end the world, but i'll settle for ending yours.}
