python – Terminal Cats

This is from the 0x41414141 CTF by Soul.

For this challenge, we are provided with a c value, n value, and a python script.

c: 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255

n: 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663

import binascii
import random
from Crypto.Util.number import isPrime

flag = open("flag.txt", "rb").read().strip()
m = int(binascii.hexlify(flag), 16)

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

p, q = genPrimes(1024)
n = p * q
e = 0x10001

print("c:", pow(m, e, n))

Based on the provided values and script, this appears to be an RSA type challenge.

I got to https://www.alpertron.com.ar/ECM.HTM to get the possible primes for the provided n value. There are only two:

1521152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591
and
152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793

I iterate these in a script to calculate phi:

primes = [152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591, 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793]

phi = 1
for p in primes:
  phi *= (int(p) - 1)

Based on the e value (e = 0x10001 = 65537) from the provided python script, I calculate d:

e = 65537
d = inverse(e,phi)

I then use the power function with the calculated d value and provided c and n values to get the plaintext value (which gets converted from long to bytes):

plaintext = pow(c,d,n)
print(long_to_bytes(plaintext))

This chunks out our flag:

The full python script:

from Crypto.Util.number import inverse, long_to_bytes

primes = [152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509185464641520736454955410019736330026303289754303711165526821866422766844554206047678337249535003432035470125187072461808523973483360158652600992259609986591, 152103631606164757991388657189704366976433537820099034648874538500153362765519668135545276650144504533686483692163171569868971464706026329525740394016509191077550351496973264159350455849525747355370985161471258126994336297660442739951587911017897809328177973473427538782352524239389465259173507406981248869793]

e = 65537

c = 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255

n = 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663

phi = 1

for p in primes:
  phi *= (int(p) - 1)
d = inverse(e,phi)

plaintext = pow(c,d,n)

print(long_to_bytes(plaintext))

Thank you for the challenge!

This is from the 0x41414141 CTF by pop_eax.

For this challenge, we are just given details for two server instances; one for US and one for EU.

Connecting via netcat, we are told that we will be given a number of problems and we have to solve them. It mentions that level 1 is tower of hanoi. A quick google search and I find more information about it. After some trial and error using different possibilities for the number of pegs.

This presentation was especially helpful in determining the formula (moves = 2ⁿ – 1) to get the number of moves: http://www.cs.uvm.edu/~rsnapp/teaching/cs32/lectures/hanoi.pdf

A manual check confirms the formula is correct, but the server responds with another problem.

There are four disks listed, so n=4. 2⁴ – 1 = 15

We will need to automate this 🙂

import socket

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('45.134.3.200', 9660))

print('Server:', str(s.recv(1024)))
#print s.recv(1024)
while True:
    data = s.recv(1024).strip()
    if data:
	count = 0
        data = str(data)
        print(data)
        for i in data:
		if i == ',':
			count = count + 1
	count = count + 1
	n = pow(2, count) - 1
        if '[' in data:
		s.send(str(n))
        	print('Client: ', n)
s.close()

When I run this script, it iterates through quite a few problems, then the server reports that I’m in level 2: and have to give the number of inversions for the provided output.

A quick google search helps me figure out how to do this in python. https://www.geeksforgeeks.org/python-program-for-count-inversions-in-an-array-set-1-using-merge-sort/

I add some checks for the current level to help apply the appropriate process and then calculate the inversions:

import socket
import re

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('45.134.3.200', 9660))

def getInvCount(arr, n): 
  
    inv_count = 0
    for i in range(n): 
        for j in range(i + 1, n): 
            if (arr[i] > arr[j]): 
                inv_count += 1
  
    return inv_count 
level = 1
print('Server:', str(s.recv(1024)))
while True:
    data = s.recv(2048).strip()
    if data == '':
        break
    if data:
		if 'level 1' in data:
			level = 1
			print ('********************************** Level 1 **********************************')
		if 'level 2' in data:
			level = 2
			print ('********************************** Level 2 **********************************')

		if level == 1:
		
			count = 0
			data = str(data)
			print str(data)
			for i in data:
					if i == ',':
							count = count + 1
			count = count + 1
			n = pow(2, count) - 1
			if '[' in data:
				s.send(str(n))
				#print('Client: ', n)
	
		if level == 2:
			print str(data)
			
			if '[' in data:
			    sep = ']'
			    stripped = data.split(sep, 1)[0]
			    arr1 = stripped.split(', ')
			    arr1 = map(lambda each:each.strip("["), arr1)
			    arr = arr1
			    arr = [int(numeric_string) for numeric_string in arr1]
			    n = len(arr)
			    inversioncount = getInvCount(arr,n)
			    s.send(str(inversioncount))
s.close()

Here is a video of the script in action:

And the flag:

I really appreciate the challenge!

Tag: python

0x41414141 CTF: Crypto: factorize (400)

0x41414141 CTF: Misc: optimizer (400)