sha1.c

   1 /* sha1.c */
   2 /*
   3     This file is part of the AVR-Crypto-Lib.
   4     Copyright (C) 2008  Daniel Otte (daniel.otte@rub.de)
   5
   6     This program is free software: you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation, either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19 /**
  20  * \file        sha1.c
  21  * \author      Daniel Otte
  22  * \date        2006-10-08
  23  * \license GPLv3 or later
  24  * \brief SHA-1 implementation.
  25  *
  26  */
  27
  28 #include <string.h> /* memcpy & co */
  29 #include <stdint.h>
  30 #include "config.h"
  31 #undef DEBUG
  32 #include "debug.h"
  33 #include "sha1.h"
  34
  35 #define LITTLE_ENDIAN
  36
  37 /********************************************************************************************************/
  38
  39 /**
  40  * \brief initialises given SHA-1 context
  41  *
  42  */
  43 void sha1_init(sha1_ctx_t *state){
  44         DEBUG_S("\r\nSHA1_INIT");
  45         state->h[0] = 0x67452301;
  46         state->h[1] = 0xefcdab89;
  47         state->h[2] = 0x98badcfe;
  48         state->h[3] = 0x10325476;
  49         state->h[4] = 0xc3d2e1f0;
  50         state->length = 0;
  51 }
  52
  53 /********************************************************************************************************/
  54 /* some helping functions */
  55 uint32_t rotl32(uint32_t n, uint8_t bits){
  56         return ((n<<bits) | (n>>(32-bits)));
  57 }
  58
  59 uint32_t change_endian32(uint32_t x){
  60         return (((x)<<24) | ((x)>>24) | (((x)& 0x0000ff00)<<8) | (((x)& 0x00ff0000)>>8));
  61 }
  62
  63
  64 /* three SHA-1 inner functions */
  65 uint32_t ch(uint32_t x, uint32_t y, uint32_t z){
  66         DEBUG_S("\r\nCH");
  67         return ((x&y)^((~x)&z));
  68 }
  69
  70 uint32_t maj(uint32_t x, uint32_t y, uint32_t z){
  71         DEBUG_S("\r\nMAJ");
  72         return ((x&y)^(x&z)^(y&z));
  73 }
  74
  75 uint32_t parity(uint32_t x, uint32_t y, uint32_t z){
  76         DEBUG_S("\r\nPARITY");
  77         return ((x^y)^z);
  78 }
  79
  80 /********************************************************************************************************/
  81 /**
  82  * \brief "add" a block to the hash
  83  * This is the core function of the hash algorithm. To understand how it's working
  84  * and what thoese variables do, take a look at FIPS-182. This is an "alternativ" implementation
  85  */
  86
  87 #define MASK 0x0000000f
  88
  89 typedef uint32_t (*pf_t)(uint32_t x, uint32_t y, uint32_t z);
  90
  91 void sha1_nextBlock (sha1_ctx_t *state, const void* block){
  92         uint32_t a[5];
  93         uint32_t w[16];
  94         uint32_t temp;
  95         uint8_t t,s;
  96         pf_t f[] = {ch,parity,maj,parity};
  97         uint32_t k[4]={ 0x5a827999,
  98                                         0x6ed9eba1,
  99                                         0x8f1bbcdc,
 100                                         0xca62c1d6};
 101
 102         /* load the w array (changing the endian and so) */
 103         for(t=0; t<16; ++t){
 104                 w[t] = change_endian32(((uint32_t*)block)[t]);
 105         }
 106
 107         uint8_t dbgi;
 108         for(dbgi=0; dbgi<16; ++dbgi){
 109                 DEBUG_S("\n\rBlock:");
 110                 DEBUG_B(dbgi);
 111                 DEBUG_C(':');
 112                 #ifdef DEBUG
 113                         cli_hexdump(&(w[dbgi]) ,4);
 114                 #endif
 115         }
 116
 117
 118         /* load the state */
 119         memcpy(a, state->h, 5*sizeof(uint32_t));
 120
 121
 122         /* the fun stuff */
 123         for(t=0; t<=79; ++t){
 124                 s = t & MASK;
 125                 if(t>=16){
 126                         #ifdef DEBUG
 127                          DEBUG_S("\r\n ws = "); cli_hexdump(&ws, 4);
 128                         #endif
 129                         w[s] = rotl32( w[(s+13)&MASK] ^ w[(s+8)&MASK] ^
 130                                  w[(s+ 2)&MASK] ^ w[s] ,1);
 131                         #ifdef DEBUG
 132                          DEBUG_S(" --> ws = "); cli_hexdump(&(w[s]), 4);
 133                         #endif
 134                 }
 135
 136                 uint32_t dtemp;
 137                 temp = rotl32(a[0],5) + (dtemp=f[t/20](a[1],a[2],a[3])) + a[4] + k[t/20] + w[s];
 138                 memmove(&(a[1]), &(a[0]), 4*sizeof(uint32_t)); /* e=d; d=c; c=b; b=a; */
 139                 a[0] = temp;
 140                 a[2] = rotl32(a[2],30); /* we might also do rotr32(c,2) */
 141
 142                 /* debug dump */
 143                 DEBUG_S("\r\nt = "); DEBUG_B(t);
 144                 DEBUG_S("; a[]: ");
 145                 #ifdef DEBUG
 146                  cli_hexdump(a, 5*4);
 147                 #endif
 148                 DEBUG_S("; k = ");
 149                 #ifdef DEBUG
 150                  cli_hexdump(&(k[t/20]), 4);
 151                 #endif
 152                 DEBUG_S("; f(b,c,d) = ");
 153                 #ifdef DEBUG
 154                  cli_hexdump(&dtemp, 4);
 155                 #endif
 156         }
 157
 158         /* update the state */
 159         for(t=0; t<5; ++t){
 160                 state->h[t] += a[t];
 161         }
 162         state->length += 512;
 163 }
 164
 165 /********************************************************************************************************/
 166
 167 void sha1_lastBlock(sha1_ctx_t *state, const void* block, uint16_t length){
 168         uint8_t lb[SHA1_BLOCK_BITS/8]; /* local block */
 169         state->length += length;
 170         memcpy (&(lb[0]), block, length/8);
 171
 172         /* set the final one bit */
 173         if (length & 0x7){ /* if we have single bits at the end */
 174                 lb[length/8] = ((uint8_t*)(block))[length/8];
 175         } else {
 176                 lb[length/8] = 0;
 177         }
 178         lb[length/8] |= 0x80>>(length & 0x3);
 179         length =(length >> 7) + 1; /* from now on length contains the number of BYTES in lb*/
 180         /* pad with zeros */
 181         if (length>64-8){ /* not enouth space for 64bit length value */
 182                 memset((void*)(&(lb[length])), 0, 64-length);
 183                 sha1_nextBlock(state, lb);
 184                 state->length -= 512;
 185                 length = 0;
 186         }
 187         memset((void*)(&(lb[length])), 0, 56-length);
 188         /* store the 64bit length value */
 189 #if defined LITTLE_ENDIAN
 190                 /* this is now rolled up */
 191         uint8_t i;
 192         for (i=1; i<=8; ++i){
 193                 lb[55+i] = (uint8_t)(state->length>>(64- 8*i));
 194         }
 195 #elif defined BIG_ENDIAN
 196         *((uint64_t)&(lb[56])) = state->length;
 197 #endif
 198         sha1_nextBlock(state, lb);
 199 }
 200
 201 /********************************************************************************************************/
 202
 203 void sha1_ctx2hash (sha1_hash_t *dest, sha1_ctx_t *state){
 204 #if defined LITTLE_ENDIAN
 205         uint8_t i;
 206         for(i=0; i<8; ++i){
 207                 ((uint32_t*)dest)[i] = change_endian32(state->h[i]);
 208         }
 209 #elif BIG_ENDIAN
 210         if (dest != state->h)
 211                 memcpy(dest, state->h, SHA256_HASH_BITS/8);
 212 #else
 213 # error unsupported endian type!
 214 #endif
 215 }
 216
 217 /********************************************************************************************************/
 218 /**
 219  *
 220  *
 221  */
 222 void sha1 (sha1_hash_t *dest, const void* msg, uint32_t length){
 223         sha1_ctx_t s;
 224         DEBUG_S("\r\nBLA BLUB");
 225         sha1_init(&s);
 226         while(length & (~0x0001ff)){ /* length>=512 */
 227                 DEBUG_S("\r\none block");
 228                 sha1_nextBlock(&s, msg);
 229                 msg = (uint8_t*)msg + SHA1_BLOCK_BITS/8; /* increment pointer to next block */
 230                 length -= SHA1_BLOCK_BITS;
 231         }
 232         sha1_lastBlock(&s, msg, length);
 233         sha1_ctx2hash(dest, &s);
 234 }
 235
 236