src/util/crypto_hash.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2009 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 2, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19
  20      SHA-512 code by Jean-Luc Cooke <jlcooke@certainkey.com>
  21
  22      Copyright (c) Jean-Luc Cooke <jlcooke@certainkey.com>
  23      Copyright (c) Andrew McDonald <andrew@mcdonald.org.uk>
  24      Copyright (c) 2003 Kyle McMartin <kyle@debian.org>
  25 */
  26
  27 /**
  28  * @file util/crypto_hash.c
  29  * @brief SHA-512 GNUNET_CRYPTO_hash related functions
  30  * @author Christian Grothoff
  31  */
  32
  33 #include "platform.h"
  34 #include "gnunet_common.h"
  35 #include "gnunet_crypto_lib.h"
  36 #include "gnunet_disk_lib.h"
  37
  38 #define SHA512_DIGEST_SIZE 64
  39 #define SHA512_HMAC_BLOCK_SIZE 128
  40
  41 struct sha512_ctx
  42 {
  43   unsigned long long state[8];
  44   unsigned int count[4];
  45   unsigned char buf[128];
  46 };
  47
  48 static unsigned long long
  49 Ch (unsigned long long x, unsigned long long y, unsigned long long z)
  50 {
  51   return z ^ (x & (y ^ z));
  52 }
  53
  54 static unsigned long long
  55 Maj (unsigned long long x, unsigned long long y, unsigned long long z)
  56 {
  57   return (x & y) | (z & (x | y));
  58 }
  59
  60 static unsigned long long
  61 RORu64 (unsigned long long x, unsigned long long y)
  62 {
  63   return (x >> y) | (x << (64 - y));
  64 }
  65
  66 #define e0(x)       (RORu64(x,28) ^ RORu64(x,34) ^ RORu64(x,39))
  67 #define e1(x)       (RORu64(x,14) ^ RORu64(x,18) ^ RORu64(x,41))
  68 #define s0(x)       (RORu64(x, 1) ^ RORu64(x, 8) ^ (x >> 7))
  69 #define s1(x)       (RORu64(x,19) ^ RORu64(x,61) ^ (x >> 6))
  70
  71 /* H* initial state for SHA-512 */
  72 #define H0         0x6a09e667f3bcc908ULL
  73 #define H1         0xbb67ae8584caa73bULL
  74 #define H2         0x3c6ef372fe94f82bULL
  75 #define H3         0xa54ff53a5f1d36f1ULL
  76 #define H4         0x510e527fade682d1ULL
  77 #define H5         0x9b05688c2b3e6c1fULL
  78 #define H6         0x1f83d9abfb41bd6bULL
  79 #define H7         0x5be0cd19137e2179ULL
  80
  81 /* H'* initial state for SHA-384 */
  82 #define HP0 0xcbbb9d5dc1059ed8ULL
  83 #define HP1 0x629a292a367cd507ULL
  84 #define HP2 0x9159015a3070dd17ULL
  85 #define HP3 0x152fecd8f70e5939ULL
  86 #define HP4 0x67332667ffc00b31ULL
  87 #define HP5 0x8eb44a8768581511ULL
  88 #define HP6 0xdb0c2e0d64f98fa7ULL
  89 #define HP7 0x47b5481dbefa4fa4ULL
  90
  91 #define LOAD_OP(t1, I, W, input) \
  92   t1  = input[(8*I)  ] & 0xff;\
  93   t1 <<= 8;\
  94   t1 |= input[(8*I)+1] & 0xff;\
  95   t1 <<= 8;\
  96   t1 |= input[(8*I)+2] & 0xff;\
  97   t1 <<= 8;\
  98   t1 |= input[(8*I)+3] & 0xff;\
  99   t1 <<= 8;\
 100   t1 |= input[(8*I)+4] & 0xff;\
 101   t1 <<= 8;\
 102   t1 |= input[(8*I)+5] & 0xff;\
 103   t1 <<= 8;\
 104   t1 |= input[(8*I)+6] & 0xff;\
 105   t1 <<= 8;\
 106   t1 |= input[(8*I)+7] & 0xff;\
 107   W[I] = t1;
 108
 109
 110 #define BLEND_OP(I, W) \
 111   W[I] = s1(W[I-2]) + W[I-7] + s0(W[I-15]) + W[I-16];
 112
 113 static void
 114 sha512_transform (unsigned long long *state, const unsigned char *input)
 115 {
 116   static const unsigned long long sha512_K[80] = {
 117     0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL, 0xb5c0fbcfec4d3b2fULL,
 118     0xe9b5dba58189dbbcULL, 0x3956c25bf348b538ULL, 0x59f111f1b605d019ULL,
 119     0x923f82a4af194f9bULL, 0xab1c5ed5da6d8118ULL, 0xd807aa98a3030242ULL,
 120     0x12835b0145706fbeULL, 0x243185be4ee4b28cULL, 0x550c7dc3d5ffb4e2ULL,
 121     0x72be5d74f27b896fULL, 0x80deb1fe3b1696b1ULL, 0x9bdc06a725c71235ULL,
 122     0xc19bf174cf692694ULL, 0xe49b69c19ef14ad2ULL, 0xefbe4786384f25e3ULL,
 123     0x0fc19dc68b8cd5b5ULL, 0x240ca1cc77ac9c65ULL, 0x2de92c6f592b0275ULL,
 124     0x4a7484aa6ea6e483ULL, 0x5cb0a9dcbd41fbd4ULL, 0x76f988da831153b5ULL,
 125     0x983e5152ee66dfabULL, 0xa831c66d2db43210ULL, 0xb00327c898fb213fULL,
 126     0xbf597fc7beef0ee4ULL, 0xc6e00bf33da88fc2ULL, 0xd5a79147930aa725ULL,
 127     0x06ca6351e003826fULL, 0x142929670a0e6e70ULL, 0x27b70a8546d22ffcULL,
 128     0x2e1b21385c26c926ULL, 0x4d2c6dfc5ac42aedULL, 0x53380d139d95b3dfULL,
 129     0x650a73548baf63deULL, 0x766a0abb3c77b2a8ULL, 0x81c2c92e47edaee6ULL,
 130     0x92722c851482353bULL, 0xa2bfe8a14cf10364ULL, 0xa81a664bbc423001ULL,
 131     0xc24b8b70d0f89791ULL, 0xc76c51a30654be30ULL, 0xd192e819d6ef5218ULL,
 132     0xd69906245565a910ULL, 0xf40e35855771202aULL, 0x106aa07032bbd1b8ULL,
 133     0x19a4c116b8d2d0c8ULL, 0x1e376c085141ab53ULL, 0x2748774cdf8eeb99ULL,
 134     0x34b0bcb5e19b48a8ULL, 0x391c0cb3c5c95a63ULL, 0x4ed8aa4ae3418acbULL,
 135     0x5b9cca4f7763e373ULL, 0x682e6ff3d6b2b8a3ULL, 0x748f82ee5defb2fcULL,
 136     0x78a5636f43172f60ULL, 0x84c87814a1f0ab72ULL, 0x8cc702081a6439ecULL,
 137     0x90befffa23631e28ULL, 0xa4506cebde82bde9ULL, 0xbef9a3f7b2c67915ULL,
 138     0xc67178f2e372532bULL, 0xca273eceea26619cULL, 0xd186b8c721c0c207ULL,
 139     0xeada7dd6cde0eb1eULL, 0xf57d4f7fee6ed178ULL, 0x06f067aa72176fbaULL,
 140     0x0a637dc5a2c898a6ULL, 0x113f9804bef90daeULL, 0x1b710b35131c471bULL,
 141     0x28db77f523047d84ULL, 0x32caab7b40c72493ULL, 0x3c9ebe0a15c9bebcULL,
 142     0x431d67c49c100d4cULL, 0x4cc5d4becb3e42b6ULL, 0x597f299cfc657e2aULL,
 143     0x5fcb6fab3ad6faecULL, 0x6c44198c4a475817ULL,
 144   };
 145
 146   unsigned long long a, b, c, d, e, f, g, h, t1, t2;
 147   unsigned long long W[80];
 148   unsigned long long t0;
 149   int i;
 150
 151   /* load the input */
 152   for (i = 0; i < 16; i++)
 153     {
 154       LOAD_OP (t0, i, W, input);
 155     }
 156
 157   for (i = 16; i < 80; i++)
 158     {
 159       BLEND_OP (i, W);
 160     }
 161
 162   /* load the state into our registers */
 163   a = state[0];
 164   b = state[1];
 165   c = state[2];
 166   d = state[3];
 167   e = state[4];
 168   f = state[5];
 169   g = state[6];
 170   h = state[7];
 171
 172   /* now iterate */
 173   for (i = 0; i < 80; i += 8)
 174     {
 175       t1 = h + e1 (e) + Ch (e, f, g) + sha512_K[i] + W[i];
 176       t2 = e0 (a) + Maj (a, b, c);
 177       d += t1;
 178       h = t1 + t2;
 179       t1 = g + e1 (d) + Ch (d, e, f) + sha512_K[i + 1] + W[i + 1];
 180       t2 = e0 (h) + Maj (h, a, b);
 181       c += t1;
 182       g = t1 + t2;
 183       t1 = f + e1 (c) + Ch (c, d, e) + sha512_K[i + 2] + W[i + 2];
 184       t2 = e0 (g) + Maj (g, h, a);
 185       b += t1;
 186       f = t1 + t2;
 187       t1 = e + e1 (b) + Ch (b, c, d) + sha512_K[i + 3] + W[i + 3];
 188       t2 = e0 (f) + Maj (f, g, h);
 189       a += t1;
 190       e = t1 + t2;
 191       t1 = d + e1 (a) + Ch (a, b, c) + sha512_K[i + 4] + W[i + 4];
 192       t2 = e0 (e) + Maj (e, f, g);
 193       h += t1;
 194       d = t1 + t2;
 195       t1 = c + e1 (h) + Ch (h, a, b) + sha512_K[i + 5] + W[i + 5];
 196       t2 = e0 (d) + Maj (d, e, f);
 197       g += t1;
 198       c = t1 + t2;
 199       t1 = b + e1 (g) + Ch (g, h, a) + sha512_K[i + 6] + W[i + 6];
 200       t2 = e0 (c) + Maj (c, d, e);
 201       f += t1;
 202       b = t1 + t2;
 203       t1 = a + e1 (f) + Ch (f, g, h) + sha512_K[i + 7] + W[i + 7];
 204       t2 = e0 (b) + Maj (b, c, d);
 205       e += t1;
 206       a = t1 + t2;
 207     }
 208
 209   state[0] += a;
 210   state[1] += b;
 211   state[2] += c;
 212   state[3] += d;
 213   state[4] += e;
 214   state[5] += f;
 215   state[6] += g;
 216   state[7] += h;
 217 }
 218
 219 static void
 220 sha512_init (struct sha512_ctx *sctx)
 221 {
 222   sctx->state[0] = H0;
 223   sctx->state[1] = H1;
 224   sctx->state[2] = H2;
 225   sctx->state[3] = H3;
 226   sctx->state[4] = H4;
 227   sctx->state[5] = H5;
 228   sctx->state[6] = H6;
 229   sctx->state[7] = H7;
 230   sctx->count[0] = sctx->count[1] = sctx->count[2] = sctx->count[3] = 0;
 231   memset (sctx->buf, 0, sizeof (sctx->buf));
 232 }
 233
 234 static void
 235 sha512_update (struct sha512_ctx *sctx,
 236                const unsigned char *data, unsigned int len)
 237 {
 238   unsigned int i, index, part_len;
 239
 240   /* Compute number of bytes mod 128 */
 241   index = (unsigned int) ((sctx->count[0] >> 3) & 0x7F);
 242
 243   /* Update number of bits */
 244   if ((sctx->count[0] += (len << 3)) < (len << 3))
 245     {
 246       if ((sctx->count[1] += 1) < 1)
 247         if ((sctx->count[2] += 1) < 1)
 248           sctx->count[3]++;
 249       sctx->count[1] += (len >> 29);
 250     }
 251
 252   part_len = 128 - index;
 253
 254   /* Transform as many times as possible. */
 255   if (len >= part_len)
 256     {
 257       memcpy (&sctx->buf[index], data, part_len);
 258       sha512_transform (sctx->state, sctx->buf);
 259
 260       for (i = part_len; i + 127 < len; i += 128)
 261         sha512_transform (sctx->state, &data[i]);
 262
 263       index = 0;
 264     }
 265   else
 266     {
 267       i = 0;
 268     }
 269
 270   /* Buffer remaining input */
 271   memcpy (&sctx->buf[index], &data[i], len - i);
 272 }
 273
 274 static void
 275 sha512_final (struct sha512_ctx *sctx, unsigned char *hash)
 276 {
 277   static unsigned char padding[128] = { 0x80, };
 278
 279   unsigned int t;
 280   unsigned char bits[128];
 281   unsigned int index;
 282   unsigned int pad_len;
 283   unsigned long long t2;
 284   int i, j;
 285
 286   /* Save number of bits */
 287   t = sctx->count[0];
 288   bits[15] = t;
 289   t >>= 8;
 290   bits[14] = t;
 291   t >>= 8;
 292   bits[13] = t;
 293   t >>= 8;
 294   bits[12] = t;
 295   t = sctx->count[1];
 296   bits[11] = t;
 297   t >>= 8;
 298   bits[10] = t;
 299   t >>= 8;
 300   bits[9] = t;
 301   t >>= 8;
 302   bits[8] = t;
 303   t = sctx->count[2];
 304   bits[7] = t;
 305   t >>= 8;
 306   bits[6] = t;
 307   t >>= 8;
 308   bits[5] = t;
 309   t >>= 8;
 310   bits[4] = t;
 311   t = sctx->count[3];
 312   bits[3] = t;
 313   t >>= 8;
 314   bits[2] = t;
 315   t >>= 8;
 316   bits[1] = t;
 317   t >>= 8;
 318   bits[0] = t;
 319
 320   /* Pad out to 112 mod 128. */
 321   index = (sctx->count[0] >> 3) & 0x7f;
 322   pad_len = (index < 112) ? (112 - index) : ((128 + 112) - index);
 323   sha512_update (sctx, padding, pad_len);
 324
 325   /* Append length (before padding) */
 326   sha512_update (sctx, bits, 16);
 327
 328   /* Store state in digest */
 329   for (i = j = 0; i < 8; i++, j += 8)
 330     {
 331       t2 = sctx->state[i];
 332       hash[j + 7] = (char) t2 & 0xff;
 333       t2 >>= 8;
 334       hash[j + 6] = (char) t2 & 0xff;
 335       t2 >>= 8;
 336       hash[j + 5] = (char) t2 & 0xff;
 337       t2 >>= 8;
 338       hash[j + 4] = (char) t2 & 0xff;
 339       t2 >>= 8;
 340       hash[j + 3] = (char) t2 & 0xff;
 341       t2 >>= 8;
 342       hash[j + 2] = (char) t2 & 0xff;
 343       t2 >>= 8;
 344       hash[j + 1] = (char) t2 & 0xff;
 345       t2 >>= 8;
 346       hash[j] = (char) t2 & 0xff;
 347     }
 348
 349   /* Zeroize sensitive information. */
 350   memset (sctx, 0, sizeof (struct sha512_ctx));
 351 }
 352
 353
 354 /**
 355  * Hash block of given size.
 356  *
 357  * @param block the data to GNUNET_CRYPTO_hash, length is given as a second argument
 358  * @param size the length of the data to GNUNET_CRYPTO_hash
 359  * @param ret pointer to where to write the hashcode
 360  */
 361 void
 362 GNUNET_CRYPTO_hash (const void *block, size_t size, GNUNET_HashCode * ret)
 363 {
 364   struct sha512_ctx ctx;
 365
 366   sha512_init (&ctx);
 367   sha512_update (&ctx, block, size);
 368   sha512_final (&ctx, (unsigned char *) ret);
 369 }
 370
 371
 372 /**
 373  * Context used when hashing a file.
 374  */
 375 struct GNUNET_CRYPTO_FileHashContext
 376 {
 377
 378   /**
 379    * Function to call upon completion.
 380    */
 381   GNUNET_CRYPTO_HashCompletedCallback callback;
 382
 383   /**
 384    * Closure for callback.
 385    */
 386   void *callback_cls;
 387
 388   /**
 389    * IO buffer.
 390    */
 391   unsigned char *buffer;
 392
 393   /**
 394    * Name of the file we are hashing.
 395    */
 396   char *filename;
 397
 398   /**
 399    * File descriptor.
 400    */
 401   struct GNUNET_DISK_FileHandle *fh;
 402
 403   /**
 404    * Our scheduler.
 405    */
 406   struct GNUNET_SCHEDULER_Handle *sched;
 407
 408   /**
 409    * Cummulated hash.
 410    */
 411   struct sha512_ctx hctx;
 412
 413   /**
 414    * Size of the file.
 415    */
 416   uint64_t fsize;
 417
 418   /**
 419    * Current offset.
 420    */
 421   uint64_t offset;
 422
 423   /**
 424    * Current task for hashing.
 425    */
 426   GNUNET_SCHEDULER_TaskIdentifier task;
 427
 428   /**
 429    * Blocksize.
 430    */
 431   size_t bsize;
 432
 433 };
 434
 435
 436 /**
 437  * Report result of hash computation to callback
 438  * and free associated resources.
 439  */
 440 static void
 441 file_hash_finish (struct GNUNET_CRYPTO_FileHashContext *fhc,
 442                   const GNUNET_HashCode * res)
 443 {
 444   fhc->callback (fhc->callback_cls, res);
 445   GNUNET_free (fhc->filename);
 446   if (!GNUNET_DISK_handle_invalid (fhc->fh))
 447     GNUNET_break (GNUNET_OK == GNUNET_DISK_file_close (fhc->fh));
 448   GNUNET_free (fhc);            /* also frees fhc->buffer */
 449 }
 450
 451
 452 /**
 453  * File hashing task.
 454  *
 455  * @param cls closure
 456  * @param tc context
 457  */
 458 static void
 459 file_hash_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 460 {
 461   struct GNUNET_CRYPTO_FileHashContext *fhc = cls;
 462   GNUNET_HashCode res;
 463   size_t delta;
 464
 465   fhc->task = GNUNET_SCHEDULER_NO_TASK;
 466   GNUNET_assert (fhc->offset < fhc->fsize);
 467   delta = fhc->bsize;
 468   if (fhc->fsize - fhc->offset < delta)
 469     delta = fhc->fsize - fhc->offset;
 470   if (delta != GNUNET_DISK_file_read (fhc->fh, fhc->buffer, delta))
 471     {
 472       GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING,
 473                                 "read", fhc->filename);
 474       file_hash_finish (fhc, NULL);
 475       return;
 476     }
 477   sha512_update (&fhc->hctx, fhc->buffer, delta);
 478   fhc->offset += delta;
 479   if (fhc->offset == fhc->fsize)
 480     {
 481       sha512_final (&fhc->hctx, (unsigned char *) &res);
 482       file_hash_finish (fhc, &res);
 483       return;
 484     }
 485   fhc->task
 486     = GNUNET_SCHEDULER_add_after (tc->sched,
 487                                   GNUNET_SCHEDULER_NO_TASK,
 488                                   &file_hash_task, fhc);
 489 }
 490
 491
 492 /**
 493  * Compute the hash of an entire file.
 494  *
 495  * @param sched scheduler to use
 496  * @param priority scheduling priority to use
 497  * @param filename name of file to hash
 498  * @param blocksize number of bytes to process in one task
 499  * @param callback function to call upon completion
 500  * @param callback_cls closure for callback
 501  * @return NULL on (immediate) errror
 502  */
 503 struct GNUNET_CRYPTO_FileHashContext *
 504 GNUNET_CRYPTO_hash_file (struct GNUNET_SCHEDULER_Handle *sched,
 505                          enum GNUNET_SCHEDULER_Priority priority,
 506                          const char *filename,
 507                          size_t blocksize,
 508                          GNUNET_CRYPTO_HashCompletedCallback callback,
 509                          void *callback_cls)
 510 {
 511   struct GNUNET_CRYPTO_FileHashContext *fhc;
 512
 513   GNUNET_assert (blocksize > 0);
 514   fhc = GNUNET_malloc (sizeof (struct GNUNET_CRYPTO_FileHashContext) + blocksize);
 515   fhc->callback = callback;
 516   fhc->callback_cls = callback_cls;
 517   fhc->sched = sched;
 518   fhc->buffer = (unsigned char *) &fhc[1];
 519   fhc->filename = GNUNET_strdup (filename);
 520   fhc->fh = NULL;
 521   sha512_init (&fhc->hctx);
 522   fhc->bsize = blocksize;
 523   if (GNUNET_OK != GNUNET_DISK_file_size (filename, &fhc->fsize, GNUNET_NO))
 524     {
 525       GNUNET_free (fhc->filename);
 526       GNUNET_free (fhc);
 527       return NULL;
 528     }
 529   fhc->fh = GNUNET_DISK_file_open (filename,
 530                                    GNUNET_DISK_OPEN_READ,
 531                                    GNUNET_DISK_PERM_NONE);
 532   if (!fhc->fh)
 533     {
 534       GNUNET_free (fhc->filename);
 535       GNUNET_free (fhc);
 536       return NULL;
 537     }
 538   fhc->task
 539     = GNUNET_SCHEDULER_add_with_priority (sched, priority,
 540                                           &file_hash_task, fhc);
 541   return fhc;
 542 }
 543
 544
 545 /**
 546  * Cancel a file hashing operation.
 547  *
 548  * @param fhc operation to cancel (callback must not yet have been invoked)
 549  */
 550 void
 551 GNUNET_CRYPTO_hash_file_cancel (struct GNUNET_CRYPTO_FileHashContext *fhc)
 552 {
 553   GNUNET_SCHEDULER_cancel (fhc->sched,
 554                            fhc->task);
 555   GNUNET_free (fhc->filename);
 556   GNUNET_break (GNUNET_OK == GNUNET_DISK_file_close (fhc->fh));
 557   GNUNET_free (fhc);
 558 }
 559
 560
 561
 562 /* ***************** binary-ASCII encoding *************** */
 563
 564 static unsigned int
 565 getValue__ (unsigned char a)
 566 {
 567   if ((a >= '0') && (a <= '9'))
 568     return a - '0';
 569   if ((a >= 'A') && (a <= 'V'))
 570     return (a - 'A' + 10);
 571   return -1;
 572 }
 573
 574 /**
 575  * Convert GNUNET_CRYPTO_hash to ASCII encoding.  The ASCII encoding is rather
 576  * GNUnet specific.  It was chosen such that it only uses characters
 577  * in [0-9A-V], can be produced without complex arithmetics and uses a
 578  * small number of characters.  The GNUnet encoding uses 102
 579  * characters plus a null terminator.
 580  *
 581  * @param block the hash code
 582  * @param result where to store the encoding (struct GNUNET_CRYPTO_HashAsciiEncoded can be
 583  *  safely cast to char*, a '\\0' termination is set).
 584  */
 585 void
 586 GNUNET_CRYPTO_hash_to_enc (const GNUNET_HashCode * block,
 587                            struct GNUNET_CRYPTO_HashAsciiEncoded *result)
 588 {
 589   /**
 590    * 32 characters for encoding (GNUNET_CRYPTO_hash => 32 characters)
 591    */
 592   static char *encTable__ = "0123456789ABCDEFGHIJKLMNOPQRSTUV";
 593   unsigned int wpos;
 594   unsigned int rpos;
 595   unsigned int bits;
 596   unsigned int vbit;
 597
 598   GNUNET_assert (block != NULL);
 599   GNUNET_assert (result != NULL);
 600   vbit = 0;
 601   wpos = 0;
 602   rpos = 0;
 603   bits = 0;
 604   while ((rpos < sizeof (GNUNET_HashCode)) || (vbit > 0))
 605     {
 606       if ((rpos < sizeof (GNUNET_HashCode)) && (vbit < 5))
 607         {
 608           bits = (bits << 8) | ((unsigned char *) block)[rpos++];       /* eat 8 more bits */
 609           vbit += 8;
 610         }
 611       if (vbit < 5)
 612         {
 613           bits <<= (5 - vbit);  /* zero-padding */
 614           GNUNET_assert (vbit == 2);    /* padding by 3: 512+3 mod 5 == 0 */
 615           vbit = 5;
 616         }
 617       GNUNET_assert (wpos <
 618                      sizeof (struct GNUNET_CRYPTO_HashAsciiEncoded) - 1);
 619       result->encoding[wpos++] = encTable__[(bits >> (vbit - 5)) & 31];
 620       vbit -= 5;
 621     }
 622   GNUNET_assert (wpos == sizeof (struct GNUNET_CRYPTO_HashAsciiEncoded) - 1);
 623   GNUNET_assert (vbit == 0);
 624   result->encoding[wpos] = '\0';
 625 }
 626
 627 /**
 628  * Convert ASCII encoding back to GNUNET_CRYPTO_hash
 629  *
 630  * @param enc the encoding
 631  * @param result where to store the GNUNET_CRYPTO_hash code
 632  * @return GNUNET_OK on success, GNUNET_SYSERR if result has the wrong encoding
 633  */
 634 int
 635 GNUNET_CRYPTO_hash_from_string (const char *enc, GNUNET_HashCode * result)
 636 {
 637   unsigned int rpos;
 638   unsigned int wpos;
 639   unsigned int bits;
 640   unsigned int vbit;
 641
 642   if (strlen (enc) != sizeof (struct GNUNET_CRYPTO_HashAsciiEncoded) - 1)
 643     return GNUNET_SYSERR;
 644
 645   vbit = 2;                     /* padding! */
 646   wpos = sizeof (GNUNET_HashCode);
 647   rpos = sizeof (struct GNUNET_CRYPTO_HashAsciiEncoded) - 1;
 648   bits = getValue__ (enc[--rpos]) >> 3;
 649   while (wpos > 0)
 650     {
 651       GNUNET_assert (rpos > 0);
 652       bits = (getValue__ (enc[--rpos]) << vbit) | bits;
 653       vbit += 5;
 654       if (vbit >= 8)
 655         {
 656           ((unsigned char *) result)[--wpos] = (unsigned char) bits;
 657           bits >>= 8;
 658           vbit -= 8;
 659         }
 660     }
 661   GNUNET_assert (rpos == 0);
 662   GNUNET_assert (vbit == 0);
 663   return GNUNET_OK;
 664 }
 665
 666 /**
 667  * Compute the distance between 2 hashcodes.  The computation must be
 668  * fast, not involve bits[0] or bits[4] (they're used elsewhere), and be
 669  * somewhat consistent. And of course, the result should be a positive
 670  * number.
 671  *
 672  * @param a some hash code
 673  * @param b some hash code
 674  * @return a positive number which is a measure for
 675  *  hashcode proximity.
 676  */
 677 unsigned int
 678 GNUNET_CRYPTO_hash_distance_u32 (const GNUNET_HashCode * a,
 679                                  const GNUNET_HashCode * b)
 680 {
 681   unsigned int x1 = (a->bits[1] - b->bits[1]) >> 16;
 682   unsigned int x2 = (b->bits[1] - a->bits[1]) >> 16;
 683   return (x1 * x2);
 684 }
 685
 686 void
 687 GNUNET_CRYPTO_hash_create_random (enum GNUNET_CRYPTO_Quality mode,
 688                                   GNUNET_HashCode * result)
 689 {
 690   int i;
 691   for (i = (sizeof (GNUNET_HashCode) / sizeof (uint32_t)) - 1; i >= 0; i--)
 692     result->bits[i] = GNUNET_CRYPTO_random_u32 (mode, UINT32_MAX);
 693 }
 694
 695 void
 696 GNUNET_CRYPTO_hash_difference (const GNUNET_HashCode * a,
 697                                const GNUNET_HashCode * b,
 698                                GNUNET_HashCode * result)
 699 {
 700   int i;
 701   for (i = (sizeof (GNUNET_HashCode) / sizeof (unsigned int)) - 1; i >= 0;
 702        i--)
 703     result->bits[i] = b->bits[i] - a->bits[i];
 704 }
 705
 706 void
 707 GNUNET_CRYPTO_hash_sum (const GNUNET_HashCode * a,
 708                         const GNUNET_HashCode * delta,
 709                         GNUNET_HashCode * result)
 710 {
 711   int i;
 712   for (i = (sizeof (GNUNET_HashCode) / sizeof (unsigned int)) - 1; i >= 0;
 713        i--)
 714     result->bits[i] = delta->bits[i] + a->bits[i];
 715 }
 716
 717 void
 718 GNUNET_CRYPTO_hash_xor (const GNUNET_HashCode * a,
 719                         const GNUNET_HashCode * b, GNUNET_HashCode * result)
 720 {
 721   int i;
 722   for (i = (sizeof (GNUNET_HashCode) / sizeof (unsigned int)) - 1; i >= 0;
 723        i--)
 724     result->bits[i] = a->bits[i] ^ b->bits[i];
 725 }
 726
 727 /**
 728  * Convert a hashcode into a key.
 729  */
 730 void
 731 GNUNET_CRYPTO_hash_to_aes_key (const GNUNET_HashCode * hc,
 732                                struct GNUNET_CRYPTO_AesSessionKey *skey,
 733                                struct GNUNET_CRYPTO_AesInitializationVector
 734                                *iv)
 735 {
 736   GNUNET_assert (sizeof (GNUNET_HashCode) >=
 737                  GNUNET_CRYPTO_AES_KEY_LENGTH +
 738                  sizeof (struct GNUNET_CRYPTO_AesInitializationVector));
 739   memcpy (skey, hc, GNUNET_CRYPTO_AES_KEY_LENGTH);
 740   skey->crc32 =
 741     htonl (GNUNET_CRYPTO_crc32_n (skey, GNUNET_CRYPTO_AES_KEY_LENGTH));
 742   memcpy (iv, &((char *) hc)[GNUNET_CRYPTO_AES_KEY_LENGTH],
 743           sizeof (struct GNUNET_CRYPTO_AesInitializationVector));
 744 }
 745
 746 /**
 747  * Obtain a bit from a hashcode.
 748  * @param code the GNUNET_CRYPTO_hash to index bit-wise
 749  * @param bit index into the hashcode, [0...511]
 750  * @return Bit \a bit from hashcode \a code, -1 for invalid index
 751  */
 752 int
 753 GNUNET_CRYPTO_hash_get_bit (const GNUNET_HashCode * code, unsigned int bit)
 754 {
 755   GNUNET_assert (bit < 8 * sizeof (GNUNET_HashCode));
 756   return (((unsigned char *) code)[bit >> 3] & (1 << (bit & 7))) > 0;
 757 }
 758
 759 /**
 760  * Determine how many low order bits match in two
 761  * GNUNET_HashCodes.  i.e. - 010011 and 011111 share
 762  * the first two lowest order bits, and therefore the
 763  * return value is two (NOT XOR distance, nor how many
 764  * bits match absolutely!).
 765  *
 766  * @param first the first hashcode
 767  * @param second the hashcode to compare first to
 768  *
 769  * @return the number of bits that match
 770  */
 771 unsigned int GNUNET_CRYPTO_hash_matching_bits(const GNUNET_HashCode *first, const GNUNET_HashCode *second)
 772 {
 773   unsigned int i;
 774
 775   for (i = 0; i < sizeof (GNUNET_HashCode) * 8; i++)
 776     if (GNUNET_CRYPTO_hash_get_bit (first, i) != GNUNET_CRYPTO_hash_get_bit (second, i))
 777       return i;
 778   return sizeof (GNUNET_HashCode) * 8;
 779 }
 780
 781 /**
 782  * Compare function for HashCodes, producing a total ordering
 783  * of all hashcodes.
 784  * @return 1 if h1 > h2, -1 if h1 < h2 and 0 if h1 == h2.
 785  */
 786 int
 787 GNUNET_CRYPTO_hash_cmp (const GNUNET_HashCode * h1,
 788                         const GNUNET_HashCode * h2)
 789 {
 790   unsigned int *i1;
 791   unsigned int *i2;
 792   int i;
 793
 794   i1 = (unsigned int *) h1;
 795   i2 = (unsigned int *) h2;
 796   for (i = (sizeof (GNUNET_HashCode) / sizeof (unsigned int)) - 1; i >= 0;
 797        i--)
 798     {
 799       if (i1[i] > i2[i])
 800         return 1;
 801       if (i1[i] < i2[i])
 802         return -1;
 803     }
 804   return 0;
 805 }
 806
 807 /**
 808  * Find out which of the two GNUNET_CRYPTO_hash codes is closer to target
 809  * in the XOR metric (Kademlia).
 810  * @return -1 if h1 is closer, 1 if h2 is closer and 0 if h1==h2.
 811  */
 812 int
 813 GNUNET_CRYPTO_hash_xorcmp (const GNUNET_HashCode * h1,
 814                            const GNUNET_HashCode * h2,
 815                            const GNUNET_HashCode * target)
 816 {
 817   int i;
 818   unsigned int d1;
 819   unsigned int d2;
 820
 821   for (i = sizeof (GNUNET_HashCode) / sizeof (unsigned int) - 1; i >= 0; i--)
 822     {
 823       d1 = ((unsigned int *) h1)[i] ^ ((unsigned int *) target)[i];
 824       d2 = ((unsigned int *) h2)[i] ^ ((unsigned int *) target)[i];
 825       if (d1 > d2)
 826         return 1;
 827       else if (d1 < d2)
 828         return -1;
 829     }
 830   return 0;
 831 }
 832
 833
 834 /**
 835  * @brief Derive an authentication key
 836  * @param key authentication key
 837  * @param rkey root key
 838  * @param salt salt
 839  * @param salt_len size of the salt
 840  * @param ... pair of void * & size_t for context chunks, terminated by NULL
 841  */
 842 void
 843 GNUNET_CRYPTO_hmac_derive_key(struct GNUNET_CRYPTO_AuthKey *key,
 844                               const struct GNUNET_CRYPTO_AesSessionKey *rkey,
 845                               const void *salt,
 846                               const size_t salt_len,
 847                               ...)
 848 {
 849   va_list argp;
 850
 851   va_start (argp, salt_len);
 852   GNUNET_CRYPTO_hmac_derive_key_v (key, rkey, salt, salt_len, argp);
 853   va_end (argp);
 854 }
 855
 856
 857 /**
 858  * @brief Derive an authentication key
 859  * @param key authentication key
 860  * @param rkey root key
 861  * @param salt salt
 862  * @param salt_len size of the salt
 863  * @param argp pair of void * & size_t for context chunks, terminated by NULL
 864  */
 865 void
 866 GNUNET_CRYPTO_hmac_derive_key_v(struct GNUNET_CRYPTO_AuthKey *key,
 867                                 const struct GNUNET_CRYPTO_AesSessionKey *rkey,
 868                                 const void *salt,
 869                                 const size_t salt_len,
 870                                 const va_list argp)
 871 {
 872   GNUNET_CRYPTO_kdf_v (key->key, sizeof(key->key), salt, salt_len, rkey->key,
 873       sizeof(rkey->key), argp);
 874 }
 875
 876 /**
 877  * Calculate HMAC of a message (RFC 2104)
 878  *
 879  * @param key secret key
 880  * @param plaintext input plaintext
 881  * @param plaintext_len length of plaintext
 882  * @param hmac where to store the hmac
 883  */
 884 void
 885 GNUNET_CRYPTO_hmac (const struct GNUNET_CRYPTO_AuthKey *key,
 886                     const void *plaintext,
 887                     size_t plaintext_len,
 888                     GNUNET_HashCode *hmac)
 889 {
 890   GNUNET_HashCode kh;
 891   GNUNET_HashCode ipad;
 892   GNUNET_HashCode opad;
 893   GNUNET_HashCode him;
 894   struct sha512_ctx sctx;
 895
 896   memset (&kh, 0, sizeof (kh));
 897   memcpy (&kh, key->key, sizeof (struct GNUNET_CRYPTO_AuthKey));
 898   memset (&ipad, 0x5c, sizeof (ipad));
 899   memset (&opad, 0x36, sizeof (opad));
 900   GNUNET_CRYPTO_hash_xor (&ipad, &kh, &ipad);
 901   GNUNET_CRYPTO_hash_xor (&opad, &kh, &opad);
 902   sha512_init (&sctx);
 903   sha512_update (&sctx, (const unsigned char*) &ipad, sizeof (ipad));
 904   sha512_update (&sctx, plaintext, plaintext_len);
 905   sha512_final (&sctx, (unsigned char*) &him);
 906   sha512_init (&sctx);
 907   sha512_update (&sctx, (const unsigned char*) &opad, sizeof (opad));
 908   sha512_update (&sctx, (const unsigned char*) &him, sizeof (him));
 909   sha512_final (&sctx, (unsigned char*) hmac);
 910 }
 911
 912
 913 /* end of crypto_hash.c */