aeskeyfind.c

// AESKeyFinder 1.0 (2008-07-18)
// By Nadia Heninger and Ariel Feldman
// Hacked 2017-05-11 by Aidan Thornton to know more key schedules
// With code from axTLS by Cameron Rich

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <sys/stat.h>
#include <windows.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <wchar.h>
//linux依存
//#include <sys/mman.h>:mmap用
//#include <unistd.h>:
//#include <getopt.h>:コマンドライン操作

extern char *optarg;
extern int optind, opterr, optopt;


#ifdef __FreeBSD__
#include <err.h>
#else
#define err(x,y) { perror(y); exit(x); }
#endif

#include "util.h"
#include "aes.h"
#include "getopt.h"

#define DEFAULT_THRESHOLD 10
static long int gThreshold = DEFAULT_THRESHOLD;
static int gVerbose = 0;
static int gProgress = 1;

#define TWEAK_INVMIXCOLUMN 0x1
#define TWEAK_REVERSE_ORDER 0x2
#define MAX_TWEAKS 0x4

// Print a key, assuming the key schedule starts at map[0].  
// num_bits should be 128 or 256 
// if gVerbose is on it will print the entire key schedule as well 
// as the constraints--the XOR of words that should XOR to 0
// Verboseがオンの場合、キースケジュール全体と制約（0とXORする必要がある単語のXOR）が出力されます。
static void print_key(uint32_t* map, int num_bits, size_t address)
{
    if (gVerbose) {
        printf("FOUND POSSIBLE %d-BIT KEY AT BYTE %zx \n\n", num_bits, address);
        printf("KEY: ");
    }

    int num_words = num_bits/32;
    for (int col = 0; col < num_words; col++)
        print_word(map[col]);
    printf("\n");


    if (gVerbose) {
        printf("\n");
        printf("EXTENDED KEY: \n");

        int num_roundkeys = 0;
        if (num_bits == 256) num_roundkeys = 15;
        if (num_bits == 128) num_roundkeys = 11;
        for (int row=0; row<num_roundkeys; row++) {
            for (int column = 0; column<4; column++) {
                print_word(map[(4*row+column)]);
            }
            printf("\n");
        }

        printf("\n");
        printf("CONSTRAINTS ON ROWS:\n");

        for (int row=1; row<num_roundkeys; row++) {
            for (int column = 0; column<num_words; column++) {
                if (num_bits == 256 && row == 7 && column >= 4) break;
                if (column==0)
                    print_word(key_core(map[num_words*row-1],row) ^
                            map[num_words*(row-1)] ^
                            map[num_words*row]);
                else if (column == 4)
                    print_word(sbox_bytes(map[num_words*row+3]) ^
                            map[num_words*(row-1)+4] ^
                            map[num_words*row+4]);
                else
                    print_word(map[num_words*row+column-1] ^
                            map[num_words*(row-1)+column] ^
                            map[num_words*row + column]);
            }
            printf("\n");
        }
        printf("\n");
    }
}

// Simple entropy test
//
// Returns true if the 176 bytes starting at location bmap[i] contain
// more than 8 repeats of any byte.  This is a (原始的測定)primitive measure of
// entropy, but it works well enough.  The function keeps track of a
// sliding window of byte counts.
static int entropy(const uint8_t* bmap, size_t i)
{
    static int new_call = 1;
    static int byte_freq[256] = {0};
    if (new_call) {
        for (int i=0; i<176; i++) byte_freq[bmap[i]]++;
        new_call = 0;
    }

    int test = 0;
    for (int b=0; b<=0xFF; b++) {
        if (byte_freq[b] > 8) {
            test = 1;
            break;
        }
    }
    byte_freq[bmap[i]]--;
    byte_freq[bmap[i+176]]++;
    return test;
}

// Prints info about the program's command line options
static void usage()
{
    fprintf(stderr, "Usage: aeskeyfind [OPTION]... MEMORY-IMAGE\n"
			"Locates scheduled 128-bit and 256-bit AES keys in MEMORY-IMAGE.\n"
			"\n"
			"\t-v\t\tverbose output -- prints the extended keys and \n"
            "\t\t\tthe constraints on the rows of the key schedule\n"
			"\t-q\t\tdon't display a progress bar\n"
			"\t-t THRESHOLD\tsets the maximum number of bit errors allowed \n"
            "\t\t\tin a candidate key schedule (default = %d)\n"
			"\t-h\t\tdisplays this help message\n", DEFAULT_THRESHOLD);
}

// Prints the progress to stderr
static void print_progress(size_t percent)
{
    fprintf(stderr, "Keyfind progress: %zu%%\r", percent);
}

static unsigned char AES_xtime(uint32_t x)
{   
    // 条件演算子
	return (x&0x80) ? (x<<1)^0x1b : x<<1;
}

// 普通のキースケジュールへと復号する最適化として，
// InvMixColumnがプリ適応されたキースケジュールを変換
// このコードは追加された拡張機能
// converts a key schedule that's had InvMixColumn pre-applied as
// an optimisation for decryption back to a normal key schedule
// added code------------------------------------------------------
//static void unconvert_key(uint32_t *k, int rounds)
//{
//    int i;
//    uint32_t w, tmp1, old_a0, a0, a1, a2, a3;
//
//    k += 4;
//
//    for (i= rounds*4; i > 4; i--)
//    {
//        w= *k;
//
//	// note: a quirk of aeskeyfind is that the bytes are in
//	// reverse order within the word compared to normal AES
//	a3 = (uint32_t)((w>>24)&0xFF);
//	a2 = (uint32_t)((w>>16)&0xFF);
//	a1 = (uint32_t)((w>>8)&0xFF);
//	a0 = (uint32_t)(w&0xFF);
//
//	tmp1 = a0 ^ a1 ^ a2 ^ a3;
//	old_a0 = a0;
//	a0 ^= tmp1 ^ AES_xtime(a0 ^ a1);
//	a1 ^= tmp1 ^ AES_xtime(a1 ^ a2);
//	a2 ^= tmp1 ^ AES_xtime(a2 ^ a3);
//	a3 ^= tmp1 ^ AES_xtime(a3 ^ old_a0);
//
//	*k++ =  ((a3 << 24) | (a2 << 16) | (a1 << 8) | a0);
//    }
//}
// added code------------------------------------------------------

// The core key finding loop
//
// Searches for AES keys in memory image bmap with starting offsets up
// to last; prints any keys found
// bmapはunsigned char[]，これの中身は
static void find_keys(const uint8_t* bmap, size_t last)
{
    size_t percent = 0;
    const size_t increment = last / 100;

    if (gProgress)
        print_progress(percent);

    for (size_t i = 0; i < last; i++) {
        if (entropy(bmap,i)) continue;

        // uint32_t型のポインタにbmap[i]のアドレスをキャスト
        uint32_t* map = (uint32_t*)&(bmap[i]);

        // Check distance from 256-bit AES key
	// FIXME: implement tweaks here too
        int xor_count_256 = 0;
        for (size_t row = 1; row < 8; row++) {
            for (size_t column = 0; column < 8; column++) {
                if (row == 7 && column == 4) break;
                if (column == 0)
                    xor_count_256 += popcount(key_core(map[8*row-1],row) ^
                            map[8*(row-1)] ^
                            map[8*row]);
                else if (column == 4)
                    xor_count_256 += popcount(sbox_bytes(map[8*row+3])^
                            map[8*(row-1)+4] ^
                            map[8*row+4]);
                else
                    xor_count_256 += popcount(map[8*row+column-1] ^
                            map[8*(row-1)+column] ^
                            map[8*row + column]);
            }
	    if (xor_count_256 > gThreshold)
	      break;
        }
        if (xor_count_256 <= gThreshold)
            print_key(map,256,i);
    
	//速度が低下するので除外
    // added code-----------------------------------------------
	//for(int tweaks = 0; tweaks < MAX_TWEAKS; tweaks++) {
	//    // Try various tweaks to how key schedule is storted
	//    uint32_t newmap[4*11];
	//    map = (uint32_t*)&(bmap[i]);
	//    if(tweaks & TWEAK_REVERSE_ORDER)
	//	for (size_t row = 0; row < 11; row++)
	//	    memcpy(newmap+4*row, map+4*(10-row), 4*sizeof(uint32_t));
	//    else
	//	memcpy(newmap, map, 4*11*sizeof(uint32_t));
	//    map = newmap;
	//    if(tweaks & TWEAK_INVMIXCOLUMN)
	//	unconvert_key(map, 10);
    // added code-----------------------------------------------

	    // Check distance from 128-bit AES key
        // rowがラウンド数と対応
        // map[n]の型はuin32_t=4byte=32bit
        // columnがkey長に対応，4回確かめて128bit分の鍵であるか検証
        // columnが0のときは先頭ワードであり，特別な置換が行われているから条件分けされている
        // key_core(map[4*row-1],row):先頭ワード用のrow-1番目のラウンドキー(map[4*row-1]とする)
        // から作成したrow番目のラウンドキー
        // map[4*(row-1)]:row-1番目のラウンドキー(32bit)
        // map[4*row]:row番目のラウンドキー(32bit)
        // (row番目ラウンド,column-1番目ワード)xor(row-1番目ラウンド,column番目ワード)xor(row番目ラウンド,column番目ワード)
        // Ex:  W4(1,0) xor W1(0,1) xor W5(1,1)
        // この式はラウンドキーがAESの定義通り実装されている場合0となる
		int xor_count_128 = 0;
	    for (size_t row = 1; row < 11; row++) {
		for (size_t column = 0; column < 4; column++) {
		    if (column == 0)
			xor_count_128 += popcount(key_core(map[4*row-1],row) ^
						  map[4*(row-1)] ^
						  map[4*row]);
		    else
			xor_count_128 += popcount((map[4*row + column-1] ^
						   map[4*(row-1)+column]) ^
						  map[4*row + column]);
		}
		if (xor_count_128 > gThreshold)
		    break;
	    }
	    if (xor_count_128 < gThreshold)
		print_key(map,128,i);
	//}

        if (gProgress) {
            size_t pct = (increment > 0) ? i / increment : i * 100 / last;
            if (pct > percent) {
                percent = pct;
                print_progress(percent);
            }
        }
    }

    if (gProgress) {
        print_progress(100);
        fprintf(stderr, "\n");
    }
}

// ファイルオープン，ファイルのポインター，大きさを返す
//linux依存コード
// Memory maps filename and return a pointer on success, setting len
// to the length of the file (does not return on error)
//unsigned char *map_file(char *filename, size_t *len) {
//  int fd = open(filename, O_RDONLY);
//  if (fd < 0)
//    err(1, "image open failed");
//
//  struct stat st;
//  if (fstat(fd, &st) != 0)
//    err(1, "image fstat failed");
//
//  unsigned char *map;
//  map = (unsigned char*)mmap(0, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
//  if (map == MAP_FAILED)
//    err(1, "image mmap failed");
//
//  *len = st.st_size;
//  return map;
//}

unsigned char* map_file(const char* filename, LONGLONG* len) {
	HANDLE hFile = CreateFile(filename, GENERIC_READ, 0, NULL, OPEN_EXISTING, 0, NULL);
	if (hFile == INVALID_HANDLE_VALUE)
		err(1, "image open failed");
	if (!GetFileSizeEx(hFile, len)) {
		CloseHandle(hFile);
		err(1, "get file_size failed");
	}
	HANDLE hMap = CreateFileMapping(hFile,NULL,PAGE_READONLY,0,0,"m_Image");
	if (hMap == NULL) {
		CloseHandle(hFile);
		hFile = INVALID_HANDLE_VALUE;
		err(1, "image mapping failed");
	}
	void* m_pPointer = (char*)MapViewOfFile(hMap, FILE_MAP_READ, 0, 0, 0);
	if (m_pPointer == NULL) {
		CloseHandle(hMap);
		CloseHandle(hFile);
		hMap = 0;
		hFile = INVALID_HANDLE_VALUE;
		err(1, "image mvof failed");
	}
	return m_pPointer;
	
}

int main(int argc, char * argv[])
{
    int ch = -1;
    while ((ch = getopt(argc, argv, "hvqt:")) != -1) {
        switch(ch) {
            case 'v':
                gVerbose = 1;
                break;
            case 'q':
                gProgress = 0;
                break;
            case 't':
                {
                    errno = 0;
                    char* endptr = NULL;
                    gThreshold = strtol(optarg, &endptr, 10);
                    if (gThreshold < 0 || errno != 0 || endptr == optarg) {
                        fprintf(stderr, "invalid threshold\n");
                        usage();
                        exit(1);
                    }
                }
                break;
            case '?':
            case 'h':
            default:
                usage();
                exit(1);
        }
    }

    argc -= optind;
    argv += optind;

    if (argc != 1) {
        usage();
        exit(1);
    }
	
    LONGLONG len;
    unsigned char *image = map_file(argv[0], &len);
	//char *filename = "D:\\my_program\\medusa_unlocker\\medusa.dump";
	//unsigned char* image = map_file(filename, &len);
	printf("filesize:%lld",len);
	puts("");
	if (len < 240) {
	fprintf(stderr, "memory image too small\n");
	exit(1);
	}
	
    find_keys(image, len - 240);

    return 0;
}