A memory-efficient SHA1 implementation

I'm working with a very restrictive embedded processor, which only has 128 bytes of ram. I'd like to implement SHA1 on it. RFC3174 describes, in 'method 2', a way of implementing SHA1 that doesn't require allocating an a开发者_JAVA百科rray of 80 32-bit words (which, at 320 bytes, is obviously not practical), and seems like it ought to be usable on my processor. I'm unable to find any implementations of 'method 2', though, and the sample code in the RFC only implements the default method.

Is anyone aware of a memory-efficient implementation of SHA1 in C or C++?

You should be able to quickly adapt the method 1 source to method 2. The function to change is Sha1ProcessMessageBlock() in method 1. Initialize w[0:15] from message, then do a loop of 0 to 79, where you only do w[] manipulation after iteration 16, and temp calculation depends on ts value (0-19 uses one, 20-39 uses another, etc). The important thing to remember is using index%16 or index & 0x0f whenever you are addressing the w[] array.

A quick modification would be something like this (double check all accesses to w to make sure I haven't missed the t & 0x0f):

void SHA1ProcessMessageBlock(SHA1Context *context)
{
    const uint32_t K[] =    {       /* Constants defined in SHA-1   */
                            0x5A827999,
                            0x6ED9EBA1,
                            0x8F1BBCDC,
                            0xCA62C1D6
                            };
    int           t;                 /* Loop counter                */
    uint32_t      temp;              /* Temporary word value        */
    uint32_t      W[16];             /* Word sequence               */
    uint32_t      A, B, C, D, E;     /* Word buffers                */

    /*
     *  Initialize the first 16 words in the array W. You can move this to your
     *  context.
     */
    for(t = 0; t < 16; t++)
    {
        W[t] = context->Message_Block[t * 4] << 24;
        W[t] |= context->Message_Block[t * 4 + 1] << 16;
        W[t] |= context->Message_Block[t * 4 + 2] << 8;
        W[t] |= context->Message_Block[t * 4 + 3];
    }


    A = context->Intermediate_Hash[0];
    B = context->Intermediate_Hash[1];
    C = context->Intermediate_Hash[2];
    D = context->Intermediate_Hash[3];
    E = context->Intermediate_Hash[4];

    for(t = 0; t < 80; t++) {
        if (t >= 16) {
            W[t&0xf] = SHA1CircularShift(1,W[(t-3)&0xf] ^ W[(t-8)&0xf] ^ W[(t-14)&0xf] ^ W[t&0xf]);

        }

        if (t<20) {
            temp =  SHA1CircularShift(5,A) +
                    ((B & C) | ((~B) & D)) + E + W[t&0xf] + K[0];
        }
        else if (t<40) {
            temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t&0xf] + K[1];
        }
        else if (t < 60) {
            temp = SHA1CircularShift(5,A) +
                   ((B & C) | (B & D) | (C & D)) + E + W[t&0xf] + K[2];
        }
        else {
            temp = SHA1CircularShift(5,A) + (B ^ C ^ D) + E + W[t&0xf] + K[3];
        }
        E = D;
        D = C;
        C = SHA1CircularShift(30,B);
        B = A;
        A = temp;
    }

    context->Intermediate_Hash[0] += A;
    context->Intermediate_Hash[1] += B;
    context->Intermediate_Hash[2] += C;
    context->Intermediate_Hash[3] += D;
    context->Intermediate_Hash[4] += E;

    context->Message_Block_Index = 0;
}

There are still savings to be made: get rid of W[] array on stack and put it in context pre-initialized with the data you get.

Also, you need a lot of pre-processing before calling this function. For example, if all your messages are less than 55 bytes, you can put it in W array, add padding, and process immediately. If not, you'll have to call process twice: first with your partially padded input, and again with the rest of the pad, etc. That sort of thing would be very application specific, and I doubt you'll be able to find the code to do it for you.

By the way, the code above is a straight adaptation from the type 1 source from your link. You can probably squeeze a bit more out of it if you try to optimize it further.

I couldn't think of a way to get any savings on the intermediate hash, so you will need a total of 108 bytes for this (109 if counter is also in RAM), and 24 of which is local to this function, and can be reused in other places - so long as they are also temporary. So it is very hard to do what you want to do.

EDIT: If all your messages are less than 55 bytes, you can save another 20 bytes in your context by getting rid of the intermediate_hash[] storage. Simply initialize A-E from the constants, and add the constants at the end. Finally, instead of storing them in a separate variable, overwrite your input when this function ends.

I have implemented SHA-1 for several memory-constrained environments. You can get by with

DWORD W[16] ;        // instead of H[80]
DWORD H[5] ;         // Intermediate hash value
DWORD BitCount[2] ;  // Probably a single DWORD is enough here

plus a few bytes of housekeeping. W is updated on the fly, as a circular buffer, instead of being generated at the start of each round.

working example:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>

using namespace std;

unsigned CircularShift(int bits, unsigned word)
{
    return ((word << bits) & 0xFFFFFFFF) | ((word & 0xFFFFFFFF) >> (32-bits));
}

int main(void)
{
    string mess;
    cin >> mess;
    unsigned int lm = mess.length();
    unsigned int lmb = lm*8;
    unsigned char *messc;
    messc=(unsigned char*)malloc((sizeof(unsigned char))*64);

    for (unsigned short int i =0;i<64;i++)
    {
        messc[i]=char(0x00);
    }
    for(int i=0;i<mess.length();i++)
    {
        messc[i]=mess[i];
    }
    messc[lm]=(unsigned char)128;
    messc[56] = (lmb >> 24) & 0xFF;
    messc[57] = (lmb >> 16) & 0xFF;
    messc[58] = (lmb >> 8) & 0xFF;
    // messc[59] = (lmb) & 0xFF;
    messc[60] = (lmb >> 24) & 0xFF;
    messc[61] = (lmb >> 16) & 0xFF;
    messc[62] = (lmb >> 8) & 0xFF;
    messc[63] = (lmb) & 0xFF;
    for(int i =0 ;i<64;i++)
    {
        cout<< hex << (int)messc[i] << " ";
    }
    unsigned *H;
    H=(unsigned*)malloc(5*sizeof(unsigned));
    H[0]        = 0x67452301;
    H[1]        = 0xEFCDAB89;
    H[2]        = 0x98BADCFE;
    H[3]        = 0x10325476;
    H[4]        = 0xC3D2E1F0;
    const unsigned K[]={0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6};
    int         t;
    unsigned    temp;
    unsigned    *W;
    unsigned    A, B, C, D, E;
    W=(unsigned*)malloc(80*sizeof(unsigned));
    unsigned char *messh;
    messh=(unsigned char*)malloc(64*sizeof(unsigned char));
    int k;
    for(t = 0; t < 16; t++)
    {
        W[t] = ((unsigned) messc[t * 4])<< 24; ;
        W[t] |= ((unsigned) messc[t * 4 + 1])<< 16;
        W[t] |= ((unsigned) messc[t * 4 + 2]) << 8;
        W[t] |= ((unsigned) messc[t * 4 + 3]);
    }
    for(t = 16; t < 80; t++)
    {
        W[t] = CircularShift(1,W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);
    }

    A = H[0];
    B = H[1];
    C = H[2];
    D = H[3];
    E = H[4];

    for(t = 0; t < 20; t++)
    {
        temp = CircularShift(5,A) + ((B & C) | ((~B) & D)) + E + W[t] + K[0];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 20; t < 40; t++)
    {
        temp = CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[1];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 40; t < 60; t++)
    {
        temp = CircularShift(5,A) +
                ((B & C) | (B & D) | (C & D)) + E + W[t] + K[2];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    for(t = 60; t < 80; t++)
    {
        temp = CircularShift(5,A) + (B ^ C ^ D) + E + W[t] + K[3];
        temp &= 0xFFFFFFFF;
        E = D;
        D = C;
        C = CircularShift(30,B);
        B = A;
        A = temp;
    }

    H[0] = (H[0] + A) & 0xFFFFFFFF;
    H[1] = (H[1] + B) & 0xFFFFFFFF;
    H[2] = (H[2] + C) & 0xFFFFFFFF;
    H[3] = (H[3] + D) & 0xFFFFFFFF;
    H[4] = (H[4] + E) & 0xFFFFFFFF;

    cout <<"\nTHIS IS SHHHHHAAAAAAAAAAA\n";
    for(int i=0;i<5;i++)
    {
        cout << hex << H[i] << " ";
    }

    //Message_Block_Index = 0;


}

All things considered, looking at your requirements, I think you are going to have to change your specs. Either a bigger chip, or a simpler algorithm. Even implementing SHA-1 (without HMAC) would be a challenge, but it should be doable.