Write up In CTF - Giant XOR

inctf - GiantXOR

Deskripsi Soal

Diberikan source code encrypt.py dan ciphertext.txt dalam hexadecimal encode. Berikut isi dari kedua file tersebut.
encrypt.py

from os import urandom
import string

key = ""

def get_key(keylength):
    global key
    c = urandom(1)
    if len(key)!=keylength:
        if c in string.printable and c not in string.whitespace:
            key += c
            get_key(keylength)
        else:
            get_key(keylength)

def multiplyKey(pt, k):
    while len(k) < len(pt):
        k += k
    k = k[:len(pt)]
    return k

def encrypt(plaintext, k):
    ciphertext = ""
    plaintext = plaintext.encode("base64")
    k = multiplyKey(plaintext, k)
    assert len(k) == len(plaintext)
    for i in range(len(plaintext)):
        ciphertext += chr(ord(plaintext[i]) ^ ord(k[i]))
    return ciphertext.encode("hex")

secret_flag = open("plaintext.txt",'r').read().strip()
keylength = int(open("keylength.txt",'r').read().strip())

get_key(keylength)

print "key: ", key
print "keylength: ", keylength

ciphertext = encrypt(secret_flag, key)

object1 = open("ciphertext.txt",'w').write(ciphertext)

ciphertext

6e19223f204b31183e333f005c122d37264a350e3e3c2808672436250b3f3d1b2e2c151c671d553e182b4713262c3f045c1d553e0b3f391c1449385d7309223c20153d022d3c011a673322394822242e0118003a5a1333123b222b361b22353d5110231230222b1f102c28566e03281a2e21240c041e3e2d491337022e313b26181a3a5a532919122a31343e071f2e2d4928531a2e31342607713702673a3963140b1737001c0f5c742d3a172e133a331b4b3d167f090418210b3a31390d0f025933390810023a334e0e2427733c021818081119141c0928552629170c172a230f08373808246a0a113d142645421b357e0853327132013d2439243565000c190514093d3f171b0b6503070a2f001b2e0d140a0e6a7f0a340522442d1a3d17356913500870290b2e31435d0d7a32061e70101f7e2f495d5f6730263a1a4b39042d49055f6d79506d48

Solusi

Jika kita lihat dari encrypt.py, program mengenkrip plaintext dengan alur berikut.

1. Plaintext dijadikan base64 terlebih dahulu
2. Hasil dari base64 plain, dilakukan multiple xor dengan key printable string dari urandom dengan panjang key yang tidak diketahui.

Kesulitan dari soal ini adalah plaintext diubah menjadi base64 sehingga kita tidak dapat menggunakan xortool secara langsung untuk mendecrypt ciphertext dan mencari key. Karena itu kita akan mencoba memecahkannya secara manual.
Untuk mendekript ini, kita harus mencari panjang key nya terlebih dahulu. Panjang key dapat diketahui dengan menggunakan hamming distance. Berikut script hamming distance yang digunakan untuk mencari length key.

#! /usr/bin/env python

from binascii import b2a_hex

def hamming_distance(A, B):
  X = int(b2a_hex(A),16) ^ int(b2a_hex(B),16)
  return count_binary_ones(X)

def count_binary_ones(X):
  ret = 0
  while X != 0:
    ret = ret + 1
    X &= X-1  
  return ret

def normalized_hamming_distance (A, length): # Takes adjacent groups of 'length' length and finds avg hamming dist and normalizes it
  ham_sum = 0
  for i in range(len(A)/length - 1):
    ham_sum += hamming_distance(A[(i+0)*length:(i+1)*length], A[(i+1)*length:(i+2)*length])
  ham_avg = (1.0 * ham_sum) / (len(A)/length - 1)
  norm_ham = ham_avg / length
  return norm_ham

def test():
  if hamming_distance("this is a test","wokka wokka!!!") == 37:
    print "Hamming Distance tests pass"
  if normalized_hamming_distance("this is a testwokka wokka!!!",14) == 37.0/14:
    print "Normalized Hamming Distance tests pass"


data = ""
filename = 'ciphertext.txt'
filename = open(filename).read()
data = filename.decode('hex')
test()
best_hamming_dist = float('inf')
for KEYSIZE in range(2,80):
  ham = normalized_hamming_distance(data,KEYSIZE)
  if ham < best_hamming_dist:
    best_hamming_dist = ham
    best_keysize = KEYSIZE

KEYSIZE = best_keysize

print "[#] Inferred KEYSIZE = " + str(KEYSIZE)

Hasil

a@a-l ~/CTF/inctf/giantxor $ python hd.py 
Hamming Distance tests pass
Normalized Hamming Distance tests pass
[#] Inferred KEYSIZE = 12

Dari script didapat panjang key adalah 12 karakter. Ide selanjut nya kita harus menebak key dari ciphertext yang sudah ada. Kita tidak dapat menggunakan frequency english letter pada plaintext, karena string di encode menggunakan base64. Kita coba cara lain, yaitu dengan melakukan bruteforce, perhuruf pada key. Berikut alur bruteforce tersebut.

misal 
key = "sesuatu" 
cipher = cipher

brute key ke 0. xor key ke 0 dengan semua cipher[0 + j*12]
kalo semua hasil nya masuk ke base64 tambah key

brute key ke i. xor key ke i dengan semua cipher[i + j*12]
kalo semua hasil nya masuk ke base64 tambah key.

lakukan sampai semua key memenuhi syarat tersebut

Menggunakan rekursif sederhana key dapat diketahui. Jika kita sudah mendapatkan key. Lakukan multiple xor dengan cipher text. dan didapatkan plaintext.
Berikut script untuk mencari kunci sekaligus mendecrypt ciphertext

import string 
from base64 import *
base64str = string.ascii_letters + string.digits + "=+/" + "\n"
prstring = string.printable

def multiplexor(cipher, key):
 hasil = ""
 for i in range(len(cipher)):
  hasil += chr( ord(cipher[i]) ^ ord(key[i % 12]))
 return hasil

def valid(key_index, ch): 
 # Cek semua hasil xor jika ada yang bukan merupakan string base64 return 0
 for index in range(key_index, len(data), 12):
  if( chr(ord(data[index]) ^ ord(ch)) not in base64str ):
   return 0
 return 1 

def findkey_rec(data, block, level, part):
 if (level == part):

  for ch in prstring:
   if valid(block + level, ch) :
    key.append(ch)
    part_key = ''.join(key)
    global password
    password += part_key
    return part_key
    # Password ketemu
 for ch in prstring:
  if valid(block + level, ch) :
   key.append(ch)
   findkey_rec(data, block, level + 1, part)
   key.pop()


data = open("ciphertext.txt").read()
data = data.decode('hex')

key = []
password = ""
part = 6

# Part dilakukan untuk mendapatkan key perblock.

for block in range(0, 12, part+1):
 key = []
 findkey_rec(data, block, 0, part) 

hasil = multiplexor(data, password)
print "Base64 plain :\n\n%s" % hasil

print "Plain : %s" % b64decode(hasil)

Berikut hasil dekripsi ciphertext

Base64 plain :

SSBob3BlIHRoaXMgd2FzIGEgZnVuIGNoYWxsZW5nZS4gQWRkaW5nIGJhc2U2NCBlbmNvZGluZyBi
ZWZvcmUgYSByZXBlYXRlZCBrZXkgWE9SIHJlYWxseSBtYWRlIHRoaW5ncyBhIGJpdCBtb3JlIGRp
ZmZpY3VsdCwgb3IgZGlkIGl0PyBCdHcsIENvbmdyYXRzIG9uIHNvbHZpbmcgdGhlIGNoYWxsZW5n
ZSEgR29vZCB3b3JrISBIZXJlIGlzIHlvdXIgZmxhZzogaW5jdGZ7YmFzZTY0X2QxZF80bGxfN2hl
X200ZzFjX3JpZ2h0P30=

Plain : I hope this was a fun challenge. Adding base64 encoding before a repeated key XOR really made things a bit more difficult, or did it? Btw, Congrats on solving the challenge! Good work! Here is your flag: inctf{base64_d1d_4ll_7he_m4g1c_right?}

FLAG : inctf{base64_d1d_4ll_7he_m4g1c_right?}