ASIS CTF 2019 write-up
チームm1z0r3として参加しました、warm-up問題2問しか解けず、大した貢献はできなかった。
解けた問題
A delicious soup[Crypto,44pts]
最初に取り込んだ問題、他の問題proof of workがついていて、逃げ腰でこの問題に切り替えました。まずは問題文↓
# flag.enc
11d.3ilVk_d3CpIO_4nlS.ncnz3e_0S}M_kn5scpm345n3nSe_u_S{iy__4EYLP_aAAall
# simple_and_delicious.py #!/usr/bin/env python #-*- coding:utf-8 -*- import random from flag import flag def encrypt(msg, perm): W = len(perm) while len(msg) % (2*W): msg += "." msg = msg[1:] + msg[:1] msg = msg[0::2] + msg[1::2] msg = msg[1:] + msg[:1] res = "" for j in xrange(0, len(msg), W): for k in xrange(W): res += msg[j:j+W][perm[k]] msg = res return msg def encord(msg, perm, l): for _ in xrange(l): msg = encrypt(msg, perm) return msg W, l = 7, random.randint(0, 1337) perm = range(W) random.shuffle(perm) *** enc = encord(flag, perm, l) f = open('flag.enc', 'w') f.write(enc) f.close()
パッと見線形に見えたが、よくよく見るとflagの文字列の配列をゴニョゴニョシャッフルしただけ。
具体的にどういうシャッフルなのかというと:
1. 最初の1文字を後ろに入れる
ASIS{8A4Qwl4K6p95N8Rqr5lneSzz6dUxzfgTwbFbV10zvY7T3qmYhRAkQj9gXlzpxK}..
↓
SIS{8A4Qwl4K6p95N8Rqr5lneSzz6dUxzfgTwbFbV10zvY7T3qmYhRAkQj9gXlzpxK}..A
2. 次にindexは偶数の文字を集め前半部分に入れる、後ろに奇数の集まりを入れる
SS84w469NRrlez6UzgwFV0v73mhAQ9Xzx}.I{AQlKp58q5nSzdxfTbb1zYTqYRkjglpK.A
3. もう一度1.の手順をやる
S84w469NRrlez6UzgwFV0v73mhAQ9Xzx}.I{AQlKp58q5nSzdxfTbb1zYTqYRkjglpK.SA
4. 文字列を７文字を一括りにして、あらかじめ決めたシャッフルルールpermにしたがって変換
例:
[S,8,4,w,4,6,9]
↓
[2,1,3,5,6,4,0]
↓
[4,8,w,6,9,4,S]……
5. 手順1-4の繰り返しをrandom(0,1337)回をやる
幸いもうちょっと暗号文を見てみると、flagの形式ASIS{...}の中I,{,}は1回ずつしか出現しなかったので、この３つをマークとして利用出来そう。
さらにシャッフルルールの長さは7かつ繰り返し回数もたかが1337程度。ここでブルートフォースの回数を軽く見積もると
$$
7! * 1337 =6738480
$$
7桁はまだいける範囲内ことがわかり、とりあえずpermの順列に沿って毎回1337まで回して、シャッフルされたI{}３つのindexを暗号文と照合して、一致したら復号したらいいの話です。
import itertools import random import sys def encrypt(msg, perm): W = len(perm) while len(msg) % (2*W): msg += "." msg = msg[1:] + msg[:1] msg = msg[0::2] + msg[1::2] msg = msg[1:] + msg[:1] res = "" for j in xrange(0, len(msg), W): for k in xrange(W): res += msg[j:j+W][perm[k]] msg = res return msg def encord(msg, perm, l): for i in xrange(l): msg = encrypt(msg, perm) if msg.index('I') == 14 and msg.index('{')==53 and msg.index('}')==31: print perm,str(i) print decord(open('flag.enc','r').read(),perm,i+1) return msg def decord(msg, perm, l): for _ in xrange(l): msg = decrypt(msg, perm) return msg def decrypt(msg,perm): W = 7 res = "" for j in xrange(0,len(msg), W): k = ['a','b','c','d','e','f','g'] for i in xrange(W): k[perm[i]] = msg[j:j+W][i] res += ''.join(k) r = ['a' for _ in range(70)] p = [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 0, 1] for z in range(70): r[p[z]] = res[z] return ''.join(r) #W, l = 7, random.randint(0, 1337) W = 7 perm = range(W) #random.shuffle(perm) f = open('flag.enc', 'r') msg = f.read() #flag = exploit(msg,perm) fff = 'ASIS{'+'8A4Qwl4K6p95N8Rqr5lneSzz6dUxzfgTwbFbV10zvY7T3qmYhRAkQj9gXlzpxK'+'}' mid = encord(fff,[2,1,3,5,6,4,0],555) print decord(mid,[2,1,3,5,6,4,0],555) for a in itertools.permutations(perm): flag = 'ASIS{'+'8A4Qwl4K6p95N8Rqr5lneSzz6dUxzfgTwbFbV10zvY7T3qmYhRAkQj9gXlzpxK'+'}' ff = encord(flag,list(a),1337) #print flag
flag collision[Coding,67pts]
指定のアドレスまでnetcatしたら、ASISお馴染みのPoWが現れた、しかも毎回hash関数が変わる。
とりあえずhash関数の種類をまとめました。
md5 sha1 sha224 sha256 sha384 sha512
まぁ向こうの言う通りに回せばなんとかなる。(ここではpwntoolの方が良い、最後interactiveに切り替えてさらに調査できる)
PoWを突破した後急に「CRCの衝突をやれ」と言われ、早速ググりました。色々実装方法を実装してもうまくいけなくて、ダメ元にブルートフォースをやったら秒で結果が出ました...(時間の無駄でした)
毎回random文字数の衝突を１０?回ぐらいやればflagが降ってきました。
from pwn import * from zlib import crc32 from m1z0r3 import * from hashlib import md5,sha1,sha224,sha256,sha384,sha512 from Crypto.Util.number import long_to_bytes import random, string def randomname(n): randlst = [random.choice(string.ascii_letters + string.digits) for i in range(n)] return ''.join(randlst) def exploit(dic): #io = remote('37.139.9.232','19199') ip = '37.139.9.232' port = 19199 s,f = sock(ip,port) hash_list = [md5,sha1,sha224,sha256,sha384,sha512] m = recv_line(f) print m last6 = m[-7:-1] print last6 h = '' def PoW(idx,last): print '[+] start pow' x = 1 while True: bx = b64e(long_to_bytes(x)) hexx = hash_list[idx](bx).hexdigest()[-6:] if hexx == last: print '[+] bingo' return bx x += 1 if 'md5' in m: ans = PoW(0,last6) s.send(ans+'\n') elif 'sha1' in m: ans = PoW(1,last6) s.send(ans+'\n') elif 'sha224' in m: ans = PoW(2,last6) s.send(ans+'\n') elif 'sha256' in m: ans = PoW(3,last6) s.send(ans+'\n') elif 'sha384' in m: ans = PoW(4,last6) s.send(ans+'\n') else: ans = PoW(5,last6) s.send(ans+'\n') for _ in range(4): print recv_line(f) while True: m = '' while True: m = recv_line(f) print m if m.endswith('CRC32:|\n'): break elif 'ASIS{' in m: print m print m idx1 = m.index('=') idx2 = m.index(' and') ll = eval(m[idx1+1:idx2]) if dic.has_key(str(ll)): a = dic[str(ll)][0] b = dic[str(ll)][1] print a,b s.send('({},{})'.format(a,b)+'\n') else: r = dict() while True: x = 'ASIS{%s}' % randomname(ll-6) c = str(crc32(x)) if r.has_key(c): print 'bingo' print [r[c],x] dic[str(ll)] = [r[c],x] break else: r[c] = x a = dic[str(ll)][0] b = dic[str(ll)][1] print a,b s.send('({},{})'.format(a,b)+'\n') def main(): dic = { '15':["ASIS{wpQ78d6lk}","ASIS{4LEVv9no8}"], '16':['ASIS{XJKqgpXG3h}','ASIS{2vIy7kh3I1}'], '17': ['ASIS{N3oUn2fNYDe}', 'ASIS{cEqP0TLR0ep}'], '18': ['ASIS{Yvc6vEOVKcqg}', 'ASIS{jqgNv5MplomO}'], '19': ['ASIS{HBGExWcsHkjIJ}', 'ASIS{001ZSSGoPajSa}'], '20': ['ASIS{vIOUyVByrhVNiu}', 'ASIS{v5otW7kNsZ2gdG}'], '21': ['ASIS{0I0cdxHShRxhNfh}', 'ASIS{ctvedzhS29uwdJj}'], '22': ['ASIS{uzC5dEMHRQt4VFNg}', 'ASIS{ATEJH1PDf4d19l4A}'], '23': ['ASIS{2URJbCqOry560DLB3}', 'ASIS{lDR7VMpKSNQ8I6SLf}'], '24': ['ASIS{yO2n6qyDdfPba8sB0a}', 'ASIS{3BC6wb9SnJ0B6F2KWC}'], '25': ['ASIS{tqRfvUiKKpouaEixLND}', 'ASIS{FhaNaHZvWzkG4guZgog}'], '26': ['ASIS{mujJoqinfBNiMuE5xCjX}', 'ASIS{PDAQbu8qsWFsjyq5qjDG}'], '27': ['ASIS{CFOsCBguwBrrjhj4dNbXt}', 'ASIS{wcaEpHuL34P9PhMx4EeVb}'], '28': ['ASIS{Y1tZFZ4y08jjF0VV2vVD67}', 'ASIS{vK2T2EzNaL489acYZjkvHg}'], '29': ['ASIS{XiCWA7vZnDsi8hGQMybac0G}', 'ASIS{F08rynuBCChtJcfF0lk2t7y}'] } while True: print dic if exploit(dic) == 0: continue if __name__ == '__main__': main()
他の問題
気が向いたら...
swamp ctf 2019 write-up
チームm1z0r3として参加しました。
解けた問題
We Three Keys [Crypto 144pts]
In this modern world of cyber, keys are the new kings of the world. In fact, we will let you use the 3 best keys that I could find, make sure to see what they offer to you!
nc chal1.swampctf.com 1441
#!/usr/bin/env python2
from Crypto.Cipher import AES
# from keys import key1, key2, key3
def pkcs7_pad(msg):
val = 16 - (len(msg) % 16)
if val == 0:
val = 16
pad_data = msg + (chr(val) * val)
return pad_data
def encrypt_message(ptxt,key, IV):
print("What message woud you like to encrypt (in hex)?")
# ptxt = raw_input("<= ")
ptxt = pkcs7_pad(ptxt.decode('hex'))
print ptxt.encode('hex')
print len(ptxt)
cipher = AES.new(key, AES.MODE_CBC, IV)
ctxt = cipher.encrypt(ptxt)
print ctxt.encode('hex')
print len(ctxt)
def decrypt_message(key, IV):
print("What message would you like to decrypt (in hex)?")
ctxt = raw_input("<= ")
ctxt = ctxt.decode('hex')
if (len(ctxt) % 16) != 0:
print "What a fake message, I see through your lies"
return
cipher = AES.new(key, AES.MODE_CBC, IV)
ptxt = cipher.decrypt(ctxt)
print ptxt.encode('hex')
def new_key():
print("Which key would you like to use now? All 3 are great")
key_opt = str(raw_input("<= "))
if key_opt == "1":
key = key1
elif key_opt == "2":
key = key2
elif key_opt == "3":
key = key3
else:
print("Still no, pick a real key plz")
exit()
return key
def main():
print("Hello! We present you with the future kings, we three keys!")
print("Pick your key, and pick wisely!")
key_opt = str(raw_input("<= "))
if key_opt == "1":
key = key1
elif key_opt == "2":
key = key2
elif key_opt == "3":
key = key3
else:
print("Come on, I said we have 3!")
exit()
while True:
print("1) Encrypt a message")
print("2) Decrypt a message")
print("3) Choose a new key")
print("4) Exit")
choice = str(raw_input("<= "))
if choice == "1":
encrypt_message(key, key)
elif choice == "2":
decrypt_message(key, key)
elif choice == "3":
key = new_key()
else:
exit()
if __name__=='__main__':
main()
pkcs7があったため、一瞬padding oracleだと思い込んだ。
でも実際知りたいのは平文ではなく、あくまでkeyだけなので、
padding oracleではないと気付いた。
一通り見終わってから得た情報は↓:
- AES問題
- 暗号化や復号化も全部自分でやれる
- ただただ平文を暗号/復号する
- keyは合計3つ
- IVのところはkeyになってる
crypto.stackexchange で答えを探したら↓にヒットした
crypto.stackexchange.com
どういうものかというと
$$
C_0 = E_K(IV\oplus P_0); \\
C_1 = E_K(C_0\oplus P_1); \\
C_2 = E_K(C_1\oplus P_2); \\
$$
本来の暗号化された暗号文は↑の感じ
ct1とct2のところ00...00とct0に替える
$$
\dot{C_0} = C_0;\\
\dot{C_1} = (0...0);\\
\dot{C_2} = C_0;\\
$$
そうすると復号化された平文は↓のようになります:
$$
P_0 = IV\oplus D_K(\dot{C_0});\\
P_1 = \dot{C_0}\oplus D_K(0);\\
P_2 = 0\oplus D_K(\dot{C_0});\\
$$
最後新しいpt0とpt2をxorを取ればkeyは出てくる。
$$ P_0\oplus P_2 = IV\oplus D_K(\dot{C_0})\oplus D_K(\dot{C_0})\\ = IV = K $$
↓はsolver
from m1z0r3 import *
from Crypto.Util.number import long_to_bytes,bytes_to_long
ip = "chal1.swampctf.com"
port = 1441
flag = ''
for i in range(1,4):
s,f = sock(ip,port)
print recv_until(f,'<= ') # choose key
s.send('{}\n'.format(i)) # send i to choose i
print recv_until(f,'<= ') # choose cmd
s.send('1\n') # send 1 to choose enc
print recv_until(f,'<= ') # ready to input
ptext = hex(bytes_to_long('a'*32))[2:-1].zfill(64)
s.send(ptext+'\n') # send ptext
ctext1 = recv_line(f).strip() # get ciphertext
ctext1_0 = ctext1[:32]
print recv_until(f,'<= ') # choose cmd
s.send('2\n') # send 2 to dec
print recv_until(f,'<= ') # ready to input
ct = ctext1_0 + '00'*16 + ctext1_0
s.send(ct+'\n') # send to dec
pt1 = recv_line(f).strip().decode('hex') # get pt
print pt1
pt1_0 = pt1[:16]
pt1_2 = pt1[32:]
print xor(pt1_0,pt1_2)
flag += xor(pt1_0,pt1_2)
print flag
We Three Keys flag{w0w_wh4t_l4zy_k3yz_much_w34k_crypt0_f41ls!}
Ghidra Release [Misc 310pts]
https://static.swampctf.com/ghidra_nsa_training.mp4
Ghidraに関する約15hのチュートリアルビデオがひたすら流されています。
多分SECCONのホテル問題と似たような感じだと推測して、
どこかで表示されるだと思うので、とりあえずffmpegで静止画に変換します。
ffmpeg -i ghidra_nsa_training.mp4 -vf fps=1/5 ghidra/img%08d.jpg
チュートリアルビデオと言ってもほとんど文字だけなので、
OCRに読んでもらうのが最初思いついたこと。
実装↓:
from PIL import Image
import sys
import pyocr
import pyocr.builders
tools = pyocr.get_available_tools()
if len(tools) == 0:
print("No OCR tool found")
sys.exit(1)
# The tools are returned in the recommended order of usage
tool = tools[0]
print("Will use tool '%s'" % (tool.get_name()))
# Ex: Will use tool 'libtesseract'
langs = tool.get_available_languages()
print("Available languages: %s" % ", ".join(langs))
lang = langs[0]
print("Will use lang '%s'" % (lang))
# Ex: Will use lang 'fra'
# Note that languages are NOT sorted in any way. Please refer
# to the system locale settings for the default language
# to use.
for i in range(1,11151):
#import sys
#sys.stdout.write("\033[2K\033[G%s" % str(i))
#sys.stdout.flush()
if i % 1000 == 0:
print(i)
txt = tool.image_to_string(
Image.open('ghidra/img{}.jpg'.format(str(i).zfill(8))),
lang=lang,
builder=pyocr.builders.TextBuilder()
)
# txt is a Python string
if 'FLAG(' in txt :
print(txt)
print(i)
もともとflag{を基づいて探していましたが、
最初にヒットした画像のところにフラグが四つに分かれていることが判明して、
検索ワードをFLAG(に切り替えました。
OCRが結構遅いので、回している間目grepでやってみたら、
スクリプトより早くフラグを取れました。(スクリプトもちゃんと答えを出せる)
Ghidra Release flag{l34kfr33_n4tion4l_s3cur1ty}
volga ctf 2019 write-up
チームm1z0r3として参加しました。
解けた問題
Blind [Crypto 200pts]
自分は暗号の一問だけ解けました。
Pull the flag...if you can.
nc blind.q.2019.volgactf.ru 7070
server.py
#!/usr/bin/env python
from __future__ import print_function
import os
import sys
import shlex
import subprocess
from private_key import d
"""
Utils
"""
def run_cmd(cmd):
try:
args = shlex.split(cmd)
return subprocess.check_output(args)
except Exception as ex:
return str(ex)
"""
Signature
"""
class RSA:
def __init__(self, e, d, n):
self.e = e
self.d = d
self.n = n
def sign(self, message):
message = int(message.encode('hex'), 16)
return pow(message, self.d, self.n)
def verify(self, message, signature):
message = int(message.encode('hex'), 16)
verify = pow(signature, self.e, self.n)
return message == verify
"""
Keys
"""
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
e = 65537
"""
Communication utils
"""
def read_message():
return sys.stdin.readline()
def send_message(message):
sys.stdout.write('{0}\r\n'.format(message))
sys.stdout.flush()
def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)
"""
Main
"""
def check_cmd_signatures(signature):
cmd1 = 'exit'
cmd2 = 'leave'
assert (signature.verify(cmd1, signature.sign(cmd1)))
assert (signature.verify(cmd2, signature.sign(cmd2)))
class SignatureException(Exception):
pass
if __name__ == '__main__':
signature = RSA(e, d, n)
check_cmd_signatures(signature)
try:
while True:
send_message('Enter your command:')
message = read_message().strip()
(sgn, cmd_exp) = message.split(' ', 1)
eprint('Accepting command {0}'.format(cmd_exp))
eprint('Accepting command signature: {0}'.format(sgn))
cmd_l = shlex.split(cmd_exp)
cmd = cmd_l[0]
if cmd == 'ls' or cmd == 'dir':
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
elif cmd == 'cd':
try:
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
os.chdir(cmd_l[1])
send_message('')
except Exception as ex:
send_message(str(ex))
elif cmd == 'cat':
try:
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
if len(cmd_l) == 1:
raise Exception('Nothing to cat')
ret_str = run_cmd(cmd_exp)
send_message(ret_str)
except Exception as ex:
send_message(str(ex))
elif cmd == 'sign':
try:
send_message('Enter your command to sign:')
message = read_message().strip()
message = message.decode('base64')
cmd_l = shlex.split(message)
sign_cmd = cmd_l[0]
if sign_cmd not in ['cat', 'cd']:
sgn = signature.sign(sign_cmd)
send_message(str(sgn))
else:
send_message('Invalid command')
except Exception as ex:
send_message(str(ex))
elif cmd == 'exit' or cmd == 'leave':
sgn = int(sgn)
if not signature.verify(cmd_exp, sgn):
raise SignatureException('Signature verification check failed')
break
else:
send_message('Unknown command {0}'.format(cmd))
break
except SignatureException as ex:
send_message(str(ex))
eprint(str(ex))
except Exception as ex:
send_message('Something must have gone very, very wrong...')
eprint(str(ex))
finally:
pass
ぱっと見ちょっとpwn問にも見えなくはない。
一通り見終わってから得た情報は↓:
- RSA問題
- シグネチャーとcmdを一緒にサーバーに送る
- 最終目標サーバーにあるflagを読み出せる
- n,eは既知(nは617桁factordbにいない)
- serverスクリプトはRSAというobjectがあり,sign関数はcat,cd以外のcmdを秘密鍵dを使って暗号化します,verifyはその逆
とにかくcat flagが安易に実行してくれなさそう
ほかのメンバーとのやり取りで「cat flagを分解し、serverにsignしてもらえる」という方法をひらめき、その方針に沿って二人平行に実装してみました。
まずsagecellにlong型のcat flagを投げてまた。
factor(bytes_to_long('cat flag'))
>> [103,408479,170205956447]
とりあえず103,408479*170205956447に分けてやってみたけどいけず、用事で先に自分の実装を共有して離脱(103*408479,170205956447だとクォーテーションに変換されるから無理)
最後は別のメンバーが解いてくれました。
↓はsolver
from m1z0r3 import *
from Crypto.Util.number import long_to_bytes,bytes_to_long
from base64 import b64encode,b64decode
import shlex
ip = "blind.q.2019.volgactf.ru"
port = 7070
s,f = sock(ip,port)
e = 65537
n = 26507591511689883990023896389022361811173033984051016489514421457013639621509962613332324662222154683066173937658495362448733162728817642341239457485221865493926211958117034923747221236176204216845182311004742474549095130306550623190917480615151093941494688906907516349433681015204941620716162038586590895058816430264415335805881575305773073358135217732591500750773744464142282514963376379623449776844046465746330691788777566563856886778143019387464133144867446731438967247646981498812182658347753229511846953659235528803754112114516623201792727787856347729085966824435377279429992530935232902223909659507613583396967
sign = [408479,103*170205956447]
sign = [b64encode(long_to_bytes(i)) for i in sign]
welcome_txt = 'Enter your command:\n'
print recv_line(f)
c_sign = '0 sign'
s.send(c_sign+'\n')
print recv_line(f)
s.send(sign[0]+'\n')
s1 = int(recv_line(f).strip())
print recv_line(f) # Enter your command:
s.send(c_sign+'\n')
print recv_line(f) # Enter your command to sign:
s.send(sign[1]+'\n')
s2 = int(recv_line(f).strip())
print recv_line(f) # Enter your command to sign:
sign = s1 * s2
print long_to_bytes(pow(sign,e,n))
c = str(sign) + ' ' + 'cat flag'+'\n'
s.send(c)
while True:
print recv_line(f)
所感としてはもうちょっといろいろ早く気づけばよかったな...あと何でsignを復元のところmodnをとらなくて済むだろう、知ってる方があったら教えてください。
自分が解けなかった問題(後で書く)
Shifter [Crypto 150pts]
大の苦手のLSFR
Show Cat [Crypto 100pts]
苦手のpassword crack
Confidence ctf 2019 write-up
p4 team手かけた(?)CTFをチームm1z0r3として参加しました。
自分は暗号の二問を解いた。
競技中解いた問題
Count me in! (crypro 59pts)
ある意味の総当たり
まずは問題文
import multiprocessing
from Crypto.Cipher import AES
# from secret import key, flag
key = "0"*16
counter = 0
aes = AES.new(key, AES.MODE_ECB)
def chunk(input_data, size):
return [input_data[i:i + size] for i in range(0, len(input_data), size)]
def xor(*t):
from functools import reduce
from operator import xor
return [reduce(xor, x, 0) for x in zip(*t)]
def xor_string(t1, t2):
t1 = map(ord, t1)
t2 = map(ord, t2)
return "".join(map(chr, xor(t1, t2)))
def pad(data):
pad_byte = 16 - len(data) % 16
return data + (chr(pad_byte) * pad_byte)
def worker_function(block):
global counter
print "start worker {} ".format(counter)
key_stream = aes.encrypt(pad(str(counter)))
result = xor_string(block, key_stream)
counter += 1
print "end worker {}".format(counter-1)
print result.encode("hex")
return counter-1
def distribute_work(worker, data_list, processes=8):
pool = multiprocessing.Pool(processes=processes)
result = pool.map(worker, data_list)
pool.close()
return result
def encrypt_parallel(plaintext, workers_number):
print 'start parallel'
chunks = chunk(pad(plaintext), 16)
results = distribute_work(worker_function, chunks, workers_number)
return results
# def main():
plaintext = """The Song of the Count
You know that I am called the Count
Because I really love to count
I could sit and count all day
Sometimes I get carried away
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4,
1-2, i love couning whatever the ammount haha!
1-2-3-4, heyyayayay heyayayay that's the sound of the count
I count the spiders on the wall...
I count the cobwebs in the hall...
I count the candles on the shelf...
When I'm alone, I count myself!
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4, 1,
2 I love counting whatever the
ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4
That's the song of the Count!
"""
# encrypted = encrypt_parallel(plaintext, 32)
# print(encrypted.encode("hex"))
if __name__ == '__main__':
multiprocessing.freeze_support()
main()
出力は↓
9d5c66e65fae92af9c8a55d9d3bf640e8a5b76a878cbf691d3901392c9b8760ebd5c62b22c88dca9d1c55098cbbb644ae9406ba32c8293bdd29139bbc2b4605bba51238f2cb399a9d0894ad9cbb8774be9406ce66fae89a6c8ef7ad9c4b87442ad1470af78e19da6d8c55096d2b9750ea8586fe668a085c2ef8a5e9cd3be6c4bba144ae66ba488e8df84418bceb2650ea84362bf0688dcabd3905d8d87a46d414626be04a58215b84263a620de3203fa4626be08e2940da35c61b82c98201ce15438cd67eb921cf77c28a969de321bf4433ea24ca59216a25b7bb662996106e11639e75ae09015bb4c2fb76d8c254fe15e6ab45cea817391547cab698c6d4ff35039b34df7df599e412fb67fde3200b55432a441f19817b01405962c9d2e1af9556aa447f09f0df75360ad6988241db91129a85deb8559a25b7bb660de084ff1cc3a0e8041bc71d71fb29883931d9d3e8f784ca743b065c91ea386909e1a9100925f4fa742b1718c1efec4d4d609df5bcb3b17e417bd268d5fe6ced4d65b9c40d6305eeb1df03e9050e68bcad241dd15b46453b85dae7cd112b2c3c7ca50dd4ddf2c1ff350f5349c5febcadbd2509c40d6340aad03bd258d5bb2d8cdc647d814d1335efe18f8718651e7c5d6b9609c57d12010fe50e939801ee1dbcbd74cce4739c1eeceba8ef87360b629ed82a6eb9d508ee381bb88e97363bf20a1cfe7a7e07cccf3cea788bd277fb265e9cde4a9b937808aa7ee85f22679a365f5c4ede5f478c0e482ab95bd3c79f731e9c9a8b6ff7cc2e6c0e0c897047fb22ba1e5afa8b778c2ef80abcabd1a37b42af4c2fce5fa60dde582a8c7971a37b42af4c2fce5e475c1f782b7cabd207bb832edd5a4e5e4130a976ad4a2fe86ac99c18491f9f6c86adae59cc4a9f33072f70ca6daede5e40b049272c8e6b980b798c69e9fb7f7891611c7758df0fc82b481d1ca9eb8e2cd5f118f26def6f693d2abc99982bce2855f038175d9e7ebcdf8a4dcca9faab0da1045857eceebed8ab68a89e0bff9f3c60a098426ceedec8daccdce8584bce6cc0d49c065c2f7f797f898c69e9fb5b0e05f019269dd88a8c2f8df89cac5f8b09d00ad16dc760ead7c3518baed47603c5b5251cc269cae93d1f8a4888699aff58942c8529f304af0362143f2bd1e37670d538753992129ff3c6c5befb21e7331590c950ac26917be39644dfba50b2b70117fcbccba57b209ae95721a1c9d36073d934b75014109102be14fb6a044a7cf9e468748976457f6342177f5a9042630622f97d2ba5a8c04a7890d4e5fcb445b7600d7c1be71b711b6b32b4444f078557ef82e4f0559225437b455aa9a0bbaff89c834531a45115125c933d6cd6cdca8f8
問題文を眺めてみたら、multiprocessの一個のprocessが終わった度にcounterが1を増やすというシステムでした。よって、keystreamが被る可能性があります。ですから前のkeystreamを使って最後の暗号文とxor取ればflagが降ってくる.
from count import *
ct = "9d5c66e65fae92af9c8a55d9d3bf640e8a5b76a878cbf691d3901392c9b8760ebd5c62b22c88dca9d1c55098cbbb644ae9406ba32c8293bdd29139bbc2b4605bba51238f2cb399a9d0894ad9cbb8774be9406ce66fae89a6c8ef7ad9c4b87442ad1470af78e19da6d8c55096d2b9750ea8586fe668a085c2ef8a5e9cd3be6c4bba144ae66ba488e8df84418bceb2650ea84362bf0688dcabd3905d8d87a46d414626be04a58215b84263a620de3203fa4626be08e2940da35c61b82c98201ce15438cd67eb921cf77c28a969de321bf4433ea24ca59216a25b7bb662996106e11639e75ae09015bb4c2fb76d8c254fe15e6ab45cea817391547cab698c6d4ff35039b34df7df599e412fb67fde3200b55432a441f19817b01405962c9d2e1af9556aa447f09f0df75360ad6988241db91129a85deb8559a25b7bb660de084ff1cc3a0e8041bc71d71fb29883931d9d3e8f784ca743b065c91ea386909e1a9100925f4fa742b1718c1efec4d4d609df5bcb3b17e417bd268d5fe6ced4d65b9c40d6305eeb1df03e9050e68bcad241dd15b46453b85dae7cd112b2c3c7ca50dd4ddf2c1ff350f5349c5febcadbd2509c40d6340aad03bd258d5bb2d8cdc647d814d1335efe18f8718651e7c5d6b9609c57d12010fe50e939801ee1dbcbd74cce4739c1eeceba8ef87360b629ed82a6eb9d508ee381bb88e97363bf20a1cfe7a7e07cccf3cea788bd277fb265e9cde4a9b937808aa7ee85f22679a365f5c4ede5f478c0e482ab95bd3c79f731e9c9a8b6ff7cc2e6c0e0c897047fb22ba1e5afa8b778c2ef80abcabd1a37b42af4c2fce5fa60dde582a8c7971a37b42af4c2fce5e475c1f782b7cabd207bb832edd5a4e5e4130a976ad4a2fe86ac99c18491f9f6c86adae59cc4a9f33072f70ca6daede5e40b049272c8e6b980b798c69e9fb7f7891611c7758df0fc82b481d1ca9eb8e2cd5f118f26def6f693d2abc99982bce2855f038175d9e7ebcdf8a4dcca9faab0da1045857eceebed8ab68a89e0bff9f3c60a098426ceedec8daccdce8584bce6cc0d49c065c2f7f797f898c69e9fb5b0e05f019269dd88a8c2f8df89cac5f8b09d00ad16dc760ead7c3518baed47603c5b5251cc269cae93d1f8a4888699aff58942c8529f304af0362143f2bd1e37670d538753992129ff3c6c5befb21e7331590c950ac26917be39644dfba50b2b70117fcbccba57b209ae95721a1c9d36073d934b75014109102be14fb6a044a7cf9e468748976457f6342177f5a9042630622f97d2ba5a8c04a7890d4e5fcb445b7600d7c1be71b711b6b32b4444f078557ef82e4f0559225437b455aa9a0bbaff89c834531a45115125c933d6cd6cdca8f8"
cct = chunk(ct.decode('hex'),16)
plaintext = plaintext + 'flag'*16
ppt = chunk(plaintext,16)
for c in range(57,61):
print '-'*64
for k in range(57):
ks = xor_string(cct[k],ppt[k])
print xor_string(cct[c],ks)
Bro,do you even lift (crypro 85pts)
モニック多項式からflagを計算する まず問題文から
#lift.sage
flag = int(open('flag.txt','r').read().encode("hex"),16)
ranges = int(log(flag,2))
p = next_prime(ZZ.random_element(2^15, 2^16))
k = 100
N = p^k
d = 5
P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
pol = 0
for c in range(d):
pol += ZZ.random_element(2^ranges, 2^(ranges+1))*x^c
print(pol)
remainder = pol(flag)
print(remainder)
pol = pol - remainder
print(pol(flag))
assert pol(flag) == 0
print(p)
print(pol)
# out.txt 35671 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
最初はよくわからなかった。
問題文はsageファイルだからまずその線で調べてみても何もわからなかった。
後半ちょっとRSAに対するcoppersmith攻撃を見てみたところモニック多項式ということを気付いた。
モニック多項式の一般形は:
今回のout.txtをみると
というあと一歩のところの感じがします。
ですのでc4の逆数をかけてまず一般形に変換してsage特有のsmall_rootsという関数を使って答えを求める。
あと気を付けるものとしては解xの上限を設定しなくては行けないらしいので。問題文から以下のような式で解の上限を計算しましたint(log(c0,2))+1=223
# solver.py
#flag = int(open('flag.txt','r').read().encode("hex"),16)
flag = int('p4{fffffffffffffffffffffff}'.encode("hex"),16)
ranges = int(log(flag,2))
p = 35671
k = 100
N = p^k
d = 5
P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
pol = 12172655049735206766902704703038559858384636896299329359049381021748*x^4 + 11349632906292428218038992315252727065628405382223597973250830870345*x^3 + 9188725924715231519926481580171897766710554662167067944757835186451*x^2 + 8640134917502441100824547249422817926745071806483482930174015978801*x + 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
# a0 = 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728
c0 = 12172655049735206766902704703038559858384636896299329359049381021748
d = inverse_mod(c0,N)
pol = pol * d
print(pol.is_monic())
# pol = pol - N
print(pol)
print(len(str(N^(1/4))))
xx = 2**223 # xxは解の上限int(log(c0,2))+1=223
print(pol.small_roots(xx))
# print(p)
# print(pol)
# flag p4{Th4t5_50m3_h34vy_l1ft1n9}
TAMUCTF 2019 write-up
チームm1z0r3として参加しました。
自分が手かけた問題のwrite-upを書きます
競技中解いた問題
[Crypro 354pts] RSAaay
(2531257, 43) My super secret message: 906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268
solver↓↓
n,e = (2531257, 43)
from Crypto.Util.number import long_to_bytes
'''
factor(2531257) = 509*4973
'''
p,q = (509,4973)
from Crypto.Util.number import inverse
phi = (p-1)*(q-1)
d = inverse(e,phi)
'''
d=58739L
'''
c = '906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268'.split(' ')
c = [int(i) for i in c]
import sys
for i in c:
print pow(i,d,n)
msg = [103, 105, 103, 101, 109, 123, 83, 97, 118, 97, 103, 101, 95, 83, 105, 120, 95, 70, 108, 121, 105, 110, 103, 95, 84, 105,103, 101, 114, 115, 125]
for i in msg:
sys.stdout.write(chr(i))
最後ちょっとひねって、二文字のasciiを繋いだことに気づき、手動で分離しました。
[Crypro 492pts] Holey Knapsack
My knapsack has a hole in it
Cipher text: 11b90d6311b90ff90ce610c4123b10c40ce60dfa123610610ce60d450d000ce61061106110c4098515340d4512361534098509270e5d09850e58123610c9 Public key: {99, 1235, 865, 990, 5, 1443, 895, 1477}
ちょっとググったら、解説が発見
原理:https://nrich.maths.org/2199
最初はprintableの文字を全部暗号化して辞書から当てようとしたら、うまくいかず。
たぶん昔が出題されたことあると踏んで検索したらありました。
ctfs/solve.py at master · everping/ctfs · GitHub
上記のsolver参考してやってみたけどもうまくいかず、最後ほかのメンバーが解いてくれました。 結局のところ、暗号文を分けないといけないですね。
from sage.all import *
c = '11b90d6311b90ff90ce610c4123b10c40ce60dfa123610610ce60d450d000ce61061106110c4098515340d4512361534098509270e5d09850e58123610c9'
pubKey = [99, 1235, 865, 990, 5, 1443, 895, 1477]
nbit = len(pubKey)
c = [c[i:i+4] for i in range(len(c)-3,4)]
encoded = map(lambda x: int(x,16),c)
print "start"
for j in encoded:
# create a large matrix of 0's (dimensions are public key length +1)
A = Matrix(ZZ,nbit+1,nbit+1)
# fill in the identity matrix
for i in xrange(nbit):
A[i,i] = 1
# replace the bottom row with your public key
for i in xrange(nbit):
A[i,nbit] = pubKey[i]
# last element is the encoded message
A[nbit,nbit] = -j
res = A.LLL()
print "M: "
M = res.row(8).list()
print M
あとあと考えたらおそらく暗号化の実装がちょっと間違えたかな、二進数を逆転してから重りを計算したほうが多分ちゃんと辞書も作れると思います。
[Misc 340pts] Hello World
空白がやたら多いcファイルがあって、多分それもコードかなという予想がつきました。検索したら、どうやら空白でもコードをかけるそうで、しかもオンラインIDEもあるということで、そのまま投げました。
Whitelips the Whitespace IDE
最初は↓のような文字しか見えなかった。
Well sweet golly gee, that sure is a lot of whitespace!
右を見たら空白*2はprintcに等しいことがわかりました。
あとはひたすらprintcの数を増やして後ろの文字を吐かせる。
Well sweet golly gee, that sure is a lot of whitespace!}3v4h_u0y_gn1c4ps_t4hw_ym_h0{megig
を逆にしたらフラグでした。
[Android 376pts] Secrets
Android系の問題を初めて触ってみた、とりあえずいろいろググりまくりました。結果以下のような手順に至りました。
* unzip howdy.zip
* d2j-dex2jar.sh classes.dex
* JD-GUIで開くR.classの中にflagというstringが発見
* aapt dump --values resources howdyapp.apk resources.arsc > v.txt
* cat v.txt | grep 0x7f0b0020 --after-context=5
これでstring中のflagの抽出ができました。
flag:gigem{infinite_gigems}
[Android 460pts] Local News
これもたしか一緒のような気がした。
flag:gigem{hidden_81aeb013bea}
[Reversing 100pts] Cheesy
確かにStringして変な文字列があったのでとりあえずbase64にデコードしたらflagでした。
flag:gigem{3a5y_R3v3r51N6!}
[Reversing 100pts] Snakes over cheese
.pycがあったのでそのままimportできそうですので、やってみました、その中変な配列が
In [1]: import reversing2
In [2]: reversing2.Fqaa
Out[2]: [102, 108, 97, 103, 123, 100, 101, 99, 111, 109, 112, 105, 108, 101, 125]
In [3]: print ''.join([chr(i) for i in reversing2.Fqaa])
flag{decompile}
[Reversing 384pts] 042
リバースことがわからないですが、でもちょっと見てみたらasciiっぽいやつが数行あったので、とりあえず変換したらflagでした。
movb $65, -16(%rbp) movb $53, -15(%rbp) movb $53, -14(%rbp) movb $51, -13(%rbp) movb $77, -12(%rbp) movb $98, -11(%rbp) movb $49, -10(%rbp) movb $89, -9(%rbp) print ''.join(map(lambda x: chr(x),[65,53,53,51,77,98,49,89])) A553Mb1Y
gigem{A554Mb1Y}
[Network/Pentest 324pts] Stop and Listen
指示通りopenVPNで繋いであげて、問題文ようにwiresharkでしばらくlistenして、stopしたら,flagがありました。
flag:gigem{f0rty_tw0_c9d950b61ea83}
write-up見て勉強になったもの(あとで書くはず)
log app
Mike's Marvelous Mystery Curves
こちらのwrite-upをさんこうしました。当時certificateの確認方法に詰まった、正直にBase64にかけばいいのになといまは思います。
* modulo pの値が小さい → 離散対数問題が突破できる
* sageの中に楕円曲線関数E = EllipticCurve(GF(p), [A, B])
* 離散対数に関する関数d_Alice = G.discrete_log(Q_Alice)
