Tuesday, July 13, 2010

smpCTF challenge #1 write-up

smpCTF challenge #1 was a simple web + programming challenge.

We were given the following instructions:
Set S = 1
Set P = 1
Set previous answer = 1

answer = S * P + previous answer + R
R = 39

After this => S + 1 and P + 1 ('answer' becomes 'previous answer') + 39
then repeat this till you have S = 11065.

The final key will be the value of 'answer' when S = 11065.

Example:
So if R = 15..

17 = 1 * 1 + 1 + 15
36 = 2 * 2 + 17 + 15
60 = 3 * 3 + 36 + 15

Submit the correct answer and you will recieve a flag. Have fun ;D

Then in an HTML comment we could read:
<!--VGhlIHZhbHVlcyBvZiBTIGFuZCBSIGNoYW5nZSBldmVyeSA1IG1pbnV0ZXMgb3Igc28gaGVoZSA7-->
 
base64 standing for:
$ echo VGhlIHZhbHVlcyBvZiBTIGFuZCBSIGNoYW5nZSBldmVyeSA1IG1pbnV0ZXMgb3Igc28gaGVoZSA7 | base64 -d
The values of S and R change every 5 minutes or so hehe ;

Obviously we have to implement the algorithm, I used Python for that (because conveniently numbers do not overflow). A dumb (close to the text) implementation could be:
#!/usr/bin/python
import sys
S, P, previous_answer, answer = 1, 1, 1, 0
findS, R = int(sys.argv[1]), int(sys.argv[2])
while S<=findS:
    answer = P * S + previous_answer + R
    S, P = S+1, P+1
    previous_answer = answer
print answer
Then a small shell script to get everything done:
  • retrieve S & R from the CTF page, wget, grep, sed
  • compute the answer using the python script
  • send the result
#!/bin/sh
U="http://www.smpctf.com/xxx874/chg18.php"
wget -qO page.htm "$U"
S=$(grep -oE 'S = [0-9]*' page.htm | tail -n1 |sed 's/S = //')
R=$(grep -oE 'R = [0-9]*' page.htm | head -n1 |sed 's/R = //')
echo "S = $S - R = $R"
A="$(./find.py $S $R)"
echo "Answer: $A"
curl -s -d "answer=$A" "$U" > ans.htm
diff -su page.htm ans.htm |grep '^-\|^+' |grep -v '^---\|^+++'
Execute to get the flag:
$ ./get.sh
S = 11065 - R = 39
Answer: 451639883701
-  </div>
+  <b>Challenge ID</b>: 36b1c546<br><b>Flag</b>: WaSThAtFunORwhaT?!?<br> </div>

The only difficulty was the challenge not working at the beginning, so we thought we didn't understand well the algorithm... hopefully they quickly fixed it.

4 comments:

  1. When I saw this challenge, it reminded me of Series (Math).

    S[n] = (n^2) + S[n-1] + R , S[0] = 1
    can be solved to
    S[n] = n(n+1)(2n+1)/6 + 1 + nR

    I just solved it ;). When playing, I also coded similar to you but using C.

    ReplyDelete
  2. I didn't bother to do the maths but you're right. Very cool solve! :)

    I'd love a challenge where the "easy" way to solve the problem takes too long and the answer expires, so that you are forced to find a smarter way, possibly doing some maths or just smart algorithmic.

    Thanks for your input!

    ReplyDelete
  3. This is all I did...

    s = 0
    p = 0
    prv = 1
    while s<51997:
    s = s + 1
    p = p + 1
    a = (s*p+prv+62)
    print a
    prv = a

    ReplyDelete
  4. Btw thanks for the walk though on # 5 it drove me nuts. also my comment above I wrote that in python, formatting was removed when I posted it.

    ReplyDelete