Making a Crypto Challenge

- 5 mins read

Planning

I was asked by a friend to make a cryptography CTF challenge for her partner, who’s an entusiastic CTF player, as an anniversary present. I know that he’s not an expert in crypto, so I had to keep it simple. Good thing I’m also not that versed in the subject. The flag in the challenge was supposed to be a plane ticket for a vacation.

My initial thoughts were:

  • have layers of different encryptions/encodings
  • use RSA
  • use some sort of threshold cryptography (because I find the concept fascinating)

To quickly mention, threshold cryptography is an cryptosystem where decrypting a ciphertext takes k out of n total key shares to perform. So decryption or signing can only be done only if the threshold of k keyshares is met. Mostly CAs, the military and government entities have been using it.

After playing with the ideas I settled on using a Python threshold cryptography library with which I could generate 5 keyshares. Each keyshare will then be “given” to a different person who has also done their own “encryption” on it. Using this approach I could combine typical beginner friendly crypto challenges together into one challenge.

The Grand Heist

You can't believe how much trouble I've gone through to get that damned secret file open.

When I finally managed to get my hands on it I found it to be encrypted with a key that's ALSO! encrypted. And to decrypt the key I need not 1, not 2, but AT LEAST 3 (!!!) keys from the 5 shareholders!!! INSANE

They really made my work hard with that. At least I managed to steal the code used for encryption and decryption when I was in their systems. (go.py) So there I went and hacked each shareholder one by one and got their keyshares.

But I'll be damned! Each bastard has their secret encrypted and each in a different way!!!

I guess I'll just have to crack my knuckles and get to work again...

So the player would be given an encrypted file, a Python script that can be used to encrypt and decrypt files using threshold cryptography, and a driectory with five different sub-challenges which each give the player a key shard. Each challenge would have their own flavor text and task to solve.

For the five shards I used these methods:

  • Password protected zip file that has to be brute-forced
  • A substitution cipher
  • RSA encryption where n,d and c are given
  • An encoding that I developed, that is very guessy and that no one should use
  • One byte XOR

The Code

Encrypting the entire plane ticket PDF was scrapped during development because of a strange issue with the threshod crypto library. Whenever I tried to encrypt a file that’s size was above a couple of kilobytes it would say that it had successfully encrypted the file (and split the key into 5 fragments) but later during the decryption process it would cause an error saying that the key length is invalid. Since the input file size seemed to be the issue, I decided to apply a workaround where I used a long password (a key) to XOR the plane ticket file and then used the threshold crypto script to encrypt that passphrase.

In the end, the code looked like this:

# encryption-decryption.py 

import threshold_crypto as tc
import Crypto

THRESHOLD = 3
PARTICIPANTS = 5

curve_params = tc.CurveParameters()
thresh_params = tc.ThresholdParameters(THRESHOLD, PARTICIPANTS)

def decrypt(encrypted_data_obj):

  print("Please insert keyshare's X and Y values in decimal format, comma separated (hit enter to skip):")
  
  participant_keys = []

  for i in range(1, PARTICIPANTS + 1):
    # For example when (X=123456789 Y=987654321) and (X=234567890 Y=876543210) : 
    # 123456789,987654321 
    # 234567890,876543210
    inp = input("= ")
    
    if inp != '':
      id, key = inp.split(",")
      keyshare = tc.KeyShare(int(id), int(key), curve_params)
      print(keyshare)
      participant_keys.append(keyshare)
    
  partial_decryptions = []
  for participant_key in participant_keys:
    partial_decryption = tc.compute_partial_decryption(encrypted_data_obj, participant_key)
    partial_decryptions.append(partial_decryption)
  
  decrypted_data = tc.decrypt_message(partial_decryptions, encrypted_data_obj, thresh_params)

  return decrypted_data

def encrypt():
  pub_key, key_shares = tc.create_public_key_and_shares_centralized(curve_params, thresh_params)
  
  KEYPHRASE = open("KEYPHRASE", "rb").read()
  FLAG = open("FLAG", "rb").read()

  encrypted_flag = xor(FLAG, KEYPHRASE)
  encrypted_keyphrase = tc.encrypt_message(KEYPHRASE.decode("utf-8"), pub_key)

  return encrypted_flag, encrypted_keyphrase, pub_key, key_shares

def read_enc_file(encrypted_file_name):
  with open(encrypted_file_name, "rb") as f:
    data = f.read().split(b"\n")
    
    C1x, C1y = data[0].split(b";")
    C2x, C2y = data[1].split(b";")
    binary_data = data[2]

    C1 = Crypto.PublicKey.ECC.EccPoint(int(C1x), int(C1y))
    C2 = Crypto.PublicKey.ECC.EccPoint(int(C2x), int(C2y))

    return tc.EncryptedMessage(C1, C2, binary_data)

def write_enc_file(file_name, encrypted_message_obj):
  
  with open(file_name, "wb") as f:
    C1x, C1y = encrypted_message_obj.C1.x.__str__().encode("utf-8"), encrypted_message_obj.C1.y.__str__().encode("utf-8")
    C2x, C2y = encrypted_message_obj.C2.x.__str__().encode("utf-8"), encrypted_message_obj.C2.y.__str__().encode("utf-8")
    binary_data = encrypted_message_obj.ciphertext

    f.write(C1x + b";" + C1y + b"\n")
    f.write(C2x + b";" + C2y + b"\n")
    f.write(binary_data)
  
  return 0

def xor(file, key):
  # Assuming the file is larger than the key and both arguments are type bytearray
  repeating_key = key * (len(file) // len(key)) + key[:len(file) % len(key)]
  
  xord_byte_array = bytearray(len(file))
  for i in range(len(file)):
    xord_byte_array[i] = file[i] ^ repeating_key[i]
  
  return xord_byte_array


# Encryption
# =======================================================
"""
enc_flag, enc_key, pub_key, key_shares = encrypt()

# Save threshold encrypted key
write_enc_file("KEY.enc", enc_key)

# Save XORed flag
open("FLAG.enc", "wb").write(enc_flag)

# Print keyshares
for share in key_shares:
  print(share)
"""
# =======================================================

# Decryption
# =======================================================
enc_flag = open("FLAG.enc", "rb").read()
KEY = decrypt(read_enc_file("KEY.enc"))
print("Successful key decryption!")

FLAG = xor(enc_flag, bytes(KEY, 'utf-8'))

open("FLAG.txt", "wb").write(FLAG)
open("KEY.txt", "w").write(KEY)
# =======================================================

Conclusion

In the end, I’m pretty happy with the result. It’s almost like a mini jeopardy style CTF, because you have to solve small challenges, picking which one you want and then once you have solved at least three, you get your reward.