I am in the process of learning how to use z3 (I would like to use it during CTF challenges) and have hit a point where I am starting to agree with my wife's favorite saying "I need help" :) and I am posting here in the hopes that someone can review my embedded sample problem (the actual code within the CTF binary was too large and convoluted to include here) and help guide me through obtaining said help.
What I am trying to accomplish is this:
Now I have written and re-written the below code until I am blue in the face and bald from pulling all my hair out and have yet to figure out what I am doing wrong. As a sanity check I have added code that when used without z3 generates the 64 bit key I am looking for (it does not figure out what one of the list values is but shows me the final answer I want z3 to figure out).
Finally, I know that the below code is rather simplistic in z3 nature (also the code has only been designed to help support my question and therefor is not coded to release/production standards) and that I am probably missing basic concepts (after I am very new to this SMT thing) so don't be afraid to confirm my wife's theory: I'm being stoopid ;) as this is not the first time such a possible trivial thing has driven me mad for a few days (and I am sure it wont be the last).
Many thanks in advance go out to anyone who can pull my head out of the sand on this and show me the error of my ways.
BTW: The sample_func code is a python representation of the actual assembly language code from the CTF binary
from z3 import * def sample_func(pDataBuf_1, pDataBuf_2): tVar1 = pDataBuf_1 tVar2 = pDataBuf_1 xVar1 = pDataBuf_1 xVar2 = pDataBuf_1 tVar3 =( (tVar1 * 0x1000 | tVar2 >> 0x14) + xVar1 ) & 0xFFFFFFFF tVar4 =( ((tVar3 ^ xVar2) & xVar2 ^ tVar3) + xVar2 + -0x3e423112 + tVar2 ) & 0xFFFFFFFF pDataBuf_1 = tVar4 pDataBuf_1 = tVar3 # # I am adding the return value as a value for z3 to check against. What I # really want is to have z3 just operate on the bitvector values. In the real # binary these bitvector values will be used to form two 64 bit keys. # return (tVar3 << 32) | tVar4 use_z3 = False non_z3_pbuf1 = [0x67452301, 0xefcdab89] p1 = z3.BitVecVal(0x00000000, 32) # Z3 needs to figure out that p1 == 0x67452301 p2 = z3.BitVecVal(0xefcdab89, 32) tlist1 = [p1, p2] non_z3_pbuf2 = [0x79707062, 0x6d326e34] pb1 = z3.BitVecVal(0x79707062, 32) pb2 = z3.BitVecVal(0x6d326e34, 32) tlist2 = [pb1, pb2] if use_z3 == True: s = Solver() while True: s.add( sample_func(tlist1, tlist2) == 0xb97541fda15711fd) print(s) if s.check() == sat: break; else: # # Using non_z3_pbuf1 and non_z3_pbuf2 will generate the following # results: # # 0xb97541fda15711fd # 0xa15711fd # 0x6d326e34 # x = sample_func(non_z3_pbuf1, non_z3_pbuf2) print(hex(x)) print(hex(non_z3_pbuf1)) print(hex(non_z3_pbuf2))
It's much better to ask specific questions, instead of general advice. But looks like you're on the right path. In particular, you should use
print s.sexpr() where
s is the solver instance to see what z3 is trying to solve. It's hard to decipher an exact goal from your question, but here's a simple rewrite:
from z3 import * def sample_func(pDataBuf_1, pDataBuf_2): tVar1 = pDataBuf_1 tVar2 = pDataBuf_1 xVar1 = pDataBuf_1 xVar2 = pDataBuf_1 tVar3 =( (tVar1 * 0x1000 | tVar2 >> 0x14) + xVar1 ) & 0xFFFFFFFF tVar4 =( ((tVar3 ^ xVar2) & xVar2 ^ tVar3) + xVar2 + -0x3e423112 + tVar2 ) & 0xFFFFFFFF pDataBuf_1 = tVar4 pDataBuf_1 = tVar3 return (tVar3 << 32) | tVar4 p1 = BitVec('p1', 32) p2 = BitVec('p2', 32) tlist1 = [p1, p2] pb1 = BitVec('pb1', 32) pb2 = BitVec('pb2', 32) tlist2 = [pb1, pb2] s = Solver() s.add( sample_func(tlist1, tlist2) == 0xb97541fda15711fd) print s.sexpr() res = s.check() if res == sat: print s.model() else: print "Didn't get sat"
When I run this, I get:
(declare-fun p2 () (_ BitVec 32)) (declare-fun p1 () (_ BitVec 32)) (assert (let ((a!1 (bvand (bvadd (bvor (bvmul p1 #x00001000) (bvashr p2 #x00000014)) p1) #xffffffff))) (let ((a!2 (bvadd (bvxor (bvand (bvxor a!1 p2) p2) a!1) p2 #xc1bdceee p2))) (= (bvor (bvshl a!1 #x00000020) (bvand a!2 #xffffffff)) #xa15711fd)))) [p1 = 2944401152, p2 = 269336837]
Now, you should study the first part of what's printed. That's the program you "constructed" and gave to z3. It's in a lisp-like notation, but should be easy to read. One thing to notice is that the variables
pb2 never make an appearance! That's because you didn't use them in
sample_func. Is that what you intended? The next step is to study the expression printed and make sure it's really what you wanted to compute. And you can take it from there.
Finally, make sure the model z3 found (i.e.,
[p1 = 2944401152, p2 = 269336837] in this case) is really the correct answer for the program you constructed. That'll make it clear if you really meant what you wrote! (The answer will no doubt be correct; but probably not what you intended.)
In general, you should think in terms of "functions" instead of "overwriting" variables when programming with z3py. But it's best to continue on this path and specific questions as you make progress. Best of luck!
User contributions licensed under CC BY-SA 3.0