Zenn

LA CTF 2025 writeup

2025/02/14に公開

概要

実働時間12時間程度?で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)

異なる2つの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,qp,q)を入力し、その後入力に応じて暗号・復号を行ってくれる。どこかでエラーを起こせばflag獲得。

秘密鍵 (p,qp,q)の条件は以下、

  • p,qp,qは素数
  • pqp\neq q
  • 263<p,q<2642^{63} < p,q < 2^{64}

try, except部分から考えるに、pow()関数を用いている部分が怪しいと推測できる。
d = pow(e,-1,phi)とあるが、p,qp,qの値次第でϕ\phieeの逆元が存在している保証はない。
mod   ϕ\mod\ \phiにおいて、ϕ\phixxが互いに素ではない場合、xxは逆元を持たない。

ϕ=(p1)×(q1),e=65537\phi=(p-1)\times(q-1), e=65537であるから、p1p-1eeと互いに素ではない素数ppを見つければ良い。

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の文字列を2つ抽出し、それぞれの文字が文字列charctersの位置を示すpos1, pos2が決定される。そのパラメータに応じて、文字列をシフトさせる。

とりあえず、flagの冒頭"la"となる文字列が何パターン存在しているのかを"aa"から"__"までの総当りで調べる。すると、3通りしか存在せず、配布ファイルには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)

余談)
「今回のシフトの方法的にある文字列を示すパラメータは3通りしかない」という部分がすぐにわかるセンスを磨きたいところである。

Rev

patricks-paraflag (Rev, 184pt)

stringコマンドで怪しげな文字列が見つかる。

l_alcotsft{_tihne__ifnlfaign_igtoyt}

1個飛ばしに読むと、"lactf{..."と読める。端まで読んだら、最初から2番目の文字から繰り返して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が1文字ずつ二進数に変換
  • 変換された二進数の最初の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

ログインするとコメントできます