Hi All,

This thread was started just as the server was changed (no bilbo, you didn't

*actually* break the board ;p)

It was continued in the temp forum kindly provided by Reverse-Engineering-Community, now I copy it back to this thread for continuation.

Cheers,

Kayaker

//////////////////////////////////////////////////////////////////////////////

bilbo

Tool Request: Symbolic Boolean Algebra Bitwise Manipulator

Hello, mates,

I made this request immediately before RCE board was gone...

I hope Zero's board will no crash too...

I'm looking for a tool which can manipulate bits without knowing their values.

I've found, besides the big apps like Maple or Mathematica, other open-source apps like Yacas or Q-lang (on sourceforge), but nothing specifically devoted to Boolean Algebra.

Here is an example of what I'm talking about...

Suppose you want to evaluate the expression A^2.

In that case I will put in input (a7 a6 a5 a4 a3 a2 a1 a0) ^ (1 0)

and I will obtain in output (a7 a6 a5 a4 a3 a2 ~a1 a0).

Can you imagine the use of such a tool? Instead of trying to reverse some boolean algorithm (with intermixed boolean operators and add/sub/mult/div), which is in nearly all case impossible, I could obtain an equation for every bit of the result.

Do you think it is possible?

Thanks, bilbo

//////////////////////////////////////////////////////////////////////////////

dELTA

Except for the fact that the expressions for each bit will grow quite big after a few steps, it shouldn't be really hard to do. Can't think of seeing any specific util that does it though.

//////////////////////////////////////////////////////////////////////////////

0xf001

hi bilbo!

interesting question. i hardly use math tools (mathcad once impressed me ), for such jobs I often write small C programs but dedicated to the specific purpose. I guess you want to work "symbolic only", and then get all possibilities to reducd the number of tries or "similar?"

well, if you give some more inputs I think we can develop such thingy

so dELTA, bilbo - I have more than enough to do, but start a lillte project is always fun. what do you say?

cheers, 0xf001

PS: aahm. I must admit I do not sooo much like to develop a windows solution anymore. does that hurt?

//////////////////////////////////////////////////////////////////////////////

elfZ

I remember myself doing something like this some time ago. Not exactly boolan and bitwise, but there was some straightforward long code sequence in a (possibly crackme) which I didn't really want to dvelve into, kinda buffer manipulation or something, so the easiest way was to write a python scriptie to parse the asm listing and spit out the final results of the registers and buffer (i.e a[4] = a[3] * 5 + a[17] * 9 and stuff)

Yet I can't picture the interface for a generic tool for the tool to be useful. The situations when such an approach would be comfortable are quite different for the generic approach IMHO.

//////////////////////////////////////////////////////////////////////////////

dELTA

Quote:

so dELTA, bilbo - I have more than enough to do, but start a lillte project is always fun. what do you say?

Well, I sadly have more than more than enough to do, but anyone else may feel entirely free to do so.

//////////////////////////////////////////////////////////////////////////////

bilbo

Thanks for the answers, especially to 0xf001 for being so helpful.

The truth is that I started the project a couple of years ago (I can eventually try to dig out the sources from my hard disks and share them), but I stopped it because it was not so easy...

The application of such a toy could be enormous in crypto fields. Imagine to process a SHA-1 algorithm with this parser, knowing the final result. At the end of the process we could eventually have a system of N equations, one for each bit of the result, having as unknown variables the input bits. Obviously the equations would be extremely complicated, as dELTA stated; but could be relatively fast to find all the possible values for the input bits!!! In other words, SHA-1 would have been reversed!

So I started defining a C++ class (bit_collection) with two main methods: parse(), to resolve and simplify the bit expressions, and evaluate() to replace the literals with values 0/1, so we can check the intermediate results and debug the parser.

Why C++? Because the operators can be overloaded, and this makes very simple to describe the algorithm to be parsed.

But I got soon tangled inside the strings manipulations: I choose to represent the expressions as strings, and this was probably an error.

A stack could have been better. Yesterday I found a sample of RPN stack applied to booleans in a Google cache: h..p://66.102.9.104/search?q=cache:-vB6zpKGcPoJ:www.sunlightd.com/Projects/BooleanParse/BooleanParse.cpp.html

Even elfZ idea - processing a string in Python language - is interesting...

The biggest problem I found up to now, not yet solved, was given by additions/subtractions/multiplications/divisions. Those operations are not bitwise, and to go on in some way you have to take into account the carries and borrows from right side bit and to left side bit.

At the moment, after a raging search on Google, I'm thinking this project cannot have a solution...

But maybe the word impossible is not so correct, from an informatics point of view...

Best regards, bilbo

//////////////////////////////////////////////////////////////////////////////

naides

Hi Bilbo:

1. One tool I have found helpful, while not all encompassing to deal with problems you suggest is (urgghhh) Excel

It can perform hex to bin transforms, it can perform most if not all algebraic and boolean operations and also has an addin language (Visual basic, visual C++) in which you can code your own, more unusual functions and plug them in.

2. I once found in the net an academic article on this subject: Transforming algebraic operations into bool ops and viceversa. I will have to dig it up, it is buried in my compressed archives, but I am sure it is in one of my computers, but I know it was the dissertation of a math PhD student, 2-3 years ago.

//////////////////////////////////////////////////////////////////////////////

stingduk

yeah i was about to suggest excel but

it cant transform something above 511 to bin format

the string 101010110 blah for 511 is the max it can change

using dec2bin()

tools --> addins --> analysis toolpack (this is not added by default)

you have add it in then

all these functions pop on FX

and now to use Xor AND OR ETC you have to dig into vba

Xor doesnt work as a function And OR works as functions in the spread sheet

111111111 DEC2BIN(511)

111111111 HEX2BIN("1ff"

111111111 OCT2BIN("777"

_________________

felix qui potuit rerum cognoscere causas

//////////////////////////////////////////////////////////////////////////////

0xf001

hi all,

hmm. my opinion is c++ wold be a good if not the best choice. I know python as well and my brother is an expert in it, while I am more the perl guy for scripting languages. well, it is like perl not really slow and precompiled and powerful and esp python is a very serious language proven for years to be good and you find everything for it, but for a serious approach not to use. excel is even worse, i am sorry

you can not use it for a serious job like this. well, beeing more on linux than windows (does not mean I do not know about what I speak, I had to do fancy things in VB as well and have tons of experience in programming in nearly all flavors existing) it is a "quickhack" solution which i am sure wil turn into its limits. VB for me is a toy language, but I should not say so, as it is probably unfair and dependent on the purpose, and a flamewar I do not want to do.

But seriously we need speed and not try to f*ck VB to get things done for which it is far not designed.

You can try it and have quick some success, but are very limited in efficient data representation and handling. Efficient!

Yes you can integrate assembler, C, C++ into VB, no problem at all, but hey as I said the job is not to get VB to be able to do it, we want to do a good job and not deal with VB.

Delphi would be a far better choice if you need a click click wizard IDE

A console app can be enough, and so we can do platform independent code The gui if you need it can sit on top. And no matter whether VB, C, C++, assembler, perl/TK, GTK, KDE, MFC, blablabla you use then it is up to you. But the core in Excel - uuaaah

however, I got a little shock reading excel and VB

cheers, 0xf001

//////////////////////////////////////////////////////////////////////////////

0xf001

an addition

I hope I did not offend anybody, had much stress while posting and just wanted to give my opinion to say please let us not do this in excel / VB as I think this is not a good choice.

regards, 0xf001

//////////////////////////////////////////////////////////////////////////////

stingduk

hehe yep me too no flame war

but i would say i have done some of my keygens with excel and vba including

some old school dos apps

any way there are lot of binary num blah blah addins avl for

excel

may be taking a look into one of these addins may lead to some output

://digilander.libero.it/foxes/binum_review.htm

://digilander.libero.it/foxes/SoftwareDownload.htm

_________________

felix qui potuit rerum cognoscere causas

//////////////////////////////////////////////////////////////////////////////

0xf001

stingduk,

ok, I know and can imagine what you can do with libraries. but for what do you need excel then?

in C you say array[x] ^ array[y] voila. fast, no library call, efficient, nice.

is not it a shame to need a function to call for xor???

and if you want to write an application which can handle huge keyspace search I still think it is not good to do in excel you have to use data formats that VB understands. in C you can pointer and typecast around as you like, and make your datatypes efficient in size, usability. when VB stores strings ie in unicode there it starts

I am mainly concerned about the performance of the result and of the quirks you need to do to tell VB what you want to do ie call an XOR function. maybe i am picky, but well, i do not like to do things just "somehow" when there is a better solution i take the better solution. then I can be happy about the result

cheers, now fight back , 0xf001

PS: the question is not if it is possible in VB. the question is how the result will be (in a spreadsheet (for what), slow, pain to code), oltough I really think that you can not do in excel what bilbo really wants.

//////////////////////////////////////////////////////////////////////////////

bilbo

naides,

(1) I know people makes everything with Excel!

Someone (Vidar) can also show the Mandelbrot set! (h..p://www.vidarholen.net/contents/mandelmacro/)...

But the task we are talking about is (nearly?) impossible before starting and it is presumed to occupy huge amount of memory and cpu-time; so I think it would be better do not rely on external frameworks such as Excel or VB... stingduk pointed out also some scaring idiosyncrasies...

I would prefer more specialized applications such as Mathematica or Maple, in that case, but also them are too hungry, in terms of resources...

(2) Transforming algebraic operations into bool ops and viceversa? It sounds very interesting, but I could not find anything related on Google... Maybe I have lost a lot of that amusing jargon that people speaked at academic world and I have no more key words for researching through Google...

0xf001,

I agree in your point of view, even in your love for Linux and for console apps...

An amphibious (Linux/Windows) console app would be the best...

Perl? Python? We must first decide:

(a) if we want to go on with this (impossible?) project and, if yes, if we will parse strings or binary stacks/trees

(b) how we can bypass the carry/borrow problem

(c) who will host the project (sourceforge, woodmann?)

Best regards, bilbo

//////////////////////////////////////////////////////////////////////////////

0xf001

bilbo, I am glad somebody understands me hehe

to be honest I still did not have time to sit down and think of the problems in implementation, and also the +,-,*,/ etc problem.

also i have no real imagination yet with what kind of representation we should work. i have time in the evening and give it a brainstorm.

also to be honest I had this idea, too (but for me only about 2 months ago, wanted to do this for the last phrack release *gggggggg* ), and there realized that this is not so easy. when we work together I think we will have a chance! I was unsure and had not time to go into deep as I soon realized all the possible "maths" opcodes I would need to deal with and had not found a solution around them. and the amount of time to research, plan, test out things scared me...

so as said, I think about it and tell you what I can come up with so far

hosting should not matter. we can use any version control system, I am open, but a lazy CVS user arch rocks more I know.

from my experience sourceforge provides a damn good service (even CVS), I have one project there and love it. the question is how open you want to source

to summarize:

perl or python I think we should not use because of performance, and limits in efficient binary data handling (speed will be a matter). a compiled executable is better imho

a) impossible? i do not know. but want to try i am for binary. can be "mixed", but calculations binary -> functions can take strings, and return strings as representation, but transform to binary arrays first

b) research

c) as you like

cheeeers, 0xf001

//////////////////////////////////////////////////////////////////////////////

naides

Gentlemen,

No offense taken and no flame started.

I put forward Excel with an Urrgggghh, because its wrinkles.

I have used it for a quick hack of a relative simple problem at hand, because it is visual, and it is simple, so one does not have to re-invent the wheel from scratch every time one is faced with a problem-solving excercise. . .

If you want a more powerful, plastic, efficent and encompassing tool, then code away . . .

//////////////////////////////////////////////////////////////////////////////

bilbo

Post subject: New Perspectives...

After some researching, I've found at least two good projects on sourcefourge dealing with the initial request of this thread:

h..p://sourceforge.net/projects/qlogico/ (implemented in C++)

h..p://sourceforge.net/projects/bexpred/ (Boolean EXPRession REDucer) (in JAVA)

None of them deal with extended algebra: they do not accept in input +,-,*,/

But my initial request is (partially) satisfied.

Next step would be to introduce other algebraic operators (+,-,*,/).

I think though that we must first learn what other people have already done, first.

And since time is an issue for both of us I would suggest to wait some time before starting the project...

As for the implementative choices, 0xf001, once again, I agree with you in both cases: a compiled executable (even if BEXPRED was realized in Java), and a mixed internal representation strings/binary stack (my initial approach based on only strings was too complicated).

In the meanwhile we must also "research" about the problem of not-bitwise operators (+,-,*,/).

Best regards, and "see" you soon 0xf001

bilbo

//////////////////////////////////////////////////////////////////////////////

0xf001

naides,

when reading my posts uuups I was not in best mood it seems ahem.

well, no problem at all, I also admit to have used excel for some tasks before like calculating audio compressors *gggggggg*, so yes it is not too bad.

the thing is I have no numbers yet, but there will be huge datastructures as result and they need to be processed. Faced with VB I often ran into perfomance problems (expected, but tried anyway). well you can go further and having an ie MS-SQL server backend for the data *ggggggggg*

bilbo:

hmm. I tell you what my understanding is to see if we are talking about the same, and well I am not so expert in crypto stuff, I do not know if the tool would be able to bring an advantage faced with real encryption routines.

I thought of going through the "target" algorithm, also knowing the encrypted data. now for each instruction encountered all possible bit combinations of the input vector are stored. or you store it symbolic, does not matter. when thinking further and going through some simple algos, the number of possible input vectors increases exhaustive. I would need to go through an algo as example to compare this against full bruteforcing to see how much is won.

on the other side, I think you are talking about getting equations. can you explain that a little more?

I can probably build the equations but lacking the imagination of how to further work with them.

I know how to solve an equation system with multiple variables.

But my maths knowledge is limited

we would need to implement an "boolean/arithmetic equation solver" which takes the built equations then as input and outputs all the numeric values based on the "output vector" the encrypted block.

also I have no imagination of where comes a RPN stack in the game. I know how to work with RPN (HP calculators rock ) but all this brings me to the assumtion we are talking about sthg different, hehe

can you somehow help me with the understanding of how you want to process?

The problem with add/div, ... as long as it is "integer" I see not as problem, you get some more subtrees of modified input vectors. for all of them you need to proceed as if it was a single bit operation.

I strongly assume the advantage you see is working symbolic. When thinking of the method I had in my mind when reading my post - as I said - I do not know if this is really such a power tool compared to bruteforcing, but need to run through a real live example to be able to tell it.

I see another problem: floating point operations. uaah

cheers, 0xf001

//////////////////////////////////////////////////////////////////////////////

dELTA

The non-linear parts of more secure crypto algorithms (like e.g. the S-boxes in DES) were included to prevent the possibility to express these algorithms as equation systems, just so you know... They also make sure that the already exponential growth of the size of your expressions get a nice and big exponential base.

Like 0xf001 says, you don't have much to win on this method when it comes to real crypto algorithms, but it might indeed be useful for some serial number algos created by less mathematically gifted shareware authors though.

//////////////////////////////////////////////////////////////////////////////

bilbo

dELTA wrote:

The non-linear parts of more secure crypto algorithms (like e.g. the S-boxes in DES) were included to prevent the possibility to express these algorithms as equation systems, just so you know... They also make sure that the already exponential growth of the size of your expressions get a nice and big exponential base.

I agree with you... at least, this is the theory... But who knows that in some cases, for special input values, some flaw becomes possible?

Remember the flaw recently discovered for MD5 algorithm (google: "MD5 flaw"

.

A tool like the one we are discussing about could help in discovering such weaknesses and, yes, "it might indeed be useful for some serial number algos created by less mathematically gifted shareware authors".

0xf001 wrote:

when thinking further and going through some simple algos, the number of possible input vectors increases exhaustive. I would need to go through an algo as example to compare this against full bruteforcing to see how much is won.

You, and dELTA, are right, but remember that even for simple cases the bruteforce approach may require months and years of computations. With the symbolic approach, in my intuition, I feel that the bigger problem is not time but space. Not so bad, isn't it?

Remember the Rainbow Tables approach (google: "Rainbow tables"

0xf001 wrote:

on the other side, I think you are talking about getting equations. can you explain that a little more?

Let's see this stupid example...

We will work with 4-bits only integers, and we want to solve this "crackme" formula: A xor (A << 1) = 3

Uh? We use a simple bruteforce approach...

Code:

#include <stdio.h>

void

main(void)

{

int i;

for (i=0; i<0xF; i++)

if ((i^(i<<1)) == 3) printf("%x\n", i);

}

Oh! Just one solution is possible: 1...

Let's try now the symbolic approach:

(a3 a2 a1 a0) ^ ( (a3 a2 a1 a0) << 1 ) = (0 0 1 1) =>

(a3 a2 a1 a0) ^ (a2 a1 a0 0) = (0 0 1 1) =>

a3 ^ a2 = 0

a2 ^ a1 = 0

a1 ^ a0 = 1

a0 ^ 0 = 1

We start solving the last equation in the 4-equation system and we find a0=1

Next third equation: a1^1 = 1, so a1=0

Next second equation: a2^0=0, so a2=0

Finally first equation: a3^02=0, so a3=0

The input value which will satisfy our algorithm will be (a3 a2 a1 a0) = (0 0 0 1) = 1

In this stupid case, the bruteforce approach was surely faster; but what about more complex cases?

0xf001 wrote:

also I have no imagination of where comes a RPN stack in the game.

Have a look at sourceforge's sources...

0xf001 wrote:

The problem with add/div, ... as long as it is "integer" I see not as problem, you get some more subtrees of modified input vectors. for all of them you need to proceed as if it was a single bit operation.

I do not understand what you are saying, but I have found a rather simple solution to add one bit in term of boolean operators: it is the one-bit adder model!

If a and b are bits, a + b = (a XOR b) taking also in account a carry given by

(a AND b)

0xf001 wrote:

I see another problem: floating point operations. uaah

yup! I didn't think of it... Is coprocessor too involved in crypto algorithms

nowadays?

Regards, bilbo

//////////////////////////////////////////////////////////////////////////////

agnonymous

Hi!

Take a look at this stuff ..similar to what you want to do bilbo

I tried to use mathematica in the past...not the most natural tool for binary equations ..I don't know if mathematica 5 has improved support though

http://www.cryptosystem.net/

http://www.minrank.org/~courtois/myresearch.html

//////////////////////////////////////////////////////////////////////////////

bilbo

Hi, agnonymous, you make my nights even more sleepless!

Those links are really valuable and I started to study...

High application is required, tough...

agnonymous wrote:

I tried to use mathematica in the past...

Tried MAXIMA today (free and open source, based on TCL) but this package too is unfriendly for bitwise operations.

Thanks again for the links...

Maybe we should divulgate a little more that stuff.

I feel that only few (even if great) brains are working on it, whilst a lot of (amusing) work can be done!

bilbo

"If this method can be made to work in practice, it is a major revolution in cryptanalysis" (Nicolas T. Courtois)

//////////////////////////////////////////////////////////////////////////////

stingduk

well i am sorry to bring excel back into the topic but its just disseminating info

nothing else so no flame

i was playing with that xnumbers and binum.xla

and i see it is able to convert the unsigned content of register viz

0xffffffff to its binary equivalent string

so i just converted the above code for a test

eax^(eax shl 1)

i alloted eax == 0xffffffff

and i see it is spitting out the result like this

Quote:

a1 b1 c1

11111111111111111111111111111111 4294967295 ffffffff

a2 b2 c2

11111111111111111111111111111111 4294967295 ffffffff

d2

11111111111111111111111111111110

c5

00000000000000000000000000000001

a1=cvDecBin(B1)

a2=cvDecBin(B2)

d2=b_shl(A2,1)

c5=b_xor(A1,D2)

b1=HEX2DEC(C1)

b2=HEX2DEC(C2)

now ill see if i can force it find a result for some arbutrary value

_________________

felix qui potuit rerum cognoscere causas

//////////////////////////////////////////////////////////////////////////////

upb

yes, i support cluey 100%, with excel you could implement this project in a nice OO way, even hide it behind some strategy patterns or smth so it could work on both boolean and nonboolean functions.

//////////////////////////////////////////////////////////////////////////////

stingduk

Quote:

# 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

#

#

# 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1

# 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0

# 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1

not sure if this makes sense or not but with the above blah i am

now able to find any value for the posted algorithm on 32 bit level

ie

R32out ^ (R32out << 1) = R32in

all i have to specify is r32in

it will spit r32out

like this

Quote:

input inhex 1a2b3c4d

shl digits 1

outputinhex F619143B

input inhex deadbeef

shl digits 1

outputinhex 4A6495A5

input inhex 2badbabe

shl digits 1

outputinhex 1964966A

input inhex 1337babe

shl digits 1

outputinhex F112966A

btw how long would the above results will take to brute force

say for a given set of ten r32out

_________________

felix qui potuit rerum cognoscere causas

//////////////////////////////////////////////////////////////////////////////

bilbo

Post subject: Another example

stingduk,

i was talking about LITERAL calculations.

It does not seems you are performing it that way.

You are just teaching Excel to perform boolean calculations (correct me if I am wrong), so, to solve the given equation

Code:

A xor (A << 1) = 3

you have to bruteforce it also in Excel.

I would like to transform the given equation into a system of 4 equations (assuming again that the input range can be 0x0-0xF), at bit level:

Code:

a0 = 1

a1 = 0

a2 = 0

a3 = 0

In that way you are sure that the ONLY valid solution is 1!

Take just another example:

Code:

A*(3-A) + (3 xor A) + (2 xor A)

assuming now that the input range is 8 bits (1 byte).

This equation is solved only for ODD values of input byte A.

It would be nice to show this in a way different from bruteforcing, isn't it?

Regards, bilbo

//////////////////////////////////////////////////////////////////////////////

stingduk

hehe i donot know if this is brute force or not

i coded this

Code:

Sub blah()

a = Application.InputBox("enter the result you want", "xorshift", Type:=1)

c = Application.InputBox("enter the number to shift left", "xorshift", Type:=1)

b = binum.cvdecbin(a, 32)

Range("c4:ah4"

.FormulaArray = binum.b_cvvect(b)

If c = 1 Then

Range("ah3"

.Value = 0

Range("ah2"

.Formula = binum.b_xor(Range("ah4"

, Range("ah3"

)

For i = 33 To 3 Step -1

Cells(3, i).Value = Cells(2, i + 1).Value

Cells(2, i).Formula = binum.b_xor(Cells(4, i), Cells(3, i))

Next i

Else

MsgBox ("shit"

End If

End Sub

and i got this result

Quote:

F619143B 11110110000110010001010000111011 1 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1

EC322876 11101100001100100010100001110110 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 0

1A2B3C4D 00011010001010110011110001001101 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1

have fun

_________________

felix qui potuit rerum cognoscere causas

//////////////////////////////////////////////////////////////////////////////