⛳
LA CTF 2025 writeup
概要
実働時間１２時間程度？で6問 (Crypto4問、Rev1問、Misc1問)、1259ポイント 407位でした。楽しい問題が多かったです。
問題ファイルなどはこちら
big e (Crypto, 161pt)
配布ファイル
from Crypto.Util.number import bytes_to_long, getPrime
flag = REDACTED
pt = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e_1 = getPrime(16)
e_2 = getPrime(16)
ct_1 = pow(pt, e_1, n)
ct_2 = pow(pt, e_2, n)
print("ct_1 = ", ct_1)
print("ct_2 = ", ct_2)
print("e_1 = ", e_1)
print("e_2 = ", e_2)
print("n = ", n)
異なる２つのeで暗号しているRSAの問題。
これは、「Common Modulus Attack」が有効だと判断。
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes
#数字は省略
ct_1 = 7003...
ct_2 = 2995...
e_1 = 49043
e_2 = 60737
n = 9162...
def extgcd(a, b):
if b:
d, y, x = extgcd(b, a % b)
y -= (a // b)*x
return d, x, y
return a, 1, 0
g,a,b = extgcd(e_1, e_2)
m1 = pow(ct_1,a,n)
m2 = pow(ct_2,b,n)
m = m1*m2%n
print(long_to_bytes(m).decode())
Extremely Convenient Breaker (Crypto, 212pt)
配布ファイル
#!/usr/local/bin/python3
from Crypto.Cipher import AES
import os
key = os.urandom(16)
with open("flag.txt", "r") as f:
flag = f.readline().strip()
cipher = AES.new(key, AES.MODE_ECB)
flag_enc = cipher.encrypt(flag.encode())
print("Here's the encrypted flag in hex: ")
print(flag_enc.hex())
print("Alright, lemme spin up my Extremely Convenient Breaker (trademark copyright all rights reserved). ")
while True:
ecb = input("What ciphertext do you want me to break in an extremely convenient manner? Enter as hex: ")
try:
ecb = bytes.fromhex(ecb)
if not len(ecb) == 64:
print("Sorry, it's not *that* convenient. Make your ciphertext 64 bytes please. ")
elif ecb == flag_enc:
print("No, I'm not decrypting the flag. ")
else:
print(cipher.decrypt(ecb))
except Exception:
print("Uh something went wrong, please try again. ")
AES暗号のECBモードで暗号化された文字列が出力される。その後、適当な文字列を復号してくれる。
暗号文の最初と最後の文字を"a"に変更した文字列を復号させて、flagの獲得を試みた。
from Crypto.Cipher import AES
from Crypto.Util.number import *
from pwn import *
import time
nc = remote("chall.lac.tf",31180)
tmp = nc.recvuntil(b"hex: \n")
print(tmp.decode())
flag_enc = nc.recvline().decode()
print(flag_enc)
tmp = nc.recvline().decode()
print(tmp)
path = "./out1.dat"
with open(path,"w") as f:
msg = "a"+flag_enc[1:]
nc.sendline(msg.encode())
tmp = nc.recvuntil(b"hex:")
flag_tmp = nc.recvline()
f.write(flag_tmp.decode())
tmp = nc.recvline()
msg = flag_enc[:-2]+"a"
nc.sendline(msg.encode())
tmp = nc.recvuntil(b"hex:")
flag_tmp = nc.recvline()
f.write(flag_tmp.decode())
#一部省略
# b"...\x17as_extremely_convenient_to_get_the_flag_too_heh}"
# b'lactf{seems_it_was_extremely_convenient_to_get_t\x0f...
RSAaaS (Crypto, 234pt)
配布ファイル
#!/usr/local/bin/python3
from Crypto.Util.number import isPrime
def RSAaaS():
try:
print("Welcome to my RSA as a Service! ")
print("Pass me two primes and I'll do the rest for you. ")
print("Let's keep the primes at a 64 bit size, please. ")
while True:
p = input("Input p: ")
q = input("Input q: ")
try:
p = int(p)
q = int(q)
assert isPrime(p)
assert isPrime(q)
except:
print("Hm, looks like something's wrong with the primes you sent. ")
print("Please try again. ")
continue
try:
assert p != q
except:
print("You should probably make your primes different. ")
continue
try:
assert (p > 2**63) and (p < 2**64)
assert (q > 2**63) and (q < 2**64)
break
except:
print("Please keep your primes in the requested size range. ")
print("Please try again. ")
continue
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)
print("Alright! RSA is all set! ")
while True:
print("1. Encrypt 2. Decrypt 3. Exit ")
choice = input("Pick an option: ")
if choice == "1":
msg = input("Input a message (as an int): ")
try:
msg = int(msg)
except:
print("Hm, looks like something's wrong with your message. ")
continue
encrypted = pow(msg, e, n)
print("Here's your ciphertext! ")
print(encrypted)
elif choice == "2":
ct = input("Input a ciphertext (as an int): ")
try:
ct = int(ct)
except:
print("Hm, looks like something's wrong with your message. ")
continue
decrypted = pow(ct, d, n)
print("Here's your plaintext! ")
print(decrypted)
else:
print("Thanks for using my service! ")
print("Buh bye! ")
break
except Exception:
print("Oh no! My service! Please don't give us a bad review! ")
print("Here, have a complementary flag for your troubles. ")
with open("flag.txt", "r") as f:
print(f.read())
RSAaaS()
接続すると、ユーザーがRSA暗号の秘密鍵(
秘密鍵 (
-
p,q p\neq q 2^{63} < p,q < 2^{64}
try, except部分から考えるに、pow()関数を用いている部分が怪しいと推測できる。
d = pow(e,-1,phi)とあるが、
from Crypto.Util.number import *
e = 65537
while True:
x = getPrime(64)
if (x-1)%e==0:
print(x)
break
#10894807912359341419
もっといい方法があったかもしれないが、見つかったので良し。
bigram-times(Crypto, 275pt)
配布ファイル
characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}~_"
flag = "lactf{REDACTED~}"
def bigram_multiplicative_shift(bigram):
assert(len(bigram) == 2)
pos1 = characters.find(bigram[0]) + 1
pos2 = characters.find(bigram[1]) + 1
shift = (pos1 * pos2) % 67
return characters[((pos1 * shift) % 67) - 1] + characters[((pos2 * shift) % 67) - 1]
shifted_flag = ""
for i in range(0, len(flag), 2):
bigram = flag[i:i+2]
shifted_bigram = bigram_multiplicative_shift(bigram)
shifted_flag += shifted_bigram
print(shifted_flag)
# jlT84CKOAhxvdrPQWlWT6cEVD78z5QREBINSsU50FMhv662W
# Get solving!
# ...it's not injective you say? Ok fine, I'll give you a hint.
not_the_flag = "mCtRNrPw_Ay9mytTR7ZpLJtrflqLS0BLpthi~2LgUY9cii7w"
also_not_the_flag = "PKRcu0l}D823P2R8c~H9DMc{NmxDF{hD3cB~i1Db}kpR77iU"
flagの文字列を２つ抽出し、それぞれの文字が文字列charctersの位置を示すpos1, pos2が決定される。そのパラメータに応じて、文字列をシフトさせる。
とりあえず、flagの冒頭"la"となる文字列が何パターン存在しているのかを"aa"から"__"までの総当りで調べる。すると、３通りしか存在せず、配布ファイルにはflagではない文字列が記載されているので、総当りで調べれば終わる。
characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}~_"
def bigram_multiplicative_shift(bigram):
assert(len(bigram) == 2)
pos1 = characters.find(bigram[0]) + 1
pos2 = characters.find(bigram[1]) + 1
shift = (pos1 * pos2) % 67
return characters[((pos1 * shift) % 67) - 1] + characters[((pos2 * shift) % 67) - 1]
shifted_flag = ""
flag_enc = "jlT84CKOAhxvdrPQWlWT6cEVD78z5QREBINSsU50FMhv662W"
# Get solving!
# ...it's not injective you say? Ok fine, I'll give you a hint.
not_the_flag = "mCtRNrPw_Ay9mytTR7ZpLJtrflqLS0BLpthi~2LgUY9cii7w"
also_not_the_flag = "PKRcu0l}D823P2R8c~H9DMc{NmxDF{hD3cB~i1Db}kpR77iU"
flag=""
for i in range(0,len(flag_enc),2):
for a in characters:
for b in characters:
x = a+b
tmp = bigram_multiplicative_shift(x)
if tmp == flag_enc[i:i+2]:
if x==not_the_flag[i:i+2] or x==also_not_the_flag[i:i+2]:
continue
flag += x
print(flag)
余談）
「今回のシフトの方法的にある文字列を示すパラメータは３通りしかない」という部分がすぐにわかるセンスを磨きたいところである。
Rev
patricks-paraflag (Rev, 184pt)
stringコマンドで怪しげな文字列が見つかる。
l_alcotsft{_tihne__ifnlfaign_igtoyt}
１個飛ばしに読むと、"lactf{..."と読める。端まで読んだら、最初から２番目の文字から繰り返してflag獲得。
Misc
extended (misc, 168pt)
配布ファイル
chall.txt
ìáãôæûÆõîîéìùßÅîïõçèßÔèéóßÌïïëóßÄéææåòåîôßÏîßÍáãßÁîäß×éîäï÷óý
gen.py
flag = "lactf{REDACTED}"
extended_flag = ""
for c in flag:
o = bin(ord(c))[2:].zfill(8)
# Replace the first 0 with a 1
for i in range(8):
if o[i] == "0":
o = o[:i] + "1" + o[i + 1 :]
break
extended_flag += chr(int(o, 2))
print(extended_flag)
with open("chall.txt", "wb") as f:
f.write(extended_flag.encode("iso8859-1"))
- flagが１文字ずつ二進数に変換
- 変換された二進数の最初の0が1に変換される。
- 変換後、文字コード"iso8859-1"で出力
という問題。
変換された文字列の最初はどこか不明である。（例：0b11111011では、1~5番目が候補になる。）そこで文字コードを制限に与え、"string.printable"に含まれる文字列をflagとみなした。（正確には他の文字もflagになる可能性もあるが目をつぶった。）
import string
flag_enc="ìáãôæûÆõîîéìùßÅîïõçèßÔèéóßÌïïëóßÄéææåòåîôßÏîßÍáãßÁîäß×éîäï÷óý"
#flag_tmp = flag_enc.decode("eso8859-1").decode()
#print(flag_tmp)
with open("chall.txt", "rb") as f:
flag_enc = f.read()
check_list = string.printable
print(check_list)
flag_tmp = ""
for e in flag_enc:
for i in range(len(bin(e)[2:])):
if bin(e)[i+2]=="1":
tmp = e - (2**(7-i))
if tmp >= 0x110000:
continue
if chr(tmp) in check_list:
flag_tmp += chr(tmp)
else:
break
print(flag_tmp)
感想
予定があったため、あまり着手できませんでしたが、楽しめました。
今回やろうとして忘れていましたが、コンテスト中はどの問題にどの程度時間をかけたのか、など時間を計っておこうと思います。
CryptoではHashと乱数の知識などが未熟なので、力をつけていきたいところです。
Crypto以外はもっと未熟なのでぼちぼち勉強していきます。
Discussion