2016 Boston Key Party CTF des-ofb Write up

from Crypto.Cipher import DES

f = open('key.txt', 'r')
key_hex = f.readline()[:-1] # discard newline
f.close()
KEY = key_hex.decode("hex")
IV = '13245678'
a = DES.new(KEY, DES.MODE_OFB, IV)

f = open('plaintext1', 'r')
plaintext = f.read()
f.close()

ciphertext = a.encrypt(plaintext)
f = open('ciphertext1', 'w')
f.write(ciphertext)
f.close()

코드를 보면 짧고 간단하게 되어있다.

KEY는 주어지지 않고 IV가 주어진다.

그리고 DES의 OFB모드로 암호화 한다.

 DES의 OFB모드는 위와 같은 암호화, 복호화 과정을 거친다.

OFB모드는 key stream을 만들기 때문에 블록암호인데도 스트림암호같은 느낌이다.

우선 문제에서 IV가 주어졌기 때문에 key를 브루트포싱을 하면 바로 복호화를 할 수 있다.

일단 DES는 브루트포싱에 취약하기 때문에 잘 사용하지 않고, 키는 64bit 즉 8바이트를 가진다.

마지막 한바이트는 패리티 비트로 사용한다.

무튼 지금은 IV가 주어져 있기 때문에 키를 브루트포싱을 해봤다.

하지만 8바이트라도 시간이 오래걸리기 때문에 제한시간 내에 키를 알아내기는 힘들다.

이 문제는 두 가지 방법으로 풀이된다.

첫번째 방법으로는  DES_OFB 모드에서는 암호화된 문자열이 다음 블록을 암호화할때 독립적이기 때문에

홀수블록과 짝수블록은 서로 암호화 되는 연산이 똑같다.

홀수 블록은 key + IV + plaintext 로 암호화가 되고

짝수 블록은 IV + plaintext 로 암호화가 된다.

즉, 각 블록을 IV와 xor된 문자열을 출력하면 홀수블록은 복호화가 안되어있고, 짝수블록은 복호화가 되어있다.

홀수블록은 key + plaintext로 암호화 되어있다.

key를 알아내기는 힘드니 짝수블록의 plaintext를 구글링을 통해 사이에 무엇이 들어가는지 유추하였다.

from Crypto.Cipher import DES
import string

def XOR(a, b) :
    out = ''
    for i in range(len(a)) :
        out += chr(ord(a[i]) ^ ord(b[i]))
    return out

def printable(l):
    return all( i in string.printable for i in l )

ciphertext = open("ciphertext", "rb").read()
IV = '13245678'
plain = []
even = []
odd = []
key = '\x15wi\xb9\xc3=D\x84'
#key = "\x00" * 8

for i in range(0, len(ciphertext), 8) :
    block = ciphertext[i:i+8]
    out = XOR(block, IV)
    if printable(out) :
        even.append(out)
    else :
        out = XOR(key, out)
        odd.append(out)
    plain.append(out)

print even
print odd
print ''.join(plain)

key값과 print값을 계속 수정하며 문제를 풀었고 최종적으로 위의 코드를 통해 문제를 풀었다.

우선 key값을 전혀 모를때 출력을 key를 '\x00'*8로 두고 복호화를 해보면 BKP라는 문자열이 나온다.

따라서 뒤의 3바이트는 CTF라고 생각하고 CTF와 해당 바이트를 XOR하여 key의 앞에 넣었다.

다시 복호화를 해보니 아까보다 조금더 글이 완성되어있었다.

y Orison my sins로 구글링을 해보았다.

쉐익스피어의 햄릿의 내용중에 일치하는 내용이 있었다.

따라서 나머지 5글자를 XOR연산하여 키를 모두 구할 수 있었다.

키를 모두 구한다음 복호화를 다시 진행하니 plaintext가 나타났다.

두번째 방법으로는 DES는 취약한 key가 존재한다.

취약한 키들과 조금 덜취약한 키들이 있는데, 밑에는 심각한 결함은 아니라고한다. ;;

from Crypto.Cipher import DES
import string
import re

f = open('ciphertext', 'rb')
ciphertext = f.read()
f.close()

parity = [ '0101010101010101', 'FEFEFEFEFEFEFEFE', 'E0E0E0E0F1F1F1F1', '1F1F1F1F0E0E0E0E' ]
noparity = [ '0000000000000000', 'FFFFFFFFFFFFFFFF', 'E1E1E1E1F0F0F0F0', '1E1E1E1E0F0F0F0F' ]

parity = [ i.decode('hex') for i in parity ]
noparity = [ i.decode('hex') for i in noparity ]

keylist = [parity, noparity]

IV = '13245678'
for key in keylist :
    for KEY in key :
        a = DES.new(KEY, DES.MODE_OFB, IV)
        plain = a.decrypt(ciphertext)
        print plain

이제 취약한 키들을 가지고 복호화를 해보면 정상적으로 복호화된 문자열이 나타나는 것을 확인할 수 있다.