Category: 0x41414141 CTF

0x41414141 CTF: Crypto: factorize (400)

Posted on by gmk

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!

0x41414141 CTF: Blockchain: sanity check (400)

Posted on by gmk

This is from the 0x41414141 CTF.

This challenge is unique for a sanity check.

We are given a blockchain address for the Rinkeby network:

0x5CDd53b4dFe8AE92d73F40894C67c1a6da82032d

And a solidity script:

pragma solidity ^0.7.0;
//SPDX-License-Identifier: UNLICENSED

contract sanity_check {
    function welcome() public pure returns (string memory){
        return "flag{}";
    }
}

I googled the Rinkeby blockchain and found that I can look up addresses on the Etherscan.io site. Looking up the provided address gives me some information. Specifically under the “Contract” tab:

I see the handy “Decompile ByteCode” button, so I give it a shot:

This opens a new tab with more information about this tool and another button to execute it. This tool is based on the Panoramix decompiler and is designed to decompile smart contracts.

Running the tool gives me what I am looking for:

#
#  Panoramix v4 Oct 2019 
#  Decompiled source of rinkeby:0x5CDd53b4dFe8AE92d73F40894C67c1a6da82032d
# 
#  Let's make the world open source
#

const welcome = 'flag{1t_1s_jus7_th3_st@rt}'

#
#  Regular functions
#

def _fallback() payable: # default function
  revert

This was a very cool sanity check!

0x41414141 CTF: Register Secret PIN

Posted on by gmk

This is from the 0x41414141 CTF.

When I went to register to compete in the 0x41414141 CTF I found that is was a little different from other CTFd based CTFs. Besides the normal registration information, it asks for a pin code (secret pin code for CTF registration).

Going back and looking through the site, I see on the About page that the secret pin code for CTF entry is hidden somewhere on the site:

After pouring through the source files for each page on the site, running curl POSTs, and looking at previous versions of the site on Archive.org, I considered the steganography approach.

Besides the normal social media link images, there are only two images on the site. One is the animated Offshift logo, which yielded no obvious results when running strings, binwalk, or other stego decoders:

The second image is a small Offshift logo that is used as the header logo:

After downloading this image, I ran strings on it to look for anything interesting:

Ahh! I see “secret: 100100100101” at the bottom of the results.

I convert the binary string to decimal:

echo "obase=10; ibase=2; 100100100101" | bc

Using the resulting decimal value as the pin, I am now able to register for the CTF.

0x41414141 CTF: Misc: optimizer (400)

Posted on by gmk

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 = 2n – 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. 24 – 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!