Z3 学习笔记

　

z3

前言

也遇到了很多使用z3解决的题，但由于没有整理，对一些api不熟悉，导致解决问题的速度很慢，所以特此做出整理。

参考API

https://z3prover.github.io/api/html/namespacez3py.html

https://ericpony.github.io/z3py-tutorial/guide-examples.htm

常见用法

初始化变量

flag = []
for i in range(49):
    flag.APPend(BitVec('flag%d' % i, 8))

创建约束求解器

solver = Solver()

添加约束条件（这一步是z3求解的关键）

olver.add(byte_610a0[v10]==i^v4)

判断解是否存在

if solver.check()==sat:

求解

print solver.model()

例题

0x0 martricks

经过一些简单的分析后，可以知道是经过偏移的矩阵乘法，本质上还是线性运算，因此可以采用z3进行解决，照着加密的过程来一遍即可。

需要注意的一点：BitVec是无符号数，Int是有符号数

from z3 import *
byte_610a0 = [0xAA, 0x7A, 0x24, 0x0A, 0xA8, 0xBC, 0x3C, 0xFC, 0x82, 0x4B, 0x51, 0x52, 0x5E, 0x1C, 0x82, 0x1F, 0x79, 0xBA, 0xB5, 0xE3, 0x43, 0x04, 0xFD, 0xAC, 0x10, 0xB5, 0x63, 0xBD, 0x8D, 0xE7, 0x35, 0xD9, 0xD3, 0xE8, 0x42, 0x6D, 0x71, 0x5A, 0x09, 0x54, 0xE9, 0x9F, 0x4C, 0xDC, 0xA2, 0xAF, 0x11, 0x87, 0x94]
byte_601060 = [0x73,0x6F,0x6D,0x65,0x20,0x6C,0x65,0x67,0x65,0x6E,0x64,0x73,0x20,0x72,0x20,0x74,0x6F,0x6C,0x64,0x2C,0x20,0x73,0x6F,0x6D,0x65,0x20,0x74,0x75,0x72,0x6E,0x20,0x74,0x6F,0x20,0x64,0x75,0x73,0x74,0x20,0x6F,0x72,0x20,0x74,0x6F,0x20,0x67,0x6F,0x6C,0x64]
# init
flag = []
for i in range(49):
    flag.append(BitVec('flag%d' % i, 8))
m1 = [BitVecVal(0, 8)]*49
m2 = [BitVecVal(0, 8)]*49
v11 = 23
for i in range(49):
    m1[v11]=flag[i]^v11
    m2[i]=byte_601060[v11]^i
    v11 = (v11+13)%49
v10 = 41
v13 = 3
v14 = 4
v7 = 5
solver = Solver()
for v5 in range(7):
    for v6 in range(7):
        v4 = BitVecVal(0, 8)
        for v8 in range(7):
            v4 += m2[7*v7+v14]*m1[7*v13+v7]
            v7 = (v7+5)%7
        i = BitVecVal(v10, 8)
        solver.add(byte_610a0[v10]==i^v4)
        v10=(v10+31)%49
        v14 = (v14+4)%7
    v13 = (v13+3)%7
flg = ''
if solver.check()==sat:
    print solver.model().sorts()
    for i in range(49):
        flg +=  chr(eval(str(solver.model().eval(flag[i]))))
    print flg

0x1

题目地址

感觉就是为了让我们练习z3而出的题，注意这里使用Int进行初始化而不是BitVec

from z3 import *
s = [Int('serial%d' % i) for i in range(20)]
solver = Solver()
solver.add(s[15] + s[4] == 10)
solver.add(s[1] * s[18] == 2 )
solver.add(s[15] / s[9] == 1)
solver.add(s[17] - s[0] == 4)
solver.add(s[5] - s[17] == -1)
solver.add(s[15] - s[1] == 5)
solver.add(s[1] * s[10] == 18)
solver.add(s[8] + s[13] == 14)
solver.add(s[18] * s[8] == 5)
solver.add(s[4] * s[11] == 0)
solver.add(s[8] + s[9] == 12)
solver.add(s[12] - s[19] == 1)
solver.add(s[9] % s[17] == 7)
solver.add(s[14] * s[16] == 40)
solver.add(s[7] - s[4] == 1)
solver.add(s[6] + s[0] == 6)
solver.add(s[2] - s[16] == 0)
solver.add(s[4] - s[6] == 1)
solver.add(s[0] % s[5] == 4)
solver.add(s[5] * s[11] == 0)
solver.add(s[10] % s[15] == 2)
solver.add(s[11] / s[3] == 0)
solver.add(s[14] - s[13] == -4)
solver.add(s[18] + s[19] == 3)
flag = []
if solver.check()==sat:
    m = solver.model()
    for i in s:
        flag.append(str(m[i]))
    print "".join(flag)
    print 'ok'

0x2

题目代码如下：

import sys
import random

key = sys.argv[1]
flag = '**CENSORED**'

assert len(key) == 13
assert max([ord(char) for char in key]) < 128
assert max([ord(char) for char in flag]) < 128

message = flag + "|" + key

encrypted = chr(random.randint(0, 128))

for i in range(0, len(message)):
  encrypted += chr((ord(messageda[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)

print(encrypted.encode('hex'))
#7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e

只需要注意一点，“|”需要初始化为Int变量

脚本如下：

from z3 import *
def read_data():
    return  "7c153a474b6a2d3f7d3f7328703e6c2d243a083e2e773c45547748667c1511333f4f745e".decode('hex')
data = read_data()
print len(data)-15
s = [Int('flag_%d' % i) for i in range(len(data)-15)]
key = [Int('key_%d' % i) for i in range(13)]
pipe = Int("pipe")
solver = Solver()
solver.add(pipe == ord("|"))
for fla in s:
    solver.add(fla >= 0)
    solver.add(fla < 128)
for ke in key:
    solver.add(ke >= 0)
    solver.add(ke < 128)
for i,c in enumerate('TWCTF{'):
    solver.add(s[i] == ord(c))
message = s+[pipe]+key
for i in range(1,len(data)):
    index = i -1
    byte = ord(data[i])
    solver.add((message[index]+key[index%13]+ord(data[index]))%128==byte)
if solver.check()==sat:
    fla = []
    m = solver.model()
    for i in s:
        fla.append(chr(int(str(m[i]))))
    print ''.join(fla)
    print 'ok'

0x3

以下摘自此博客

BitVec类型

只有BitVec变量可以进行异或

BitVecVal值之间不能进行>或<比较,只能转换成Python认识的类型才可以比较

BitVec变量值之间可进行>或<或=或>=或<=的比较

z3中不允许列表与列表之间添加==约束条件

题目:

#!/usr/bin/env python3

import base64

def encrypt(plaintext, key):
    plaintext += '|'
    plaintext += key
    key = key*(len(plaintext)//len(key))
    key += key[:len(plaintext)-len(key)]
    print len(key)
    print len(plaintext)
    cipher = ''.join(chr(ord(i)^ord(j)) for i,j in zip(plaintext, key))
    cipher = base64.b64encode(cipher.encode('ascii'))
    print cipher
    return cipher.decode('ascii')

if __name__ == '__main__':
    import sys
    key = sys.argv[1]
    plaintext = sys.argv[2]
    print(encrypt(plaintext, key))

经过分析，需要爆破出key的长度以及flag的偏移

代码如下：

from z3 import *
import base64

def encrypt(plaintext, key):
    plaintext += '|'
    plaintext += key
    key = key*(len(plaintext)//len(key))
    key += key[:len(plaintext)-len(key)]

    cipher = ''.join(chr(ord(i)^ord(j)) for i,j in zip(plaintext, key))
    cipher = base64.b64encode(cipher.encode('ascii'))
    return cipher.decode('ascii')

#z=11,y=17
ceshi_encrypted=encrypt("lalalanihaoflag{8989082399}","11122233344455566")


timu_encrypted="BCU8EGwlJzAdBjAcGCgaFxgsNyEKIy9iOBxDLwFePVtEIj1kOxBsJisnCg1jHFd4HQ0GaSYnF2wuLDIKT2MJVjxVDA5pKScQOGEuOBkGYwFMeAYLSyg3chcjYSQ0Cg9jBld4AQsZPTEgCiImYiMKBDENTCtVAgQ7ZCUCPzUnNU8aJglKK1lEBSwyNxFsKiw+GEM3AF14FxEZJy08BGwyKjACBmMHXngURAYsJTxDLS8mcR8GNxxBeAUFGD1/chAjYS44GQZjHFA5AUhLLT07DSttYjkKQy4BXzABRBgoPWhDLS0ucQIaYwRRPhBISygoPkMhOGIiGxEmBl8sHUQcLDY3QysoNDQBQzcHGCwdAUsvLTwGPzViMg4WMA0YMRtECiUochckJGImABEvDBR4AQwOaSI7BCQ1YjcAEWMcUD1VKAIrISACOCgtP08MJUh1ORsPAicgfEMEJDA0TwowSEwwEEQbOy0oBmwnLSNPFysBS3gZAR0sKGhDKi0jNhQ3Kw1nNRQDAiobJQw+JR04HDw7B0olCS0vGyceIg4QLTIsC3swTTwe"

#encrypted=ceshi_encrypted
encrypted=timu_encrypted

cipher=base64.b64decode(encrypted.encode("ascii")).decode('ascii')
length=len(cipher)
cipher=[BitVecVal(ord(each),8) for each in cipher]
plain_line=[BitVec('p%d' % i,8) for i in range(length)]
key_line=[BitVec('k%d' % i,8) for i in range(length)]
prefix=[BitVecVal(ord(each),8) for each in "flag{"]
for y in range(1,length-7+1):
    for z in range(0,length-y-7+1):
        s=Solver()
        #s.add(plain_line[z:z+5]==prefix)
        s.add(plain_line[z]==prefix[0])
        s.add(plain_line[z+1]==prefix[1])
        s.add(plain_line[z+2]==prefix[2])
        s.add(plain_line[z+3]==prefix[3])
        s.add(plain_line[z+4]==prefix[4])
        for i in range(length):
            32<=plain_line[i]
            plain_line[i]<=126
            32<=key_line[i]
            key_line[i]<=126
        plain_line[-y-1]==ord('|')
        key=plain_line[-y:]
        for i in range(length):
            s.add(key_line[i]==key[i%y])
            s.add(plain_line[i]^key_line[i]==cipher[i])
        if s.check()==sat:
            answer=s.model()
            print(answer)
            key_line="".join([chr(answer[each].as_long()) for each in key_line])
            plain_line="".join([chr(answer[each].as_long()) for each in plain_line])
            print("key_line:")
            print(key_line)
            print("plain_line:")
            print(plain_line)
            input("Congratulations!")

        else:
            print("try key len:%d,'flag{' index:%d" % (y,z))
            continue

总结

暂时就收集了这么多，后续还会继续补充！

相关阅读

新显卡驱动Y460N/Z360等机型如何鉴别独立显卡是否启用

问题描述采用optimus技术新版显卡驱动Y460N/Z360等机型如何鉴别独立显卡是否启用?问题分析新版NVIDIA显卡驱动在通知区域带有GPU