この大会は2018/3/25 4:00(JST)~2018/3/26 4:00(JST)に開催されました。
今回もチームで参戦。結果は5200点で216チーム中11位でした。
自分で解けた問題をWriteupとして書いておきます。
IRC (Misc 50)
IRCタグから#ctf_securinetsチャネルに入る。
Welcome to CTF Securinets Channel :D Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}
Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}
Easy (Reverse Engineering 100)
$ strings easy | grep Flag Flag{This_Is_A_Hidden_Flag!!}
Flag{This_Is_A_Hidden_Flag!!}
looser (Crypto 150)
キー1文字でXORしていそう。PNGに復号することを想定して復号する。
with open('flag.png.crypt', 'rb') as f: c = f.read() key = ord(c[0]) ^ 0x89 flag = '' for i in range(len(c)): code = ord(c[i]) ^ key flag += chr(code) with open('flag.png', 'wb') as f: f.write(flag)
Flag{Hopefully_headers_are_constants}
The worst RSA Joke (Crypto 350)
公開鍵と暗号ファイルが与えられている。まず、公開鍵を見てみる。
$ openssl rsa -pubin -text < public.pem Public-Key: (2049 bit) Modulus: 01:21:3b:05:7d:6f:de:bc:45:27:b5:b7:42:1a:c1: e9:3c:cf:fe:a7:6c:4f:08:74:99:1c:f3:fa:cf:0e: ab:9e:f6:46:a2:18:39:82:0b:4d:65:3a:91:6b:68: f2:58:e9:d3:f7:c2:ba:05:4e:4a:f0:5f:3e:4d:61: b3:de:77:2d:2a:d2:33:8b:0e:ae:6e:a0:8f:20:76: e4:e4:b0:8a:b2:09:20:fa:68:85:e6:c4:4d:ec:1b: ee:28:a8:76:53:c7:4b:cb:9e:9f:12:94:de:8a:48: bd:61:46:52:a3:d6:59:df:ce:7b:89:44:61:0f:25: bf:af:93:6e:9a:54:16:7c:4d:22:7d:16:d3:2e:65: ea:45:8b:69:d6:0d:ec:d7:fa:03:4c:1b:3b:d8:62: 71:71:64:e7:78:5e:b0:6d:cc:5b:88:ba:a2:62:e4: 31:20:e5:46:65:c0:cb:cb:3e:ad:51:b0:a0:08:19: b4:e9:1d:48:72:d3:fb:e7:72:4e:03:ab:71:bc:af: 8b:b8:4c:74:de:c9:6a:ad:fc:b1:86:53:a8:f0:53: 93:d6:66:06:99:23:bc:7b:9b:31:36:3d:6d:6d:9b: 45:9f:46:db:5b:af:96:f8:40:4a:af:1a:83:1f:0d: b8:aa:d7:d9:3a:42:56:e8:15:6b:2b:70:75:7a:01: 20:93 Exponent: 65537 (0x10001) writing RSA key -----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEBITsFfW/evEUntbdCGsHp PM/+p2xPCHSZHPP6zw6rnvZGohg5ggtNZTqRa2jyWOnT98K6BU5K8F8+TWGz3nct KtIziw6ubqCPIHbk5LCKsgkg+miF5sRN7BvuKKh2U8dLy56fEpTeiki9YUZSo9ZZ 3857iURhDyW/r5NumlQWfE0ifRbTLmXqRYtp1g3s1/oDTBs72GJxcWTneF6wbcxb iLqiYuQxIOVGZcDLyz6tUbCgCBm06R1IctP753JOA6txvK+LuEx03slqrfyxhlOo 8FOT1mYGmSO8e5sxNj1tbZtFn0bbW6+W+EBKrxqDHw24qtfZOkJW6BVrK3B1egEg kwIDAQAB -----END PUBLIC KEY-----
n = 0x01213b057d6fdebc4527b5b7421ac1e93ccffea76c4f0874991cf3facf0eab9ef646a21839820b4d653a916b68f258e9d3f7c2ba054e4af05f3e4d61b3de772d2ad2338b0eae6ea08f2076e4e4b08ab20920fa6885e6c44dec1bee28a87653c74bcb9e9f1294de8a48bd614652a3d659dfce7b8944610f25bfaf936e9a54167c4d227d16d32e65ea458b69d60decd7fa034c1b3bd862717164e7785eb06dcc5b88baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6d9b459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a012093 = 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
nを素因数分解してみる。
$ python -m primefac 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611: 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
c = m^e % n ↓ c = m^e % (素数 * n)
この場合は復号結果が複数出るが、文字として読み取れるものをブルートフォースで探す。
from Crypto.PublicKey import RSA def is_prime(d): if d < 2: return False if d == 2: return True if d % 2 == 0: return False a = 3 while a ** 2 <= d: if d % a == 0: return False a = a + 2 return True def is_printable(s): for i in range(len(s)): if ord(s[i]) < 32 or ord(s[i]) > 126: return False return True with open('RSA_Worst_Joke/public.pem', 'r') as f: pub_data = f.read() pubkey = RSA.importKey(pub_data) p = pubkey.n e = pubkey.e with open('RSA_Worst_Joke/flag.enc', 'r') as f: c = int(f.read().decode('base64').encode('hex'), 16) for q in range(50): if is_prime(q): n = p * q phi = (p - 1) * (q - 1) x = 0 while True: if (phi * x + 1) % e == 0: d = (phi * x + 1) / e break x = x + 1 m = pow(c, d, n) hex_flag = '%x' % m if len(hex_flag) % 2 == 1: hex_flag = '0' + hex_flag flag = hex_flag.decode('hex') if is_printable(flag): print 'q =', q print flag
実行結果は以下の通り。
q = 47 The empire secret system has been exposed ! The top secret flag is : Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Improve the quality (Crypto 800)
decription.txtには以下のように記載されている。
Hello Every one, We didn't know what to do, so we are asking for your help. A friend of us sent us the following text: I used an elliptic curve encrytion for the first time. The only thing that i kown about elliptic curve is that a number K must always be hidden. so i made multiple encryption to send some information. Here is all the informations about the elliptic curve that i used excep the K number. The elliptic curve is : y^2 = x^3 + A*x + B A = 658974 Sorry i forget the B :/ , I just remember that it's most significant number is 6 As an order of a finite field must be a prime power, i used p = 962280654317 (FiniteField(p)). as a starter point, i used the generator G for this elliptic curve: (518459267012 : 339109212996 : 1) and each time i reuse it to encrypt again let my secret message be K . for exemple I divided my K to 2 elements k1 and k2 then Q1 is k1*G and Q2 is k2*G here are the Qi that i got: [(656055339629 : 670956206845 : 1), (714432985374 : 30697818482 : 1), (519532969453 : 833497145865 : 1), (606806384185 : 353033449641 : 1), (370553209582 : 211121736115 : 1), (95617246846 : 666814491609 : 1), (474872055371 : 795112698430 : 1), (249845085299 : 222352033875 : 1), (850954431245 : 810446463695 : 1), (188731559428 : 877002121896 : 1), (168665615402 : 464872506873 : 1), (26722558561 : 269217869309 : 1), (16403346294 : 478534963882 : 1), (539749282946 : 332444159141 : 1), (932295517649 : 23439478940 : 1), (765194933041 : 920187938377 : 1), (853124087439 : 845601917928 : 1), (246454416048 : 212483699689 : 1), (312547608490 : 688107262695 : 1), (43261158649 : 439444472742 : 1), (320785434805 : 477080449838 : 1), (741706320740 : 672809544395 : 1), (361762297756 : 858805805323 : 1), (782235980044 : 600673464737 : 1), (69196762074 : 327427680437 : 1), (876001563166 : 573218279075 : 1), (117946101727 : 954797129239 : 1), (771781111553 : 314018907599 : 1), (579549799021 : 322325160055 : 1), (857081196493 : 464260539273 : 1), (852938568103 : 429083796488 : 1), (850954431245 : 810446463695 : 1), (55203632714 : 255470537391 : 1), (600464434215 : 605840305721 : 1), (620532163623 : 575613893944 : 1), (215810002861 : 481354983411 : 1), (538481263994 : 666638294130 : 1), (528666082457 : 895034116069 : 1), (296218553972 : 899557390183 : 1), (428618251485 : 445768511836 : 1), (632412058600 : 685699421425 : 1), (634041855232 : 495546745721 : 1), (570481762204 : 252944477333 : 1), (760959783781 : 435626456209 : 1)]
y^2 = x^3 + a*x + b mod n →b = y^2 - x^3 - a*x mod n
この場合は以下の文字になるので、まずはBを求める。
a -> A b -> B n -> p
p = 962280654317 A = 658974 G = (518459267012, 339109212996) x = G[0] y = G[1] B = (pow(y, 2) - pow(x, 3) - A * x) % p print 'B =', B
B = 618
Bの値はわかったので、Pohlig–Hellman algorithmを使って、k1から順番に求める。その値を見ながらメッセージになるようASCIIコード(10進数)として2桁ずつ読み込む。
コードは以下の通り。
# solve.sage p = 962280654317 A = 658974 B = 618 G = (518459267012, 339109212996) Q = [(656055339629, 670956206845), (714432985374, 30697818482), (519532969453, 833497145865), (606806384185, 353033449641), (370553209582, 211121736115), (95617246846, 666814491609), (474872055371, 795112698430), (249845085299, 222352033875), (850954431245, 810446463695), (188731559428, 877002121896), (168665615402, 464872506873), (26722558561, 269217869309), (16403346294, 478534963882), (539749282946, 332444159141), (932295517649, 23439478940), (765194933041, 920187938377), (853124087439, 845601917928), (246454416048, 212483699689), (312547608490, 688107262695), (43261158649, 439444472742), (320785434805, 477080449838), (741706320740, 672809544395), (361762297756, 858805805323), (782235980044, 600673464737), (69196762074, 327427680437), (876001563166, 573218279075), (117946101727, 954797129239), (771781111553, 314018907599), (579549799021, 322325160055), (857081196493, 464260539273), (852938568103, 429083796488), (850954431245, 810446463695), (55203632714, 255470537391), (600464434215, 605840305721), (620532163623, 575613893944), (215810002861, 481354983411), (538481263994, 666638294130), (528666082457, 895034116069), (296218553972, 899557390183), (428618251485, 445768511836), (632412058600, 685699421425), (634041855232, 495546745721), (570481762204, 252944477333), (760959783781, 435626456209)] F = FiniteField(p) E = EllipticCurve(F, [A,B]) G = E.point(G) factors, exponents = zip(*factor(E.order())) primes = [factors[i] ^ exponents[i] for i in range(len(factors))] str_num = '' for i in range(len(Q)): dlogs = [] for fac in primes: t = int(G.order()) / int(fac) dlog = discrete_log(t*E.point(Q[i]), t*G, operation='+') dlogs += [dlog] k = crt(dlogs, primes) print k #print k * G == E.point(Q[i]) str_num += str(k) msg = '' for i in range(0, len(str_num), 2): msg += chr(int(str_num[i:i+2])) print msg
実行結果は以下の通り。
CONVERT THIS TO LOWER CASE FIRST : THIS IMAGE CONTAINS THE FLAG, TRY TO GET IT THE SUBMITTED FLAG MUST BE IN THIS FORMAT: FLAG-EC[WHAT YOU'LL FIND IN THE IMAGE] IMAGE URL: HTTP://CRYPTO.CTFSECURINETS.COM/1/STEG-PART.PNG
上記で大文字、小文字が関係するところは小文字にする。
http://crypto.ctfsecurinets.com/1/steg-part.pngのファイルを見たら、フラグが書いてあった。
flag-ec[EC_St!e-g1(a)no]