hi, i can't upload target specific code (despite the fact that there is ~no way to identify the target from this code).. if someone wants my commented asm key validation routine, pm me..

so, now for the problem ..
my main question is: how do all the prostar reversers approach this situation because i'm stuck? also, is there a common name for this key validation technique (i.e. one better than "xor protection"?

problem:

key is of form:

XXXXX-XXXXX-XXXXX-XXXXX-XXXXX
^^^^^set #1

it is validated by a routine that does the following:

groupY = f( 5 hex characters in set Y )
groupY is 3 bytes

block = byte1, byte2, byte3, ... byte15
= group1, group2, ... group5

var_1D = byte1 ^ byte2 ^ byte3 ^ ... ^ byte14

if( byte15 == var_1D )
GOOD
else
BAD

-> need to find combination of byte1 .. byte15 that work
-> under constraint that set #i passes critera in subroutine.
-> ~500,000 possibilities for each set #i

i first tried the easy approach: set #1 == set #2 == .. == set #4
then byte13 ^ byte14 = byte15 would give you an answer
unfortunately, this case doesn't work with any valid sets

i wrote a brute forcer to get all valid sets.. i wrote one too to try with set #1 == set #2 and solve the rest.. it's still pretty ridiculous and i don't expect a solution from it

-pknight

Hello,

I'm no sure to fully understand what you mean, but we'll try anyway....

I think you are talking on a XOR encryption scheme. Even if it's
part of basic encryption scheme, it's still encryption. Don't know
if a protection using this encryption scheme have a specific
name...

I'm in trouble to understand the part where you say :

it is validated by a routine that does the following:

groupY = f( 5 hex characters in set Y )
groupY is 3 bytes

from this, i understand that the key must be of the form XXX-XXX-XXX-XXX-XXX, not XXXXX-XXXXX-XXXXX-XXXXX-XXXXX ?

anyway, about the XOR encryption, the key is :

If ((a XOR b) = c) then ((c XOR b) = a)

You can extend that mathematically, as far as i know (i'm not
a real beast in crypto....)

if you got Var15 = var_1D = byte1 ^ byte2 ^ byte3 ^ ... ^ byte14,

ithen you can compute each of the byte using the formula :

byte14 = Var15 ^ byte1 ^.... ^ byte 13

looping value for each byte1, ... byte 13 should give you all
possible byte14 for each case.....

Is that answering your question ? or i'm totally aside ?

Regards
Fox

the original key you enter is of the form
XXXXX-XXXXX-XXXXX-XXXXX-XXXXX

each XXXXX then gets mapped to a 3 byte group YYY. so, what goes into the xor's is a "key" that looks like
YYY-YYY-YYY-YYY-YYY (ignore dashes, they're just there to show 5 3-byte groups)

finding a solution to byte1 ^ byte2 ^ ... ^ byte15 is actually very easy. the problem comes from

YYY = f( XXXXX ).. not even all XXXXX make it to YYY! some are ok, some are 'filtered' (bad)

you're solution to byte1 ^ byte2 ^ ... ^ byte15 must also be a valid YYY. hrm, i've got an idea.. if i get anywhere w/ it, i'll let the messageboard know

byte1 ^ byte2 ^ ... ^ byte15 above should read
byte1 ^ byte2 ^ ... ^ byte14 = byte15

-pknight

Well, let's have a look at f(XXXXX)=YYY. Post pseudocode (i.e. if you were going to rewrite the algorithm in a language other than asm, how would you do it?)

You're looking for a collision on one byte:

sum(i=1 to 14) y_i = y_15 (*)

right? Say some fraction 0 < r < 1 of the XXXXX's are accepted. Statistics say that if f is random, you should only need to try around 256/r random X combinations before you get a match. (i.e. there's a r/256 chance that (*) holds.)

ok, i figured it out.. don't know why i didn't think of this before the first post . thanks for your replies!

the bytes were being grouped as follows:
group1 = byte1, byte2, byte3
group2 = byte4, byte5, byte6
...
group5 = byte13, byte14, byte15

from this, i needed to solve:

byte1 ^ byte2 ^ ... ^ byte15 = 0

nothing new right? ..right

if you calculate an xor for each group:
xor1 = byte1 ^ byte2 ^ byte3 = 1-byte
...
xor5 = byte13 ^ byte14 ^ byte15 = 1-byte

it is obvious there will be a many-to-one mapping for groups to xor bytes. this is because there are way more than 256 groups and there can be at most 256 unique xor bytes. so, instead of brute forcing through byte combinations byte1..byte15, i brute-forced through byte combinations xor1..xor5. e.g.

xor1 ^ xor2 ^ ... ^ xor5 = 0 (where xor_i are 1 byte)

the values that were possible for xor_i bytes were found by figuring out which XXXXX passed function f() and calculating xor_i for each. these were stored in a list, then the list was unique'd. this left 128 unique xor_i values.. not too shabby hehe

ignoring the fact that i was duping some of my efforts calculating stuff like x ^ y ^ z *and* z ^ y ^ x etc. (order doesn't matter) i let loose my 1.4ghz on it and it took 8 hours to scan the whole solution space. once i found a valid combination, i then went *back* to scan the XXXXX for ones that produced the right xor_i's.



-pknight