two-sum.md

two-sum

Overview

100 points

Category: Binary Exploitation

Tags : #overflow #integermath

Description

Can you solve this? What two positive numbers can make this possible: n1 > n1 + n2 OR n2 > n1 + n2 Enter them here nc saturn.picoctf.net <port>.

Approach

Source provided in flag.c :

#include <stdio.h>
#include <stdlib.h>

static int addIntOvf(int result, int a, int b) {
    result = a + b;
    if(a > 0 && b > 0 && result < 0)
        return -1;
    if(a < 0 && b < 0 && result > 0)
        return -1;
    return 0;
}

int main() {
    int num1, num2, sum;
    FILE *flag;
    char c;

    printf("n1 > n1 + n2 OR n2 > n1 + n2 \n");
    fflush(stdout);
    printf("What two positive numbers can make this possible: \n");
    fflush(stdout);
    
    if (scanf("%d", &num1) && scanf("%d", &num2)) {
        printf("You entered %d and %d\n", num1, num2);
        fflush(stdout);
        sum = num1 + num2;
        if (addIntOvf(sum, num1, num2) == 0) {
            printf("No overflow\n");
            fflush(stdout);
            exit(0);
        } else if (addIntOvf(sum, num1, num2) == -1) {
            printf("You have an integer overflow\n");
            fflush(stdout);
        }

        if (num1 > 0 || num2 > 0) {
            flag = fopen("flag.txt","r");
            if(flag == NULL){
                printf("flag not found: please run this on the server\n");
                fflush(stdout);
                exit(0);
            }
            char buf[60];
            fgets(buf, 59, flag);
            printf("YOUR FLAG IS: %s\n", buf);
            fflush(stdout);
            exit(0);
        }
    }
    return 0;
}

The program asks for two integers and sums them, if sum is less than either of the input values then the flag is dropped. This is simple integer overflow.

The input values and sum are all handled as signed integers.

Maximum signed integer value is 2,147,483,647.

Solution

Plan of attack :

1. Select two numbers that overflow the maximum positive range of a signed integer when added, the first very close (or equal) to the maximum, the second just enough to overflow, such that the sum is less than the first number.

Output from running the above input during the event (actual value of the flag has been redacted for the purposes of this write up) :

$ echo -e "2147483647\n1" | nc saturn.picoctf.net 57395
n1 > n1 + n2 OR n2 > n1 + n2 
What two positive numbers can make this possible: 
You entered 2147483647 and 1
You have an integer overflow
YOUR FLAG IS: picoCTF{............redacted................}