Skip to content

Instantly share code, notes, and snippets.

@xrmr

xrmr/brute.c

Created June 24, 2019 16:54
Show Gist options
  • Save xrmr/a36d7a10a89af460d29ac8ae9dc783ad to your computer and use it in GitHub Desktop.
Save xrmr/a36d7a10a89af460d29ac8ae9dc783ad to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @stong stong revised this gist Jun 23, 2019. 1 changed file with 36 additions and 16 deletions.
    52 changes: 36 additions & 16 deletions brute.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,9 +1,9 @@
    // clang -Werror -Wall -O3 -mssse3 -msha cpu-brute.c sha.c prng.c -o brute
    // 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
    #define gen_bsd_drand48 1
    // #define gen_msvc_rand 1
    #include "prng.h"

    #include <stdint.h>
    @@ -16,29 +16,29 @@
    #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.0
    // 0x7B, 0xA6, 0xF1, 0xDF, 0x9B, 0x88, 0xA2, 0x5C, 0x6C, 0x5D, 0xA5, 0x22,
    // 0xCC, 0xC3, 0x07, 0x24, 0x8A, 0xA0, 0xEC, 0x62
    // };
    { // 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
    // 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
    #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,
    @@ -47,6 +47,15 @@ int main()
    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;
    @@ -68,6 +77,11 @@ int main()
    {
    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);
    @@ -80,9 +94,15 @@ int main()

    if (!memcmp(digest, hash, 20))
    {
    printf("CRACKED!!!! %x %s\n", seed, &pw[SALT_LEN]);
    int fd = open("sice.txt", O_APPEND | O_RDWR | O_CREAT,0);
    dprintf(fd, "CRACKED!!!! %x %s\n", seed, &pw[SALT_LEN]);
    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;
  2. @stong stong revised this gist Jun 23, 2019. No changes.
  3. @stong stong revised this gist Jun 23, 2019. 6 changed files with 511 additions and 64 deletions.
    142 changes: 78 additions & 64 deletions brute.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,78 +1,92 @@
    #include <stdint.h>
    #include <math.h>
    #define FREEBSD_DRAND48_SEED_0 (0x330e)

    // clang -Werror -Wall -O3 -mssse3 -msha cpu-brute.c sha.c prng.c -o brute

    #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)
    #include "sha1.h"

    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);
    }
    // #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>

    double Perl_drand48_r(perl_drand48_t *random_state)
    #define PARALLEL 48
    int main()
    {
    U32 accu;
    U16 temp[2];
    char* charset = "abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";

    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;
    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
    // };
    { // ida 7.2
    0xF2, 0x9F, 0x55, 0xF0, 0x7C, 0x04, 0x3A, 0xD3, 0x4B, 0x3D, 0xE1, 0x50,
    0x50, 0x15, 0x35, 0xF4, 0x44, 0x24, 0xED, 0xAD
    };

    return ldexp((double) random_state->seed[0], -48) +
    ldexp((double) random_state->seed[1], -32) +
    ldexp((double) random_state->seed[2], -16);
    }
    #define SALT_LEN 25
    // 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
    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

    #include <stdio.h>
    int main()
    {
    char* charset = "abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";
    perl_drand48_t rand_state;
    char pw[13];
    pw[12] = '\0';
    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
    {
    Perl_drand48_init_r(&rand_state, seed);
    for (int i = 0; i < 12; i++)
    if (!(seed & 0xffffff)) printf("%x\n", seed);
    perl_srand(&rand_state, seed);
    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 key = (int)(Perl_drand48_r(&rand_state) * 54.0);
    pw[i] = charset[key];
    printf("CRACKED!!!! %x %s\n", seed, &pw[SALT_LEN]);
    int fd = open("sice.txt", O_APPEND | O_RDWR | O_CREAT,0);
    dprintf(fd, "CRACKED!!!! %x %s\n", seed, &pw[SALT_LEN]);
    close(fd);
    kill(0, SIGQUIT);
    break;
    }
    puts(pw);
    } while(++seed);
    } while(++seed != upto);
    printf("Worker %d done\n", worker);
    }
    23 changes: 23 additions & 0 deletions brute2.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,23 @@
    #!/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";
    }
    120 changes: 120 additions & 0 deletions prng.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,120 @@
    #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
    33 changes: 33 additions & 0 deletions prng.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,33 @@
    #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
    241 changes: 241 additions & 0 deletions sha.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,241 @@
    // 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
    16 changes: 16 additions & 0 deletions sha1.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,16 @@
    #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);
  4. @stong stong created this gist Jun 22, 2019.
    78 changes: 78 additions & 0 deletions brute.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,78 @@
    #include <stdint.h>
    #include <math.h>
    #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);
    }

    #include <stdio.h>
    int main()
    {
    char* charset = "abcdefghijkmpqrstuvwxyzABCDEFGHJKLMPQRSTUVWXYZ23456789";
    perl_drand48_t rand_state;
    char pw[13];
    pw[12] = '\0';
    uint32_t seed = 0;
    do
    {
    Perl_drand48_init_r(&rand_state, seed);
    for (int i = 0; i < 12; i++)
    {
    int key = (int)(Perl_drand48_r(&rand_state) * 54.0);
    pw[i] = charset[key];
    }
    puts(pw);
    } while(++seed);
    }
    16 changes: 16 additions & 0 deletions brute.pl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,16 @@
    #!/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";
    }