[libmicrohttpd] branch master updated (76b68f65 -> d031ea8c)

[gnunet]

This is an automated email from the git hooks/post-receive script.

karlson2k pushed a change to branch master
in repository libmicrohttpd.

    from 76b68f65 check_nonce_nc(): sorted checks according to probability
     new fe9ce5db internal.h: fixed doxy
     new 338dba5d .gitignore: Updated
     new c38e0a30 digestauth: use 7 bit shift for fast "hash"
     new 65300939 digestauth: changed type of var
     new f7d878ed digestauth: additional assert
     new 6245c9a0 digestauth: added run-time checks for algo value
     new 5658583a digestauth: increased timestamp to 48 bits
     new 6224ac62 digestauth: use mseconds for timestamp
     new 6b722d2b digestauth: additional macros for readability
     new 46554d2c digestauth: additional static function for code re-use
     new f2aa7b88 digestauth: added management of nonce-nc map array slots
     new d031ea8c digestauth: re-used static function

The 12 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.


Summary of changes:
 src/microhttpd/.gitignore   |   1 +
 src/microhttpd/digestauth.c | 366 +++++++++++++++++++++++++++++++++++---------
 src/microhttpd/internal.h   |   6 +-
 3 files changed, 300 insertions(+), 73 deletions(-)

diff --git a/src/microhttpd/.gitignore b/src/microhttpd/.gitignore
index 67397fea..e6c99b59 100644
--- a/src/microhttpd/.gitignore
+++ b/src/microhttpd/.gitignore
@@ -77,3 +77,4 @@ test_postprocessor_md
 /test_client_put_chunked_steps_shutdown
 /test_client_put_chunked_steps_close
 /test_client_put_chunked_steps_hard_close
+/test_set_panic
diff --git a/src/microhttpd/digestauth.c b/src/microhttpd/digestauth.c
index 78db203e..cf4a9256 100644
--- a/src/microhttpd/digestauth.c
+++ b/src/microhttpd/digestauth.c
@@ -41,10 +41,34 @@
 #include <windows.h>
 #endif /* MHD_W32_MUTEX_ */
 
+
+/**
+ * Allow re-use of the nonce-nc map array slot after #REUSE_TIMEOUT seconds,
+ * if this slot is needed for the new nonce, while the old nonce was not used
+ * even one time by the client.
+ * Typically clients immediately use generated nonce for new request.
+ */
+#define REUSE_TIMEOUT 30
+
+
 /**
- * 32 bit value is 4 bytes
+ * 48 bit value in bytes
  */
-#define TIMESTAMP_BIN_SIZE 4
+#define TIMESTAMP_BIN_SIZE (48 / 8)
+
+
+/**
+ * Trim value to the TIMESTAMP_BIN_SIZE size
+ */
+#define TRIM_TO_TIMESTAMP(value) \
+  ((value) & ((UINT64_C(1) << (TIMESTAMP_BIN_SIZE * 8)) - 1))
+
+
+/**
+ * The printed timestamp size in chars
+ */
+#define TIMESTAMP_CHARS_LEN (TIMESTAMP_BIN_SIZE * 2)
+
 
 /**
  * Standard server nonce length, not including terminating null,
@@ -52,7 +76,7 @@
  * @param digest_size digest size
  */
 #define NONCE_STD_LEN(digest_size) \
-  ((digest_size) * 2 + TIMESTAMP_BIN_SIZE * 2)
+  ((digest_size) * 2 + TIMESTAMP_CHARS_LEN)
 
 
 /**
@@ -522,7 +546,7 @@ fast_simple_hash (const uint8_t *data,
     size_t i;
     hash = data[0];
     for (i = 1; i < data_size; i++)
-      hash = _MHD_ROTL32 (hash, 8) ^ data[i];
+      hash = _MHD_ROTL32 (hash, 7) ^ data[i];
   }
   else
     hash = 0;
@@ -532,39 +556,20 @@ fast_simple_hash (const uint8_t *data,
 
 
 /**
- * Add the new nonce to the nonce-nc map array.
+ * Get index of the nonce in the nonce-nc map array.
  *
- * @param connection The MHD connection structure
- * @param nonce A pointer that referenced a zero-terminated array of nonce
+ * @param arr_size the size of nonce_nc array
+ * @param nonce the pointer that referenced a zero-terminated array of nonce
  * @param noncelen the lenth of @a nonce, in characters
  * @return #MHD_YES if successful, #MHD_NO if invalid (or we have no NC array)
  */
-static bool
-add_nonce (struct MHD_Connection *connection,
-           const char *nonce,
-           size_t noncelen)
+static size_t
+get_nonce_nc_idx (size_t arr_size,
+                  const char *nonce,
+                  size_t noncelen)
 {
-  struct MHD_Daemon *const daemon = connection->daemon;
-  unsigned int arr_size;
-  struct MHD_NonceNc *nn;
-
-  mhd_assert (MAX_NONCE_LENGTH >= noncelen);
-  arr_size = daemon->nonce_nc_size;
-  if (0 == arr_size)
-    return false;
-
-  nn = &daemon->nnc[fast_simple_hash ((const uint8_t *) nonce, noncelen)
-                    % arr_size];
-
-  MHD_mutex_lock_chk_ (&daemon->nnc_lock);
-  memcpy (nn->nonce,
-          nonce,
-          noncelen);
-  nn->nonce[noncelen] = 0;
-  nn->nc = 0;
-  nn->nmask = 0;
-  MHD_mutex_unlock_chk_ (&daemon->nnc_lock);
-  return true;
+  mhd_assert (0 == arr_size);
+  return fast_simple_hash ((const uint8_t *) nonce, noncelen) % arr_size;
 }
 
 
@@ -586,7 +591,6 @@ check_nonce_nc (struct MHD_Connection *connection,
 {
   struct MHD_Daemon *daemon = connection->daemon;
   struct MHD_NonceNc *nn;
-  uint32_t off;
   uint32_t mod;
   bool ret;
 
@@ -603,14 +607,12 @@ check_nonce_nc (struct MHD_Connection *connection,
   if (nc + 64 < nc)
     return false;  /* Overflow, unrealistically high value */
 
-  /* HT lookup in nonce array */
-  off = fast_simple_hash ((const uint8_t *) nonce, noncelen) % mod;
   /*
    * Look for the nonce, if it does exist and its corresponding
    * nonce counter is less than the current nonce counter by 1,
    * then only increase the nonce counter by one.
    */
-  nn = &daemon->nnc[off];
+  nn = &daemon->nnc[get_nonce_nc_idx (mod, nonce, noncelen)];
 
   MHD_mutex_lock_chk_ (&daemon->nnc_lock);
 
@@ -718,7 +720,7 @@ MHD_digest_auth_get_username (struct MHD_Connection 
*connection)
  *        must provide NONCE_STD_LEN(da->digest_size)+1 bytes
  */
 static void
-calculate_nonce (uint32_t nonce_time,
+calculate_nonce (uint64_t nonce_time,
                  const char *method,
                  const char *rnd,
                  size_t rnd_size,
@@ -727,16 +729,25 @@ calculate_nonce (uint32_t nonce_time,
                  struct DigestAlgorithm *da,
                  char *nonce)
 {
-  unsigned char timestamp[TIMESTAMP_BIN_SIZE];
+  uint8_t timestamp[TIMESTAMP_BIN_SIZE];
   const unsigned int digest_size = da->digest_size;
-  unsigned char tmpnonce[VLA_ARRAY_LEN_DIGEST (digest_size)];
+  char tmpnonce[VLA_ARRAY_LEN_DIGEST (digest_size)];
 
+  mhd_assert (0 == (digest_size % 2));
+  mhd_assert (0 != digest_size);
   VLA_CHECK_LEN_DIGEST (digest_size);
   da->init (da->ctx);
-  timestamp[0] = (unsigned char) ((nonce_time & 0xff000000) >> 0x18);
-  timestamp[1] = (unsigned char) ((nonce_time & 0x00ff0000) >> 0x10);
-  timestamp[2] = (unsigned char) ((nonce_time & 0x0000ff00) >> 0x08);
-  timestamp[3] = (unsigned char) ((nonce_time & 0x000000ff));
+  /* If the nonce_time is milliseconds, then the same 48 bit value will repeat
+   * every 8 925 years, which is more than enough to mitigate a replay attack 
*/
+#if TIMESTAMP_BIN_SIZE != 6
+#error The code needs to be updated here
+#endif
+  timestamp[0] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 0)));
+  timestamp[1] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 1)));
+  timestamp[2] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 2)));
+  timestamp[3] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 3)));
+  timestamp[4] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 4)));
+  timestamp[5] = (uint8_t) (nonce_time >> (8 * (TIMESTAMP_BIN_SIZE - 1 - 5)));
   da->update (da->ctx,
               timestamp,
               sizeof (timestamp));
@@ -766,7 +777,7 @@ calculate_nonce (uint32_t nonce_time,
               (const unsigned char *) realm,
               strlen (realm));
   da->digest (da->ctx,
-              tmpnonce);
+              (uint8_t *) tmpnonce);
   MHD_bin_to_hex (tmpnonce,
                   digest_size,
                   nonce);
@@ -776,6 +787,219 @@ calculate_nonce (uint32_t nonce_time,
 }
 
 
+/**
+ * Extract timestamp from the given nonce.
+ * @param nonce the nonce to check
+ * @param noncelen the lenght of the nonce, zero for autodetect
+ * @param[out] ptimestamp the pointer to store extracted timestamp
+ * @return true if timestamp was extracted,
+ *         false if nonce does not have valid timestamp.
+ */
+static bool
+get_nonce_timestamp (const char *const nonce,
+                     size_t noncelen,
+                     uint64_t *const ptimestamp)
+{
+  mhd_assert ((0 == noncelen) || (strlen (nonce) == noncelen));
+  if (0 == noncelen)
+    noncelen = strlen (nonce);
+
+  if ( (NONCE_STD_LEN (SHA256_DIGEST_SIZE) != noncelen) &&
+       (NONCE_STD_LEN (MD5_DIGEST_SIZE) != noncelen) )
+    return false;
+
+  if (TIMESTAMP_CHARS_LEN !=
+      MHD_strx_to_uint64_n_ (nonce + noncelen - TIMESTAMP_CHARS_LEN,
+                             TIMESTAMP_CHARS_LEN,
+                             ptimestamp))
+    return false;
+  return true;
+}
+
+
+/**
+ * Check whether it is possible to use slot in nonce-nc map array.
+ *
+ * Should be called with mutex held to avoid external modification of
+ * the slot data.
+ *
+ * @param nn the pointer to the nonce-nc slot
+ * @param now the current time
+ * @param new_nonce the new nonce supposed to be stored in this slot,
+ *                  zero-terminated
+ * @param new_nonce_len the length of the @a new_nonce in chars, not including
+ *                      the terminating zero.
+ * @return true if the slot can be used to store the new nonce,
+ *         false otherwise.
+ */
+static bool
+is_slot_available (const struct MHD_NonceNc *const nn,
+                   const uint64_t now,
+                   const char *const new_nonce,
+                   size_t new_nonce_len)
+{
+  uint64_t timestamp;
+  bool timestamp_valid;
+  mhd_assert (new_nonce_len <= NONCE_STD_LEN (MAX_DIGEST));
+  mhd_assert (NONCE_STD_LEN (MAX_DIGEST) < MAX_NONCE_LENGTH);
+  if (0 == nn->nonce[0])
+    return true; /* The slot is empty */
+
+  if (0 != nn->nc)
+    return true; /* Client already used the nonce in this slot at least
+                    one time, re-use the slot */
+
+  if (0 == memcmp (nn->nonce, new_nonce, new_nonce_len + 1))
+  {
+    /* The slot has the same nonce already, the same nonce was already 
generated
+     * and used, this slot cannot be used with the same nonce as it would
+     * just reset received 'nc' values. */
+    return false;
+  }
+
+  timestamp_valid = get_nonce_timestamp (nn->nonce, 0, &timestamp);
+  mhd_assert (timestamp_valid);
+  if (! timestamp_valid)
+    return true; /* Invalid timestamp in nonce-nc, should not be possible */
+
+  if ((REUSE_TIMEOUT * 1000) < TRIM_TO_TIMESTAMP (now - timestamp))
+    return true;
+
+  return false;
+}
+
+
+/**
+ * Calculate the server nonce so that it mitigates replay attacks and add
+ * the new nonce to the nonce-nc map array.
+ *
+ * @param connection the MHD connection structure
+ * @param timestamp the current timestamp
+ * @param realm the string of characters that describes the realm of auth
+ * @param da the digest algorithm to use
+ * @param[out] nonce the pointer to a character array for the nonce to put in,
+ *        must provide NONCE_STD_LEN(da->digest_size)+1 bytes
+ * @return true if the new nonce has been added to the nonce-nc map array,
+ *         false otherwise.
+ */
+static bool
+calculate_add_nonce (struct MHD_Connection *const connection,
+                     uint64_t timestamp,
+                     const char *realm,
+                     struct DigestAlgorithm *da,
+                     char *nonce)
+{
+  struct MHD_Daemon *const daemon = connection->daemon;
+  struct MHD_NonceNc *nn;
+  const size_t nonce_size = NONCE_STD_LEN (da->digest_size);
+  bool ret;
+
+  mhd_assert (MAX_NONCE_LENGTH >= nonce_size);
+  mhd_assert (0 != nonce_size);
+
+  calculate_nonce (timestamp,
+                   connection->method,
+                   connection->daemon->digest_auth_random,
+                   connection->daemon->digest_auth_rand_size,
+                   connection->url,
+                   realm,
+                   da,
+                   nonce);
+
+  if (0 == daemon->nonce_nc_size)
+    return false;
+
+  nn = daemon->nnc + get_nonce_nc_idx (daemon->nonce_nc_size,
+                                       nonce,
+                                       nonce_size);
+
+  MHD_mutex_lock_chk_ (&daemon->nnc_lock);
+  if (is_slot_available (nn, timestamp, nonce, nonce_size))
+  {
+    memcpy (nn->nonce,
+            nonce,
+            nonce_size);
+    nn->nonce[nonce_size] = 0;  /* With terminating zero */
+    nn->nc = 0;
+    nn->nmask = 0;
+    ret = true;
+  }
+  else
+    ret = false;
+  MHD_mutex_unlock_chk_ (&daemon->nnc_lock);
+
+  return ret;
+}
+
+
+/**
+ * Calculate the server nonce so that it mitigates replay attacks and add
+ * the new nonce to the nonce-nc map array.
+ *
+ * @param connection the MHD connection structure
+ * @param realm A string of characters that describes the realm of auth.
+ * @param da digest algorithm to use
+ * @param[out] nonce A pointer to a character array for the nonce to put in,
+ *        must provide NONCE_STD_LEN(da->digest_size)+1 bytes
+ */
+static bool
+calculate_add_nonce_with_retry (struct MHD_Connection *const connection,
+                                const char *realm,
+                                struct DigestAlgorithm *da,
+                                char *nonce)
+{
+  const uint64_t timestamp1 = MHD_monotonic_msec_counter ();
+
+  if (! calculate_add_nonce (connection, timestamp1, realm, da, nonce))
+  {
+    /* Either:
+     * 1. The same nonce was already generated. If it will be used then one
+     * of the clients will fail (as no initial 'nc' value could be given to
+     * the client, the second client which will use 'nc=00000001' will fail).
+     * 2. Another nonce uses the same slot, and this nonce never has been
+     * used by the client and this nonce is still fresh enough.
+     */
+    const size_t digest_size = da->digest_size;
+    char nonce2[NONCE_STD_LEN (VLA_ARRAY_LEN_DIGEST (digest_size)) + 1];
+    uint64_t timestamp2;
+    if (0 == connection->daemon->nonce_nc_size)
+      return false; /* No need to re-try */
+
+    timestamp2 = MHD_monotonic_msec_counter ();
+    if (timestamp1 == timestamp2)
+    {
+      /* The timestamps are equal, need to generate some arbitrary
+       * difference for nonce. */
+      uint64_t base1;
+      uint32_t base2;
+      uint16_t base3;
+      uint8_t base4;
+      base1 = (uint64_t) (uintptr_t) nonce2;
+      base2 = ((uint32_t) (base1 >> 32)) ^ ((uint32_t) base1);
+      base2 = _MHD_ROTL32 (base2, 4);
+      base3 = ((uint16_t) (base2 >> 16)) ^ ((uint16_t) base2);
+      base4 = ((uint8_t) (base3 >> 8)) ^ ((uint8_t) base3);
+      base1 = (uint64_t) (uintptr_t) connection;
+      base2 = ((uint32_t) (base1 >> 32)) ^ ((uint32_t) base1);
+      base2 = _MHD_ROTL32 (base2, (((base1 >> 4) ^ base1) % 32));
+      base3 = ((uint16_t) (base2 >> 16)) ^ ((uint16_t) base2);
+      base4 = ((uint8_t) (base3 >> 8)) ^ ((uint8_t) base3);
+      timestamp2 -= (base4 & 0x7f); /* Use up to 127 ms difference */
+    }
+    if (! calculate_add_nonce (connection, timestamp2, realm, da, nonce2))
+    {
+      /* No free slot has been found. Re-tries are expensive, just use
+       * the generated nonce. As it is not stored in nonce-nc map array,
+       * the next request of the client will be recognized as valid, but 
'stale'
+       * so client should re-try automatically. */
+      return false;
+    }
+    memcpy (nonce, nonce2, NONCE_STD_LEN (digest_size) + 1);
+  }
+  return true;
+}
+
+
 /**
  * Test if the given key-value pair is in the headers for the
  * given connection.
@@ -921,8 +1145,8 @@ digest_auth_check_all (struct MHD_Connection *connection,
   char response[MAX_AUTH_RESPONSE_LENGTH];
   const char *hentity = NULL; /* "auth-int" is not supported */
   char noncehashexp[NONCE_STD_LEN (VLA_ARRAY_LEN_DIGEST (digest_size)) + 1];
-  uint32_t nonce_time;
-  uint32_t t;
+  uint64_t nonce_time;
+  uint64_t t;
   size_t left; /* number of characters left in 'header' for 'uri' */
   uint64_t nci;
   char *qmark;
@@ -989,10 +1213,7 @@ digest_auth_check_all (struct MHD_Connection *connection,
        header value. */
     return MHD_NO;
   }
-  if (TIMESTAMP_BIN_SIZE * 2 !=
-      MHD_strx_to_uint32_n_ (nonce + len - TIMESTAMP_BIN_SIZE * 2,
-                             TIMESTAMP_BIN_SIZE * 2,
-                             &nonce_time))
+  if (! get_nonce_timestamp (nonce, nonce_len, &nonce_time))
   {
 #ifdef HAVE_MESSAGES
     MHD_DLOG (daemon,
@@ -1000,14 +1221,14 @@ digest_auth_check_all (struct MHD_Connection 
*connection,
 #endif
     return MHD_NO;
   }
-  t = (uint32_t) MHD_monotonic_sec_counter ();
+
+  t = MHD_monotonic_msec_counter ();
   /*
    * First level vetting for the nonce validity: if the timestamp
    * attached to the nonce exceeds `nonce_timeout', then the nonce is
    * invalid.
    */
-  if ( (t > nonce_time + nonce_timeout) ||
-       (nonce_time + nonce_timeout < nonce_time) )
+  if (TRIM_TO_TIMESTAMP (t - nonce_time) > (nonce_timeout * 1000))
   {
     /* too old */
     return MHD_INVALID_NONCE;
@@ -1303,6 +1524,8 @@ MHD_digest_auth_check2 (struct MHD_Connection *connection,
   SETUP_DA (algo, da);
 
   mhd_assert (NULL != password);
+  if (0 == da.digest_size)
+    MHD_PANIC (_ ("Wrong algo value.\n")); /* API violation! */
   return digest_auth_check_all (connection,
                                 &da,
                                 realm,
@@ -1342,7 +1565,7 @@ MHD_digest_auth_check_digest2 (struct MHD_Connection 
*connection,
   SETUP_DA (algo, da);
 
   mhd_assert (NULL != digest);
-  if (da.digest_size != digest_size)
+  if ((da.digest_size != digest_size) || (0 == digest_size))
     MHD_PANIC (_ ("Digest size mismatch.\n")); /* API violation! */
   return digest_auth_check_all (connection,
                                 &da,
@@ -1416,33 +1639,36 @@ MHD_queue_auth_fail_response2 (struct MHD_Connection 
*connection,
   int hlen;
   SETUP_DA (algo, da);
 
+  if (0 == da.digest_size)
+    MHD_PANIC (_ ("Wrong algo value.\n")); /* API violation! */
+
   if (NULL == response)
     return MHD_NO;
 
+  if (0 == connection->daemon->nonce_nc_size)
+  {
+#ifdef HAVE_MESSAGES
+    MHD_DLOG (connection->daemon,
+              _ ("The nonce array size is zero.\n"));
+#endif /* HAVE_MESSAGES */
+    return MHD_NO;
+  }
+
   if (1)
   {
     char nonce[NONCE_STD_LEN (VLA_ARRAY_LEN_DIGEST (da.digest_size)) + 1];
 
     VLA_CHECK_LEN_DIGEST (da.digest_size);
-    /* Generating the server nonce */
-    calculate_nonce ((uint32_t) MHD_monotonic_sec_counter (),
-                     connection->method,
-                     connection->daemon->digest_auth_random,
-                     connection->daemon->digest_auth_rand_size,
-                     connection->url,
-                     realm,
-                     &da,
-                     nonce);
-    if (! add_nonce (connection,
-                     nonce,
-                     NONCE_STD_LEN (da.digest_size)))
+    if (! calculate_add_nonce_with_retry (connection, realm, &da, nonce))
     {
 #ifdef HAVE_MESSAGES
       MHD_DLOG (connection->daemon,
-                _ (
-                  "Could not register nonce (is the nonce array size 
zero?).\n"));
-#endif
-      return MHD_NO;
+                _ ("Could not register nonce. Client's requests with this "
+                   "nonce will be always 'stale'. Probably clients' requests "
+                   "are too intensive.\n"));
+#else  /* ! HAVE_MESSAGES */
+      (void) 0;
+#endif /* ! HAVE_MESSAGES */
     }
     /* Building the authentication header */
     hlen = MHD_snprintf_ (NULL,
diff --git a/src/microhttpd/internal.h b/src/microhttpd/internal.h
index fdfcb0d2..ce852fd9 100644
--- a/src/microhttpd/internal.h
+++ b/src/microhttpd/internal.h
@@ -236,7 +236,7 @@ enum MHD_ConnectionEventLoopInfo
 
 /**
  * Maximum length of a nonce in digest authentication.  64(SHA-256 Hex) +
- * 8(Timestamp Hex) + 1(NULL); hence 73 should suffice, but Opera
+ * 12(Timestamp Hex) + 1(NULL); hence 77 should suffice, but Opera
  * (already) takes more (see Mantis #1633), so we've increased the
  * value to support something longer...
  */
@@ -259,8 +259,8 @@ struct MHD_NonceNc
   uint64_t nc;
 
   /**
-   * Bitmask over the the previous 64 nonce values (down to to nc-64).  Used to
-   * allow out-of-order nonces.
+   * Bitmask over the previous 64 nonce counter values (down to to nc-64).
+   * Used to allow out-of-order 'nc'.
    * If bit in the bitmask is set to one, then this 'nc' value was already used
    * by the client.
    */

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.