😺
TJCTF2023 Writeup Crypto
はじめに
TJCTF2023に参加しました。 0nePaddingのメンバーとして参加しました。主にcryptoを解きました。いつもなら半分も解けないのですが今回は半分以上解くことができてうれしかったです。
babyrsa
Problem
low exponent attackです。
n = 10888751337932558679268839254528888070769213269691871364279830513893837690735136476085167796992556016532860022833558342573454036339582519895539110327482234861870963870144864609120375793020750736090740376786289878349313047032806974605398302398698622431086259032473375162446051603492310000290666366063094482985737032132318650015539702912720882013509099961316767073167848437729826084449943115059234376990825162006299979071912964494228966947974497569783878833130690399504361180345909411669130822346252539746722020515514544334793717997364522192699435604525968953070151642912274210943050922313389271251805397541777241902027
e = 3
c = 2449457955338174702664398437699732241330055959255401949300755756893329242892325068765174475595370736008843435168081093064803408113260941928784442707977000585466461075146434876354981528996602615111767938231799146073229307631775810351487333
Solve
import gmpy2
from Crypto.Util.number import *
n = 10888751337932558679268839254528888070769213269691871364279830513893837690735136476085167796992556016532860022833558342573454036339582519895539110327482234861870963870144864609120375793020750736090740376786289878349313047032806974605398302398698622431086259032473375162446051603492310000290666366063094482985737032132318650015539702912720882013509099961316767073167848437729826084449943115059234376990825162006299979071912964494228966947974497569783878833130690399504361180345909411669130822346252539746722020515514544334793717997364522192699435604525968953070151642912274210943050922313389271251805397541777241902027
e = 3
c = 2449457955338174702664398437699732241330055959255401949300755756893329242892325068765174475595370736008843435168081093064803408113260941928784442707977000585466461075146434876354981528996602615111767938231799146073229307631775810351487333
# low exponent attack with a twist
#
# normal m^e < n
m,result = gmpy2.iroot(c,e)
print(long_to_bytes(int(m)))
print(m)
ezdlp
Problem
以下が与えられます。離散対数問題みたいですね。いいソルバーが見つからなかったので初めはwebサイトを使って無理やり解きました…
sagemathを使うと簡単に解けます。なのできれいな方を載せます。
g = 8999
s = 11721478752747238947534577901795278971298347908127389421908790123
p = 12297383901740584470151577318651150337988716807049317851420298478128932232846789427512414204247770572072680737351875225891650166807323215624748551744377958007176198392481481171792078565005580006750936049744616851983231170824931892761202881982041842121034608612146861881334101500003915726821683000760611763097
g^x = s mod p
flag = tjctf{x}
Solve
g = 8999
s = 11721478752747238947534577901795278971298347908127389421908790123
p = 12297383901740584470151577318651150337988716807049317851420298478128932232846789427512414204247770572072680737351875225891650166807323215624748551744377958007176198392481481171792078565005580006750936049744616851983231170824931892761202881982041842121034608612146861881334101500003915726821683000760611763097
ans = discrete_log(mod(s,p),mod(g,p))
print(ans)
sage ezdlp.sage
26104478854569770948763268629079094351020764258425704346666185171631094713742516526074910325202612575130356252792856014835908436517926646322189289728462011794148513926930343382081388714077889318297349665740061482743137948635476088264751212120906948450722431680198753238856720828205708702161666784517
iheartrsa
Problem
まず初めにフラグの値をハッシュ値に直しています。
適当な素数二つをかけてできた値nを準備します。
最初のハッシュ値を累乗した値がnを超えるまでfor文で回します。
適当に触ってみたところほとんどの場合iが8あたりに落ち着くことがわかりました。このことよりeが8であることがわかります。
あとはlow exponent attackを行いハッシュ値を当て、フラグを取得しました。
#!/usr/local/bin/python3.10 -u
import ast
import sys
import select
from Crypto.Util import number
import hashlib
with open('flag.txt') as f:
flag = f.readline()
raw_bin = str(
bin(int('0x'+str(hashlib.sha256(flag.encode('utf-8')).hexdigest()), 16))[2:])
hsh = int('0b1' + '0' * (256 - len(raw_bin)) + raw_bin, 2)
p = number.getPrime(1024)
q = number.getPrime(1024)
n = p * q
e = 0
for i in range(0, 100):
if pow(hsh, i) >= n:
e = i
break
m = pow(hsh, e, n)
print(f'm: {m}')
print(f'n: {n}')
def input_with_timeout(prompt, timeout):
sys.stdout.write(prompt)
sys.stdout.flush()
ready, _, _ = select.select([sys.stdin], [], [], timeout)
if ready:
return sys.stdin.readline().rstrip('\n')
raise Exception
try:
answer = input_with_timeout('', 20)
try:
answer = ast.literal_eval(answer)
if hsh == answer:
print('you love rsa so i <3 you :DD')
print(flag)
else:
print("im upset")
except Exception as e:
print("im very upset")
except Exception as e:
print("\nyou've let me down :(")
Solve
from pwn import *
import gmpy2
from Crypto.Util.number import *
#context.log_level ="debug"
def strip_data(d):
d = d.replace('\\n', '')
d = d.replace('b', '')
d = d.replace("'", '')
return d
p = remote('tjc.tf', 31628)
m = str(p.recvuntil(b'\n'))
print(m)
m = strip_data(m)[3:]
m = int(m)
print(type(m))
print(m)
n = str(p.recvuntil(b'\n'))
n = strip_data(n)[3:]
n = int(n)
print(n)
e = 8
for i in range(10000):
h,result = gmpy2.iroot(i*n+m,e)
if result:
print(long_to_bytes(int(h)))
print(h)
break
ans_byte = long_to_bytes(h)
p.sendline(str(h))
req = p.recvuntil(b'\n')
print(req)
req = p.recvuntil(b'\n')
print(req)
squishy
Problem
adminというバイト列を累乗してできる値を当てるゲームです。
admin以外の好きなバイト列を暗号化することができます。
dとnが使いまわしなのでうまいこと当てるゲームです。
この問題ではcを当てることができればよいです。
adminというバイト列をlongに直したものに
#!/usr/local/bin/python3.10 -u
import sys
import select
from Crypto.Util.number import bytes_to_long, getPrime
def input_with_timeout(prompt, timeout=10):
sys.stdout.write(prompt)
sys.stdout.flush()
ready, _, _ = select.select([sys.stdin], [], [], timeout)
if ready:
return sys.stdin.buffer.readline().rstrip(b'\n')
raise Exception
def sign(a):
return pow(bytes_to_long(a), d, n)
def check(a, s):
return bytes_to_long(a) == pow(s, e, n)
e = 65537
users = {b"admin"}
p = getPrime(1000)
q = getPrime(1000)
n = p * q
d = pow(e, -1, (p - 1) * (q - 1))
print(n)
while True:
cmd = input("Cmd: ")
if cmd == "new":
name = input_with_timeout("Name: ")
if name not in users:
users.add(name)
print(name, sign(name))
else:
print("Name taken...")
elif cmd == "login":
name = input_with_timeout("Name: ")
sig = int(input_with_timeout("Sign: ").decode())
if check(name, sig) and name in users:
if name == b"admin":
print("Hey how'd that happen...")
print(open("../../../../../../../Downloads/flag.txt", "r").read())
else:
print("No admin, no flag")
else:
print("Invalid login.")
else:
print("Command not recognized...")
Solve
とても汚いです…
from pwn import *
from Crypto.Util.number import *
context.log_level ="debug"
def strip_data(d,st):
d = d.replace('\\n', '')
d = d.replace('b', '')
d = d.replace("'", '')
d = d.replace('"','')
d = d.replace(st,'')
d = d.replace(' ','')
return d
# Prepare in advance
e = 65537
bt = b'admin'
bt_long = bytes_to_long(bt)
e2 = 2**e
m2 = e2*bt_long
m2_bytes = long_to_bytes(m2)
p = remote('tjc.tf', 31358)
# for new
req = p.recvline()
print(req)
req = p.recvuntil(b'Cmd:')
print(req)
p.sendline(b'new')
req = p.recvuntil(b'Name:')
print(req)
p.sendline(m2_bytes)
req = p.recvuntil(b'\n')
print(req)
lst = str(req).split()
print(lst)
#handle data
ans = strip_data(lst[2],'admin')
ans = int(ans)//2
print("admin:",ans)
# for login
req = p.recvuntil(b'Cmd:')
print(req)
p.sendline(b'login')
req = p.recvuntil(b'Name:')
print(req)
p.sendline(b'admin')
req = p.recvuntil(b'Sign:')
print(req)
p.sendline(str(ans))
req = p.recvline()
print(req)
req = p.recvline()
print(req)
e
Problem
序盤でlow exponent attackが出てきたのにまたこれかな？と思いました。
from Crypto.Util.number import bytes_to_long
p = random_prime(2 ^ 650)
q = random_prime(2 ^ 650)
N = p*q
e = 5
flag = open("flag.txt", "rb").read().strip()
m = bytes_to_long(b'the challenges flag is ' + flag)
c = m ^ e % N
print("N: ", N)
print("C: ", c)
print("e: ", e)
案の定low exponent attackでは解けません。
実はmの初めのbytesがわかってしまっています。
通常であればflagのみを暗号化するところ、すべての文字列が暗号化されてしまっています。なので上位ビットがわかる形になっています。
この場合coppersmith's attackが利用できます。
N: 853008036761402960429244085500226305898326229049062709229066738337581395441559298620215547481097485360068401045559533084692445386310317304293873811639421668853703030998563380404046228010704173349786419154143323587451196441095743638783569173579503503557413613700490069592150975220823978641111437607374483116682547794651693986279540940965888470663234601045413512056249535670198419685119952947
C: 298700332507654723773580072855784292117810966958600234446114828082727445272393622869719877676272804981941548843479760604983256960593285221389548684954375981617049731866256547635842115184695147132731165168615990125469633018271766466825307769730709868985624843944432541800012321786587028293887532995722347604510229248766961319729482167555605707032678858635163105035385522888663577785577519392
e: 5
Solve
チームメンバーに協力してもらいました。ビット数がわからないので無理やり解きました。
# partial_m.sage
n=853008036761402960429244085500226305898326229049062709229066738337581395441559298620215547481097485360068401045559533084692445386310317304293873811639421668853703030998563380404046228010704173349786419154143323587451196441095743638783569173579503503557413613700490069592150975220823978641111437607374483116682547794651693986279540940965888470663234601045413512056249535670198419685119952947
c=298700332507654723773580072855784292117810966958600234446114828082727445272393622869719877676272804981941548843479760604983256960593285221389548684954375981617049731866256547635842115184695147132731165168615990125469633018271766466825307769730709868985624843944432541800012321786587028293887532995722347604510229248766961319729482167555605707032678858635163105035385522888663577785577519392
e=5
prefix=11149651487439933873850349163109051510832664011661210400
print(prefix)
PR.<x> = PolynomialRing(Zmod(n))
for i in range(1,2000):
p = prefix << i
f = (p + x)^e - c
diff = f.small_roots(epsilon=1/30)
if len(diff):
print(diff)
break
# [2596154188015208448549466628024351636928606845]
参考
RSA Attack: Stereotyped message attack | gsdt
セキュリティキャンプ2021 参加記 - Qiita
Discussion
アメリカの大学院でサイバーセキュリティを勉強しています。HTB "Twinkle"のWriteupも書いていただけないでしょうか🙇♀️