RSS

Leetmore CTF 2012: PPC 300 (Quantum Computing Captcha)

This entry was posted on Oct 18 2012

Factorizing large numbers is hard. But, prior to solving this challenge, probably nobody knew how hard it actually is!  The challenge provided an image of a large integer with the word “factorize” prepended in front of it. The PNG picture changes every time you visit the page again.


PPC 300

We fetched the HTML of the challenge first to have a look inside.

$ curl http://misteryou.ru/ppc300/



rel=stylesheet type='text/css'>


ReFactor






So what we need to do is to find factors of the big number.

With Wolfram alpha we can input the big number and “factorization” and it will return a list of factors: http://www.wolframalpha.com/input/?i=285333216290284618438394521747220218201+factorization

If we submit the prime number, we get:

ReFactor

You are human! ALERT!

Because, we are too slow.

To automate this process, we need an OCR tool to extract the number from the PNG picture. (typing by hand takes way too long)

It would be nice to calculate the factors with a command line program. First, we tried GNU ‘factor’ of coreutils, but it was very slow (more than a few minutes). Thereafter, we found a much faster and more recent implementation. Just in case if someone wants to get the code:

hg clone http://gmplib.org:8000/factoring

Sadly enough it only supports numbers up to 2^127-1 = 170141183460469231731687303715884105727, while the number that we need to factorize is just one digit bigger.

It is possible to compile it whit GMP (GNU Multiple Precision Arithmetic Library) support, but in that case is seems to be as slow as GNU ‘factor’ of coreutils.

So we decided to use Wolfram alpha anyway (which requires manually copying of the prime factor). When we have one of the factors, we need to send this info with a POST request to http://misteryou.ru/ppc300/

  – captchatype = refactor
  – trueanswer = 3E724A15D0242D2D9D1BB03B
  – answer = prime factor

Our final python code was:

import subprocess
import urllib

# Get the last version of the webpage:
fh_getquestion = urllib.urlopen('http://misteryou.ru/ppc300/')

# Read the HTML and parse out the info we need:
for line in fh_getquestion:
line = line.strip()
if 'src=' in line:
# Extract PNG filename.
png_file = line.split("'")[1][12:]
# Build URL to PNG file.
png_url = 'http://misteryou.ru/ppc300/img/' + png_file
elif 'trueanswer' in line:
# Get trueanswer value.
trueanswer = line.split("'")[5]

fh_getquestion.close()

# Download the PNG image with wget.
subprocess.call(["wget", png_url])

# Run cuneiform to extract the text (number) out of the PNG image.
factorize_nbr = subprocess.check_output(["cuneiform", png_file , "-o",
"/dev/stdout"]).split("\n")[0].split(" ")[1]

# Build the Wolfram alpha URL.
wolfram_alpha_url = "http://www.wolframalpha.com/input/?i=" +
str(factorize_nbr) + "+factorization"

print "\nOpen Wolfram alpha page: " + wolfram_alpha_url + "\n"

# Open the Wolfram alpha page in Firefox.
subprocess.call(["firefox", wolfram_alpha_url])

# Manual step:
# ------------
# Be a really fast human being and copy one of the prime factors
# given by Wolfram alpha to this running script again.

# Paste the prime factor value to this prompt.
answer = raw_input("Enter factor: ")

# Set POST request parameters.
params = urllib.urlencode({ 'captchatype': 'refactor', 'trueanswer':
trueanswer, 'answer': answer })

print "\nPOST paramters: " + params + "\n"

# Submit prime factor with POST request.
fh_answerquestion = urllib.urlopen('http://misteryou.ru/ppc300/', params)

# Print returned HTML.
print fh_answerquestion.read()

fh_answerquestion.close()

The output from the code above:

$ python ./ppc300-solution.py

--2012-10-10 23:51:02-- http://misteryou.ru/ppc300/img/9f9d3b017e405192.png
Resolving misteryou.ru... 159.253.22.174
Connecting to misteryou.ru|159.253.22.174|:80... connected.
HTTP request sent, awaiting response... 200 OK
Length: 15407 (15K) [image/png]
Saving to: `9f9d3b017e405192.png'

100%[===============================================================================================================================================>]
15,407 --.-K/s in 0.1s

2012-10-10 23:51:02 (136 KB/s) - `9f9d3b017e405192.png' saved [15407/15407]

Open Wolfram alpha page:

http://www.wolframalpha.com/input/?i=285333216290284618438394521747220218201+factorization

Enter factor: 16747469112141221639

POST parameters: answer=16747469112141221639&trueanswer=3E724A15D0242D2D9D1BB03B&captchatype=refactor

The result was:



rel=stylesheet type='text/css'>


ReFactor

Ok, u are robot
Secret is:
1101011
1101001
1101100
1101100
1011111
110001
1011111
1101000
1110101
1101101
1100001
1101110

The binary strings always have 7 digits, so it is very likely that they represent ASCII characters:

$ echo '1101011
1101001
1101100
1101100
1011111
110001
1011111
1101000
1110101
1101101
1100001
1101110' | sed -e 's/
/, /g'
1101011, 1101001, 1101100, 1101100, 1011111, 110001, 1011111,
1101000, 1110101, 1101101, 1100001, 1101110

In python we can easily get the string:

>>> print "".join([ chr(int(str(x),2)) for x in [ 1101011, 1101001, 1101100, 1101100, 1011111, 110001, 1011111, 1101000, 1110101, 1101101, 1100001, 1101110 ] ])

The output from the code above was the flag itself.

Solution: kill_1_human


2 Responses to “Leetmore CTF 2012: PPC 300 (Quantum Computing Captcha)”

  1. Hi,

    I’ve also solved this using wolframalpha, but I used wolframalpha API so I can do clean connect and extract result from my py script.

    Example: http://api.wolframalpha.com/v2/query?appid=yourId&input=factor%20‘ + str(num) + ‘&format=plaintext’


  2. Yeah, we thought of that solution later. Parsing the generated XML is the easiest and fastest option.


Post a Comment