2016 Boston Key Party CTF ltseorg Write up

문제는 ruby와 python 파일 한개씩 주어진다.

require 'socket'
require 'shellwords'
server = TCPServer.new(9090)

while (connection = server.accept)
	Thread.new(connection) do |conn|
		conn.puts "gimme str 1"
		s1 = conn.gets.chomp
		conn.puts "gimme str 2"
		s2 = conn.gets.chomp
		exec = "python ./tlseorg.py --check #{Shellwords.shellescape s1} #{Shellwords.shellescape s2}"
		out = `#{exec}`
		puts out
		if out == "Success\n"
			conn.puts "FLAG"
		else
			conn.puts "failure"
		end
		conn.close
	end
end

루비언어로 작성된 프로그램은 서버역할을 하며 python 파일을 실행 시키는데 두번째인자로 --check,  3,4 번재 인자로 입력한 값을 전달한다.

그리고 이를 파이썬이 실행시키고 만약 입력한 두 스트링의 해시값이 충돌하면 FLAG를 출력해 준다.

import sys, binascii, os, time
from Crypto.Cipher import AES

def gqq():
	def qqg():gqq();qq(q("20206c7473656f72673a20416d2049206265696e672064657461696e65643f"));qq(q("20206c7473656f72673a20416d2049206672656520746f20676f3f"));qg()
	def qqq():qq(q("6c7473656f72673a204920616d206e6f7420616e73776572696e6720616e79207175657374696f6e7320776974686f7574206d79206c61777965722070726573656e742e"));qg()
	def gqq():time.sleep(1)
	def qg():qqg()
	def q(qq):return binascii.unhexlify(qq)
	def qq(q):print(q)
	def gq():qqg()
	qqq()

# March-15: After 23 tries I think we fixed the issue with the IV.
IV = binascii.unhexlify("696c61686773726c7177767576646968") 

BLOCK_SIZE = 16

key1 = ["00" for x in xrange(32)]; key1[0] = "11";key1 =  binascii.unhexlify("".join(key1))
key2 = ["00" for x in xrange(32)]; key2[0] = "FF";key2 =  binascii.unhexlify("".join(key2))

P = AES.new(key1, AES.MODE_ECB)
Q = AES.new(key2, AES.MODE_ECB)

def pad_msg(msg):
	while not (len(msg) % 16 == 0): msg+="\x00"
	return msg

def xor(str1, str2):
	out = []
	for i in xrange(len(str1)):
		out.append( chr(ord(str1[i])^ord(str2[i])) )
	return "".join(out)

# "Pretty much" Grostl's provably secure compression function assuming ideal ciphers
	# Grostl pseudo-code is: h = P(m + h) + h + Q(m) and this is basically the same thing, right?
	# Ltsorg pseudo-code: h = P(m + h) + m + Q(h)
def compress(m, h): return xor( xor( P.encrypt( xor(m, h) ), m), Q.encrypt(h) ) 

def finalization(m, h): return xor(m, h)[0:14]

def hash(msg):
	msg=pad_msg(msg)
	# groestl's IV was boring 
	h = IV

	for i in xrange(0, len(msg), BLOCK_SIZE):
		m = msg[i: i+BLOCK_SIZE]
		h = compress(m ,h)
	return finalization(m, h)


def check(hashstr1, hashstr2): 
	hash1 = binascii.unhexlify(hashstr1);hash2 = binascii.unhexlify(hashstr2)
	if hashstr1 == hashstr2 or hash1 == hash2: return False 
	elif hash(hash1) == hash(hash2): return True
	return False


def main():
	if len(sys.argv) == 2:
		if sys.argv[1] == "-v": gqq()
		else:
			print "input: "+sys.argv[1]
			print "output: "+binascii.hexlify(hash(binascii.unhexlify(sys.argv[1])))
		return
	elif len(sys.argv) == 3 and (sys.argv[1] == "-v" or sys.argv[2] == "-v"): gqq()
	elif len(sys.argv) == 4 and (sys.argv[1] == "--check"):
			if check(sys.argv[2], sys.argv[3]): print "Success"
			else: print "Failure"
	else:
		print("ltseorg: missing argument")
		print("Usage: ltseorg [OPTION...] [input]")
		print("-v \t Display Software version information")
		print("--check \t Check if two inputs break collision resistance.")

if __name__ == "__main__":
	main() 

파이썬파일인데 gqq 어쩌고 함수들은 왜 있는지는 잘 모르겠는데 내가 풀때는 필요가 없었다.

유심히 봐야할 부분은 이 4개 함수이다.

우선 위에 힌트로 Grostl 해시함수에서 m과 h의 순서를 바꾼것이 보인다.

바로 밑에 compress함수가 변형된 함수인 것을 알 수 있다.

check함수에서 입력값 두개의 해시값이 같아야 True를 리턴해 주는데,

hash함수에서 보면 finalization(m, h)을 리턴해준다.

finalization함수는 xor역할을 하는데 만약 여기서 m과 h가 같아버리면 0을 리턴해준다.

grostl 변형함수와 m과 h가 같아야한다, 이 두개의 조건을 이용해서 문제를 풀 수 있다.

(eP,eQ는 encrypt, dP,dQ는 decrypt)

우선 h0 = IV 이고, 첫번째 입력 값을 m0라 두면, 

h1 = eP(m0+h0) + m0 + eQ(h0) = m0  -  식1

이 식을 한개 만들 수 있다. (m과 h가 같아야하기 때문에)

연산을 해보면, m0에 해당하는 수는 dP(eQ(IV)) + IV 이다.

따라서 첫번째 메시지 m0은 dP(eQ(IV)) + IV 이다.

두번째 메시지는 첫번째 메시지를 기준으로 찾는데,

블록암호 이기때문에, 첫16바이트를 m10, 두번째 16바이트를 m11로 표시했다.

 

h0 = IV

h1 = compress(m10, h0)

h2 = compress(m11, h1)

에서 m11 = h2을 만족하는 m11을 찾으면 된다.

이미 h1은 첫번째를 계산 할때 h1 = compress(m0, h0)로 알고있는 상태이다.

식1에서 m0대신 m11, h0대신 h1을 넣으면 똑같은 방법으로 m11을 알 수 있다.

연산을 해보면 m11은 dP(eQ(h1)) + h1 이다.

이렇게 구해진 m10, m10+m11 값은 해시값으로 0을 리턴 하기 때문에 콜리즌이 발생하게 된다.

import sys, binascii, os, time
from Crypto.Cipher import AES
import time
import socket

IV = binascii.unhexlify("696c61686773726c7177767576646968")
key1 = ["00" for x in xrange(32)];key1[0] = "11";key1 =  binascii.unhexlify("".join(key1))
key2 = ["00" for x in xrange(32)];key2[0] = "FF";key2 =  binascii.unhexlify("".join(key2))

P = AES.new(key1, AES.MODE_ECB)
Q = AES.new(key2, AES.MODE_ECB)

def pad_msg(msg):
	while not (len(msg) % 16 == 0):
		msg+="\x00"
	return msg

def xor(str1, str2):
	out = []
	for i in xrange(len(str1)):
		out.append( chr(ord(str1[i])^ord(str2[i])) )
	return "".join(out)

# "Pretty much" Grostl's provably secure compression function assuming ideal ciphers
# Grostl pseudo-code is: h = P(m + h) + h + Q(m) and this is basically the same thing, right?
# Ltsorg pseudo-code: h = P(m + h) + m + Q(h)
def compress(m, h):
	return xor( xor( P.encrypt( xor(m, h) ), m), Q.encrypt(h) )

def finalization(m, h):
	return xor(m, h)[0:14]

def hash(msg):
	BLOCK_SIZE = 16
	msg=pad_msg(msg)
	# groestl's IV was boring
	h = IV
#IV = binascii.unhexlify("696c61686773726c7177767576646968")
	for i in xrange(0, len(msg), BLOCK_SIZE):
		m = msg[i: i+BLOCK_SIZE]
		h = compress(m ,h)
	return finalization(m, h)

def check(hashstr1, hashstr2):
	hash1 = binascii.unhexlify(hashstr1);hash2 = binascii.unhexlify(hashstr2)
	if hashstr1 == hashstr2 or hash1 == hash2: return False
	elif hash(hash1) == hash(hash2): return True
	return False

h0 = IV
m10 = xor( P.decrypt( Q.encrypt(h0) ), h0 )
h1 = compress( m10, h0 )
m11 = xor( P.decrypt( Q.encrypt(h1) ), h1 )

str1 = binascii.hexlify(m10)
str2 = binascii.hexlify(m10 + m11)

if check(str1, str2) :
	s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
	s.connect( ('127.0.0.1', 9090) )
	print s.recv(1024).split('\n')[0]
	print str1
	s.send(str1 + '\n')
	time.sleep(1)
	print s.recv(1024).split('\n')[0]
	print str2
	s.send(str2 + '\n')
	time.sleep(1)
	print s.recv(1024)
	s.close()