c - SHA-1哈希错误

Question

我计划用AVR密码的SHA-1implementation进行HMAC然而，我似乎无法生成正确的SHA-1和。
例如，如果我用以下命令调用函数

  unsigned char sha1sum[20];
  char *msg = "FFFFFFFFFF";

  sha1( sha1sum, msg, strlen(msg));

我得到的是000000000000000000002C002312290000000029而不是预期的c1bb92851109fe950a2655fa1d4ba1d04719f6fb有人知道怎么回事吗？这是AVR密码的实现

#include <string.h> /* memcpy & co */
#include <stdint.h>
#include "config.h"
#include "debug.h"
#include "sha1.h"

#ifdef DEBUG
#  undef DEBUG
#endif

#include "cli.h"

#define LITTLE_ENDIAN

/********************************************************************************************************/

/**
 * \brief initialises given SHA-1 context
 *
 */
void sha1_init(sha1_ctx_t *state){
    DEBUG_S("\r\nSHA1_INIT");
    state->h[0] = 0x67452301;
    state->h[1] = 0xefcdab89;
    state->h[2] = 0x98badcfe;
    state->h[3] = 0x10325476;
    state->h[4] = 0xc3d2e1f0;
    state->length = 0;
}

/********************************************************************************************************/
/* some helping functions */
uint32_t rotl32(uint32_t n, uint8_t bits){
    return ((n<<bits) | (n>>(32-bits)));
}

uint32_t change_endian32(uint32_t x){
    return (((x)<<24) | ((x)>>24) | (((x)& 0x0000ff00)<<8) | (((x)& 0x00ff0000)>>8));
}


/* three SHA-1 inner functions */
uint32_t ch(uint32_t x, uint32_t y, uint32_t z){
    DEBUG_S("\r\nCH");
    return ((x&y)^((~x)&z));
}

uint32_t maj(uint32_t x, uint32_t y, uint32_t z){
    DEBUG_S("\r\nMAJ");
    return ((x&y)^(x&z)^(y&z));
}

uint32_t parity(uint32_t x, uint32_t y, uint32_t z){
    DEBUG_S("\r\nPARITY");
    return ((x^y)^z);
}

/********************************************************************************************************/
/**
 * \brief "add" a block to the hash
 * This is the core function of the hash algorithm. To understand how it's working
 * and what thoese variables do, take a look at FIPS-182. This is an "alternativ" implementation
 */

#define MASK 0x0000000f

typedef uint32_t (*pf_t)(uint32_t x, uint32_t y, uint32_t z);

void sha1_nextBlock (sha1_ctx_t *state, const void *block){
    uint32_t a[5];
    uint32_t w[16];
    uint32_t temp;
    uint8_t t,s,fi, fib;
    pf_t f[] = {ch,parity,maj,parity};
    uint32_t k[4]={ 0x5a827999,
                    0x6ed9eba1,
                    0x8f1bbcdc,
                    0xca62c1d6};

    /* load the w array (changing the endian and so) */
    for(t=0; t<16; ++t){
        w[t] = change_endian32(((uint32_t*)block)[t]);
    }

#if DEBUG
    uint8_t dbgi;
    for(dbgi=0; dbgi<16; ++dbgi){
        /*
        DEBUG_S("\n\rBlock:");
        DEBUG_B(dbgi);
        DEBUG_C(':');
        */
        cli_putstr_P(PSTR("\r\nBlock:"));
        cli_hexdump(&dbgi, 1);
        cli_putc(':');
        cli_hexdump(&(w[dbgi]) ,4);
    }
#endif

    /* load the state */
    memcpy(a, state->h, 5*sizeof(uint32_t));


    /* the fun stuff */
    for(fi=0,fib=0,t=0; t<=79; ++t){
        s = t & MASK;
        if(t>=16){
            #if DEBUG
             DEBUG_S("\r\n ws = "); cli_hexdump(&(w[s]), 4);
            #endif
            w[s] = rotl32( w[(s+13)&MASK] ^ w[(s+8)&MASK] ^
                 w[(s+ 2)&MASK] ^ w[s] ,1);
            #ifdef DEBUG
             DEBUG_S(" --> ws = "); cli_hexdump(&(w[s]), 4);
            #endif
        }

        uint32_t dtemp;
        temp = rotl32(a[0],5) + (dtemp=f[fi](a[1],a[2],a[3])) + a[4] + k[fi] + w[s];
        memmove(&(a[1]), &(a[0]), 4*sizeof(uint32_t)); /* e=d; d=c; c=b; b=a; */
        a[0] = temp;
        a[2] = rotl32(a[2],30); /* we might also do rotr32(c,2) */
        fib++;
        if(fib==20){
            fib=0;
            fi = (fi+1)%4;
        }
        #if DEBUG
        /* debug dump */
        DEBUG_S("\r\nt = "); DEBUG_B(t);
        DEBUG_S("; a[]: ");
         cli_hexdump(a, 5*4);
        DEBUG_S("; k = ");
         cli_hexdump(&(k[t/20]), 4);
        DEBUG_S("; f(b,c,d) = ");
         cli_hexdump(&dtemp, 4);
        #endif
    }

    /* update the state */
    for(t=0; t<5; ++t){
        state->h[t] += a[t];
    }
    state->length += 512;
}

/********************************************************************************************************/

void sha1_lastBlock(sha1_ctx_t *state, const void *block, uint16_t length){
    uint8_t lb[SHA1_BLOCK_BYTES]; /* local block */
    while(length>=SHA1_BLOCK_BITS){
        sha1_nextBlock(state, block);
        length -= SHA1_BLOCK_BITS;
        block = (uint8_t*)block + SHA1_BLOCK_BYTES;
    }
    state->length += length;
    memset(lb, 0, SHA1_BLOCK_BYTES);
    memcpy (lb, block, (length+7)>>3);

    /* set the final one bit */
    lb[length>>3] |= 0x80>>(length & 0x07);

    if (length>512-64-1){ /* not enouth space for 64bit length value */
        sha1_nextBlock(state, lb);
        state->length -= 512;
        memset(lb, 0, SHA1_BLOCK_BYTES);
    }
    /* store the 64bit length value */
#if defined LITTLE_ENDIAN
        /* this is now rolled up */
    uint8_t i;
    for (i=0; i<8; ++i){
        lb[56+i] = ((uint8_t*)&(state->length))[7-i];
    }
#elif defined BIG_ENDIAN
    *((uint64_t)&(lb[56])) = state->length;
#endif
    sha1_nextBlock(state, lb);
}

/********************************************************************************************************/

void sha1_ctx2hash (void *dest, sha1_ctx_t *state){
#if defined LITTLE_ENDIAN
    uint8_t i;
    for(i=0; i<5; ++i){
        ((uint32_t*)dest)[i] = change_endian32(state->h[i]);
    }
#elif BIG_ENDIAN
    if (dest != state->h)
        memcpy(dest, state->h, SHA1_HASH_BITS/8);
#else
# error unsupported endian type!
#endif
}

/********************************************************************************************************/
/**
 *
 *
 */
void sha1 (void *dest, const void *msg, uint32_t length){
    sha1_ctx_t s;
    DEBUG_S("\r\nBLA BLUB");
    sha1_init(&s);
    while(length & (~0x0001ff)){ /* length>=512 */
        DEBUG_S("\r\none block");
        sha1_nextBlock(&s, msg);
        msg = (uint8_t*)msg + SHA1_BLOCK_BITS/8; /* increment pointer to next block */
        length -= SHA1_BLOCK_BITS;
    }
    sha1_lastBlock(&s, msg, length);
    sha1_ctx2hash(dest, &s);
}

标题如下：

#ifndef SHA1_H_
#define SHA1_H_

#include "stdint.h"
/** \def SHA1_HASH_BITS
 * definees the size of a SHA-1 hash in bits 
 */

/** \def SHA1_HASH_BYTES
 * definees the size of a SHA-1 hash in bytes 
 */

/** \def SHA1_BLOCK_BITS
 * definees the size of a SHA-1 input block in bits 
 */

/** \def SHA1_BLOCK_BYTES
 * definees the size of a SHA-1 input block in bytes 
 */
#define SHA1_HASH_BITS  160
#define SHA1_HASH_BYTES (SHA1_HASH_BITS/8)
#define SHA1_BLOCK_BITS 512
#define SHA1_BLOCK_BYTES (SHA1_BLOCK_BITS/8)

/** \typedef sha1_ctx_t
 * \brief SHA-1 context type
 * 
 * A vatiable of this type may hold the state of a SHA-1 hashing process
 */
typedef struct {
    uint32_t h[5];
//  uint64_t length;
    uint8_t length;
} sha1_ctx_t;

/** \typedef sha1_hash_t
 * \brief hash value type
 * A variable of this type may hold a SHA-1 hash value 
 */
/*
typedef uint8_t sha1_hash_t[SHA1_HASH_BITS/8];
*/

/** \fn sha1_init(sha1_ctx_t *state)
 * \brief initializes a SHA-1 context
 * This function sets a ::sha1_ctx_t variable to the initialization vector
 * for SHA-1 hashing.
 * \param state pointer to the SHA-1 context variable
 */
void sha1_init(sha1_ctx_t *state);

/** \fn sha1_nextBlock(sha1_ctx_t *state, const void *block)
 *  \brief process one input block
 * This function processes one input block and updates the hash context 
 * accordingly
 * \param state pointer to the state variable to update
 * \param block pointer to the message block to process
 */
void sha1_nextBlock (sha1_ctx_t *state, const void *block);

/** \fn sha1_lastBlock(sha1_ctx_t *state, const void *block, uint16_t length_b)
 * \brief processes the given block and finalizes the context
 * This function processes the last block in a SHA-1 hashing process.
 * The block should have a maximum length of a single input block.
 * \param state pointer to the state variable to update and finalize
 * \param block pointer to themessage block to process
 * \param length_b length of the message block in bits  
 */
void sha1_lastBlock (sha1_ctx_t *state, const void *block, uint16_t length_b);

/** \fn sha1_ctx2hash(sha1_hash_t *dest, sha1_ctx_t *state)
 * \brief convert a state variable into an actual hash value
 * Writes the hash value corresponding to the state to the memory pointed by dest.
 * \param dest pointer to the hash value destination
 * \param state pointer to the hash context
 */ 
void sha1_ctx2hash (void *dest, sha1_ctx_t *state);

/** \fn sha1(sha1_hash_t *dest, const void *msg, uint32_t length_b)
 * \brief hashing a message which in located entirely in RAM
 * This function automatically hashes a message which is entirely in RAM with
 * the SHA-1 hashing algorithm.
 * \param dest pointer to the hash value destination
 * \param msg  pointer to the message which should be hashed
 * \param length_b length of the message in bits
 */ 
void sha1(void *dest, const void *msg, uint32_t length_b);



#endif /*SHA1_H_*/

更新如果我用sha1sum初始化unsigned char sha1sum[20] = 0;，得到的和都是0x00。

Answer 1

问题代码中至少有两个bug（详细信息如下），但这两个bug都无法解释所显示的结果，并且调用代码中的unsigned char sha1sum[20] = {0}会更改结果这一额外事实从我们读入机器代码的C源代码的翻译有问题很有可能，sha1_ctx2hash没有写在它应该写的地方。
问题可能在标题中而不是在问题中，编译器错误因为我们使用的是8051，所以这可能是/曾经是pointer types的一个问题，特别是在必须指向相同大小指针的指针类型转换中。
另外，8051编译器是不是小尾数呢？这似乎是常见的Keil C51 uses big-endian convention这是编译器+支持库的任意选择，因为在原来的8051上没有多字节数据相关的指令，最接近的是LCALL，堆栈推送是小endian，但是LJMP和MOV DPTR，#代码是大endian。更新：我们被告知编译器是由IAR编写的。根据IAR's documentation，版本5是big-endian，而版本6则改为little-endian。
更新：我们发现了另一个关键问题（除了可能不安全的指针转换和下面讨论的两个错误之外）。在hunt中的某个时刻，用一个没有endianness依赖关系或指针转换的过程替换代码，输出变为0000eb1700007f3d000004f0000059290000fc21，建议的32位值被截断为16位事实上，OP透露：
我的stdint.h里有这个：typedef unsigned uint32_t;
只有当C标准给出的唯一保证是至少16位，并且大多数C编译器使用最小值来处理小于32位的CPU（出于效率的原因；有些编译器甚至可以选择禁用将字节操作数提升为整数，甚至对unsigned int是正确的80+80+96）。
测试代码中的错误：0应该是sha1( sha1sum, msg, strlen(msg))之类的，因为长度参数是以位为单位的。
sha1( sha1sum, msg, strlen(msg)*8)w.r.t.头文件中的错误：代码读取

for (i=0; i<8; ++i){
    lb[56+i] = ((uint8_t*)&(state->length))[7-i];
}

假设sha1_lastBlock是8个字节，而不是，因为头中的state->length已更改为uint64_t length（8051编译器上通常不提供uint8_t length）。big endian case（目前尚未编译）的代码也会受到影响。
如果确实uint64_t并且因此对最多31个字节的长度的限制是可以接受的，那么小端和大端的情况都会减少到uint8_t length（没有循环）。
或者，对于任何无符号类型和endiannesslb[SHA1_BLOCK_BYTES-1] = state->length;都可以使用：

for (i = SHA1_BLOCK_BYTES; state->length != 0; state->length >>= 8)
    lb[--i] = (uint8_t)(state->length);

注意：代码length正在将*((uint64_t*)&(lb[56])) = state->length的8字节写入数组length的末尾，但仅在具有正确lb[]的大端机上正确。
当uint64_t时，代码有一个潜在的额外问题：在要散列的最后一个字节中至少有一个位没有被屏蔽，如果设置了它，它将进入散列并使其出错这在散列完整字节的用例中不会造成损害。
原始代码可能是正确的（除了上述潜在的额外问题外），但是由于目标是用一个调用对内存中的数据进行散列（what(length+7)%8 < 6做什么），并且既不紧凑也不可读，所以不必要地复杂。除其他问题外：
在sha1中有一个（正确的）块循环，因此在块的标题中的限制词应该不存在单个输入块的最大长度；
这使得sha1_lastBlock中的另一个块循环冗余；
如果使用sha1或哈希小于56字节，则可以删除这两个循环；
循环可能会被16字节的uint8_t length和从索引表中调用向量的函数所减慢；
在小endian情况下，endianness转换效率很低；
在memmove中，sha1_ctx2hash会在我的心理编译器中触发一个错误，因为#elif BIG_ENDIAN似乎未定义，BIG_ENDIAN应该有一个参数；这个参数应该是#elif（如上面几行所用）；
#elif defined BIG_ENDIAN是pf_t f[] = {ch,parity,maj,parity};的一个很好的候选者，也许const：我曾经使用过的每一个8051的C编译器都不会意识到数组在设置后没有改变，因此可以在代码中进行雕刻；
对于这样的编译器，不必要地使用函数指针（如上所述）是一种尝试过的测试方法，会损害性能，甚至更糟；至少它会阻止对调用树的分析，需要在静态地址使用overlay来分配自动变量，这反过来会显著提高性能和代码大小。
如果你追求的是速度，那么你开始的代码是不够的，没有什么能完全匹配汇编语言就像20年前，我为8051工具链编写了SHA-1，与仅使用C相比，程序集调整带来了巨大的节省（IIRC：主要是因为从性能角度来看，32位的旋转非常糟糕）。
更新：这里是一个示例性代码，它以一种与endian无关的方式散列短消息，不使用任何指针转换，也不依赖于static（这对于所使用的编译器来说是不充分的）。请注意，<stdint.h>参数以字节（而不是位）为单位，限制为55字节，不允许在顶部实现HMAC-SHA-1这是为了保持代码简单：超过这个限制，我们需要对压缩函数进行多次迭代，因此要么是大量的代码重复，至少需要两个函数，要么是某种状态机。

#include <limits.h> // for UCHAR_MAX, UINT_MAX, ULONG_MAX

// Compute the SHA-1 hash of a short msg, of length at most 55 bytes
// Result hash must be 20 bytes; it can overlap msg.
// CAUTION: if length>55 the result is wrong, and if length>59
// we loose second-preimage resistance, thus collision-resistance.
void sha1upto55bytes(
          unsigned char *hash,  // result, 20 bytes
    const unsigned char *msg,   // bytes to hash
          unsigned char length  // length of msg in bytes, maximum 55
    )
    {
    // We locally (re)define uint8_t and uint32_t so as not to depend of <stdint.h>
    // which is not available on some old C compilers for embedded systems.
#if 255==UCHAR_MAX
    typedef unsigned char uint8_t;
#endif
#if 16383==UINT_MAX>>9>>9
    typedef unsigned int uint32_t;
#elif  16383==ULONG_MAX>>9>>9
    typedef unsigned long uint32_t;
#endif

    // Internal buffer (64 bytes)
    // We require 8-bit uint8_t, 32-bit uint32_t, and integer promotion; otherwise,
    // we try to abort compilation on the following declaration.
    uint32_t w[
        99==(uint8_t)355              &&  // check uint8_t
        4303==(uint32_t)(-1)/999u/999 &&  // check uint32_t
        440==(uint8_t)55<<3               // check integer promotion
        ? 16 : -1];                       // negative index if error

    // Type for state, so that we can use struct copy for that
    typedef struct state_t { uint32_t q[5]; } state_t;

    // Initial state; use single quotes if the compiler barks
    const state_t s = {{ 0x67452301,0xefcdab89,0x98badcfe,0x10325476,0xc3d2e1f0 }};

    // Active state (20 bytes); on 8051 should be in internal RAM for best performance
    state_t h = s;  // initialize the state using a struct copy

   // Workhorse temporary; on 8051 should be in internal RAM for best performance
    uint32_t x;

    // Workhorse index; on 8051 should be a register for performance
    uint8_t  j;

    // Prepare the single block to hash; this code works regardless of endianness,
    // and does not perform misaligned memory accesses if msg is misaligned.
    x = 0;  // This is only to prevent a bogus compiler warning
    j = 0;
    do
        {   // for each block byte, up to and including high 4 bytes of length
        x <<= 8;
        if (j < length)
            x |= *msg++;    // message byte
        else
            if (j == length)
                x |= 0x80;  // padding byte
        if ((j&3)==3)
            w[j >> 2] = x;
        }
    while (++j!=60);
    w[15] = length << 3;    // length in bits, needs integer promotion for length>31

    // Hash that block
    j = 0;
    do {        // round loop, run 80 times
        do {        // dummy loop (avoid a goto)
            if (j<40) {
                if (j<20) {             // for rounds 0..19
                    x = (((h.q[2] ^ h.q[3])&h.q[1]) ^ h.q[3]) + 0x5A827999;
                    break;  // out of dummy loop
                    }
                else
                    x = 0x6ED9EBA1;     // for rounds 20..39
                }
            else {
                if (j<60) {             // for rounds 40..59
                    x = (h.q[1] | h.q[2])&h.q[3];
                    x |= h.q[1] & h.q[2];
                    x += 0x8F1BBCDC;
                    break;
                    }
                else
                    x = 0xCA62C1D6;     // for rounds 60..79
                }
            // for rounds 20..39 and 60..79
            x += h.q[1] ^ h.q[2] ^ h.q[3];
            }
        while (0);      // end of of dummy loop
        // for all rounds
        x += (h.q[0] << 5) | (h.q[0] >> 27);
        x += h.q[4];
        h.q[4] = h.q[3];
        h.q[3] = h.q[2];
        h.q[2] = (h.q[1] << 30) | (h.q[1] >> 2);
        h.q[1] = h.q[0];
        h.q[0] = x;
        x = w[j & 15];
        if (j>=16) {    // rounds 16..79
            x ^= w[(j + 2) & 15];
            x ^= w[(j + 8) & 15];
            x ^= w[(j + 13) & 15];
            w[j & 15] = x = (x << 1) | (x >> 31);
            }
        h.q[0] += x;    // for all rounds
        }
    while (++j != 80);
    // The five final 32-bit modular additions are made in the next loop, and
    // reuse the constants (rather than a RAM copy), saving code and RAM.

    // Final addition and store result; this code works regardless of endianness,
    // and does not perform misaligned memory accesses if hash is misaligned.
    j = 0;
    do
        {
        x = h.q[j] + s.q[j];    // final 32-bit modular additions
        *hash++ = (uint8_t)(x>>24);
        *hash++ = (uint8_t)(x>>16);
        *hash++ = (uint8_t)(x>> 8);
        *hash++ = (uint8_t)(x    );
        }
    while (++j != 5);
    }