주어진 평문, 암호문을 이용하여 사용된 두개의 키를 알아내는 과제
1. 암호문은 DES(ECB), AES-128(CBC)를 이용하여 암호화됨
2. 계산시간의 축약을 위해, password list가 주어진다. 리스트에는 md5 hash 값과, word가 한라인에 공백으로 구분되어 기재됨
2-1. 리스트는 약 18만 5천여개의 hash로 이루어져있다.
3. DES CBC이므로 8바이트 key를 사용해 암호화를 해야하므로, 주어진 hash에서 가장 앞글자 8자리를 사용할것
4. AES-128은 주어진 hash를 모두 사용해 암호화할것
외국사람들이 내 블로그 볼일이 있겠나 싶어 그냥 한글로 정리한다.
처음에 이 과제를 받고 어떻게 해야하나 생각을 해봤다.
평문과 암호화된 텍스트, 그리고 심지어 암호화 방법도 주어졌으니
암호화를 두번하고, 나오는 cipher text를 주어진 암호문과 비교 하는방법을 생각했다.
당연히, NP-hard Problem 이라고 생각했다. 그 외의 방법이 있나.. 싶었는데 내가 멍청이란걸 깨닫기전엔...
그래도 모르니 일단 코드 공유를 한다.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import os,sys,timeit,string,base64
from Crypto.Cipher import AES,DES
__author__ = "Song Myeong-Uk"
__date__ = "2015.05.27"
#global value
md5_keys = {}
target_plaintext = ""
encrypted_plaintext = ""
start_time = timeit.default_timer() #when program start
#@func: download_data
#@desc: If there is no md5 hash passwords, download it
def download_data():
print "[-] passwords.txt not found! downloading now..."
url = "http://www.ece.ubc.ca/~hyoung/passwords.txt"
urllib.urlretrieve(url, 'passwords.txt')
print "[-] passwords.txt download complete"
#@func: save_input_data
#@desc: Insert input data to global variable
def save_input_data():
global target_plaintext
global encrypted_plaintext
i = 0
with open('PlaintextCiphertext.txt', 'r') as f:
i = 0
for line in f:
line = line.replace("\r\n","").replace("\n","")
if i is 0:
target_plaintext = line
elif i is 1:
encrypted_plaintext = line
i = i + 1
print "[-] Done!"
#@func: download_data
#@desc: To faster calculate. insert file data in memory instead IO system
def md5_to_memory():
global md5_keys
with open('passwords.txt', 'r') as f:
for line in f:
key_hash = line.split(" ")[0]
password = line.split(" ")[1].replace("\r\n","").replace("\n","")
md5_keys[key_hash] = password
print "[-] Done!"
#@func: DES_encrypt
#@param hash: first selected key of text file
#@desc: Simple DES(ECB) encryptor. return encrypted text
def DES_encrypt(hash):
global target_plaintext
des = DES.new(hash[:8], DES.MODE_ECB)
text = pad(target_plaintext,8)
cipher_text = des.encrypt(text)
return cipher_text
#@func: AES_encrypt
#@param DESed: DES encrypted text
#@param hash: Second selected key of text file
#@desc: Simple AES(CBC) Encryptor. return encoded base64 text
def AES_encrypt(DESed,hash):
global target_plaintext
#128 bits = 16bytes
mode = AES.MODE_CBC
encryptor = AES.new(hash, mode, IV='\x00'*16)
text = pad(DESed,16)
ciphertext = encryptor.encrypt(text)
return ciphertext.encode('base64')
def s2b(x):
return ''.join(c.encode('hex') for c in x)
#@func: decrypt
#@param enc: encrpyted text
#@param k1: First selected key of text file
#@param k2: First selected key of text file
#@desc: just test case
def decrypt(enc,k1,k2):
# enc = "W7n515icc+1dW5+82CYgPOGyFqgaFLA0FTCgB/jw1DZBeKUUF2h4z7yRWb03ZIeE"
# k1 = "0001245350b5eb0a1548fc6d27d3b4d1"
# k2 = "00009965"
text = enc
dec = AES.new(k1, AES.MODE_CBC, IV='\x00'*16)
des = DES.new(k2[:8], DES.MODE_ECB)
return unpad(des.decrypt(pad(unpad(dec.decrypt(text.decode('base64'))),8)))
#@func: pad
#@param x: text
#@param b: limit
#@desc: add null character to text untill b
def pad(x,b):
pad1 = lambda s: s + (b - len(s) % b) * chr(b - len(s) % b)
return pad1(x)
def unpad(x):
try:
unpad1 = lambda s : s[0:-ord(s[-1])]
return unpad1(x)
except Exception,err:
return x
#@func: progress
#@desc: execute calc when it ready
def progress():
global md5_keys
try:
for hash in md5_keys:
for hash2 in md5_keys:
DESed_text = DES_encrypt(hash)
if encrypted_plaintext is AES_encrypt(DESed_text,hash2):
print "[-] find keys ... !!"
print md5_keys[hash]
print md5_keys[hash2]
raise BreakAllTheLoops()
else:
#debug to print. you can pass it
#pass
print "[-] Trying key : {} - {},{}".format(AES_encrypt(DESed_text,hash2),md5_keys[hash],md5_keys[hash2]).replace("\r\n","").replace("\n","")
print "[-] Can not find keys ... "
except BreakAllTheLoops:
pass
# for hash in md5_keys:
# for hash2 in md5_keys:
# if target_plaintext is decrypt(encrypted_plaintext,hash2,hash):
# print hash
# print hash2
# main execution
if __name__ == "__main__":
print "[+] starting {}...".format(os.path.basename(__file__))
# check if data file exists
#check input file exists
cipher_exists = os.path.isfile('PlaintextCiphertext.txt')
print "[+] checking input file: PlaintextCiphertext.txt"
if not cipher_exists:
print "[+] PlaintextCiphertext.txt not found!"
sys.exit()
else:
print "[-] Done!"
print "[+] checking password data: passwords.txt"
txt_exists = os.path.isfile('passwords.txt')
if not txt_exists:
download_data()
else:
print "[-] Done!"
print "[+] Process init ... [1/2]"
save_input_data()
print "[+] Process init ... [2/2]"
md5_to_memory()
print "[+] Start processing ... "
print "[-] Target plaintext : {}".format(target_plaintext)
print "[-] Target Encrpyted key : {}".format(encrypted_plaintext)
progress()
stop_time = timeit.default_timer() #when program end
print "Done!!"
print "Program Run Time : " + str(stop_time - start_time)
코드는 단순하다. 먼저 DES를 하고 AES를 해서 최종
총 키가 18만개니까, 최악의 경우를 고려하면 O(n^2) 가 되는 방법이다.
1초에 30개씩 처리한다고 해도 며칠은 돌려야된다.. 잘될리가 없었다. 속도문제도 그렇고 퍼포먼스가 나오지 않았다.
이대로는 안되겠다 생각했다. 문제를 다시 읽어서 교수님이 원하는게 뭔가 생각을 했다.
왜 하필이면 두번만했을까, 왜 더블 AES도 아니고 다른 암호화를 썼을까
처음에 접근했어야 하는 문제를 개삽질 한번하고 다시 생각해보게 되었다.
그 과정에 Double DES를 생각하게 되었다.
Double DES 에 대한건 영상을 하나 첨부한다.
요점만 말하자면, 첫번째 암호화 한 결과와 암호화된 값을 복호화함으로서 생기는 중간값이 매치가 되야 정상 프로세스가 진행되게 된다. 즉, 중간값을 알아내기 위한 MITM(Meet in the middle) 공격이 가능해진다. (기존의 MITM이랑은 좀 다르다)
따라서, AES는 decrpyt 하고 DES는 encrpyt 하면 반드시 매칭되는 중간 값이 나오게 된다.
속도도 O(nx2)가 맥시멈으로서 제곱과는 비교가 되지 않는건 물론이고...
#!/usr/bin/env python # -*- coding: utf-8 -*- import os, sys, time, base64, string, urllib from Crypto.Cipher import AES, DES from Crypto.Hash import MD5 # author information __author__ = "Song Myeong-Uk" __email__ = "mwsong@imtl.skku.ac.kr" __date__ = "2015.05.27" # constants DATA_FILE_URL = "http://www.ece.ubc.ca/~hyoung/passwords.txt" DATA_FILE_NAME = "passwords.txt" INPUT_FILE_NAME = "PlaintextCiphertext.txt" OUTPUT_FILE_NAME = "keys.txt" # global variables md5_keys = {} target_plaintext = "" encrypted_plaintext = "" DES_keys = {} AES_keys = {} # pad value with given block size: 16 def pad(x): BLOCK_SIZE = 16 if len(x) == BLOCK_SIZE: return x c = (len(x) // BLOCK_SIZE) + 1 c *= BLOCK_SIZE return "{:\x00<{l}}".format(x, l=c) # returns value of md5 for given value def hashMD5 (v): m = MD5.new(v) return m.digest() # download base md5 hash password list from url def download_data(): global DATA_FILE_URL, DATA_FILE_NAME print "[-] {} not found! downloading now...".format(DATA_FILE_NAME) urllib.urlretrieve(DATA_FILE_URL, DATA_FILE_NAME) print "[-] {} download complete".format(DATA_FILE_NAME) # calculate run time def print_time(t): diff = time.time() - t print "[*] total run time: {:.4f} seconds".format(diff) # load data from input file def save_input_data(): global target_plaintext, encrypted_plaintext global INPUT_FILE_NAME with open(INPUT_FILE_NAME, 'r') as f: data = [ l.strip() for l in f.readlines() ] target_plaintext = data[0] encrypted_plaintext = data[1] # load md5 data into dictionary def md5_to_memory(): global md5_keys global DATA_FILE_NAME with open(DATA_FILE_NAME, 'r') as f: data = [ l.strip() for l in f.readlines() ] for line in data: line = line.split(' ') md5_keys[line[0]] = line[1] # encrypts plaintext with DES using different keys def plaintext_to_des(): global md5_keys, DES_keys for k in md5_keys: KEY = DES_encrypt(hashMD5(md5_keys[k])[:8]).encode('hex')[:64] DES_keys[KEY] = md5_keys[k] # decrypts ciphertext with AES128 using different keys def enc_to_decrypt(): global encrypted_plaintext, md5_keys, AES_keys, DES_keys for k in md5_keys: KEY = AES_decrypt(encrypted_plaintext, hashMD5(md5_keys[k])).encode('hex')[:64] AES_keys[KEY] = md5_keys[k] try: if DES_keys[KEY]: print "[!] solution key found" print "[-] key1: {}".format(DES_keys[KEY]) print "[-] key2: {}".format(AES_keys[KEY]) write_key(DES_keys[KEY], AES_keys[KEY]) else: print "[!] solution key not found" except Exception, err: pass # writes found key to file def write_key(k1, k2): global OUTPUT_FILE_NAME print "[+] writing key file...", with open(OUTPUT_FILE_NAME, 'wb') as f: f.write(k1 + '\n' + k2) print "done" # DES-ECB encrypt with given key def DES_encrypt(key): global target_plaintext return DES.new(key, DES.MODE_ECB).encrypt(pad(target_plaintext)) # AES-CBC decrypt text with given key def AES_decrypt(text, key): return AES.new(key, AES.MODE_CBC, IV='\x00'*16).decrypt(base64.b64decode(text)) # main execution block def main(): print "[+] starting {}...".format(os.path.basename(__file__)) # time function execution start_time = time.time() # check if base data file exists txt_exists = os.path.isfile(DATA_FILE_NAME) print "[+] checking password data: {}".format(DATA_FILE_NAME) if not txt_exists: download_data() # check if input file exists cipher_exists = os.path.isfile(INPUT_FILE_NAME) print "[+] checking input file: {}".format(INPUT_FILE_NAME) if not cipher_exists: print "[!] {} not found! terminating...".format(INPUT_FILE_NAME) print_time(start_time) sys.exit() # load input data print "[+] loading input file data..." save_input_data() # load md5 to memory print "[+] preparing md5 dictionary..." md5_to_memory() # DES encrypt print "[+] processing with DES... [1/2]" plaintext_to_des() # AES decrypt print "[+] processing with AES... [2/2]" enc_to_decrypt() # time execution print_time(start_time) if __name__ == "__main__": main()
7초만에 프로세스는 끝난게 된다.
여러 다른 어프로치를 했봤으나, 실질적인 소득은 위 두가지 코드가 전부이고, 따로 레퍼런스랄것도 이번에 없다.
Meet-in-the-Middle 공격을 잘 이해만 한다면 쉽게 구현할 수 있다.
최근에는 Single DES 및 Double DES는 아예 쓰이지도 않고, 중간자 공격에 대비해 최소 Triple DES를 사용하고,
이마저도 AES가 표준이 됨으로서 DES가 많이 사용되고 있지는 않지만, 암호화를 하려는 사람들은 이런 Known Ciphertext Attack 을 항상 염두에 둬야할것이다.
Reference
https://www.youtube.com/watch?v=vROZGQ9XLe8
