pintos-os.org Git - openvswitch/blob - lib/sha1.c

   1 /*
   2  * This file is from the Apache Portable Runtime Library.
   3  * The full upstream copyright and license statement is included below.
   4  * Modifications copyright (c) 2009, 2010 Nicira Networks.
   5  */
   6
   7 /* Licensed to the Apache Software Foundation (ASF) under one or more
   8  * contributor license agreements.  See the NOTICE file distributed with
   9  * this work for additional information regarding copyright ownership.
  10  * The ASF licenses this file to You under the Apache License, Version 2.0
  11  * (the "License"); you may not use this file except in compliance with
  12  * the License.  You may obtain a copy of the License at
  13  *
  14  *     http://www.apache.org/licenses/LICENSE-2.0
  15  *
  16  * Unless required by applicable law or agreed to in writing, software
  17  * distributed under the License is distributed on an "AS IS" BASIS,
  18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19  * See the License for the specific language governing permissions and
  20  * limitations under the License.
  21  */
  22
  23 /* This software also makes use of the following component:
  24  *
  25  * NIST Secure Hash Algorithm
  26  *      heavily modified by Uwe Hollerbach uh@alumni.caltech edu
  27  *      from Peter C. Gutmann's implementation as found in
  28  *      Applied Cryptography by Bruce Schneier
  29  *      This code is hereby placed in the public domain
  30  */
  31
  32 #include <config.h>
  33 #include "sha1.h"
  34 #include <ctype.h>
  35 #include <string.h>
  36 #include "compiler.h"
  37 #include "util.h"
  38
  39 /* a bit faster & bigger, if defined */
  40 #define UNROLL_LOOPS
  41
  42 /* SHA f()-functions */
  43 static inline uint32_t
  44 f1(uint32_t x, uint32_t y, uint32_t z)
  45 {
  46     return (x & y) | (~x & z);
  47 }
  48
  49 static inline uint32_t
  50 f2(uint32_t x, uint32_t y, uint32_t z)
  51 {
  52     return x ^ y ^ z;
  53 }
  54
  55 static inline uint32_t
  56 f3(uint32_t x, uint32_t y, uint32_t z)
  57 {
  58     return (x & y) | (x & z) | (y & z);
  59 }
  60
  61 static inline uint32_t
  62 f4(uint32_t x, uint32_t y, uint32_t z)
  63 {
  64     return x ^ y ^ z;
  65 }
  66
  67 /* SHA constants */
  68 #define CONST1          0x5a827999L
  69 #define CONST2          0x6ed9eba1L
  70 #define CONST3          0x8f1bbcdcL
  71 #define CONST4          0xca62c1d6L
  72
  73 /* 32-bit rotate */
  74 static inline uint32_t
  75 rotate32(uint32_t x, int n)
  76 {
  77     return ((x << n) | (x >> (32 - n)));
  78 }
  79
  80 #define FUNC(n, i)                                                      \
  81     do {                                                                \
  82         temp = rotate32(A, 5) + f##n(B, C, D) + E + W[i] + CONST##n;    \
  83         E = D;                                                          \
  84         D = C;                                                          \
  85         C = rotate32(B, 30);                                            \
  86         B = A;                                                          \
  87         A = temp;                                                       \
  88     } while (0)
  89
  90 #define SHA_BLOCK_SIZE           64
  91
  92 /* Do SHA transformation. */
  93 static void
  94 sha_transform(struct sha1_ctx *sha_info)
  95 {
  96     int i;
  97     uint32_t temp, A, B, C, D, E, W[80];
  98
  99     for (i = 0; i < 16; ++i) {
 100         W[i] = sha_info->data[i];
 101     }
 102     for (i = 16; i < 80; ++i) {
 103         W[i] = W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16];
 104         W[i] = rotate32(W[i], 1);
 105     }
 106     A = sha_info->digest[0];
 107     B = sha_info->digest[1];
 108     C = sha_info->digest[2];
 109     D = sha_info->digest[3];
 110     E = sha_info->digest[4];
 111 #ifdef UNROLL_LOOPS
 112     FUNC(1, 0);  FUNC(1, 1);  FUNC(1, 2);  FUNC(1, 3);  FUNC(1, 4);
 113     FUNC(1, 5);  FUNC(1, 6);  FUNC(1, 7);  FUNC(1, 8);  FUNC(1, 9);
 114     FUNC(1,10);  FUNC(1,11);  FUNC(1,12);  FUNC(1,13);  FUNC(1,14);
 115     FUNC(1,15);  FUNC(1,16);  FUNC(1,17);  FUNC(1,18);  FUNC(1,19);
 116
 117     FUNC(2,20);  FUNC(2,21);  FUNC(2,22);  FUNC(2,23);  FUNC(2,24);
 118     FUNC(2,25);  FUNC(2,26);  FUNC(2,27);  FUNC(2,28);  FUNC(2,29);
 119     FUNC(2,30);  FUNC(2,31);  FUNC(2,32);  FUNC(2,33);  FUNC(2,34);
 120     FUNC(2,35);  FUNC(2,36);  FUNC(2,37);  FUNC(2,38);  FUNC(2,39);
 121
 122     FUNC(3,40);  FUNC(3,41);  FUNC(3,42);  FUNC(3,43);  FUNC(3,44);
 123     FUNC(3,45);  FUNC(3,46);  FUNC(3,47);  FUNC(3,48);  FUNC(3,49);
 124     FUNC(3,50);  FUNC(3,51);  FUNC(3,52);  FUNC(3,53);  FUNC(3,54);
 125     FUNC(3,55);  FUNC(3,56);  FUNC(3,57);  FUNC(3,58);  FUNC(3,59);
 126
 127     FUNC(4,60);  FUNC(4,61);  FUNC(4,62);  FUNC(4,63);  FUNC(4,64);
 128     FUNC(4,65);  FUNC(4,66);  FUNC(4,67);  FUNC(4,68);  FUNC(4,69);
 129     FUNC(4,70);  FUNC(4,71);  FUNC(4,72);  FUNC(4,73);  FUNC(4,74);
 130     FUNC(4,75);  FUNC(4,76);  FUNC(4,77);  FUNC(4,78);  FUNC(4,79);
 131 #else /* !UNROLL_LOOPS */
 132     for (i = 0; i < 20; ++i) {
 133         FUNC(1,i);
 134     }
 135     for (i = 20; i < 40; ++i) {
 136         FUNC(2,i);
 137     }
 138     for (i = 40; i < 60; ++i) {
 139         FUNC(3,i);
 140     }
 141     for (i = 60; i < 80; ++i) {
 142         FUNC(4,i);
 143     }
 144 #endif /* !UNROLL_LOOPS */
 145     sha_info->digest[0] += A;
 146     sha_info->digest[1] += B;
 147     sha_info->digest[2] += C;
 148     sha_info->digest[3] += D;
 149     sha_info->digest[4] += E;
 150 }
 151
 152 /* 'count' is the number of bytes to do an endian flip. */
 153 static void
 154 maybe_byte_reverse(uint32_t *buffer OVS_UNUSED, int count OVS_UNUSED)
 155 {
 156 #if !WORDS_BIGENDIAN
 157     int i;
 158     uint8_t ct[4], *cp;
 159
 160         count /= sizeof(uint32_t);
 161         cp = (uint8_t *) buffer;
 162         for (i = 0; i < count; i++) {
 163             ct[0] = cp[0];
 164             ct[1] = cp[1];
 165             ct[2] = cp[2];
 166             ct[3] = cp[3];
 167             cp[0] = ct[3];
 168             cp[1] = ct[2];
 169             cp[2] = ct[1];
 170             cp[3] = ct[0];
 171             cp += sizeof(uint32_t);
 172         }
 173 #endif
 174 }
 175
 176 /*
 177  * Initialize the SHA digest.
 178  * context: The SHA context to initialize
 179  */
 180 void
 181 sha1_init(struct sha1_ctx *sha_info)
 182 {
 183     sha_info->digest[0] = 0x67452301L;
 184     sha_info->digest[1] = 0xefcdab89L;
 185     sha_info->digest[2] = 0x98badcfeL;
 186     sha_info->digest[3] = 0x10325476L;
 187     sha_info->digest[4] = 0xc3d2e1f0L;
 188     sha_info->count_lo = 0L;
 189     sha_info->count_hi = 0L;
 190     sha_info->local = 0;
 191 }
 192
 193 /*
 194  * Update the SHA digest.
 195  * context: The SHA1 context to update.
 196  * input: The buffer to add to the SHA digest.
 197  * inputLen: The length of the input buffer.
 198  */
 199 void
 200 sha1_update(struct sha1_ctx *ctx, const void *buffer_, size_t count)
 201 {
 202     const uint8_t *buffer = buffer_;
 203     unsigned int i;
 204
 205     if ((ctx->count_lo + (count << 3)) < ctx->count_lo) {
 206         ctx->count_hi++;
 207     }
 208     ctx->count_lo += count << 3;
 209     ctx->count_hi += count >> 29;
 210     if (ctx->local) {
 211         i = SHA_BLOCK_SIZE - ctx->local;
 212         if (i > count) {
 213             i = count;
 214         }
 215         memcpy(((uint8_t *) ctx->data) + ctx->local, buffer, i);
 216         count -= i;
 217         buffer += i;
 218         ctx->local += i;
 219         if (ctx->local == SHA_BLOCK_SIZE) {
 220             maybe_byte_reverse(ctx->data, SHA_BLOCK_SIZE);
 221             sha_transform(ctx);
 222         } else {
 223             return;
 224         }
 225     }
 226     while (count >= SHA_BLOCK_SIZE) {
 227         memcpy(ctx->data, buffer, SHA_BLOCK_SIZE);
 228         buffer += SHA_BLOCK_SIZE;
 229         count -= SHA_BLOCK_SIZE;
 230         maybe_byte_reverse(ctx->data, SHA_BLOCK_SIZE);
 231         sha_transform(ctx);
 232     }
 233     memcpy(ctx->data, buffer, count);
 234     ctx->local = count;
 235 }
 236
 237 /*
 238  * Finish computing the SHA digest.
 239  * digest: the output buffer in which to store the digest.
 240  * context: The context to finalize.
 241  */
 242 void
 243 sha1_final(struct sha1_ctx *ctx, uint8_t digest[SHA1_DIGEST_SIZE])
 244 {
 245     int count, i, j;
 246     uint32_t lo_bit_count, hi_bit_count, k;
 247
 248     lo_bit_count = ctx->count_lo;
 249     hi_bit_count = ctx->count_hi;
 250     count = (int) ((lo_bit_count >> 3) & 0x3f);
 251     ((uint8_t *) ctx->data)[count++] = 0x80;
 252     if (count > SHA_BLOCK_SIZE - 8) {
 253         memset(((uint8_t *) ctx->data) + count, 0, SHA_BLOCK_SIZE - count);
 254         maybe_byte_reverse(ctx->data, SHA_BLOCK_SIZE);
 255         sha_transform(ctx);
 256         memset((uint8_t *) ctx->data, 0, SHA_BLOCK_SIZE - 8);
 257     } else {
 258         memset(((uint8_t *) ctx->data) + count, 0,
 259                SHA_BLOCK_SIZE - 8 - count);
 260     }
 261     maybe_byte_reverse(ctx->data, SHA_BLOCK_SIZE);
 262     ctx->data[14] = hi_bit_count;
 263     ctx->data[15] = lo_bit_count;
 264     sha_transform(ctx);
 265
 266     for (i = j = 0; j < SHA1_DIGEST_SIZE; i++) {
 267         k = ctx->digest[i];
 268         digest[j++] = k >> 24;
 269         digest[j++] = k >> 16;
 270         digest[j++] = k >> 8;
 271         digest[j++] = k;
 272     }
 273 }
 274
 275 /* Computes the hash of 'n' bytes in 'data' into 'digest'. */
 276 void
 277 sha1_bytes(const void *data, size_t n, uint8_t digest[SHA1_DIGEST_SIZE])
 278 {
 279     struct sha1_ctx ctx;
 280
 281     sha1_init(&ctx);
 282     sha1_update(&ctx, data, n);
 283     sha1_final(&ctx, digest);
 284 }
 285
 286 void
 287 sha1_to_hex(const uint8_t digest[SHA1_DIGEST_SIZE],
 288             char hex[SHA1_HEX_DIGEST_LEN + 1])
 289 {
 290     int i;
 291
 292     for (i = 0; i < SHA1_DIGEST_SIZE; i++) {
 293         *hex++ = "0123456789abcdef"[digest[i] >> 4];
 294         *hex++ = "0123456789abcdef"[digest[i] & 15];
 295     }
 296     *hex = '\0';
 297 }
 298
 299 bool
 300 sha1_from_hex(uint8_t digest[SHA1_DIGEST_SIZE], const char *hex)
 301 {
 302     int i;
 303
 304     for (i = 0; i < SHA1_DIGEST_SIZE; i++) {
 305         bool ok;
 306
 307         digest[i] = hexits_value(hex, 2, &ok);
 308         if (!ok) {
 309             return false;
 310         }
 311         hex += 2;
 312     }
 313     return true;
 314 }
 315