Post Info: # Author: Flavio do Carmo Junior aka waKKu
# URL: Author’s Webpage
# Date: February 10, 2011
# Category: Exploiting, Programming, Security, Food for thoughts
Howdy fellas… me again ;)
This post is a bit different from the last one, you’ll probably have some fun with it…
1. Introduction
Long time ago (2009), in Brazil, we got a huge blackout we called “Apagão”. A brazilian blogger posted about a possible SQL Injection flaw into ONS’s system… Well, this isn’t relevant, but this post has literally shined in almost all internet news portals here in Brazil.
I, curious as I usually am, ended up reading a lot of other things on that blog that day…
Yesterday on #dclabs IRC channel, I have no idea why, but me and raph0x88 started chatting about Information Leakage when a programmer “forgots” to return() a value on his/her program (API/libraries included).
This post exists because more than curious I am really stubborn confident. One post that I’d read that day, was a post about strcmp() C function and its return value, but I’d never spent time testing it…
Translating, the post says something like:
As everyone knows (if don’t: man strcmp), the function strcmp() is responsible by compare two strings and return a value that has the same sign as the difference between the first differing pair of characters. This means that if we compare char by char, in the moment of the char in the left parameter differs to the char in the right parameter, the function will return the difference between them. If they match, the function returns 0 (zero).
Ok, back to our story and my relutant mind, I was thinking: Há, raph0x88 doesn’t know this “feature” of strcmp() – I can fool him! ;D. Below is 10% of our (portuguese) talk:
<waKKu> raph0x88 eu to dizendo q eu levo menos de 10 tentativas pra identificar CADA caracter da senha <waKKu> raph0x88 valendo 1 semana de MESTRE waKKu ? <raph0x88> DUVIDOOOO <raph0x88> menos de 10 tentativas? <raph0x88> valendo.. <raph0x88> 1 semana de mestre wakku <raph0x88> ou uma semana de mestre raph <raph0x88> tu tem q me mostrar um codigo que advinhe uma senha q eu colocar de 10 characteres <raph0x88> em menos de 100 tentativas <raph0x88> senão é 1 semana me chamando de mestre <waKKu> aceito <raph0x88> e se tu conseguir, eu te chamo de mestre
Long story short: I told raph0x88 that I was able to break any character of a string in less than 10 tries. He doubt it and I proposed a challenge: If I get it done, he’d MUST call me MASTER waKKu for one week – If I don’t, I’d call him.
Well, as I said earlier I actually thought I would need only 1 try for each character, but my subconscious told me to say 10 ;)
I’ve never stopped to REALLY read strcmp()’s manpage and make sure of the statemant proposed by that blog, I’ve just believed in it and, as it is not really a praticable vulnerability (once it needs a huge number of wrong conditions). But raph0x88 was totally aware of strcmp()’s behaviour, he knew how the function plays with its return values.
Some time and google surfing later, I found that post on Maycon’s blog and thought: I’m going to have a MASTER week…
BUT, when doing my tests I got a damn surprise! I couldn’t reproduce that “behaviour” using current glibc!
Ok, no panic… One week isn’t that long, we could easily travel during the whole week :X but anyway, I’d need to provide some post about this “challenge” and is too soon to give up (at least so far).
2. Function Analysis
First of all: manpage of current strcmp():
RETURN VALUE
The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1 (or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.
Hmmm…
– returns -1 if comparison character in left string is lower than the one in right string.
– returns 0 if comparison character in left string is equal to the one in right string.
– returns 1 if comparison character in left string is greater than the one in right string.
The function returns as soon as it founds a different character, fair enough. Actually, I can’t think any better way to write, in a single function, a string comparison method able to differs lower than, equal to or greater than.
strcmp()’s Disassemble… only for those curious ;)
(gdb) disass strcmp Dump of assembler code for function strcmp: 0xf7e90be0 <strcmp+0>: mov 0x4(%esp),%ecx 0xf7e90be4 <strcmp+4>: mov 0x8(%esp),%edx 0xf7e90be8 <strcmp+8>: mov (%ecx),%al 0xf7e90bea <strcmp+10>: cmp (%edx),%al 0xf7e90bec <strcmp+12>: jne 0xf7e90bf7 <strcmp+23> 0xf7e90bee <strcmp+14>: inc %ecx 0xf7e90bef <strcmp+15>: inc %edx 0xf7e90bf0 <strcmp+16>: test %al,%al 0xf7e90bf2 <strcmp+18>: jne 0xf7e90be8 <strcmp+8> 0xf7e90bf4 <strcmp+20>: xor %eax,%eax 0xf7e90bf6 <strcmp+22>: ret 0xf7e90bf7 <strcmp+23>: mov $0x1,%eax 0xf7e90bfc <strcmp+28>: mov $0xffffffff,%ecx 0xf7e90c01 <strcmp+33>: cmovb %ecx,%eax 0xf7e90c04 <strcmp+36>: ret End of assembler dump. (gdb) set dis intel (gdb) disass strcmp Dump of assembler code for function strcmp: 0xf7e90be0 <strcmp+0>: mov ecx,DWORD PTR [esp+4] 0xf7e90be4 <strcmp+4>: mov edx,DWORD PTR [esp+8] 0xf7e90be8 <strcmp+8>: mov al,BYTE PTR [ecx] 0xf7e90bea <strcmp+10>: cmp al,BYTE PTR [edx] 0xf7e90bec <strcmp+12>: jne 0xf7e90bf7 <strcmp+23> 0xf7e90bee <strcmp+14>: inc ecx 0xf7e90bef <strcmp+15>: inc edx 0xf7e90bf0 <strcmp+16>: test al,al 0xf7e90bf2 <strcmp+18>: jne 0xf7e90be8 <strcmp+8> 0xf7e90bf4 <strcmp+20>: xor eax,eax 0xf7e90bf6 <strcmp+22>: ret 0xf7e90bf7 <strcmp+23>: mov eax,0x1 0xf7e90bfc <strcmp+28>: mov ecx,0xffffffff 0xf7e90c01 <strcmp+33>: cmovb eax,ecx 0xf7e90c04 <strcmp+36>: ret End of assembler dump. (gdb)
Hmmmm… “Blind SQL Injection” comes to mind, those who already played with a Blind SQL Injection knows that we can use a Binary Search algorithm to find EACH character using the fastest way possible, in this case (ASCII table), we’ve a MAXIMUM number of 7 tries.
Happens that in a Blind SQLi, I can compare 1 character against 1 character, when they match I go to the next… Easy, clean, fashion…
waKKu@blog:$ cat wtf.c
#include <stdio.h>
#define STRING "F"
int main(int argc, char **argv) {
if (!strcmp(argv[1], STRING)) {
printf("BINGO!!! Strings match.\n");
return(0);
}
}
waKKu@blog:$ gcc -o wtf wtf.c
waKKu@blog:$ ./wtf A
waKKu@blog:$ echo $?
255
waKKu@blog:$ ./wtf Z
waKKu@blog:$ echo $?
1
waKKu@blog:$ ./wtf F
BINGO!!! Strings match.
waKKu@blog:$ echo $?
0
waKKu@blog:$
AHHHHHH!!! Beautiful, isn’t it?.. strcmp() returns -1 (to figure out why 255 you need to know that that exitcode is a 8 bits value and this computer works with Two’s Complement) if my character is LOWER than, returns +1 if it is GREATER than and returns 0 if they match… Hooray! handle it bro… Binary search + isolated chars + maximum of 7 tries == MASTER waKKu ;).
The “:/” Moment.
waKKu@blog:$ cat wtf.c
#include <stdio.h>
#define STRING "ABCDEFGHIJ"
int main(int argc, char **argv) {
if (!strcmp(argv[1], STRING)) {
printf("BINGO!!! Strings match.\n");
return(0);
}
}
waKKu@blog:$ gcc -o wtf wtf.c
waKKu@blog:$ ./wtf A
waKKu@blog:$ echo $?
255
waKKu@blog:$
“WAIT, WHAT!?!?”… HOW WOULD I ISOLATE EACH CHARACTER FROM OUTSIDE OF THE PROGRAM!?!?
Even if I provide the right FIRST character, strcmp() will try to compare the SECOND character on both strings, that in this output’s case is 0x00 (end of string, null termination, nothing, nada, zip…) and will keep returning that my string is LOWER than the “passphrase”.
3. Frustration
Now I could start panic! I started with a lot of try-and-error approaches…
“That’s it! That’s it!”, I’ll keep incrementing my character, from the first ASCII until the returning value changes from +1 to -1, then I know the last character is the right one and can go to the next position… Well, that leaves me with a worst case of 94 tries characters EACH :/…
Yeah… seems like my best bet is really Binary Search…
ASCII possible characters: 94 - Search example: 48
1st. try: 94/2 => 47
2nd. try: 48+94/2 => 71
3rd. try: 48+70/2 => 59
4th. try: 48+58/2 => 53
5th. try: 48+52/2 => 50 *** (1)
6th. try: 48+49/2 => 48 *** (2) Found it????
7th. try: 48+47/2 => 47
8th. try: 48+47/2 => 47
...
1000a. try: 48+47/2 => 47 ...
(2) I’ve found the number, but I’ve no way to know it. If I test I’ll still get -1 as return value…
So, if I decided to go with standard Binary Search algorithm, I’ll fall into an infinite loop, ‘coz I’ve no stop condition…
(1) Hm… Landed into a maximum of 3 values in range… I could test from 49 to 47, 1 by 1 and done… 10 tries for 1 character == MASTER waKKu.
Sounds promising, but there is one more iem, some moment that I need to go down (at a greater number) and moment that I need to go up (lower number)… That will costs me, at least one more piece of code to find out where to go…
Again, some code: A snippet python example of Binary Search:
count = 1
x = (min + max) / 2
while (num <> x):
print "count: %d - min: %d - max: %d - x: %d" % (count, min, max, x)
if num > x:
min = x+1
else:
max = x-1
x = (min + max) / 2
count+=1
print "Tries: ", count, " - Num: ", x
waKKu@blog:$ ./binsearch.py 48 32 94 # 32 == First ASCII, 94 == Last ASCII, 48 == Value to search for count: 1 - min: 32 - max: 94 - x: 63 count: 2 - min: 32 - max: 62 - x: 47 count: 3 - min: 48 - max: 62 - x: 55 count: 4 - min: 48 - max: 54 - x: 51 count: 5 - min: 48 - max: 50 - x: 49 Tries: 6 - Num: 48 waKKu@blog:$
Really impressive algorithm, isn’t?…
4. Enlightening (frozen pizza) time (howdy Zé!!)
Who cares about speed, huh?… My worst case is 7 and it is a way below my limits…
Now I stopped worring about “when” I’ll find the character. I’m pretty sure I’ll find it out, either on first try or on seventh, makes no difference.
New approach: Pushing limits ;)
count = 1
x = (min + max) / 2
while (count <= 10): # Changed
print "count: %d - min: %d - max: %d - x: %d" % (count, min, max, x)
if num > x:
min = x+1
else:
max = x-1
x = (min + max) / 2
count+=1
print "Tries: ", count, " - Num: ", x
waKKu@blog:$ ./binsearch.py 48 32 94 # 32 == First ASCII, 94 == Last ASCII, 48 == Value to search for count: 1 - min: 32 - max: 94 - x: 63 count: 2 - min: 32 - max: 62 - x: 47 count: 3 - min: 48 - max: 62 - x: 55 count: 4 - min: 48 - max: 54 - x: 51 count: 5 - min: 48 - max: 50 - x: 49 count: 6 - min: 48 - max: 48 - x: 48 count: 7 - min: 48 - max: 47 - x: 47 count: 8 - min: 48 - max: 47 - x: 47 count: 9 - min: 48 - max: 47 - x: 47 count: 10 - min: 48 - max: 47 - x: 47 Tries: 11 - Num: 47 waKKu@blog:$
Hmmm… One number below… Simple, add +1 and we’re done!
But…
If you recall my conditions: When I found the right value of the first character, strcmp() returns OK(0) to this comparison and go to the next, but then I’ve no second character and strcmp() says that my string is lower…
That means my condition is true for “lower than or equal to” instead of only lower than…
count = 1
x = (min + max) / 2
while (count <= 10):
print "count: %d - min: %d - max: %d - x: %d" % (count, min, max, x)
if num >= x: # Changed
min = x+1
else:
max = x-1
x = (min + max) / 2
count+=1
print "Tries: ", count, " - Num: ", x
waKKu@blog:$ ./binsearch.py 48 32 94 # 32 == First ASCII, 94 == Last ASCII, 48 == Value to search for count: 1 - min: 32 - max: 94 - x: 63 count: 2 - min: 32 - max: 62 - x: 47 count: 3 - min: 48 - max: 62 - x: 55 count: 4 - min: 48 - max: 54 - x: 51 count: 5 - min: 48 - max: 50 - x: 49 count: 6 - min: 48 - max: 48 - x: 48 count: 7 - min: 49 - max: 48 - x: 48 count: 8 - min: 49 - max: 48 - x: 48 count: 9 - min: 49 - max: 48 - x: 48 count: 10 - min: 49 - max: 48 - x: 48 Iteracoes: 11 - Num: 48 waKKu@blog:$
Known my worst case is 7, no need to continue until 10…
5. A new algorithm
Recap time:
– When my character is lower than or equal to, I get +1
– When my character is greater than, I get -1 (255)
New crux: How to identify the end of “passphrase”?
The last character of all strings in memory is (at least should be :X) a 0x00 (true zero, not this “0″, this is value/ASCII 0x30), therefore if I follow our binary search algorithm trying to find for 0x00, we got:
waKKu@blog:$ ./binsearch.py 0 32 94 # 32 == First ASCII, 94 == Last ASCII, 0 == Value to search for count: 1 - min: 32 - max: 94 - x: 63 count: 2 - min: 32 - max: 62 - x: 47 count: 3 - min: 32 - max: 46 - x: 39 count: 4 - min: 32 - max: 38 - x: 35 count: 5 - min: 32 - max: 34 - x: 33 count: 6 - min: 32 - max: 32 - x: 32 count: 7 - min: 32 - max: 31 - x: 31 count: 8 - min: 32 - max: 30 - x: 31 count: 9 - min: 32 - max: 30 - x: 31 count: 10 - min: 32 - max: 30 - x: 31 Tries: 11 - Num: 31 waKKu@blog:$
Due to our min+max/2 calculations, we fell into an infinite loop always on min-1, in our case (ASCII), 31 (or hexa 0x1F).
Cool, that is our condition to end of string, when “x” becomes 31 (0x1f) means that we’ve reached the end of “pasphrase”.
6. The final code
One more “particular item” last (sorry ;))… I told raph0x88 that my solution would be in C (because ain’t not that great on it and he’s, so I should beat him on his rules (sounds hacky, huh?)).
I decided to post this code on both, pastebin and here:
“Vulnerable” code: @Pastebin.com
“Exploit” code: @Pastebin.com
Execution outputs: @Pastebin.com
From here below, it’s only execution outputs and good bye ;).
waKKu@blog$ cat budasafado.c
#include <stdio.h>
#define PASS "<raph0x88> 1 semana de mestre wakku"
int main(int argc, char **argv) {
if (argc != 2)
return(1);
//puts("try hard! - Vamo conta cada linha dessa");
if (!strcmp(PASS, argv[1])) {
puts("Ola... Eu sou o waKKu, mas o raph0x88 DEVE me chamar de MESTRE waKKu! LOLLLL");
}
}
waKKu@blog$ cat salcifufu-raph.c
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
int main(int argc, char **argv) {
char min, max;
int status, i;
char *x, *ptr;
pid_t pid;
if (argc != 3) {
printf("Usage: %s <passwd maxlen> <progname>\n", argv[0]);
exit(1);
}
x = (char *)malloc(atoi(argv[1]));
ptr = x;
while (1) {
min = 0x20; // Primero caracter imprimivel da tabela ASCII (SPACE)
max = 0x7E; // Ultimo caracter imprimivel da tabela ASCII (~)
*ptr = (char)((min + max) / 2); // Meio da tabela ASCII
for (i=0; i<7; i++) {
if ((pid = fork()) == -1) {
perror("fork");
exit(EXIT_FAILURE);
}
if (pid == 0) {
if (execl(argv[2], argv[2], x, NULL) == -1) {
perror("execl");
exit(EXIT_FAILURE);
}
} else {
if ((wait(&status)) == -1) {
perror("wait");
exit(EXIT_FAILURE);
}
if (WEXITSTATUS(status) == 1)
min = *ptr+1;
if (WEXITSTATUS(status) == 255)
max = *ptr-1;
*ptr = (char)((min + max) / 2); // Meio da busca
//printf("min: %d - max: %d - x: %d\n", min, max, *ptr);
//printf("WEXITSTATUS: %d\n", WEXITSTATUS(status));
//sleep(1);
}
}
if (*ptr == 0x1F) {
printf("----------------------------------------\nPassword Found[%d]: %s\n", strlen(x), x);
return(0);
} else {
ptr++;
printf("Password found so far: %s\n", x);
}
}
return(0);
}
waKKu@blog$ gcc -o budasafado budasafado.c
waKKu@blog$ gcc -o salcifufu-raph salcifufu-raph.c
waKKu@blog$ ./salcifufu-raph
Usage: ./salcifufu-raph <passwd maxlen> <progname>
waKKu@blog$ ./salcifufu-raph 100 ./budasafado
Password found so far: <
Password found so far: <r
Password found so far: <ra
Password found so far: <rap
Password found so far: <raph
Password found so far: <raph0
Password found so far: <raph0x
Password found so far: <raph0x8
Password found so far: <raph0x88
Password found so far: <raph0x88>
Password found so far: <raph0x88>
Password found so far: <raph0x88> 1
Password found so far: <raph0x88> 1
Password found so far: <raph0x88> 1 s
Password found so far: <raph0x88> 1 se
Password found so far: <raph0x88> 1 sem
Password found so far: <raph0x88> 1 sema
Password found so far: <raph0x88> 1 seman
Password found so far: <raph0x88> 1 semana
Password found so far: <raph0x88> 1 semana
Password found so far: <raph0x88> 1 semana d
Password found so far: <raph0x88> 1 semana de
Password found so far: <raph0x88> 1 semana de
Password found so far: <raph0x88> 1 semana de m
Password found so far: <raph0x88> 1 semana de me
Password found so far: <raph0x88> 1 semana de mes
Password found so far: <raph0x88> 1 semana de mest
Password found so far: <raph0x88> 1 semana de mestr
Password found so far: <raph0x88> 1 semana de mestre
Password found so far: <raph0x88> 1 semana de mestre
Password found so far: <raph0x88> 1 semana de mestre w
Password found so far: <raph0x88> 1 semana de mestre wa
Password found so far: <raph0x88> 1 semana de mestre wak
Password found so far: <raph0x88> 1 semana de mestre wakk
Ola... Eu sou o waKKu, mas o raph0x88 DEVE me chamar de MESTRE waKKu! LOLLLL
Password found so far: <raph0x88> 1 semana de mestre wakku
----------------------------------------
Password Found[36]: <raph0x88> 1 semana de mestre wakku
waKKu@blog$
That’s all folks!
–
waKKu
int strcmp(const char *s1, const char *s2);
Amazing, but it’ll probably take me time to do all this. I’d rather write a hijacking library to hijack strcmp() via $LD_PRELOAD and printout *s1,*s2 and chill :)
True enough…
;)
useless :)