SHA-1 algorithm help

[gulyan]

Hi, I'm trying to make the sha-1 algorithm based on the wikipedia pseudocode.
For the 'The quick brown fox jumps over the lazy dog" string I should get
2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12 but what I get is
1D8B8841 A544939A 98BB54FE 4C325476 C44AE1F0
(after I convert from dec to hex)
I have no idea what the problem is :(
Thx in advance

#define ROTL ( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

void SHA1(char *in, long nr, char *sha)
{
	long i, j, w[80];
	unsigned long h0 = 0x67452301;
	unsigned long h1 = 0xEFCDAB89;
	unsigned long h2 = 0x98BADCFE;
	unsigned long h3 = 0x10325476;
	unsigned long h4 = 0xC3D2E1F0;
	unsigned long a, b, c, d, e, f, k, temp;
	unsigned long length = nr*32;
	in[nr++] = (char)128;//1 7x0
	while(nr%64 != 60)in[nr++] = 0;//8x0
	*((long*)(in+nr)) = length;
	nr += 4;
	for(i=0;i<nr;i+=64)
	{
		for(j=i;j<i+64;j+=4)w[(i-j)/4] = *((long*)in+j);// break chunk into sixteen 32-bit big-endian words w[i], 0 <= i <= 15
		for(i=16;i<80;i++)w[i] = ROTL((w[i-3]^w[i-8]^w[i-14]^w[i-16]), 1);
		a = h0;
		b = h1;
		c = h2;
		d = h3;
		e = h4;
		for(i=0;i<80;i++)
		{
			if(0<=i&&i<20)
			{
				f = (b & c) | ((! b) & d);
				k = 0x5A827999;
			}
			else if(i>=20&&i<40)
			{
				f = b ^ c ^ d;
				k = 0x6ED9EBA1;
			}
			else if(i>=40&&i<60)
			{
				f = (b & c) | (b & d) | (c & d);
				k = 0x8F1BBCDC;
			}
			else if(i>=60&&i<80)
			{
				f = b ^ c ^ d;
				k = 0xCA62C1D6;
			}
			temp = ROTL(a, 5) + f + e + k + w[i];
			e = d;
			d = c;
			c = ROTL(b, 30);
			b = a;
			a = temp;
		}
		h0 = h0 + a;
		h1 = h1 + b;
		h2 = h2 + c;
		h3 = h3 + d;
		h4 = h4 + e;
	}
	sprintf_s(sha, 512, "%u %u %u %u %u", h0, h1, h2, h3, h4);
}

[gpraghuram]

I tired compiling this in Cygwin using gcc and i am getting the error for ROTL sayings its not a function...

Raghu

[gulyan]

thx for the reply

unsigned long ROTL(unsigned long a, unsigned long b)
{
	return (a<<b)|(a>>(32-b));
}

should do the same thing as

#define ROTL ( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

but my problems are not compiler errors :(
btw.. I'm using vc++

[gpraghuram]

Since the endianess is involved in this you will get a different answer in the Intel machine...
Do you know which compiler or processor the example has used for this?

raghu

[Banfa]

#define ROTL ( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

This syntax is not correct it should be

#define ROTL( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

Notice the lack of space following ROTL, other wise ROTL becomes a normal macro defined as

"( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) )"

not a function like macro taking 2 parameters.

[Banfa]

Hi, I'm trying to make the sha-1 algorithm based on the wikipedia pseudocode.

I Did this myself a couple of months ago and it works fine so there is no problem with the pseudo code you are using as a base.

Looking at you code the actual data manipulation in the loop looks fine, what concerns me is your buffer manipulation before the loop. In fact your inner most loop is almost exactly the same as mine (not withstanding variable name differences) but the buffer manipulation you do in 3 or four lines outside the loops and 2 lines inside the outer most loop is 30 lines of code in my version.

Of course it may well be able to do it in less lines of code, I was memory constrained because my version had to work on a low memory micro-controller target.

Anyway here are some specific issues

void SHA1(char *in, long nr, char *sha)
{
<snip>

// This is not the bit length of your data, you have passed a char * and 
// so nr is presumably the number of chars.  The bit length of your data 
// is then nr*8
	unsigned long length = nr*32;

// These next 2 lines are extremely dangerous, they assume that the caller 
// has called the function with a buffer that is long enough to extend the data 
// to the next multiple of 512 bites (or 64 bytes). in should have type const 
// char * and you should have your own work buffer to copy the data to.
	in[nr++] = (char)128;//1 7x0
	while(nr%64 != 60)in[nr++] = 0;//8x0

// Dangerous and will only work on a big endian platform, non portable code
	*((long*)(in+nr)) = length;

	nr += 4;
	for(i=0;i<nr;i+=64)
	{
// This is wrong and a major difference between you and my impementation, 
// you have converted each byte to a 32 bit word, I pack the bytes into the
// 32 bit words, where as your first word in the buffer has the value 
// 0x00000054 in my implementation it has the value 0x54686520
// You need to pack the bytes into 32 bit words
		for(j=i;j<i+64;j+=4)w[(i-j)/4] = *((long*)in+j);// break chunk into sixteen 32-bit big-endian words w[i], 0 <= i <= 15

<snip>
	}
}

[gulyan]

thx for the reply :D
I've made changes to the code and also found that i was using "i" inside the for wich used it as an index....

I'm a little confuze about big and little endians

after the firs run through the loop, w[0] contains " ehT" not "The" .. so i gues this is a little endian.

for(j=i;j<i+64;j+=4)w[(j-i)/4] = *((long*)(buff+j));

How can I make a 32-bit big endian using 4 bytes? :-??


the code now looks like this

#define ROTL( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

void SHA1(const char *in, long length, char *sha)
{
    char *buff = new char[length + 64];
	int i, j;
	for(i = 0; i < length; i++)buff[i] = in[i];//copy to buffer
	long bitLength = length * sizeof(char);//size in bits
	long w[80], a, b, c, d, e, f, k, temp;
	unsigned long h0 = 0x67452301;
    unsigned long h1 = 0xEFCDAB89;
    unsigned long h2 = 0x98BADCFE;
    unsigned long h3 = 0x10325476;
    unsigned long h4 = 0xC3D2E1F0;
	buff[length++] = (char)128;//1 7x0
    while(length%64 != 60)buff[length++] = 0;//8x0
	*((long*)(in+length)) = bitLength;
	length+=4;
	for(i=0;i<length;i+=64)
    {
        for(j=i;j<i+64;j+=4)w[(j-i)/4] = *((long*)(buff+j));
		for(j=16;j<80;j++)w[j] = ROTL((w[j-3]^w[j-8]^w[j-14]^w[j-16]), 1);
		if(i==0)cout<<w[0]<<endl;
        a = h0;
        b = h1;
        c = h2;
        d = h3;
        e = h4;
        for(j=0;j<80;j++)
        {
            if(0<=j&&j<20)
            {
                f = (b & c) | ((! b) & d);
                k = 0x5A827999;
            }
            else if(j>=20&&j<40)
            {
                f = b ^ c ^ d;
                k = 0x6ED9EBA1;
            }
            else if(j>=40&&j<60)
            {
                f = (b & c) | (b & d) | (c & d);
                k = 0x8F1BBCDC;
            }
            else if(j>=60&&j<80)
            {
                f = b ^ c ^ d;
                k = 0xCA62C1D6;
            }
            temp = ROTL(a, 5) + f + e + k + w[j];
            e = d;
            d = c;
            c = ROTL(b, 30);
            b = a;
            a = temp;
        }
        h0 = h0 + a;
        h1 = h1 + b;
        h2 = h2 + c;
        h3 = h3 + d;
        h4 = h4 + e;
	}
	sprintf_s(sha, 512, "%u %u %u %u %u", h0, h1, h2, h3, h4);
}

[Banfa]

for(j=i;j<i+64;j+=4)w[(j-i)/4] = *((long*)(buff+j));

How can I make a 32-bit big endian using 4 bytes? :-??

Do not use pointer casts, it doesn't work on little endian machines (I guess you are using a PC which is little endian).

Use the bitwise operators in this case | (or) and << (shift left) to locate each byte in the specific place you want it to hold in the 32 bit word. For instance the first byte should be the most significant byte of the word so

unsigned long word;
unsigned char byte;

word = 0;
word |= byte << 24;

By using arithmetic operators rather than casts you ensure you code is portable because the operation with have the same result on all platforms but the cast (as you have seen) has different results on big and little endian platforms.


P.S. You now have a memory leak in you function because you do not delete buff.

[Banfa]

long bitLength = length * sizeof(char);//size in bits

sizeof returns the size of a type (or variable) in bytes not bits. Since a char is always 1 byte sizeof(char) is guaranteed to be 1.

You could use the symbol CHAR_BITS defined in limits.h (or climits if your are using C++).

However I think the implementation as you have it will only work on machines with 8 bit bytes. This is because a machine with not 8 bit bytes (7 for example) would be unlike to have a 32 bit unsigned long and much more likely to have a 28bit unsigned long.

[gulyan]

thx again, I've made tha changes in the program

long bitLength = length * 8;

and

for(j=i;j<i+64;j+=4)
		{
			w[(j-i)/4] = buff[j] << 24;
			w[(j-i)/4] |= buff[j+1] << 16;
			w[(j-i)/4] |= buff[j+2] << 8;
			w[(j-i)/4] |= buff[j+3];
		}

After the first run through the loop, w[0] is 1416127776 wich is 01010100 01101000 01100101 00100000 in binary, meaning 84, 104, 101, 32.
Using the ASCII table it means "The " so now it works fine but the final result is still not the right one :( i get this (afeter i convert to hex) :
12415579 DA38E2A2 98BADDEE 88325476 BD725B not this:
2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

this is what I have so far:

#define ROTL( a , b ) ( ( ( b ) << a ) | ( ( b ) >> ( 32 - a ) ) )

void SHA1(const char *in, long length, char *sha)
{
    char *buff = new char[length + 64];
	int i, j;
	for(i = 0; i < length; i++)buff[i] = in[i];//copy to buffer
	long bitLength = length * 8;//size in bits
	long w[80], a, b, c, d, e, f, k, temp;
	unsigned long h0 = 0x67452301;
    unsigned long h1 = 0xEFCDAB89;
    unsigned long h2 = 0x98BADCFE;
    unsigned long h3 = 0x10325476;
    unsigned long h4 = 0xC3D2E1F0;
	buff[length++] = (char)128;//1 7x0
    while(length%64 != 60)buff[length++] = 0;//8x0
	cout<<bitLength<<endl;
	buff[length] = char((bitLength >> 24));
	buff[length+1] = char(255&(bitLength >> 16));
	buff[length+2] = char(255&(bitLength >> 8));
	buff[length+3] = char(255&(bitLength));
	length+=4;
	for(i=0;i<length;i+=64)
    {
        for(j=i;j<i+64;j+=4)
		{
			w[(j-i)/4] = buff[j] << 24;
			w[(j-i)/4] |= buff[j+1] << 16;
			w[(j-i)/4] |= buff[j+2] << 8;
			w[(j-i)/4] |= buff[j+3];
		}
		if(i==0)cout<<w[0]<<endl;
		for(j=16;j<80;j++)w[j] = ROTL((w[j-3]^w[j-8]^w[j-14]^w[j-16]), 1);
        a = h0;
        b = h1;
        c = h2;
        d = h3;
        e = h4;
        for(j=0;j<80;j++)
        {
            if(0<=j&&j<20)
            {
                f = (b & c) | ((! b) & d);
                k = 0x5A827999;
            }
            else if(j>=20&&j<40)
            {
                f = b ^ c ^ d;
                k = 0x6ED9EBA1;
            }
            else if(j>=40&&j<60)
            {
                f = (b & c) | (b & d) | (c & d);
                k = 0x8F1BBCDC;
            }
            else if(j>=60&&j<80)
            {
                f = b ^ c ^ d;
                k = 0xCA62C1D6;
            }
            temp = ROTL(a, 5) + f + e + k + w[j];
            e = d;
            d = c;
            c = ROTL(b, 30);
            b = a;
            a = temp;
        }
        h0 = h0 + a;
        h1 = h1 + b;
        h2 = h2 + c;
        h3 = h3 + d;
        h4 = h4 + e;
	}
	delete [] buff;
	sprintf_s(sha, 512, "%u %u %u %u %u", h0, h1, h2, h3, h4);
}

[archonmagnus]

if(0<=j&&j<20)
{
    f = (b & c) | ((! b) & d);
    k = 0x5A827999;
}

One thing that will help is using the correct "NOT" operation. (!b) will be evaluated as "false" rather than the compliment of b. You can fix this by using the bitwise operator "~" as:

[code=cpp]
if(j<20)
{
f = (b & c) | ((~b) & d);
k = 0x5A827999;
}
[/code]

See Operators in C and C++ [Wikipedia]. Hope that helps.

[Banfa]

The final 3 errors in your code are

The algorithm calls for unsigned arithmetic but you used lots of signed variables and thus invoke signed arithmetic, specifically sign extension when converting chars to longs.

You have used logical not (!) instead of bitwise not (~) in your calculations.

Actually the formula in your macro ROTL is wrong, check it with a simple example and you will see.

Fix those 3 and your function works (or at least it did for me).

[gulyan]

Thx Banfa and archonmagnus for your help :D

I changed the ! to ~ and rewrote the macro.

With the last sugestion of using unsigned when converting, the algorithm finaly works. Thx again :D

This is the final algorithm.. maybe it can help someone else as well

unsigned long ROTL(long a, long b)
{
	return (a<<b)|(~(0xFFFFFFFF<<b)&(a>>(32-b)));
}

void SHA1(const char *in, long length, char *sha)
{
    unsigned char *buff = new unsigned char[length + 64];
	int i, j;
	for(i = 0; i < length; i++)buff[i] = (unsigned char)in[i];//copy to buffer
	long bitLength = length * 8;//size in bits
	long w[80], a, b, c, d, e, f, k, temp;
	unsigned long h0 = 0x67452301;
    unsigned long h1 = 0xEFCDAB89;
    unsigned long h2 = 0x98BADCFE;
    unsigned long h3 = 0x10325476;
    unsigned long h4 = 0xC3D2E1F0;
	buff[length++] = (unsigned char)128;//1 7x0
    while(length%64 != 60)buff[length++] = 0;//8x0
	cout<<bitLength<<endl;
	buff[length] = (unsigned char)((bitLength >> 24));
	buff[length+1] = (unsigned char)(255&(bitLength >> 16));
	buff[length+2] = (unsigned char)(255&(bitLength >> 8));
	buff[length+3] = (unsigned char)(255&(bitLength));
	length+=4;
	for(i=0;i<length;i+=64)
    {
        for(j=i;j<i+64;j+=4)
		{
			w[(j-i)/4] = buff[j] << 24;
			w[(j-i)/4] |= buff[j+1] << 16;
			w[(j-i)/4] |= buff[j+2] << 8;
			w[(j-i)/4] |= buff[j+3];
		}
		for(j=16;j<80;j++)w[j] = ROTL((w[j-3]^w[j-8]^w[j-14]^w[j-16]), 1);
        a = h0;
        b = h1;
        c = h2;
        d = h3;
        e = h4;
        for(j=0;j<80;j++)
        {
            if(0<=j&&j<20)
            {
                f = (b & c) | ((~b) & d);
                k = 0x5A827999;
            }
            else if(j>=20&&j<40)
            {
                f = b ^ c ^ d;
                k = 0x6ED9EBA1;
            }
            else if(j>=40&&j<60)
            {
                f = (b & c) | (b & d) | (c & d);
                k = 0x8F1BBCDC;
            }
            else if(j>=60&&j<80)
            {
                f = b ^ c ^ d;
                k = 0xCA62C1D6;
            }
            temp = ROTL(a, 5) + f + e + k + w[j];
            e = d;
            d = c;
            c = ROTL(b, 30);
            b = a;
            a = temp;
        }
        h0 = h0 + a;
        h1 = h1 + b;
        h2 = h2 + c;
        h3 = h3 + d;
        h4 = h4 + e;
	}
	delete [] buff;
	sprintf_s(sha, 512, "%u %u %u %u %u", h0, h1, h2, h3, h4);
}