[patch 2/3] Fortuna fixes - Mailing list pgsql-patches

After studying Fortuna more, I found out that I missed
some of the details.

- reseeding should happen only if pool #0 has aquired additional
  entropy.

- a 'rekeying' operation should happend after each request and
  also after 1M of extracted data.  That means taking next two
  blocks and using it as new key.

- Fortuna _really_ wants entropy sources to be somewhat unpredictible.

  So roll dice when adding it and also add them to pools randomly,
  not sequentially.

  This hopefully makes harder for someone to doctor with the
  internal state (as in our case user can directly control
  what goes into it).

  That also drops the idea of several sources - which really
  fits more to hardware backed event sources.

- add a really obvious obfuscation: take the absolutely first
  block be initial counter value.  If Fortuna (AES to be exact)
  is secure with known counter value, then it should be also
  secure with unknown counter value.  This does not go against
  the important property of counter - that the bit-pattern repeat
  period should be as long as possible.

- S2K functions should use px_get_pseudo_random_bytes not
  px_get_random_bytes.

Index: pgsql/contrib/pgcrypto/fortuna.c
===================================================================
*** pgsql.orig/contrib/pgcrypto/fortuna.c
--- pgsql/contrib/pgcrypto/fortuna.c
***************
*** 94,107 ****
  /* for one big request, reseed after this many bytes */
  #define RESEED_BYTES    (1024*1024)


  /*
   * Algorithm constants
   */

- /* max sources */
- #define MAX_SOURCES        8
-
  /* Both cipher key size and hash result size */
  #define BLOCK            32

--- 94,109 ----
  /* for one big request, reseed after this many bytes */
  #define RESEED_BYTES    (1024*1024)

+ /*
+  * Skip reseed if pool 0 has less than this many
+  * bytes added since last reseed.
+  */
+ #define POOL0_FILL        (256/8)

  /*
   * Algorithm constants
   */

  /* Both cipher key size and hash result size */
  #define BLOCK            32

*************** struct fortuna_state {
*** 118,126 ****
      uint8            key[BLOCK];
      MD_CTX            pool[NUM_POOLS];
      CIPH_CTX        ciph;
-     unsigned        source_pos[MAX_SOURCES];
      unsigned        reseed_count;
      struct timeval    last_reseed_time;
  };
  typedef struct fortuna_state FState;

--- 120,130 ----
      uint8            key[BLOCK];
      MD_CTX            pool[NUM_POOLS];
      CIPH_CTX        ciph;
      unsigned        reseed_count;
      struct timeval    last_reseed_time;
+     unsigned        pool0_bytes;
+     unsigned        rnd_pos;
+     int                counter_init;
  };
  typedef struct fortuna_state FState;

*************** static void md_result(MD_CTX *ctx, uint8
*** 161,167 ****
      memset(&tmp, 0, sizeof(tmp));
  }

-
  /*
   * initialize state
   */
--- 165,170 ----
*************** static void init_state(FState *st)
*** 174,179 ****
--- 177,208 ----
  }

  /*
+  * Endianess does not matter.
+  * It just needs to change without repeating.
+  */
+ static void inc_counter(FState *st)
+ {
+     uint32 *val = (uint32*)st->counter;
+     if (++val[0])
+         return;
+     if (++val[1])
+         return;
+     if (++val[2])
+         return;
+     ++val[3];
+ }
+
+ /*
+  * This is called 'cipher in counter mode'.
+  */
+ static void encrypt_counter(FState *st, uint8 *dst)
+ {
+     ciph_encrypt(&st->ciph, st->counter, dst);
+     inc_counter(st);
+ }
+
+
+ /*
   * The time between reseed must be at least RESEED_INTERVAL
   * microseconds.
   */
*************** static void reseed(FState *st)
*** 207,215 ****
      MD_CTX key_md;
      uint8 buf[BLOCK];

!     /* check frequency */
!     if (too_often(st))
!         return;

      /*
       * Both #0 and #1 reseed would use only pool 0.
--- 236,243 ----
      MD_CTX key_md;
      uint8 buf[BLOCK];

!     /* set pool as empty */
!     st->pool0_bytes = 0;

      /*
       * Both #0 and #1 reseed would use only pool 0.
*************** static void reseed(FState *st)
*** 244,292 ****
  }

  /*
   * update pools
   */
! static void add_entropy(FState *st, unsigned src_id, const uint8 *data, unsigned len)
  {
      unsigned pos;
      uint8 hash[BLOCK];
      MD_CTX md;

-     /* just in case there's a bug somewhere */
-     if (src_id >= MAX_SOURCES)
-         src_id = USER_ENTROPY;
-
      /* hash given data */
      md_init(&md);
      md_update(&md, data, len);
      md_result(&md, hash);

!     /* update pools round-robin manner */
!     pos = st->source_pos[src_id];
      md_update( &st->pool[pos], hash, BLOCK);

!     if (++pos >= NUM_POOLS)
!         pos = 0;
!     st->source_pos[src_id] = pos;

      memset(hash, 0, BLOCK);
      memset(&md, 0, sizeof(md));
  }

  /*
!  * Endianess does not matter.
!  * It just needs to change without repeating.
   */
! static void inc_counter(FState *st)
  {
!     uint32 *val = (uint32*)st->counter;
!     if (++val[0])
!         return;
!     if (++val[1])
!         return;
!     if (++val[2])
!         return;
!     ++val[3];
  }

  static void extract_data(FState *st, unsigned count, uint8 *dst)
--- 272,351 ----
  }

  /*
+  * Pick a random pool.  This uses key bytes as random source.
+  */
+ static unsigned get_rand_pool(FState *st)
+ {
+     unsigned rnd;
+
+     /*
+      * This slightly prefers lower pools - thats OK.
+      */
+     rnd = st->key[st->rnd_pos] % NUM_POOLS;
+
+     st->rnd_pos++;
+     if (st->rnd_pos >= BLOCK)
+         st->rnd_pos = 0;
+
+     return rnd;
+ }
+
+ /*
   * update pools
   */
! static void add_entropy(FState *st, const uint8 *data, unsigned len)
  {
      unsigned pos;
      uint8 hash[BLOCK];
      MD_CTX md;

      /* hash given data */
      md_init(&md);
      md_update(&md, data, len);
      md_result(&md, hash);

!     /*
!      * Make sure the pool 0 is initialized,
!      * then update randomly.
!      */
!     if (st->reseed_count == 0 && st->pool0_bytes < POOL0_FILL)
!         pos = 0;
!     else
!         pos = get_rand_pool(st);
      md_update( &st->pool[pos], hash, BLOCK);

!     if (pos == 0)
!         st->pool0_bytes += len;

      memset(hash, 0, BLOCK);
      memset(&md, 0, sizeof(md));
  }

  /*
!  * Just take 2 next blocks as new key
   */
! static void rekey(FState *st)
  {
!     encrypt_counter(st, st->key);
!     encrypt_counter(st, st->key + CIPH_BLOCK);
!     ciph_init(&st->ciph, st->key, BLOCK);
! }
!
! /*
!  * Fortuna relies on AES standing known-plaintext attack.
!  * In case it does not, slow down the attacker by initialising
!  * the couter to random value.
!  */
! static void init_counter(FState *st)
! {
!     /* Use next block as counter. */
!     encrypt_counter(st, st->counter);
!
!     /* Hide the key. */
!     rekey(st);
!
!     /* The counter can be shuffled only once. */
!     st->counter_init = 1;
  }

  static void extract_data(FState *st, unsigned count, uint8 *dst)
*************** static void extract_data(FState *st, uns
*** 294,324 ****
      unsigned n;
      unsigned block_nr = 0;

!     /*
!      * Every request should be with different key,
!      * if possible.
!      */
!     reseed(st);
!
!     /*
!      * If the reseed didn't happen, don't use the old data
!      * rather encrypt again.
!      */

      while (count > 0) {
-         /* must not give out too many bytes with one key */
-         if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
-         {
-             reseed(st);
-             block_nr = 0;
-         }
-
          /* produce bytes */
!         ciph_encrypt(&st->ciph, st->counter, st->result);
!         block_nr++;
!
!         /* prepare for next time */
!         inc_counter(st);

          /* copy result */
          if (count > CIPH_BLOCK)
--- 353,369 ----
      unsigned n;
      unsigned block_nr = 0;

!     /* Can we reseed? */
!     if (st->pool0_bytes >= POOL0_FILL && !too_often(st))
!         reseed(st);
!
!     /* Is counter initialized? */
!     if (!st->counter_init)
!         init_counter(st);

      while (count > 0) {
          /* produce bytes */
!         encrypt_counter(st, st->result);

          /* copy result */
          if (count > CIPH_BLOCK)
*************** static void extract_data(FState *st, uns
*** 328,334 ****
--- 373,389 ----
          memcpy(dst, st->result, n);
          dst += n;
          count -= n;
+
+         /* must not give out too many bytes with one key */
+         block_nr++;
+         if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
+         {
+             rekey(st);
+             block_nr = 0;
+         }
      }
+     /* Set new key for next request. */
+     rekey(st);
  }

  /*
*************** static void extract_data(FState *st, uns
*** 338,344 ****
  static FState main_state;
  static int init_done = 0;

! void fortuna_add_entropy(unsigned src_id, const uint8 *data, unsigned len)
  {
      if (!init_done)
      {
--- 393,399 ----
  static FState main_state;
  static int init_done = 0;

! void fortuna_add_entropy(const uint8 *data, unsigned len)
  {
      if (!init_done)
      {
*************** void fortuna_add_entropy(unsigned src_id
*** 347,353 ****
      }
      if (!data || !len)
          return;
!     add_entropy(&main_state, src_id, data, len);
  }

  void fortuna_get_bytes(unsigned len, uint8 *dst)
--- 402,408 ----
      }
      if (!data || !len)
          return;
!     add_entropy(&main_state, data, len);
  }

  void fortuna_get_bytes(unsigned len, uint8 *dst)
Index: pgsql/contrib/pgcrypto/fortuna.h
===================================================================
*** pgsql.orig/contrib/pgcrypto/fortuna.h
--- pgsql/contrib/pgcrypto/fortuna.h
***************
*** 32,45 ****
  #ifndef __FORTUNA_H
  #define __FORTUNA_H

- /*
-  * Event source ID's
-  */
- #define SYSTEM_ENTROPY    0
- #define USER_ENTROPY    1
-
  void fortuna_get_bytes(unsigned len, uint8 *dst);
! void fortuna_add_entropy(unsigned src_id, const uint8 *data, unsigned len);

  #endif

--- 32,39 ----
  #ifndef __FORTUNA_H
  #define __FORTUNA_H

  void fortuna_get_bytes(unsigned len, uint8 *dst);
! void fortuna_add_entropy(const uint8 *data, unsigned len);

  #endif

Index: pgsql/contrib/pgcrypto/internal.c
===================================================================
*** pgsql.orig/contrib/pgcrypto/internal.c
--- pgsql/contrib/pgcrypto/internal.c
***************
*** 42,50 ****
  #include "fortuna.h"

  /*
!  * How often to try to acquire system entropy.  (In seconds)
   */
! #define SYSTEM_RESEED_FREQ    (3*60*60)


  #ifndef MD5_DIGEST_LENGTH
--- 42,63 ----
  #include "fortuna.h"

  /*
!  * System reseeds should be separated at least this much.
   */
! #define SYSTEM_RESEED_MIN            (20*60)        /* 20 min */
! /*
!  * How often to roll dice.
!  */
! #define SYSTEM_RESEED_CHECK_TIME    (10*60)        /* 10 min */
! /*
!  * The chance is x/256 that the reseed happens.
!  */
! #define SYSTEM_RESEED_CHANCE        (4)    /* 256/4 * 10min ~ 10h */
!
! /*
!  * If this much time has passed, force reseed.
!  */
! #define SYSTEM_RESEED_MAX            (12*60*60)    /* 12h */


  #ifndef MD5_DIGEST_LENGTH
*************** px_get_pseudo_random_bytes(uint8 *dst, u
*** 823,842 ****
  }

  static time_t seed_time = 0;

  static void system_reseed(void)
  {
      uint8 buf[1024];
      int n;
      time_t t;

      t = time(NULL);
!     if (seed_time && (t - seed_time) < SYSTEM_RESEED_FREQ)
          return;

      n = px_acquire_system_randomness(buf);
      if (n > 0)
!         fortuna_add_entropy(SYSTEM_ENTROPY, buf, n);

      seed_time = t;
      memset(buf, 0, sizeof(buf));
--- 836,875 ----
  }

  static time_t seed_time = 0;
+ static time_t check_time = 0;

  static void system_reseed(void)
  {
      uint8 buf[1024];
      int n;
      time_t t;
+     int skip = 1;

      t = time(NULL);
!
!     if (seed_time == 0)
!         skip = 0;
!     else if ((t - seed_time) < SYSTEM_RESEED_MIN)
!         skip = 1;
!     else if ((t - seed_time) > SYSTEM_RESEED_MAX)
!         skip = 0;
!     else if (!check_time || (t - check_time) > SYSTEM_RESEED_CHECK_TIME)
!     {
!         check_time = t;
!
!         /* roll dice */
!         px_get_random_bytes(buf, 1);
!         skip = buf[0] >= SYSTEM_RESEED_CHANCE;
!     }
!     /* clear 1 byte */
!     memset(buf, 0, sizeof(buf));
!
!     if (skip)
          return;

      n = px_acquire_system_randomness(buf);
      if (n > 0)
!         fortuna_add_entropy(buf, n);

      seed_time = t;
      memset(buf, 0, sizeof(buf));
*************** int
*** 854,860 ****
  px_add_entropy(const uint8 *data, unsigned count)
  {
      system_reseed();
!     fortuna_add_entropy(USER_ENTROPY, data, count);
      return 0;
  }

--- 887,893 ----
  px_add_entropy(const uint8 *data, unsigned count)
  {
      system_reseed();
!     fortuna_add_entropy(data, count);
      return 0;
  }

Index: pgsql/contrib/pgcrypto/pgp-s2k.c
===================================================================
*** pgsql.orig/contrib/pgcrypto/pgp-s2k.c
--- pgsql/contrib/pgcrypto/pgp-s2k.c
*************** pgp_s2k_fill(PGP_S2K *s2k, int mode,int
*** 225,237 ****
          case 0:
              break;
          case 1:
!             res = px_get_random_bytes(s2k->salt, PGP_S2K_SALT);
              break;
          case 3:
!             res = px_get_random_bytes(s2k->salt, PGP_S2K_SALT);
              if (res < 0)
                  break;
!             res = px_get_random_bytes(&tmp, 1);
              if (res < 0)
                  break;
              s2k->iter = decide_count(tmp);
--- 225,237 ----
          case 0:
              break;
          case 1:
!             res = px_get_pseudo_random_bytes(s2k->salt, PGP_S2K_SALT);
              break;
          case 3:
!             res = px_get_pseudo_random_bytes(s2k->salt, PGP_S2K_SALT);
              if (res < 0)
                  break;
!             res = px_get_pseudo_random_bytes(&tmp, 1);
              if (res < 0)
                  break;
              s2k->iter = decide_count(tmp);
Index: pgsql/contrib/pgcrypto/pgp-pgsql.c
===================================================================
*** pgsql.orig/contrib/pgcrypto/pgp-pgsql.c
--- pgsql/contrib/pgcrypto/pgp-pgsql.c
*************** PG_FUNCTION_INFO_V1(pg_dearmor);
*** 87,123 ****
      } while (0)

  /*
   * Mix user data into RNG.  It is for user own interests to have
   * RNG state shuffled.
   */
  static void add_entropy(text *data1,  text *data2, text *data3)
  {
      PX_MD *md;
!     uint8 sha1[20];
!     int res;

      if (!data1 && !data2 && !data3)
          return;

!     res = px_find_digest("sha1", &md);
!     if (res < 0)
          return;

!     if (data1)
!         px_md_update(md, VARDATA(data1), VARSIZE(data1) - VARHDRSZ);
!     if (data2)
!         px_md_update(md, VARDATA(data2), VARSIZE(data2) - VARHDRSZ);
!     if (data3)
!         px_md_update(md, VARDATA(data3), VARSIZE(data3) - VARHDRSZ);

!     px_md_finish(md, sha1);
!     px_md_free(md);

!     res = px_add_entropy(sha1, 20);
!     memset(sha1, 0, 20);

!     if (res < 0)
!         ereport(NOTICE, (errmsg("add_entropy: %s", px_strerror(res))));
  }

  /*
--- 87,146 ----
      } while (0)

  /*
+  * Mix a block of data into RNG.
+  */
+ static void add_block_entropy(PX_MD *md, text *data)
+ {
+     uint8 sha1[20];
+
+     px_md_reset(md);
+     px_md_update(md, VARDATA(data), VARSIZE(data) - VARHDRSZ);
+     px_md_finish(md, sha1);
+
+     px_add_entropy(sha1, 20);
+
+     memset(sha1, 0, 20);
+ }
+
+ /*
   * Mix user data into RNG.  It is for user own interests to have
   * RNG state shuffled.
   */
  static void add_entropy(text *data1,  text *data2, text *data3)
  {
      PX_MD *md;
!     uint8 rnd[3];

      if (!data1 && !data2 && !data3)
          return;

!     if (px_get_random_bytes(rnd, 3) < 0)
          return;

!     if (px_find_digest("sha1", &md) < 0)
!         return;

!     /*
!      * Try to make the feeding unpredictable.
!      *
!      * Prefer data over keys, as it's rather likely
!      * that key is same in several calls.
!      */

!     /* chance: 7/8 */
!     if (data1 && rnd[0] >= 32)
!         add_block_entropy(md, data1);
!
!     /* chance: 5/8 */
!     if (data2 && rnd[1] >= 160)
!         add_block_entropy(md, data2);
!
!     /* chance: 5/8 */
!     if (data3 && rnd[2] >= 160)
!         add_block_entropy(md, data3);

!     px_md_free(md);
!     memset(rnd, 0, sizeof(rnd));
  }

  /*

--