📝

niteCTF 2022 に参加しました

2022/12/26に公開約12,700字

結果

チーム参加。94位/492チーム

解けた問題

Cryptography

  • Basically, I locked up [174 solves]
  • itsybitsyrsa [170 solves]
  • Shoo-in [77 solves]

Basically, I locked up [174 solves]

I was experimenting with making a new encryption algorithm, and came up with this one. I unfortunately decided to test it on a file which was very important to me, and now I need help in decrypting the file :(

flag format: NITE{}

途中で与えられたファイルが入れ替わったせいで、手間取りまくった。 CTFのスタートダッシュは控えるべきかな(それでもやりたくなってしまうけど)

new_encryption.py
def new_encryption(file_name, password):
  with open(file_name, "rb") as f:
    plaintext = f.read()
  assert(len(password) == 8)
  assert(b"HiDeteXT" in plaintext)
  add_spice = lambda b: 0xff & ((b << 1) | (b >> 7))
  ciphertext = bytearray(add_spice(c) ^ ord(password[i % len(password)]) for i, c in enumerate(plaintext))
  with open(file_name + "_encrypted", "wb") as f:
    f.write(ciphertext)

def new_decryption(file_name, password):
  with open(file_name + "_encrypted", "rb") as f:
    ciphertext = f.read()
  remove_spice = lambda b: 0xff & ((b >> 1) | (b << 7))
  plaintext = bytearray(remove_spice(c ^ ord(password[i % len(password)])) for i, c in enumerate(ciphertext))
  with open(file_name + "_decrypted", "wb") as f:
    f.write(plaintext)

password = REDACTED

new_encryption("Important", password)
new_decryption("Important", password)

8文字の password がわかれば、復号できるみたい。

また、平文の中には HiDeteXT という文章があることがわかっている。

HiDeteXT の位置を決め打ちすることによって、復号が可能となる。

add_spice    = lambda b: 0xff & ((b << 1) | (b >> 7))
remove_spice = lambda b: 0xff & ((b >> 1) | (b << 7))

HiDeteXT = 'HiDeteXT'

with open('Important_encrypted', 'rb') as f:
    ciphertext = f.read()

    n = len(ciphertext)

    for begin_idx in range(n - len(HiDeteXT)):
        guess_password = [0] * 8
        for i in range(8):
            guess_password[(begin_idx + i) % 8] = ciphertext[begin_idx + i] ^ add_spice(ord(HiDeteXT[i]))
        
        guess_pleintext = ''
        for i in range(n):
            guess_pleintext += chr(remove_spice(ciphertext[i] ^ guess_password[i % 8]))
        
        if 'NITE' in guess_pleintext:
            print(guess_pleintext)
            print(''.join(chr(c) for c in guess_password))
Oh, You Searching for HiDeteXT ??

NITE{BrUT3fORceD_y0uR_wAy_iN}

HiDeteXT

NITE{BrUT3fORceD_y0uR_wAy_iN}

itsybitsyrsa [170 solves]

you have n , e , c . can you figure out the message ?

Flag format: nitectf{}

e = 19 であり、 m^e < N と推測し、計算をしたらflagを得た。

import gmpy2
from Crypto.Util.number import *

ciphertext = 6078024553798423193134967325270202387306878937484454700144785210832339394815755363797263535831144760384402536810461373914152520460747525153665635734626316310578003166548806000257683343852515263031628982090233695220996295032936575716583495728596126751240079096593674364003045802249298199299361678669999745224985018839154146274074600219004965752333973048957727607976725390827990575687729813226401613702699051183257441850021693636974059959344719833412453497905025417839593351622709320636996239925666464353782301133515409222675847507495737188612142538775923129639884713213170912412518764747314619754618935957508354423666708305283517089032529536091110672987796381041103691446861077236961021291528811563298490135433417943714341600679964290019221435173955077079534262914560363410100316164874755331857321367215504170169506530829003731002286506634566210457965981128308504884772191672868854893390582947404342842342030835898357035291520488504627786631610266867404462368810904044020922219016091271442927517366424724153649714183355349680378250273179790120117028240988746574955059493160419888665136152805270891708176918684492030128951968893950334587567572817024928765027704515006283132198362570058143023780563048556943074104495580079392728582124369736058787865590815783160185854832854400083556883133430113640241620974371084500414639729721776378201893504526891318527252714991185354640966396032717093278978086783973148758992064489657034951664501685021776992781825670446309052924862405987959567508952981788143192406287870556075361766899243818598590213907358880725157
e = 19 

plaintext = gmpy2.iroot(ciphertext, e)[0]

print(long_to_bytes(plaintext).decode('utf-8'))

nitectf{rsa_can_be_very_adaptable}

Shoo-in [77 solves]

Mr. Pascal has placed his bet on a game, again. But he thinks you can help him this time.

Flag format: niteCTF{}

chall.py
import gmpy2
import secrets as s
from flag import flag

fn = open(r"firstnames.py", 'r')
ln = open(r"lastnames.py", 'r')
fp = open (r"primes.py", 'r')
fn_content = fn.readlines()
ln_content = ln.readlines()
prime_arr = fp.readlines()

class RNG:
    def __init__ (self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def gen(self):
        out = self.seed
        while True:
            out = (self.a * out + self.b) % self.p
            self.a += 1
            self.b += 1
            self.p += 1
            yield out

def getPrime ():
    prime = int(prime_arr[next(gen)].strip())
    return prime

def generate_keys():
    p = getPrime()
    q = getPrime()
    n = p*q
    g = n+1
    l = (p-1)*(q-1)
    mu = gmpy2.invert(((p-1)*(q-1)), n)
    return (n, g, l, mu)

def pallier_encrypt(key, msg, rand):
    n_sqr = key[0]**2
    return (pow(key[1], msg, n_sqr)*pow(rand, key[0], n_sqr) ) % n_sqr

N=(min(len(fn_content), len(ln_content))) # 1300 <fn = 2000, ln = 1300>
seed, a, b = s.randbelow(N), s.randbelow(N), s.randbelow(N) # 強めの乱数(ライブラリの性質からは逆探知不能)
lcg = RNG(seed, a, b, N)
gen=lcg.gen()

for i in range (0, 10):
    if i==0:
        name1 = fn_content[a].strip()+" "+ln_content[b].strip() # テキトウに名前を作る(最初はa, bを使う), fn, lnともに被りがある
    else:
        name1 = fn_content[next(gen)].strip()+" "+ln_content[next(gen)].strip()
    name2 = fn_content[next(gen)].strip()+" "+ln_content[next(gen)].strip() # シードをもとに戦う
    print (f"{name1}	vs	{name2}")
    
    winner=next(gen)%2
    inp = int(input ("Choose the winner: 1 or 2\n"))
    if (winner!=inp%2):
        print ("Sorry, you lost :(")
        break
    else:
        if (i<9):
            print ("That's correct, here is the next round\n")
        else:
            print ("Congratulations! you made it")
            print ("Can you decode this secret message?")
            key=generate_keys()
            print(pallier_encrypt(key, int.from_bytes(flag, "big"), next(gen))) # 運勝ちをさせないようにするために、乱数の予測値をもとに、RSAを解かせるのね
サーバーの様子
== proof-of-work: disabled ==
Rebekah Elijah  vs      Emery Tobias
Choose the winner: 1 or 2
1
That's correct, here is the next round

Devyn Kelley    vs      Lorenzo Bond
Choose the winner: 1 or 2
2
That's correct, here is the next round

Koen Mcdonald   vs      Cohen Clementine
Choose the winner: 1 or 2
1
That's correct, here is the next round

Aldo Vincent    vs      Demarcus Vernon
Choose the winner: 1 or 2
1
Sorry, you lost :(
firstnames.py
Tyrone
Zain
Gerald
Seamus
Matteo
Erick
Devin
Lucian
Vincent
Nikhil
Damion
Beckham
Emmanuel
Jesse
Bryant
Remington
Lorenzo
Benjamin
Gary
Elisha
(省略)

一部かぶりがある

lastnames.py
Foley
Simmons
Frazier
Beard
Guerrero
Mooney
Hoover
Rojas
Ritter
Stevens
Mercado
Mccall
Austin
Raymond
Wyatt
Wilcox
Barr
Wood
Buckley
Santiago
(省略)

こちらも一部かぶりがある

どうにかしてシードを求める問題だということがわかる。(勘で 10 回勝負することも可能だが、なんにせよそのあとに pallier 暗号を解かないといけないため)

名前の被りが確認されたが、ほんの数十組だったので、被りのない名前が来るまでリセマラした。

今回の場合、最初の name1 によって a, b の初期値がわかり、name2 の firstname によってnext(gen) がわかっているので、これらの値から、 seedを全通り決め打ちすることで求めることができる。

10回勝負すると、pallier 暗号の復号を求められるが、シード値から秘密鍵 p, q を得られるので、定義に従って復号が可能となる。

参考になったサイト

solve.py
from Crypto.Util.number import *
from pwn import *
import gmpy2
import math
import re

def paillier_decrypt(c, pk, sk):
    n, g = pk
    λ, μ = sk
    assert(0 <= c < n*n)
    return (L(pow(c, λ, n*n), n) * μ) % n

def L(x, n):
    return (x - 1) // n

class RNG:
    def __init__ (self, seed, a, b, p):
        self.seed = seed
        self.a = a
        self.b = b
        self.p = p

    def gen(self):
        out = self.seed
        while True:
            out = (self.a * out + self.b) % self.p
            self.a += 1
            self.b += 1
            self.p += 1
            yield out

is_blacklist_fn = [False] * 1300
is_blacklist_ln = [False] * 1300

with open('firstnames.py', 'r') as f:
    fn_content = f.readlines()
    for i in range (1300):
        for j in range (1300):
            if i == j:
                continue
            if fn_content[i].strip() == fn_content[j].strip():
                is_blacklist_fn[i] = True
                is_blacklist_fn[j] = True

with open('lastnames.py', 'r') as f:
    ln_content = f.readlines()
    for i in range (1300):
        for j in range (1300):
            if i == j:
                continue
            if ln_content[i].strip() == ln_content[j].strip():
                is_blacklist_ln[i] = True
                is_blacklist_ln[j] = True

p = remote('34.90.236.228', 1337)

first_call = p.recvline()

retline = p.recvline()

s = retline.decode('UTF-8')

strs = re.findall(r'\S+', s)

with open('firstnames.py', 'r') as fn:
    with open('lastnames.py', 'r') as ln:
        fn_content = fn.read().splitlines()
        ln_content = ln.read().splitlines()

        a = fn_content.index(strs[0])
        b = ln_content.index(strs[1])
        x1 = fn_content.index(strs[3])
        x2 = ln_content.index(strs[4])

        if is_blacklist_fn[a] or is_blacklist_ln[b] or is_blacklist_fn[x1]:
            print("Error")
            exit()

        seed = -1
        for guess_seed in range(1300):
            if (a * guess_seed + b) % 1300 == x1:
                seed = guess_seed
                break

        lcg = RNG(seed, a, b, 1300)
        gen = lcg.gen()
        
        next(gen)
        next(gen)

        choose_the_winner = p.recvuntil('2\n')

        guess_winner = next(gen) % 2

        p.sendline(str(guess_winner).encode('UTF-8'))

        correct = p.recvline()

        for i in range (1, 9):
            #name1
            next(gen)
            next(gen)
            #name2
            next(gen)
            next(gen)

            retline = p.recvline()

            choose_the_winner = p.recvuntil('2\n')

            guess_winner = next(gen) % 2

            p.sendline(str(guess_winner).encode('UTF-8'))

            correct = p.recvline()

            nl = p.recvline()

        # round 10

        #name1
        next(gen)
        next(gen)
        #name2
        next(gen)
        next(gen)

        retline = p.recvline()

        choose_the_winner = p.recvuntil('2\n')

        guess_winner = next(gen) % 2

        p.sendline(str(guess_winner).encode('UTF-8'))

        grats = p.recvline()

        question = p.recvline()

        enc_bytes = p.recvline()

        log.info(f'enc_bytes = {enc_bytes}')

        c = int(enc_bytes.decode('UTF-8'))

        p = -1
        with open('primes.py', 'r')as fp:
            prime_arr = fp.readlines()
            p = int(prime_arr[next(gen)].strip())

        q = -1
        with open('primes.py', 'r')as fp:
            prime_arr = fp.readlines()
            q = int(prime_arr[next(gen)].strip())

        print(f'p = {p}')
        print(f'q = {q}')

        n = p * q

        g = n + 1

        λ = math.lcm(p - 1, q - 1)

        μ = pow(L(pow(g, λ, n*n), n) % n, -1, n)

        m = paillier_decrypt(c, (n, g), (λ, μ))
        
        print(long_to_bytes(m).decode('UTF-8'))

[*] enc_bytes = b'6270768600749165172821326066144736931802886817755933732977495827163549874791365697356252023303153956224233403409552796860610001458868348468871971848312113242556772089956104036986235857676776485183074643400548060139571657367801807649778423311575936962159798282824894206439693165894984453005530846487195930843340278206433697300255728758608024068249733762315924549757239022566696575437340772432763045603168861872626908632803555631841979964206305970502546511666463687971519975955558348966736485108617723565490885554019864209754958424762160272130565925005592651162934975966706231916308195225449816978810508866410887045137\n'
p = 7631248518224585410391152861779423893111649779156243350225102113079533890101695245436107612059545138709554515016861199832350893810558557771024004874889401
q = 11665353488766999356893899956598632665394134661710570205440925140657847512388926059601802068064638775883619737121902116121738483404187299747100163684456957
niteCTF{n0T_sO_R@nd0m}

niteCTF{n0T_sO_R@nd0m}

paillier 暗号については、いろんなサイトで定義が異なっていたので、要勉強です(恥ずかしながら初めて聞いたので)

Discussion

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