How to properly use z3 when calling a function that modifies the input

1

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:

  • I would like to pass two python lists (containing 32 bit values) into a function as function parameters.
  • Within this function I extract the function arguments and use them in some basic math routines.
  • Final calculations will be recorded back into the first python list

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[0]
    tVar2 = pDataBuf_1[1]

    xVar1 = pDataBuf_1[0]
    xVar2 = pDataBuf_1[1]


    tVar3 =(  (tVar1 * 0x1000 | tVar2 >> 0x14) + xVar1 ) & 0xFFFFFFFF
    tVar4 =(  ((tVar3 ^ xVar2) & xVar2 ^ tVar3) + xVar2 + -0x3e423112 + tVar2 ) & 0xFFFFFFFF

    pDataBuf_1[0] = tVar4
    pDataBuf_1[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[0]))
    print(hex(non_z3_pbuf2[1]))
python
z3py
ctf
asked on Stack Overflow Nov 29, 2019 by mmessuri

1 Answer

1

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[0]
    tVar2 = pDataBuf_1[1]

    xVar1 = pDataBuf_1[0]
    xVar2 = pDataBuf_1[1]


    tVar3 =(  (tVar1 * 0x1000 | tVar2 >> 0x14) + xVar1 ) & 0xFFFFFFFF
    tVar4 =(  ((tVar3 ^ xVar2) & xVar2 ^ tVar3) + xVar2 + -0x3e423112 + tVar2 ) & 0xFFFFFFFF

    pDataBuf_1[0] = tVar4
    pDataBuf_1[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 pb1 and 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!

answered on Stack Overflow Nov 29, 2019 by alias

User contributions licensed under CC BY-SA 3.0