Memory-hard password-based key derivation functions?

Question

How are memory hard functions designed for the purpose of password based key derivation? To protect against a brute force attack from a parallel machine.

What design could work well with Skein? The Skein paper (pdf) has a time hard PBKDF (basically hashing the password repeat very many times) but not a memory hard one.

Answer 1

Memory hard functions are designed so that the internal calculations rely on a relatively large state. The functions should not have shortcuts that allow an adversary to calculate the result without using of the state at once (at least not without incurring a very high overhead). That way it is impossible for fast hardware to be developed that does not require large amounts of memory.

There isn't one specific design for memory hard functions within PBKDF's. You can have a look at various existing designs (scrypt, Argon2) of memory hard PBKDF's for examples of memory hard functions.

---

Lets define 3 different methods, going from low level to high level:

1. Catena was mentioned specifically in the comments as it simply requires a generic hash method to function. If any secure hash function can be used then Skein should be a secure option.

2. KMAC by now has been defined as a secure HMAC replacement by NIST. So you could use scrypt with PBKDF2 where the HMAC is replaced by KMAC.

3. scrypt uses PBKDF2 as underlying CPU hard function. Simply replace the PBKDF2 function within scrypt with another CPU hard function such as Skein's PBKDF.

These are hints, providing the security proof is left to the reader.

Answer 2

Currently, a single GPU cluster can break almost 1000 billions ($10^{10}$) passwords/hashes per seconds, imagine what a state attacker or hackers team can do with hardware ASICs, supercomputers or botnets networks. Basically, a password of 16-17 characters ($2^{80}$ entropy) can be broken within hours or days with brute force, and we are not even in quantum age yet.

Things are going worse because hashes are usually generated on a single CPU, while the world CPUs number is increasing, so the availability for attackers.

There are two explanations for this:

1. Developers generate passwords hash too fast and without salt, so when the hackers recover the hash databases they can recover passwords by brute force. Or they try to generate hash with low entropy input.
2. GPUs use a lot of small cores to perform this task, if each core would use a lot of memory for the algorithm they will run out of memory soon.

The weak point in local encryption process is not the algorithm usually, but the hash key generated from password, if a person can remember 15 characters, then the attacker rather tries all variants of this low entropy input instead of breaking the 256bits random key that encrypts data. So if the encryption key is generated slow, there are less chances of a brute force attack of the system.

There are several known such stretching functions, like scrypt, bellow you can find a simple sample of how such a function can be made to avoid massive parallel computing attacks.

via: gist.github.com/anonymous/c0edbaf71e0be3d07db3 (Created Oct 22, 2015)

// HKF - Memory Hard Key Derivation Function v 1.4
// Adrian Pirvu - October 14, 2015
//
// A memory hard key derivation function without useless overhead
// 3.4s with 1G memory and 1 million rounds on first generation i7 CPU
// INPUT: password - up to 256 bytes; salt - no limitation;  megabytes: memory you intend to use; rounds: memory pickup rounds;
// OUTPUT: stretched key hash (current 256 bytes) - you can either simple hash to less this value or use part of it.
// Arc4 used as a one way random generator, but any stream cipher can be used
// No need to generate memory diffusion like others functions, I only make sure that the final hash that I get is irreversible and not biased
// No side attacks considered, if the attacker has access to your RAM then an activity tracking RAT already took your password or screenshots of your mouse clicks
// Tags: fast memory hard function, password hashing, memory hard key stretching, memory hard key strengthening, scrypt, bcrypt, sequential memory hard function
// Looking for feedback and some possible GPUs cluster tests. If anyone is interested in further development or a possible public project, please let me know.



#include "stdafx.h"
//#include <string.h>
//#include <time.h>
//#include <windows.h>


extern "C"
{

    unsigned int i = 0, j = 0, m = 0, z = 0;
    unsigned char s[256], k[256];

    void RngInit(unsigned char* key, int keyLength, unsigned char* salt, int saltLength);
    unsigned char RngNextByte();
    unsigned int RngNextInt();


    //unsigned int TEST_MEGABYTES = 1024;
    //unsigned int TEST_ROUNDS = 1000000;


    // return a hashable strengthen key of desired length from password and salt
    __declspec(dllexport) void GetHashKey(unsigned char* password, int passwordLength, unsigned char* salt, int saltLength, int megabytes, int rounds, unsigned char* output)
    {
        // dinamically allocates memory 4 * 1024 * megabytes
        int ROWS = 4 * 1024 * megabytes; // each row is 256 bytes (256 * 4 * 1024 = 1k * 1024 = 1M)
        int COLUMNS = 64; // * 4 bytes per int = 256 bytes
        unsigned int* box = new unsigned int[ROWS * COLUMNS];
        unsigned int tmp = 0;

        // init the random engine and get a temporary key
        RngInit(password, passwordLength, salt, saltLength);
        unsigned int key[64];
        for (int col = 0; col < 64; col++)
            key[col] = RngNextInt();

        // reinit the engine for safety and get a start key and the session salt
        RngInit((unsigned char*) key, 256, salt, saltLength);
        unsigned int pepper[64];
        for (int col = 0; col < 64; col++)
        {
            key[col] = RngNextInt();
            pepper[col] = RngNextInt();
            box[col] = key[col]; // first row is the start key
        }

        // fills the memory fast, with a bit of diffusion (we really don't need much)
        unsigned int random = key[34] * key[56] + key[62];
        for (int row = 1; row < ROWS; row++)
        {
            // breaks the row random and switch parts
            int index = box[(row - 1) * COLUMNS + 56] & 0x000000FF;
            memcpy((unsigned char*) &box[row * COLUMNS] + index, (unsigned char*) &box [(row - 1) * COLUMNS], 256 - index);
            memcpy((unsigned char*) &box[row * COLUMNS], (unsigned char*) &box [(row - 1) * COLUMNS] + 256 - index, index);

            // xor each number with the session salt and pseudorandom number
            for (int col = 0; col < 64; col++)
            {
                random = (2147483629 * random + 2147483587); // maybe something with longer period?
                box[row * COLUMNS + col] = (box[row * COLUMNS + col] + pepper[col]) ^ random;
            }
        }

        // start with the last row to avoid precalculations and algo redesign
        for (int col = 0; col < 64; col++)
            key[col] = box[(ROWS - 1) * COLUMNS + col];


        //clock_t start = clock();

        // intensively get random integers from memory and mix them into the pseudorandom key
        for (int rnd = 0; rnd < rounds; rnd++)
            for (int col = 0; col < 64; col++)
            {
                i = (i + 1) % 256;
                j = (j + s[i]) % 256;
                tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                unsigned int sum1 = (s[i] + s[j]);
                unsigned int column = sum1 % 64;
                unsigned int row = (key[col] + sum1 + i + j) % ROWS;
                sum1 = sum1 % 256;

                i = (i + 1) % 256;
                j = (j + s[i]) % 256;
                tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                unsigned int sum2 = (s[i] + s[j]) % 256;

                unsigned int total = (sum1 << (16 + (sum2 % 8))) + (sum2 << (sum1 % 8));
                key[col] = (key[col] + total) ^ (box [row * COLUMNS + column] + pepper[col]);
                //key[col] += RngNextInt() ^ (box [row * COLUMNS + column] + key[col]);
            }

        //clock_t diff = clock() - start;
        //char message[1000];
        //float seconds = ((float) diff) / CLOCKS_PER_SEC;
        //sprintf(message, "Seconds: %0.3f\r\n\0", seconds);
        //OutputDebugStringA(message);


        // build output
        for (int col = 0; col < 256; col++)
            output[col] = RngNextByte() ^ ((unsigned char*) key)[col];

        // cleanup
        for (int col = 0; col < COLUMNS; col++)
        {
            box[(ROWS - 1) * COLUMNS + col] ^= box[(ROWS - 1)* COLUMNS + col];
            key[col] ^= key[col];
            pepper[col] ^= pepper[col];
        }
        ROWS = 0;
        COLUMNS = 0;

        // should overwrite memory
        delete[] box;
    }



    // init RNG engine 
    void RngInit(unsigned char* key, int keyLength, unsigned char* salt, int saltLength)
    {
        unsigned char tmp = 0;

        i = j = 0;
        for (i = 0; i < 256; i++)
        {
            s[i] = i;
            k[i] = key[i % keyLength];
        }

        j = 0;
        for (i = 0; i < 256; i++)
        {
            j = (j + s[i] + k[i]) % 256;
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp ;
        }

        // discard start to bypass key scheduler flaws, also mix the salt
        i = j = m = z = 0;
        for (int idx = 0; idx < 3000 + k[251] + saltLength; idx++)
        {
            i = (i + 1) % 256;
            if (saltLength > 0)
                j = (m + s[(j + s[i]) % 256] + salt[idx % saltLength]) % 256;
            else
                j = (m + s[(j + s[i]) % 256]) % 256;
            m = (m + i + s[j]) % 256;
            tmp = s[i];
            s[i] = s[j];
            s[j] = tmp;
            z = s[(j + s[(i + s[(z + m) % 256]) % 256]) % 256];
        }
    }



    // obtain a random byte from Rng engine
    unsigned char RngNextByte()
    {
        unsigned char tmp = 0;

        // use RC4, is faster
        i = (i + 1) % 256;
        j = (j + s[i]) % 256;
        tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
        return (s[i] + s[j]) % 256;

        //i = (i + 1) % 256;
        //j = (m + s[(j + s[i]) % 256]) % 256;
        //m = (m + i + s[j]) % 256;
        //tmp = s[i];
        //s[i] = s[j];
        //s[j] = tmp;
        //z = s[(j + s[(i + s[(z + m) % 256]) % 256]) % 256];
        //return z;
    }



    // obtain a random int from Rng engine
    unsigned int RngNextInt()
    {
        unsigned char tmp = 0;
        unsigned char output[4];
        for (int idx = 0; idx < sizeof(int); idx++)
            output[idx] = RngNextByte();

        return *((unsigned int*) output);
    }



    //// main function, for test purposes
    //int main(int argc, char * argv[])
    //{
    //  const char* password = "monkey";
    //  const char* salt = "superman";
    //  
    //  unsigned char output[256];
    //  GetHashKey((unsigned char*) password, strlen(password), (unsigned char*) salt, strlen(salt), TEST_MEGABYTES, TEST_ROUNDS, output);

    //  //FILE* file = fopen("d:\\key.dat", "wb");
    //  //fwrite((void*) key, 1, 100000000, file);
    //  //fflush(file);
    //  //fclose(file);
    //}

}