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)
6e19223f204b31183e333f005c122d37264a350e3e3c2808672436250b3f3d1b2e2c151c671d553e182b4713262c3f045c1d553e0b3f391c1449385d7309223c20153d022d3c011a673322394822242e0118003a5a1333123b222b361b22353d5110231230222b1f102c28566e03281a2e21240c041e3e2d491337022e313b26181a3a5a532919122a31343e071f2e2d4928531a2e31342607713702673a3963140b1737001c0f5c742d3a172e133a331b4b3d167f090418210b3a31390d0f025933390810023a334e0e2427733c021818081119141c0928552629170c172a230f08373808246a0a113d142645421b357e0853327132013d2439243565000c190514093d3f171b0b6503070a2f001b2e0d140a0e6a7f0a340522442d1a3d17356913500870290b2e31435d0d7a32061e70101f7e2f495d5f6730263a1a4b39042d49055f6d79506d48
Solusi
Jika kita lihat dari encrypt.py, program mengenkrip plaintext dengan alur berikut.- Plaintext dijadikan base64 terlebih dahulu
- Hasil dari base64 plain, dilakukan multiple xor dengan key printable string dari urandom dengan panjang key yang tidak diketahui.
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)
a@a-l ~/CTF/inctf/giantxor $ python hd.py
Hamming Distance tests pass
Normalized Hamming Distance tests pass
[#] Inferred KEYSIZE = 12
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
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)
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?}
inctf{base64_d1d_4ll_7he_m4g1c_right?}