2
\$\begingroup\$

I need to create unique nonces for cryptographic purposes in a library that I am writing. If the nonces ever fail to be unique, the consequences may be up to and including remote execution of arbitrary code (by means of allowing injection of untrusted input into an unmarshalling operation).

While my particular application does not need to be thread-safe yet, I want the code to be thread-safe so that it can work in multithreaded applications without modification. I also want it to be fairly efficient – more so than (say) using a global lock for every operation.

The code has not (yet) been tested, mostly because I have no idea how to write a test case for multi-threaded (and mostly lock-free) code. It makes the assumption that all thread-local storage is initialized to zero when a new thread is created – otherwise, it will fail miserably.

The header file nonce.h:

#ifndef NONCE_H_INCLUDED
#define NONCE_H_INCLUDED NONCE_H_INCLUDED
#pragma once
#ifdef __cplusplus
extern "C" {
#elif 0
}
#endif

typedef struct {
   char nonce[12];
} nonce;

nonce generate_new_nonce(void);

#if 0
{
#elif defined __cplusplus
}
#endif // defined __cplusplus

#endif // !defined NONCE_H_INCLUDED

And the implementation file nonce.c:

#include "nonce.h"
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define STATIC_ASSERT(x)                                \
   (0*sizeof(struct {                                   \
      int static_assertion_failed : 1 - 2*((int)!(x)); \
      int dummy: 31;                                    \
   }))

static __thread uint32_t local_counter;
static __thread uint64_t local_snapshot;
static uint64_t global_counter;
static uintptr_t lock;

static uint64_t get_new_snapshot(void);

#ifdef __cplusplus
extern "C"
#endif
nonce generate_new_nonce(void) {
   STATIC_ASSERT(sizeof(local_counter) == 4);
   STATIC_ASSERT(sizeof(local_snapshot) == 8);
   STATIC_ASSERT(sizeof(global_counter) == 8);
   nonce retval;
   if (0 == local_counter) {
      local_snapshot = get_new_snapshot();
   }
   memcpy(retval.nonce, &local_counter, sizeof local_counter);
   memcpy(retval.nonce + 4, &local_snapshot, sizeof local_snapshot);
   local_counter += 1;
   return retval;
}

static uint64_t get_new_snapshot(void) {
   while(__sync_lock_test_and_set(&lock, 1)) {}
   const uint64_t retval = global_counter;
   global_counter++;
   if (global_counter == 0) {
      /* Wraparound */
      abort();
   }
   __sync_lock_release(&lock);
   return retval;
}
\$\endgroup\$
3
\$\begingroup\$

If all you do in your lock is global_counter++ you may as well make it a c++11 atomic, and just write local_counter = global_counter++.

Or, using what you've used so far, local_counter = __sync_fetch_and_add(&global_counter,1)

You may drop the wraparound check. You can increment once per nanosecond and it'd flip in a few hundred years.

After all that's been said in the comments I'm pretty much convinced there are no simple (read: 3 lines of code) solutions given 4g threads will get created and we have only 32 bit atomics.

There are 3 valid solutions:

  1. Stay with the mutex. I guess if you're spending the time to create a thread, it's not the end of the world to lock a mutex once per the thread's lifetime.

  2. Reuse those threads so you never get to 4g. Maybe you can not coz your client's app created them?

  3. Reuse the nonce ranges. Having so many threads means most of them exit way before they consume the 64bit range per 32bit snapshot.
    Now, you can have a destructor on the TLS entry of the snapshot. Lookup pthread_key_create.
    You can use this destructor to push the current snapshot and counter into a lock free stack and pop them out in get_new_snapshot.
    You can init that array/stack with 1000 nonce ranges (999,0), (998,0),... (0,0)
    The first thread would pop (0,0). When it exits it'd push back whatever it got to. Say (0,122283).
    If a thread ever consumes it's 64bit range of nonces (if your app runs for a millennia) it can pop another range.
    You can pre-allocate a stack large enough for as many concurrent threads as you like. If it's ever consumed default to dynamically allocating more ranges. But this would would probably never get executed.

I can give more detail about a pre-allocated lock free stack, if you like.

\$\endgroup\$
  • \$\begingroup\$ I wrote the code as-is to be portable to 32 bit systems, where 64 bit atomics might not be available. \$\endgroup\$ – Demi Sep 6 '16 at 5:51
  • \$\begingroup\$ You don't need 64 bit atomics. For a 12 byte nonce you can use a thread-local uint64_t + atomic uint32_t. That is, flip the roles of counter and snapshot. \$\endgroup\$ – a25bedc5-3d09-41b8-82fb-ea6c353d75ae Sep 7 '16 at 1:42
  • \$\begingroup\$ That would crash the program if this API was used by 2^32 distinct threads, even if only a small subset were active at any given time. \$\endgroup\$ – Demi Sep 7 '16 at 4:00
  • \$\begingroup\$ I don't see how exactly it'd crash. 2^32 threads is far more than any machine is capable of. If you're aiming that high, 12 bytes would not be enough. You'd have to use uint1024_t \$\endgroup\$ – a25bedc5-3d09-41b8-82fb-ea6c353d75ae Sep 7 '16 at 4:15
  • \$\begingroup\$ You can't have that many threads at once. But you most certainly can launch that many threads, just not at the same time. \$\endgroup\$ – Demi Sep 7 '16 at 12:53
1
\$\begingroup\$
#elif 0
}

and related

#if 0
{

are quite unconventional. You may safely omit anything which is conditioned to 0.


Testing size of static variables is truly paranoid. If you are that serious, you should assert that sizeof(nonce) == sizeof(local_counter) + sizeof(local_snapshot).


The value of nonce is unique, but fairly predictable. Not a security expert, I have feeling that there is an exploit waiting.

One possible attack vector is to flood your service to the point of abort. At this moment an attacker knows that the nonce is going to be all zeroes.

\$\endgroup\$
  • \$\begingroup\$ The #if 0 et all are to work around an Emacs indentation bug. Predictability is not a problem for this application – security does not depend on the individual values of the nonces, only that they be used only once. The short should be unreachable over any reasonable timescale. \$\endgroup\$ – Demi Sep 6 '16 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.