Secure Programming Cookbook for C and C++

6.8. Using a Nonce to Protect Against Birthday Attacks

Problem

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

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.

Discussion

Warning

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:

1. Select a nonce using a well-seeded cryptographic random number generator (see Chapter 11). If you’re going to have multiple messages to process, select a random portion that is common to all messages (at least 64 bits) and use a counter for the rest. (The counter should be big enough to handle any possible number of messages. Here we also recommend dedicating at least 64 bits.)

2. Determine the internal block length of the hash function (discussed later in this section).

3. Pad the nonce to the internal block length ...