# Memory hard password based key derivation functions?

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.

• the scheme mentioned there is basically PBKDF2. If you want to use Skein for secure password hashing take a look at Catena. – SEJPM Aug 6 '15 at 17:11
• Catena seems a particularly good fit as it describes a framework that relies on a hash function. Other schemes often rely on a specific PRF. – Maarten Bodewes Oct 22 '15 at 14:39

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.

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

}

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Dec 17 '17 at 13:28