Implementation of the SHA256 algorithm do not return the expected result

user_2692962 0
Viewed 732

With the implementation below, based on the pseudo-code available here, I am trying to convert a string generated with the concatenation of the members from this class:

class BlockHeader
{
private:
  int version;
  string hashPrevBlock;
  string hashMerkleRoot;
  int time;
  int bits;
  int nonce;
}

into a SHA256 hash, like what was done with the python code below, available here:

>>> import hashlib
>>> header_hex = ("01000000" +
 "81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
 "e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
 "c7f5d74d" +
 "f2b9441a" +
 "42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

I expect that my program would return the same result the program above returned, but instead, when I compile and run this:

int main() {
  BlockHeader header;
  header.setVersion(0x01000000);
  header.setHashPrevBlock("81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000");
  header.setHashMerkleRoot("e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b");
  header.setTime(0xc7f5d74d);
  header.setBits(0xf2b9441a);
  header.setNonce(0x42a14695);

  Sha256 hash1(header.bytes());
  array<BYTE, SHA256_BLOCK_SIZE> h1 = hash1.hash();

  cout << "hash1: ";
  for(int i=0; i<h1.size(); i++)
    printf("%.2x", h1[i]);
  printf("\n");

  Sha256 hash2(h1);
  array<BYTE, SHA256_BLOCK_SIZE> h2 = hash2.hash();

  cout << "hash2: ";
  for(int i=0; i<h2.size(); i++)
    printf("%.2x", h2[i]);
  printf("\n");
}

the result is that:

hash1: e2245204380a75c6bc6ac56f0000000040030901000000001100011000000000
hash2: 68a74f2a36c8906068c6cd6f00000000020000000000000080a7d06f00000000

I am aware the endianess in my program are not the same of the python result, but this I can fix later, when I get the correct result. Looking in the code below, can anyone give a hint of what I am missing here?

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

#define CH(x,y,z) (((x) & (y)) ^ (~(x) & (z)))
#define MAJ(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))

#define EP0(x) (ROTRIGHT(x,2) ^ ROTRIGHT(x,13) ^ ROTRIGHT(x,22))
#define EP1(x) (ROTRIGHT(x,6) ^ ROTRIGHT(x,11) ^ ROTRIGHT(x,25))

#define SIG0(x) (ROTRIGHT(x,7) ^ ROTRIGHT(x,18) ^ ((x) >> 3))
#define SIG1(x) (ROTRIGHT(x,17) ^ ROTRIGHT(x,19) ^ ((x) >> 10))

Sha256::Sha256(vector<BYTE> data) {
    SIZE64 L = data.size() / 2;
    SIZE64 K = 0;
    while( (L + 1 + K + 8) % 64 != 0)
        K = K + 1;

    for(int i=0; i<L; i++) {
        BYTE c = (data[i] % 32 + 9) % 25 * 16 + (data[i+1] % 32 + 9) % 25;
        source.push_back(c);
    }

    source.push_back(0x80);

    for(int i=0; i<K; i++)
        source.push_back(0x00);

    SIZE64 x = L + 1 + K + 8;
    for(int i=0; i<sizeof(x); i++)
        source.push_back( x >> i*8 );
}

Sha256::Sha256(array<BYTE, SHA256_BLOCK_SIZE> data) {
    SIZE64 L = data.size() / 2;
    SIZE64 K = 0;
    while( (L + 1 + K + 8) % 64 != 0)
        K = K + 1;

    for(int i=0; i<L; i++) {
        BYTE c = (data[i] % 32 + 9) % 25 * 16 + (data[i+1] % 32 + 9) % 25;
        source.push_back(c);
    }

    source.push_back(0x80);

    for(int i=0; i<K; i++)
        source.push_back(0x00);

    SIZE64 x = L + 1 + K + 8;
    for(int i=0; i<sizeof(x); i++)
        source.push_back( x >> i*8 );
}

array<BYTE, SHA256_BLOCK_SIZE> Sha256::hash() {
    array<BYTE, SHA256_BLOCK_SIZE> result;

    WORD32 h0 = 0x6a09e667, h1 = 0xbb67ae85, h2 = 0x3c6ef372, h3 = 0xa54ff53a, h4 = 0x510e527f, h5 = 0x9b05688c, h6 = 0x1f83d9ab, h7 = 0x5be0cd19;

    WORD32 k[64] = {0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2};

    WORD32 a, b, c, d, e, f, g, h, i, j, t1, t2, m[64];

    for(int chunk=0; chunk<=source.size()/64; chunk++) {
        for (i = 0, j = chunk*64; i < 16; ++i, j += 4)
            m[i] = (source[j] << 24) | (source[j + 1] << 16) | (source[j + 2] << 8) | (source[j + 3]);
        for ( ; i < 64; ++i)
            m[i] = SIG1(m[i - 2]) + m[i - 7] + SIG0(m[i - 15]) + m[i - 16];

        a = h0;
        b = h1;
        c = h2;
        d = h3;
        e = h4;
        f = h5;
        g = h6;
        h = h7;

        for (i = 0; i < 64; ++i) {
            t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i];
            t2 = EP0(a) + MAJ(a,b,c);
            h = g;
            g = f;
            f = e;
            e = d + t1;
            d = c;
            c = b;
            b = a;
            a = t1 + t2;
        }

        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;
        h4 += e;
        h5 += f;
        h6 += g;
        h7 += h;
    }

    for(int i=0; i<4; i++) result[0] = h0 >> i;
    for(int i=0; i<4; i++) result[1] = h1 >> i;
    for(int i=0; i<4; i++) result[2] = h2 >> i;
    for(int i=0; i<4; i++) result[3] = h3 >> i;
    for(int i=0; i<4; i++) result[4] = h4 >> i;
    for(int i=0; i<4; i++) result[5] = h5 >> i;
    for(int i=0; i<4; i++) result[6] = h6 >> i;
    for(int i=0; i<4; i++) result[7] = h7 >> i;

  return result;
}
sha256 c++
1 Answers

In the Sha256::hash function, result is a BYTE array, whereas h0 is a WORD32. You might want to split h0 into 4 BYTEs and store into the result array, but the for loop at the end of the function won't achieve your goal.

What you want to do is to concatenate h0 to h7, and then extract the bytes from h0 to h7 by shifting 24, 16, 8, 0 bits:

// concatenate h0 to h7
WORD32 hs[8] = {h0, h1, h2, h3, h4, h5, h6, h7};

// extract bytes from hs to result
for(int i=0; i<8; i++) { // loop from h0 to h7
    result[i*4  ] = hs[i] >> 24; // the most significant byte of h_i
    result[i*4+1] = hs[i] >> 16;
    result[i*4+2] = hs[i] >> 8;
    result[i*4+3] = hs[i];       // the least significant byte of h_i
}

EDIT

After some testing, I found another error:

for(int chunk=0; chunk<=source.size()/64; chunk++) {
                      ^^

should be

for(int chunk=0; chunk<source.size()/64; chunk++) {
                      ^

chuck starts from 0, so you should use < instead of <=.
For example, when source.size() is 64, you only have 1 chunk to process.

EDIT2

I fully tested your code and found two problems in the constructors of the Sha256 class.

Your code implies that you assume the vector<BYTE> passed to the constructor is a hex string. That is OK, but you use the same code for the array<BYTE, SHA256_BLOCK_SIZE> version, which is the return type of hash() function, which returns a BYTE array instead of hex string.

For a BYTE array, you can simply push the byte data[i] into the source. Also, L should be data.size() because every element has size 1 in a byte array.

Besides, you try to append the size of the input(x) to source, but x should not include the appended one and zeros, and it is the bit count of the input, so x should simply be L*8. Also, the size should be a big-endian integer, so you have to push the bigger byte first:

for(int i=0; i<sizeof(x); i++) // WRONG: little endian
for(int i=sizeof(SIZE64)-1; i>=0; i--) // Correct: big endian

I have made it execute correctly and output:

hash1: b9d751533593ac10cdfb7b8e03cad8babc67d8eaeac0a3699b82857dacac9390
hash2: 1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000

If you encounter other problems, feel free to ask. You are very close to the correct answer. Hope you can fix all the bugs successfully :)

EDIT3: implementation of other function

struct BlockHeader {
    int version;
    string hashPrevBlock;
    string hashMerkleRoot;
    int time;
    int bits;
    int nonce;
    vector<BYTE> bytes();
};

#define c2x(x) (x>='A' && x<='F' ? (x-'A'+10) : x>='a' && x<='f' ? (x-'a'+10) : x-'0')
vector<BYTE> BlockHeader::bytes() {
    vector<BYTE> bytes;
    for (int i=24; i>=0; i-=8) bytes.push_back(version>>i);
    for (int i=0; i<hashPrevBlock.size(); i+=2)
        bytes.push_back(c2x(hashPrevBlock[i])<<4 | c2x(hashPrevBlock[i+1]));
    for (int i=0; i<hashMerkleRoot.size(); i+=2)
        bytes.push_back(c2x(hashMerkleRoot[i])<<4 | c2x(hashMerkleRoot[i+1]));
    for (int i=24; i>=0; i-=8) bytes.push_back(time>>i);
    for (int i=24; i>=0; i-=8) bytes.push_back(bits>>i);
    for (int i=24; i>=0; i-=8) bytes.push_back(nonce>>i);
    return bytes; // return bytes instead of hex string
}

// exactly the same as the vector<BYTE> version
Sha256::Sha256(array<BYTE, SHA256_BLOCK_SIZE> data) {
    SIZE64 L = data.size(); // <<
    SIZE64 K = 0;
    while( (L + 1 + K + 8) % 64 != 0)
        K = K + 1;
    // can be simplified to: int K = (128-1-8-L%64)%64;

    // ** thanks to "chux - Reinstate Monica" pointing out i should be a SIZE64
    for(SIZE64 i=0; i<L; i++) { // **
        source.push_back(data[i]); // <<
    }

    source.push_back(0x80);

    for(int i=0; i<K; i++)
        source.push_back(0x00);

    SIZE64 x = L*8; // <<
    for(int i=sizeof(SIZE64)-1; i>=0; i--) { // big-endian
        source.push_back(x >> i*8);
    }
}

EDIT4: variable size in for loop

As "chux - Reinstate Monica" pointed out, it may be a problem if the size of the data is bigger than INT_MAX. All for-loop using a size as the upper limit should use a size_t type counter(instead of int) to prevent this problem.

// in BlockHeader::bytes()
for (size_t i=0; i<hashPrevBlock.size(); i+=2)
// in Sha256::hash()
for (size_t chunk=0; chunk<source.size()/64; chunk++)
// in main()
for (size_t i=0; i<h1.size(); i++)
for (size_t i=0; i<h2.size(); i++)

Notice that size_t is unsigned. The reverse version won't work because i is never less than 0.

for (size_t i=data.size()-1; i>=0; i--) // infinite loop
user_144318630
Related