Trustd Challange - Writeup
Intro, Initial thoughts & reversing the server
This was a really fun challenge for me, I’ve never done much with crypto before so I learned a lot from it. I looked at it during the CTF and knew there was no way I could finish it in time so moved on to other stuff. I remembered I never re-visited it a while back, so I dug up my old IDB and got back at it. Thx to the GitS guys for makeing a really fun challenge.
Opening up the trustd binary (ghostintheshellcode.com) in IDA, we see a public key in the strings, and SHA1/RSA functions in the imports. So we’re possibly looking at a crypto based reversing challenge. Pulling the pub key from the binary we get:
-----BEGIN PUBLIC KEY----- MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAhm8XUR8nQ1OvYyb/633sEio2B5KAG 2U5o9qQoGc6jAgMBAAE= -----END PUBLIC KEY-----
It looks pretty small, so maybe we can factor the primes used for mod (N) and use those to figure out the private exponent. So, lets take a look at the code and see what it does and how we might be able to exploit it. I’m going to skip how to find the program’s main from libc_start, and portions of code that require the binary to be running as the user ‘trustd’, its pretty common code but if you need help with it just give me a shout. The server forks off so it can listen for new connections, but for debugging purposes you can either
set follow-fork-mode child for gdb, or if you debug in IDA simply patch the binary here:
08048DCA 74 31 jz short loc_8048DFD
Make that a jnz (0x75) or just flip the zero flag while debugging, and continue. The call eax just below that will take us where we’ll spend most of our time, sub_80491F2. Inside this function we see several calls to send and recv helper functions:
0804921C E8 EB FE FF FF call sendHelper ; call 0804910C 080492E1 E8 99 FE FF FF call recvHelper ; call 0804917F
After the first branch, we see a call to the time function whos return value is saved to a local variable, followed by a string format function then a send:
08049239 E8 0A F8 FF FF call _time 0804923E 89 85 94 FE FE FF mov [ebp+timestamp], eax ... 08049260 E8 63 F6 FF FF call _sprintf ... 0804926E E8 95 F7 FF FF call _strlen ... 08049287 E8 80 FE FF FF call sendHelper ; "Server timestamp: %u\n"
Next we get a reply from the server to send our package, followed by two recv’s. The first recv expects two bytes from us, and those two bytes determine how much data the next recv takes from us. So we dictate how much data on recv #2. Next there’s a 3rd recv of 0x20 bytes, followed by a branch to some SHA1 functions, and later a call to RSA_public_decrypt. In short, it looks like the server takes some of the data we sent it and performs a SHA1 has on it, then attempts to decrypt some data also sent by us. So lets take a closer look.
So we know that recv #1 lets us define how much data is taken from us on recv #2. Looking at what’s going on at recv #2, we see the following:
080492F7 8B 85 94 FE FE FF mov eax, [ebp+timestamp] ; cpy timestamp to eax 080492FD 89 85 9C FE FE FF mov [ebp+timestamp_and_payload], eax ; cpy timestamp to a buffer 08049303 0F B7 85 9A FE FE+ movzx eax, [ebp+payload_1_sizeofpay] ; cpy data from last recv to eax 0804930A 0F B7 C0 movzx eax, ax ; ensure its a word 0804930D 89 44 24 08 mov [esp+8], eax ; int last recv used as size of this recv 08049311 8D 85 9C FE FE FF lea eax, [ebp+timestamp_and_payload] ; new buf to eax 08049317 83 C0 04 add eax, 4 ; &newbuff+4 0804931A 89 44 24 04 mov [esp+4], eax ; buf 0804931E 8B 45 08 mov eax, [ebp+fd] 08049321 89 04 24 mov [esp], eax ; fd 08049324 E8 56 FE FF FF call recvHelper ; recv the payload
The timestamp is copied to eax, then thats copied to the new buffer used in this recv. At 08049317 it adjusts the address so the data it receives next is appended to the timestamp, then it receives that data. So we now have the timestamp from the server + our data, and on the next branch, we see 0x20 bytes recv’d into another new buffer.
Now at the next chunk of code, first we see a SHA1_Init, SHA1_Update and SHA1_Final. This is calculating the SHA1 of some data we sent the server, and if we look at the code, we see:
0804936E E8 65 F5 FF FF call _SHA1_Init ; initializes a SHA_CTX structure 08049373 0F B7 85 9A FE FE+ movzx eax, [ebp+payload_1_sizeofpay] ; user defined sent data size 0804937A 0F B7 C0 movzx eax, ax 0804937D 83 C0 04 add eax, 4 ; sent size+4 08049380 89 44 24 08 mov [esp+8], eax ; push size 08049384 8D 85 9C FE FE FF lea eax, [ebp+timestamp_and_payload] 0804938A 89 44 24 04 mov [esp+4], eax ; push timestamp+userdata 0804938E 8D 85 24 FE FE FF lea eax, [ebp+SHA_CTX] 08049394 89 04 24 mov [esp], eax ; push &SHA_CTX 08049397 E8 6C F7 FF FF call _SHA1_Update 0804939C 8D 85 24 FE FE FF lea eax, [ebp+SHA_CTX] 080493A2 89 44 24 04 mov [esp+4], eax 080493A6 8D 45 E0 lea eax, [ebp+sha1_timestamp_payload] 080493A9 89 04 24 mov [esp], eax 080493AC E8 57 F5 FF FF call _SHA1_Final
So this is simply calcualting the SHA1 of the timestamp and the data we sent the server in recv #2.
Next we see the public key that’s embedded in the server get loaded into memory, then that key is used to decrypt the data we sent the server in recv #3, note the padding type it’ll be used later:
E8 56 F5 FF FF call _PEM_read_bio_RSA_PUBKEY 89 85 8C FE FE FF mov [ebp+var_10174], eax C7 44 24 10 01 00+ mov dword ptr [esp+10h], 1 ; int padding 8B 85 8C FE FE FF mov eax, [ebp+var_10174] 89 44 24 0C mov [esp+0Ch], eax ; RSA* rsa 8D 45 A0 lea eax, [ebp+decrypted_data] 89 44 24 08 mov [esp+8], eax ; unsigned char* to 8D 45 C0 lea eax, [ebp+encrypted_payload3] 89 44 24 04 mov [esp+4], eax ; unsigned char* from C7 04 24 20 00 00+ mov dword ptr [esp], 20h ; int flen E8 44 F6 FF FF call _RSA_public_decrypt 85 C0 test eax, eax ; check decrypted len
Assuming this decrypt is fine, we see a memcmp next:
0804945C 8D 45 A0 lea eax, [ebp+decrypted_data] ; first 20 bytes of decrypted should = sha1 0804945F 89 44 24 04 mov [esp+4], eax ; s2 08049463 8D 45 E0 lea eax, [ebp+sha1_timestamp_payload] 08049466 89 04 24 mov [esp], eax ; s1 08049469 E8 7A F4 FF FF call _memcmp
So the data that gets decrypted is compared to the SHA1 of the buffer used in recv #3, and later on we see that the data we sent in recv #2 gets executed as long as the decrypt and memcmp are good:
080494F7 8D 85 9C+ lea eax, [ebp+timestamp_and_payload] 080494FD 8D 50 04 lea edx, [eax+4] 08049500 8B 45 08 mov eax, [ebp+fd] 08049503 89 04 24 mov [esp], eax 08049506 FF D2 call edx
Alright, the reversing is done and we know what’s needed. The payload we send the server should look like so:
Analysis of the encryption
Now, on to the crux of the problem (if you know nothing about crypto or RSA), figuring out a way to get all the private key data we need and implementing the client so we can execute a payload on the server. From the public key, we need to get N and the public exponent. There are a couple ways to do this that I’m aware of, searching around you can find a couple of web pages that describe how to pull the data we need out of a base64 decoded key, but an easier option is that openssl can do this for us with the following:
openssl rsa -pubin -noout -text -in Desktop/trustd-pub.key Public-Key: (256 bit) Modulus: 00:c0:21:9b:c5:d4:47:c9:d0:d4:eb:d8:c9:bf:fa: df:7b:04:8a:8d:81:e4:a0:06:d9:4e:68:f6:a4:28: 19:ce:a3 Exponent: 65537 (0x10001)
Alright, now that we have N we need to factor it. The most efficient way to do so (that I’ve found) is by using msieve
Thu Jun 07 17:44:14 2012 Msieve v. 1.48 Thu Jun 07 17:44:14 2012 factoring 86903447985273817061649026028208869261645872445919569781766446906998743748259 (77 digits) ... Thu Jun 07 17:48:27 2012 prp39 factor: 283084734709882699265958010584224673887 Thu Jun 07 17:48:27 2012 prp39 factor: 306987404581657058400653947384531204157 Thu Jun 07 17:48:27 2012 elapsed time 00:04:13
So above are our factors, now we need to use those to generate our private key. The public exponent e and the mod n is given to us by the public key.
Public Exponent: E = 65537 or 0x10001, commonly used. Primes: P = 283084734709882699265958010584224673887 Q = 306987404581657058400653947384531204157 Mod (N) = p*q >>> 283084734709882699265958010584224673887 * 306987404581657058400653947384531204157 N = 86903447985273817061649026028208869261645872445919569781766446906998743748259 Confirming what we see in the openssl output for mod: >>> hex(283084734709882699265958010584224673887 * 306987404581657058400653947384531204157) '0xc0219bc5d447c9d0d4ebd8c9bffadf7b048a8d81e4a006d94e68f6a42819cea3L'
So, we now need the private exponent, and you can find it using the extended euclidean algo. If you’re completely unfamiliar, I’d google around for “pen and paper” explainations of it. If you want/need it quickly just plug it into a tool like keygener assistant or programatically using python or C. There are several crypt libs that can handle it for you. Regardless how you figure it out, we get:
D = 46136253807034681432258946283770559961547133070914278173070258897746316858697
Pseudo-code and stuff
We have everything we need to encrypt/decrypt now, so how do we use it? We already reversed what a client connecting to the server should do, here’s the gist of it.
- generate a timestamp, send it to the end user
- put timestamp at start of main payload buffer
- recv 2, sizeof main payload buffer
- recv sizeof(payload), main payload. payloadBuff = timestamp+main payload
- recv 20h of encrypted data
- do sha1 of timestamp+main_payload
- decrypt the 20h of signed data
- if decrypt is success:
- compare 20 bytes of the decrypted data with the sha1 of the timestamp+main-payload
- if good:
- execute main payload
- if decrypt is success:
- recv timestamp
- put timestamp at beginning of the payload buffer (payload1)
- hash = sha1(payload1)
- signedHash = Rsa_private_encrypt(hash)
- send payload_0(sizeof(payload_1))
- send payload_1(shellcode)
- send payload_2(signedHash)
- cross fingers
I pulled an easy verification by forcing the timestamp to a known so I could have a payload prebuilt instead of on the fly and some small shellcode that was a simple
d@arch86 ~ % nc localhost 1978 < ~/pay3AAAA Trusted Package Manager v0.6a Server timestamp: 1144201745 Send your package now. Signature valid, executing package. Where pay3AAA was: d@arch86 ~ % xxd ~/pay3AAAA 0000000: 0200 ebfe ae84 bcc9 17a1 f0ea 6b97 6798 ............k.g. 0000010: 4652 1a45 bfc7 1cfd d119 faa9 e9b5 5a64 FR.E..........Zd 0000020: d450 12a0 .P..
I set a BP just after the call to time, and set eax to 0x44332211 and the server accepts my package, so I know the code to sign my package is good.
Writing the client & wrap-up
I started by building my code in C/Cpp and just used the openssl libs. My inital thought was, since the server is using RSA_public_decrypt, we can probably just use RSA_private_encrypt on our package and we’re good, which is correct (to an extent). For my client socket code, I used python. That python code recives and parses out the timestamp from the server, then runs my C binary to generate the signed payload. That payload is written to disk, my python client reads it, then builds the package and sends it to the server, and i have a nc listener waiting for my shell.
In my C code, I manually set the key data, then called my modified version of RSA_private_encrypt. After I got everything put together I asked a buddy who had beat it and our code was pretty simliar but I was getting a null ptr deref when I called openssl’s version, so I removed a free(ctx) to get it to work I also removed non-relevant code to make it easier to follow, so its kinda ghetto I guess, but it works. My C code looks something like:
RSA *key = RSA_new(); BIGNUM *n = BN_new(); ... BN_dec2bn(&p, "283084734709882699265958010584224673887"); BN_dec2bn(&q, "306987404581657058400653947384531204157"); BN_hex2bn(&e, "10001"); // 65537 BN_dec2bn(&n, "86903447985273817061649026028208869261645872445919569781766446906998743748259"); BN_dec2bn(&d, "46136253807034681432258946283770559961547133070914278173070258897746316858697"); ... BN_sub(p1,p,BN_value_one()); BN_sub(q1,q,BN_value_one()); BN_mod(dmp1,d,p1,ctx); BN_mod(dmq1,d,q1,ctx); BN_mod_inverse(iqmp, q, p, ctx); ... key->p = p; key->q = q; key->e = e; key->n = n; key->d = d; key->dmp1 = dmp1; key->dmq1 = dmq1; key->iqmp = iqmp; ... int sizePsig = (RSA_size(key)) - 11; //To size unsigned char *encrypted = (unsigned char*) malloc(sizePsig); // To /* perform digital signature using myRSA_eay_private_encrypt */ status = myRSA_eay_private_encrypt(flen, EM, encrypted, key, RSA_PKCS1_PADDING);
The important functions called in myRSA_eay_private_encrypt are:
These add the PKCS1.5 padding (hence ToSize-11) and then encrypt, respectively. You could also use something similar to the above code to write to stdout a pem private key using PEM_write_RSAPrivateKey, which could be imported into python, use ctypes and call everything directly after importing the openssl libs, etc. I believe there are several different ways to approach this challenge, I just stuck with what I started with to save time, avoid dup work etc. Fun challenge though for sure, I enjoyed it and learned a lot. Thanks to a few of the other Robot Mafia guys for pointing out to me what the PKCS1.5 padding actually is/does, which lead me to the bug in my code making my encrypt/decrypt fail. Thanks for reading.