genkeys.c

/*
 * asleap - recover weak LEAP passwords.  Pronounced "asleep".
 *
 * Copyright (c) 2004, Joshua Wright <jwright@hasborg.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation. See COPYING for more
 * details.
 *
 * asleap is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 */

/*
 * Significant code is graciously taken from the following:
 * MS-CHAPv2 and attack tools by Jochen Eisinger, Univ. of Freiburg
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdint.h>
#include "common.h"
#include "version.h"
#include "utils.h"

#define PROGNAME "genkeys"

/* Globals */
unsigned long long sortcount;

int compfunc(const void *x, const void *y)
{

    struct hashpass_rec rec1, rec2;

    sortcount++;
    rec1 = (struct hashpass_rec)(*(struct hashpass_rec *)x);
    rec2 = (struct hashpass_rec)(*(struct hashpass_rec *)y);

    if (rec1.hash[15] == rec2.hash[15]) {
        return (0);
    } else if (rec1.hash[15] < rec2.hash[15]) {
        return (-1);
    } else {
        return (1);
    }
}

/* getnextrec accepts a record structure, a file pointer and a flag to indicate
   if we want to populate the password member of the structure (requires a
   malloc).  getnextrec populates the structure with the next record available,
   and returns the record length on success, or negative on failure. */
int getnextrec(struct hashpass_rec *rec, FILE * fp, int fillpass)
{
    int passlen;

    fread(&rec->rec_size, 1, 1, fp);

    passlen = (rec->rec_size - 17);

    if (fillpass) {
        if (passlen < 1) {
            perror("[getnextrec] Too short password length");
            return (-1);
        }

        if ((rec->password = malloc(passlen)) == NULL) {
            return (-1);
        }

        fread(rec->password, passlen, 1, fp);

    } else {

        /* Skip past the password */
        fseek(fp, passlen, SEEK_CUR);
    }

    fread(rec->hash, 16, 1, fp);

    return (rec->rec_size);
}

/* closebuckets accepts an array of type hashbucket_rec and closes each
   file handle.  There is no return value. */
void closebuckets(struct hashbucket_rec hbucket[256], int hsub)
{

    char bucketfile[256];
    for (hsub--; hsub != -1; hsub--) {
        fclose(hbucket[hsub].sbucket);
        sprintf(bucketfile, "genk-bucket-%02x.tmp", hsub);
        remove(bucketfile);
    }
}

void usage(char *message)
{

    if (strlen(message) > 0) {
        printf("%s: %s\n", PROGNAME, message);
    }

    printf("Usage: %s [options]\n", PROGNAME);
    printf("\n"
           "\t-r \tInput dictionary file, one word per line\n"
           "\t-f \tOutput pass+hash filename\n"
           "\t-n \tOutput index filename\n"
           "\t-h \tLast 2 hash bytes to filter with (optional)\n" "\n");
}

int main(int argc, char *argv[])
{

    char password[MAX_NT_PASSWORD + 1];
    unsigned char pwhash[MD4_SIGNATURE_SIZE];
    int passlen, getnextret, c;
    off_t recoffset;
    float elapsed = 0;
    unsigned long int wordcount = 0;
    struct timeval start, end;
    FILE *inputfl, *outputfl, *outputidx;
    struct hashpass_rec rec, tmprec;
    struct hashpassidx_rec idxrec;
    char wordlist[1025], datafile[1025], indexfile[1025];

    char bucketfile[255];
    unsigned int hsub = 0, brecsub = 0, bucketrecords;
    struct hashbucket_rec hbucket[256];
    struct hashpass_rec *brec;

    printf("genkeys %s - generates lookup file for asleap. "
           "<jwright@hasborg.com>\n", VER);

    while ((c = getopt(argc, argv, "r:f:n:h:")) != EOF) {
        switch (c) {
        case 'r':
            strncpy(wordlist, optarg, sizeof(wordlist) - 1);
            break;
        case 'f':
            strncpy(datafile, optarg, sizeof(datafile) - 1);
            break;
        case 'n':
            strncpy(indexfile, optarg, sizeof(indexfile) - 1);
            break;
        default:
            usage("");
            exit(1);
        }
    }

    if (IsBlank(wordlist) || IsBlank(datafile) || IsBlank(indexfile)) {
        usage("Must supply -r -f and -n");
        exit(1);
    }

    if (*wordlist == '-') {
        printf("Using STDIN for words.\n");
        inputfl = stdin;
    } else {
        if ((inputfl = fopen(wordlist, "rb")) == NULL) {
            perror("fopen");
            exit(1);
        }
    }

    if ((outputfl = fopen(datafile, "wb")) == NULL) {
        perror("fopen");
        fclose(outputfl);
        exit(1);
    }

    if ((outputidx = fopen(indexfile, "wb")) == NULL) {
        perror("fopen");
        fclose(outputfl);
        exit(1);
    }

    /* Create the appropriate buckets for the output files to be used for
       sorting the pass+hash file */

    memset(hbucket, 0, sizeof(hbucket));
    memset(bucketfile, 0, sizeof(bucketfile));

    printf("Generating hashes for passwords (this may take some time) ...");
    fflush(stdout);

    gettimeofday(&start, 0);

    /* create the bucket files */
    for (hsub = 0; hsub < 256; hsub++) {
        sprintf(bucketfile, "genk-bucket-%02x.tmp", hsub);
        if ((hbucket[hsub].sbucket = fopen(bucketfile, "wb")) == NULL) {
            /* Crap, now we have to back-track to close everything we opened */
            closebuckets(hbucket, hsub);
            fprintf(stderr, "Error creating bucket files. ");
            perror("fopen");
            exit(1);
        }
    }

    while (!feof(inputfl)) {

        fgets(password, MAX_NT_PASSWORD + 1, inputfl);
        /* Remove newline */
        password[strlen(password) - 1] = 0;

        /* Code to accommodate Windows-formatted dictionary files on Linux.
           Thanks ocnarfid8/#kismet.
         */
        if (password[strlen(password) - 1] == 0x0d) {
            password[strlen(password) - 1] = 0;
        }

#ifndef _OPENSSL_MD4
        /* md4.c seems to have a problem with passwords longer than 31 bytes.
           This seems odd to me, but it should have little impact on our
           final product, since I assume there are few passwords we will be
           able to identify with a dictionary attack that are longer than 31
           bytes. */
        password[31] = 0;
#endif

        NtPasswordHash(password, strlen(password), pwhash);

        memcpy(rec.hash, pwhash, sizeof(rec.hash));
        rec.rec_size = (strlen(password) + sizeof(rec.hash)
                + sizeof(rec.rec_size));

        /* Write the output record to the correct bucket, depending on byte
           14 of the hash value. */
        hsub = rec.hash[14];
        fwrite(&rec.rec_size, sizeof(rec.rec_size), 1,
               hbucket[hsub].sbucket);
        fwrite(password, strlen(password), 1, hbucket[hsub].sbucket);
        fwrite(&rec.hash, sizeof(rec.hash), 1, hbucket[hsub].sbucket);

        hbucket[hsub].numrec++;
        wordcount++;
    }

    /* Flush all buffers before closing -- I don't think this is really
       necessary, but it's kind of a belt-and-suspenders thing.  No one ever
       said I was a snappy dresser. */
    fflush(NULL);
    fclose(inputfl);

    /* Close and reopen all the buckets (they were in "w" mode) */

    for (hsub = 0; hsub < 256; hsub++) {
        sprintf(bucketfile, "genk-bucket-%02x.tmp", hsub);
        fclose(hbucket[hsub].sbucket);
        if ((hbucket[hsub].sbucket = fopen(bucketfile, "rb")) == NULL) {
            closebuckets(hbucket, hsub);
            fprintf(stderr, "Error re-opening bucket files.");
            perror("fopen");
            exit(1);
        }
    }

    printf("Done.\n");

    /* Report stats on writing hashes */
    gettimeofday(&end, 0);

    /* Borrowed from Tim Newsham's wep_crack.c -- thanks Tim */
    if (end.tv_usec < start.tv_usec) {
        end.tv_sec -= 1;
        end.tv_usec += 1000000;
    }
    end.tv_sec -= start.tv_sec;
    end.tv_usec -= start.tv_usec;
    elapsed = end.tv_sec + end.tv_usec / 1000000.0;

    printf("%lu hashes written in %.2f seconds:  %.2f hashes/second\n",
           wordcount, elapsed, wordcount / elapsed);

    printf("Starting sort (be patient) ...");
    fflush(stdout);

    hsub = 0;
    while (hsub < 256) {
        sprintf(bucketfile, "genk-bucket-%02x.tmp", hsub);

        /* If there are no records in the bucket, unlink */
        if (hbucket[hsub].numrec == 0) {
            /* Bucket is empty, get rid if it */
            fclose(hbucket[hsub].sbucket);
            hbucket[hsub].sbucket = NULL;
            unlink(bucketfile);
            hsub++;
            continue;
        }

/*
 * With all our buckets created, clean up and then sort each bucket.  After
 * Sorting the bucket, write the output file to the outputfl handle for one
 * big file.
 */

        /* malloc() enough space in memory for each record that we have to
           load into memory for sorting */
        if ((brec = calloc(hbucket[hsub].numrec, sizeof(rec))) == NULL) {
            fprintf(stderr,
                "Unable to allocate %ld bytes of memory.  ",
                (hbucket[hsub].numrec * sizeof(rec)));
            closebuckets(hbucket, 256);
            perror("malloc");
            exit(-1);
        }

        bucketrecords = hbucket[hsub].numrec;
        for (brecsub = 0; brecsub < bucketrecords; brecsub++) {

            /* Get 1 byte for the record length */
            if (fread(&brec[brecsub].rec_size, 1, 1,
                  hbucket[hsub].sbucket) != 1) {
                fprintf(stderr,
                    "Unable to read from bucket %02x. ",
                    hsub);
                perror("fread");
                closebuckets(hbucket, 256);
                exit(-1);
            }

            /* Calculate password length - 17 is hash+rec length byte */
            passlen = (brec[brecsub].rec_size - 17);

            /* malloc() memory for this password based on password length */
            if ((brec[brecsub].password =
                 malloc(passlen + 1)) == NULL) {
                fprintf(stderr,
                    "Cannot allocate %d bytes of memory. ",
                    (passlen + 1));
                perror("malloc");
                closebuckets(hbucket, 256);
                exit(-1);
            }
            memset(brec[brecsub].password, 0, passlen + 1);

            /* Populate the password field with the next parameter in the 
               record */
            fread(brec[brecsub].password, passlen, 1,
                  hbucket[hsub].sbucket);

            /* Populate the hash field with the final parameter in the record */
            fread(brec[brecsub].hash, 16, 1, hbucket[hsub].sbucket);
        }

        /* sort this bucket */
        qsort(brec, hbucket[hsub].numrec, sizeof(rec), compfunc);

        /* Write the sorted records to the outputfl handle */
        for (brecsub = 0; brecsub < bucketrecords; brecsub++) {
            passlen = brec[brecsub].rec_size - 17;
            fwrite(&brec[brecsub].rec_size, sizeof(rec.rec_size), 1,
                   outputfl);
            fwrite(brec[brecsub].password, passlen, 1, outputfl);
            fwrite(brec[brecsub].hash, sizeof(rec.hash), 1,
                   outputfl);
            free(brec[brecsub].password);
        }

        /* Get rid of the bucket */
        fclose(hbucket[hsub].sbucket);
        sprintf(bucketfile, "genk-bucket-%02x.tmp", hsub);
        remove(bucketfile);
        free(brec);

        hsub++;

    }

    fflush(outputfl);
    fclose(outputfl);

    printf("Done.\nCompleted sort in %llu compares.\n", sortcount);
    printf("Creating index file (almost finished) ...");
    fflush(stdout);

    /* Re-open output file "r" */
    if ((outputfl = fopen(datafile, "rb")) == NULL) {
        perror("fopen");
        fclose(outputfl);
        exit(1);
    }

/* Create the index file - populate an initial record, then keep reading
 * through the file.  When the last 2 bytes of the hash change, write the
 * index record to the index file and keep reading records until EOF.
 */

    recoffset = 0;
    getnextret = 0;

    /* Populate the initial index record from the outputfl */
    if ((getnextret = getnextrec(&tmprec, outputfl, 0)) < 0) {
        perror("getnextrec");
        exit(-1);
    }

    memset(&idxrec, 0, sizeof(idxrec));
    memset(&rec, 0, sizeof(rec));

    /* Update the offset of the record, this is always 0 for the first record */
    recoffset = recoffset + getnextret;

    idxrec.hashkey[0] = tmprec.hash[14];
    idxrec.hashkey[1] = tmprec.hash[15];
    idxrec.offset = 0;
    idxrec.numrec = 1;

    while (!feof(outputfl)) {

        if ((getnextret = getnextrec(&rec, outputfl, 0)) < 0) {
            perror("getnextrec");
            exit(-1);
        }
        recoffset = recoffset + getnextret;

        if (idxrec.hashkey[0] != rec.hash[14] ||
            idxrec.hashkey[1] != rec.hash[15]) {

            /* Finished reading records for this hash key value.  Write the
               index record and populate the next index record. */
            if (fwrite(&idxrec, sizeof(idxrec), 1, outputidx) != 1) {
                perror("Error writing index record");
                fclose(outputfl);
                fclose(outputidx);
            }
            //           fflush(outputidx);
            /*
               printf("DEBUG index record:\n");
               printf("idxrec.hashkey = %02x%02x\n", idxrec.hashkey[0], idxrec.hashkey[1]);
               printf("idxrec.offset = %llu\n", idxrec.offset);
               printf("idxrec.numrec = %llu\n", idxrec.numrec);
               printf("========================================================\n");
             */

            /* Initialize struct for the next index entry set */
            memset(&idxrec, 0, sizeof(idxrec));

            /* Populate the next hash reference and offset */
            idxrec.hashkey[0] = rec.hash[14];
            idxrec.hashkey[1] = rec.hash[15];
            idxrec.offset = recoffset - getnextret;
            idxrec.numrec = 1;
            continue;

        } else {
            /* Got another record with the same hash value, increment count */
            idxrec.numrec++;
            continue;
        }
    }

    /* Write the final index record */
    if (fwrite(&idxrec, sizeof(idxrec), 1, outputidx) != 1) {
        perror("Error writing final index record");
        fclose(outputfl);
        fclose(outputidx);
        exit(-1);
    }

    fclose(outputfl);
    fclose(outputidx);

    printf("Done.\n");
    fflush(stdout);

    exit(0);

}