The challenge description was: Last month I was trying to simplify an algorithm.. and I found how to mess up a source really really bad. And then this challenge is born. Maybe is really simple or maybe is so hard that all of you will give up. Good luck!

A binary was provided so let's have a look at it:

mrt:~/ctf/polictf/reversing/reversemeplz$ file challenge
challenge: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV),
dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32,
BuildID[sha1]=da884e304160351da7785e93dc168eecafe770ed, stripped

mrt:~/ctf/polictf/reversing/reversemeplz$ ./challenge
test
Wrong input.

It's not doing much, let's have a look at the dump and try understanding what is happening:

mrt:~/ctf/polictf/reversing/reversemeplz$ objdump -d -M intel challenge > dump

mrt:~/ctf/polictf/reversing/reversemeplz$ less dump

challenge:     file format elf32-i386


Disassembly of section .init:

...

 8048390:	8d 4c 24 04          	lea    ecx,[esp+0x4]
 8048394:	83 e4 f0             	and    esp,0xfffffff0
 8048397:	ff 71 fc             	push   DWORD PTR [ecx-0x4]
 804839a:	55                   	push   ebp
 804839b:	89 e5                	mov    ebp,esp
 804839d:	56                   	push   esi
 804839e:	53                   	push   ebx
 804839f:	51                   	push   ecx
 80483a0:	8d b5 68 ff ff ff    	lea    esi,[ebp-0x98]
 80483a6:	81 ec 18 01 00 00    	sub    esp,0x118
 80483ac:	56                   	push   esi
 80483ad:	e8 7e ff ff ff       	call   8048330 <gets@plt>                   ; get user input
 80483b2:	89 34 24             	mov    DWORD PTR [esp],esi
 80483b5:	e8 47 04 00 00       	call   8048801 <__libc_start_main@plt+0x481>; check input
 80483ba:	83 c4 10             	add    esp,0x10
 80483bd:	85 c0                	test   eax,eax
 80483bf:	74 2e                	je     80483ef <__libc_start_main@plt+0x6f> ; if 0 invalid input

So the function at 0x8048801 is checking the user input and if it fails will return 0 in eax. Let's see what this function does:

...
 8048801:	55                   	push   ebp
 8048802:	b9 0f 00 00 00       	mov    ecx,0xf
 8048807:	89 e5                	mov    ebp,esp
 8048809:	57                   	push   edi
 804880a:	56                   	push   esi
 804880b:	53                   	push   ebx
 804880c:	8d 7d b8             	lea    edi,[ebp-0x48]
 804880f:	be 80 89 04 08       	mov    esi,0x8048980
 8048814:	83 ec 50             	sub    esp,0x50
 8048817:	8b 5d 08             	mov    ebx,DWORD PTR [ebp+0x8]
 804881a:	f3 a5                	rep movs DWORD PTR es:[edi],DWORD PTR ds:[esi]
 804881c:	31 ff                	xor    edi,edi
 804881e:	31 f6                	xor    esi,esi
 8048820:	80 3c 33 60          	cmp    BYTE PTR [ebx+esi*1],0x60                ; check user input char
 8048824:	7f 10                	jg     8048836 <__libc_start_main@plt+0x4b6>    ; jump greater 0x60 - `
 8048826:	8a 43 01             	mov    al,BYTE PTR [ebx+0x1]
 8048829:	83 e0 01             	and    eax,0x1
 804882c:	50                   	push   eax
 804882d:	e8 e7 fc ff ff       	call   8048519 <__libc_start_main@plt+0x199>    ; rot13
 8048832:	88 04 33             	mov    BYTE PTR [ebx+esi*1],al
 8048835:	58                   	pop    eax
 8048836:	80 3c 33 7a          	cmp    BYTE PTR [ebx+esi*1],0x7a                ; jump lower equal 0x7a - z
 804883a:	7e 13                	jle    804884f <__libc_start_main@plt+0x4cf>
 804883c:	8a 43 01             	mov    al,BYTE PTR [ebx+0x1]
 804883f:	83 e0 02             	and    eax,0x2
 8048842:	0f be c0             	movsx  eax,al
 8048845:	50                   	push   eax
 8048846:	e8 ce fc ff ff       	call   8048519 <__libc_start_main@plt+0x199>    ; rot13
 804884b:	88 04 33             	mov    BYTE PTR [ebx+esi*1],al
 804884e:	59                   	pop    ecx
 804884f:	0f be 04 33          	movsx  eax,BYTE PTR [ebx+esi*1]
 8048853:	50                   	push   eax
 8048854:	e8 c0 fc ff ff       	call   8048519 <__libc_start_main@plt+0x199>    ; rot13
 8048859:	3c cc                	cmp    al,0xcc
 804885b:	88 44 35 a8          	mov    BYTE PTR [ebp+esi*1-0x58],al
 804885f:	5a                   	pop    edx
 8048860:	76 0a                	jbe    804886c <__libc_start_main@plt+0x4ec>
 8048862:	3c cf                	cmp    al,0xcf
 8048864:	b8 01 00 00 00       	mov    eax,0x1
 8048869:	0f 45 f8             	cmovne edi,eax
 804886c:	46                   	inc    esi
 804886d:	83 fe 0f             	cmp    esi,0xf                                  ; check that all chars have been processed
 8048870:	75 ae                	jne    8048820 <__libc_start_main@plt+0x4a0>    ;
 8048872:	31 c0                	xor    eax,eax
 8048874:	4f                   	dec    edi
 8048875:	75 09                	jne    8048880 <__libc_start_main@plt+0x500>    ; must be true to get proper key
 8048877:	31 c0                	xor    eax,eax                                  ; return false
 8048879:	eb 51                	jmp    80488cc <__libc_start_main@plt+0x54c>    ; bad key
 804887b:	83 f8 0e             	cmp    eax,0xe                                  ; 14 chars long
 804887e:	74 15                	je     8048895 <__libc_start_main@plt+0x515>
 8048880:	40                   	inc    eax                                      ; increment offset
 8048881:	0f b6 54 05 a8       	movzx  edx,BYTE PTR [ebp+eax*1-0x58]            ; 2nd input char + offset in edx
 8048886:	0f b6 4c 05 a7       	movzx  ecx,BYTE PTR [ebp+eax*1-0x59]            ; 1st input char + offset in ecx
 804888b:	29 ca                	sub    edx,ecx                                  ; edx - ecx
 804888d:	3b 54 85 b4          	cmp    edx,DWORD PTR [ebp+eax*4-0x4c]           ; compare result with ebp + offset*4-0x4c
 8048891:	74 e8                	je     804887b <__libc_start_main@plt+0x4fb>    ; continue if equal
 8048893:	eb e2                	jmp    8048877 <__libc_start_main@plt+0x4f7>    ; jump to return false
 8048895:	80 7b 0f 00          	cmp    BYTE PTR [ebx+0xf],0x0                   ; 15th char must be null byte
 8048899:	74 13                	je     80488ae <__libc_start_main@plt+0x52e>
 804889b:	8a 55 a9             	mov    dl,BYTE PTR [ebp-0x57]
 804889e:	8a 45 a8             	mov    al,BYTE PTR [ebp-0x58]
 80488a1:	3c cc                	cmp    al,0xcc
 80488a3:	8d 4a ff             	lea    ecx,[edx-0x1]
 80488a6:	74 cf                	je     8048877 <__libc_start_main@plt+0x4f7>    ; jump to return false
 80488a8:	31 d0                	xor    eax,edx
 80488aa:	88 ca                	mov    dl,cl
 80488ac:	eb f3                	jmp    80488a1 <__libc_start_main@plt+0x521>
 80488ae:	6a 00                	push   0x0
 80488b0:	e8 64 fc ff ff       	call   8048519 <__libc_start_main@plt+0x199>    ; rot13
 80488b5:	85 c0                	test   eax,eax
 80488b7:	59                   	pop    ecx
 80488b8:	75 bd                	jne    8048877 <__libc_start_main@plt+0x4f7>    ; jump to return false
 80488ba:	0f b6 03             	movzx  eax,BYTE PTR [ebx]
 80488bd:	50                   	push   eax
 80488be:	e8 56 fc ff ff       	call   8048519 <__libc_start_main@plt+0x199>    ; rot13
 80488c3:	5a                   	pop    edx
 80488c4:	3c 62                	cmp    al,0x62                                  ; last validation
 80488c6:	0f 94 c0             	sete   al                                       ; input must start with 0x62 (b)
 80488c9:	0f b6 c0             	movzx  eax,al
 80488cc:	8d 65 f4             	lea    esp,[ebp-0xc]
 80488cf:	5b                   	pop    ebx
 80488d0:	5e                   	pop    esi
 80488d1:	5f                   	pop    edi
 80488d2:	5d                   	pop    ebp
 80488d3:	c3                   	ret    
...

My notes might be a bit confusing but there is really only a couple important addresses in the dump. 0x8048877 sets eax to 0 to specify it failed during input validation and return, so each jump to this address means an important piece of the validation process has been done before that.

From this single function we know that the input must be 14 characters long (+1 for the null byte) and must contains only lowercase a-z. Finding out what the function call at 0x8048519 does exactly isn't even necessary if you just look at the addresses 0x8048881 to 0x8048891 where it substracts the current character with the earlier and compare with a value in memory.

Time to start gdb, set a breakpoint at address 0x8048881, run the program, enter 14 lowercase chars and see what happens:

mrt:~/ctf/polictf/reversing/reversemeplz$ gdb ./challenge

Reading symbols from ./challenge...(no debugging symbols found)...done.
gdb$ b * 0x8048881
Breakpoint 1 at 0x8048881
gdb$ r
Starting program: /home/mrt/ctf/polictf/reversing/reversemeplz/challenge
aaaaaaaaaaaaaa
--------------------------------------------------------------------------[regs]
  EAX: 0x00000001  EBX: 0xFFFFD600  ECX: 0x00000048  EDX: 0x0000005E  o d I t s z a p c
  ESI: 0x0000000F  EDI: 0xFFFFFFFF  EBP: 0xFFFFD568  ESP: 0xFFFFD50C  EIP: 0x08048881
  CS: 0023  DS: 002B  ES: 002B  FS: 0000  GS: 0063  SS: 002B
[0x002B:0xFFFFD50C]------------------------------------------------------[stack]
0xFFFFD55C : 00 50 FC F7 00 D6 FF FF - 00 00 00 00 98 D6 FF FF .P..............
0xFFFFD54C : 06 00 00 00 F8 FF FF FF - F6 FF FF FF 00 00 00 00 ................
0xFFFFD53C : FD FF FF FF 01 00 00 00 - 06 00 00 00 F5 FF FF FF ................
0xFFFFD52C : 03 00 00 00 F8 FF FF FF - 05 00 00 00 0E 00 00 00 ................
0xFFFFD51C : 6E 6E 10 08 FF FF FF FF - 11 00 00 00 F5 FF FF FF nn..............
0xFFFFD50C : 0A 00 00 00 6E 6E 6E 6E - 6E 6E 6E 6E 6E 6E 6E 6E ....nnnnnnnnnnnn
[0x002B:0xFFFFD50C]-------------------------------------------------------[data]
0xFFFFD50C : 0A 00 00 00 6E 6E 6E 6E - 6E 6E 6E 6E 6E 6E 6E 6E ....nnnnnnnnnnnn
0xFFFFD51C : 6E 6E 10 08 FF FF FF FF - 11 00 00 00 F5 FF FF FF nn..............
0xFFFFD52C : 03 00 00 00 F8 FF FF FF - 05 00 00 00 0E 00 00 00 ................
0xFFFFD53C : FD FF FF FF 01 00 00 00 - 06 00 00 00 F5 FF FF FF ................
0xFFFFD54C : 06 00 00 00 F8 FF FF FF - F6 FF FF FF 00 00 00 00 ................
0xFFFFD55C : 00 50 FC F7 00 D6 FF FF - 00 00 00 00 98 D6 FF FF .P..............
0xFFFFD56C : BA 83 04 08 00 D6 FF FF - 71 EA B1 07 2E 4E 3D F6 ........q....N=.
0xFFFFD57C : C8 2E E2 F7 F8 BB E2 F7 - 06 0D FF F7 00 D0 FF F7 ................
--------------------------------------------------------------------------[code]
=> 0x8048881:   movzx  edx,BYTE PTR [ebp+eax*1-0x58]
   0x8048886:   movzx  ecx,BYTE PTR [ebp+eax*1-0x59]
   0x804888b:   sub    edx,ecx
   0x804888d:   cmp    edx,DWORD PTR [ebp+eax*4-0x4c]
   0x8048891:   je     0x804887b
   0x8048893:   jmp    0x8048877
   0x8048895:   cmp    BYTE PTR [ebx+0xf],0x0
   0x8048899:   je     0x80488ae
--------------------------------------------------------------------------------

Breakpoint 1, 0x08048881 in ?? ()
gdb$

Our input aaaaaaaaaaaaaa became nnnnnnnnnnnnnn after the call of the function at 0x8048519, this is a ROT13 cipher. It doesn't really matter actually to solve this since we are only interested in the value compared at 0x804888d. Current letter is subtracted to the previous one and the result must match the one in memory pointed by ebp+eax*4-0x4c.

Let's list the values we have to match:

gdb$ x/14x $ebp+$eax*4-0x4c
0xffffd520:     0xffffffff      0x00000011      0xfffffff5      0x00000003
0xffffd530:     0xfffffff8      0x00000005      0x0000000e      0xfffffffd
0xffffd540:     0x00000001      0x00000006      0xfffffff5      0x00000006
0xffffd550:     0xfffffff8      0xfffffff6
gdb$

Which means our second character in our input substracted to the first should be -1. (0xffffffff) At this point it was possible to make a script to solve this automatically and pick the proper letter and shift everything until all values are matched. But I guess it would have taken me longer than doing it manually, so I started with baaaaaaaaaaaaa to see if the first check would be validated. Just keep in mind that our input will be a ROT13 cipher, meaning our input becomes onnnnnnnnnnnnn. The value of the character n is 0x6e, substracted to o which is 0x6f returns -1. And so on for the next characters.

If a substraction cannot meet the value specified in memory, shifting all characters value would be enough to end up with a valid input.

When you manage to pass all validations, you should have your flag. Although it is possible to pass all validations there is one last check at 0x80488c4 comparing the first character of your input with 0x62 (b), if it doesn't match it will fail validation.

Which means pofuxpuifgmbhzp would pass all but the last validation. The letter b after ROT13 result in the letter o which means our input must start with o and all other letters must be shifted accordingly to match this change.

In the case of pofuxpuifgmbhzp, if we shift all letters by -0x1 to match p to o we get our proper input: onetwotheflagyo

mrt:~/ctf/polictf/reversing/reversemeplz$ ./challenge
onetwotheflagyo
The flag is flag{onetwotheflagyo}

We got our flag: flag{onetwotheflagyo}