Cryptography

Challenge	Link
Casino (101 solves)	Here
Spring (48 solves)	Here
Order (46 solves)	Here

Casino (101 solves)

Description

Care to test your luck?

nc casino.hsctf.com 1337

Solution

So we need money >= 1000000000 to get the flag. Since we can control nonce and hex we can manipulate the plaintext during the decryption process.

To modify the money (plaintext) which is 0.0, we can use scientific notation to get big number with only 3 bytes values. To modify the money (plaintext) which is 0.0, we can use scientific notation to get big number with only 3 bytes value. Here is the detail of process

pt_nonce = Decrypt(nonce) 
tmp1 = pt_nonce[12]^ct_value[12] # pt_nonce[12] ^ ct_value[12] = ord('0')
tmp2 = pt_nonce[11]^ct_value[11] # pt_nonce[11] ^ ct_value[11] = ord('.')
tmp3 = pt_nonce[10]^ct_value[10] # pt_nonce[10] ^ ct_value[10] = ord('0')

# convert the value to our target by converting to null byte and then target
tmp1 ^ ord('0') ^ ord('9') = ord('9') # ord('0') ^ ord('0') = 0 -> 0 ^ ord('9') = ord('9')
tmp2 ^ ord('.') ^ ord('e') = ord('e') # ord('.') ^ ord('.') = 0 -> 0 ^ ord('e') = ord('e')
tmp3 ^ ord('0') ^ ord('1') = ord('1') # ord('0') ^ ord('0') = 0 -> 0 ^ ord('1') = ord('1')

from pwn import *

def flag():
	r.recvuntil(b"> ")
	r.sendline(b"1")

def play():
	r.recvuntil(b"> ")
	r.sendline(b"2")
	r.recvuntil(b"> ")
	r.sendline(b"1")

def save():
	r.recvuntil(b"> ")
	r.sendline(b"4")
	r.recvuntil(b": ")
	saved = r.recvline().strip().decode().split(".")
	r.close()
	return saved

def load(nonce, ct):
	data = nonce.hex() + "." + ct.hex()
	r.recvuntil(b"> ")
	r.sendline(b"3")
	r.recvuntil(b"> ")
	r.sendline(data.encode())
	return r.recvline()

def attack(ct):
	ct = list(ct)
	ct[12] ^= ord('0')
	ct[12] ^= ord('9')
	ct[11] ^= ord('.')
	ct[11] ^= ord('e')
	ct[10] ^= ord('0')
	ct[10] ^= ord('1')
	return bytes(ct)

r = remote("casino.hsctf.com", 1337)
data = save()
nonce = bytes.fromhex(data[0])
ct = bytes.fromhex(data[1])

ct = attack(ct)

r = remote("casino.hsctf.com", 1337)
resp = load(nonce, ct)
flag()
r.interactive()

Flag : flag{you're_ready_for_vegas_now}

Spring (48 solves)

Description

One day in April, I found these strange numbers, along with a program.

Solution

The program encrypt the image using random number generated by Java.util.Random.nextLong . nextLong is pseudorandom generator and for cracking it i used script provided by https://github.com/Cr4ckC4t/crack-java-prng/blob/main/crack-nextLong.py . Here is the full implementation for my solver

#!/usr/bin/env python3

# Implement and crack java's util.Random.nextLong()
# Reference: https://developer.classpath.org/doc/java/util/Random-source.html

import sys
from Crypto.Util.number import *
# Colors
class fc:
        cyan = '\033[96m'
        green = '\033[92m'
        orange = '\033[93m'
        red = '\033[91m'
        end = '\033[0m'
        bold = '\033[1m'


# Return the signed representation of a value
# For example:
#	unsigned  1001 =  9
#       signed    1001 = -7
#
#  getSigned(9,4) == 7
#
def getSigned(n,bits):
	if n >= 2**(bits-1):
		return -((n^(2**bits-1))+1)
	else:
		return n

# Returns the value that you need to pass to java.util.Random.setSeed()
# in order to set the seed to `seed`.
def reverseSeed(seed):
        return (seed ^ 0x5DEECE66D)

# This function is unused in this code.
# It implements the java.util.Random.setSeed() function
def setSeed(seed):
	return (seed ^ 0x5DEECE66D) & (2**48-1)

# Implementation of java.util.Random.next(32)
def next32(seed):
	newseed = (seed * 0x5DEECE66D + 0xB) & (2**48-1)
	return newseed, getSigned((newseed >> 16), 32)

# Implementation of java.util.Random.nextLong()
def nextLong(seed):
	seed, a = next32(seed)
	seed, b = next32(seed)
	return  seed, getSigned(((a<<32)+b), 64)

# Contrary to getSigned(), expects 64 bit as input
# Returns the correct bit representation of the value but as positive integer
def signedLongToInt(long):
        x = ''
        if long < 0:
                x = bin((abs(long)^(2**64-1))+1)[2:]
        else:
                x = bin(long)[2:]
        return int(x,2)

# Since one long token consists of two generate 32 bit tokens
# and since the first token consists of the first 32 bit of the
# seed for the second token - we can brute force the remaining 16
# bits to find the seed that was used to create the second token.
# Once we have the seed, we can create every following number.
def crackSeed(long):
	longbin = bin(signedLongToInt(long))[2:]  # get the correct binary representation of a long
	longbin = '0'*(64-len(longbin))+longbin   # pad seed to 64 bit

	lower = longbin[32:]  # take lower 32 bit

	# Usually brute forcing the 16 LSBs of the 48 bit seed should be good enough
	# But in some special cases, we might need to brute force a few more bits

	for bits in range(16,20): # amount of bits to brute force
		print(f'{fc.orange}[>]{fc.end} Brute forcing {fc.orange}{bits}{fc.end} bits...')
		upper = longbin[0:48-bits] 				# the *known* bits of the seed (start at 32)
		for i in range(2**bits): 				# iterate over all unknown bits
			bini = bin(i)[2:]
			bini = '0'*(bits-len(bini))+bini  		# pad unknown bits to correct length
			print(f'\tSeed: {fc.cyan}{upper}{fc.red}{bini}{fc.end}', end='\r')
			genseed = upper+bini				# create the 48 bit seed
			ns, nb = next32(int(genseed,2)) 		# call nextInt() with the seed
			if nb == getSigned(int(lower,2),32):		# compare with the known result (lower)
				print("\n")
				# The found seed is the one being used internally
				print(f"{fc.green}[>] Found the used seed: {int(genseed,2)}{fc.end}")
				# If you want to start a PRNG with this seed manually (e.g. Java REPL)
				# you'll have to use the reversed seed.
				seed = reverseSeed(int(genseed,2))	# reverse the seed
				print(f"{fc.green}[>]{fc.end} The reversed seed is: {fc.green}{seed}{fc.end}")
				return ns				# return the next seed
		print(f'\n\t{fc.red}Couldn\'t find the seed.{fc.end}')
	print()
	sys.exit(1)

token = -504229198866833519
png_sig = bytes.fromhex("89504E470D0A1A0A")
png = png_sig
png_sig = bytes_to_long(png_sig)

f = open("out.txt","r").read()
exec(f"out = {f}")
seed = crackSeed(png_sig^out[0])
ns = seed
for i in range(1,len(out)):
	ns, long = nextLong(ns)
	png += long_to_bytes((out[i]^long)&0xffffffffffffffff).rjust(8,b'\x00')

g = open("flag.png","wb")
g.write(png)
g.close()

Flag : flag{the_season_of_lies}

Order (46 solves)

Description

Python's hash function is not cryptographically secure. I thought I was cool and tried writing my own hash function that was somewhat similar. Sadly, I forgot to store my flag and all I have left is this challenge and the fact that it's output is 1. Can you help me recover the flag?

Solution

From euler's theorem we know that a^phi = 1 mod n. By using this knowledge we can get phi value from modulus then bruteforcing all possibilities through its divisor then reverse the encryption process. Here is solver i used during competition

from Crypto.Util.number import *

# reverse encryption process
# t = k*(phi - 1)
# (flag^-1 * a) mod p = t
# flag^-1  = t * a^-1
# flag = ((flag ^-1)^-1)

sus = 11424424906182351530856980674107667758506424583604060548655709094382747184198
a = 19733537947376700017757804691557528800304268370434291400619888989843205833854285488738413657523737062550107458
p = 48743250780330593211374612602058842282787459461925115700941964201240170956193881047849685630951233309564529903

a_inv = pow(a, -1, p)


phi = euler_phi(p)

for i in divisors(phi):
    if pow(sus, i, p) == 1:
        for t in range(i-1, p, i):
        	tmp = a_inv * t
        	tmp = pow(tmp, -1, p)
        	flag = long_to_bytes(tmp)
        	if b"flag{" in flag:
        		print(flag.decode())
        		break
        break

Flag : flag{big_numbers_are_bad_numbers}