3.0 KiB

Raw Permalink Blame History

ASISCTF 2021: Crypto Warm up

In this challenge you are given a cipher text and an encryption algorithm.

Cipher Analysis

First it generates a random n bit prime p and pads the plaintext with random ascii characters until len(msg) == p. In our case p is a 19489 (a 15 bit prime).

def encrypt(msg, nbit):
	l, p = len(msg), getPrime(nbit)
	rstr = random_str(p - l)
	msg += rstr

The random_str function isnt anything special, it just creates a random string using all printable non-whitespace characters. Then it selects a random 1024 bit number which passes the is_valid requirement.

	while True:
		s = getRandomNBitInteger(1024)
			if is_valid(s, p):
				break

Then it computes the ciphertext, it is a permutation of the padded plaintex. For this to be decryptable s would need to be coprime to p.

	enc = msg[0]
	for i in range(p-1):
			enc += msg[pow(s, i, p)]
	return enc

Reducing s

Due to s only being used in $s^{i} \mod p$ s can be reduced modulo p. That means that this can be easily brute forced as there are only p - 1 (19488) possible values for s.

However we can create a solution which is faster than bruteforce and works for p way larger than 19489 using a known plaintext attack.

Reducing the search space

We know that msg starts with 'ASIS{'. The first characters dont give any meaningful information sinec they also appear as the first two characters of the ciphertext. This leaves us with 'I' at index 2, 'S' as index 3 and '{' at index 4

Then, for each character we find all occurences of that character in the ciphertext and their indicies and solve for $s^{n-1} \equiv k \mod p$ where k is the index of the known char and add the roots to set s_i

with open('output.txt') as f:
	output = f.read()

def findIdx(ch):
	return [enum for enum, x in enumerate(output) if x == ch and enum != 0]

known = [('I', 2), ('S', 3), ('{', 4)]
S = set()
for char in known:
	possibilities = findIdx(char[0])
	s = []
	for poss in possibilities:
		roots = Mod(char[1], p).nth_root(poss - 1, all = True)
		s.extend(roots)

Next we define S as the intersection of all sets s_i. S should contain drastically fewer possibilities for s (in our case 2).

Inverting the permutation

Then we can try inverting the permutation for all s in S and see which one looks like the flag. (Here we assume that the flag is less than 100 characters

for s in S:
	flag = 'AS'
	for x in range(2, 100):
		exponent = discrete_log(Mod(x, p), Mod(s, p))
		flag += output[exponent + 1]
	print(flag)

Flag o'clock

After running sage solve.sage the program spits out

possible S: {8562, 10927}
ASIS{_how_dFC.YptZTh1S?h0mx_m4d;_lGD_w;dr\_CUYpI0_5J2T3+?k!!!*Z}j4M?rTU{|MEyI5cnOa6h3+P2Dbv=b,$|R|_)
ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}j-3?cTU&|MEy&*+nOa9F3_P2SbvHb!,aR|_" ```

3.0 KiB Raw Permalink Blame History