# YauzaCTF 21 - Crypto Challenges ## Shadows The challenge is composed of two files: ``` import json from Crypto.Util.number import bytes_to_long, getPrime from storage import flag def mul(x): m = 1 for i in x: m *= i return m if __name__ == '__main__': flag = bytes_to_long(flag.encode()) count = 25 threshold = 11 psize = 24 primes = list(sorted(getPrime(psize) for _ in range(count))) pmin = mul(primes[-threshold + 1:]) pmax = mul(primes[:threshold]) assert pmin < flag < pmax shadows = [flag % x for x in primes] with open('secrets.json', 'wt') as out_file: out_file.write(json.dumps({ 'shadows': shadows[1:threshold], 'primes': primes[:threshold], 'threshold': threshold })) ``` and ``` {"shadows": [7832917, 8395798, 4599919, 154544, 3430534, 4694683, 123690, 5911445, 7380167, 10597668], "primes": [8412883, 8889941, 9251479, 9471269, 9503671, 9723401, 10092149, 10389901, 10551241, 10665527, 11099951], "threshold": 11} ``` It is a Chinese Remainder problem, but one remainder is missing. However, the prime numbers are very small (24 bits). We solve this challenge by bruteforcing the missing remainder. ``` from sympy.ntheory.modular import crt import binascii shadow = [ 0, 7832917, 8395798, 4599919, 154544, 3430534, 4694683, 123690, 5911445, 7380167, 10597668] primes = [8412883, 8889941, 9251479, 9471269, 9503671, 9723401, 10092149, 10389901, 10551241, 10665527, 11099951] threshold = 11 n=0 while n < 0xffffffff: shadow[0]=n ct=hex(crt(primes,shadow)[0])[2:] if len(ct) % 2 ==1: ct="0"+ct pt=binascii.unhexlify(ct) if pt.lower().startswith(b"yau"): print(n,pt) n+=1 # 7717390 b'YauzaCTF{k33p_1t_1n_7h3_sh4d0w5}' ``` and the flag is **YauzaCTF{k33p_1t_1n_7h3_sh4d0w5}**. ## Knapsack The Knapsack challenge is only composed of : ``` flag= [12777998288638, 10593582832873, 7834439533378, 10486500991495, 14714582460036, 7568907598905, 12800035735033, 14724457772647, 11910445040159, 11202963622894, 10291238568620, 15103559399914, 13156142631772, 16988824411176] ba = [2948549611747, 2043155587142, 361533419625, 1001380428657, 2438250374319, 1059738568330, 115120002311, 198226659880, 2343897184958, 2592576935132, 2327834076450, 237536244289, 309228208827, 3327276767693, 462372704541, 2176574227058] ``` Please find here a description of the cryptosystem (https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem). In short, a superincreasing sequence (item i is bigger than the sum of all previous item) is used to create a linear combinaison with the bits of the plaintext (big endian). In our case, we solve this problem by using the LLL algorithm which recovers the individual bits of the plaintext. ``` # python3 -m pip install olll # https://www.math.ucsd.edu/~crypto/Projects/JenniferBakker/Math187/ import olll flag= [12777998288638, 10593582832873, 7834439533378, 10486500991495, 14714582460036, 7568907598905, 12800035735033, 14724457772647, 11910445040159, 11202963622894, 10291238568620, 15103559399914, 13156142631772, 16988824411176] ba = [2948549611747, 2043155587142, 361533419625, 1001380428657, 2438250374319, 1059738568330, 115120002311, 198226659880, 2343897184958, 2592576935132, 2327834076450, 237536244289, 309228208827, 3327276767693, 462372704541, 2176574227058] _flag="" for i in range(len(flag)): reduced = olll.reduction([ [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[0]], [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[1]], [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[2]], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[3]], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[4]], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[5]], [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -ba[6]], [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -ba[7]], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -ba[8]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -ba[9]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -ba[10]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -ba[11]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -ba[12]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -ba[13]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -ba[14]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -ba[15]], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, flag[i]]],0.75) for j in range(len(reduced)): if all([x in [0,1] for x in reduced[j]]): pt="".join([str(x) for x in reduced[j]]) _flag+=chr(int("0b"+pt[:8],2))+chr(int("0b"+pt[8:-1],2)) break print(_flag) ``` and the flag is **YauzaCTF{l34ky_kn4ps4k_d4mn}**. However, as only 16 words are provided, the encryption works on 16 bits and the flag could have been bruteforce two caracteres by two caracteres. # Signatures The objective of this challenge was to forge a signature. ``` from Crypto.Hash import SHA256 from Crypto.Util.number import bytes_to_long, long_to_bytes, size, getRandomNBitInteger from storage import flag def byten(x, n): return (x >> (n * 8)) & 0xFF def mask(n): return (1 << n) - 1 def rotate(x, n, s): return ((x >> (s - n)) | (x << n)) & mask(s) def scramble(x): magic = 0xC3A569C3A569C3A569C3A569C3A569C33C965A3C965A3C965A3C965A3C965A3C for i in range(32): x = rotate(x, 27, 256) ^ rotate(magic, i, 256) return x def sha2(x): hash = SHA256.new() hash.update(x) return hash.digest() def gen_pair(): private = [getRandomNBitInteger(256) for _ in range(16)] public = [long_to_bytes(y) for y in private] for i in range(16): for j in range(255): public[i] = sha2(public[i]) return private, [bytes_to_long(y) for y in public] def sign(x, key): parts = [byten(x, i) for i in range(16)] digest = [long_to_bytes(y) for y in key] for i in range(16): for j in range(parts[i]): digest[i] = sha2(digest[i]) return digest def verify(x, sign, public): parts = [255 - byten(x, i) for i in range(16)] digest = list(sign) for i in range(16): for j in range(parts[i]): digest[i] = sha2(digest[i]) if digest[i] != long_to_bytes(public[i]): return False return True def do_signature(x, private): signature = sign(scramble(x), private) return bytes_to_long(b''.join(signature)) def do_verify(x, signature, public): signature = long_to_bytes(signature, 256*16//8) signature = [signature[i*32:(i + 1)*32] for i in range(16)] return verify(scramble(x), signature, public) menu = '''\ [1] Sign message [2] Get flag [3] Quit''' if __name__ == '__main__': private, public = gen_pair() challenge = getRandomNBitInteger(256) while True: try: print(menu) opt = input('> ') if opt == '1': data = int(input('msg: ')) if size(data) > 256: raise Exception('Message is too long (256 bits max)') if data == challenge: raise Exception('Nice try') print(do_signature(data, private)) elif opt == '2': print('Enter signature for the message:') print(challenge) data = int(input('sign: ')) if size(data) > 256*16: raise Exception('Signature is too long (16 blocks, 256 bits each)') if not do_verify(challenge, data, public): raise Exception('Wrong signature') print(flag) elif opt == '3': exit(0) else: raise Exception('Unknown option') except Exception as ex: print('Error:', ex) ``` In short, 16 numbers of 256 bits are generated, and the private part is composed of the application of the sha2 function 255 times to those value. To sign x, the value is scrambled (but this is not random) and then signed. The signature is composed of the iterative hash (defined by scrambled) to the public value (but not accessible). The hash verification is done by completing the iterative hash up to the 255 iterations and compared to the private the values. However, the scramble is not random and we wan sign a unlimited number of value. Obviously, we cannot sign directly the challenge value, but we can sign the challenge+1 and challenge-255. By doing so, and debugging the scramble function, only the 12th hash need to be replace. ``` from Crypto.Util.number import bytes_to_long, long_to_bytes def byten(x, n): return (x >> (n * 8)) & 0xFF def mask(n): return (1 << n) - 1 def rotate(x, n, s): return ((x >> (s - n)) | (x << n)) & mask(s) def scramble(x): magic = 0xC3A569C3A569C3A569C3A569C3A569C33C965A3C965A3C965A3C965A3C965A3C for i in range(32): x = rotate(x, 27, 256) ^ rotate(magic, i, 256) return x x = 59182351624691910219326985342729375057882681376420056568634437032596443492739 print(x) print([byten(scramble(x), i) for i in range(16)]) print(x+1) print([byten(scramble(x+1), i) for i in range(16)]) print(x-256) print([byten(scramble(x-1*256), i) for i in range(16)]) a = long_to_bytes(465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606408045821517139432326422296790898124715803347883679032272895159791606401948168895861665579691598078624201466057484352669448377992595009347956456578381061031966996879770504071577086367576854726859566213928445636280725461334608970479085247607004316287928015349012652756358025784101700205221024513687939983444389) b = long_to_bytes(465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032961769471727195650400111929555586754060473465177109923522104142468599388859755052387968837453908619830019404790000556863073934960080603593462952028975781509803947359050823559088118106624830406830160160710195391926501622538682861989) _a=[] _b=[] for i in range(0,len(a),32): _a.append(a[i:i+32]) _b.append(b[i:i+32]) d=[] for i in range(len(_a)): d.append(_a[i]) d[12]=_b[12] print(bytes_to_long(b"".join(d))) ``` ``` python3 sig-solv.py 59182351624691910219326985342729375057882681376420056568634437032596443492739 [161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 38, 158, 158, 211] 59182351624691910219326985342729375057882681376420056568634437032596443492740 [161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 33, 158, 158, 211] 59182351624691910219326985342729375057882681376420056568634437032596443492483 [161, 210, 230, 135, 69, 64, 83, 211, 48, 58, 15, 135, 38, 159, 158, 211] 465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032437002192304770610953619957988753638573108978591540140452603895680396134899330432311679768843766457252834305627950581267665427794796212496983071957108055647096825006898338300514264627818400155841477587794514801721943731302305728933 ``` ``` [1] Sign message [2] Get flag [3] Quit > 2 Enter signature for the message: 59182351624691910219326985342729375057882681376420056568634437032596443492739 [1] Sign message [2] Get flag [3] Quit > 1 msg: 59182351624691910219326985342729375057882681376420056568634437032596443492740 465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606408045821517139432326422296790898124715803347883679032272895159791606401948168895861665579691598078624201466057484352669448377992595009347956456578381061031966996879770504071577086367576854726859566213928445636280725461334608970479085247607004316287928015349012652756358025784101700205221024513687939983444389 [1] Sign message [2] Get flag [3] Quit > 1 msg: 59182351624691910219326985342729375057882681376420056568634437032596443492483 465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032961769471727195650400111929555586754060473465177109923522104142468599388859755052387968837453908619830019404790000556863073934960080603593462952028975781509803947359050823559088118106624830406830160160710195391926501622538682861989 [1] Sign message [2] Get flag [3] Quit > 2 Enter signature for the message: 59182351624691910219326985342729375057882681376420056568634437032596443492739 sign: 465233205604637202506760326829663346832718358584342704377526676531456583213027044434313303358679698065522542773114273048506701964046590069842032892804914036261334946215446005698275285885418551161917524152550942290471666602345989814073901222387069350907034985618057927584755437210481648237090946478858228086916303333668371385935137687108213234344933259154952037606672734331878491493350560888958993008547315926649151527789192554997474378153065156698657933792958417026642831940806359993066942470166209282399119024669714542862636409673768200965733136969493298245479757490993054684277476672139834035216790640541049939542989940450026148069357586118608633605328394824097530277755063516347515082173996053134893932945295510819444024469396529677913379125296526419240413026096799784204676938728349310471183113185605860923869857886801912554908128139772976649439036567473253463692976757046987370156352410228790757374961557394419846639606348766911389921643589310021168955413927473979471344476191317336481672837546032437002192304770610953619957988753638573108978591540140452603895680396134899330432311679768843766457252834305627950581267665427794796212496983071957108055647096825006898338300514264627818400155841477587794514801721943731302305728933 YauzaCTF{Crypt0_\$1gn3rrrr} [1] Sign message [2] Get flag [3] Quit ``` **YauzaCTF{Crypt0_\$1gn3rrrr}** That's all Folks, Electro