📝

# 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{}

new_encryption.py
def new_encryption(file_name, password):
with open(file_name, "rb") as f:
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)

with open(file_name + "_encrypted", "rb") as f:
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)



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:

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')

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
Mccall
Austin
Raymond
Wyatt
Wilcox
Barr
Wood
Buckley
Santiago
(省略)


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

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

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:
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:
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:

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:
p = int(prime_arr[next(gen)].strip())

q = -1
with open('primes.py', 'r')as fp:
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 暗号については、いろんなサイトで定義が異なっていたので、要勉強です（恥ずかしながら初めて聞いたので）

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