3

I am trying to solve reverse engineering problem(s) from https://challenges.re/2/ - this is challenge 2 and the target is to get the highest possible level of understanding what the code does.

<f>:
   0:          mov    eax,DWORD PTR [esp+0x4]
   4:          bswap  eax
   6:          mov    edx,eax
   8:          and    eax,0xf0f0f0f
   d:          and    edx,0xf0f0f0f0
  13:          shr    edx,0x4
  16:          shl    eax,0x4
  19:          or     eax,edx
  1b:          mov    edx,eax
  1d:          and    eax,0x33333333
  22:          and    edx,0xcccccccc
  28:          shr    edx,0x2
  2b:          shl    eax,0x2
  2e:          or     eax,edx
  30:          mov    edx,eax
  32:          and    eax,0x55555555
  37:          and    edx,0xaaaaaaaa
  3d:          add    eax,eax
  3f:          shr    edx,1
  41:          or     eax,edx
  43:          ret

Here's my approach to solution, in comments. Because the code does not give me an initial starting point, I am assuming the initial value assignment to be 12 34 56 78:

mov    eax,DWORD PTR [esp+0x4] ; eax < 12 34 56 78 (‭305419896‬d)
bswap  eax               ; eax < 78 56 34 12
mov    edx,eax           ; eax = edx = 78 56 34 12
and    eax,0xf0f0f0f         ; eax = 02 04 06 08
and    edx,0xf0f0f0f0        ; edx = 70 50 30 10
shr    edx,0x4           ; edx = 07 05 03 01
shl    eax,0x4           ; eax = 20 40 60 80
or     eax,edx           ; eax = 27 45 63 81
mov    edx,eax           ; edx = eax = 27 45 63 81  
and    eax,0x33333333        ; eax = 23 01 23 01
and    edx,0xcccccccc        ; edx = 04 44 40 80
shr    edx,0x2           ; edx = 01 11 10 20
shl    eax,0x2           ; eax = 8C 04 8C 04
or     eax,edx           ; eax = 8D 15 9C 24
mov    edx,eax           ; eax = edx = 8D 15 9C 24
and    eax,0x55555555          ; eax = 05 15 14 04
and    edx,0xaaaaaaaa        ; edx = 88 00 88 20    
add    eax,eax           ; eax = 8D 15 9C 24
shr    edx,1             ; edx = 44 00 44 10
or     eax,edx           ; eax = CD 15 D6 34
ret                  ; return eax > CD 15 D6 34 (3440760372d)

What I still don't get is the big picture - seems like some random mathematical operations without a purpose and probably I am wrong. What gives?

  • 1
    It's probably just compiler optimizations. What might look like a simple formula to you, can look completely different when compiled. For instance, 2*8. Instead of moving 2 into a register, then 8 into another register, then performing a mul on those two values, it may just move a value into a register, then shift it left or right however many bits to end up at the same value. – dsasmblr Jul 24 '18 at 20:12
  • @dsasmblr It is optimized, the challenge author wrote it on his page. My idea is, sans optimization, is there any true purpose to this code? – Jishan Jul 24 '18 at 21:09
  • 1
    I think you're just overthinking it. This snippet of code could represent anything, like maybe an obfuscation/encryption routine. Or it could represent nothing meaningful at all, and all you need to understand is that this routine takes a value, modifies it, and returns the modified value. If you were in a much later challenge, I'd think maybe the author wants you to guess what this code looks like in C, but then you'd be studying compiler optimizations per the compiler(s) noted, etc. I think what you did is enough. =) – dsasmblr Jul 24 '18 at 22:52
4

It is a bit reversal algorithm. I am not sure if the numbers shown for the OP's examples are correct. If I start (in MS VStudios inline assembler) with 0x12345678 (as a DWORD), or

0001 0010 0011 0100 0101 0110 0111 1000

then I end up with its bit reversal, being 0x1E6A2C48, or

0001 1110 0110 1010 0010 1100 0100 1000

The algorithm looks similar to the "Generalized Bit Reversal" in the Book "Hackers Delight" by Henry S. Warren Jr., 2nd edition, on p.129 (in my pdf version), although not verified. Quote:

if (k & 1) x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;
if (k & 2) x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;
if (k & 4) x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4;
if (k & 8) x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;
if (k & 16) x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;
// The last two 'and' operations can be omitted.
| improve this answer | |
1

you probably have some error in the and operation
answer by josh is right if you start with 12345678

mov eax,DWORD PTR [esp+0x4]     eax =       12 34 56 78
bswap eax                       eax =       78 56 34 12
mov edx,eax                     edx = eax = 78 56 34 12
and eax,0x0f0f0f0f              eax =       08 06 04 02
and edx,0xf0f0f0f0              edx =       70 50 30 10
shr edx,0x4                     edx =       07 05 03 01
shl eax,0x4                     eax =       80 60 40 20
or eax,edx                      eax =       87 65 43 21
mov edx,eax                     edx =       87 65 43 21
and eax,0x33333333              eax =       03 21 03 21
and edx,0xcccccccc              edx =       84 44 40 00
shr edx,0x2                     edx =       21 11 10 00
shl eax,0x2                     eax =       0c 84 0c 84
or eax,edx                      eax =       2d 95 1c 84
mov edx,eax                     edx = eax = 2d 95 1c 84
and eax,0x55555555              eax =       05 15 14 04
and edx,0xaaaaaaaa              edx =       28 80 08 80
add eax,eax                     eax =       0a 2a 28 08
shr edx,1                       edx =       14 40 04 40
or eax,edx                      eax =       1e 6a 2c 48
ret

lets do it in say python

>>> a = 0x78563412
>>> b = 0x0f0f0f0f
>>> c = 0xf0f0f0f0
>>> d = 0x33333333
>>> e = 0xcccccccc
>>> temp = (((((a&b)<<4|(a&c)>>4)&d)<<2) | ((((a&b)<<4|(a&c)>>4)&e)>>2))
>>> hex(((temp & 0x55555555 )*2) | (temp & 0xaaaaaaaa) >> 1)
'0x1e6a2c48L'
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.