Some crypto challenges: Author writeup from BSidesSF CTF

Hey everybody,

This is yet another author’s writeup for BSidesSF CTF challenges! This one will focus on three crypto challenges I wrote: mainframe, mixer, and decrypto!

mainframe - bad password reset

mainframe, which you can view on the Github release immediately presents the player with some RNG code in Pascal:

  function msrand: cardinal;
  const
    a = 214013;
    c = 2531011;
    m = 2147483648;
  begin
    x2 := (a * x2 + c) mod m;
    msrand := x2 div 65536;
  end;

If you reverse engineer that, or google a constant, you’ll find that it’s a pretty common random number generator called a Linear Congruential Generator. You can find a ton of implementations, including that one, on Rosetta Code.

The text below that says:

We don't really know how it's seeded, but we do know they generate password resets one byte at a time (12 bytes total) - rand() % 0xFF - and they don't change the seed in between.

I had at least one question about that set up - since rand() % 0xFF at best can only be 255/256 possible values - but this is a CTF problem, right?

To solve this, I literally implemented the gen_password() function in C (on the theory that it’ll be fastest that way):

int seed = 0;

int my_rand() {
  seed = (214013 * seed + 2531011) & 0x7fffffff;
  return seed >> 16;
}

void gen_password(uint8_t buffer[12]) {
  uint32_t i;

  for(i = 0; i < 12; i++) {
    buffer[i] = my_rand() % 0xFF;
  }
}

void print_hex(uint8_t *hex) {
  uint32_t i;
  for(i = 0; i < 12; i++) {
    printf("%02x", hex[i]);
  }
}

Then called it for each possible seed:

  int index;
  for(index = 0x0; index < 0x7FFFFFFF; index++) {
    seed = index;

    gen_password(generated_pw);

    if(!memcmp(generated_pw, desired, 12)) {
      printf("Found it! Seed = %d\n", index);
      gen_password(generated_pw);
      printf("Next password: \n");
      print_hex(generated_pw);
      printf("\n");
      exit(0);
    }
  }

Then I generated a test password: cfd55275b5d38beba9ab355b

Put that into the program:

$ ./solution cfd55275b5d38beba9ab355b
...
Next password:
126ab42e0de3d300260ff309

And log in as root, thereby solving the question!

In case you’re curious, to implement this challenge I store the RNG seed in your local session. That way, people aren’t stomping on each other’s cookies!

mixer - ECB block shuffle

For the next challenge, mixer (Github link), you’re presented with a login form with a first name, a last name, and an is_admin field. is_admin is set to 0, disabled, and isn’t actually sent as part of the form submit. The goal is to switch on the is_admin flag in your cookie.

When you log in, it sends the username and password as a GET request, and tells you to keep an eye on a certain cookie:

$ curl -s --head 'http://localhost:1234/?action=login&first_name=test&last_name=test' | grep 'Set-Cookie: user='
Set-Cookie: user=a3000ad8bfaa21b7b20797c3d480601af63df911b378cf9729a203ff65d35ee723e95cf1d27d3a01758d32ea42bd52bb9b4113cd881549cb3edbc20ca3077726; path=/; HttpOnly

Unfortunately for the player, the cookie is encrypted! We can confirm this by passing in a longer name and seeing a longer cookie:

$ curl -s --head 'http://localhost:1234/?action=login&first_name=AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA&last_name=test' | grep 'Set-Cookie'
Set-Cookie: user=fbfaf2879c8e57b4ba623424c401915228bb743e365ba0dbe6987df8a6c3af9b28bb743e365ba0dbe6987df8a6c3af9b28bb743e365ba0dbe6987df8a6c3af9b1fa044b6e8a48ecb5f6ee54aa10f36c037010895d9a22f694c7b0b415dc22107029f9e0eb4236189e29044158b50c0d0; path=/; HttpOnly
Set-Cookie: rack.session=BAh7B0kiD3Nlc3Npb25faWQGOgZFVEkiRWM3ZDY1NjRlNDFkMTkzODMxNWVi%0AYzFkYWZhNjljMGNkYWY3MzEzNTRiNzE0NmQ5NTRjZDQ0ODQxNTUwNmVjMGMG%0AOwBGSSIMYWVzX2tleQY7AEYiJe%2BrNKamgEXyzoed3PFi8cn7XWYz%2Fu0UnP9B%0AR1OIjrqX%0A; path=/; HttpOnly

Not only is it longer, there’s another important characteristic. If we break up the encrypted data into 128-bit blocks, we can see a pattern emerge:

fbfaf2879c8e57b4ba623424c4019152
28bb743e365ba0dbe6987df8a6c3af9b
28bb743e365ba0dbe6987df8a6c3af9b
28bb743e365ba0dbe6987df8a6c3af9b
1fa044b6e8a48ecb5f6ee54aa10f36c0
37010895d9a22f694c7b0b415dc22107
029f9e0eb4236189e29044158b50c0d0

Notice how the second, third, and fourth blocks encrypt to the same data? That tells us that we’re likely looking at encryption in ECB mode - electronic codebook - where each block of data is independently encrypted.

ECB mode has a useful property called “malleability”. That means that the encrypted data can be changed in a controlled way, and the decrypted version of the data will reflect that change. Specifically, we can move blocks of data (16 bytes at a time) around - rearrange, delete, etc.

We can confirm this by sending back a user cookie with only the repeated field, which we can assume is a full block of As: “AAAAAAAAAAAAAAAA”, twice (we also include the rack.session cookie, which is required to keep state):

$ export USER=28bb743e365ba0dbe6987df8a6c3af9b28bb743e365ba0dbe6987df8a6c3af9b $ export RACK=BAh7B0kiD3Nlc3Npb25faWQGOgZFVEkiRWM3ZDY1NjRlNDFkMTkzODMxNWVi%0AYzFkYWZhNjljMGNkYWY3MzEzNTRiNzE0NmQ5NTRjZDQ0ODQxNTUwNmVjMGMG%0AOwBGSSIMYWVzX2tleQY7AEYiJe%2BrNKamgEXyzoed3PFi8cn7XWYz%2Fu0UnP9B%0AR1OIjrqX%0A $ curl -s 'http://localhost:1234/' -H "Cookie: user=$USER; rack.session=$RACK" | grep Error

Error parsing JSON: 765: unexpected token at 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA'

Well, we know it’s JSON! And we successfully created new ciphertext - simply 32 A characters.

If you mess around with the different blocks, you can eventually figure out that the JSON object encrypted in your cookie, if you choose “First Name” and “Last Name” for your names, looks like this:

{"first_name":"First Name","last_name":"Last Name","is_admin":0}

We can colour the blocks to see them more clearly:

{"first_name":"F
irst Name","last
_name":"Last Nam
e","is_admin":0}

So the “First Name” string starts with one character in the first block, then finished in the second block. If we were to make the first name 17 characters, the first byte would be in the first block, and the second block would be entirely made up of the first name. Kinda like this:

{"first_name":"A
AAAAAAAAAAAAAAAA
AAAAAAAAA","last
_name":"Last Nam
e","is_admin":0}

Note how 100% of the second block is controlled by us. Since ECB blocks are encrypted independently, that means we can use that as a building-block to build whatever customer ciphertext we want!

The only thing we can’t use in a block is quotation marks, because they’ll be escaped (unless we carefully ensure that the </tt> from the escape is in a separate block).

If I set my first name to some JSON-like data:

t:1}             est

And the last name to “AA”, it creates the encrypted blocks:

{"first_name":"t
:1}             
est","last_name"
:"AA","is_admin"
:0}

Then we can do a little surgury, and replace the last block with the second block:

{"first_name":"t
:1}              <-- Moved from here...
est","last_name"
:"AA","is_admin"
:1}              <-- ...to here

Or, put together:

{"first_name":"test","last_name":"AA","is_admin":1}

Or just:

{"first_name":"test","last_name":"AA","is_admin":1}

So now, with encrypted blocks, we do the same thing. First encrypt the name t:1} est / AA (in curl, we have to backslash-escape the { and convert to +):

$ curl -s --head 'http://localhost:1234/?action=login&first_name=t:1\}+++++++++++++est&last_name=AA' | grep 'Set-Cookie'
Set-Cookie: user=bb9f8c6b5224a3eebbfe923d31c3ed04c275c360f2a1321f9916ddc88a158d0e10c9e456be5b2e62e9709eb06b1f54a08f115ffefce89f2294fb29c2f2f32ecdc07be6f8d314073bbf780b2b7bbb5f80; path=/; HttpOnly
Set-Cookie: rack.session=BAh7B0kiD3Nlc3Npb25faWQGOgZFVEkiRTExOGFmODMzMjE0ZTA4OWE0OWYy%0ANGYzOTI4MzY1ZWMxNTY0ZGIyMWZhYmZjYzNiNTM5OGQ1MDk4OTA1NGRkMzYG%0AOwBGSSIMYWVzX2tleQY7AEYiJUrTUZz8H7iqi4W5CXOsTV5z4MCP0DTS7ZeI%0A5n02%2B7Xb%0A; path=/; HttpOnly

Then split the user cookie into blocks, like we did with the encrypted text:

bb9f8c6b5224a3eebbfe923d31c3ed04
c275c360f2a1321f9916ddc88a158d0e
10c9e456be5b2e62e9709eb06b1f54a0
8f115ffefce89f2294fb29c2f2f32ecd
c07be6f8d314073bbf780b2b7bbb5f80

We literally switch the blocks around like we did before:

bb9f8c6b5224a3eebbfe923d31c3ed04
c275c360f2a1321f9916ddc88a158d0e <-- Moved from here...
10c9e456be5b2e62e9709eb06b1f54a0
8f115ffefce89f2294fb29c2f2f32ecd
c275c360f2a1321f9916ddc88a158d0e <-- ...to here

Which gives us the new user cookie, which we combine with the rack.session cookie:

$ export USER=bb9f8c6b5224a3eebbfe923d31c3ed0410c9e456be5b2e62e9709eb06b1f54a08f115ffefce89f2294fb29c2f2f32ecdc275c360f2a1321f9916ddc88a158d0e
$ export RACK=BAh7B0kiD3Nlc3Npb25faWQGOgZFVEkiRTExOGFmODMzMjE0ZTA4OWE0OWYy%0ANGYzOTI4MzY1ZWMxNTY0ZGIyMWZhYmZjYzNiNTM5OGQ1MDk4OTA1NGRkMzYG%0AOwBGSSIMYWVzX2tleQY7AEYiJUrTUZz8H7iqi4W5CXOsTV5z4MCP0DTS7ZeI%0A5n02%2B7Xb%0A
$ curl -s 'http://localhost:1234/' -H "Cookie: user=$USER; rack.session=$RACK" | grep Congrats
      <p>And it looks like you're admin, too! Congrats! Your flag is <span class='highlight'>CTF{is_fun!!uffling_block_sh}</span></p>

And that’s the challenge! We were able to take advantage of ECB’s inherent malleability to change our JSON object to an arbitrary value.

decrypto - padding oracle + hash extension

The final crypto challenge I wrote was called decrypto (github link), since by that point I had entirely lost creativity, and is a combination of crypto vulnerabilities: a padding oracle and a hash extension. The goal was to demonstrate the classic Cryptographic Doom Principle, by checking the signature AFTER decrypting, instead of before.

Like before, this challenge uses the user= cookie, but additionally the signature= cookie will need to be modified as well.

Here are the cookies:

$ curl -s --head 'http://localhost:1234/' | grep 'Set-Cookie'
Set-Cookie: signature=e66764f9e71824ad37a46732fb49838e6b65a36bcb7235e9286f6ed5bd84dfa8; path=/; HttpOnly
Set-Cookie: user=e71606ae685181fefb03ad69309e6ad6b8f6a2e0ecc1dd08215bdf27e90c7399e8100767eee43fb6f403d41c733b856b53accf9d755d830d244501b088190adb; path=/; HttpOnly
Set-Cookie: rack.session=BAh7CEkiD3Nlc3Npb25faWQGOgZFVEkiRTE0ZDFlZWNmNjE5MjhhZTg3ZjQy%0AMzk5MGFhZjk0NGZiZDRkYjRjNTk1ODU0OTRkYzAyNzRlOWVjYmI1MGJmNGIG%0AOwBGSSILc2VjcmV0BjsARiINJB8WSMskiqBJIghrZXkGOwBGIiX%2Fz97Y3FAe%0AiIsMrhHmtd1Eh94IpIgj3FRdGcUcSKH0dg%3D%3D%0A; path=/; HttpOnly

We’ll have to maintain the rack.session cookie, since that’s where our encryption keys are stored. We initially have no idea of what format the user= cookie decrypts to, and no matter how much you ask, I wasn’t gonna tell you. You can, however, see a few fields if you look at the actual rendered page:

Welcome to the mainframe!
It looks like you want to access the flag!
...
Please present user object
...
...scanning
...scanning
...
Scanning user object...
...your UID value is set to 57
...your NAME value is set to baseuser
...your SKILLS value is set to n/a
...
ERROR: ACCESS DENIED
...
UID MUST BE '0'

If we refresh, those values are still present, so we can assume that they’re encoded into that value somehow. The cookie is, it turns out, exactly 64 bytes long.

First, let’s make sure we can properly request the page with curl:

$ export RACK=BAh7CEkiD3Nlc3Npb25faWQGOgZFVEkiRTE0ZDFlZWNmNjE5MjhhZTg3ZjQy%0AMzk5MGFhZjk0NGZiZDRkYjRjNTk1ODU0OTRkYzAyNzRlOWVjYmI1MGJmNGIG%0AOwBGSSILc2VjcmV0BjsARiINJB8WSMskiqBJIghrZXkGOwBGIiX%2Fz97Y3FAe%0AiIsMrhHmtd1Eh94IpIgj3FRdGcUcSKH0dg%3D%3D%0A
$ export SIGNATURE=e66764f9e71824ad37a46732fb49838e6b65a36bcb7235e9286f6ed5bd84dfa8
$ export USER=e71606ae685181fefb03ad69309e6ad6b8f6a2e0ecc1dd08215bdf27e90c7399e8100767eee43fb6f403d41c733b856b53accf9d755d830d244501b088190adb
$ curl -s 'http://localhost:1234/' -H "Cookie: user=$USER; signature=$SIGNATURE; rack.session=$RACK"
[...]
   data.push("...your UID value is set to 52");
   data.push("...your NAME value is set to baseuser");
   data.push("...your SKILLS value is set to n/a");
[...]

One of the first things I always try when I see an encrypted-looking cookie is to change the last byte and see what happens. Now that we have a working curl request, let’s try that:

$ export RACK=BAh7CEkiD3Nlc3Npb25faWQGOgZFVEkiRTE0ZDFlZWNmNjE5MjhhZTg3ZjQy%0AMzk5MGFhZjk0NGZiZDRkYjRjNTk1ODU0OTRkYzAyNzRlOWVjYmI1MGJmNGIG%0AOwBGSSILc2VjcmV0BjsARiINJB8WSMskiqBJIghrZXkGOwBGIiX%2Fz97Y3FAe%0AiIsMrhHmtd1Eh94IpIgj3FRdGcUcSKH0dg%3D%3D%0A
$ export SIGNATURE=e66764f9e71824ad37a46732fb49838e6b65a36bcb7235e9286f6ed5bd84dfa8
$ export USER=e71606ae685181fefb03ad69309e6ad6b8f6a2e0ecc1dd08215bdf27e90c7399e8100767eee43fb6f403d41c733b856b53accf9d755d830d244501b088190ade
$ curl -s 'http://localhost:1234/' -H "Cookie: user=$USER; signature=$SIGNATURE; rack.session=$RACK" | grep -i error
    data.push("FATAL ERROR: bad decrypt")

The decrypt fails if we set the last byte wrong! What if we set it to each of the 256 possible bytes?

$ export RACK=BAh7CEkiD3Nlc3Npb25faWQGOgZFVEkiRTE0ZDFlZWNmNjE5MjhhZTg3ZjQy%0AMzk5MGFhZjk0NGZiZDRkYjRjNTk1ODU0OTRkYzAyNzRlOWVjYmI1MGJmNGIG%0AOwBGSSILc2VjcmV0BjsARiINJB8WSMskiqBJIghrZXkGOwBGIiX%2Fz97Y3FAe%0AiIsMrhHmtd1Eh94IpIgj3FRdGcUcSKH0dg%3D%3D%0A
$ export SIGNATURE=e66764f9e71824ad37a46732fb49838e6b65a36bcb7235e9286f6ed5bd84dfa8

$ for i in `seq 0 255`; do export USER=e71606ae685181fefb03ad69309e6ad6b8f6a2e0ecc1dd08215bdf27e90c7399e8100767eee43fb6f403d41c733b856b53accf9d755d830d244501b088190a`printf '%02x' $i`; curl -s 'http://localhost:1234/' -H "Cookie: user=$USER; signature=$SIGNATURE; rack.session=$RACK" | grep -i 'error' | grep -v 'bad decrypt'; done
    data.push("FATAL ERROR: Bad signature!")
    data.push("ERROR: ACCESS DENIED");

There are two errors that are NOT the usual “bad decrypt” one - one is “ACCESS DENIED” - our original - and the other is “Bad signature!”. Hmm! This sounds an awful lot like a padding oracle vulnerability!

Fortunately, I’ve written a tool for this!

Here’s my Poracle configuration file (just a file called Solution.rb in the same folder as Poracle.rb):

# encoding: ASCII-8BIT

##
# Demo.rb
# Created: February 10, 2013
# By: Ron Bowes
#
# A demo of how to use Poracle, that works against RemoteTestServer.
##

require './Poracle'
require 'httparty'
require 'singlogger'
require 'uri'

# Note: set this to DEBUG to get full full output
SingLogger.set_level_from_string(level: "DEBUG")
L = SingLogger.instance()

# 16 is good for AES and 8 for DES
BLOCKSIZE = 16

def request(cookies)
  return HTTParty.get(
    'http://localhost:1234/',
    follow_redirects: false,
    headers: {
      'Cookie' => "signature=#{cookies[:signature]}; user=#{cookies[:user]}; rack.session=#{cookies[:session]}"
    }
  )
end

def get_cookies()
  reset = HTTParty.head('http://localhost:1234/?action=reset', follow_redirects: false)
  cookies = reset.headers['Set-Cookie']

  return {
    signature: cookies.scan(/signature=([0-9a-f]*)/).pop.pop,
    user:      cookies.scan(/user=([0-9a-f]*)/).pop.pop,
    session:   cookies.scan(/rack\.session=([^;]*)/).pop.pop,
  }
end

# Get the initial set of cookies
COOKIES = get_cookies()

# This is the do_decrypt block - you'll have to change it depending on what your
# service is expecting (eg, by adding cookies, making a POST request, etc)
poracle = Poracle.new(BLOCKSIZE) do |data|
  cookies = COOKIES.clone()
  cookies[:user] = data.unpack("H*").pop

  result = request(cookies)
  #result.parsed_response.force_encoding("ASCII-8BIT")

  # Split the response and find any line containing error / exception / fail
  # (case insensitive)
  errors = result.parsed_response.split(/\n/).select { |l| l =~ /bad decrypt/i }

  # Return true if there are zero errors
  errors.empty?
end

data = COOKIES[:user]

L.info("Trying to decrypt: %s" % data)

# Convert to a binary string using pack
data = [data].pack("H*")

result = poracle.decrypt_with_embedded_iv(data)

# Print the decryption result
puts("-----------------------------")
puts("Decryption result")
puts("-----------------------------")
puts result
puts("-----------------------------")

If I run it, it outputs:

$ ruby ./Solution.rb
I, [2019-03-10T14:57:29.516523 #24889]  INFO -- : Starting Poracle with blocksize = 16
I, [2019-03-10T14:57:29.516584 #24889]  INFO -- : Trying to decrypt: 02e16b251f7077786a2bba0d82ce1e4fab04a1a088c681ed493156fb7ef14a7a20b0f63c99a74249f9c04192da896ae0b4105ea7e187de2d960ec95f5de6bbaa
I, [2019-03-10T14:57:29.516604 #24889]  INFO -- : Grabbing the IV from the first block...
I, [2019-03-10T14:57:29.519956 #24889]  INFO -- : Starting Poracle decryptor...
D, [2019-03-10T14:57:29.520023 #24889] DEBUG -- : Encrypted length: 64
D, [2019-03-10T14:57:29.520037 #24889] DEBUG -- : Blocksize: 16
D, [2019-03-10T14:57:29.520047 #24889] DEBUG -- : 4 blocks:
D, [2019-03-10T14:57:29.520070 #24889] DEBUG -- : Block 1: ["02e16b251f7077786a2bba0d82ce1e4f"]
D, [2019-03-10T14:57:29.520085 #24889] DEBUG -- : Block 2: ["ab04a1a088c681ed493156fb7ef14a7a"]
D, [2019-03-10T14:57:29.520098 #24889] DEBUG -- : Block 3: ["20b0f63c99a74249f9c04192da896ae0"]
D, [2019-03-10T14:57:29.520110 #24889] DEBUG -- : Block 4: ["b4105ea7e187de2d960ec95f5de6bbaa"]
...
[... lots of output ...]
...
-----------------------------
Decryption result
-----------------------------
UID 53
NAME baseuser
SKILLS n/a
-----------------------------

Aha, that’s what the decrypted block looks like! Keep in mind that Poracle started its own session, so the values are different than they were earlier.

What we want to do is append a UID 0 to the bottom:

UID 53
NAME baseuser
SKILLS n/a
UID 0

But if we just use the padding oracle to encrypt that, we’ll get an “Invalid Signature” error. Fortunately, this is also vulnerable to hash length extension! And, also fortunately, I wrote a tool for this, too, along with a super detailed blog about the attack!

I added the following code to the bottom of Solution.rb:

# Write it to a file
File.open("/tmp/decrypt", "wb") do |f|
  f.write(result)
end

# Call out to hash_extender and pull out the new data
append = "\nUID 0\n".unpack("H*").pop
out = `./hash_extender --file=/tmp/decrypt -s #{COOKIES[:signature]} -a '#{append}' --append-format=hex -f sha256 -l 8`
new_signature = out.scan(/New signature: ([0-9a-f]*)/).pop.pop
new_data = out.scan(/New string: ([0-9a-f]*)/).pop.pop

This dumps the decrypted data to a file, /tmp/decrypt. It then appends “\nUID 0\n” using hash_extender, and grabs the new signature/data.

Then, finally, we add a call to poracle.encrypt to re-encrypt the data:

# Call out to Poracle to encrypt the new data
new_encrypted_data = poracle.encrypt([new_data].pack('H*'))

# Perform the request to get the flag
cookies = COOKIES.clone
cookies[:user] = new_encrypted_data.unpack("H*").pop
cookies[:signature] = new_signature
puts(request(cookies))

If you let the whole thing run, you’ll first note that the encryption takes a whole lot longer than the decryption did. That’s because it can’t optimize for “probably English letters” going that way.

But eventually, it’ll finish and print out the whole page, including:

...
  data.push("...your UID value is set to 0");
  data.push("...your NAME value is set to baseuser");
  data.push("...your SKILLS value is set to n/a");
  data.push("...your �@ value is set to ");
  data.push("FLAG VALUE: <span class='highlight'>CTF{parse_order_matters}</span></p>");
...

And that’s the end of the crypto challenges! Definitely read my posts on padding oracles and hash extension, since I dive into deep detail!

mainframe - bad password reset

mixer - ECB block shuffle

decrypto - padding oracle + hash extension

Comments