Crypto
easy_RSA
套娃题，第一层题目如下：
n:0x9371c61a2b760109781f229d43c6f05b58de65aa2a674ff92334cb5219132448d72c1293c145eb6f35e58791669f2d8d3b6ce506f4b3543beb947cf119f463a00bd33a33c4d566c4fd3f4c73c697fa5f3bf65976284b9cc96ec817241385d480003cdda9649fa0995b013e66f583c9a9710f7e18396fbf461cb31720f94a0f79L
e:0x3
encrypt(m):0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffbbd5a5e1a10f686c3f240e85d011f6c8b968d1d607b2e1d5a78ad6947b7d3ec8f33ad32489befab601fe745164e4ff4aed7630da89af7f902f6a1bf7266c9c95b29f2c69c33b93a709f282d43b10c61b1a1fe76f5fee970780d7512389fd1L
encrypt(m+1):0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffc5c26b0c12bcff9f697f274f59f0e55a147768332fc1f1bac5bbc8f9bb508104f232bdd20091d26adc52e36feda4a156eae7dce4650f83fabc828fdcfb01d25efb98db8b94811ca855a6aa77caff991e7b986db844ff7a140218449aaa7e8L一看俩次m是线性关系，也就是打个padding，而且e=3也比较适合padding攻击，直接冲。
import gmpy2
import libnum
def getM2(a,b,c1,c2,n):
a3 = pow(a,3,n)
b3 = pow(b,3,n)
first = c1-a3*c2+2*b3
first = first % n
second = 3*b*(a3*c2-b3)
second = second % n
third = second*gmpy2.invert(first,n)
third = third % n
fourth = (third+b)*gmpy2.invert(a,n)
return fourth % n
# m1 = f(m2) = a * m2 + b
n = 0x9371c61a2b760109781f229d43c6f05b58de65aa2a674ff92334cb5219132448d72c1293c145eb6f35e58791669f2d8d3b6ce506f4b3543beb947cf119f463a00bd33a33c4d566c4fd3f4c73c697fa5f3bf65976284b9cc96ec817241385d480003cdda9649fa0995b013e66f583c9a9710f7e18396fbf461cb31720f94a0f79L
c1 = 0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffbbd5a5e1a10f686c3f240e85d011f6c8b968d1d607b2e1d5a78ad6947b7d3ec8f33ad32489befab601fe745164e4ff4aed7630da89af7f902f6a1bf7266c9c95b29f2c69c33b93a709f282d43b10c61b1a1fe76f5fee970780d7512389fd1L
c2 = 0x5f4e03f28702208b215f39f1c8598b77074bfa238dfb9ce424af7cc8a61f7ea48ffc5c26b0c12bcff9f697f274f59f0e55a147768332fc1f1bac5bbc8f9bb508104f232bdd20091d26adc52e36feda4a156eae7dce4650f83fabc828fdcfb01d25efb98db8b94811ca855a6aa77caff991e7b986db844ff7a140218449aaa7e8L
a = 1
b = -1
padding2 = 1
m = getM2(a, b, c1, c2, n)-padding2
print libnum.n2s(m)得到：the key is :everything_is_easy_in_this_question
解压得到如下：
280316470206017f5f163a3460100b111b2c254e103715600f13,
091b0f471d05153811122c70340c0111053a394e0b39500f0a18,
4638080a1e49243e55531a3e23161d411a362e4044111f374409,
0e0d15470206017f59122935601405421d3a244e10371560140f,
031a08080e1a540d62327f242517101d4e2b2807177f13280511,
0a090f001e491d2c111d3024601405431a36231b083e022c1d,
16000406080c543854077f24280144451c2a254e093a0333051a,
02050701120a01334553393f32441d5e1b716027107f19334417,
131f15470800192f5d167f352e0716481e2b29010a7139600c12,
1609411e141c543c501d7f232f0812544e2b2807177f00320b1f,
0a090c470a1c1d3c5a1f2670210a0011093a344e103715600712,
141e04040f49153142043a22601711520d3a331d0826找到个类似的题AlexCTF 2017 : crypto100-many_time_secrets，用他的脚本改改得到如下脚本：
#!/usr/bin/python
## OTP - Recovering the private key from a set of messages that were encrypted w/ the same private key (Many time pad attack) - crypto100-many_time_secret @ alexctf 2017
# @author intrd - http://dann.com.br/
# Original code by jwomers: https://github.com/Jwomers/many-time-pad-attack/blob/master/attack.py)
import string
import collections
import sets, sys
# 11 unknown ciphertexts (in hex format), all encrpyted with the same key
c1 = "280316470206017f5f163a3460100b111b2c254e103715600f13"
c2 = "091b0f471d05153811122c70340c0111053a394e0b39500f0a18"
c3 = "4638080a1e49243e55531a3e23161d411a362e4044111f374409"
c4 = "0e0d15470206017f59122935601405421d3a244e10371560140f"
c5 = "031a08080e1a540d62327f242517101d4e2b2807177f13280511"
c6 = "0a090f001e491d2c111d3024601405431a36231b083e022c1d"
c7 = "16000406080c543854077f24280144451c2a254e093a0333051a"
c8 = "02050701120a01334553393f32441d5e1b716027107f19334417"
c9 = "131f15470800192f5d167f352e0716481e2b29010a7139600c12"
c10 = "1609411e141c543c501d7f232f0812544e2b2807177f00320b1f"
c11 = "0a090c470a1c1d3c5a1f2670210a0011093a344e103715600712"
ciphers = [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11]
# The target ciphertext we want to crack
target_cipher = "141e04040f49153142043a22601711520d3a331d0826"
# XORs two string
def strxor(a, b): # xor two strings (trims the longer input)
return "".join([chr(ord(x) ^ ord(y)) for (x, y) in zip(a, b)])
# To store the final key
final_key = [None]*150
# To store the positions we know are broken
known_key_positions = set()
# For each ciphertext
for current_index, ciphertext in enumerate(ciphers):
counter = collections.Counter()
# for each other ciphertext
for index, ciphertext2 in enumerate(ciphers):
if current_index != index: # don't xor a ciphertext with itself
for indexOfChar, char in enumerate(strxor(ciphertext.decode('hex'), ciphertext2.decode('hex'))): # Xor the two ciphertexts
# If a character in the xored result is a alphanumeric character, it means there was probably a space character in one of the plaintexts (we don't know which one)
if char in string.printable and char.isalpha(): counter[indexOfChar] += 1 # Increment the counter at this index
knownSpaceIndexes = []
# Loop through all positions where a space character was possible in the current_index cipher
for ind, val in counter.items():
# If a space was found at least 7 times at this index out of the 9 possible XORS, then the space character was likely from the current_index cipher!
if val >= 7: knownSpaceIndexes.append(ind)
#print knownSpaceIndexes # Shows all the positions where we now know the key!
# Now Xor the current_index with spaces, and at the knownSpaceIndexes positions we get the key back!
xor_with_spaces = strxor(ciphertext.decode('hex'),' '*150)
for index in knownSpaceIndexes:
# Store the key's value at the correct position
final_key[index] = xor_with_spaces[index].encode('hex')
# Record that we known the key at this position
known_key_positions.add(index)
# Construct a hex key from the currently known key, adding in '00' hex chars where we do not know (to make a complete hex string)
final_key_hex = ''.join([val if val is not None else '00' for val in final_key])
# Xor the currently known key with the target cipher
output = strxor(target_cipher.decode('hex'),final_key_hex.decode('hex'))
print "Fix this sentence:"
print ''.join([char if index in known_key_positions else '*' for index, char in enumerate(output)])+"\n"
# WAIT.. MANUAL STEP HERE
# This output are printing a * if that character is not known yet
# fix the missing characters like this: "Let*M**k*ow if *o{*a" = "cure, Let Me know if you a"
# if is too hard, change the target_cipher to another one and try again
# and we have our key to fix the entire text!
#sys.exit(0) #comment and continue if u got a good key
i = ord('r') # for i in range(128)
j = ord('c') # for j in range(128)
k = ord('t') # for k in range(128)
l = ord('s') # for l in range(128)
target_plaintext = "r{}e{}{} answer succes{}ly".format(chr(i), chr(j), chr(k), chr(l))
print "Fixed:"
print target_plaintext+"\n"
key = strxor(target_cipher.decode('hex'),target_plaintext)
print "Decrypted msg:"
for cipher in ciphers:
print strxor(cipher.decode('hex'),key)
print "\nPrivate key recovered: "+key+"\n"先是得到部分句子r*e** answer succks*ly（因为是猜解所以可能有不对字符？）
然后爆破或者瞎猜得到rrect answer successly。（具体看上面脚本）
解出大部分明文以及部分密钥。
Decrypted msg:
Now you need to use th
own flag as the key of
Time Pad Encryptin. N
hat you have passed th
evious RSA test, this
lenge is not particula
please get the true me
difficult for you. It
ust simple encryption.
pe you can solve this
lem quickly and get th
Private key recovered: flag{it_1s_P@dd1n_@nd_至于为啥是部分而不是全部呢？因为出题的没把target_cipher给全，差了4字节，最后1字节肯定是}，所以还有3字节，那就写个加密脚本爆破一下看看哪个加密后能和题目一样呗。
不过因为明文也是只有一部分，所以要补全，因为第一行感觉挺好补的就拿第一行爆破了。
补完是：Now you need to use the kn。
import random
def xor_bytes(key_stream, message):
length = min(len(key_stream), len(message))
return bytes([key_stream[i]^ message[i] for i in range(length)])
message = b"Now you need to use the kn"
for i in range(128):
for j in range(128):
for k in range(128):
key_stream = b'flag{it_1s_P@dd1n_@nd_'+f'{chr(i)}'.encode()+f'{chr(j)}'.encode()+f'{chr(k)}'.encode()+b'}'
cipher = xor_bytes(key_stream, message)
if cipher.hex() == "280316470206017f5f163a3460100b111b2c254e103715600f13":
print(key_stream)
print(cipher.hex())
print(xor_bytes(key_stream, cipher))得到flag。
flag{it_1s_P@dd1n_@nd_p@d}
Reverse
100mazes
题目源码倒是挺直白的，没有函数跳来跳去或者汇编嵌入啥的。
就是走100次迷宫然后路径连起来求个md5。
于是就先看看迷宫长啥样呗，随便挑几个对比可以感觉100个迷宫的差别并不大，都是25*25，然后代码布局也基本上一样。
不一样的地方在于每个迷宫的地图、路线方向标识、起点，然后这题的迷宫生成方式比较有意思，是两组矩阵xor的结果，而代码里的矩阵在生成的时候有干扰代码__asm { rdrand rax }，不容易提取，是等下写脚本的难点之一，写死在rodata的矩阵倒是简单，25*25*4字节的大小，然后每个矩阵还有28间隔，脚本提取就行了。
以maze1为例分析下迷宫源码，得到如下信息。
直接开始写脚本读取迷宫数据。
def maze(funcStart, rodataStart):
...
# 读取程序
elf = open('100mazes', 'rb').read()
# 从ida导出的函数定位点
func = [0x78A, 0x224F, 0x3CDE, 0x574F, 0x717E, 0x8BD1, 0xA62A, 0xC059, 0xDB7E, 0xF5A1, 0x11024, 0x129D5, 0x1441C, 0x15E9F, 0x1790A, 0x19387, 0x1AE5E, 0x1C8F9, 0x1E3AC, 0x1FE59, 0x21984, 0x2341F, 0x24EBA, 0x26997, 0x283F0, 0x29E25, 0x2B8A8, 0x2D2EF, 0x2EDA8, 0x3085B, 0x322FC, 0x33D85, 0x3581A, 0x37297, 0x38D2C, 0x3A79D, 0x3C232, 0x3DCAF, 0x3F73E, 0x411B5, 0x42C4A, 0x446EB, 0x4613E, 0x47BD3, 0x4963E, 0x4B18D, 0x4CBE0, 0x4E645, 0x500C8, 0x51B5D, 0x5366A, 0x550D5, 0x56B94, 0x5867D, 0x5A0B8, 0x5BB4D, 0x5D5A6, 0x5F077, 0x60AE8, 0x6251D, 0x63F76, 0x659C3, 0x6749A, 0x68F71, 0x6AA12, 0x6C4E3, 0x6E008, 0x6FA9D, 0x7150E, 0x72FE5, 0x74A56, 0x7652D, 0x78022, 0x79B1D, 0x7B5D6, 0x7D08F, 0x7EB84, 0x805CB, 0x81FCA, 0x83ABF, 0x8558A, 0x87019, 0x88AC6, 0x8A585, 0x8BFC0, 0x8DA37, 0x8F508, 0x90FD3, 0x92A68, 0x94575, 0x96034, 0x97AA5, 0x99570, 0x9AF81, 0x9CA1C, 0x9E523, 0x9FFB8, 0xA1A65, 0xA355A, 0xA5079]
# rodata起始位置
rodata = 0xA7420
# 传入猜测需要的数据走迷宫
roads = ""
for i in range(100):
roads+=maze(funcStart=func[i], rodataStart=rodata)
rodata += 0x9E0
print(roads)
# 判断路线长度
assert len(roads) == 1500
# 根据路线生成flag
import hashlib
d = hashlib.md5(roads.encode()).hexdigest()
print(d)
flag = 'flag{'+d[0:8]+'-'+d[8:12]+'-'+d[12:16]+'-'+d[16:20]+'-'+d[20:32]+'}'
print(flag)大致脚本结构就是如上这样，难就难在如何提取数据。
思路是根据汇编十六进制的命令格式去遍历匹配。
矩阵1是mov命令生成，这题里可以匹配一下c6 85 xx xx ff ff。
接着是路线方向标识，和矩阵1一样，不过匹配个4回就结束。
然后x和y的话，匹配下c7 85 xx xx ff ff。
最后矩阵2直接隔4个取一下就行。
import numpy as np
def maze(funcStart, rodataStart):
data1 = []
p = 0
while len(data1) < 625:
if elf[funcStart+p] == 0xc6 and elf[funcStart+p+1] == 0x85 and elf[funcStart+p+4:funcStart+p+6] == b'\xff\xff':
pos = elf[funcStart+p+2:funcStart+p+4].hex()
data = elf[funcStart+p+6]
data1.append(data)
# print(pos, data)
p += 7
else:
p += 1
direction = []
while len(direction) < 4:
if elf[funcStart+p] == 0xc6 and elf[funcStart+p+1] == 0x85 and elf[funcStart+p+4:funcStart+p+6] == b'\xff\xff':
pos = elf[funcStart+p+2:funcStart+p+4].hex()
data = elf[funcStart+p+6]
direction.append(chr(data))
# print(pos, data)
p += 7
else:
p += 1
x = 0
while True:
if elf[funcStart+p] == 0xc7 and elf[funcStart+p+1] == 0x85 and elf[funcStart+p+4:funcStart+p+6] == b'\xff\xff':
pos = elf[funcStart+p+2:funcStart+p+4].hex()
x = elf[funcStart+p+6]
# print(pos, data)
p += 10
break
else:
p += 1
y = 0
while True:
if elf[funcStart+p] == 0xc7 and elf[funcStart+p+1] == 0x85 and elf[funcStart+p+4:funcStart+p+6] == b'\xff\xff':
pos = elf[funcStart+p+2:funcStart+p+4].hex()
y = elf[funcStart+p+6]
# print(pos, data)
p += 10
break
else:
p += 1
data1 = [i.tolist() for i in np.array_split(data1, 25)]
data2 = []
p = 0
while len(data2) < 625:
assert elf[rodataStart + p + 1: rodataStart + p + 4] == b'\x00\x00\x00'
data = elf[rodataStart + p]
data2.append(data)
# print(data)
p+=4
data2 = [i.tolist() for i in np.array_split(data2, 25)]
dataXY = []
for j in range(25):
dataX = []
for i in range(25):
dataX.append(data1[j][i]^data2[j][i])
dataXY.append(dataX)
# print(dataX)
oldy = y
oldx = x
assert dataXY[y][x] == 46
road = ""
while len(road) < 15:
if 0 <= y-1 <= 24 and oldy != y-1 and dataXY[y-1][x] == 46:
oldx = x
oldy = y
y = y-1
road += direction[0] # ↑
elif 0 <= y + 1 <= 24 and oldy != y + 1 and dataXY[y + 1][x] == 46:
oldx = x
oldy = y
y = y + 1
road += direction[1] # ↓
elif 0 <= x - 1 <= 24 and oldx != x - 1 and dataXY[y][x - 1] == 46:
oldx = x
oldy = y
x = x - 1
road += direction[2] # ←
elif 0 <= x+1 <= 24 and oldx != x+1 and dataXY[y][x+1] == 46:
oldx = x
oldy = y
x = x+1
road += direction[3] # →
return road最后拼合脚本得到flag。
flag{60e92557-3e0c-3123-6eb1-c57005fc0655}
Comments NOTHING