[picoCTF] General Skills - flag_shop

 

Description

There's a flag shop selling stuff, can you buy a flag? Source

 

Solve

Integer Overflow 에 관한 문제다. int는 4byte 크기이다 (-2,147,483,648 ~ 2,147,483,647)

 

Source Review

#include <stdio.h>
#include <stdlib.h>
int main()
{
    setbuf(stdout, NULL);
    int con;
    con = 0;
    int account_balance = 1100;
    while(con == 0){
        
        printf("Welcome to the flag exchange\n");
        printf("We sell flags\n");

        printf("\n1. Check Account Balance\n");
        printf("\n2. Buy Flags\n");
        printf("\n3. Exit\n");
        int menu;
        printf("\n Enter a menu selection\n");
        fflush(stdin);
        scanf("%d", &menu);
        if(menu == 1){
            printf("\n\n\n Balance: %d \n\n\n", account_balance);
        }
        else if(menu == 2){
            printf("Currently for sale\n");
            printf("1. Defintely not the flag Flag\n");
            printf("2. 1337 Flag\n");
            int auction_choice;
            fflush(stdin);
            scanf("%d", &auction_choice);
            if(auction_choice == 1){
                printf("These knockoff Flags cost 900 each, enter desired quantity\n");
                
                int number_flags = 0;
                fflush(stdin);
                scanf("%d", &number_flags);
                if(number_flags > 0){
                    int total_cost = 0;
                    total_cost = 900*number_flags;
                    printf("\nThe final cost is: %d\n", total_cost);
                    if(total_cost <= account_balance){
                        account_balance = account_balance - total_cost;
                        printf("\nYour current balance after transaction: %d\n\n", account_balance);
                    }
                    else{
                        printf("Not enough funds to complete purchase\n");
                    }
                                    
                    
                }
                    
                    
                    
                
            }
            else if(auction_choice == 2){
                printf("1337 flags cost 100000 dollars, and we only have 1 in stock\n");
                printf("Enter 1 to buy one");
                int bid = 0;
                fflush(stdin);
                scanf("%d", &bid);
                
                if(bid == 1){
                    
                    if(account_balance > 100000){
                        FILE *f = fopen("flag.txt", "r");
                        if(f == NULL){

                            printf("flag not found: please run this on the server\n");
                            exit(0);
                        }
                        char buf[64];
                        fgets(buf, 63, f);
                        printf("YOUR FLAG IS: %s\n", buf);
                        }
                    
                    else{
                        printf("\nNot enough funds for transaction\n\n\n");
                    }}

            }
        }
        else{
            con = 1;
        }

    }
    return 0;
}

• 34 ~ 36번 라인을 보면 지역 변수 안에 int 형 선언한 뒤 그 밑에 scanf로 사용자 입력을 받아들여 초기화 하고 있다.
• 39 번 라인에서는 total_cost = 900 * number_flags 연산식을 통해 사용자 입력을 통해 받아 들인 number_flags 값을 계산해서 total_cost 값이 계산되고 있는 것을 확인할 수 있다.
• 41번 라인에서는 total_cost가 account_balance 보다 낮을 경우
  • 42번 라인으로 분기한 뒤 account_balance = account_balance - total_count 연산식으로 account_balance를 초기화 시킨다.

 

Approach

소스 코드 상으로 flag얻으려면 3번 옵션을 통해서 flag를 얻을 수 있지만 그러려면 account_balance의 값을 조절해야된다. 조절할 수 있는 방법은 2번 옵션의 flow에서 account_balance를 초기화 시키는 라인에서 무언가를 해야될 듯 보인다.

Source Review에서 보았듯 integer overflow를 이용하면 39번 라인의 결과를 통해 42번 라인에 영향을 줄 수 있을 것 같아 보인다. 39번 라인에 total_cost 값을 integer overflow를 통해 최소 음수값으로 만들게 되면 42번 라인의 연산식에서 다음과 같이 동작할 것이다

account_balance = account_balance - (-total_cost)

위 식에서 알 수 있는 것은 -(-total_cost)가 양수가 된다는 점이다. 주의해야 될 점은 account_balance도 integer로 선언되어있다는 점이다.

즉 account_balance - (-total_cost)의 값이 integer overflow를 이용해 100,000 보다 큰 값으로 초기화 시키는 number_flags 값을 입력

예를 들어 다음과 같다

number_flags = 2386093
account_balance = 1100 - (-(900 * 2386093))
account_balance = 1100 + 2147483700
account_balance = -2147482600

• 위 계산 결과를 통해 보면 2386903을 입력해서는 account_balance를 100,000 보다 크게 만들 수는 없다

100,000 보다 크게 만드려면? 다음과 같은 계산을 통해 예측해봤다.

최소 음수값은 -2,147,483,648 이다. -100,001 만큼 더해준다. 결과는 -2147583649 이다.
앞서 언급했듯 -(-) 는 + 이기 때문에 부호는 크게 신경쓰지 않는다.

2147583649 / 900 로 나눈 뒤 반올림 한 값(2386204) 을 입력해준다

 

연산식은 다음과 같이 동작할 것이다

number_flags = 2386204
number_flags = 900 * 2386204 = 2147583600 // 2147583600 은 over flow의 결과는 -2147383696 이다

account_balance = 1100 -(-2147383696) = 2147384796
// 2147384796의 over flow 의 결과는 2147384796 이다
// int의 max 값이 2,147,483,648이기 떄문에  2,147,384,796 은 overflow가 일어나지 않는다.

account_balance는 2,147,384,796 로 초기화 된다.

 

Result