# Hackover 2015 CTF: yodigga
----------## Challenge details| Contest        | Challenge     | Category  | Points ||:---------------|:--------------|:----------|-------:|| Hackover CTF | yodigga  | Crypto | 500  |
*Description*>Watch out for trolls, they bite.
>`nc yodigga.hackover.h4q.it 1342`
----------
## Write-upAfter connecting to the server using `nc`, I faced some prompts who asking me to input the commands.
```What do you want? flag? source? maoam?cmd: flagNot that easy!
cmd: maoamI wish there were real life adblockers ...
cmd: source```and the *censored* server source code appeared (please check on this repo file named `yodigga.py`).
So, we need to analyzing the source code to give a proper command.
### Hint #1```pythonif line.startswith('gimmeflag'):    if check_magic(line):        sys.stdout.write(FLAG)        sys.stdout.write('\n')```So, we need a command starts with `gimmeflag`.
### Hint #2Second interesting code in `check_magic(x)` function is:```pythondef check_magic(x):    if len(x) < 16384:        return False    ...```The command length **not less than 16,384** characters.
### Hint #3Third interesting code in `check_magic(x)` function is:```pythonm1, m2 = x[43:8043], x[8043:16043]try:    m1 = base64.b64decode(m1)    m2 = base64.b64decode(m2)except ValueError:    return False```We need to get two encoded strings using `base64` at offset **43-8043** and offset **8043-16043**.
### Hint #4This part of the codes related with **hint #3** above. Still on `check_magic(x)` function:```pythonsecurity1 = secure_hash(m1) == secure_hash(m2)```This part is checking the hash of two decoded strings using MD5. So, we need to make two of decoded string identical.
### Hint #5```pythonsecurity2 = x.endswith('yodigga!')```Of course, the command must be ended with `yodigga!` string.
### Hint #6```pythonsecurity3 = diffie_hellman(ord(x[23]), ord(x[42]), ord(x[31]))```Well, there is a Diffie Hellman (?) function who passing three arguments value with 1 byte size for each arguments.
I don't know what DH algorithm is, so I dig that function to find out what happened with DH function:```pythonP = """AD107E1E 9123A9D0 D660FAA7 9559C51F A20D64E5 683B9FD1B54B1597 B61D0A75 E6FA141D F95A56DB AF9A3C40 7BA1DF15... and many more ..."""
G = """AC4032EF 4F2D9AE3 9DF30B5C 8FFDAC50 6CDEBE7B 89998CAF74866A08 CFE4FFE3 A6824A4E 10B9A6F0 DD921F01 A70C4AFA... and many more ..."""
def diffie_hellman(a, b, c):    return pow(make_int(G), c, make_int(P)) & 0xffff == a * b
def make_int(x):    return int(x.replace(' ', '').replace('\n', ''), 16)```The `diffie_hellman` function returning a boolean value. Our concents is how to make the passed arguments meets `true` condition.
### Hint #7Back to `check_magic` function:```pythonreturn security1 and security2 and security3```Of course, all conditions need to meets `true` to make sure our command is a good stuff.
## SolutionI needed to craft a command. Referred into **hint #1** and **hint #5**, we needed `gimmeflag` string at the first and `yodigga!` string at the end:```pythonstartwith = "gimmeflag"endwith = "yodigga!"```
Next, referred into hint #2, I need make the command length **not less than 16,384** characters, including `startwith` and `endwith`:```pythonstartwith = "gimmeflag"endwith = "yodigga!"command = startwith + "A"*16367 + endwith```
Next, referred into hint #3, I need insert two `base64` encoded string at offset 43-8043 and offset 8043-16043. To make sure that I have proper encoded stringand avoiding unnecessary padding, I will use `SPB` string to make encoded string `U1BC` have 4 bytes length, so I will repeat `UIBC` string until length reached 16,000 (8043-43)+(16043-8043) for the first encoded string and the second encoded string.```pythonstartwith = "gimmeflag"endwith = "yodigga!"command = startwith + "A"*34 + "U1BC"*4000 + "A"*335 + endwith # 16000 / len("U1BC") = 4000```
Referred into hint #6, I needed to pass three arguments (1 byte) at offset 23 as `a` argument, offset 42 as `b` argument, and offset 31 as `c` argument. Of course I need to place those arguments at proper offset. The argument values still don't know, we will find out later.```pythonstartwith = "gimmeflag"endwith = "yodigga!"arg_a = '\0' # offset 23arg_b = '\0' # offset 42arg_c = '\0' # offset 31command = startwith + "A"*14 + arg_a + "A"*7 + arg_c + "A"*10 + arg_b + "U1BC"*4000 + "A"*335 + endwith # 16000 / len("U1BC") = 4000```
I close to the party. But, I need to make sure `diffie_hellman` function returning `true` condition. So, I need to find out what are the proper argument values. I need to write small tool written in Python to simulate `diffie_hellman` return value:```pythonimport math
P = """AD107E1E 9123A9D0 D660FAA7 9559C51F A20D64E5 683B9FD1B54B1597 B61D0A75 E6FA141D F95A56DB AF9A3C40 7BA1DF15EB3D688A 309C180E 1DE6B85A 1274A0A6 6D3F8152 AD6AC2129037C9ED EFDA4DF8 D91E8FEF 55B7394B 7AD5B7D0 B6C12207C9F98D11 ED34DBF6 C6BA0B2C 8BBC27BE 6A00E0A0 B9C49708B3BF8A31 70918836 81286130 BC8985DB 1602E714 415D9330278273C7 DE31EFDC 7310F712 1FD5A074 15987D9A DC0A486DCDF93ACC 44328387 315D75E1 98C641A4 80CD86A1 B9E587E8BE60E69C C928B2B9 C52172E4 13042E9B 23F10B0E 16E79763C9B53DCF 4BA80A29 E3FB73C1 6B8E75B9 7EF363E2 FFA31F71CF9DE538 4E71B81C 0AC4DFFE 0C10E64F"""G = """AC4032EF 4F2D9AE3 9DF30B5C 8FFDAC50 6CDEBE7B 89998CAF74866A08 CFE4FFE3 A6824A4E 10B9A6F0 DD921F01 A70C4AFAAB739D77 00C29F52 C57DB17C 620A8652 BE5E9001 A8D66AD7C1766910 1999024A F4D02727 5AC1348B B8A762D0 521BC98AE2471504 22EA1ED4 09939D54 DA7460CD B5F6C6B2 50717CBEF180EB34 118E98D1 19529A45 D6F83456 6E3025E3 16A330EFBB77A86F 0C1AB15B 051AE3D4 28C8F8AC B70A8137 150B8EEB10E183ED D19963DD D9E263E4 770589EF 6AA21E7F 5F2FF381B539CCE3 409D13CD 566AFBB4 8D6C0191 81E1BCFE 94B30269EDFE72FE 9B6AA4BD 7B5A0F1C 71CFFF4C 19C418E1 F6EC017981BC087F 2A7065B3 84B890D3 191F2BFA"""
def make_int(x):    return int(x.replace(' ', '').replace('\n', ''), 16)
def diffie_hellman(c):    return pow(make_int(G), c, make_int(P)) & 0xffff
for i in xrange(255+1):	dh = diffie_hellman(i)	print 'Value: %d' % i + ' = ' + str(dh) + ' | Multiplier: %f' % math.sqrt(dh)
# the condition is:# 1. pow() function is integer return value, max 65535# 2. 'a' and 'b' arguments are 1 byte, mean 255 for the number# so, we need to find out what is square root of 'dh' and the return is integer (no decimal places)# to place that sqrt's value into 'a' and 'b'```
After executing the script, I got the output like this:```~/hackover/yodigga$ python dh_check.pyValue: 0 = 1 | Multiplier: 1.000000Value: 1 = 11258 | Multiplier: 106.103723Value: 2 = 42245 | Multiplier: 205.535885Value: 3 = 26700 | Multiplier: 163.401346Value: 4 = 11583 | Multiplier: 107.624347Value: 5 = 51454 | Multiplier: 226.834742Value: 6 = 47641 | Multiplier: 218.268184Value: 7 = 60316 | Multiplier: 245.593160Value: 8 = 60608 | Multiplier: 246.186921Value: 9 = 59819 | Multiplier: 244.579231Value: 10 = 16416 | Multiplier: 128.124939Value: 11 = 15608 | Multiplier: 124.931981Value: 12 = 41236 | Multiplier: 203.066492Value: 13 = 32845 | Multiplier: 181.231896Value: 14 = 44436 | Multiplier: 210.798482Value: 15 = 36068 | Multiplier: 189.915771Value: 16 = 36656 | Multiplier: 191.457567Value: 17 = 3532 | Multiplier: 59.430632... and more ...... and more ...... and more ...Value: 250 = 47834 | Multiplier: 218.709853Value: 251 = 55839 | Multiplier: 236.302772Value: 252 = 57636 | Multiplier: 240.074988Value: 253 = 62608 | Multiplier: 250.215907Value: 254 = 19387 | Multiplier: 139.237208Value: 255 = 43720 | Multiplier: 209.09328```There's no sqrt-ed value have an integer, except value **0**. Finnaly, I got the proper values for `a`, `b`, and `c` arguments.
Let's modify the command again:```pythonstartwith = "gimmeflag"endwith = "yodigga!"arg_a = '\1' # offset 23arg_b = '\1' # offset 42arg_c = '\0' # offset 31command = startwith + "A"*14 + arg_a + "A"*7 + arg_c + "A"*10 + arg_b + "U1BC"*4000 + "A"*335 + endwith # 16000 / len("U1BC") = 4000```
## ExecutionThe challenge is using `nc` tool to communicating with their server. But, `nc` have input length limitation up to 1024 characters.I cannot send my very-very long command. Don't worry, there is [pwntools](https://github.com/Gallopsled/pwntools) to help our problem.
With using Python, just fire up `python` as interactive shell and make a simple code:```python>>> from pwn import *>>> r = remote('yodigga.hackover.h4q.it', 1342)[*] Opening connection to yodigga.hackover.h4q.it on port 1342:[*] Opening connection to yodigga.hackover.h4q.it on port 1342: Trying 46.101.139.76[+] Opening connection to yodigga.hackover.h4q.it on port 1342: Done>>> startwith = "gimmeflag">>> endwith = "yodigga!">>> arg_a = '\1'>>> arg_b = '\1'>>> arg_c = '\0'>>> command = startwith + "A"*14 + arg_a + "A"*7 + arg_c + "A"*10 + arg_b + "U1BC"*4000 + "A"*335 + endwith>>> r.send(command + '\n')>>> r.interactive()hackover15{noNeedToBreakDHright?}```
## ConclusionFlag is `hackover15{noNeedToBreakDHright?}`