Artificial truth

The more you see, the less you believe.

[archives] [latest] | [homepage] | [atom/rss]

Defeating crp-'s collide with radare2
Fri 16 September 2016 — download

It has been a long time since my last radare2-related writeup, so I tried to fix this during the r2con (great event by the way, you should have come.), but apparently, this time, crp- wrote something really convoluted, so it took me a bit more time to get a working keygen.

Anyway, without further ado, collide, by crp- (local mirror), with radare2 (make sure to use the latest git version, or you won't have fancy things like graphs.)!

$ ./collide 
[ collide.crp- ]
stage0: FAIL

Stage0

$ r2 -A ./collide
[x] Analyze all flags starting with sym. and entry0 (aa)
[x] Analyze len bytes of instructions for references (aar)
[x] Analyze function calls (aac)
[x] Constructing a function name for fcn.* and sym.func.* functions (aan))
 -- Mind that the 'g' in radare is silent
 [0x080485ba]> pdf
  (fcn) entry0 369
            ; var int local_4h @ esp+0x4
            ; var int local_8h @ esp+0x8
            ; var int local_ch @ esp+0xc
            ; var int local_10h @ esp+0x10
            ; var int local_14h @ esp+0x14
            ; var int local_18h @ esp+0x18
            ; var int local_1ch @ esp+0x1c
            0x080485ba      83ec2c         sub esp, 0x2c
            0x080485bd      c744240c0000.  mov dword [esp + local_ch], 0
            0x080485c5      c74424080000.  mov dword [esp + local_8h], 0
            0x080485cd      83ec0c         sub esp, 0xc
            0x080485d0      68739f0408     push str.__collide.crp____n ; str.__collide.crp____n ; "[ collide.crp- ]." @ 0x8049f73
            0x080485d5      e816feffff     call sub.write_3f0
            0x080485da      83c410         add esp, 0x10
            0x080485dd      83ec0c         sub esp, 0xc
            0x080485e0      8d44241c       lea eax, [esp + local_1ch]
            0x080485e4      50             push eax
            0x080485e5      e866010000     call sub.getuid_750
            0x080485ea      83c410         add esp, 0x10
            0x080485ed      83ec0c         sub esp, 0xc
            0x080485f0      68859f0408     push str.stage0: ; str.stage0: ; "stage0: " @ 0x8049f85
            0x080485f5      e8f6fdffff     call sub.write_3f0
            0x080485fa      83c410         add esp, 0x10
            0x080485fd      83ec0c         sub esp, 0xc
            0x08048600      688e9f0408     push str..key ; str..key    ; ".key" @ 0x8049f8e
            0x08048605      e831020000     call sub.getuid_83b
            0x0804860a      83c410         add esp, 0x10
            0x0804860d      89442408       mov dword [esp + local_8h], eax
            0x08048611      837c240800     cmp dword [esp + local_8h], 0
        ┌─< 0x08048616      7505           jne 0x804861d
       ┌──< 0x08048618      e9de000000     jmp 0x80486fb
       ││   ; JMP XREF from 0x08048616 (entry0)
       │└─> 0x0804861d      83ec0c         sub esp, 0xc
           0x08048620      68939f0408     push str.OK_nstage1: ; str.OK_nstage1: ; "OK.stage1: " @ 0x8049f93
           0x08048625      e8c6fdffff     call sub.write_3f0
           0x0804862a      83c410         add esp, 0x10
           0x0804862d      83ec04         sub esp, 4
           0x08048630      8d44240c       lea eax, [esp + local_ch]
           0x08048634      50             push eax
           0x08048635      8d442414       lea eax, [esp + local_14h]
           0x08048639      50             push eax
           0x0804863a      688e9f0408     push str..key ; str..key    ; ".key" @ 0x8049f8e
           0x0804863f      e8aefeffff     call sub.malloc_4f2
           0x08048644      83c410         add esp, 0x10
           0x08048647      837c240800     cmp dword [esp + local_8h], 0
       │┌─< 0x0804864c      7f05           jg 0x8048653
      ┌───< 0x0804864e      e9a8000000     jmp 0x80486fb
      │││   ; JMP XREF from 0x0804864c (entry0)
      ││└─> 0x08048653      83ec08         sub esp, 8
      ││    0x08048656      ff742410       push dword [esp + local_10h]
      ││    0x0804865a      ff742418       push dword [esp + local_18h]
      ││    0x0804865e      e80dfeffff     call fcn.08048470
      ││    0x08048663      83c410         add esp, 0x10
      ││    0x08048666      85c0           test eax, eax
      ││┌─< 0x08048668      7431           je 0x804869b
      │││   0x0804866a      83ec0c         sub esp, 0xc
      │││   0x0804866d      689f9f0408     push str.___re.....___ ; str.___re.....___ ; "-- re..... -- " @ 0x8049f9f
      │││   0x08048672      e879fdffff     call sub.write_3f0
      │││   0x08048677      83c410         add esp, 0x10
      │││   0x0804867a      c74424040000.  mov dword [esp + local_4h], 0
      │││   ; JMP XREF from 0x08048699 (entry0)
     ┌────> 0x08048682      817c2404d307.  cmp dword [esp + local_4h], 0x7d3
    ┌─────< 0x0804868a      7e02           jle 0x804868e
   ┌──────< 0x0804868c      eb6d           jmp 0x80486fb
   ││││││   ; JMP XREF from 0x0804868a (entry0)
   │└─────> 0x0804868e      e885fdffff     call fcn.08048418
    ││││   0x08048693      8d442404       lea eax, [esp + local_4h]
    ││││   0x08048697      ff00           inc dword [eax]
    └────< 0x08048699      ebe7           jmp 0x8048682
     │││   ; JMP XREF from 0x08048668 (entry0)
     ││└─> 0x0804869b      837c240800     cmp dword [esp + local_8h], 0
     ││┌─< 0x080486a0      7e59           jle 0x80486fb
     │││   0x080486a2      83ec04         sub esp, 4
     │││   0x080486a5      8d442414       lea eax, [esp + local_14h]
     │││   0x080486a9      50             push eax
     │││   0x080486aa      ff742410       push dword [esp + local_10h]
     │││   0x080486ae      ff742418       push dword [esp + local_18h]
     │││   0x080486b2      e814020000     call sub.memcpy_8cb
     │││   0x080486b7      83c410         add esp, 0x10
     │││   0x080486ba      85c0           test eax, eax
    ┌────< 0x080486bc      7502           jne 0x80486c0
   │┌─────< 0x080486be      eb3b           jmp 0x80486fb
   ││││││   ; JMP XREF from 0x080486bc (entry0)
   ││└────> 0x080486c0      83ec0c         sub esp, 0xc
   ││ │││   0x080486c3      68ae9f0408     push str.OK_nstage2: ; str.OK_nstage2: ; "OK.stage2: " @ 0x8049fae
   ││ │││   0x080486c8      e823fdffff     call sub.write_3f0
   ││ │││   0x080486cd      83c410         add esp, 0x10
   ││ │││   0x080486d0      83ec08         sub esp, 8
   ││ │││   0x080486d3      ff742410       push dword [esp + local_10h]
   ││ │││   0x080486d7      ff742418       push dword [esp + local_18h]
   ││ │││   0x080486db      e8d6030000     call fcn.08048ab6
   ││ │││   0x080486e0      83c410         add esp, 0x10
   ││ │││   0x080486e3      85c0           test eax, eax
   ││┌────< 0x080486e5      7502           jne 0x80486e9
  ┌───────< 0x080486e7      eb12           jmp 0x80486fb
  │││││││   ; JMP XREF from 0x080486e5 (entry0)
  │││└────> 0x080486e9      83ec0c         sub esp, 0xc
  │││ │││   0x080486ec      68ba9f0408     push str.OK_n__key_accepted___n ; str.OK_n__key_accepted___n ; "OK.[ key accepted ]." @ 0x8049fba
  │││ │││   0x080486f1      e8fafcffff     call sub.write_3f0
  │││ │││   0x080486f6      83c410         add esp, 0x10
  │││┌────< 0x080486f9      eb10           jmp 0x804870b
  │││││││   ; XREFS: JMP 0x080486e7  JMP 0x080486be  JMP 0x0804868c  JMP 0x0804864e  JMP 0x08048618  JMP 0x080486a0  
  └└└─└└└─> 0x080486fb      83ec0c         sub esp, 0xc
           0x080486fe      68cf9f0408     push str.FAILED_n ; str.FAILED_n ; "FAILED." @ 0x8049fcf
           0x08048703      e8e8fcffff     call sub.write_3f0
           0x08048708      83c410         add esp, 0x10
           ; JMP XREF from 0x080486f9 (entry0)
     └────> 0x0804870b      837c240c00     cmp dword [esp + local_ch], 0
        ┌─< 0x08048710      740f           je 0x8048721
           0x08048712      83ec0c         sub esp, 0xc
           0x08048715      ff742418       push dword [esp + local_18h]
           0x08048719      e892fcffff     call sym.imp.free
           0x0804871e      83c410         add esp, 0x10
           ; JMP XREF from 0x08048710 (entry0)
        └─> 0x08048721      83ec0c         sub esp, 0xc
            0x08048724      6a00           push 0
            0x08048726      e8a5fcffff     call sym.imp._exit
 [0x080485ba]> 

Ok, this is a bit long. It seems that the sub.write_3f0 function is always called after strings, so it's likely some kind of puts():

[0x080485ba]> pdf @ sub.write_3f0
            ;-- section_end..plt:
            ;-- section..text:
 (fcn) sub.write_3f0 40
           ; XREFS: CALL 0x080485d5  CALL 0x080485f5  CALL 0x08048625  CALL 0x08048703  CALL 0x080486c8  CALL 0x080486f1  CALL 0x08048672  
           0x080483f0      83ec0c         sub esp, 0xc                ; [9] va=0x080483f0 pa=0x000003f0 sz=7017 vsz=7017 rwx=--r-x .text
           0x080483f3      83ec04         sub esp, 4
           0x080483f6      83ec08         sub esp, 8
           0x080483f9      ff74241c       push dword [esp + 0x1c]
           0x080483fd      e89e1a0000     call fcn.08049ea0
           0x08048402      83c40c         add esp, 0xc
           0x08048405      50             push eax
           0x08048406      ff742418       push dword [esp + 0x18]
           0x0804840a      6a01           push 1
           0x0804840c      e81fffffff     call sym.imp.write
           0x08048411      83c410         add esp, 0x10
           0x08048414      83c40c         add esp, 0xc
           0x08048417      c3             ret
[0x080485ba]> pdf @ fcn.08049ea0
 (fcn) fcn.08049ea0 38
           ; CALL XREF from 0x080483fd (sub.write_3f0)
           ; CALL XREF from 0x08048491 (fcn.08048470)
           ; CALL XREF from 0x080484a7 (fcn.08048470)
           0x08049ea0      83ec04         sub esp, 4
           0x08049ea3      c70424000000.  mov dword [esp], 0
           ; JMP XREF from 0x08049ebd (fcn.08049ea0)
       ┌─> 0x08049eaa      8b442408       mov eax, dword [esp + 8]    ; [0x8:4]=0
          0x08049eae      803800         cmp byte [eax], 0
      ┌──< 0x08049eb1      7502           jne 0x8049eb5
     ┌───< 0x08049eb3      eb0a           jmp 0x8049ebf
     │││   ; JMP XREF from 0x08049eb1 (fcn.08049ea0)
     │└──> 0x08049eb5      89e0           mov eax, esp
         0x08049eb7      ff00           inc dword [eax]
         0x08049eb9      ff442408       inc dword [esp + 8]
      └─< 0x08049ebd      ebeb           jmp 0x8049eaa
          ; JMP XREF from 0x08049eb3 (fcn.08049ea0)
     └───> 0x08049ebf      8b0424         mov eax, dword [esp]
           0x08049ec2      83c404         add esp, 4
           0x08049ec5      c3             ret
[0x080485ba]> 

The subfunction fcn.08049ea0 looks like a strlen. When you take a look at the graph view (by typing VV), it becomes obvious:

[0x08049ea0]> VV @ fcn.08049ea0

      =-----------------------=
      |  0x8049ea0            |
      | (fcn) fcn.08049ea0 38 |
      | sub esp, 4            |
      | mov dword [esp], 0    |
      =-----------------------=
               v
               '
               |
               .--------------------------.
      =--------------------------=   =----------------------=
      |  0x8049eaa               |   |  0x8049eb5           |
      | mov eax, dword [esp + 8] |   | mov eax, esp         |
      | cmp byte [eax], 0        |   | inc dword [eax]      |
      | jne 0x8049eb5 ;[a]       |   | inc dword [esp + 8]  |
      =--------------------------=   | jmp 0x8049eaa ;[c]   |
               f      t              =----------------------=
               '      |                   ^
               |      `-------------------'
      =-----------------------=
      | [0x8049eb3]           |
      | jmp 0x8049ebf ;[b]    |
      =-----------------------=
               v
               '
               |
      =----------------------=
      |  0x8049ebf           |
      | mov eax, dword [esp] |
      | add esp, 4           |
      | ret                  |
      =----------------------=

It's using a local variable as a counter (in [esp]), and returns its value when a 0 (aka NULL) is met.

So radare2 managed to correctly hint us with the name of the function, sub.write_3f0, it's effectively a wrapper to write.

Then, there is a call to sub.getuid_750 at 0x080485e5:

[0x080485ba]> pdf @ sub.getuid_750
 (fcn) sub.getuid_750 235
           0x08048750      83ec1c         sub esp, 0x1c
           0x08048753      83ec0c         sub esp, 0xc
           0x08048756      83ec04         sub esp, 4
           0x08048759      e812fcffff     call sym.imp.getuid
           0x0804875e      83c404         add esp, 4
           0x08048761      50             push eax
           0x08048762      e8d9fbffff     call sym.imp.getpwuid
           0x08048767      83c410         add esp, 0x10
           0x0804876a      89442414       mov dword [esp + 0x14], eax
           0x0804876e      837c241400     cmp dword [esp + 0x14], 0
       ┌─< 0x08048773      750d           jne 0x8048782            
          0x08048775      c744240c0000.  mov dword [esp + 0xc], 0
      ┌──< 0x0804877d      e9b1000000     jmp 0x8048833          
      │└─> 0x08048782      c74424186300.  mov dword [esp + 0x18], 0x63
          0x0804878a      8b442414       mov eax, dword [esp + 0x14]
          0x0804878e      8b00           mov eax, dword [eax]  
          0x08048790      89442410       mov dword [esp + 0x10], eax
      │┌─> 0x08048794      8b442410       mov eax, dword [esp + 0x10]
      ││   0x08048798      803800         cmp byte [eax], 0
     ┌───< 0x0804879b      7502           jne 0x804879f
    ┌────< 0x0804879d      eb43           jmp 0x80487e2
    │└───> 0x0804879f      8b442410       mov eax, dword [esp + 0x10]
     ││   0x080487a3      0fbe10         movsx edx, byte [eax]
     ││   0x080487a6      8b442418       mov eax, dword [esp + 0x18]
     ││   0x080487aa      0fafc2         imul eax, edx
     ││   0x080487ad      89442418       mov dword [esp + 0x18], eax
     ││   0x080487b1      8d442418       lea eax, [esp + 0x18]
     ││   0x080487b5      c13803         sar dword [eax], 3
     ││   0x080487b8      8b442410       mov eax, dword [esp + 0x10]
     ││   0x080487bc      0fbe10         movsx edx, byte [eax]
     ││   0x080487bf      8d442418       lea eax, [esp + 0x18]
     ││   0x080487c3      3110           xor dword [eax], edx
    │┌───> 0x080487c5      8b442418       mov eax, dword [esp + 0x18]
    ││││   0x080487c9      83e003         and eax, 3
    ││││   0x080487cc      85c0           test eax, eax
   ┌─────< 0x080487ce      7502           jne 0x80487d2
  ┌──────< 0x080487d0      eb08           jmp 0x80487da
  │└─────> 0x080487d2      8d442418       lea eax, [esp + 0x18]
   ││││   0x080487d6      d120           shl dword [eax], 1
   │└───< 0x080487d8      ebeb           jmp 0x80487c5
  └──────> 0x080487da      8d442410       lea eax, [esp + 0x10]
     ││   0x080487de      ff00           inc dword [eax]
     │└─< 0x080487e0      ebb2           jmp 0x8048794
    └────> 0x080487e2      8b442414       mov eax, dword [esp + 0x14]
          0x080487e6      8b4008         mov eax, dword [eax + 8]
          0x080487e9      83e001         and eax, 1
          0x080487ec      8d1400         lea edx, [eax + eax]
          0x080487ef      8d442418       lea eax, [esp + 0x18]
          0x080487f3      0110           add dword [eax], edx
          0x080487f5      8b442414       mov eax, dword [esp + 0x14]
          0x080487f9      8b500c         mov edx, dword [eax + 0xc]
          0x080487fc      83e201         and edx, 1
          0x080487ff      8d442418       lea eax, [esp + 0x18]
          0x08048803      0110           add dword [eax], edx
          0x08048805      8b542420       mov edx, dword [esp + 0x20]
          0x08048809      8b442414       mov eax, dword [esp + 0x14]
          0x0804880d      8b4008         mov eax, dword [eax + 8]
          0x08048810      8902           mov dword [edx], eax
          0x08048812      8b542420       mov edx, dword [esp + 0x20]
          0x08048816      8b442414       mov eax, dword [esp + 0x14]
          0x0804881a      8b400c         mov eax, dword [eax + 0xc]
          0x0804881d      894204         mov dword [edx + 4], eax
          0x08048820      8b542420       mov edx, dword [esp + 0x20]
          0x08048824      8b442418       mov eax, dword [esp + 0x18]
          0x08048828      894208         mov dword [edx + 8], eax
          0x0804882b      c744240c0100.  mov dword [esp + 0xc], 1
      └──> 0x08048833      8b44240c       mov eax, dword [esp + 0xc]
           0x08048837      83c41c         add esp, 0x1c
           0x0804883a      c3             ret
[0x080485ba]> 

Err, something long, with computations: graph view to the rescue!

                                             =------------------------------=
                                             | [0x8048750]                  |
                                             | (fcn) sub.getuid_750 235     |
                                             | sub esp, 0x1c                |
                                             | sub esp, 0xc                 |
                                             | sub esp, 4                   |
                                             | call sym.imp.getuid ;[a]     |
                                             | add esp, 4                   |
                                             | push eax                     |
                                             | call sym.imp.getpwuid ;[b]   |
                                             | add esp, 0x10                |
                                             | mov dword [esp + 0x14], eax  |
                                             | cmp dword [esp + 0x14], 0    |
                                             | jne 0x8048782 ;[c]           |
                                             =------------------------------=
                                                             t f
                             .-------------------------------' '-------------------.
                             |                                                     |
                       =------------------------------=          =--------------------------=
                       |  0x8048782                   |          |  0x8048775               |
                       | mov dword [esp + 0x18], 0x63 |          | mov dword [esp + 0xc], 0 |
                       | mov eax, dword [esp + 0x14]  |          | jmp 0x8048833 ;[j]       |
                       | mov eax, dword [eax]         |          =--------------------------=
                       | mov dword [esp + 0x10], eax  |                            v
                       =------------------------------=                            |
                            v                                                      |
 .------------------------. |                                                      |
 |                      =-----------------------------=                            |
 |                      |  0x8048794                  |                            |
 |                      | mov eax, dword [esp + 0x10] |                            |
 |                      | cmp byte [eax], 0           |                            |
 |                      | jne 0x804879f ;[h]          |                            |
 |                      =-----------------------------=                            |
 |                            t f                                                  |
 |               .------------' '------------------------------.                   |
 |               |                                             |                   |
 |         =------------------------------=            =--------------------=      |
 |         |  0x804879f                   |            |  0x804879d         |      |
 |         | mov eax, dword [esp + 0x10]  |            | jmp 0x80487e2 ;[i] |      |
 |         | movsx edx, byte [eax]        |            =--------------------=      |
 |         | mov eax, dword [esp + 0x18]  |                    v                   |
 |         | imul eax, edx                |                    |                   |
 |         | mov dword [esp + 0x18], eax  |     =------------------------------=   |
 |         | lea eax, [esp + 0x18]        |     |  0x80487e2                   |   |
 |         | sar dword [eax], 3           |     | mov eax, dword [esp + 0x14]  |   |
 |         | mov eax, dword [esp + 0x10]  |     | mov eax, dword [eax + 8]     |   |
 |         | movsx edx, byte [eax]        |     | and eax, 1                   |   |
 |         | lea eax, [esp + 0x18]        |     | lea edx, [eax + eax]         |   |
 |         | xor dword [eax], edx         |     | lea eax, [esp + 0x18]        |   |
 |         =------------------------------=     | add dword [eax], edx         |   |
 |              v                               | mov eax, dword [esp + 0x14]  |   |
 |              '                               | mov edx, dword [eax + 0xc]   |   |
 |              |                               | and edx, 1                   |   |
 | .------------.                               | lea eax, [esp + 0x18]        |   |
 | |        =-----------------------------=     | add dword [eax], edx         |   |
 | |        |  0x80487c5                  |     | mov edx, dword [esp + 0x20]  |   |
 | |        | mov eax, dword [esp + 0x18] |     | mov eax, dword [esp + 0x14]  |   |
 | |        | and eax, 3                  |     | mov eax, dword [eax + 8]     |   |
 | |        | test eax, eax               |     | mov dword [edx], eax         |   |
 | |        | jne 0x80487d2 ;[e]          |     | mov edx, dword [esp + 0x20]  |   |
 | |        =-----------------------------=     | mov eax, dword [esp + 0x14]  |   |
 | |              t f                           | mov eax, dword [eax + 0xc]   |   |
 | |              | |                           | mov dword [edx + 4], eax     |   |
 | |              | |                           | mov edx, dword [esp + 0x20]  |   |
 | |              | '-----------------.         | mov eax, dword [esp + 0x18]  |   |
 | |              |                   |         | mov dword [edx + 8], eax     |   |
 | |              |                   |         | mov dword [esp + 0xc], 1     |   |
 | |              |                   |         =------------------------------=   |
 | |              |                   |                        |                   |
 | | =-----------------------= =--------------------=          |                   |
 | | |  0x80487d2            | |  0x80487d0         |          |                   |
 | | | lea eax, [esp + 0x18] | | jmp 0x80487da ;[f] |          '-------.-----------'
 | | | shl dword [eax], 1    | =--------------------=                  |             
 | | | jmp 0x80487c5 ;[d]    |        v                                |
 | | =-----------------------=        |                                |
 | `-------'                      =-----------------------=  =----------------------------= 
 |                                |  0x80487da            |  |  0x8048833                 |
 |                                | lea eax, [esp + 0x10] |  | mov eax, dword [esp + 0xc] |
 |                                | inc dword [eax]       |  | add esp, 0x1c              |
 |                                | jmp 0x8048794 ;[g]    |  | ret                        |                          
 |                                =-----------------------=  =----------------------------=
 `-------------------------------------'

It's a bit better. The first node is calling getpwuid, and if there is an error, it'll put 0 into [esp + 0xc], and go to the end of the function, that put [esp + 0xc] into eax, the return value, so this is likely the error handling path.

The branch on the left, 0x8048782, will put the constant 0x63 at [esp + 0x18], and the first member (char* pw_name, aka the current username) of the structure returned by getpwuid is put at [esp + 0x10].

Then, we have two nested loops:

  1. The first one will iterate over every letter of the current username, and on each cycle it will do something like value = (([esp + 0x10] *) current_pw_name_letter) >> 3) ^ current_pw_name_letter, in the 0x804879f block.
  2. The second loop will set value to value << 1 as long as value & 3 is different from zero.

This could be translated, in C, as:

for (uint32_t value = 63; *pw_name; pw_name++) {
    value = (((value * *pw_name) >> 3) ^ *pw_name);
    while (value & 3) {
        value = value << 1;
    }
}

The last block before the function is returning (at 0x80487e2) is getting the aforementioned return value of getpwuid, stored at [esp + 0x14], accessing the third field (pw_uid, aka user id), and'ing it with 1, multiplying it by two, adding it to our value variable, and finally and'ing the third field (pw_gid, aka current gid) with 1, and adding it too. This can be summarised as value = value + (pw_uid & 1) * 2 + (pw_gid & 1). And finally, it sets eax to one, and returns. Our value variable isn't returned nor used? What is going on?

If you take a close look at 0x080485e0, you'll see this:

[0x080485ba]> pd 3 @ 0x080485e0
           0x080485e0      8d44241c       lea eax, [esp + local_1ch]  ; 0x1c
           0x080485e4      50             push eax
           0x080485e5      e866010000     call sub.getuid_750
[0x080485ba]> 

The program is passing a variable by reference to the function, so maybe it's worth looking again at what's happening in the last bloc of 0x80487e2, where it's dealing with the stack, moving values around and pointing to others…

It seems indeed that the last part of the bloc is setting the fields of the structure passed to sub.getuid_750 to {pw_uid, pw_gid, value} ; So this structure will likely be used somewhere else.

The next called function is 0x80483f0, with the parameter .key.

[0x080485ba]> pdf @ sub.write_3f0
 (fcn) sub.write_3f0 40
           0x080483f0      83ec0c         sub esp, 0xc
           0x080483f3      83ec04         sub esp, 4
           0x080483f6      83ec08         sub esp, 8
           0x080483f9      ff74241c       push dword [esp + 0x1c]
           0x080483fd      e89e1a0000     call fcn.08049ea0
           0x08048402      83c40c         add esp, 0xc
           0x08048405      50             push eax
           0x08048406      ff742418       push dword [esp + 0x18]
           0x0804840a      6a01           push 1
           0x0804840c      e81fffffff     call sym.imp.write
           0x08048411      83c410         add esp, 0x10
           0x08048414      83c40c         add esp, 0xc
           0x08048417      c3             ret
[0x080485ba]> 

It's calling fcn.08049ea0, then writes something on stdout.

                                        =---------------------------------=
                                        |  0x804883b                      |
                                        | (fcn) sub.getuid_83b 144        |
                                        | ; var int local_ch @ esp+0xc    |
                                        | ; var int local_18h @ esp+0x18  |
                                        | ; var int local_20h @ esp+0x20  |
                                        | ; var int local_28h @ esp+0x28  |
                                        | ; var int local_2ch @ esp+0x2c  |
                                        | ; var int local_3ch @ esp+0x3c  |
                                        | ; var int local_8ch @ esp+0x8c  |
                                        | sub esp, 0x7c                   |
                                        | sub esp, 8                      |
                                        | lea eax, [esp + local_18h]      |
                                        | push eax                        |
                                        | push dword [esp + local_8ch]    |
                                        | call sub.__lxstat_f20 ;[a]      |
                                        | add esp, 0x10                   |
                                        | test eax, eax                   |
                                        | jne 0x80488b1 ;[b]              |
                                        =---------------------------------=
                                                        f t
                                        .---------------' '-------------------.
                                        |                                     |
                                =---------------------------------------=     |
                                |  0x8048859                            |     |
                                | cmp dword [esp + local_3ch], 0x800000 |     |
                                | jg 0x80488b1 ;[b]                     |     |
                                =---------------------------------------=     |
                                        f t                                   |
                                      .-' '-----------------------------.     |
                                      |                                 |     |
                              =-----------------------------------=     |     |
                              |  0x8048863                        |     |     |
                              | call sym.imp.getuid ;[c]          |     |     |
                              | cmp dword [esp + local_28h], eax  |     |     |
                              | jne 0x80488b1 ;[b]                |     |     |
                              =-----------------------------------=     |     |
                                      f t                               |     |
                                .-----' '-------------------------.     |     |
                                |                                 |     |     |
                        =-----------------------------------=     |     |     |
                        |  0x804886e                        |     |     |     |
                        | call sym.imp.getgid ;[d]          |     |     |     |
                        | cmp dword [esp + local_2ch], eax  |     |     |     |
                        | jne 0x80488b1 ;[b]                |     |     |     |
                        =-----------------------------------=     |     |     |
                                f t                               |     |     |
                          .-----' '-------------------------.     |     |     |
                          |                                 |     |     |     |
                  =----------------------------------=      |     |     |     |
                  |  0x8048879                       |      |     |     |     |
                  | mov eax, dword [esp + local_20h] |      |     |     |     |
                  | and eax, 0xf000                  |      |     |     |     |
                  | cmp eax, 0x8000                  |      |     |     |     |
                  | jne 0x80488b1 ;[b]               |      |     |     |     |
                  =----------------------------------=      |     |     |     |
                          f t                               |     |     |     |
                    .-----' '-------------------------.     |     |     |     |
                    |                                 |     |     |     |     |
            =----------------------------------=      |     |     |     |     |
            |  0x8048889                       |      |     |     |     |     |
            | mov eax, dword [esp + local_20h] |      |     |     |     |     |
            | and eax, 0x38                    |      |     |     |     |     |
            | test eax, eax                    |      |     |     |     |     |
            | jne 0x80488b1 ;[b]               |      |     |     |     |     |
            =----------------------------------=      |     |     |     |     |
                    f t                               |     |     |     |     |
              .-----' '-------------------------.     |     |     |     |     |
              |                                 |     |     |     |     |     |
      =----------------------------------=      |     |     |     |     |     |
      |  0x8048894                       |      |     |     |     |     |     |
      | mov eax, dword [esp + local_20h] |      |     |     |     |     |     |
      | and eax, 7                       |      |     |     |     |     |     |
      | test eax, eax                    |      |     |     |     |     |     |
      | jne 0x80488b1 ;[b]               |      |     |     |     |     |     |
      =----------------------------------=      |     |     |     |     |     |
              f t                               |     |     |     |     |     |
        .-----' '-------------------------.     |     |     |     |     |     |
        |                                 |     |     |     |     |     |     |
=----------------------------------=      |     |     |     |     |     |     |
|  0x804889f                       |      |     |     |     |     |     |     |
| mov eax, dword [esp + local_20h] |      |     |     |     |     |     |     |
| and eax, 0x1c0                   |      |     |     |     |     |     |     |
| cmp eax, 0x100                   |      |     |     |     |     |     |     |
| jne 0x80488b1 ;[b]               |      |     |     |     |     |     |     |
=----------------------------------=      |     |     |     |     |     |     |
        f    t                            |     |     |     |     |     |     |
        '    '--------------.             '--.--'-----'-----'-----'-----'-----'
        |                   |                |
=--------------------=  =-------------------------------=
|  0x80488af         |  |  0x80488b1                    |
| jmp 0x80488bb ;[e] |  | mov dword [esp + local_ch], 0 |
=--------------------=  | jmp 0x80488c3 ;[f]            |
    v                   =-------------------------------=
    |                                   v
=----------------------------------=    '
|  0x80488bb                       |    |
| mov eax, dword [esp + local_3ch] |    |
| mov dword [esp + local_ch], eax  |    |
=----------------------------------=    |
    v                                   |
    |-----------------------------------'
    |
=---------------------------------=
| [0x80488c3]                     |
| mov eax, dword [esp + local_ch] |
| add esp, 0x7c                   |
| ret                             |
=---------------------------------=

Looks like a series of tests.

[0x080485ba]> pdf @ sub.__lxstat_f20 
 (fcn) sub.__lxstat_f20 53
           ; var int local_4h @ ebp-0x4
           ; arg int arg_8h @ ebp+0x8
           ; arg int arg_ch @ ebp+0xc
           ; CALL XREF from 0x0804884d (sub.getuid_83b)
           0x08049f20      55             push ebp
           0x08049f21      89e5           mov ebp, esp
           0x08049f23      83ec10         sub esp, 0x10
           0x08049f26      895dfc         mov dword [ebp - local_4h], ebx
           0x08049f29      8b550c         mov edx, dword [ebp + arg_ch] ; [0xc:4]=0
           0x08049f2c      e824000000     call fcn.08049f55
           0x08049f31      81c36f010000   add ebx, 0x16f
           0x08049f37      c70424030000.  mov dword [esp], 3
           0x08049f3e      89542408       mov dword [esp + 8], edx
           0x08049f42      8b5508         mov edx, dword [ebp + arg_8h] ; [0x8:4]=0
           0x08049f45      89542404       mov dword [esp + 4], edx
           0x08049f49      e812e4ffff     call sym.imp.__lxstat
           0x08049f4e      8b5dfc         mov ebx, dword [ebp - local_4h]
           0x08049f51      89ec           mov esp, ebp
           0x08049f53      5d             pop ebp
           0x08049f54      c3             ret
[0x080485ba]> pdf @ fcn.08049f55
 (fcn) fcn.08049f55 4
           ; CALL XREF from 0x08049f2c (sub.__lxstat_f20)
           0x08049f55      8b1c24         mov ebx, dword [esp]
           0x08049f58      c3             ret
[0x080485ba]> 

It seems that sub.__lxstat_f20 is a simple wrapper around lxstat. You may want to read its manpage to know what are the fields of the structure that it returns.

Our cascade of tests function that will:

  1. Call lxstat and check that there is no error.
  2. Check that the file is owned by the current user.
  3. Check that the file is owned by the current group.
  4. Check that the file is a regular file (Check the implementation of S_ISREG for details, or simply the manpage of lstat.).
  5. Check that the file is has rights & 0x38 != 0 and rights & 0x7 != 0 rights & 0x1c0 != 0x100, meaning that the file should be 0400, aka only readable by the current user.

If all those conditions are met, the function will return the size of the file, else, it will return zero.

Here it's easy to know what fields of the stat structure are accessed, because everything is done relatively to esp, you only have to know the size of the different fields.

You can of course show those field by doing dynamic analysis:

$e r2 -A -d ./collide
Process with PID 11188 started...
attach 11188 11188
bin.baddr 0x08048000
Assuming filepath ./collide
asm.bits 32
[x] Analyze all flags starting with sym. and entry0 (aa)
[x] Analyze len bytes of instructions for references (aar)
[x] Analyze function calls (aac)
[x] Constructing a function name for fcn.* and sym.func.* functions (aan))
 -- Have you seen the latest radare2 TV spot?
[0xf776dac0]> db 0x08048852
[0xf776dac0]> dc
[ collide.crp- ]
stage0: hit breakpoint at: 8048852
attach 11188 1
[0x08048852]> pf w::ioiiii::w st_dev st_ino st_mode st_nlink st_uid st_gid
st_rdev st_size @ (esp + 34)
   st_dev : 0xffbc9616 = 0x0000
   st_ino : 0xffbc9620 = 5641011
  st_mode : 0xffbc9624 = (octal)  000100664
 st_nlink : 0xffbc9628 = 1
   st_uid : 0xffbc962c = 1000
   st_gid : 0xffbc9630 = 1000
   st_dev : 0xffbc9634 = 0
   st_off : 0xffbc9640 = 0x002b
[0x08048852]> 

The last command may look at bit cryptic, and you may be asking yourself "What about using the t command instead, to deal with types?".

The issue with the t command is that internally, radare2 is using tcc, that doesn't respect very well alignement directives. Maybe it's r2's fault, maybe it's tcc one, but when you're using the to - command and paste the C structure definition (don't forget to add a __attribute__ (( aligned (4))) attribute to it) and print it with pf syntax, this is what you'll get:

[0x08048852]> to ./struct.h   # I put the structure into a file for easier
edition
[0x08048852]> cat stat
#define dev_t   uint64_t 
#define ino_t   uint32_t 
#define mode_t  uint32_t
#define nlink_t uint32_t 
#define uid_t   uint32_t 
#define gid_t   uint32_t 
#define dev_t   uint64_t
#define off_t   uint64_t
#define blksize_t uint64_t

typedef struct stat {
    dev_t     st_dev;         /* ID of device containing file */
    ino_t     st_ino;         /* inode number */
    mode_t    st_mode;        /* protection */
    nlink_t   st_nlink;       /* number of hard links */
    uid_t     st_uid;         /* user ID of owner */
    gid_t     st_gid;         /* group ID of owner */
    dev_t     st_rdev;        /* device ID (if special file) */
    off_t     st_size;        /* total size, in bytes */
} stat_s __attribute__((aligned(8)));

[0x08048852]> t stat
pf qiiiiiqq st_dev st_ino st_mode st_nlink st_uid st_gid st_rdev st_size
[0x08048852]> 

It's not the same that the previous pf one, because currently radare2 and tcc aren't playing nice with structures aligment. But what is pf anyway? And what's the deal with its über-weird syntax?

pf stands for print formated data. As usual, you can get help by appending ? to it. Its syntax is pretty easy: pf [types] [field names].

So my previous cryptic line, pf w::ioiiii::w st_dev st_ino st_mode st_nlink st_uid st_gid st_rdev st_size @ (esp + 34) describes a structure that looks like this:

struct stat {
  word st_dev;
  int pad1[2];   // padding, won't be displayed
  int st_ino;
  int st_mode;   // `o` as in _octal_
  int st_nlink;
  int st_uid;
  int st_gid;
  int st_rdev;
  int pad2[2];   // padding, won't be displayed
  quadword st_size;
};

Pretty cool isn't it?

Ok, back to the main function. After the call to sub.getuid_83b, there is a condition check, and a jump to the end of the function, likely a BADBOY branch. The other path leads to a call to the wrapper to write, with the string "OK\nstage1". Time to check if our analysis is right:

$ echo test > .key
$ chmod 400 .key
$ ./collide
[ collide.crp- ]
stage0: OK
stage1: FAILED

Yay!

Stage1

We successfully passed the comparison at 0x08048611 ; the next function call is sub.malloc_4f2, at 0x0804863f, with .key as argument:

[0x080485ba]> pdsf @ sub.malloc_4f2 
0x080484fe sym.imp.malloc
0x0804852c sym.imp.open
0x0804855f sym.imp.read
0x080485a4 sym.imp.free
[0x080485ba]> 

It seems that it's simply reading the file .key into the heap.

Maybe it's time to get a big overview of what is happening in the main function: You can use the VV command to get the graph view, but like in the visual mode, you can switch between modes with the p/P keys. I really like the summary one:

                                                                                           =-----------------------------------=
                                                                                           |  0x80485ba                        |
                                                                                           | 0x080485d0 str.__collide.crp____n |
                                                                                           | 0x080485f0 str.stage0:            |
                                                                                           | 0x08048600 str..key               |
                                                                                           =-----------------------------------=
                                                                                                             t f
                                                                                            .----------------' '---------------.
                                                                                            |                                  |
                                                                             =----------------------------=     =--------------------=
                                                                             |  0x804861d                 |     |  0x8048618         |
                                                                             | 0x08048620 str.OK_nstage1: |     =--------------------=
                                                                             | 0x0804863a str..key        |                     v
                                                                             =----------------------------=                     |
                                                                                            t f                                 |
                                                                       .--------------------' '-------.                         |
                                                                       |                              |                         |
                                                                 =-------------------------=  =--------------------=            |
                                                                 |  0x8048653              |  |  0x804864e         |            |
                                                                 | 0x0804865e fcn.08048470 |  =--------------------=            |
                                                                 =-------------------------=          v                         |
                                                                       t f                            |                         |
                                                           .-----------' '---------------------.      '-------------------------|
                                                           |                                    |                               |
                                                 =--------------------=             =------------------------------=            |
                                                 |  0x804869b         |             |  0x804866a                   |            |
                                                 =--------------------=             | 0x0804866d str.___re.....___ |            |
                                                         f t                        =------------------------------=            |
                                                         | |                                   v                                |
                                        .----------------' '------------.                      '                                |
                                        |                               |  .-----------------. |                                |
                                =--------------------=                  |  |             =--------------------=                 |
                                |  0x80486a2         |                  |  |             |  0x8048682         |                 |
                                =--------------------=                  |  |             =--------------------=                 |
                                      t f                               |  |                   t f                              |
                  .-------------------' '---------------.               |  |       .-----------' '-----------.                  |
                  |                                     |               |  |       |                         |                  |
            =----------------------------=      =--------------------=  |  | =-------------------------= =--------------------= |
            |  0x80486c0                 |      |  0x80486be         |  |  | |  0x804868e              | |  0x804868c         | |
            | 0x080486c3 str.OK_nstage2: |      =--------------------=  |  | | 0x0804868e fcn.08048418 | =--------------------= |
             | 0x080486db fcn.08048ab6    |              v              |  | =-------------------------=     v                  |
             =----------------------------=              |              |  `-------'                         |                  |
                      t f                                '---------.    |                                    |                  |
      .---------------' '--------------------------.               |    |                                    |                  |
      |                                            |               |    |                                    |                  |
=---------------------------------------=  =--------------------=  |    |                                    |                  |
|  0x80486e9                            |  |  0x80486e7         |  |    |                                    |                  |
| 0x080486ec str.OK_n__key_accepted___n |  =--------------------=  |    |                                    |                  |
=---------------------------------------=      v                   |    |                                    |                  |
    v                                          |                   |    |                                    |                  |
    |                                          '--------------.----'----'------------------------------------'------------------'
    |                                                         |
    |                                               =-------------------------=
    |                                               |  0x80486fb              |
    |                                               | 0x080486fe str.FAILED_n |
    |                                               =-------------------------=
    |                                                         v
    '---------------------------------------.-----------------'
                                               |
                                      =--------------------=
                                      |  0x804870b         |
                                      =--------------------=
                                              f t
                                   .----------' '-------.
                                   |                    |
                           =-------------------------=  |
                           |  0x8048712              |  |
                           | 0x08048719 sym.imp.free |  |
                           =-------------------------=  |
                                   v                    |
                                   '----.     .---------'
                                        |     |
                                   =--------------------------=
                                   | [0x8048721]              |
                                   | 0x08048726 sym.imp._exit |
                                   =--------------------------=

Right after fcn.08048470 there is a test, and if it's false, it'll jump to a loop, do something with the string -- re..... --, and then jumps to FAILED\n. So we can ignore this part and focus on making the function return true.

[0x080485ba]> pdsf @ fcn.08048470
0x08048479 "hmpf, i need a hint..."
0x08048491 fcn.08049ea0
0x080484a7 fcn.08049ea0
0x080484ca fcn.08049ec6
[0x080485ba]> pdsf @ fcn.08049ea0
[0x080485ba]> pdsf @ fcn.08049ec6
[0x080485ba]>

Educated guess: fcn.0x09049ea0 is a custom strlen, and fcn.08049ec6 is memcmp, so if we put hmpf, i need a hint.. into our .key file, we should get the message -- re..... --:

$ echo 'hmpf, i need a hint..' >| .key
$ chmod 400 .key                      
$ ./collide
[ collide.crp- ]
stage0: OK
stage1: -- re..... -- FAILED
$

So the next interesting function is sub.memcpy_8cb, and it's taking 3 parameters:

  1. The content of the file .key
  2. The size of the file
  3. The structure {uid, gid, value}.
                                             <@@@@@@>
                                                f t
                                          .-----' |
                                          |       |
                                       [_88e9_]   |
                                          f t     |
                                     .----' |     |
                                     |      |     |
                                  [_88f0_]  |     |
                                     f t    |     |
                                .----'.'    |     |
                                |     |     |     |
                           [_88fb_]   |     |     |
                              t f     |     |     |
                    .---------' '-. .-'-----'-----'
                    |             | |
                 [_8911_]      [_8904_]
                    v              v
                    |              '------------.
.-------------------.                           | 
|                   |                           | 
|                [_8937_]                       | 
|                   f t                         | 
|                   | '---------------------.   | 
|                [_899c_]                   |   | 
|                   f t                     |   | 
|                   | '---------------.     |   | 
|                [_89af_]             |     |   | 
|                   f t               |     |   | 
|                   ' '---------.   .-'-----'   | 
|                   |           |   |           | 
|                [_89c2_]      [_89c4_]         | 
|                   v             v             | 
|                   |             '---------.   | 
|                [_89d1_]                   |   | 
|                  t f                      |   | 
|           .------' '--------------.       |   | 
|           |                       |       |   | 
|        [_89eb_]                [_89de_]   |   | 
|           t f                     v       |   | 
|     .-----' '------------.        '       |   | 
|     |                    |        |       |   | 
|  [_8a55_]           [_8a4b_]      |       |   | 
|    f t                   v        |       |   | 
|    | '-----------.       |        |       |   | 
|    |             |       '--------'-------'-.-' 
|  [_8a64_]        |                          |   
|    v             |                          |   
|    '-------------'--.                       |   
|                     |                       |   
|                  [_8a69_]               [_8aae_]
|                     v                           
|                     |                           
|           .---------.                           
|           |        [_8a7c_]                     
|           |           t f                       
|           |       .---' '---------.             
|           |       |               |             
|           |  [_8a8b_]          [_8a86_]         
|           `-----'                 |
|                                   | 
'-----------------------------------'

Looks really convoluted :/

But we can break it un sub-parts: everything that eventually and unconditionally leads to _8aae_ is potentially a BADBOY location. Potentially, and not certainly, because one of them is the good way to exit the loop.

You can use the minimap-with-disasm view (smash p or P until you land on it) to quickly find the it.

If you check the last node of the graph (at 0x8048aae), you can see this:

0x8048aae:
mov eax, dword [esp + 0x10]
add esp, 0x5c
ret

With a bit of luck, the function will return a different value (in eax) when everything was right, so there should be an location that put an unique value into [esp + 0x10]:

$ rasm2 'mov dword [esp + 0x10], 0'
c744241000000000
$ rasm2 'mov dword [esp + 0x10], 1'
c744241001000000

So looking for c74424100 should be enough:

[0x080485ba]> pdf @ sub.memcpy_8cb~c74424100
    │└└└─> 0x08048904      c74424100000.  mov dword [esp + 0x10], 0
  │└└└───> 0x080489c4      c74424100000.  mov dword [esp + 0x10], 0
    ││││   0x080489de      c74424100100.  mov dword [esp + 0x10], 1
   │││││   0x08048a4b      c74424100000.  mov dword [esp + 0x10], 0
[0x080485ba]> 

Yay, there is only one location that puts 1 into [esp + 0x10], and it's at the basic block 0x80489de. The condition right before it is

=----------------------------=
|  0x80489d1                 |
| lea eax, [esp + 0x48]      |
| inc dword [eax]            |
| cmp dword [esp + 0x48], 2  |
| jne 0x80489eb ;[f]         |
=----------------------------=

If you highlight 0x48 (with the / key, like in vim), you'll see that the only other location where it's used is in the first block, where it's initialised to 0.

So the big loop will be executed once, and the part before our right-exit block, twice.

Lets focus on the first part of the function:

[0x080485ba]> pdb @ sub.memcpy_8cb
 (fcn) sub.memcpy_8cb 491
           0x080488cb      83ec5c         sub esp, 0x5c
           0x080488ce      c744244c0000.  mov dword [esp + 0x4c], 0
           0x080488d6      c74424480000.  mov dword [esp + 0x48], 0
           0x080488de      8b442464       mov eax, dword [esp + 0x64]
           0x080488e2      83e001         and eax, 1
           0x080488e5      85c0           test eax, eax
       ┌─< 0x080488e7      751b           jne 0x8048904
[0x080485ba]> 

If you're too lazy to count the offset clever, you can break on 0x080488de, and see that it's the size of the .key file:

jvoisin@kaa 21:13 ~/dev/r2/exploit/collide r2 -d ./collide             
Process with PID 17892 started...
attach 17892 17892
bin.baddr 0x08048000
Assuming filepath ./collide
asm.bits 32
 -- Now featuring NoSQL!
[0xf76eeac0]> db 0x080488de
[0xf76eeac0]> dc
[ collide.crp- ]
stage0: OK
stage1: hit breakpoint at: 80488de
attach 17892 1
[0x080488de]> pf i @ esp + 0x64
0xff9ff738 = 42
[0x080488de]> ls -l .key
--r----------  1 1000:1000  42          .key
[0x080488de]> 
[0x080485ba]> pd 20 @ sub.memcpy_8cb
 (fcn) sub.memcpy_8cb 491
           0x080488cb      83ec5c         sub esp, 0x5c
           0x080488ce      c744244c0000.  mov dword [esp + 0x4c], 0
           0x080488d6      c74424480000.  mov dword [esp + 0x48], 0
           0x080488de      8b442464       mov eax, dword [esp + 0x64]
           0x080488e2      83e001         and eax, 1
           0x080488e5      85c0           test eax, eax
       ┌─< 0x080488e7      751b           jne 0x8048904
          0x080488e9      837c246477     cmp dword [esp + 0x64], 0x77
      ┌──< 0x080488ee      7614           jbe 0x8048904
      ││   0x080488f0      8b442464       mov eax, dword [esp + 0x64]
      ││   0x080488f4      83e00f         and eax, 0xf
      ││   0x080488f7      85c0           test eax, eax
     ┌───< 0x080488f9      7509           jne 0x8048904
     │││   0x080488fb      8b442468       mov eax, dword [esp + 0x68]
     │││   0x080488ff      833800         cmp dword [eax], 0
    ┌────< 0x08048902      750d           jne 0x8048911
    │└└└─> 0x08048904      c74424100000.  mov dword [esp + 0x10], 0
      ┌─< 0x0804890c      e99d010000     jmp 0x8048aae
    └────> 0x08048911      8b442460       mov eax, dword [esp + 0x60]
          0x08048915      8a00           mov al, byte [eax]
[0x080485ba]> 

So it's checking that the size of the file is even, superior to 0x77, that and'ing it with 0xf is equal to zero, and it's checking that our struct->uid isn't zero (you can check that it's indeed our structure using with a breakpoint, as done previously.).

Moving to the next block:

[0x080485ba]> pdb @ 0x08048911
           0x08048911      8b442460       mov eax, dword [esp + 0x60]
           0x08048915      8a00           mov al, byte [eax]
           0x08048917      25ff000000     and eax, 0xff
           0x0804891c      8944244c       mov dword [esp + 0x4c], eax
           0x08048920      8b442460       mov eax, dword [esp + 0x60]
           0x08048924      40             inc eax
           0x08048925      8a00           mov al, byte [eax]
           0x08048927      25ff000000     and eax, 0xff
           0x0804892c      89c2           mov edx, eax
           0x0804892e      c1e208         shl edx, 8
           0x08048931      8d44244c       lea eax, [esp + 0x4c]
           0x08048935      0110           add dword [eax], edx
[0x080485ba]> 

What is at [esp + 0x60]?

$ r2 -d ./collide
Process with PID 18794 started...
attach 18794 18794
bin.baddr 0x08048000
Assuming filepath ./collide
asm.bits 32
 -- No fix, no sleep
[0xf76f4ac0]> db 0x08048911
[0xf76f4ac0]> dc
[ collide.crp- ]
stage0: OK
stage1: hit breakpoint at: 8048911
attach 18794 1
[0x08048911]> pxr 4 @ esp + 0x60
0xffe51cf4  0x092bd9d8  ..+. ecx (1234AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAP)
[0x08048911]> cat .key
1234AAAAAAAAAA[]
[0x08048911]> 

So it's reading the first two bytes of the .key file, shifting them by 8, and adding this to the pointer to the file's start: looks like an offset.

We're now entering in the main loop of the function:

[0x080485ba]> pd 44 @ sub.malloc_4f2 + 0x445
           ; JMP XREF from 0x08048a86 (sub.memcpy_8cb)
           0x08048937      8b44244c       mov eax, dword [esp + 0x4c] 
           0x0804893b      03442460       add eax, dword [esp + 0x60]
           0x0804893f      89442444       mov dword [esp + 0x44], eax
           0x08048943      83ec0c         sub esp, 0xc
           0x08048946      ff742450       push dword [esp + 0x50]
           0x0804894a      e8ddfdffff     call fcn.0804872c
           0x0804894f      83c410         add esp, 0x10
           0x08048952      89442440       mov dword [esp + 0x40], eax
           0x08048956      8d442444       lea eax, [esp + 0x44]       
           0x0804895a      830010         add dword [eax], 0x10
           0x0804895d      83ec0c         sub esp, 0xc
           0x08048960      ff742450       push dword [esp + 0x50]
           0x08048964      e8c3fdffff     call fcn.0804872c
           0x08048969      83c410         add esp, 0x10
           0x0804896c      8944243c       mov dword [esp + 0x3c], eax
           0x08048970      8d442444       lea eax, [esp + 0x44]       
           0x08048974      830010         add dword [eax], 0x10
           0x08048977      83ec0c         sub esp, 0xc
           0x0804897a      ff742450       push dword [esp + 0x50]
           0x0804897e      e8a9fdffff     call fcn.0804872c
           0x08048983      83c410         add esp, 0x10
           0x08048986      89442438       mov dword [esp + 0x38], eax
           0x0804898a      8b442440       mov eax, dword [esp + 0x40]
           0x0804898e      03442460       add eax, dword [esp + 0x60]
           0x08048992      8b542468       mov edx, dword [esp + 0x68]
           0x08048996      8b00           mov eax, dword [eax]
           0x08048998      3b02           cmp eax, dword [edx]
       ┌─< 0x0804899a      7528           jne 0x80489c4
          0x0804899c      8b44243c       mov eax, dword [esp + 0x3c]
          0x080489a0      03442460       add eax, dword [esp + 0x60]
          0x080489a4      8b542468       mov edx, dword [esp + 0x68]
          0x080489a8      8b00           mov eax, dword [eax]
          0x080489aa      3b4204         cmp eax, dword [edx + 4]   
      ┌──< 0x080489ad      7515           jne 0x80489c4
      ││   0x080489af      8b442438       mov eax, dword [esp + 0x38]
      ││   0x080489b3      03442460       add eax, dword [esp + 0x60]
      ││   0x080489b7      8b542468       mov edx, dword [esp + 0x68]
      ││   0x080489bb      8b00           mov eax, dword [eax]
      ││   0x080489bd      3b4208         cmp eax, dword [edx + 8]   
     ┌───< 0x080489c0      7502           jne 0x80489c4
    ┌────< 0x080489c2      eb0d           jmp 0x80489d1
    │└└└─> 0x080489c4      c74424100000.  mov dword [esp + 0x10], 0
      ┌─< 0x080489cc      e9dd000000     jmp 0x8048aae
         ; JMP XREF from 0x080489c2 (sub.memcpy_8cb)
    └────> 0x080489d1      8d442448       lea eax, [esp + 0x48]       ; 0x48 ; 'H'
[0x080485ba]>

So, there is a function, fcn.0804872c, called tree times, with offsets distant of 0x10 as arguments, and its return value is used, as an offset, to compare it against our struct.

[0x080485ba]> pdf @ fcn.0804872c
 (fcn) fcn.0804872c 36
           0x0804872c      53             push ebx
           0x0804872d      8b4c2408       mov ecx, dword [esp + 8]
           0x08048731      8b442408       mov eax, dword [esp + 8]
           0x08048735      8b542408       mov edx, dword [esp + 8]
           0x08048739      8b4004         mov eax, dword [eax + 4]
           0x0804873c      0faf4208       imul eax, dword [edx + 8]
           0x08048740      89c2           mov edx, eax
           0x08048742      8b442408       mov eax, dword [esp + 8]
           0x08048746      8b580c         mov ebx, dword [eax + 0xc]
           0x08048749      8d0413         lea eax, [ebx + edx]
           0x0804874c      3301           xor eax, dword [ecx]
           0x0804874e      5b             pop ebx
           0x0804874f      c3             ret
[0x080485ba]> 

This is roughly equivalent to return (((param[4] * param[8])) + param[0xc]) ^ param[0].

So, it means that in our .key file, the uid, gid and value field of our struct must be present a specific offsets.

Then, we have our aforementioned condition, to exit (or not) the loop.

And finally, the end of the function:

   │└────> 0x080489eb      8b542464       mov edx, dword [esp + 0x64]
    │││   0x080489ef      89d0           mov eax, edx
    │││   0x080489f1      c1f81f         sar eax, 0x1f
    │││   0x080489f4      c1e81f         shr eax, 0x1f
    │││   0x080489f7      8d0410         lea eax, [eax + edx]
    │││   0x080489fa      d1f8           sar eax, 1
    │││   0x080489fc      03442460       add eax, dword [esp + 0x60]
    │││   0x08048a00      8944241c       mov dword [esp + 0x1c], eax
    │││   0x08048a04      8b542464       mov edx, dword [esp + 0x64]
    │││   0x08048a08      89d0           mov eax, edx
    │││   0x08048a0a      c1f81f         sar eax, 0x1f
    │││   0x08048a0d      c1e81f         shr eax, 0x1f
    │││   0x08048a10      8d0410         lea eax, [eax + edx]
    │││   0x08048a13      d1f8           sar eax, 1
    │││   0x08048a15      89442418       mov dword [esp + 0x18], eax
    │││   0x08048a19      83ec04         sub esp, 4
    │││   0x08048a1c      6a0c           push 0xc
    │││   0x08048a1e      ff742470       push dword [esp + 0x70]
    │││   0x08048a22      8d44242c       lea eax, [esp + 0x2c]
    │││   0x08048a26      50             push eax
    │││   0x08048a27      e854f9ffff     call sym.imp.memcpy
    │││   0x08048a2c      83c410         add esp, 0x10
    │││   0x08048a2f      8b442420       mov eax, dword [esp + 0x20]
    │││   0x08048a33      0faf442424     imul eax, dword [esp + 0x24]
    │││   0x08048a38      33442428       xor eax, dword [esp + 0x28]
    │││   0x08048a3c      8944242c       mov dword [esp + 0x2c], eax
    │││   0x08048a40      8b442418       mov eax, dword [esp + 0x18]
    │││   0x08048a44      83e007         and eax, 7
    │││   0x08048a47      85c0           test eax, eax
   │┌────< 0x08048a49      740a           je 0x8048a55
   │││││   0x08048a4b      c74424100000.  mov dword [esp + 0x10], 0
  ┌──────< 0x08048a53      eb59           jmp 0x8048aae
  ││└────> 0x08048a55      8b442418       mov eax, dword [esp + 0x18]
  ││ │││   0x08048a59      8944240c       mov dword [esp + 0xc], eax
  ││ │││   0x08048a5d      837c240c00     cmp dword [esp + 0xc], 0
  ││┌────< 0x08048a62      7905           jns 0x8048a69
  ││││││   0x08048a64      8344240c07     add dword [esp + 0xc], 7
  ││└────> 0x08048a69      8b44240c       mov eax, dword [esp + 0xc]
  ││ │││   0x08048a6d      c1f803         sar eax, 3
  ││ │││   0x08048a70      89442418       mov dword [esp + 0x18], eax
  ││ │││   0x08048a74      c74424140000.  mov dword [esp + 0x14], 0
  ││┌────> 0x08048a7c      8b442414       mov eax, dword [esp + 0x14]
  ││││││   0x08048a80      3b442418       cmp eax, dword [esp + 0x18]
 ┌───────< 0x08048a84      7c05           jl 0x8048a8b
 │││││└──< 0x08048a86      e9acfeffff     jmp 0x8048937
 └───────> 0x08048a8b      83ec08         sub esp, 8
  ││││    0x08048a8e      8d442428       lea eax, [esp + 0x28]
  ││││    0x08048a92      50             push eax
  ││││    0x08048a93      ff742428       push dword [esp + 0x28]
  ││││    0x08048a97      e83e020000     call fcn.08048cda
  ││││    0x08048a9c      83c410         add esp, 0x10
  ││││    0x08048a9f      8d44241c       lea eax, [esp + 0x1c]
  ││││    0x08048aa3      830008         add dword [eax], 8
  ││││    0x08048aa6      8d442414       lea eax, [esp + 0x14]
  ││││    0x08048aaa      ff00           inc dword [eax]
  ││└────< 0x08048aac      ebce           jmp 0x8048a7c
  └└─└─└─> 0x08048aae      8b442410       mov eax, dword [esp + 0x10]
           0x08048ab2      83c45c         add esp, 0x5c
           0x08048ab5      c3             ret
[0x080485ba]> 

You may be wondering what this snippet is doing:

0x080489ef      89d0           mov eax, edx
0x080489f1      c1f81f         sar eax, 0x1f
0x080489f4      c1e81f         shr eax, 0x1f
0x080489f7      8d0410         lea eax, [eax + edx]
0x080489fa      d1f8           sar eax, 1

It's a classic compiler trick to implement a signed division.

I fail to see the point of sar eax, 0x1f, but shr eax, 0x1f will only keep the highest bit of eax, aka the sign bit, and lea eax, [eax + edx] will add it to edx, and sar eax, 1 will finally perform the division by two (a right shift or one is equivalent to a division by two.).

Take -7 for example: -7 / 2 = (-7 + 1) >> 1 = -3, while -7 >> 1 = -4.

So the size of the file .key is divided by 2, this value is stored at [esp + x10], then divided again by two, stored at [esp + 0x18]. There is then a call to memcpy, that is copying 0xC bytes of the content of the .key file into a local variable, then the program is computing var = (struct.uid * struct.gid) ^ struct.value.

It's then checking if the size of the file .key divided by two and and'ed by 7 is equal to zero. It it is, it'll jump to a BADBOY location.

Some stuffs are moved around, and there is finally an internal loop, that does call fcn.08048cda amongst doing other computations, roughly equivalent to:

struct our_struct keydata = key_file_content + (size_of_the_key_file / 2);
for (uint32_t i = 0; i < sizeof(keydata) / 8; i++) {                         
    fcn08048cda((((uint32_t *) &keydata) + i*2), &our_struct); 
}

Lets hope that it's not another computation loop…

[0x080485ba]>  pdf @ fcn.08048cda
 (fcn) fcn.08048cda 230
           0x08048cda      53             push ebx
           0x08048cdb      83ec10         sub esp, 0x10
           0x08048cde      a1d89f0408     mov eax, dword [0x8049fd8]
           0x08048ce3      c1e005         shl eax, 5
           0x08048ce6      89442404       mov dword [esp + 4], eax
           0x08048cea      8b442418       mov eax, dword [esp + 0x18]
           0x08048cee      8b00           mov eax, dword [eax]
           0x08048cf0      8944240c       mov dword [esp + 0xc], eax
           0x08048cf4      8b442418       mov eax, dword [esp + 0x18]
           0x08048cf8      83c004         add eax, 4
           0x08048cfb      8b00           mov eax, dword [eax]
           0x08048cfd      89442408       mov dword [esp + 8], eax
           0x08048d01      c70424000000.  mov dword [esp], 0
       ┌─> 0x08048d08      8b0424         mov eax, dword [esp]
          0x08048d0b      3b05dc9f0408   cmp eax, dword [0x8049fdc]
      ┌──< 0x08048d11      7c05           jl 0x8048d18
     ┌───< 0x08048d13      e98c000000     jmp 0x8048da4
     │└──> 0x08048d18      8b44240c       mov eax, dword [esp + 0xc]
         0x08048d1c      89c2           mov edx, eax
         0x08048d1e      c1e204         shl edx, 4
         0x08048d21      8b44241c       mov eax, dword [esp + 0x1c]
         0x08048d25      83c008         add eax, 8
         0x08048d28      0310           add edx, dword [eax]
         0x08048d2a      8b442404       mov eax, dword [esp + 4]
         0x08048d2e      0344240c       add eax, dword [esp + 0xc]
         0x08048d32      89d1           mov ecx, edx
         0x08048d34      31c1           xor ecx, eax
         0x08048d36      8b44240c       mov eax, dword [esp + 0xc]
         0x08048d3a      89c2           mov edx, eax
         0x08048d3c      c1ea05         shr edx, 5
         0x08048d3f      8b44241c       mov eax, dword [esp + 0x1c]
         0x08048d43      83c00c         add eax, 0xc
         0x08048d46      8b18           mov ebx, dword [eax]
         0x08048d48      8d0413         lea eax, [ebx + edx]
         0x08048d4b      89ca           mov edx, ecx
         0x08048d4d      31c2           xor edx, eax
         0x08048d4f      8d442408       lea eax, [esp + 8]
         0x08048d53      2910           sub dword [eax], edx
         0x08048d55      8b442408       mov eax, dword [esp + 8]
         0x08048d59      89c2           mov edx, eax
         0x08048d5b      c1e204         shl edx, 4
         0x08048d5e      8b44241c       mov eax, dword [esp + 0x1c]
         0x08048d62      0310           add edx, dword [eax]
         0x08048d64      8b442404       mov eax, dword [esp + 4]
         0x08048d68      03442408       add eax, dword [esp + 8]
         0x08048d6c      89d1           mov ecx, edx
         0x08048d6e      31c1           xor ecx, eax
         0x08048d70      8b442408       mov eax, dword [esp + 8]
         0x08048d74      89c2           mov edx, eax
         0x08048d76      c1ea05         shr edx, 5
         0x08048d79      8b44241c       mov eax, dword [esp + 0x1c]
         0x08048d7d      83c004         add eax, 4
         0x08048d80      8b18           mov ebx, dword [eax]
         0x08048d82      8d0413         lea eax, [ebx + edx]
         0x08048d85      89ca           mov edx, ecx
         0x08048d87      31c2           xor edx, eax
         0x08048d89      8d44240c       lea eax, [esp + 0xc]
         0x08048d8d      2910           sub dword [eax], edx
         0x08048d8f      8b15d89f0408   mov edx, dword [0x8049fd8]
         0x08048d95      8d442404       lea eax, [esp + 4]
         0x08048d99      2910           sub dword [eax], edx
         0x08048d9b      89e0           mov eax, esp
         0x08048d9d      ff00           inc dword [eax]
      └─< 0x08048d9f      e964ffffff     jmp 0x8048d08
     └───> 0x08048da4      8b542418       mov edx, dword [esp + 0x18]
           0x08048da8      8b44240c       mov eax, dword [esp + 0xc]
           0x08048dac      8902           mov dword [edx], eax
           0x08048dae      8b542418       mov edx, dword [esp + 0x18]
           0x08048db2      83c204         add edx, 4
           0x08048db5      8b442408       mov eax, dword [esp + 8]
           0x08048db9      8902           mov dword [edx], eax
           0x08048dbb      83c410         add esp, 0x10
           0x08048dbe      5b             pop ebx
           0x08048dbf      c3             ret
[0x080485ba]> 

Another computation loop, hurray!

It seems that eax is used as a counter, and that the number of iteration is stored at 0x8049fdc. There are multiple ways of displaying its value: pf like we did previously, but radare2's asm.comments is also working:

0x080485ba]> pf i @ 0x8049fdc
0x08049fdc = 32
[0x080485ba]> e asm.comments = true
[0x080485ba]> pd 1 @ 0x08048d0b
           0x08048d0b      3b05dc9f0408   cmp eax, dword [0x8049fdc]  ; [0x8049fdc:4]=32
0x080485ba]>

So, 32 iterations. The first block is likely initializing some data:

[0x080485ba]> pdb @ fcn.08048cda
 (fcn) fcn.08048cda 230
           ; CALL XREF from 0x08048a97 (sub.memcpy_8cb)
           0x08048cda      53             push ebx
           0x08048cdb      83ec10         sub esp, 0x10
           0x08048cde      a1d89f0408     mov eax, dword [0x8049fd8]  ; [0x8049fd8:4]=0x9e3779b9
           0x08048ce3      c1e005         shl eax, 5
           0x08048ce6      89442404       mov dword [esp + 4], eax
           0x08048cea      8b442418       mov eax, dword [esp + 0x18] ; [0x18:4]=0x80485ba entry0
           0x08048cee      8b00           mov eax, dword [eax]
           0x08048cf0      8944240c       mov dword [esp + 0xc], eax
           0x08048cf4      8b442418       mov eax, dword [esp + 0x18] ; [0x18:4]=0x80485ba entry0
           0x08048cf8      83c004         add eax, 4
           0x08048cfb      8b00           mov eax, dword [eax]
           0x08048cfd      89442408       mov dword [esp + 8], eax
           0x08048d01      c70424000000.  mov dword [esp], 0
[0x080485ba]> 

0x9e3779b9 << 5 is moved at [esp + 4], looks like this value will be used as read-only at 0x08048d2a and 0x08048d64, then decremented by 0x9e3779b9 on each iteration.

[esp + 0x18] is the content of the second part of our .key file, and you can see that the first dword will be stored at [esp + 0xc] while the second will be at [esp + 8].

Then, the big calculation block!

It's actually pretty simple, since there are only basic arithmetic options. The only trick is to remember the offsets of our struct, but you can always renamed local variables with the afvn local_1ch new_name command.

This whole function is doing something like:

uint32_t fcn08048cda(const uint8_t* keyfile_second_part, const struct* our_struct){
#define INCREMENT 0x9e3779b9 << 5;
    uint32_t key = init;

    uint32_t* second_part1 = *keyfile_second_part;
    uint32_t* second_part2 = *keyfile_second_part + 1;

    for (uint32_t i=0; i<32; i++){
         second_part2 -= (((*(secon_part1) << 4) + pwhash1->hash)                           
                 ^ (key2 + *(secon_part1))) ^ (((*(secon_part1) >> 5) + pwhash2->hash));        
         *(secon_part1) -= ((((*(second_part2) << 4) + pwhash2->uid)                           
                 ^ (key2 + *(second_part2)))) ^ (((*(second_part2) >> 5) + pwhash2->gid)); 
        key += init;
    }

    *keyfile_second_part = second_part1;
    *(keyfile_second_part + 1) = second_part2;
#undef INCREMENT
}

Now, if you remember what we said about sub.memcpy_8cb, after this function is called in a loop size_of_the_key_file / 16 times, and after than, it checks again that our uid, gid and value are still matching.

We need to reverse (and simplify a bit) this scheme to forge a key, fortunately, it's not that hard, you only have to revert the << 5 operation on the key, and to permute the second_part and second_part + 1 operations.

static void fcn08048cda_reversed(uint32_t *second_part, const our_struct_t *our_struct) {
#define INCREMENT 0x9e3779b9                                                     
    uint32_t key = INCREMENT;                                                    

    for (uint32_t i = 0; i < 32; i++) {                                          
        *(second_part) +=                                                               
            (((*(second_part+1) >> 5) + our_struct->gid))                               
            ^ ((*(second_part+1) << 4) + our_struct->uid)                               
            ^ (key + *(second_part+1))                                                  
            ;                                                                    
        *(second_part+1) +=                                                             
            ((*(second_part) << 4) + our_struct->value)                                 
            ^ (key + *(second_part))                                                    
            ^ (                                                                  
                    (*(second_part) >> 5)                                               
                    + ((our_struct->uid * our_struct->gid) ^ our_struct->value)  
            );                                                                   
        key += INCREMENT;                                                        
    }                                                                            
#undef INCREMENT                                                                 
} 

It seems that it'll be a real pain to construct a file to validate this crackme…

Stage2

The stage2 only consists in a call to fcn.08048ab6. If you launch radare2 with analysis, and manually analyse this function (to avoid renaming), you should be able to do this:

[0x080485ba]> af @ 0x08048ab6
[0x080485ba]> pdfs @ fcn.08048ab6~fcn
0x08048afd fcn.08048dc0
0x08048b0d fcn.08048dc0
0x08048b2e fcn.08048e02
0x08048b54 fcn.08048e02
0x08048b6c fcn.08048f18
0x08048b81 fcn.08048f18
0x08048b98 fcn.08049ec6
0x08048bce fcn.08049ec6
[0x080485ba]> 

Remember fcn.08049ec6? It's a custom memcmp. Every function is called twice, this is weird…

[0x080485ba]> pdf @ fcn.08048dc0
 (fcn) fcn.08048dc0 66
           0x08048dc0      8b542404       mov edx, dword [esp + 4]
           0x08048dc4      8b442404       mov eax, dword [esp + 4]
           0x08048dc8      c74014000000.  mov dword [eax + 0x14], 0
           0x08048dcf      c74210000000.  mov dword [edx + 0x10], 0
           0x08048dd6      8b442404       mov eax, dword [esp + 4]
           0x08048dda      c70001234567   mov dword [eax], 0x67452301
           0x08048de0      8b442404       mov eax, dword [esp + 4]
           0x08048de4      c7400489abcd.  mov dword [eax + 4], 0xefcdab89
           0x08048deb      8b442404       mov eax, dword [esp + 4]
           0x08048def      c74008fedcba.  mov dword [eax + 8], 0x98badcfe
           0x08048df6      8b442404       mov eax, dword [esp + 4]
           0x08048dfa      c7400c765432.  mov dword [eax + 0xc], 0x10325476
           0x08048e01      c3             ret
[0x080485ba]> pdfs @ fcn.0x8048e02
0x08048e81 sym.imp.memcpy
0x08048e98 fcn.08048fcb
0x08048ec6 fcn.08048fcb

If you take a look at fcn.08048fcb, you'll see a lot of mov, rol, and some sub and add. This really looks like a hash function, with fcn.08048dc0 being the initialization, fcn.08048e02 the computation, and fcn.08048f18 the final pass.

Time to find for what hash the constants 0x67452301, 0xefcdab89, 0x98badcfe and 0x10325476 are used. Keep in mind that we're dealing with little-endian, so the constants are in fact 0x76543210, 0xfedcba98, 89ab cdef, 0x01234567, or even better, in another order:

  • 0x01234567
  • 0x89abcdef
  • 0xfedcba98
  • 0x76543210

If you ask a search engine about those, you'll find that they are used in the MD5 function.

After the md5 computations, there are two calls to memcmp, and since the binary is called collide, I guess we'll have to find a collision in md5, Two different plaintexts, with the same md5 hash. Since there is only a single call (well, done twice, on different data) to the computation part of the hash function, it's really looks like a single-block collision.

I tried to use the code from Vlastimil Klima, porting it to Linux, outputting the vectors as C code, … but since the code is awful (and with a lot of comments in Czech), I gave a try to fastcoll, but it didn't compile with a recent boost version, so I went back in time and used md5coll.c, that I had used to pass a infamous level11 on a well-known two-letters wargame ;)

Now the only remaining thing to do is to create our .key file, that will look like a my_struct1 || encrypt (my_struct2), with the only differences between my_struct1 and my_struct2 being the md5 collision vector.

The my_struct will look like this:

struct my_struct {
        uint32_t vector1[32];  // first vector for the collision
        uint32_t padding[0x1d13 - sizeof (v1)]
        uint32_t uid_var1;
        uint32_t uid_var2;
        uint32_t uid_var3;
        uint32_t uid_var4;
        uint32_t gid_var1;
        uint32_t gid_var2;
        uint32_t gid_var3;
        uint32_t gid_var4;
        uint32_t value_var1;
        uint32_t value_var2;
        uint32_t value_var3;
        uint32_t value_var4;
        uint32_t uid;
        uint32_t gid;
        int32_t value;
        uint32_t padding_end[];
    }

Since I didn't want to compute the padding to make the file size a multiple of 0xf (because I'm lazy), I just bruteforced it by hand (since it's 1 in my case, it didn't take long :D).

Remember that the var stuff are used like this (var1 * var2 + var3) ^ var4, to find the offset of their corresponding fields. So we can zero them all (or just var1 or var2 and var3), and use only var4 as offset indicator.

You can get my keygen here:

$ wget https://dustri.org/b/files/collide_keygen.c
$ gcc ./keygen.c
$ ./a.out
$ ./collide 
[ collide.crp- ]
stage0: OK
stage1: OK
stage2: OK
[ key accepted ]
$

Conclusion

I was a bit disappointed by this crackme: too much boring reversing, and too few interesting tricks, but still above the average.

Shout out to oddcoder for his successful GSoC with radare2, implementing and improving variables detection/handling/typing/manipulation/…

Thank you crp-