TJCTF2023 Writeup Crypto

はじめに

TJCTF2023に参加しました。
https://ctf.tjctf.org/
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 = m^d \quad mod \quad n$$

$$c_2 =(m2^e)^d \quad mod \quad n$$

$$c_2 =m^d2^{ed} \quad mod \quad n$$

$$\frac{c_2}{2} =m^d \quad mod \quad n = c$$

この問題ではcを当てることができればよいです。$c_2$ を求めることができれば2で割るだけなので、cを求めることができ、フラグの取得ができます。
adminというバイト列をlongに直したものに$2^e$をかけたものを暗号化すると$c_2$ が求まります。

#!/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]

参考

https://inaz2.hatenablog.com/entry/2016/01/20/022936
RSA Attack: Stereotyped message attack | gsdt
セキュリティキャンプ2021 参加記 - Qiita