늘모자란, 개발

Assignment #3
주어진 평문, 암호문을 이용하여 사용된 두개의 키를 알아내는 과제

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 늘모