Hohoho 3 continue (crypto)

Below is the server source code:

#!/usr/bin/env python3
import hashlib
from Crypto.Util.number import *

m = getRandomNBitInteger(128)

class User:
	def __init__(self, name, token):
		self.name = name
		self.mac = token

	def verifyToken(self):
		data = self.name.encode(errors="surrogateescape")
		crc = (1 << 128) - 1
		for b in data:
			crc ^= b
			for _ in range(8):
				crc = (crc >> 1) ^ (m & -(crc & 1))
		return hex(crc ^ ((1 << 128) - 1))[2:] == self.mac

def generateToken(name):
	data = name.encode(errors="surrogateescape")
	crc = (1 << 128) - 1
	for b in data:
		crc ^= b
		for _ in range(8):
			crc = (crc >> 1) ^ (m & -(crc & 1))
	return hex(crc ^ ((1 << 128) - 1))[2:]

def printMenu():
	print("1. Register")
	print("2. Login")
	print("3. Make a wish")
	print("4. Wishlist (Santa Only)")
	print("5. Exit")

def main():
	print("Want to make a wish for this Christmas? Submit here and we will tell Santa!!\n")
	user = None
	registered = False
	while(1):
		printMenu()
		try:
			option = int(input("Enter option: "))
			if option == 1:
				# User only can register once to fix forge token bug
				if registered:
					print("Ho Ho Ho! No cheating!")
					break
				name = str(input("Enter your name: "))
				if "Santa Claus" in name:
					print("Cannot register as Santa!\n")
					continue
				print(f"Use this token to login: {generateToken(name)}\n")
				registered = True
				
			elif option == 2:
				name = input("Enter your name: ")
				mac = input("Enter your token: ")
				user = User(name, mac)
				if user.verifyToken():
					print(f"Login successfully as {user.name}")
					print("Now you can make a wish!\n")
				else:
					print("Ho Ho Ho! No cheating!")
					break
			elif option == 3:
				if user:
					wish = input("Enter your wish: ")
					open("wishes.txt","a").write(f"{user.name}: {wish}\n")
					print("Your wish has recorded! Santa will look for it!\n")
				else:
					print("You have not login yet!\n")

			elif option == 4:
				if user and "Santa Claus" in user.name:
					wishes = open("wishes.txt","r").read()
					print("Wishes:")
					print(wishes)
				else:
					print("Only Santa is allow to access!\n")
			elif option == 5:
				print("Bye!!")
				break
			else:
				print("Invalid choice!")
		except Exception as e:
			print(str(e))
			break

if __name__ == "__main__":
	main()

The idea is that when we register a user, the server uses an algorithm to generate a token for us. We cannot register as a user with "Santa Claus" as part of our name.

In order to win we have to determine the token of the "Santa Claus" user, and view the wishes.

The crux of the challenge lies in the generateToken function:

def generateToken(name):
	data = name.encode(errors="surrogateescape")
	crc = (1 << 128) - 1
	for b in data:
		crc ^= b
		for _ in range(8):
			crc = (crc >> 1) ^ (m & -(crc & 1))
	return hex(crc ^ ((1 << 128) - 1))[2:]

The crc value is first initialised to be 0xFFFF...FF (128 bits). The outer for loop iterates through each byte of data in the username. It first does an XOR operation between the byte and the crc value. Then, in the outer for loop, the complement of the least significant bit of the crc value is AND with m (which is the 128-bit secret), before being XOR'd with the leftmost 127 bits of the old crc value to give the new crc value. Finally, the entire crc value is flipped to give us the token.

• Note here that if the rightmost bit of crc is 0 in the inner for loop, (m & -(crc & 1)) just evaluates to 0 . So we effectively just do crc = (crc >> 1) ^ (m & -(crc & 1)).

• However if the rightmost bit of crc is 1 in the inner for loop, then -(crc & 1) evaluates to 0xFFF...F, and (m & -(crc & 1)) evaluates to m, so we basically just do crc = (crc >> 1) ^ m.

• Observe that if data = 0b01111111 or 0x7f, then the outer for loop only occurs once. Then when we do crc ^= b, the seven least significant bits of crc are flipped to 0 , and that would cause the first 7 iterations of the inner for loop to just be right shift operations. On the eighth inner for loop iteration, then we would have crc = (crc >> 1) ^ m.

So if we just took (0xFFF...FFF (128 bits) >> 8) ^ (token(b"\x7f") ^ 0xFFF...FFF (128 bits)), we can retrieve the secret 128-bit value. With the m value, we can then run generateToken ourselves to obtain the token for Santa Claus!

import hashlib
from Crypto.Util.number import *
from pwn import *

# p = process(["python3", "server.py"])
p = remote("43.217.80.203", 34790)
context.log_level = 'debug'
# m = getRandomNBitInteger(128)
# print(f"m: {hex(m)}")

def generateToken(name):
    data = name.encode(errors="surrogateescape")
    # print(f"data: {data}")
    crc = (1 << 128) - 1
    for b in data:
        # print(f"b: {b}")
        crc ^= b
        # print(f"crc: {hex(crc)}")
        for _ in range(8):
            crc = (crc >> 1) ^ (m & -(crc & 1))
            # print(f"crc: {hex(crc)}")
    return hex(crc ^ ((1 << 128) - 1))[2:]

p.sendlineafter(b"option: ", b"1")
p.sendlineafter(b"name: ", b"\x7f")
p.recvuntil(b"login: ")
token = int(p.recvline()[:-1], 16)
last_crc = token ^ 0xffffffffffffffffffffffffffffffff
m = 0xffffffffffffffffffffffffffffff ^ last_crc 
santa_token = generateToken("Santa Claus")
p.sendlineafter(b"option: ", b"2")
p.sendlineafter(b"name: ", b"Santa Claus")
p.sendlineafter(b"Enter your token: ", santa_token.encode())
p.sendlineafter(b"option: ", b"4")
p.interactive() # wgmy{3fa42c79018552d4419e67d186c91875}