Be myself :: [picoctf 2015]Repeated XOR

달력

052017  이전 다음

  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  •  
  •  
  •  

문제는 다음과 같다.

encrypted.txt를 보면 다음과 같다.

hex가 잔득 적힌 txt파일이다. 파이썬으로 .decode('hex')해서 바이너리로 만든 다음에 연산하면 될 것 같다.

이 문제는 사실 알면 단순하게 바로 풀 수 있는데 워낙 크립토에 문외한인지라.. 상당히 오랜시간이 걸린 문제다. ㅠㅠ
문제 제목이 힌트인데 Repeated xor 같은 경우는 어떤 key가 주어지고, plain text의 길이만큼 concatenation되어서 문장 전체와 xor하는 암호화 기법이다. 이 것을 복호화 하는 방법은, poly alphabetic cipher를 복호화 하는 방법과 같은데 먼저 키의 길이를 구한다. 키의 길이가 구해지면, 각 키의 길이 만큼 떨어진 문자들을 새로운 N 칼럼으로 만들어서 frequency를 조사하여, 제일 많이 나타나는 문자가 공백이 xor 되어 인크립션 되었을 확률이 높으므로, 원래의 키 값이 드러나게 되는 것이다.

쉽게 말하면 "ABCDEFGHI" 라는 암호화된 문자열이 있고 키의 길이가 3이라고 가정하자. 그렇다면 A,D,G(키의 길이 3칸씩 떨어짐)와 B,E,H 그리고 C,F,I 를 각 칼럼으로 나누고 각각 frequency 를 조사 하여 키 값을 알아내는 방식이다.

키 길이를 구하는 방법은 크게 다음과 같이 두가지로 나뉜다.


1. Kasiski_examination 을 이용한다.https://en.wikipedia.org/wiki/Kasiski_examination
이 방법은 poly alphabetic cipher 이어도 반복되는 문자열이 plain text에 존재하고 같은 치환이 이루어 져서, 암호화 된 텍스트 상에서 반복되는 문자열을 찾아서 그 거리를 각각 구한다. 그리고 그 거리의 최대공약수를 구하고, 그 최대 공약수는 키의 배수가 된다. 천천히 생각해 보면 이해가 될 것이다

그런데 이 방법에는 가장 큰 단점이 존재하는데, key 의 길이의 배수가. 반복되는 문자열 사이의 거리 여야 한다는 것이다. 즉 키의 길이는 6인데 반복되는 문자열 사이의 거리가 20 이라면 나누어 떨어지지 않으므로 이 방법이 무효하다는 것이다. 그래서 더 정확한 다음의 방법을 사용하였다.


2. Hamming Weight 를 이용하는 방법이다. 자세한 설명은 다음의 링크를 참조하자.
https://picoctf.com/crypto_mats/index.html#multi_byte_xor

짧게 설명하자면, encryption 된 문자열끼리 xor 연산을 한다면, 다음과 같다. 암호화 된 문자열을 char enc[] 라는 배열에 있다고 가정한다면 enc[0] ^ enc[1] 은 결국 (평문[0]^key[0])^(평문[1]^key[1]) 이렇게 되는데, 만약 키 길이만큼 떨어진 enc 원소를 xor 한다면( key 길이가 8이라 가정) (평문[0]^key[0]) ^ (평문[8]^key[0]) 이 되므로 평문끼리 xor한 결과가 된다. 그런데 평문끼리(알파벳) xor 한 결과의 Hamming Weight는 2~4 정도 이므로 이를 이용해서 키의 길이를 찾는다. 왼쪽으로 키의 길이라 생각되는 만큼 암호문을 쉬프트하고 원래 암호문과 xor 하여 각각의 바이트들의 Hamming Weight를 구하고 평균을 내서 제일 평균이 작은 키의 길이가 원래 키의 길이일 확률이 높다.

나는 2번을 이용하여 키의 길이가 11임을 알아 내고, frequency를 조사하여 공백(0x20)과 xor하여 원래의 키 값을 알아내었다. (실제 문제 풀이시엔 제일 높은 frequency가 공백이라 생각못하고 'E'라고 생각해서 애를 먹었다...)

풀이는 다음과 같다.

가정한 키의 길이가 11일때 Hamming weight 평균이 2로 가장 작으므로 키의 길이라 생각할 수 있다.
frequency 조사하여 복호화 하면 다음과 같다.



import struct
import string

def key_padding(key,msglen):
	orig_key = key
	result_key = ''
	block = (msglen / len(key))
	left = msglen % len(key)
	for i in range(block):
		result_key += key

	result_key += key[:left]
	return result_key

def HammingWeight(t):
	result = 0
	for i in range(32):
		if (t>>i)&1 == 1:
			result+= 1

	return result

def GetKey(msg):
	if len(msg)%11 != 0:
		print "msg len is not multiple 11"
		return

	keyList = []
	#create block list
	blockList = []
	for i in range(11):
		blockList.append([])

	#devide block
	j = 0
	for tmp in msg:
		blockList[j%11].append(tmp)
		j += 1

	for i in range(11):
		result = {blockList[i].count(x): x for x in blockList[i]}
		keyList.append(chr(ord(result[sorted(result).pop()])^ord(' ')))

	return keyList


def main():
	f = open("encrypted.txt","r")
	buf = f.read().decode('hex')
	f.close()

	################### possible key len is 11########
	# for i in range(1,20):
	# 	Ham = lambda (x,y): HammingWeight(ord(x)^ord(y))
	# 	result = map(Ham,zip(buf,buf[i:]))
	# 	fham = filter(lambda x: x<6, result)
	# 	print "[*]try key len %d " %i
	# 	avg_ham = reduce(lambda x,y: x+y, result)
	# 	avg_ham = avg_ham / len(result)
	# 	print "[-]"+str(avg_ham)
	###################################################

	keyList = GetKey(buf)
	keyList[3] = '\x76'
	#print keyList
	keyList = ''.join(i for i in keyList)
	print "find key %s " %(keyList.encode('hex'))

	pkey = key_padding(keyList,len(buf))
	decode = map(lambda (x,y): ord(x)^ord(y), zip(pkey,buf))
	decode = ''.join(chr(x) for x in decode)
	print decode

if __name__ == '__main__':
	main()

decrypt.py

encrypted.txt



신고

'crypto' 카테고리의 다른 글

[picoctf 2015]Repeated XOR  (4) 2015.11.20
확장된 유클리드  (0) 2015.05.07
암호 공격방법  (0) 2015.04.25
[펌]python hashlib  (0) 2015.03.21
전반적인 암호화  (0) 2015.02.26
Posted by flack3r

티스토리 툴바