Thursday, December 6, 2018

Pwn2Win 2018 - GCM

These were the steps to resolve Pwn2Win 2018’s GCM challenge, a challenge about a critical vulnerability in Python’s cryptography package.

Description

There is only one method of performing bank transactions that can not be monitored by The Bavarian. It’s not an ATM, but a secret system.

Server: nc 200.136.252.51 5555


Python script provided with the challenge:

#!/usr/bin/python -u

import os
import ast
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

key = open("secret").read().strip()
flag = open("flag.txt").read().strip()

def get_token(username, admin):
    iv = os.urandom(12)
    
    encryptor = Cipher(
        algorithms.AES(key),
        modes.GCM(iv),
        backend=default_backend()
    ).encryptor()

    balance = 1000 if admin == "Y" else 0
    account = {"username": username, "balance": balance, "secret": key, "admin": admin}
    enc = encryptor.update(str(account)) + encryptor.finalize()
    token = {"iv": iv.encode("hex"), "enc": enc.encode("hex"), "tag": encryptor.tag.encode("hex")}
    return str(token)
    

def login():
    username = raw_input("Username: ")
    password = raw_input("Password: ")
    if username == "admin":
        if password == key:
            token = get_token(username, "Y")
            print("Logged in as Lord of Money! Here is the token: %s" % (token))
        else:
            print("Invalid credentials!")
    else:
        token = get_token(username, "N")
        print("Logged in as %s! Here is the token:\n%s" % (username, token))


def pay():
    token = ast.literal_eval(raw_input("Token: "))
    iv = token["iv"].decode("hex")
    enc = token["enc"].decode("hex")
    tag = token["tag"].decode("hex")

    decryptor = Cipher(
        algorithms.AES(key),
        modes.GCM(iv),
        backend=default_backend()
    ).decryptor()

    account = ast.literal_eval(decryptor.update(enc) + decryptor.finalize_with_tag(tag))
    if account["balance"] != 1000 and account["admin"] == "N":
        print("Huh? you have no money and want the flag? -.-")
    else:
        print(flag)


def menu():
    while True:
        print("\nWelcome to Tr4nsferw1s3! Please chose one of the options:")
        print("  [1] Login")
        print("  [2] Transfer/pay")
        print("  [3] Exit")
        
        option = int(raw_input())
        if option == 1:
            login()
        elif option == 2:
            pay()
        elif option == 3:
            print("Bye!")
            break
        else:
            print("Invalid option!")

if __name__ == '__main__':
    menu()

Introduction

First things first. I think it is nice to explain GCM here before talking about the challenge itself.

As Wikipedia said, “Galois/Counter Mode (GCM) is a mode of operation for symmetric key cryptographic block ciphers that has been widely adopted because of its efficiency and performance”.

When we use ECB or CBC our plaintext is divided into blocks and the blocks are ciphered using the chosen algorithm (like AES or 3DES). The difference between ECB and CBC is the cascate effect, as CBC uses the previous block to encrypt the current block, alongside the algorithm itself. In CBC a new concept appears, the Initialization Vector, so we can use the same approach for the first block. The CBC mode can be seen in the image below.

CBC Block Mode

How does GCM differ from CBC? The plaintext is divided into blocks as well, but the encryption algorithm is used to encrypt a counter, not the plaintext itself. And how is the plaintext encrypted? Using a simple xor between the encrypted counter and the plaintext.

For now, all ciphertexts will be expressed in hex encoding and all plaintexts in UTF-8 encoding.

One-Time Pad (OTP)

There is a symmetric encryption method named One-Time Pad which cannot be cracked. It is about a simple xor between a key and a plaintext. However, the key must have the same size of the plaintext, it cannot be reused and should be random. So, if you want to encrypt 1GB of data, you will need a 1GB random key, and you if you want to encrypt another 1GB of data, you will need another 1GB random key.

So, in an OTP, since the size of my plaintext is the same as the size of my key, the size of my ciphertext will be the same size of my plaintext.

Pretty simple, right? Not really! Obviously it is not feasible to implement such algorithm in the real world. It would be impossible to manage these keys. But the OTP is a very important concept in order to understand stream ciphers and attacks against them.

Changing the contents of the plaintext

How to change the contents of the plaintext in One-Time Pad?

Let’s imagine someone encrypted the follow plaintext:

Please send 1 million bucks to Amanda.

This plaintext was xor’ed using a random key (with the same size of the plaintext) and this is the resulting ciphertext:

481bfb5851e84276ac091fd5e98fbdbc0ded04b66a55f53d89339eaba16b2efef611a3f0354e

I, as the attacker, captured the ciphertext from the network and for some reason I know its plaintext form. I know that the system uses an OTP as its encryption algorithm:

c1 = p1 xor key

with c1 as the ciphertext, p1 as the plaintext and key as the key used. I have c1 and p1, so I can calculate the key, but I will not calculate the key here because it will be easier to understand the attack against GCM this way.

Now let’s say I want to change the ciphertext so as to send the money to Rafael, not Amanda. I know that c2 = p2 xor key, so:

c1 = p1 xor key
c2 = p2 xor key

As xor is a symmetrical operator, I can shift variables to any side I want:

c1 = p1 xor key
c2 = p2 xor key

key = p1 xor c1
key = p2 xor c2

p1 xor c1 = p2 xor c2

p1 xor p2 = c1 xor c2

Interesting, right? So the xor between the plaintexts equals the xor between the ciphertexts. This is what I have now:

p1 = Please send 1 million bucks to Amanda.
p2 = Please send 2 million bucks to Rafael.
c1 = 481bfb5851e84276ac091fd5e98fbdbc0ded04b66a55f53d89339eaba16b2efef611a3f0354e
c2 = ?

Now it’s easy to change the ciphertext to what I want:

p1 xor p2 = c1 xor c2
c2 = c1 xor p1 xor p2

c2 = "481bfb5851e84276ac091fd5e98fbdbc0ded04b66a55f53d89339eaba16b2efef611a3f0354e" xor "Please send 1 million bucks to Amanda." xor "Please send 1 million bucks to Rafael."

c2 = "481bfb5851e84276ac091fd5e98fbdbc0ded04b66a55f53d89339eaba16b2eedfa16acf1384e"

Try to use the key 18779e39228d6205c9677bf5d8afd0d561816dd904759748ea58ed8bd5040ebf9b70cd945460 to decipher the two ciphertexts and you will see the magic. The destination will receive my ciphertext and transfer the money for me.

Prevention against plaintext change

As we’ve seen, it’s easy to generate a new ciphertext when you know the original plaintext and the original ciphertext. Ok, it’s easier to find the key when using OTP, but generate a new ciphertext is quite important concept when we talk about stream ciphers, as retrieve the key is not that easy. AES itself will not protect you against changing the plaintext. When using CBC you need some kind of integrity check like CBC-HMAC. With GCM it’s not different, but it specifies an integrity check by default, as we will see further.

A block cipher as a stream cipher

Quoting Wikipedia: “Stream ciphers can be viewed as approximating the action of a proven unbreakable cipher, the one-time pad (OTP)”.

Stream ciphers will generate a pseudorandom cipher digit stream (keystream) using a seed. I will not get into the specifics of a stream cipher here, but it’s easy to imagine that a stream cipher will expand the original small key to a dynamic big key that will encrypt the original plaintext using xor. A 128 bit key could be expanded to a 1GB key that will be xor’ed with a 1GB plaintext data, for example.

And then we have GCM, a block cipher mode that acts like a stream cipher. Let’s see its diagram:

Galois Counter Mode diagram

Can you see the blue Ek boxes? It’s encrypting a counter, not the plaintext itself. The plaintext is being xor‘ed with the encrypted counter.

Think about that for a minute.

The Ek box uses a Initialization Vector and an encryption key, so the same IV and encryption key will generate the same input for the ciphertext.

Read it loud:

GCM is like a stream cipher. The keystream is generated using the IV and the key. As you will probably reuse the key, the IV should NEVER be reused.

If I use some key and generate a unique IV for every ciphertext I guarantee my confidentiality. As said before, GCM has an integrity check: the Auth Tag (you can see it in the bottom right corner). The Auth Tag will be used to check if the plaintext was changed. A single bit altered in the plaintext also alters the Auth Tag, causing the validation to fail.

GCM is one of the best block cipher modes out there.

If implemented correctly.

Write-up

Service behaviour

There was a service that simulated some kind of internet banking:

rasknikov@kali:~$ nc 200.136.252.51 5555

Welcome to Tr4nsferw1s3! Please chose one of the options:
  [1] Login
  [2] Transfer/pay
  [3] Exit

When logging in as admin, an error was received:

Username: admin
Password: admin
Invalid credentials!

With a different username, a token was generated:

Username: ghost
Password: ghost
Logged in as ghost! Here is the token:
{'enc': '5d3c979ddcbc4c06006c795ee7864a71dc5187b351b14db4953721017b211e086e35cfae8a3eba915aa4a4d97b2c76a90b203618c141a293e4c2cb33a78c33a3b64331bf1f12d71699b6c28164ec95810ee22b9ccabd38c71e3ebbfa6e3196', 'tag': '521d6a9fe5a6d39dd500feea2c1a7f65', 'iv': 'b7046258da2d419d7565cda2'}

Let’s login again to see if the same IV will be generated:

Username: ghost
Password: ghost
Logged in as ghost! Here is the token:
{'enc': 'b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '77b37533f95ca5144ff4facac9d63b29', 'iv': 'eac4ad3a55efed2c67c64437'}

Completely different IV.

The Transfer/pay option shows that I have no money. It asks for my token before executing the transfer.

Token: {'enc': 'b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '77b37533f95ca5144ff4facac9d63b29', 'iv': 'eac4ad3a55efed2c67c64437'}
Huh? you have no money and want the flag? -.-

Let’s change one bit of the first byte to see if the script is checking the GCM tag:

Token: {'enc': 'b9de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '77b37533f95ca5144ff4facac9d63b29', 'iv': 'eac4ad3a55efed2c67c64437'}
Traceback (most recent call last):
  File "gcm.py", line 79, in <module>
    menu()
  File "gcm.py", line 71, in menu
    pay()
  File "gcm.py", line 53, in pay
    account = ast.literal_eval(decryptor.update(enc) + decryptor.finalize_with_tag(tag))
  File "/usr/lib/python2.7/dist-packages/cryptography/hazmat/primitives/ciphers/base.py", line 206, in finalize_with_tag    data = self._ctx.finalize_with_tag(tag)
  File "/usr/lib/python2.7/dist-packages/cryptography/hazmat/backends/openssl/ciphers.py", line 213, in finalize_with_tag
    return self.finalize()
  File "/usr/lib/python2.7/dist-packages/cryptography/hazmat/backends/openssl/ciphers.py", line 164, in finalize
    raise InvalidTag
cryptography.exceptions.InvalidTag

Yeap, it’s checking.

Studying the script

Since the script has been provided, let’s study each line.

The key and the flag are retrieved from the server files.

key = open("secret").read().strip()
flag = open("flag.txt").read().strip()

Here is the get_token method. The IV is indeed randomly generated and the key is used in the AES-GCM encryption.

def get_token(username, admin):
    iv = os.urandom(12)
    
    encryptor = Cipher(
        algorithms.AES(key),
        modes.GCM(iv),
        backend=default_backend()
    ).encryptor()

If admin’s permission is Y (YES) I will get 1000 set to my balance. If not, I will receive 0. Then, an object containing the username, balance, the secret key and the admin permission is cast to string and encrypted afterwards.

    balance = 1000 if admin == "Y" else 0
    account = {"username": username, "balance": balance, "secret": key, "admin": admin}
    enc = encryptor.update(str(account)) + encryptor.finalize()
    token = {"iv": iv.encode("hex"), "enc": enc.encode("hex"), "tag": encryptor.tag.encode("hex")}
    return str(token)

Now the login method.

The password is only checked when the chosen username is admin. Otherwise it’s ignored. So let’s ignore the password for now.

def login():
    username = raw_input("Username: ")
    password = raw_input("Password: ")
    if username == "admin":
        if password == key:
            token = get_token(username, "Y")
            print("Logged in as Lord of Money! Here is the token: %s" % (token))
        else:
            print("Invalid credentials!")

If the username is different from admin, a token will be generated using the get_token method, changing the admin permission to N:

    else:
        token = get_token(username, "N")
        print("Logged in as %s! Here is the token:\n%s" % (username, token))

Now the pay method.

It will decrypt the token read from the input:

def pay():
    token = ast.literal_eval(raw_input("Token: "))
    iv = token["iv"].decode("hex")
    enc = token["enc"].decode("hex")
    tag = token["tag"].decode("hex")

    decryptor = Cipher(
        algorithms.AES(key),
        modes.GCM(iv),
        backend=default_backend()
    ).decryptor()
    account = ast.literal_eval(decryptor.update(enc) + decryptor.finalize_with_tag(tag))    

There is a check here. If the balance is ` 1000 OR the admin permission is different from N` the flag will be printed. At first I thought I would need to change the balance to get the flag, but just changing the admin permission was enough.

if account["balance"] != 1000 and account["admin"] == "N":
    print("Huh? you have no money and want the flag? -.-")
else:
    print(flag)

The remaining lines are the menu, which requires no explanation.

The script is very well implemented, with a random IV for every plaintext and the tag being validated in every decryption.

So, how to bypass this well written netcat bank?

A wild CVE appears

Maybe there is some vulnerability here. So let’s search for python gcm vulnerability.

python gcm vulnerability searched on Google

Ok, top result. This must be important.

A flaw was found in python-cryptography versions between >=1.9.0 and <2.3. The finalize_with_tag API did not enforce a minimum tag length. If a user did not validate the input length prior to passing it to finalize_with_tag an attacker could craft an invalid payload with a shortened tag (e.g. 1 byte) such that they would have a 1 in 256 chance of passing the MAC check. GCM tag forgeries can cause key leakage.

Source: https://nvd.nist.gov/vuln/detail/CVE-2018-10903

Ok, this is QUITE IMPORTANT! The CVE-2018-10903 allows me to brute force the tag in a feasible timespan. A normal brute force, in this system, would take 2^128 tries and with the CVE my number of maximum tries drops to 2^8, which is nothing to a modern computer.

Everything made sense now. I could use p1 xor p2 = c1 xor c2 to generate a new ciphertext (with the admin permission set to Y) and easily brute force the tag.

First, I need to understand how my p1 is generated. I know that my username is ghost, my balance is 0 and my admin permission is N. I don’t know the secret, so let’s call it '00' for know.

rasknikov@kali:~$ python
Python 2.7.15+ (default, Aug 31 2018, 11:56:52)
[GCC 8.2.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> str({"username": "ghost", "balance": 0, "secret": "00", "admin": "N"})
"{'username': 'ghost', 'admin': 'N', 'secret': '00', 'balance': 0}"
>>>

Here is the first version of my p1:

{'username': 'ghost', 'admin': 'N', 'secret': '00', 'balance': 0}`.

I know that my ciphertext should have the same size of my plaintext. As I’m using the token below:

{'enc': 'b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '77b37533f95ca5144ff4facac9d63b29', 'iv': 'eac4ad3a55efed2c67c64437'}

Let’s count p1 and c1:

rasknikov@kali:~$ echo -n "b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b" | xxd -p -r | wc -c
95

rasknikov@kali:~$ echo -n "{'username': 'ghost', 'admin': 'N', 'secret': '00', 'balance': 0}" | wc -c
65

My c1 is 95 bytes long and my p1 is 65 bytes long. The difference is 30 bytes. What is missing? The secret, of course! I just used two bytes in my p1, so my secret must be 32 bytes long. 32 characters in hex are 16 real bytes, and 16 bytes are 128 bits. It’s a 128 bit AES key.

Let’s generate my p1 again:

rasknikov@kali:~$ python
Python 2.7.15+ (default, Aug 31 2018, 11:56:52)
[GCC 8.2.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> str({"username": "ghost", "balance": 0, "secret": "00000000000000000000000000000000", "admin": "N"})
"{'username': 'ghost', 'admin': 'N', 'secret': '00000000000000000000000000000000', 'balance': 0}"

And count:

rasknikov@kali:~$ echo -n "{'username': 'ghost', 'admin': 'N', 'secret': '00000000000000000000000000000000', 'balance': 0}" | wc -c
95

Now my len(p1) == len(c1)!

p1 = {'username': 'ghost', 'admin': 'N', 'secret': '00000000000000000000000000000000', 'balance': 0}
p2 = ?
c1 = b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b
c2 = ?

My goal is to generate a c2. For that I need a p2. I just need to change the admin permission, so my p2 becomes

{'username': 'ghost', 'admin': 'Y', 'secret': '00000000000000000000000000000000', 'balance': 0}

Wait a minute. How do you know that the secret is 00000000000000000000000000000000? It could be anything!

Yes! The key could be anything, but the same key is used inside the plaintext, so inside the p1 xor p2 = c1 xor c2 attack the key is nullified, because a xor a = 0, and 0 xor b = b.

WHAT?

a = 4141414141FFFFFFFFFF4141414141
b = 4242424242FFFFFFFFFF4242424242
a xor b = 030303030300000000000303030303

---

a = 4141414141AAAAAAAAAA4141414141
b = 4242424242AAAAAAAAAA4242424242
a xor b = 030303030300000000000303030303

See? I changed the middle bytes of the inputs, but the output remained the same! This is like that because the same bytes are in the same place, so it is important the secret key be in the same place. Fortunately, when calling str(obj) in Python a string where the secret is always at the same position will be generated (based on the script).

Now I have:

p1 = {'username': 'ghost', 'admin': 'N', 'secret': '00000000000000000000000000000000', 'balance': 0}
p2 = {'username': 'ghost', 'admin': 'Y', 'secret': '00000000000000000000000000000000', 'balance': 0}
c1 = b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b
c2 = ?

Now I can easily calculate my c2:

c2 = "{'username': 'ghost', 'admin': 'N', 'secret': '00000000000000000000000000000000', 'balance': 0}" xor "{'username': 'ghost', 'admin': 'Y', 'secret': '00000000000000000000000000000000', 'balance': 0}" xor "b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c5f9f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b"

c2 = b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c489f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b

I used CyberChef for this calc, as you can see here

Here you can see that just one byte has been changed. The byte that gave me the flag. :)

Diff between the two ciphertexts

Here is my final template token:

{'enc': 'b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c489f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '00', 'iv': 'eac4ad3a55efed2c67c64437'}

I kept the same iv so the p1 xor p2 = c1 xor c2 could work.

I just need to brute force the tag now.

The brute force script

from pwn import *

token = "{'enc': 'b8de1e2e131153ae6b456a70f192b834e18db5ba1612728df5f3aeb304eb313c489f7049e7a1ac8f4175bb7d29ec20321bc15499b947d898f10fe000946d475a17500586217fc2d8627278396806996d35ca57da8a61b0f6fedc675a68997b', 'tag': '%0.2X', 'iv': 'eac4ad3a55efed2c67c64437'}\n"

for i in range(0, 256):
    r = remote('200.136.252.51', 5555)
    r.recvuntil('Exit\n')
    r.send('2\n')
    r.recv(1024)
    print "%0.2X" % i
    r.send(token % i)
    print r.recv(2048)
    print r.recv(2048)	
    r.close()

I did not try to get the vulnerable library. I was so confident that my script would work that I ran it directly in production.

And it fortunately worked.

After some tries, the flag was spitted to my screen. As you could see in the script, I had to watch the console until I found something different from Invalid Tag. Something different appeared, I cancelled the script and the beautiful flag was there.

Flag: CTF-BR{__CVE-2018-10903_ok_I_got_it}

Thanks

Thank you pedroysb. Very interesting challenge. It’s always nice to take on challenges with recents CVEs! Thank you Marzano for the english and crypto review. :D

Cryptography , Capture the Flag , Writeup