watevrCTF_Crypto over the intrawebs

roger

题目描述如下：

I was hosting a very secure python chat server during my lunch break and I saw two of my classmates connect to it over the local network. Unfortunately, they had removed most of the code when i came up to them. I don’t know what they said, can you help me figure it out?

Files:conversation, super_secure_client_1.py, super_secure_client_2.py, super_secure_server.py

审计源码，猜测通信的内容经过了encrypt函数的加密，其加密算法是可逆的，但是我们不知道key，但是观察发现每次加密时,会先在明文前面加上USERNAME + ": "这一前缀，而这一前缀是已知的，因此我们可以使用已知明文攻击的思路，通过解方程组来尝试恢复秘钥。

以Conversion文件中第一条记录为例，根据Message from: 198.51.100.0我们可知其使用的前缀为Houdini:，共计8个字符，根据加密时使用的递推表达式：

out[i+2] == (out[i+1] + ((out[i] * ord(plaintext[i])) ^ (key+out[i+1]))) ^ (key*out[i]) i=0,1,2...

其中out[0]=8886,out[1]=42

可知为了利用上Houdini:这8个字符来列方程需要out数组的前10个值，这里我们采用z3来解方程，先打印出z3格式的方程组：

out = [8886,42,212351850074573251730471044,424970871445403036476084342,5074088654060645719700112791577634658478525829848,17980375751459479892183878405763572663247662296,121243943296116422476619559571200060016769222670118557978266602062366168,242789433733772377162253757058605232140494788666115363337105327522154016,2897090450760618154631253497246288923325478215090551806927512438699802516318766105962219562904,7372806106688864629183362019405317958359908549913588813279832042020854419620109770781392560]
plaintext = "Houdini:"

for i in range(8):
    print 's.add('+'(('+str(out[i+1])+'+('+str((out[i] * ord(plaintext[i])))+'^key+'+str(out[i+1])+'))) ^ (key*'+str(out[i])+')'+'=='+str(out[i+2])+')'

然后我们把输出的内容作为约束，但是在设key为BitVec变量时我们发现此时我们还不知道key的bit数，但是鉴于其取值范围比较小（最大为77比特），我们可以依次尝试可能的比特数，然后把解出来的key作为密钥去解密，直到解密出的内容中包含flag：

from z3 import *

def decrypt(ciphertext,key):
    out = ciphertext
    plaintext = ''
    for i in range(2,len(ciphertext)):
        p = chr((((out[i] ^ (key*out[i-2])) - out[i-1]) ^ (key+out[i-1]))//out[i-2])
        plaintext += p
    return plaintext

for i in range(0,77+1)[::-1]:
    key = BitVec('key',i)
    s = Solver()
    s.add(((42+(639792^key+42))) ^ (key*8886)==212351850074573251730471044)
    s.add(((212351850074573251730471044+(4662^key+212351850074573251730471044))) ^ (key*42)==424970871445403036476084342)
    s.add(((424970871445403036476084342+(24845166458725070452465112148^key+424970871445403036476084342))) ^ (key*212351850074573251730471044)==5074088654060645719700112791577634658478525829848)
    s.add(((5074088654060645719700112791577634658478525829848+(42497087144540303647608434200^key+5074088654060645719700112791577634658478525829848))) ^ (key*424970871445403036476084342)==17980375751459479892183878405763572663247662296)
    s.add(((17980375751459479892183878405763572663247662296+(532779308676367800568511843115651639140245212134040^key+17980375751459479892183878405763572663247662296))) ^ (key*5074088654060645719700112791577634658478525829848)==121243943296116422476619559571200060016769222670118557978266602062366168)
    s.add(((121243943296116422476619559571200060016769222670118557978266602062366168+(1977841332660542788140226624633992992957242852560^key+121243943296116422476619559571200060016769222670118557978266602062366168))) ^ (key*17980375751459479892183878405763572663247662296)==242789433733772377162253757058605232140494788666115363337105327522154016)
    s.add(((242789433733772377162253757058605232140494788666115363337105327522154016+(12730614046092224360045053754976006301760768380362448587717993216548447640^key+242789433733772377162253757058605232140494788666115363337105327522154016))) ^ (key*121243943296116422476619559571200060016769222670118557978266602062366168)==2897090450760618154631253497246288923325478215090551806927512438699802516318766105962219562904)
    s.add(((2897090450760618154631253497246288923325478215090551806927512438699802516318766105962219562904+(14081787156558797875410717909399103464148697742634691073552108996284932928^key+2897090450760618154631253497246288923325478215090551806927512438699802516318766105962219562904))) ^ (key*242789433733772377162253757058605232140494788666115363337105327522154016)==7372806106688864629183362019405317958359908549913588813279832042020854419620109770781392560)
    s.check()
    res = s.model()
    res = res[key].as_long().real
    ans = ''
    msg = open('conversation','rb').readlines()
    for i in range(1,len(msg),2):
        tmp = map(int,msg[i].split('Content: ')[1].split(' '))
        ans += decrypt(tmp,res)
    if 'watevr{' in ans:
        print ans
        break

执行脚本即可恢复出通信内容如下：

Houdini: uhm, is this thing working?

nnewram: yeah, hi

Houdini: hi nnew

Houdini: so eh, do you have it?

nnewram: id ont know what you mean

nnewram: *dont

nnewram: have what?

Houdini: :bruh:

Houdini: you know, the thing

nnewram: what, thing?

Houdini: the flag....

nnewram: oooooh

nnewram: right

nnewram: sure let me get it

nnewram: one second

Houdini: kk

nnewram: yeah here you go

nnewram: watevr{Super_Secure_Servers_are_not_always_so_secure}

Houdini: niceeeee

Houdini: thank you

Houdini: oh wait, we should probably remove the code

nnewram: yeah that's actually kinda smart

Houdini: ok cya later

nnewram: cya

在通信内容中发现flag：

watevr{Super_Secure_Servers_are_not_always_so_secure}

monkeyman

每天都有1次免费给楼主评分送学币的机会！