📝
niteCTF 2022 に参加しました
結果
チーム参加。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{}
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を解かせるのね
:::detailsサーバーの様子
== 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暗号の復号を求められるが、シード値から秘密鍵
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