3
$\begingroup$

Background:

Hello, I'm working on a hobby project in which I might want to implement a key derivation function within a somewhat resource limited embedded system. For standard crypto functions, I only have access to SHA and AES (no KDFs). So, I was thinking of rewriting one of the standard ones (like bcrypt or scrypt) but frankly, it doesn't seem like it should be that difficult. I threw together a proof-of-concept SHA-256 based KDF with seems to me both memory "hard" and processing "hard". As written now, it first performs 1000 rounds of SHA-256, storing each successive result in memory. Then it performs a chain of arithmetic that creates data dependencies throughout all those values in memory. The final result is a 32 bit key.

Question:

I'm posting the code that I wrote (it's structured merely as a proof of concept at this point) and I was wondering if anyone could look it over and tell me if they see any glaring insecurities in my logic? I realize that some parallelization is still possible, but I think the data dependencies should still prevent full parallelization.

C++ code:

#include <iostream>
#include "sha256.h"
#include <string.h>

using namespace std;

const int MEMSIZE = 32000; // adjustable memory size parameter

int main()
{
    // input strings (would come from user in a production implementation)
    string password = "pwCharsNormallyRandm";
    string salt = "saltNormRand";

    // SHA setup stuff
    string input = password + salt;
    unsigned char digest[SHA256::DIGEST_SIZE];
    memset(digest,0,SHA256::DIGEST_SIZE);
    SHA256 ctx = SHA256();
    ctx.init();

    // perform the first hash (gets stored in digest)
    ctx.update( (unsigned char*)input.c_str(), input.length());
    ctx.final(digest);

    // mem is a "large" block of memory that's used to make KDF "memory hard"
    uint8_t mem[MEMSIZE];
    // some iterator variables
    int mI, dI;
    int mIUB = 0;

    cout << "First digest from password+salt:" << endl;
    for (dI = 0; dI < 32; ++dI)
        cout << (int)digest[dI] << ",";
    cout << endl;

    // store digest in mem
    mIUB = mIUB + 32;
    dI = 0;
    for (mI = 0; mI < mIUB; ++mI) {
        mem[mI]=digest[dI];
        ++dI;
    }

    /* This loop performs many rounds of SHA on the digest, storing each
       iteration of the digest in successive sections of mem for later use. */
    int SHARound;
    for(SHARound = 2; SHARound <= MEMSIZE/32; ++SHARound){

        // digest = SHA of digest
        ctx.update(digest, 32);
        ctx.final(digest);

        // store digest in mem
        mIUB = mIUB + 32;
        dI = 0;
        for (mI; mI < mIUB; ++mI) {
            mem[mI]=digest[dI];
            ++dI;
        }
    }

    /*////////////////////////////////////////////////////////////////////////
    The next part of the KDF is to perform many steps of arithmetic between
    bytes in mem so that there is a chain of data dependence throughout the
    entire array. */

    uint8_t result[32]; // an array to hold arithmetic results
    mIUB = 32;

    // initialize result with the contents at the end of the mem array
    int rI;
    mI = MEMSIZE - 32;
    for (rI = 0; rI < 32; ++rI){
        result[rI] = mem[mI];
        ++mI;
    }

    /* perform some arithmetic on result which depends on values at the
       beginning of mem */
    rI = 0;
    for(mI = 0; mI < mIUB; ++mI) {
        if(result[rI]%2 == 0)
            result[rI] = result[rI] + mem[mI];
        else
            result[rI] = result[rI] - mem[mI];
        ++rI;
    }

    /* Loop through the rest of mem to complete the chain of
       data dependent arithmetic (result depends on the previous result and
       the values in the next section of mem). */
    int arithRound;
    for(arithRound = 2; arithRound <= MEMSIZE/32; ++arithRound){
        mIUB = mIUB + 32;
        rI = 0;
        for(mI; mI < mIUB; ++mI) {
            if(result[rI]%2 == 0)
                result[rI] = result[rI] + mem[mI];
            else
                result[rI] = result[rI] - mem[mI];
            ++rI;
        }
    }

    cout << "Final result (key):" << endl;
    for (dI = 0; dI < 32; ++dI)
        cout << (int)result[dI] << ",";
    cout << endl;

    return 0;
}
$\endgroup$
  • 5
    $\begingroup$ Please include a compact description using mathematical notation or pseudo code instead of long c code full of unnecessary details. $\endgroup$ – CodesInChaos Aug 21 '14 at 9:42
  • 1
    $\begingroup$ @esushi? Why KBKDF? This is clearly password based, not key based. $\endgroup$ – CodesInChaos Aug 21 '14 at 19:25
  • $\begingroup$ I'm not encouraging you to use unproven schemes, but if you're interested in learning, you might like to follow the Password Hashing Competition. You might find the submissions interesting, and a couple years from now there should be some nice new password hashing algorithms available. For now, use PBKDF2, bcrypt or scrypt, of course. $\endgroup$ – Matt Nordhoff Aug 22 '14 at 4:25
3
$\begingroup$

If I got the code correctly, it works in the following way:

  1. Computes digest $D = SHA256(password + salt)$
  2. Computes table T with $N=MEMSIZE /32$ elements: $T_{0}=D, T_{i}=SHA256(T_{i-1})$
  3. Set $R=T_{N-1}$
  4. Update $R$ by mixing it with $T_{0}$, $T_{1}$, ..., $T_{N-1}$, where "mixing" is a byte addition or subtraction depending on value of the byte
  5. After mixing with the last element of T, output $R$ as a key.

First, I believe this algorithm is not "memory hard". Attacker with a memory-constrained devices (GPU/ASIC) can still compute the key with negligible memory and at twice the computational complexity of the original algorithm. Attacker would first compute the last element of the table $T$, thus obtaining initial value of $R$. He or she will then make a second computational pass and will update $R$ along with (re-)computing elements of the table $T$.

Second, if the resulting key is stored (e.g. as a password hash) then attacker might be able to run guessing attacks with negligible memory and at original complexity. Here's how:

  • First, attacker guesses parity of the bytes in $R$ (e.g. assumes parity for all bytes is zero). On average, parity of 16 bytes will be guessed correctly.
  • Next, he computes $T_{i}$ and updates $R$ at the same time. He can do this because mixing only depends on parity.
  • Once $T_{N-1}$ is reached and attacker has the "real" $R$, he identifies byte positions with correct parity guesses and completes computation of $R$ by adding bytes in identified positions from $T_{N-1}$.
  • $R$ that attacker has obtained should match the "real" value of $R$ in positions where attacker's guess of parity was correct, i.e. on average that should give 16 byte positions to match, which is more than enough for password hash verification (chance of random password surviving this check is $2^{-8*M}$ ($M$ – number of bytes with correctly guessed parity).
  • If there's a match on previous step, attacker can confirm password by running "full" algorithm on a less constrained device.

(I'm not 100% sure the above attack would work, but it seems it should)

As a final note, it's almost never a good idea to invent your own algorithm. If you only have access to SHA-256 you can still implement PBKDF2-SHA256. It's not perfect, but at least it is studied and its shortcomings are well-understood.

$\endgroup$
  • $\begingroup$ Hi, thank you for your analysis! I see now the vulnerabilities in my algorithm. I had a hunch it was a more difficult problem than I was first thinking, but just couldn't see why. I'll take your advice and try to implement PBKDF2, I just wish it was more "memory hard". $\endgroup$ – katrik Aug 21 '14 at 21:38
1
$\begingroup$

I wouldn't recommend rolling your own KDF. PBKDF2 is easy to implement with access to SHA-256, and with a high enough iteration count will still slow down an attacker, even if not as much as scrypt.

From a quick look, it seems that you are walking the memory linearly both when generating the SHA output and when collecting the data output data through additions and subtractions. That means a more optimized implementation wouldn't need to store anything in memory at all.

If you wanted a memory hard algorithm, you'd have to do something like scrypt – use the data in an unpredictable order – or at least walk over it multiple times in a process that cannot be reordered.

$\endgroup$
  • $\begingroup$ Yes that's a good idea (walking over the array in an unpredictable order). I could probably dream up a modification to my process that would do that, but I'm definitely more reluctant now to keep trying to roll my own algorithm. Though I am sort of a "learn by doing" type... so who knows :p $\endgroup$ – katrik Aug 21 '14 at 21:58
  • $\begingroup$ @katrik, note data-dependent order may easily lead to cache timing attacks. $\endgroup$ – otus Aug 22 '14 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.