一道可以学到密码知识的CTF密码学题目

Jing Ling

2017-01-04

SHA1爆破, crc32碰撞, cryptographic, ctf, md5不再安全, python, rsa wiener attack, 密码学, 维吉尼亚基于字典攻击

0x00 前言

这题是以前出的一道CTF密码学题目，至于设置5层密码只是想让初学者学到更多的东西，感兴趣的小伙伴可以下载题目玩玩。

0x01 解题

1、第一层：CRC32碰撞

得到题目压缩包:

尝试解压，却发现需要密码，根据压缩包里的文件和文件名，猜测是题意是想让我们通过对pwd1，pwd2和pwd3文本文件进行CRC32碰撞获得文本内容，从而得到组合密码。

通过网上查找资料，了解CRC32碰撞原理，了解原理之后可以在github上找到可利用的Python脚本。

分别对3个CRC32值进行碰撞，找到最可能的组合：_CRC32_i5_n0t_s4f3，输入密码解压进入下一层。
如果是善于动手编程能力较好的小伙伴也可以自己编写一个脚本来跑，下面给出自己的demo：

# -*- coding: utf-8 -*-
# crc32Collision.py
import threading
import binascii
import time

def breakpassword():
    start=time.clock()
    crc_num=set([0x7C2DF918,0xA58A1926,0x4DAD5967])
    x = range(32,128)
    for i in x:
        for j in x:
            for k in x:
                for l in x:
                    for m in x:
                        for n in x:
                            mutex.acquire() # 取得锁
                            string=chr(i)+chr(j)+chr(k)+chr(l)+chr(m)+chr(n)
                            if binascii.crc32(string) in crc_num:
                                print "crc32 of %s is-> %s" %(string,hex(binascii.crc32(string)))
                                f=open("string.txt",'a')
                                f.write(string)
                                f.close()
                            mutex.release() # 释放锁
    end=time.clock()
    print "Used time: %f s" % (end - start)

def main(thread_num):
    print "breaking,please wait!"
    global mutex #定义全局变量
    mutex=threading.Lock() # 创建锁

    threads=[] #定义线程池
    # 先创建线程对象
    for x in xrange(0,thread_num): 
        threads.append(threading.Thread(target=breakpassword))
        # 启动所有线程
        for t in threads:
            t.start()
        # 主线程中等待所有子线程退出
        for t in threads:
            t.join()

if __name__ == '__main__':
    main(10)  # 创建n个线程

2、第二层：维吉尼亚基于字典攻击

解压之后得到下图三个文件：

打开tips.txt读懂题意，要求我们在keys.txt中找到密钥解密ciphertext.txt，解密密文之后便可以得到Find password.7z的解压密码。通过网上大量的资料查阅，了解维吉尼亚密码加密解密原理和算法，搜索相应的解密工具可以在http://inventwithpython.com/hacking/diff/找到可以模板，需要读懂相应模块并修改使用：

# -*- coding: utf-8 -*-
#vigenereDictionaryHacker.py
import detectEnglish
LETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def translateMessage(key, message, mode):
	translated = [] # 存储加密/解密消息字符串
	keyIndex = 0
	key = key.upper()
	for symbol in message: # 遍历每个消息里的字符的消息
		num = LETTERS.find(symbol.upper())
		if num != -1: # -1 意味着转换为大写在LETTERS找不到
			if mode == 'encrypt':
				num += LETTERS.find(key[keyIndex]) # 加密时相加
			elif mode == 'decrypt':
				num -= LETTERS.find(key[keyIndex]) # 解密时相减
			num %= len(LETTERS) # 处理潜在的循环			
			# 添加转换后加密/解密字符
			if symbol.isupper():
				translated.append(LETTERS[num])
			elif symbol.islower():
				translated.append(LETTERS[num].lower())
			keyIndex += 1 # 继续下一个用密钥字符来解密
			if keyIndex == len(key):
				keyIndex = 0
		else:
			# 字符不在LETTERS里直接添加
			translated.append(symbol)
	return ''.join(translated)
def decryptMessage(key, message):
	return translateMessage(key, message, 'decrypt')
def hackVigenere(ciphertext):
	fo = open('keys.txt')
	words = fo.readlines()
	fo.close()
	for word in words:
		word = word.strip()
		decryptedText = decryptMessage(word, ciphertext)
		if detectEnglish.isEnglish(decryptedText, wordPercentage=40):
			print('------------------------>>>Notice!<<<----------------------')
			print('Possible encryption break:')
			print('->>Possible key: ' + str(word))
			print('->>Possible plaintext: ' + decryptedText[:100])
			print('Enter D for done, or just press Enter to continue breaking:')
			response = raw_input('> ')
			if response.upper().startswith('D'):
				return decryptedText
def main():
	ciphertext = """rla xymijgpf ppsoto wq u nncwel ff tfqlgnxwzz sgnlwduzmy vcyg ib bhfbe u tnaxua ff satzmpibf vszqen eyvlatq cnzhk dk hfy mnciuzj ou s yygusfp bl dq e okcvpa hmsz vi wdimyfqqjqubzc hmpmbgxifbgi qs lciyaktb jf clntkspy drywuz wucfm"""
	hackedMessage = hackVigenere(ciphertext)
	if hackedMessage != None:
		print('\nCopy Possible plaintext to the clipboard:\n')
		print(hackedMessage)
	else:
		print('Failed to hack encryption.')
if __name__ == '__main__':
	main()

# -*- coding: utf-8 -*-
# detectEnglish.py
# 英文单词探测模块
# 模块引用:
#   import detectEnglish
#   detectEnglish.isEnglish(someString) # 返回真或假
# 模块需要一个包含常见英文单词的"words.txt"，下载地址：http://invpy.com/dictionary.txt
UPPERLETTERS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
LETTERS_AND_SPACE = UPPERLETTERS + UPPERLETTERS.lower() + ' \t\n'
def loadDictionary():
    dictionaryFile = open('words.txt')
    englishWords = {}
    for word in dictionaryFile.read().split('\n'):
        englishWords[word] = None
    dictionaryFile.close()
    return englishWords
ENGLISH_WORDS = loadDictionary()
def getEnglishCount(message):
    message = message.upper()
    message = removeNonLetters(message)
    possibleWords = message.split()
    # print possibleWords
    if possibleWords == []:
        return 0.0 # 没有单词返回0.0
    matches = 0
    for word in possibleWords:
        if word in ENGLISH_WORDS:
            matches += 1
    return float(matches) / len(possibleWords)
def removeNonLetters(message):
    lettersOnly = []
    for symbol in message:
        if symbol in LETTERS_AND_SPACE:
            lettersOnly.append(symbol)
    return ''.join(lettersOnly)
def isEnglish(message, wordPercentage=20, letterPercentage=85):
    # 默认设置转换后的message中单词的20%能在words.txt中的单词列表找到
    # 默认设置转换后的message中85%是字母或空格
    # (not punctuation or numbers).
    wordsMatch = getEnglishCount(message) * 100 >= wordPercentage
    numLetters = len(removeNonLetters(message))
    messageLettersPercentage = float(numLetters) / len(message) * 100
    lettersMatch = messageLettersPercentage >= letterPercentage
    return wordsMatch and lettersMatch

解密结果：

所以Find password.7z的解压密码就是：vigenere cipher funny

3、第三层：SHA1

解压Find password.7z得到如下文件：

打开U need unzip password.txt读懂题意，题目要求我们通过编写脚本爆破SHA1的明文密文对，得到明文作为解压密码进入下一关。
了解了SHA1密码之后，通过查阅资料发现我们可以使用Python的hashlib模块来进行爆破，下面给出demo：

#break_sha1.py
import hashlib
import time
def match(h,pwd):
	hl=list(h)
	if hl[0]=='6':
		if hl[1]=='1':
			if hl[2]=='9':
				if hl[3]=='c':
					if hl[4]=='2':
						if hl[5]=='0':
							if hl[6]=='c':
								if hl[8]=='a':
									if hl[16]=='9':
										if hl[24]=='b':
											if hl[32]=='e':
												print "Find!"
												print "Hash:%s" %h
												print "Password:%s" %pwd
												matched=1
												return matched
	else:
		matched=0
		return matched
def generate():
	x=range(32,128)
	for i in x:
		for j in x:
			for k in x:
				for l in x:
					pwd=chr(i)+'7'+chr(j)+'5-'+chr(k)+'4'+chr(l)+'3?'
					sha1_hash=hashlib.sha1()
					sha1_hash.update(pwd)
					h=sha1_hash.hexdigest()
					matched=match(h,pwd)
					if matched:
						print "congratulation!"
						return 0
					else:
						pass
def main():
	start=time.clock()
	print "Breaking,please wait!"
	generate()
	end=time.clock()
	print "Used time:%s" %(end-start)
if __name__ == '__main__':
	main()

结果：

所以得到Easy SHA1.7z的解压密码：I7~5-s4F3?

4、第四层：MD5不再安全

解压Easy SHA1.7z之后得到如下文件：

打开MD5_is_really_safe？.txt文本，题目要让我们找到两个不同程序但是他们的MD5值却相同，这题考察我们对MD5安全性的感知度。通过搜索引擎可以找到大量关于王小云教授对MD5破解相关资料，百度关键词：MD5碰撞 MD5校验真的安全吗？ MD5真的已靠不住? 等等。

下载HelloWorld-colliding.exe GoodbyeWorld-colliding.exe运行结果：

Hello World ;-)已在提示里，那么另一个程序的输出就是：Goodbye World :-(
根据提示输入做为Vulnerable RSA.7z的解压密码，解压成功进入下一关。

5、第五层：Vulnerable RSA

解压Vulnerable RSA.7z后得到如下文件：

在了解RSA的原理和常见的攻击方法后，我们用OpeSSL来导入公钥查看模数n，指数e。

1	openssl rsa -inform PEM -in rsa_public_key.pem -noout -modulus -text -pubin

可以看到指数（Exponent）很大，在RSA中我们知道ed ≡ 1 (mod φ(n))，如果n确定，e非常大，就会导致d很小，就会出现维纳攻击（Wiener’s attack），攻击原理是使用连分式（Continued fraction）去求得d。

了解原理后我们可以在github找到基于维纳攻击的工具rsa-wiener-attack，然后将其中的RSAwienerHacker.py改写一下：

#RSAwienerAttack.py  
import ContinuedFractions, Arithmetic
def hack_RSA(e,n):
    '''
    Finds d knowing (e,n)
    applying the Wiener continued fraction attack
    '''
    frac = ContinuedFractions.rational_to_contfrac(e, n)
    convergents = ContinuedFractions.convergents_from_contfrac(frac)
    
    for (k,d) in convergents:
        #check if d is actually the key
        if k!=0 and (e*d-1)%k == 0:
            phi = (e*d-1)//k
            s = n - phi + 1
            # check if the equation x^2 - s*x + n = 0
            # has integer roots
            discr = s*s - 4*n
            if(discr>=0):
                t = Arithmetic.is_perfect_square(discr)
                if t!=-1 and (s+t)%2==0:
                    print("\nHacked!")
                    return d
def main():
    e=354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
    n=460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
    print "e="
    print e
    print "n="
    print n
    d=hack_RSA(e,n)
    print "d="
    print d
if __name__ == '__main__':
    main()

结果：

我们得到了私钥d，且知道了e，那我们就可以使用rsatool来生产私钥文件：

rsatool.py -e 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619 -n 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597 -d 8264667972294275017293339772371783322168822149471976834221082393409363691895 -o rsa_private_key.pem -f PEM

得到rsa_private_key.pem，于是我们利用OpenSSL对flag.enc解密：

1	openssl rsautl -decrypt -in flag.enc -inkey rsa_private_key.pem

最终得到flag：flag{W0rld_Of_Crypt0gr@phy}