6.8 Using a Nonce to Protect Against Birthday Attacks

6.8.1 Problem

You want to harden a hash function against birthday attacks instead of switching to an algorithm with a longer digest.

6.8.2 Solution

Use a nonce or salt before and after your message (preferably a securely generated random salt), padding the nonce to the internal block size of the hash function.

6.8.3 Discussion

Hash functions are not secure by themselves—not for a password system, not for message authentication, not for anything! If you do need a hash function by itself, be sure to at least protect against length extension attacks, as described in Recipe 6.7.

In most cases, when using a nonce or salt with a hash function, where the nonce is as large as the output length of the hash function, you double the effective strength of the hash function in circumstances where a birthday attack would apply. Even smaller nonces help improve security.

To ensure the best security, we strongly recommend that you follow these steps:

One thing that you need to be sure to avoid is a situation in which the attacker can control the nonce value. A nonce works well only if it cannot be reused. If an attacker can control the nonce, he can generally guarantee it gets reused, in which case problems like the birthday attack still apply.

In cases where having a nonce that the attacker can't control isn't appropriate, you can probably live with birthday attacks if you're using SHA1 or better. To protect against other attacks without using a nonce, see Recipe 6.7.

All hash functions have a compression function as an element. The size to which that function compresses is the internal block size of the function, and it is usually larger than the actual digest value. For hash functions based on block ciphers, the internal block size is the output length of the hash function (and the compression function is usually built around XOR'ing multiple pieces of block-sized data). Table 6-4 lists the internal block sizes of common message digest functions not based on block ciphers.

Table 6-4. Internal block sizes of common message digest functions

Algorithm	Digest size	Internal block size
MD2	128 bits	16 bytes (128 bits)
MD4	128 bits	64 bytes (512 bits)
MD5	128 bits	64 bytes (512 bits)
RIPEMD-160	160 bits	64 bytes (512 bits)
SHA1	160 bits	64 bytes (512 bits)
SHA-256	256 bits	64 bytes (512 bits)
SHA-384	384 bits	128 bytes (1,024 bits)
SHA-512	512 bits	128 bytes (1,024 bits)

Here's a pair of functions that do all-in-one wrapping of the OpenSSL EVP message digest interface:

#include <openssl/evp.h>
#include <openssl/rand.h>
#include <string.h>
   
unsigned char *spc_create_nonced_digest(EVP_MD *type, unsigned char *in,
                                        unsigned long n, unsigned int *outlen) {
  int           bsz, dlen;
  EVP_MD_CTX    ctx;
  unsigned char *pad, *ret;
   
  EVP_DigestInit(&ctx, type);
  dlen = EVP_MD_CTX_size(&ctx);
  if (!(ret = (unsigned char *)malloc(dlen * 2))) return 0;
  RAND_bytes(ret, dlen);
  EVP_DigestUpdate(&ctx, ret, dlen);
   
  bsz = EVP_MD_CTX_block_size(&ctx);
  if (!(pad = (unsigned char *)malloc(bsz - dlen))) {
    free(ret);
    return 0;
  }
  memset(pad, 0, bsz - dlen);
  EVP_DigestUpdate(&ctx, pad, bsz - dlen);
  EVP_DigestUpdate(&ctx, in, n);
  EVP_DigestUpdate(&ctx, ret, dlen);
  EVP_DigestUpdate(&ctx, pad, bsz - dlen);
  free(pad);
  EVP_DigestFinal(&ctx, ret + dlen, outlen);
  *outlen *= 2;
  return ret;
}
   
int spc_verify_nonced_digest(EVP_MD *type, unsigned char *in, unsigned long n,
                             unsigned char *toverify) {
  int           dlen, outlen, bsz, i;
  EVP_MD_CTX    ctx;
  unsigned char *pad, *vfy;
   
  EVP_DigestInit(&ctx, type);
  bsz  = EVP_MD_CTX_block_size(&ctx);
  dlen = EVP_MD_CTX_size(&ctx);
  EVP_DigestUpdate(&ctx, toverify, dlen);
   
  if (!(pad = (unsigned char *)malloc(bsz - dlen))) return 0;
  memset(pad, 0, bsz - dlen);
  EVP_DigestUpdate(&ctx, pad, bsz - dlen);
  EVP_DigestUpdate(&ctx, in, n);
  EVP_DigestUpdate(&ctx, toverify, dlen);
  EVP_DigestUpdate(&ctx, pad, bsz - dlen);
  free(pad);
   
  if (!(vfy = (unsigned char *)malloc(dlen))) return 0;
  EVP_DigestFinal(&ctx, vfy, &outlen);
  in += dlen;
  for (i = 0;  i < dlen;  i++)
    if (vfy[i] != toverify[i + dlen]) {
      free(vfy);
      return 0;
    }
  free(vfy);
  return 1;
}

The first function, spc_create_nonced_digest( ), automatically selects a nonce from the OpenSSL random number generator and returns twice the digest size in output, where the first digest-sized block is the nonce and the second is the hash. The second function, spc_verify_nonced_digest( ), takes data consisting of a nonce concatenated with a hash value, and returns 1 if the hash validates, and 0 otherwise.

Two macros can make extracting the nonce and the hash easier:

#include <stdio.h>
#include <string.h>
#include <openssl/evp.h>

/* Here, l is the output length of spc_create_nonced_digest(  ) */
#define spc_extract_nonce(l, s)  (s)
#define spc_extract_digest(l, s) ((s)+((l) / 2))

Here's a sample program using this API:

int main(int argc, char *argv[  ]) {
  unsigned int  i, ol;
  unsigned char *s = "Testing hashes with nonces.";
  unsigned char *dgst, *nonce, *ret;
   
  ret   = spc_create_nonced_digest(EVP_sha1(  ), s, strlen(s), &ol);
  nonce = spc_extract_nonce(ol, ret);
  dgst  = spc_extract_digest(ol, ret);
  printf("Nonce = ");
  for(i = 0; i < ol / 2; i++)
    printf("%02x", nonce[i]);
  printf("\nSHA1-Nonced(Nonce, \"%s\") = \n\t", s);
  for(i = 0; i < ol / 2; i++)
    printf("%02x", dgst[i]);
  printf("\n");
  if (spc_verify_nonced_digest(EVP_sha1(  ), s, strlen(s), ret))
    printf("Recalculation verified integrity.\n");
  else
    printf("Recalculation FAILED to match.\n");
    return 0;
}

6.8.4 See Also

Recipe 6.7