how strcmp() made my week…   3 comments

  • Post Info:
    1. # 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

    Advertisements

    Posted February 10, 2011 by waKKu in Exploiting, Food for thoughts, Programming, Security

    3 responses to “how strcmp() made my week…

    Subscribe to comments with RSS.

    1. 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 :)

    2. useless :)

    Leave a Reply

    Fill in your details below or click an icon to log in:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out / Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out / Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out / Change )

    Google+ photo

    You are commenting using your Google+ account. Log Out / Change )

    Connecting to %s

    %d bloggers like this: