PDA

View Full Version : Reversing SHR EAX,1F


captcpsc
April 30th, 2012, 20:37
OK maybe this was too hard, or stupid or something, got several views but no help so moderator feel free to delete?
------


I'm trying to figure out what some lines of assembly language would look like in a higher level language such as C but also understand the WHY the compiler optimizer would code it like this verses something more direct.

Code:

IMUL ECX <- EDX:EAX = EAX * ECX
SAR EDX, 5 <- EDX / 32
MOV EAX, EDX
SHR EAX, 1F <--- 1F being 31 doesn't this always just clear out the register?
ADD EAX, EDX <- so basically 0 + EDX
CDQ <- wipes out EDX extends EAX so EDX:EAX?


I'm finding one of the best ways to figure this stuff out is to put the code to a test? Take values and plug them in and see what happens?

SO I try to take the extremes
EAX = 7FFFFFFF
ECX = 7FFFFFFF

3FFFFFFF00000001

3FFFFFFF S
EDX:EAX = 3FFFFFFF00000001
EDX = 3FFFFFFF / 20(32 Decimal)

SAR, 5 = 1FFFFFF

SHR EAX, 1F (so 0)
ADD EAX, EDX
EAX = 1FFFFFF
CDQ -- EDX = 00000000 EAX = 01FFFFFF

however negative makes it a bit tricky.... worst case the SHR seems to leave a 1 in EAX
SO
EAX = 80000000
ECX = 7FFFFFFF

EDX:EAX = EDX:C0000000 EAX:80000000
SAR EDX, 5 - EDX:FE000000
MOV EAX, EDX
SHR EAX, 1F EAX = 1

EAX = FE000001

CDQ creates
EDX:EAX = FFFFFFFF:FE000001

So it's not any kinda absolute function or anything? I hope someone has worked this one out before or can figure it out.

naides
May 3rd, 2012, 06:22
Without going into a step by step, this piece of code is isolating the sign bit of a 32 bit variable and "sticking" it into the result. Think: how do you assure that: ( -3) * (-4) == (+12)?

captcpsc
May 3rd, 2012, 10:17
Quote:
[Originally Posted by naides;92453]Without going into a step by step, this piece of code is isolating the sign bit of a 32 bit variable and "sticking" it into the result. Think: how do you assure that: ( -3) * (-4) == (+12)?


I'm kinda a newbie to assembly so I think in this case some step by step would help? See when I take your example and apply it,

Code:
mov eax, -3
mov ecx, -4
imul ecx
sar edx, 5
shr eax, 1fh
add eax, edx
cdq
retn


after the imul instruction

EDX: 00000000
EAX: 0000000C

the sar instruction then is useless on edx, then the shr basically empties eax, because it's not negative then the add is 0 + 0... CDQ just extends EAX which again will result in no change because EDX is already 0? I'm not sure what you are saying?

Maximus
May 3rd, 2012, 11:42
the SAR instruction preserves your sign.
make +a*-b/+c, where +c is a power of 2 (>32)

captcpsc
May 3rd, 2012, 12:13
Quote:
[Originally Posted by Maximus;92455]the SAR instruction preserves your sign.
make +a*-b/+c, where +c is a power of 2 (>32)



Are you sure you don't mean the SHR instruction preserves your sign? If I do

Code:
.code
start:
mov eax, 3
mov ecx, -4
imul ecx
sar edx, 5
shr eax, 1fh
add eax, edx
cdq
retn

end start


So A = 3, B = (-4) C = 5 which is 32 (decimal) after executing the SAR instruction EDX is still FFFFFFFF
"The sar instruction shifts all the bits in the destination operand to the right one bit, replicating the H.O. bit'

so FFFFFFFF is of course 11111111111111111111111111111111 (32 of em) so SAR EDX, 5 is still going to be 11111111111111111111111111111111 or FFFFFFFF.

Maximus
May 3rd, 2012, 20:39
Try to divide by 2 a negative number with SHR.

captcpsc
May 4th, 2012, 10:05
I'm not sure I understand your repsonse maximus? The "SHR EAX, 1Fh" basically keeps the HO bit. Indicating the sign of the IMUL operation.

So playing around a little with math and such. the SAR EDX, 5 (for positve numbers) will move the lowest 5 bits. But combined with the EAX value you end up with 137, 438, 953, 472 = 1 after the SAR EDX, 5. Then since it's positive no digit is added. So you would end up with the results after CDQ of EDX:EAX 00000000:00000001

So could you start switching this back into code by doing something like

int eax = 2147483648d
int ecx = 64d

result = eax * ecx;

result = result - 137438953471 (Which of course is interesting cuz it happens to be 2^37 - 1) so
result = result - ( (2^37) - 1)

---- ok now to try and figure out negative?

Maximus
May 4th, 2012, 10:47
ah, ok.
a*b/c--->a*(b/c)==> a/d-->a*(b/c) where d=b/c

now, go on and see what happens...

captcpsc
May 4th, 2012, 11:50
Two's compliment is really messing with my head for the negatives. It seems like every (-137438953472) in the value after the imul increases the final value by -1. But how that's going to look along with the plus and no jumps or anything to be used to differentiate the positive and the negative I'm really struggling to reverse that to c or some pseudo algorithm.


Quote:
[Originally Posted by Maximus;92466]ah, ok.
a*b/c--->a*(b/c)==> a/d-->a*(b/c) where d=b/c

now, go on and see what happens...


I totally am confused.

I follow along at first a*b/c then add the parens to ensure correct order of operations. a*(b/c)

now you bring in d and make it stand for b/c

so after the ==> shouldn't it be a*d?


------ Your original response to me was

Here is the message that has just been posted:
***************
you didnt follow me:
a*b/c--->a*(b/c)

However, in such code you didnt SEE any division, right? now think how could you do a division without using a division... it is not hard. With an arithmetic shift.
Imagine you want to divide a number by say 15. You can use a div, OR you can multiply by a fraction that is EQUIVALENT to 1/15, it could be 2/30, 3/45... eventually, raising up the lower factor, you will end up in a fraction with a minimal rounding loss for the precision you are looking for.
Now, go on with your math and try to understand what happens.
***************


And yes I do understand how shifting does division :-) AND would be faster then actual assembly division as far as clock cycles etc go.

and adding the parens to enforce order of operations in this message made sense to. Also switching up the problem to make it run faster makes sense as well with the precision and fractions.

Maximus
May 4th, 2012, 15:15
aargh, you'd have to reach the solution by yourself, i didnt edit it in time -.-
well, with the original answer you have all the pieces, but that would have been your work to do :P

hint: a/b can be done as a*(1/b).

Kayaker
May 4th, 2012, 23:31
Just to mess things up further, and for something to play with, some may remember the little app by the asm guru The Svin, called Magic Divider. You enter the divisor you want and it gives you a Magic Number and a set of instructions to use it, for unsigned integers and non-fractional results.

For example, to divide X by 15, the following works

Code:

MagicNumber = 2290649225

mov eax, X
mov edx, MagicNumber
mul edx
SHR edx, 3


To divide X by 14:

Code:

MagicNumber = 2454267026

mov eax, X
mov edx, MagicNumber
inc eax
mul edx
SHR edx, 3



This thread started by The Svin introduced the app:

http://www.asmcommunity.net/board/index.php?topic=4855.0

There is some further discussion on the algo here which also mentions that the theory behind the Magic Number was mentioned in an AMD optimization manual, and there's also a link to a paper on the underlying maths involved (albeit Greek to me) - "Integer Division Using Reciprocals" by Robert Alverson.

http://www.masm32.com/board/index.php?topic=5821.0


The Svin's app with source can be downloaded here or here:

http://www.wasm.ru/tools/22/magicnumber.zip
http://apihooks.com.sweb.cz/EliCZ/import/Magic.zip

Maximus
May 11th, 2012, 15:06
Hi Kayaker,
since you're interested in magic numbers, see http://en.wikipedia.org/wiki/Fast_inverse_square_root

if i remember well, the magic number is obtained by (ab)using the logarithm relationship in order to obtain a raw approximation under log2, then later refined using newton method.

captcpsc
May 11th, 2012, 15:24
Wow? You post that and I was on that page less then a half hour ago. I find all kinda places that are more then willing to do the Magic Number even show the assembly code just like the program Kayacker posted but no one was doing a given the magic number give me the original number? Then it hit me wait if I put the magic number in then it will spit back the original? ( http://www.hackersdelight.org/magic.htm ) Well this works for lots of numbers like 5, 13 etc... But here is my code

Code:

Address Hex dump Command Comments
0046214A |. B8 555555D5 MOV EAX,D5555555
0046214F |. F7EE IMUL ESI
00462151 |. C1FA 02 SAR EDX,2
00462154 |. 8BC2 MOV EAX,EDX
00462156 |. C1E8 1F SHR EAX,1F
00462159 |. 03C2 ADD EAX,EDX
0046215B |. 8D0440 LEA EAX,[EAX*2+EAX]
0046215E |. 8D34C6 LEA ESI,[EAX*8+ESI]
00462161 |. 8BD9 MOV EBX,ECX
00462163 |. 83E1 0F AND ECX,0000000F
00462166 |. 83C1 F9 ADD ECX,-7
00462169 |. 894C24 18 MOV DWORD PTR SS:[LOCAL.9],ECX
0046216D |. 894C24 24 MOV DWORD PTR SS:[LOCAL.6],ECX


Which seems much more complex then

Code:

MagicNumber = 3616814565
mov eax,X
mov edx, MagicNumber
inc eax
mul edx
SHR edx, 4


I'm really interested in figuring out how DFFFFFFF is found and what this would have looked like before the compiler optimization?

And why can't I find a table with these anywhere? I feel like I should take one of these programs and generate a table with it?

bilbo
May 18th, 2012, 00:19
well, I don't know where you extracted the code from, but from this http://pastebin.com/zMPg6ckP ("http://pastebin.com/zMPg6ckP"), it seems to be some custom encryption/decryption algorithm...
so maybe there is no "traditional" mathematic behind it...
again, I did not studied the code because I don't know what it is intended for: compiling the decryptor from the above link gives no understable results...

Thanks to Kayaker and Maximus for your links, they deserve more attention...

Best regards, bilbo

captcpsc
May 18th, 2012, 08:37
Quote:
Thanks to Kayaker and Maximus for your links, they deserve more attention...


No doubt both are awesome and have helped me a tremendous amount. As well as increased my education on such subjects.

The code I have is from a game. The "serial protection" can be completely avoided with 1 change to the code. So as far as "hacking" it or "cracking" it whatever you want to say that's far from the issue. The issue was more in being able to reverse something to what it resembled in C++. It's a learning exercise.

Code:
AND ECX,0000000F


Simply becomes ECX = ECX % 10 (hex)(16, decimal)

But the PRETTY cool thing about compiling and optimization is a good compiler and optimizer is able to take division and various things and switch it around to faster more optimized code. MY thoughts are if I can LEARN better what the optimizer is doing for more efficient code it'll help me be a better more efficient programmer. Maybe code in a way that I take better advantages of optimization... It also of course allows me to look at other code and then reverse it and gain further understanding on how others did things and stuff. SURE reversing can be used for evil for profit to hurt a companies bottom line etc... but in a nicer pure form it's an awesome very fun way to learn stuff.

bilbo
May 19th, 2012, 11:13
I agree, and furthermore if you LEARN, all the community can learn with you, because as long as you are interested in the matter, you will be encouraged to share what you are learning with everyone.
Best regards, bilbo

Woodmann
May 19th, 2012, 23:14
Quote:
But the PRETTY cool thing about compiling and optimization is a good compiler and optimizer is able to take division and various things and switch it around to faster more optimized code. MY thoughts are if I can LEARN better what the optimizer is doing for more efficient code it'll help me be a better more efficient programmer. Maybe code in a way that I take better advantages of optimization... It also of course allows me to look at other code and then reverse it and gain further understanding on how others did things and stuff. SURE reversing can be used for evil for profit to hurt a companies bottom line etc... but in a nicer pure form it's an awesome very fun way to learn stuff.



I couldnt have said it better

Woodmann