Buffer overflows - overwriting a string

Question

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?

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

score 3 · Answer 1 · answered Oct 14 '13 at 14:08

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.

answered Oct 14 '13 at 14:08

Lundin

195,001
40
254
396

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 Oct 14 '13 at 14:14
1

@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. – Lundin Oct 14 '13 at 14:17
@MrDiggles The above is especially true on high-end systems like Linux/x86, where the system will have stack frames and alignment requirements. – Lundin Oct 14 '13 at 14:19
@Lundin It's a programming competition problem centered around security, an exercise in understanding the basics of security in software development. The environment they have set up is meant to facilitate these kinds of exploits. – MrDiggles Oct 14 '13 at 14:20
2

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. – Axel Oct 14 '13 at 14:23
1

@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](http://c-faq.com/stdio/scanfprobs.html) has some nice information about the topic. – Lundin Oct 14 '13 at 14:25
2

@Axel If that was the case, then then question should hand out the binary, rather than the high-level programming language source code. – Lundin Oct 14 '13 at 14:28

score 2 · Accepted Answer · answered Oct 14 '13 at 14:33

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.

answered Oct 14 '13 at 14:33

Axel

13,939
5
50
79

Oh wow, it was that easy. I just spend the last hour poring over addresses in gdb. Thanks so much! – MrDiggles Oct 14 '13 at 14:39
Indeed... Good answer! – haccks Oct 15 '13 at 08:58

user694733 · Answer 3 · 2013-10-14T14:04:01.743

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.

edited Oct 14 '13 at 14:04

answered Oct 14 '13 at 13:57

user694733

15,208
2
42
68

Wait, why do You say "not necessarily next to each other in memory". AFAIk they will be. – icbytes Oct 14 '13 at 14:00
@icbytes Nothing stops implementation from adding extra data to stack between the buffers. – user694733 Oct 14 '13 at 14:02
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 Oct 14 '13 at 14:05
@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. – user694733 Oct 14 '13 at 14:08
@MrDiggles; This is not the case always. – haccks Oct 14 '13 at 14:09

score 1 · Answer 4 · edited May 23 '17 at 12:21

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.

edited May 23 '17 at 12:21

Community

1
1

answered Oct 14 '13 at 14:02

Axel

13,939
5
50
79

Only str2 can overwrite str1, from what I've observed. – MrDiggles Oct 14 '13 at 14:10

haccks · Answer 5 · 2013-10-14T14:06:14.573

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;
}

edited Oct 14 '13 at 14:06

answered Oct 14 '13 at 13:53

haccks

104,019
25
176
264

Think about it again. It works. It is using `sscanf()` that is problematic. – Axel Oct 15 '13 at 07:05

Buffer overflows - overwriting a string

5 Answers5