2

I'm having some trouble with a problem I found. Given the following:

int match(char *s1, char *s2) {
    while( *s1 != '\0' && *s2 != '\0' && *s1 == *s2 ){
        s1++; s2++;
    }
    return( *s1 - *s2 );
}

int main() {
    char str1[8], str2[8];
    scanf("%s", str1);
    scanf("%s", str2);
    if (match(str1, str2) == 0)
        printf("They are the same.\n");
    else
        printf("They are not the same.\n");
}

What two input strings of different values can be used to cause the program to print the message "They are the same"? (The code above can not be altered)

I understand that when the arrays are added to the stack, they are "pushed" into it and information is written in the same direction. So if I were to enter "AAAAAAAAA" (A x 9) to str2, it would overflow and str1 would print "A".

My first attempts were to enter A x 16 for str2, hoping that the program would overwrite the value in str1 with 8 A's and the program would only read 8 values in str2. str1 did have a value of A x 8, but str2 retained its value of A x 16.

Is there a way to use this to solve this problem? Or am I thinking about this the wrong way?

EDIT: This problem was meant to be run on a specific machine with an outdated, therefore vulnerable, version of Linux. I've run the program through gdb and it shows that the two strings are next to each other in memory and that str2 is overflowing into str1. My question then, is can I use this to make str2 and str1 look identical to the program when it compares them?

Improve this question
2
  • Why should the input of the second variable overwrite the content of the first one ? Commented Oct 14, 2013 at 13:53
  • Well, I figure that's the only way to go when solving this problem. How else could the program be "fooled"? Commented Oct 14, 2013 at 13:57

5 Answers 5

Reset to default
3

What two input strings of different values can be used to cause the program to print the message "They are the same"? (The code above can not be altered)

No such well-defined scenario exists. The requirements make no sense.

I understand that when the arrays are added to the stack, they are "pushed" into it and information is written in the same direction. So if I were to enter "AAAAAAAAA" (A x 9) to str2, it would overflow and str1 would print "A".

That is not correct. The buffer str1 (which can contain 7 letters + 1 null termination) would overflow and from there anything can happen, you invoke undefined behavior. Some examples of possible undefined behavior is: segmentation fault/crash & burn, or the program appearing to work correctly.

There are no guarantees that str2 is allocated adjacently to str1. Nor are there any guarantees that str1 is allocated before str2. There aren't even any guarantees they are allocated on the stack, although that's quite likely.

Is there a way to use this to solve this problem?

No.

Or am I thinking about this the wrong way?

Yes.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

The problem was meant to be used on a specific system. I've run the program through gdb and it shows that the strings are next to each other in memory and str2 is overflowing into str1.
@MrDiggles When it comes to undefined behavior, "observations" are unfortunately completely irrelevant, as they only apply to the current version of your specific, compiled binary. Alter something, then compile again, and the stack layout can turn out completely different. So even if you don't port the program to another compiler or system, it can still crash and burn from compilation to compilation.
I think it's still a valid question. Anything can happen doesn't mean anything will happen. You have to take that point of view when you are developing software, and make sure it doesn't expose undefine behaviour. But when examining existing software, you can assume even undefined behaviour is predictable on a specific system. Otherwise, exploiting buffer overflows in existing software wouldn't be possible - we all know this isn't the case.
@MrDiggles It is quite possible that whoever designed the competition questions lacked any deeper knowledge about programming. I would suggest forgetting that competition and instead focus on understanding the actual cause of the vulnerability in the program, which is using scanf in production code. As usual, the C FAQ has some nice information about the topic.
@Axel If that was the case, then then question should hand out the binary, rather than the high-level programming language source code.
|
2

I have another idea: What happens if you enter "A" and "A A"? According to this, sscanf expects non-whitespace characters for '%s' , so it will stop reading after the first "A" in "A A" (note the space character). The tag "buffer-overflow" is misleading.

Improve this answer

2 Comments

Oh wow, it was that easy. I just spend the last hour poring over addresses in gdb. Thanks so much!
Indeed... Good answer!
1

Have you tried the other way around? It depends on how the stack is laid out. I'd try "AAAAAAAAAA" forstr1 and "AAAAAAA" (7x'A') for str2. AFAIR the stack grows form top to bottom.

See here for an explanation.

EDIT: I know evil (undefined) things will happen if you write over the array limits, but the question explicitly tells not to alter the program. Looks like an exercise to understand security risks in software development.

Improve this answer

1 Comment

Only str2 can overwrite str1, from what I've observed.
1

Overwriting your buffer invokes undefined behaviour. Anything can happen, so you must never rely on it.

Also, str1 and str2 are not necessarily next to each other in memory, and you cannot depend on that.

Possible solution

char buffer[16];
char * str1 = &buffer[8];
char * str2 = &buffer[0];

This way you can overflow from str2 to str1 safely (but not from str1 to str2). You should still have proper length checks though.

Improve this answer

5 Comments

Wait, why do You say "not necessarily next to each other in memory". AFAIk they will be.
@icbytes Nothing stops implementation from adding extra data to stack between the buffers.
The problem specifically says that the program is not to be altered. And I ran the program through gdb and found that the two arrays are next to each other in memory.
@MrDiggles They are next to each other on that system. It doesn't change the fact that overwriting the buffer is undefined behaviour, and you cannot fix it reliably without fixing the program.
@MrDiggles; This is not the case always.
0

What two input strings of different values can be used to cause the program to print the message "They are the same"?

Your function for string comparison is wrong. return( *s1 - *s2 ); makes no sense here. Change function to 

int match(char *s1, char *s2) {
    while( *s1 != '\0' && *s2 != '\0') {
        if(*s1 != *s2 )
             return 1;
        s1++; s2++;
    }

    return 0;
}
Improve this answer

1 Comment

Think about it again. It works. It is using sscanf() that is problematic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.