IDA Pro

brute.c

// clang -Werror -Wall -O3 -mssse3 -msha cpu-brute.c sha.c prng.c -o brute && scp brute scanifi:/tmp

#include "sha1.h"

#define gen_bsd_drand48 1
// #define gen_msvc_rand 1
#include "prng.h"

#include <stdint.h>
#include <math.h>
#include <stdio.h>
#include <memory.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <signal.h>

#define IDA72 1

#define PARALLEL 48
int main()
{
    char* charset = "abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";

#ifdef IDA72
    uint8_t hash[20] = 
    { // ida 7.2
        0xF2, 0x9F, 0x55, 0xF0, 0x7C, 0x04, 0x3A, 0xD3, 0x4B, 0x3D, 0xE1, 0x50,
        0x50, 0x15, 0x35, 0xF4, 0x44, 0x24, 0xED, 0xAD
    };
#else
    uint8_t hash[20] = 
    { // ida 7.0
        0x7B, 0xA6, 0xF1, 0xDF, 0x9B, 0x88, 0xA2, 0x5C, 0x6C, 0x5D, 0xA5, 0x22,
        0xCC, 0xC3, 0x07, 0x24, 0x8A, 0xA0, 0xEC, 0x62
    };
#endif

#define SALT_LEN 25
#ifdef IDA72
    uint8_t pw[49] = { // ida 7.2. utf-16 LE, unknown rng
        0x50, 0x61, 0x73, 0x73, 0x77, 0x6F, 0x72, 0x64, 0x43, 0x68, 0x65, 0x63,
        0x6B, 0x48, 0x61, 0x73, 0x68, 0xC4, 0x16, 0x39, 0x79, 0x28, 0x46, 0xE4,
        0x56, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00
    };
#define PW_UTF16LE 1
#else
    uint8_t pw[37] = { // ida 7.0 MS-ANSI, msvc rng, seed=0x3AC5C29B
        0x50, 0x61, 0x73, 0x73, 0x77, 0x6F, 0x72, 0x64, 0x43, 0x68, 0x65, 0x63,
        0x6B, 0x48, 0x61, 0x73, 0x68, 0x84, 0x6E, 0x85, 0x47, 0x45, 0x12, 0xDF,
        0xF8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00
    };
#define PW_UTF16LE 0
#endif

    perl_rand_state rand_state;
    sha1_ctx ctx;
    uint8_t digest[20];
    
    uint32_t seed = 0;
    uint32_t upto = (uint32_t)(0x100000000L / (uint64_t)PARALLEL);
    int worker = 0;
    for (; worker < PARALLEL; worker++) {
        if (!fork()) {
            printf("Worker %d, bruting %x to %x\n", worker,seed,upto);
            break; // child
        }
        seed = upto;
        upto += (uint64_t)(0x100000000L / (uint64_t)PARALLEL);
    }

    do
    {
        if (!(seed & 0xffffff)) printf("%x\n", seed);
        perl_srand(&rand_state, seed);

#ifdef IDA72
        perl_rand(&rand_state); // discard first result?!
#endif

        for (int i = 0, j = 0; i < 12; i++)
        {
            int key = (int)(perl_rand(&rand_state) * 54.0);
            pw[j+++SALT_LEN] = charset[key];
            if (PW_UTF16LE) pw[j+++SALT_LEN] = '\0';
        }
        SHA1Init(&ctx);
        SHA1Update(&ctx, pw, sizeof(pw));
        SHA1Final(&ctx, digest);
        
        if (!memcmp(digest, hash, 20))
        {
            int fd = open("sice.txt", O_APPEND | O_RDWR | O_CREAT,0);
            printf("CRACKED!!!! %x\n", seed);
            dprintf(fd, "CRACKED!!!! %x\n", seed);
            for (int i = 0; i < (PW_UTF16LE ? 24 : 12); i += (PW_UTF16LE ? 2 : 1)) {
                printf("%c", pw[i + SALT_LEN]);
                dprintf(fd, "%c", pw[i + SALT_LEN]);
            }
            printf("\n");
            dprintf(fd, "\n");
            close(fd);
            kill(0, SIGQUIT);
            break;
        }
    } while(++seed != upto);
    printf("Worker %d done\n", worker);
}

brute.pl

#!/usr/bin/env perl
#
@_e = split //,"abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";

for ($seed=0;$seed<4294967296;++$seed)
{
    # $i=3326487116;
    srand($seed);
    $pw="";
    for($i=0;$i<12;++$i)
    {
            $key = rand 54;
            $pw = $pw . $_e[$key];
    }
    print "$pw\n";
}

brute2.pl

#!/usr/bin/env perl
#
@_e = split //,"abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";

$seed = 0;
sub ms_rand
{
    $seed = ( $seed * 214013 + 2531011 ) & (0x7FFF_FFFF);
    return ( ( $seed >> 16 ) & 0x7fff );
}

for ($seed=0;$seed<4294967296;++$seed)
{
    # $i=3326487116;
    srand($seed);
    $pw="";
    for($i=0;$i<12;++$i)
    {
            $key = (ms_rand() / 32767.0) * 54;
            $pw = $pw . $_e[$key];
    }
    print "$pw\n";
}

prng.c

#include <stdint.h>
#include <math.h>

// new openbsd drand48 prng
#define FREEBSD_DRAND48_SEED_0   (0x330e)
#define FREEBSD_DRAND48_SEED_1   (0xabcd)
#define FREEBSD_DRAND48_SEED_2   (0x1234)
#define FREEBSD_DRAND48_MULT_0   (0xe66d)
#define FREEBSD_DRAND48_MULT_1   (0xdeec)
#define FREEBSD_DRAND48_MULT_2   (0x0005)
#define FREEBSD_DRAND48_ADD      (0x000b)

const unsigned short _rand48_mult[3] = {
                FREEBSD_DRAND48_MULT_0,
                FREEBSD_DRAND48_MULT_1,
                FREEBSD_DRAND48_MULT_2
};

const unsigned short _rand48_add = FREEBSD_DRAND48_ADD;

#define U16 uint16_t
#define U32 uint32_t
typedef struct {
    U16 seed[3];
} perl_drand48_t;

void Perl_drand48_init_r(perl_drand48_t *random_state, U32 seed)
{
    random_state->seed[0] = FREEBSD_DRAND48_SEED_0;
    random_state->seed[1] = (U16) seed;
    random_state->seed[2] = (U16) (seed >> 16);
}


double Perl_drand48_r(perl_drand48_t *random_state)
{
    U32 accu;
    U16 temp[2];

    accu = (U32) _rand48_mult[0] * (U32) random_state->seed[0]
         + (U32) _rand48_add;
    temp[0] = (U16) accu;        /* lower 16 bits */
    accu >>= sizeof(U16) * 8;
    accu += (U32) _rand48_mult[0] * (U32) random_state->seed[1]
          + (U32) _rand48_mult[1] * (U32) random_state->seed[0];
    temp[1] = (U16) accu;        /* middle 16 bits */
    accu >>= sizeof(U16) * 8;
    accu += _rand48_mult[0] * random_state->seed[2]
          + _rand48_mult[1] * random_state->seed[1]
          + _rand48_mult[2] * random_state->seed[0];
    random_state->seed[0] = temp[0];
    random_state->seed[1] = temp[1];
    random_state->seed[2] = (U16) accu;

    return ldexp((double) random_state->seed[0], -48) +
           ldexp((double) random_state->seed[1], -32) +
           ldexp((double) random_state->seed[2], -16);
}

// old microsoft libc prng
typedef uint32_t msvc_rand_state_t;

void msvc_libc_srand(msvc_rand_state_t* random_state, uint32_t seed)
{
    *random_state = seed;
}

double msvc_libc_rand(msvc_rand_state_t *random_state)
{
    // msvc
    *random_state = (*random_state * 214013 + 2531011) & 0x7FFFFFFF;
    return ((*random_state >> 16) & 0x7fff) / 32768.0;

    // RtlUniform
    // *random_state = (*random_state * 0x7fffffed + 0x7fffffc3) % 0x7FFFFFFF;
    // return (*random_state & 0x7fff) / 32768.0;

    // glibc
    // *random_state = (*random_state * 1103515245 + 12345) & 0x7FFFFFFF;
    // return (*random_state & 0x7fff) / 32768.0;

    // ansi C
    // *random_state = (*random_state * 1103515245 + 12345) & 0x7FFFFFFF;
    // return ((*random_state >> 16) & 0x7fff) / 32768.0;
}

#if 0
#include <stdio.h>
int main()
{
    char* charset = "abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";
    perl_rand_state rand_state;
    char pw[13];
    pw[12] = '\0';
    uint32_t seed = 0x3AC5C29B;
    do
    {
        perl_srand(&rand_state, seed);
        for (int i = 0; i < 12; i++)
        {
            int key = (int)(perl_rand(&rand_state) * 54.0);
            pw[i] = charset[key];
        }
        puts(pw);
    } while(++seed);
}

// test vectors
// "password";     // IDA ver // gen // seed[, seed]
// "qY2jts9hEJGy"; // IDA 7.0 // Old // 3AC5C29B, BAC5C29B
// "ZFdLqEM2QMVe"; // IDA 6.8 // Old // 2FF0126C, AFF0126C
// "PDxD5J82DsFy"; // IDA 6.8 // New // 842411E7
// "FgVQyXZY2XFk"; // IDA 6.7 // New // C6462A4C
// "itJpyHidszaR"; // IDA 6.6 // Old // 25681E67, A5681E67
// "7ChFzSbF4aik"; // IDA 6.5 // Old // 626D5BFE, E26D5BFE
// "6VYGSyLguBfi"; // IDA 6.3 // Old // 73171059, F3171059
// "TuLWLErJwMHx"; // IDA 6.2 // New // CFD6740C
// "6A8RYbHhHrH";  // IDA 5.2 // Old // 1ADD7BD6, 9ADD7BD6
// "eyKiZ5dXXzd";  // Hex 1.1 // Old // 6253A857, E253A857
#endif

prng.h

#pragma once

#include <stdint.h>

#ifdef gen_bsd_drand48
typedef struct {
    uint16_t seed[3];
} perl_drand48_t;

void Perl_drand48_init_r(perl_drand48_t *random_state, uint32_t seed);

double Perl_drand48_r(perl_drand48_t *random_state);

#define perl_rand_state perl_drand48_t
#define perl_srand Perl_drand48_init_r
#define perl_rand Perl_drand48_r

#elif defined(gen_msvc_rand)
typedef struct {
    uint32_t seed;
} msvc_rand_state_t;

void msvc_libc_srand(msvc_rand_state_t* random_state, uint32_t seed);

double msvc_libc_rand(msvc_rand_state_t *random_state);

#define perl_rand_state msvc_rand_state_t
#define perl_srand msvc_libc_srand
#define perl_rand msvc_libc_rand

#else
#error must define one of gen_bsd_drand48 or gen_msvc_rand
#endif

sha.c

// clang -Wall -O3 -mssse3 -msha sha.c -o sha

#include <stdint.h>
#include <immintrin.h>
#include <memory.h>

#define MBYTES 64

typedef struct {
    unsigned char msgbuf[MBYTES];
    size_t msgbuf_count;
    uint64_t total_count;
 
    // Intermediate hash
    __m128i h0123;  // h0 : h1 : h2 : h3
    __m128i h4;     // h4 : 0 : 0 : 0
} sha1_ctx;


#define H0 0x67452301
#define H1 0xefcdab89
#define H2 0x98badcfe
#define H3 0x10325476
#define H4 0xc3d2e1f0

void SHA1Init(sha1_ctx* ctx)
{
    ctx->h0123 = _mm_set_epi32(H0, H1, H2, H3);
    ctx->h4    = _mm_set_epi32(H4, 0, 0, 0);
    ctx->msgbuf_count = 0;
    ctx->total_count = 0;
}

void SHA1ProcessMsgBlock(sha1_ctx* ctx, const unsigned char* msg)
{
    // Cyclic W array
    // We keep the W array content cyclically in 4 variables
    // Initially:
    // cw0 = w0 : w1 : w2 : w3
    // cw1 = w4 : w5 : w6 : w7
    // cw2 = w8 : w9 : w10 : w11
    // cw3 = w12 : w13 : w14 : w15
    const __m128i byteswapindex = _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
    const __m128i* msgx = (const __m128i*)msg;
    __m128i cw0 = _mm_shuffle_epi8(_mm_loadu_si128(msgx), byteswapindex);
    __m128i cw1 = _mm_shuffle_epi8(_mm_loadu_si128(msgx + 1), byteswapindex);
    __m128i cw2 = _mm_shuffle_epi8(_mm_loadu_si128(msgx + 2), byteswapindex);
    __m128i cw3 = _mm_shuffle_epi8(_mm_loadu_si128(msgx + 3), byteswapindex);

// Advance W array cycle
// Inputs: 
//  CW0 = w[t-16] : w[t-15] : w[t-14] : w[t-13]
//  CW1 = w[t-12] : w[t-11] : w[t-10] : w[t-9]
//  CW2 = w[t-8] : w[t-7] : w[t-6] : w[t-5]
//  CW3 = w[t-4] : w[t-3] : w[t-2] : w[t-1]
// Outputs: 
//  CW1 = w[t-12] : w[t-11] : w[t-10] : w[t-9]
//  CW2 = w[t-8] : w[t-7] : w[t-6] : w[t-5]
//  CW3 = w[t-4] : w[t-3] : w[t-2] : w[t-1]
//  CW0 = w[t] : w[t+1] : w[t+2] : w[t+3]
#define CYCLE_W(CW0, CW1, CW2, CW3)         \
    CW0 = _mm_sha1msg1_epu32(CW0, CW1);     \
    CW0 = _mm_xor_si128(CW0, CW2);          \
    CW0 = _mm_sha1msg2_epu32(CW0, CW3); 

    __m128i state1 = ctx->h0123;                     // state1 = a : b : c : d
    __m128i w_next = _mm_add_epi32(cw0, ctx->h4);    // w_next = w0+e : w1 : w2 : w3
    __m128i state2;

    // w0 - w3
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 0);// state2 = a' : b' : c' : d'
    w_next = _mm_sha1nexte_epu32(state1, cw1);  // w_next = w4+e' : w5 : w6 : w7
    // w4 - w7
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 0);
    w_next = _mm_sha1nexte_epu32(state2, cw2);
    // w8 - w11
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 0);
    w_next = _mm_sha1nexte_epu32(state1, cw3);
    // w12 - w15
    CYCLE_W(cw0, cw1, cw2, cw3);    // cw0 = w16 : w17 : w18 : w19
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 0);
    w_next = _mm_sha1nexte_epu32(state2, cw0);
    // w16 - w19
    CYCLE_W(cw1, cw2, cw3, cw0);    // cw1 = w20 : w21 : w22 : w23
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 0);
    w_next = _mm_sha1nexte_epu32(state1, cw1);
    // w20 - w23
    CYCLE_W(cw2, cw3, cw0, cw1);    // cw2 = w24 : w25 : w26 : w27
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 1);
    w_next = _mm_sha1nexte_epu32(state2, cw2);
    // w24 - w27
    CYCLE_W(cw3, cw0, cw1, cw2);    // cw3 = w28 : w29 : w30 : w31
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 1);
    w_next = _mm_sha1nexte_epu32(state1, cw3);
    // w28 - w31
    CYCLE_W(cw0, cw1, cw2, cw3);    // cw0 = w32 : w33 : w34 : w35
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 1);
    w_next = _mm_sha1nexte_epu32(state2, cw0);
    // w32 - w35
    CYCLE_W(cw1, cw2, cw3, cw0);    // cw1 = w36 : w37 : w38 : w39
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 1);
    w_next = _mm_sha1nexte_epu32(state1, cw1);
    // w36 - w39
    CYCLE_W(cw2, cw3, cw0, cw1);    // cw2 = w40 : w41 : w42 : w43
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 1);
    w_next = _mm_sha1nexte_epu32(state2, cw2);
    // w40 - w43
    CYCLE_W(cw3, cw0, cw1, cw2);    // cw3 = w44 : w45 : w46 : w47
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 2);
    w_next = _mm_sha1nexte_epu32(state1, cw3);
    // w44 - w47
    CYCLE_W(cw0, cw1, cw2, cw3);    // cw0 = w48 : w49 : w50 : w51
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 2);
    w_next = _mm_sha1nexte_epu32(state2, cw0);
    // w48 - w51
    CYCLE_W(cw1, cw2, cw3, cw0);    // cw1 = w52 : w53 : w54 : w55
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 2);
    w_next = _mm_sha1nexte_epu32(state1, cw1);
    // w52 - w55
    CYCLE_W(cw2, cw3, cw0, cw1);    // cw2 = w56 : w57 : w58 : w59
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 2);
    w_next = _mm_sha1nexte_epu32(state2, cw2);
    // w56 - w59
    CYCLE_W(cw3, cw0, cw1, cw2);    // cw3 = w60 : w61 : w62 : w63
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 2);
    w_next = _mm_sha1nexte_epu32(state1, cw3);
    // w60 - w63
    CYCLE_W(cw0, cw1, cw2, cw3);    // cw0 = w64 : w65 : w66 : w67
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 3);
    w_next = _mm_sha1nexte_epu32(state2, cw0);
    // w64 - w67
    CYCLE_W(cw1, cw2, cw3, cw0);    // cw1 = w68 : w69 : w70 : w71
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 3);
    w_next = _mm_sha1nexte_epu32(state1, cw1);
    // w68 - w71
    CYCLE_W(cw2, cw3, cw0, cw1);    // cw2 = w72 : w73 : w74 : w75
    state1 = _mm_sha1rnds4_epu32(state2, w_next, 3);
    w_next = _mm_sha1nexte_epu32(state2, cw2);
    // w72 - w75
    CYCLE_W(cw3, cw0, cw1, cw2);    // cw3 = w76 : w77 : w78 : w79
    state2 = _mm_sha1rnds4_epu32(state1, w_next, 3);
    w_next = _mm_sha1nexte_epu32(state1, cw3);

    // w76 - w79
    state1     = _mm_sha1rnds4_epu32(state2, w_next, 3);    // state1 = final a : b : c : d
    ctx->h4    = _mm_sha1nexte_epu32(state2, ctx->h4);      // Add final e to h4
    ctx->h0123 = _mm_add_epi32(state1, ctx->h0123);         // Add final a:b:c:d to h0:h1:h2:h3
}

void SHA1Update(sha1_ctx* ctx, const void* buf, size_t length)
{
    const unsigned char* p = (const unsigned char*)buf;
    ctx->total_count += length;

    // If any bytes are left in the message buffer, 
    // fullfill the block first
    if (ctx->msgbuf_count) {
        size_t c = MBYTES - ctx->msgbuf_count;
        if (length < c) {
            memcpy(ctx->msgbuf + ctx->msgbuf_count, p, length);
            ctx->msgbuf_count += length;
            return;
        }
        else {
            memcpy(ctx->msgbuf + ctx->msgbuf_count, p, c);
            p += c;
            length -= c;
            SHA1ProcessMsgBlock(ctx, ctx->msgbuf);
            ctx->msgbuf_count = 0;
        }
    }

    // When we reach here, we have no data left in the message buffer
    while (length >= MBYTES) {
        // No need to copy into the internal message block
        SHA1ProcessMsgBlock(ctx, p);
        p += MBYTES;
        length -= MBYTES;
    }

    // Leave the remaining bytes in the message buffer
    if (length) {
        memcpy(ctx->msgbuf, p, length);
        ctx->msgbuf_count = length;
    }
}

void SHA1Final(sha1_ctx* ctx, void* digest)
{
    // When we reach here, the block is supposed to be unfullfilled.
    // Add the terminating bit
    ctx->msgbuf[ctx->msgbuf_count++] = 0x80;

    // Need to set total length in the last 8-byte of the block.
    // If there is no room for the length, process this block first
    if (ctx->msgbuf_count + 8 > MBYTES) {
        // Fill zeros and process
        memset(ctx->msgbuf + ctx->msgbuf_count, 0, MBYTES - ctx->msgbuf_count);
        SHA1ProcessMsgBlock(ctx, ctx->msgbuf);
        ctx->msgbuf_count = 0;
    }

    // Fill zeros before the last 8-byte of the block
    memset(ctx->msgbuf + ctx->msgbuf_count, 0, MBYTES - 8 - ctx->msgbuf_count);

    // Set the length of the message in big-endian
    __m128i tmp = _mm_loadl_epi64((__m128i*)&ctx->total_count);
    tmp = _mm_slli_epi64(tmp, 3);   // convert # of bytes to # of bits
    const __m128i total_count_byteswapindex = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 2, 3, 4, 5, 6, 7);
    tmp = _mm_shuffle_epi8(tmp, total_count_byteswapindex); // convert to big endian
    _mm_storel_epi64((__m128i*)(ctx->msgbuf + MBYTES - 8), tmp);

    // Process the last block
    SHA1ProcessMsgBlock(ctx, ctx->msgbuf);

    // Set the resulting hash value, upside down
    const __m128i byteswapindex = _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
    __m128i r0123 = _mm_shuffle_epi8(ctx->h0123, byteswapindex);
    __m128i r4    = _mm_shuffle_epi8(ctx->h4, byteswapindex);

    uint32_t* digestdw = (uint32_t*)digest;
    _mm_storeu_si128((__m128i*)digestdw, r0123);
    digestdw[4] = _mm_cvtsi128_si32(r4);
}

#if 0
#include <stdio.h>
int main()
{
    sha1_ctx ctx;
    SHA1Init(&ctx);
    SHA1Update(&ctx, "a", 1);
    uint8_t digest[20];
    SHA1Final(&ctx, digest);
    for (int i = 0; i < 20; i++)
    {
        printf("%02x", digest[i]);
    }
    printf("\n");
}
#endif

sha1.h

#pragma once

#include <stdint.h>
#include <immintrin.h>
typedef struct {
#define MBYTES 64
    unsigned char msgbuf[MBYTES];
    size_t msgbuf_count;
    uint64_t total_count;
    __m128i h0123;
    __m128i h4;
} sha1_ctx;

void SHA1Init(sha1_ctx* ctx);
void SHA1Update(sha1_ctx* ctx, const void* buf, size_t length);
void SHA1Final(sha1_ctx* ctx, void* digest);