CISG2015 MISC.3解析

May 18, 2015

引子

每个少年，也许都曾有过一个成为武林高手的梦。但随着时间流逝，还有多少热血存留在记忆的深处，多少人成为了茫茫红尘中的一个庸庸碌碌之辈。浮生若梦，弹指一挥间，青丝白发。

我不是武林高手，但我希望我是。我希望你是。

题目原文

藤原暮雨在一个月的观察行动中，机智地截获到了“三叶豆腐店”内部通讯的一段密文。面对密文藤原一头雾水，不过他知道明文中一定出现了flag这个单词。请你帮他解密出明文。

http://game.sycsec.com/download/Misc3_new.zip（链接可能会失效）

Misc3_new.zip文件内容

#!/usr/bin/python

from struct import pack
from struct import unpack

state = 0

def rand():
    global state
    state = (state * 1103515425 + 54321) & 0x3fffffff
    return state
    
def srand(seed):
    global state
    state = seed
    
def encrypt(data,key):
    srand(key)
    cipher = ""
    for c in data:
        cipher += pack("i",(ord(c)<<22) + rand())
    return cipher

def decrypt(data,key):
    srand(key)
    plain = ""
    for i in range(0,len(data),4):
        temp = unpack("i",data[i:i+4])[0] - rand()
        plain += chr(temp >> 22)
    return plain

def main():
    f1 = open("plaintext","rb")
    f2 = open("ciphertext","wb")
    data = f1.read()
    from secretfile import secretkey
    data = encrypt(data,secretkey)
    f2.write(data)

if __name__ == "__main__":
    main()

题目解析

这题的目的就是要解密ciphertext，然后拿到flag

思路

crypt.py分析

首先是main函数

def main():
    f1 = open("plaintext","rb") #打开明文
    f2 = open("ciphertext","wb") #打开密文文件准备写入
    data = f1.read() #从明文中读入数据
    #不知从哪里拿来了一个secretkey，这并不重要，后面会详细分析
    from secretfile import secretkey 
    data = encrypt(data,secretkey) #调用加密函数来加密data
    f2.write(data) #将密文写入到密文文件

然后是加密解密函数

#加密函数
def encrypt(data,key):
    srand(key) #用key设置随机数种子
    cipher = ""
    for c in data: 
        #对传入的每个字符先左移22位
        #然后再加上一个随机数
        #最后用pack将这个数字转换为int(int为32bit，即4字节)
        cipher += pack("i",(ord(c)<<22) + rand()) 
    return cipher

#解密函数
def decrypt(data,key):
    srand(key) #用key设置随机数种子
    plain = ""
    for i in range(0,len(data),4): #因为int为4字节，所以这里的step为4
        #加密过程的逆向
        #先减去随机数
        temp = unpack("i",data[i:i+4])[0] - rand()
        #然后右移22位，并将之转化为字符
        plain += chr(temp >> 22)
    return plain

最后就是随机数生成函数了，这个随机数生成算法并不同于常见的线性同余算法，它最后使用了按位与的操作，将随机数限定在了[0,0x3fffffff]之间。

state = 0 #保存随机数状态的值

#随机数生成函数
def rand():
    global state #注明state是全局变量
    #每个随机数都是由上一个随机数计算得来的，这点很重要
    state = (state * 1103515425 + 54321) & 0x3fffffff
    return state

#设置随机数种子，就是直接设置了state的值    
def srand(seed):
    global state
    state = seed

好了代码分析已经差不多了。

加密的弱点分析：

重要线索：

猜测一下可能的情况：

当随机数很小的时候的情况分析：

例如被加密的字符是a，随机数很小为54321

1100001 0000000000000000000000 #a<<22之后的二进制表示

0000000 0000001101010000110001 #54321的二进制表示

1100001 0000001101010000110001 #加密后的二进制表示

当随机数位于[0, 0x3fffff] （0x3fffff也就是二进制中22个1）的时候那其实就是明文的字符值+明文的随机数

而这种事件出现的平均概率为0.0039062490723154033（0x3fffff/0x3fffffff）。

因为ascii字符的范围在[0,255]之间，所以我们可以先将密文右移22位，看看是否在范围内，代码为下面的check22()函数。

但是很显然，我们有理由相信在较小的密文中这种事件出现的概率更大，so，让我们给密文排个序吧。

def check22(num):
    t = num >>22
    return t in range(256)

def order(data):
    a = []
    for i in range(0,len(data),4):
        temp = unpack("i",data[i:i+4])[0]
        if check22(temp):
            a.append((temp, hex(temp), bin(temp)))

    a.sort()
    for i in a:
        print(i)

运行完order()函数，得到了排序完的数字

(180362139, '0xac01b9b', '0b1010110000000001101110011011')
(180370932, '0xac03df4', '0b1010110000000011110111110100')
(180372350, '0xac0437e', '0b1010110000000100001101111110')
(180402993, '0xac0bb31', '0b1010110000001011101100110001')
(180511464, '0xac262e8', '0b1010110000100110001011101000')
...

排序已经出来了，拼人品的时候终于到了，我好激动>…<

尝试了第一个数字0xac01b96,在解密到一半的时候错误，错误的原因应该是一个较大的随机数加上了一个较小的字符值，导致右移22位之后的值正好在[0, 255]之间。

在尝试第二个数字0xac03df4的时候顺利解完，解密函数如下：

def decrypt(data):
    plain = ""
    bStartDecrypt = False
    for i in range(0,len(data),4):
        temp = unpack("i",data[i:i+4])[0]
        if bStartDecrypt:
            temp -= rand()
            plain += chr(temp >> 22)
            #print(plain)
        elif temp == 0xac03df4: #只要检测到了0xac03df4，就开始解密
            print("get min i:", i)
            print(chr((temp - 0x3df4)>>22))
            srand(0x3df4)
            bStartDecrypt = True

    print(plain)

运行完后得到flag

('get min i:', 2572260)
+
...省略n个字符
XxuEMGwaAqTXQlF+7pB/5S4vnZ85Lap2siP8q/jFYp87z7PXHmJ20opxy8yxnBsRP
oWEs8glONXf1H+h4kkdTcCg+HfwGXqYrf0jyFBgAAAABJRU5ErkJggg==|flag is 
hidden in the above data It is a picture and you should base64decode it.

前两句是我的debug输出内容，表明了是从第2572260个密文开始解密的。 最初开始解密的明文字符是’+’

flag is hidden in the above data It is a picture and you should base64decode it.

然后flag说我不是flag，flag在我上面。。。然后它是一张图片而且还是被Base64加密了图片。

现在问题来了，我们是从一半开始解密的，明文只有一半，直接用Base64解密肯定是不行的

这里有两条线索：

如果不熟悉Base64编码的话可能会遇到麻烦。我已经被坑过了。。

是图片就好办了，因为图片一般都是有固定格式的，而常见的图片格式也就那么几种。只要猜到是哪种格式的图片就好办了。

诶，又要拼人品吗？哈哈，我喜欢。

##思路： * 因为每个随机数都是通过上一个随机数计算而来的，因此只要知道了第一个密文的随机数，我们就可以解密接下来的所有内容。而常见的图片格式都是有固定的文件头的。

常见的图片格式文件头分析：

之前抱着死马当活马医的态度用Base64将半个flag解密了下，果然没有一个图片软件能打开。。 顺便用xxd看了下它的16进制表示：

...
014acf0: adfd 23c8 5060 0000 0004 9454 e44a e426  ..#.P`.....T.J.&
014ad00: 0820

从最后两个字节0820我们可以排除jpg，因为jpg在文件末尾有0xFFD9的结束标记（参考） ,然而我们并没有见到。

密文查看函数，查看密文的前5个整数：

def showData(data):
    for i in range(0,20,4):
        temp = unpack("i",data[i:i+4])[0]
        print(hex(temp))

得到第一个密文是：0x52aaac6b，然后我们就可以根据这个密文来推测随机数了，函数如下：

def getRandNum(cNum, c):
    return cNum - (ord(c)<<22)

接下来拼下人品，看看是不是png，根据png的文件头 89504E47 的Base64码来逆推随机数

import base64
base64.b64encode(chr(0x89)+chr(0x50)+chr(0x4e)+chr(0x47))

获得png文件头的Base64密文：iVBORw==，首字母为i。

然后调用decryptSecond()函数来解密：

seed = getRandNum(0x52aaac6b, 'i')
decryptSecond(data, seed)

相应的解密函数如下：

def decryptSecond(data,key):
    srand(key)
    plain = ""
    for i in range(4,len(data),4):  #注意这里的起始值为4，意思是从第二个int开始解码
        temp = unpack("i",data[i:i+4])[0] - rand()
        plain += chr(temp >> 22)

    print(plain)
    return plain

然后人品爆发，完整解密通过，将输出内容重定向到文件后，记得要将最后一句话去掉，然后在文件开头添加字符i。

于是我们得到了整个图片被Base64加密过的密文。

Base64解密代码：

import base64
f = open("NEWFLAG")
flagStr = f.read()
f.close()

a = base64.b64decode(flagStr)

f = open("FLAG_PIC.png", "wb")
f.write(a)
f.close()

最终拿到flag，Happy~

各种曲折

再不相信大力出奇迹了

其实题面中有一句话误导了我：他知道明文中一定出现了flag这个单词，然后我自然而然就想到了爆破。

虽然爆破没有成功，但是还是很有收获的。

爆破的思路1:

爆破的思路2:

爆破的思路3：

爆破思路2的优化：

Comments

comments powered by Disqus