refactor DHT for new service API
[oweals/gnunet.git] / src / cadet / gnunet-service-cadet_tunnel.c
index 28e6aa383e4f1481cf977c046d202fbcd291a7fe..e60c3c0239b70d2b4f074ef17902cb0462b4e32f 100644 (file)
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2013 Christian Grothoff (and other contributing authors)
+     Copyright (C) 2013 GNUnet e.V.
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -14,8 +14,8 @@
 
      You should have received a copy of the GNU General Public License
      along with GNUnet; see the file COPYING.  If not, write to the
-     Free Software Foundation, Inc., 59 Temple Place - Suite 330,
-     Boston, MA 02111-1307, USA.
+     Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+     Boston, MA 02110-1301, USA.
 */
 
 #include "platform.h"
 #if !defined(GNUNET_CULL_LOGGING)
 #define DUMP_KEYS_TO_STDERR GNUNET_YES
 #else
-#define DUMP_KEYS_TO_STDERR GNUNET_NO
+#define DUMP_KEYS_TO_STDERR GNUNET_YES
 #endif
 
+#define MIN_TUNNEL_BUFFER       8
+#define MAX_TUNNEL_BUFFER       64
 #define MAX_SKIPPED_KEYS        64
 #define MAX_KEY_GAP             256
 #define AX_HEADER_SIZE (sizeof (uint32_t) * 2\
@@ -92,54 +94,6 @@ struct CadetTConnection
   uint32_t throughput;
 };
 
-/**
- * Structure used during a Key eXchange.
- */
-struct CadetTunnelKXCtx
-{
-  /**
-   * Encryption ("our") old "confirmed" key, for encrypting traffic sent by us
-   * end before the key exchange is finished or times out.
-   */
-  struct GNUNET_CRYPTO_SymmetricSessionKey e_key_old;
-
-  /**
-   * Decryption ("their") old "confirmed" key, for decrypting traffic sent by
-   * the other end before the key exchange started.
-   */
-  struct GNUNET_CRYPTO_SymmetricSessionKey d_key_old;
-
-  /**
-   * Same as @c e_key_old, for the case of two simultaneous KX.
-   * This can happen if cadet decides to start a re-key while the peer has also
-   * started its re-key (due to network delay this is impossible to avoid).
-   * In this case, the key material generated with the peer's old ephemeral
-   * *might* (but doesn't have to) be incorrect.
-   * Since no more than two re-keys can happen simultaneously, this is enough.
-   */
-  struct GNUNET_CRYPTO_SymmetricSessionKey e_key_old2;
-
-  /**
-   * Same as @c d_key_old, for the case described in @c e_key_old2.
-   */
-  struct GNUNET_CRYPTO_SymmetricSessionKey d_key_old2;
-
-  /**
-   * Challenge to send and expect in the PONG.
-   */
-  uint32_t challenge;
-
-  /**
-   * When the rekey started. One minute after this the new key will be used.
-   */
-  struct GNUNET_TIME_Absolute rekey_start_time;
-
-  /**
-   * Task for delayed destruction of the Key eXchange context, to allow delayed
-   * messages with the old key to be decrypted successfully.
-   */
-  struct GNUNET_SCHEDULER_Task *finish_task;
-};
 
 /**
  * Encryption systems possible.
@@ -149,12 +103,8 @@ enum CadetTunnelEncryption
   /**
    * Default Axolotl system.
    */
-  CADET_Axolotl,
+  CADET_Axolotl
 
-  /**
-   * Fallback OTR-style encryption.
-   */
-  CADET_OTR
 };
 
 /**
@@ -186,10 +136,16 @@ struct CadetTunnelSkippedKey
    * Message key.
    */
   struct GNUNET_CRYPTO_SymmetricSessionKey MK;
+
+  /**
+   * Key number for a given HK.
+   */
+  unsigned int Kn;
 };
 
+
 /**
- * Axolotl data, according to @url https://github.com/trevp/axolotl/wiki .
+ * Axolotl data, according to https://github.com/trevp/axolotl/wiki .
  */
 struct CadetTunnelAxolotl
 {
@@ -250,11 +206,6 @@ struct CadetTunnelAxolotl
    */
   struct GNUNET_CRYPTO_EcdhePrivateKey *kx_0;
 
-  /**
-   * ECDH Identity key (recv).
-   */
-  struct GNUNET_CRYPTO_EcdhePublicKey DHIr;
-
   /**
    * ECDH Ratchet key (send).
    */
@@ -281,9 +232,28 @@ struct CadetTunnelAxolotl
   uint32_t PNs;
 
   /**
-   * True (#GNUNET_YES) if the party will send a new ratchet key in next msg.
+   * True (#GNUNET_YES) if we have to send a new ratchet key in next msg.
    */
   int ratchet_flag;
+
+  /**
+   * Number of messages recieved since our last ratchet advance.
+   * - If this counter = 0, we cannot send a new ratchet key in next msg.
+   * - If this counter > 0, we can (but don't yet have to) send a new key.
+   */
+  unsigned int ratchet_allowed;
+
+  /**
+   * Number of messages recieved since our last ratchet advance.
+   * - If this counter = 0, we cannot send a new ratchet key in next msg.
+   * - If this counter > 0, we can (but don't yet have to) send a new key.
+   */
+  unsigned int ratchet_counter;
+
+  /**
+   * When does this ratchet expire and a new one is triggered.
+   */
+  struct GNUNET_TIME_Absolute ratchet_expiration;
 };
 
 /**
@@ -316,11 +286,6 @@ struct CadetTunnel
    */
   enum CadetTunnelEState estate;
 
-  /**
-   * Key eXchange context.
-   */
-  struct CadetTunnelKXCtx *kx_ctx;
-
   /**
    * Peer's ephemeral key, to recreate @c e_key and @c d_key when own ephemeral
    * key changes.
@@ -340,7 +305,7 @@ struct CadetTunnel
   /**
    * Task to start the rekey process.
    */
-  struct GNUNET_SCHEDULER_Task * rekey_task;
+  struct GNUNET_SCHEDULER_Task *rekey_task;
 
   /**
    * Paths that are actively used to reach the destination peer.
@@ -447,28 +412,6 @@ struct CadetTunnelQueue
 };
 
 
-/**
- * Cached Axolotl key with signature.
- */
-struct CadetAxolotlSignedKey
-{
-  /**
-   * Information about what is being signed (@a permanent_key).
-   */
-  struct GNUNET_CRYPTO_EccSignaturePurpose purpose;
-
-  /**
-   * Permanent public ECDH key.
-   */
-  struct GNUNET_CRYPTO_EcdhePublicKey permanent_key;
-
-  /**
-   * An EdDSA signature of the permanent ECDH key with the Peer's ID key.
-   */
-  struct GNUNET_CRYPTO_EddsaSignature signature;
-} GNUNET_PACKED;
-
-
 /******************************************************************************/
 /*******************************   GLOBALS  ***********************************/
 /******************************************************************************/
@@ -501,48 +444,23 @@ extern int shutting_down;
  */
 static struct GNUNET_CONTAINER_MultiPeerMap *tunnels;
 
-/**
- * Default TTL for payload packets.
- */
-static unsigned long long default_ttl;
-
-
 /**
  * Own Peer ID private key.
  */
 const static struct GNUNET_CRYPTO_EddsaPrivateKey *id_key;
 
-/********************************  AXOLOTL ************************************/
-
-static struct GNUNET_CRYPTO_EcdhePrivateKey *ax_key;
-
-/**
- * Own Axolotl permanent public key (cache).
- */
-static struct CadetAxolotlSignedKey ax_identity;
-
-/********************************    OTR   ***********************************/
-
-
-/**
- * Own global OTR ephemeral private key.
- */
-static struct GNUNET_CRYPTO_EcdhePrivateKey *otr_ephemeral_key;
 
-/**
- * Cached message used to perform a OTR key exchange.
- */
-static struct GNUNET_CADET_KX_Ephemeral otr_kx_msg;
+/********************************  AXOLOTL ************************************/
 
 /**
- * Task to generate a new OTR ephemeral key.
+ * How many messages are needed to trigger a ratchet advance.
  */
-static struct GNUNET_SCHEDULER_Task *rekey_task;
+static unsigned long long ratchet_messages;
 
 /**
- * OTR Rekey period.
+ * How long until we trigger a ratched advance.
  */
-static struct GNUNET_TIME_Relative rekey_period;
+static struct GNUNET_TIME_Relative ratchet_time;
 
 
 /******************************************************************************/
@@ -626,79 +544,20 @@ static int
 is_ready (struct CadetTunnel *t)
 {
   int ready;
-
-  GCT_debug (t, GNUNET_ERROR_TYPE_DEBUG);
-  ready = CADET_TUNNEL_READY == t->cstate
-          && (CADET_TUNNEL_KEY_OK == t->estate
-              || CADET_TUNNEL_KEY_REKEY == t->estate);
+  int conn_ok;
+  int enc_ok;
+
+  conn_ok = CADET_TUNNEL_READY == t->cstate;
+  enc_ok = CADET_TUNNEL_KEY_OK == t->estate
+           || CADET_TUNNEL_KEY_REKEY == t->estate
+           || (CADET_TUNNEL_KEY_PING == t->estate
+               && CADET_Axolotl == t->enc_type);
+  ready = conn_ok && enc_ok;
   ready = ready || GCT_is_loopback (t);
   return ready;
 }
 
 
-/**
- * Check if a key is invalid (NULL pointer or all 0)
- *
- * @param key Key to check.
- *
- * @return #GNUNET_YES if key is null, #GNUNET_NO if exists and is not 0.
- */
-static int
-is_key_null (struct GNUNET_CRYPTO_SymmetricSessionKey *key)
-{
-  struct GNUNET_CRYPTO_SymmetricSessionKey null_key;
-
-  if (NULL == key)
-    return GNUNET_YES;
-
-  memset (&null_key, 0, sizeof (null_key));
-  if (0 == memcmp (key, &null_key, sizeof (null_key)))
-    return GNUNET_YES;
-  return GNUNET_NO;
-}
-
-
-/**
- * Ephemeral key message purpose size.
- *
- * @return Size of the part of the ephemeral key message that must be signed.
- */
-static size_t
-ephemeral_purpose_size (void)
-{
-  return sizeof (struct GNUNET_CRYPTO_EccSignaturePurpose) +
-         sizeof (struct GNUNET_TIME_AbsoluteNBO) +
-         sizeof (struct GNUNET_TIME_AbsoluteNBO) +
-         sizeof (struct GNUNET_CRYPTO_EcdhePublicKey) +
-         sizeof (struct GNUNET_PeerIdentity);
-}
-
-
-/**
- * Ephemeral key message purpose size.
- *
- * @return Size of the part of the ephemeral key message that must be signed.
- */
-static size_t
-ax_purpose_size (void)
-{
-  return sizeof (struct GNUNET_CRYPTO_EccSignaturePurpose) +
-         sizeof (struct GNUNET_CRYPTO_EcdhePublicKey);
-}
-
-
-/**
- * Size of the encrypted part of a ping message.
- *
- * @return Size of the encrypted part of a ping message.
- */
-static size_t
-ping_encryption_size (void)
-{
-  return sizeof (uint32_t);
-}
-
-
 /**
  * Get the channel's buffer. ONLY FOR NON-LOOPBACK CHANNELS!!
  *
@@ -776,85 +635,23 @@ get_connection_allowed (const struct CadetTConnection *tc)
 
 
 /**
- * Check that a ephemeral key message s well formed and correctly signed.
- *
- * @param t Tunnel on which the message came.
- * @param msg The ephemeral key message.
- *
- * @return GNUNET_OK if message is fine, GNUNET_SYSERR otherwise.
- */
-int
-check_ephemeral (struct CadetTunnel *t,
-                 const struct GNUNET_CADET_KX_Ephemeral *msg)
-{
-  /* Check message size */
-  if (ntohs (msg->header.size) != sizeof (struct GNUNET_CADET_KX_Ephemeral))
-    return GNUNET_SYSERR;
-
-  /* Check signature size */
-  if (ntohl (msg->purpose.size) != ephemeral_purpose_size ())
-    return GNUNET_SYSERR;
-
-  /* Check origin */
-  if (0 != memcmp (&msg->origin_identity,
-                   GCP_get_id (t->peer),
-                   sizeof (struct GNUNET_PeerIdentity)))
-    return GNUNET_SYSERR;
-
-  /* Check signature */
-  if (GNUNET_OK !=
-      GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_CADET_KX,
-                                  &msg->purpose,
-                                  &msg->signature,
-                                  &msg->origin_identity.public_key))
-    return GNUNET_SYSERR;
-
-  return GNUNET_OK;
-}
-
-
-/**
- * Select the best key to use for encryption (send), based on KX status.
- *
- * Normally, return the current key. If there is a KX in progress and the old
- * key is fresh enough, return the old key.
- *
- * @param t Tunnel to choose the key from.
+ * Create a new Axolotl ephemeral (ratchet) key.
  *
- * @return The optimal key to encrypt/hmac outgoing traffic.
+ * @param t Tunnel.
  */
-static const struct GNUNET_CRYPTO_SymmetricSessionKey *
-select_key (const struct CadetTunnel *t)
+static void
+new_ephemeral (struct CadetTunnel *t)
 {
-  const struct GNUNET_CRYPTO_SymmetricSessionKey *key;
-
-  if (NULL != t->kx_ctx
-      && NULL == t->kx_ctx->finish_task)
-  {
-    struct GNUNET_TIME_Relative age;
-
-    age = GNUNET_TIME_absolute_get_duration (t->kx_ctx->rekey_start_time);
-    LOG (GNUNET_ERROR_TYPE_DEBUG,
-         "  key exchange in progress, started %s ago\n",
-         GNUNET_STRINGS_relative_time_to_string (age, GNUNET_YES));
-    // FIXME make duration of old keys configurable
-    if (age.rel_value_us < GNUNET_TIME_UNIT_MINUTES.rel_value_us)
-    {
-      LOG (GNUNET_ERROR_TYPE_DEBUG, "  using old key\n");
-      key = &t->kx_ctx->e_key_old;
-    }
-    else
-    {
-      LOG (GNUNET_ERROR_TYPE_DEBUG, "  using new key (old key too old)\n");
-      key = &t->e_key;
-    }
-  }
-  else
+  GNUNET_free_non_null (t->ax->DHRs);
+  t->ax->DHRs = GNUNET_CRYPTO_ecdhe_key_create();
+  #if DUMP_KEYS_TO_STDERR
   {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "  no KX: using current key\n");
-    key = &t->e_key;
+    struct GNUNET_CRYPTO_EcdhePublicKey pub;
+    GNUNET_CRYPTO_ecdhe_key_get_public (t->ax->DHRs, &pub);
+    LOG (GNUNET_ERROR_TYPE_DEBUG, "  new DHRs generated: pub  %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &pub));
   }
-  return key;
+  #endif
 }
 
 
@@ -878,7 +675,7 @@ t_hmac (const void *plaintext, size_t size,
 
 #if DUMP_KEYS_TO_STDERR
   LOG (GNUNET_ERROR_TYPE_INFO, "  HMAC %u bytes with key %s\n", size,
-       GNUNET_h2s ((struct GNUNET_HashCode *) key));
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) key));
 #endif
   GNUNET_CRYPTO_hmac_derive_key (&auth_key, key,
                                  &iv, sizeof (iv),
@@ -887,44 +684,7 @@ t_hmac (const void *plaintext, size_t size,
                                  NULL);
   /* Two step: CADET_Hash is only 256 bits, HashCode is 512. */
   GNUNET_CRYPTO_hmac (&auth_key, plaintext, size, &hash);
-  memcpy (hmac, &hash, sizeof (*hmac));
-}
-
-
-/**
- * Encrypt daforce_newest_keyta with the tunnel key.
- *
- * @param t Tunnel whose key to use.
- * @param dst Destination for the encrypted data.
- * @param src Source of the plaintext. Can overlap with @c dst.
- * @param size Size of the plaintext.
- * @param iv Initialization Vector to use.
- * @param force_newest_key Force the use of the newest key, otherwise
- *                         CADET will use the old key when allowed.
- *                         This can happen in the case when a KX is going on
- *                         and the old one hasn't expired.
- */
-static int
-t_encrypt (struct CadetTunnel *t, void *dst, const void *src,
-           size_t size, uint32_t iv, int force_newest_key)
-{
-  struct GNUNET_CRYPTO_SymmetricInitializationVector siv;
-  const struct GNUNET_CRYPTO_SymmetricSessionKey *key;
-  size_t out_size;
-
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_encrypt start\n");
-
-  key = GNUNET_YES == force_newest_key ? &t->e_key : select_key (t);
-  #if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_INFO, "  ENC with key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) key));
-  #endif
-  GNUNET_CRYPTO_symmetric_derive_iv (&siv, key, &iv, sizeof (iv), NULL);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_encrypt IV derived\n");
-  out_size = GNUNET_CRYPTO_symmetric_encrypt (src, size, key, &siv, dst);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_encrypt end\n");
-
-  return out_size;
+  GNUNET_memcpy (hmac, &hash, sizeof (*hmac));
 }
 
 
@@ -995,6 +755,14 @@ t_ax_encrypt (struct CadetTunnel *t, void *dst, const void *src, size_t size)
 
   ax = t->ax;
 
+  ax->ratchet_counter++;
+  if (GNUNET_YES == ax->ratchet_allowed
+      && (ratchet_messages <= ax->ratchet_counter
+          || 0 == GNUNET_TIME_absolute_get_remaining (ax->ratchet_expiration).rel_value_us))
+  {
+    ax->ratchet_flag = GNUNET_YES;
+  }
+
   if (GNUNET_YES == ax->ratchet_flag)
   {
     /* Advance ratchet */
@@ -1003,7 +771,7 @@ t_ax_encrypt (struct CadetTunnel *t, void *dst, const void *src, size_t size)
     struct GNUNET_HashCode hmac;
     static const char ctx[] = "axolotl ratchet";
 
-    ax->DHRs = GNUNET_CRYPTO_ecdhe_key_create ();
+    new_ephemeral (t);
     ax->HKs = ax->NHKs;
 
     /* RK, NHKs, CKs = KDF( HMAC-HASH(RK, DH(DHRs, DHRr)) ) */
@@ -1018,18 +786,20 @@ t_ax_encrypt (struct CadetTunnel *t, void *dst, const void *src, size_t size)
     ax->PNs = ax->Ns;
     ax->Ns = 0;
     ax->ratchet_flag = GNUNET_NO;
+    ax->ratchet_allowed = GNUNET_NO;
+    ax->ratchet_counter = 0;
+    ax->ratchet_expiration =
+      GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(), ratchet_time);
   }
 
   t_hmac_derive_key (&ax->CKs, &MK, "0", 1);
   GNUNET_CRYPTO_symmetric_derive_iv (&iv, &MK, NULL, 0, NULL);
 
   #if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_INFO, "  txt: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) src));
-  LOG (GNUNET_ERROR_TYPE_INFO, "  CKs: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &ax->CKs));
-  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_ENC with key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &MK));
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "  CKs: %s\n",
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->CKs));
+  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_ENC with key %u: %s\n", ax->Ns,
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &MK));
   #endif
 
   out_size = GNUNET_CRYPTO_symmetric_encrypt (src, size, &MK, &iv, dst);
@@ -1068,22 +838,19 @@ t_ax_decrypt (struct CadetTunnel *t, void *dst, const void *src, size_t size)
   GNUNET_CRYPTO_symmetric_derive_iv (&iv, &MK, NULL, 0, NULL);
 
   #if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_INFO, "  CKr: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &ax->CKr));
-  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC with key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &MK));
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "  CKr: %s\n",
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->CKr));
+  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC with key %u: %s\n", ax->Nr,
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &MK));
   #endif
 
-  GNUNET_assert (size > sizeof (struct GNUNET_MessageHeader));
+  GNUNET_assert (size >= sizeof (struct GNUNET_MessageHeader));
   out_size = GNUNET_CRYPTO_symmetric_decrypt (src, size, &MK, &iv, dst);
   GNUNET_assert (out_size == size);
 
   t_hmac_derive_key (&ax->CKr, &ax->CKr, "1", 1);
 
   LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_ax_decrypt end\n");
-  LOG (GNUNET_ERROR_TYPE_INFO, "  txt: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) dst));
-
 
   return out_size;
 }
@@ -1109,7 +876,7 @@ t_h_encrypt (struct CadetTunnel *t, struct GNUNET_CADET_AX *msg)
 
   #if DUMP_KEYS_TO_STDERR
   LOG (GNUNET_ERROR_TYPE_INFO, "  AX_ENC_H with key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &ax->HKs));
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->HKs));
   #endif
 
   out_size = GNUNET_CRYPTO_symmetric_encrypt (&msg->Ns, AX_HEADER_SIZE,
@@ -1143,7 +910,7 @@ t_h_decrypt (struct CadetTunnel *t, const struct GNUNET_CADET_AX *src,
 
   #if DUMP_KEYS_TO_STDERR
   LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC_H with key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &ax->HKr));
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->HKr));
   #endif
 
   out_size = GNUNET_CRYPTO_symmetric_decrypt (&src->Ns, AX_HEADER_SIZE,
@@ -1151,135 +918,7 @@ t_h_decrypt (struct CadetTunnel *t, const struct GNUNET_CADET_AX *src,
 
   GNUNET_assert (AX_HEADER_SIZE == out_size);
 
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_ax_decrypt end\n");
-}
-
-
-/**
- * Decrypt and verify data with the appropriate tunnel key.
- *
- * @param key Key to use.
- * @param dst Destination for the plaintext.
- * @param src Source of the encrypted data. Can overlap with @c dst.
- * @param size Size of the encrypted data.
- * @param iv Initialization Vector to use.
- *
- * @return Size of the decrypted data, -1 if an error was encountered.
- */
-static int
-decrypt (const struct GNUNET_CRYPTO_SymmetricSessionKey *key,
-         void *dst, const void *src, size_t size, uint32_t iv)
-{
-  struct GNUNET_CRYPTO_SymmetricInitializationVector siv;
-  size_t out_size;
-
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  decrypt start\n");
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  decrypt iv\n");
-  GNUNET_CRYPTO_symmetric_derive_iv (&siv, key, &iv, sizeof (iv), NULL);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  decrypt iv done\n");
-  out_size = GNUNET_CRYPTO_symmetric_decrypt (src, size, key, &siv, dst);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  decrypt end\n");
-
-  return out_size;
-}
-
-
-/**
- * Decrypt and verify data with the most recent tunnel key.
- *
- * @param t Tunnel whose key to use.
- * @param dst Destination for the plaintext.
- * @param src Source of the encrypted data. Can overlap with @c dst.
- * @param size Size of the encrypted data.
- * @param iv Initialization Vector to use.
- *
- * @return Size of the decrypted data, -1 if an error was encountered.
- */
-static int
-t_decrypt (struct CadetTunnel *t, void *dst, const void *src,
-           size_t size, uint32_t iv)
-{
-  size_t out_size;
-
-#if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_decrypt with %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &t->d_key));
-#endif
-  if (CADET_TUNNEL_KEY_UNINITIALIZED == t->estate)
-  {
-    GNUNET_STATISTICS_update (stats, "# non decryptable data", 1, GNUNET_NO);
-    LOG (GNUNET_ERROR_TYPE_WARNING,
-         "got data on %s without a valid key\n",
-         GCT_2s (t));
-    GCT_debug (t, GNUNET_ERROR_TYPE_WARNING);
-    return -1;
-  }
-
-  out_size = decrypt (&t->d_key, dst, src, size, iv);
-
-  return out_size;
-}
-
-
-/**
- * Decrypt and verify data with the appropriate tunnel key and verify that the
- * data has not been altered since it was sent by the remote peer.
- *
- * @param t Tunnel whose key to use.
- * @param dst Destination for the plaintext.
- * @param src Source of the encrypted data. Can overlap with @c dst.
- * @param size Size of the encrypted data.
- * @param iv Initialization Vector to use.
- * @param msg_hmac HMAC of the message, cannot be NULL.
- *
- * @return Size of the decrypted data, -1 if an error was encountered.
- */
-static int
-t_decrypt_and_validate (struct CadetTunnel *t,
-                        void *dst, const void *src,
-                        size_t size, uint32_t iv,
-                        const struct GNUNET_CADET_Hash *msg_hmac)
-{
-  struct GNUNET_CRYPTO_SymmetricSessionKey *key;
-  struct GNUNET_CADET_Hash hmac;
-  int decrypted_size;
-
-  /* Try primary (newest) key */
-  key = &t->d_key;
-  decrypted_size = decrypt (key, dst, src, size, iv);
-  t_hmac (src, size, iv, key, &hmac);
-  if (0 == memcmp (msg_hmac, &hmac, sizeof (hmac)))
-    return decrypted_size;
-
-  /* If no key exchange is going on, we just failed. */
-  if (NULL == t->kx_ctx)
-  {
-    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-                "Failed checksum validation on tunnel %s with no KX\n",
-                GCT_2s (t));
-    GNUNET_STATISTICS_update (stats, "# wrong HMAC no KX", 1, GNUNET_NO);
-    return -1;
-  }
-
-  /* Try secondary key, from previous KX period. */
-  key = &t->kx_ctx->d_key_old;
-  decrypted_size = decrypt (key, dst, src, size, iv);
-  t_hmac (src, size, iv, key, &hmac);
-  if (0 == memcmp (msg_hmac, &hmac, sizeof (hmac)))
-    return decrypted_size;
-
-  /* Hail Mary, try tertiary, key, in case of parallel re-keys. */
-  key = &t->kx_ctx->d_key_old2;
-  decrypted_size = decrypt (key, dst, src, size, iv);
-  t_hmac (src, size, iv, key, &hmac);
-  if (0 == memcmp (msg_hmac, &hmac, sizeof (hmac)))
-    return decrypted_size;
-
-  GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
-              "Failed checksum validation on tunnel %s with KX\n",
-              GCT_2s (t));
-  GNUNET_STATISTICS_update (stats, "# wrong HMAC with KX", 1, GNUNET_NO);
-  return -1;
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "  t_h_decrypt end\n");
 }
 
 
@@ -1295,86 +934,170 @@ t_decrypt_and_validate (struct CadetTunnel *t,
  * @return Size of the decrypted data, -1 if an error was encountered.
  */
 static int
-try_old_ax_keys (struct CadetTunnel *t, struct GNUNET_CADET_AX *dst,
+try_old_ax_keys (struct CadetTunnel *t, void *dst,
                  const struct GNUNET_CADET_AX *src, size_t size)
 {
   struct CadetTunnelSkippedKey *key;
-  struct GNUNET_CADET_Hash hmac;
+  struct GNUNET_CADET_Hash *hmac;
   struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
+  struct GNUNET_CADET_AX plaintext_header;
+  struct GNUNET_CRYPTO_SymmetricSessionKey *valid_HK;
+  size_t esize;
   size_t res;
   size_t len;
+  unsigned int N;
 
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "Trying old keys\n");
+  hmac = &plaintext_header.hmac;
+  esize = size - sizeof (struct GNUNET_CADET_AX);
 
+  /* Find a correct Header Key */
   for (key = t->ax->skipped_head; NULL != key; key = key->next)
   {
-    t_hmac (&src->Ns, AX_HEADER_SIZE, 0, &key->HK, &hmac);
-    if (0 != memcmp (&hmac, &src->hmac, sizeof (hmac)))
+    #if DUMP_KEYS_TO_STDERR
+    LOG (GNUNET_ERROR_TYPE_DEBUG, "  Trying hmac with key %s\n",
+         GNUNET_i2s ((struct GNUNET_PeerIdentity *) &key->HK));
+    #endif
+    t_hmac (&src->Ns, AX_HEADER_SIZE + esize, 0, &key->HK, hmac);
+    if (0 == memcmp (hmac, &src->hmac, sizeof (*hmac)))
+    {
+      LOG (GNUNET_ERROR_TYPE_DEBUG, "  hmac correct\n");
+      valid_HK = &key->HK;
       break;
+    }
   }
   if (NULL == key)
     return -1;
 
+  /* Should've been checked in -cadet_connection.c handle_cadet_encrypted. */
+  GNUNET_assert (size > sizeof (struct GNUNET_CADET_AX));
+  len = size - sizeof (struct GNUNET_CADET_AX);
+  GNUNET_assert (len >= sizeof (struct GNUNET_MessageHeader));
+
+  /* Decrypt header */
+  GNUNET_CRYPTO_symmetric_derive_iv (&iv, &key->HK, NULL, 0, NULL);
+  res = GNUNET_CRYPTO_symmetric_decrypt (&src->Ns, AX_HEADER_SIZE,
+                                         &key->HK, &iv, &plaintext_header.Ns);
+  GNUNET_assert (AX_HEADER_SIZE == res);
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "  Message %u, previous: %u\n",
+       ntohl (plaintext_header.Ns), ntohl (plaintext_header.PNs));
+
+  /* Find the correct Message Key */
+  N = ntohl (plaintext_header.Ns);
+  while (NULL != key && N != key->Kn)
+    key = key->next;
+  if (NULL == key || 0 != memcmp (&key->HK, valid_HK, sizeof (*valid_HK)))
+    return -1;
+
   #if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC with skipped key %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &key->MK));
+  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC_H with skipped key %s\n",
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &key->HK));
+  LOG (GNUNET_ERROR_TYPE_INFO, "  AX_DEC with skipped key %u: %s\n",
+       key->Kn, GNUNET_i2s ((struct GNUNET_PeerIdentity *) &key->MK));
   #endif
 
-  GNUNET_assert (size > sizeof (struct GNUNET_CADET_AX));
-  len = size - sizeof (struct GNUNET_CADET_AX);
+  /* Decrypt payload */
   GNUNET_CRYPTO_symmetric_derive_iv (&iv, &key->MK, NULL, 0, NULL);
-  res = GNUNET_CRYPTO_symmetric_decrypt (&src[1], len, &key->MK, &iv, &dst[1]);
+  res = GNUNET_CRYPTO_symmetric_decrypt (&src[1], len, &key->MK, &iv, dst);
 
+  /* Remove key */
   GNUNET_CONTAINER_DLL_remove (t->ax->skipped_head, t->ax->skipped_tail, key);
   t->ax->skipped--;
-  GNUNET_free (key);
+  GNUNET_free (key); /* GNUNET_free overwrites memory with 0xbaadf00d */
 
   return res;
 }
 
 
 /**
- * Stage skipped AX keys and calculate the message key.
- *
- * Stores each HK and MK for skipped messages.
+ * Delete a key from the list of skipped keys.
+ *
+ * @param t Tunnel to delete from.
+ * @param HKr Header Key to use.
+ */
+static void
+store_skipped_key (struct CadetTunnel *t,
+                   const struct GNUNET_CRYPTO_SymmetricSessionKey *HKr)
+{
+  struct CadetTunnelSkippedKey *key;
+
+  key = GNUNET_new (struct CadetTunnelSkippedKey);
+  key->timestamp = GNUNET_TIME_absolute_get ();
+  key->Kn = t->ax->Nr;
+  key->HK = t->ax->HKr;
+  t_hmac_derive_key (&t->ax->CKr, &key->MK, "0", 1);
+  #if DUMP_KEYS_TO_STDERR
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "    storing MK for Nr %u: %s\n",
+       key->Kn, GNUNET_i2s ((struct GNUNET_PeerIdentity *) &key->MK));
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "    for CKr: %s\n",
+       GNUNET_i2s ((struct GNUNET_PeerIdentity *) &t->ax->CKr));
+  #endif
+  t_hmac_derive_key (&t->ax->CKr, &t->ax->CKr, "1", 1);
+  GNUNET_CONTAINER_DLL_insert (t->ax->skipped_head, t->ax->skipped_tail, key);
+  t->ax->Nr++;
+  t->ax->skipped++;
+}
+
+
+/**
+ * Delete a key from the list of skipped keys.
+ *
+ * @param t Tunnel to delete from.
+ * @param key Key to delete.
+ */
+static void
+delete_skipped_key (struct CadetTunnel *t, struct CadetTunnelSkippedKey *key)
+{
+  GNUNET_CONTAINER_DLL_remove (t->ax->skipped_head, t->ax->skipped_tail, key);
+  GNUNET_free (key);
+  t->ax->skipped--;
+}
+
+
+/**
+ * Stage skipped AX keys and calculate the message key.
+ *
+ * Stores each HK and MK for skipped messages.
  *
  * @param t Tunnel where to stage the keys.
  * @param HKr Header key.
- * @param Nr Current message number.
  * @param Np Received meesage number.
- * @param CKr[in/out] Chain key, gets ratcheted forward to the new state.
+ *
+ * @return GNUNET_OK if keys were stored.
+ *         GNUNET_SYSERR if an error ocurred (Np not expected).
  */
-static void
+static int
 store_ax_keys (struct CadetTunnel *t,
                const struct GNUNET_CRYPTO_SymmetricSessionKey *HKr,
-               uint32_t Nr, uint32_t Np,
-               struct GNUNET_CRYPTO_SymmetricSessionKey *CKr)
+               uint32_t Np)
 {
-  struct CadetTunnelSkippedKey *key;
-  unsigned int i;
+  int gap;
 
-  if (Np - Nr > MAX_KEY_GAP)
+
+  gap = Np - t->ax->Nr;
+  LOG (GNUNET_ERROR_TYPE_INFO, "Storing keys [%u, %u)\n", t->ax->Nr, Np);
+  if (MAX_KEY_GAP < gap)
   {
     /* Avoid DoS (forcing peer to do 2*33 chain HMAC operations) */
     /* TODO: start new key exchange on return */
     GNUNET_break_op (0);
-    return;
+    LOG (GNUNET_ERROR_TYPE_WARNING, "Got message %u, expected %u+\n",
+         Np, t->ax->Nr);
+    return GNUNET_SYSERR;
   }
-
-  for (i = Nr; i < Np; i++)
+  if (0 > gap)
   {
-    key = GNUNET_new (struct CadetTunnelSkippedKey);
-    key->timestamp = GNUNET_TIME_absolute_get ();
-    t_hmac_derive_key (CKr, &key->MK, "0", 1);
-    #if DUMP_KEYS_TO_STDERR
-    LOG (GNUNET_ERROR_TYPE_INFO, "    storing MK for Nr %u: %s\n",
-         GNUNET_h2s ((struct GNUNET_HashCode *) &key->MK));
-    LOG (GNUNET_ERROR_TYPE_INFO, "    for CKr: %s\n",
-         GNUNET_h2s ((struct GNUNET_HashCode *) &t->ax->CKr));
-    #endif
-    t_hmac_derive_key (CKr, CKr, "1", 1);
-    GNUNET_CONTAINER_DLL_insert (t->ax->skipped_head, t->ax->skipped_tail, key);
-    t->ax->skipped++;
+    /* Delayed message: don't store keys, flag to try old keys. */
+    return GNUNET_SYSERR;
   }
+
+  while (t->ax->Nr < Np)
+    store_skipped_key (t, HKr);
+
+  while (t->ax->skipped > MAX_SKIPPED_KEYS)
+    delete_skipped_key (t, t->ax->skipped_tail);
+
+  return GNUNET_OK;
 }
 
 
@@ -1396,14 +1119,13 @@ t_ax_decrypt_and_validate (struct CadetTunnel *t, void *dst,
   struct CadetTunnelAxolotl *ax;
   struct GNUNET_CADET_Hash msg_hmac;
   struct GNUNET_HashCode hmac;
-  struct GNUNET_CADET_AX *dstmsg;
+  struct GNUNET_CADET_AX plaintext_header;
   uint32_t Np;
   uint32_t PNp;
   size_t esize;
   size_t osize;
 
   ax = t->ax;
-  dstmsg = dst;
   esize = size - sizeof (struct GNUNET_CADET_AX);
 
   if (NULL == ax)
@@ -1420,21 +1142,22 @@ t_ax_decrypt_and_validate (struct CadetTunnel *t, void *dst,
     struct GNUNET_CRYPTO_EcdhePublicKey *DHRp;
 
     /* Try Next HK */
+    LOG (GNUNET_ERROR_TYPE_DEBUG, "  trying next HK\n");
     t_hmac (&src->Ns, AX_HEADER_SIZE + esize, 0, &ax->NHKr, &msg_hmac);
     if (0 != memcmp (&msg_hmac, &src->hmac, sizeof (msg_hmac)))
     {
       /* Try the skipped keys, if that fails, we're out of luck. */
       return try_old_ax_keys (t, dst, src, size);
     }
-    LOG (GNUNET_ERROR_TYPE_INFO, "next HK\n");
+    LOG (GNUNET_ERROR_TYPE_INFO, "next HK worked\n");
 
     HK = ax->HKr;
     ax->HKr = ax->NHKr;
-    t_h_decrypt (t, src, dstmsg);
-    Np = ntohl (dstmsg->Ns);
-    PNp = ntohl (dstmsg->PNs);
-    DHRp = &dstmsg->DHRs;
-    store_ax_keys (t, &HK, ax->Nr, PNp, &ax->CKr);
+    t_h_decrypt (t, src, &plaintext_header);
+    Np = ntohl (plaintext_header.Ns);
+    PNp = ntohl (plaintext_header.PNs);
+    DHRp = &plaintext_header.DHRs;
+    store_ax_keys (t, &HK, PNp);
 
     /* RKp, NHKp, CKp = KDF (HMAC-HASH (RK, DH (DHRp, DHRs))) */
     GNUNET_CRYPTO_ecc_ecdh (ax->DHRs, DHRp, &dh);
@@ -1448,21 +1171,24 @@ t_ax_decrypt_and_validate (struct CadetTunnel *t, void *dst,
     ax->CKr = keys[2];
     ax->DHRr = *DHRp;
     ax->Nr = 0;
+    ax->ratchet_allowed = GNUNET_YES;
   }
   else
   {
     LOG (GNUNET_ERROR_TYPE_DEBUG, "current HK\n");
-    t_h_decrypt (t, src, dstmsg);
-    Np = ntohl (dstmsg->Ns);
-    PNp = ntohl (dstmsg->PNs);
+    t_h_decrypt (t, src, &plaintext_header);
+    Np = ntohl (plaintext_header.Ns);
+    PNp = ntohl (plaintext_header.PNs);
   }
-
-  if (Np > ax->Nr + 1)
-    store_ax_keys (t, &ax->HKr, ax->Nr, Np, &ax->CKr);
-
-  ax->Nr = Np;
+  LOG (GNUNET_ERROR_TYPE_INFO, "  got AX Nr %u\n", Np);
+  if (Np != ax->Nr)
+    if (GNUNET_OK != store_ax_keys (t, &ax->HKr, Np))
+      /* Try the skipped keys, if that fails, we're out of luck. */
+      return try_old_ax_keys (t, dst, src, size);
 
   osize = t_ax_decrypt (t, dst, &src[1], esize);
+  ax->Nr = Np + 1;
+
   if (osize != esize)
   {
     GNUNET_break_op (0);
@@ -1473,182 +1199,6 @@ t_ax_decrypt_and_validate (struct CadetTunnel *t, void *dst,
 }
 
 
-/**
- * Create key material by doing ECDH on the local and remote ephemeral keys.
- *
- * @param key_material Where to store the key material.
- * @param ephemeral Peer's public ephemeral key.
- *
- * @return GNUNET_OK if it went fine, GNUNET_SYSERR otherwise.
- */
-static int
-derive_otr_key_material (struct GNUNET_HashCode *key_material,
-                         const struct GNUNET_CRYPTO_EcdhePublicKey *ephemeral)
-{
-  if (GNUNET_OK !=
-      GNUNET_CRYPTO_ecc_ecdh (otr_ephemeral_key, ephemeral, key_material))
-  {
-    GNUNET_break (0);
-    return GNUNET_SYSERR;
-  }
-  return GNUNET_OK;
-}
-
-
-/**
- * Create a symmetic key from the identities of both ends and the key material
- * from ECDH.
- *
- * @param key Destination for the generated key.
- * @param sender ID of the peer that will encrypt with @c key.
- * @param receiver ID of the peer that will decrypt with @c key.
- * @param key_material Hash created with ECDH with the ephemeral keys.
- */
-void
-derive_symmertic (struct GNUNET_CRYPTO_SymmetricSessionKey *key,
-                  const struct GNUNET_PeerIdentity *sender,
-                  const struct GNUNET_PeerIdentity *receiver,
-                  const struct GNUNET_HashCode *key_material)
-{
-  const char salt[] = "CADET kx salt";
-
-  GNUNET_CRYPTO_kdf (key, sizeof (struct GNUNET_CRYPTO_SymmetricSessionKey),
-                     salt, sizeof (salt),
-                     key_material, sizeof (struct GNUNET_HashCode),
-                     sender, sizeof (struct GNUNET_PeerIdentity),
-                     receiver, sizeof (struct GNUNET_PeerIdentity),
-                     NULL);
-}
-
-
-/**
- * Derive the tunnel's keys using our own and the peer's ephemeral keys.
- *
- * @param t Tunnel for which to create the keys.
- *
- * @return GNUNET_OK if successful, GNUNET_SYSERR otherwise.
- */
-static int
-create_otr_keys (struct CadetTunnel *t)
-{
-  struct GNUNET_HashCode km;
-
-  if (GNUNET_OK != derive_otr_key_material (&km, &t->peers_ephemeral_key))
-    return GNUNET_SYSERR;
-  derive_symmertic (&t->e_key, &my_full_id, GCP_get_id (t->peer), &km);
-  derive_symmertic (&t->d_key, GCP_get_id (t->peer), &my_full_id, &km);
-  #if DUMP_KEYS_TO_STDERR
-  LOG (GNUNET_ERROR_TYPE_INFO, "ME: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &otr_kx_msg.ephemeral_key));
-  LOG (GNUNET_ERROR_TYPE_INFO, "PE: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &t->peers_ephemeral_key));
-  LOG (GNUNET_ERROR_TYPE_INFO, "KM: %s\n", GNUNET_h2s (&km));
-  LOG (GNUNET_ERROR_TYPE_INFO, "EK: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &t->e_key));
-  LOG (GNUNET_ERROR_TYPE_INFO, "DK: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &t->d_key));
-  #endif
-  return GNUNET_OK;
-}
-
-
-/**
- * Create a new Key eXchange context for the tunnel.
- *
- * If the old keys were verified, keep them for old traffic. Create a new KX
- * timestamp and a new nonce.
- *
- * @param t Tunnel for which to create the KX ctx.
- *
- * @return GNUNET_OK if successful, GNUNET_SYSERR otherwise.
- */
-static int
-create_kx_ctx (struct CadetTunnel *t)
-{
-  LOG (GNUNET_ERROR_TYPE_INFO, "  new kx ctx for %s\n", GCT_2s (t));
-
-  if (NULL != t->kx_ctx)
-  {
-    if (NULL != t->kx_ctx->finish_task)
-    {
-      LOG (GNUNET_ERROR_TYPE_INFO, "  resetting exisiting finish task\n");
-      GNUNET_SCHEDULER_cancel (t->kx_ctx->finish_task);
-      t->kx_ctx->finish_task = NULL;
-    }
-  }
-  else
-  {
-    t->kx_ctx = GNUNET_new (struct CadetTunnelKXCtx);
-    t->kx_ctx->challenge = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
-                                                     UINT32_MAX);
-  }
-
-  if (CADET_TUNNEL_KEY_OK == t->estate)
-  {
-    LOG (GNUNET_ERROR_TYPE_INFO, "  backing up keys\n");
-    t->kx_ctx->d_key_old = t->d_key;
-    t->kx_ctx->e_key_old = t->e_key;
-  }
-  else
-    LOG (GNUNET_ERROR_TYPE_INFO, "  old keys not valid, not saving\n");
-  t->kx_ctx->rekey_start_time = GNUNET_TIME_absolute_get ();
-  return create_otr_keys (t);
-}
-
-
-/**
- * @brief Finish the Key eXchange and destroy the old keys.
- *
- * @param cls Closure (Tunnel for which to finish the KX).
- * @param tc Task context.
- */
-static void
-finish_kx (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
-{
-  struct CadetTunnel *t = cls;
-
-  LOG (GNUNET_ERROR_TYPE_INFO, "finish KX for %s\n", GCT_2s (t));
-
-  if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
-  {
-    LOG (GNUNET_ERROR_TYPE_INFO, "  shutdown\n");
-    return;
-  }
-
-  GNUNET_free (t->kx_ctx);
-  t->kx_ctx = NULL;
-}
-
-
-/**
- * Destroy a Key eXchange context for the tunnel. This function only schedules
- * the destruction, the freeing of the memory (and clearing of old key material)
- * happens after a delay!
- *
- * @param t Tunnel whose KX ctx to destroy.
- */
-static void
-destroy_kx_ctx (struct CadetTunnel *t)
-{
-  struct GNUNET_TIME_Relative delay;
-
-  if (NULL == t->kx_ctx || NULL != t->kx_ctx->finish_task)
-    return;
-
-  if (is_key_null (&t->kx_ctx->e_key_old))
-  {
-    t->kx_ctx->finish_task = GNUNET_SCHEDULER_add_now (finish_kx, t);
-    return;
-  }
-
-  delay = GNUNET_TIME_relative_divide (rekey_period, 4);
-  delay = GNUNET_TIME_relative_min (delay, GNUNET_TIME_UNIT_MINUTES);
-
-  t->kx_ctx->finish_task = GNUNET_SCHEDULER_add_delayed (delay, finish_kx, t);
-}
-
-
-
 /**
  * Pick a connection on which send the next data message.
  *
@@ -1757,16 +1307,12 @@ queue_data (struct CadetTunnel *t, const struct GNUNET_MessageHeader *msg)
 
   LOG (GNUNET_ERROR_TYPE_DEBUG, "queue data on Tunnel %s\n", GCT_2s (t));
 
-  if (GNUNET_YES == is_ready (t))
-  {
-    GNUNET_break (0);
-    return NULL;
-  }
+  GNUNET_assert (GNUNET_NO == is_ready (t));
 
   tqd = GNUNET_malloc (sizeof (struct CadetTunnelDelayed) + size);
 
   tqd->t = t;
-  memcpy (&tqd[1], msg, size);
+  GNUNET_memcpy (&tqd[1], msg, size);
   GNUNET_CONTAINER_DLL_insert_tail (t->tq_head, t->tq_tail, tqd);
   return tqd;
 }
@@ -1785,27 +1331,25 @@ queue_data (struct CadetTunnel *t, const struct GNUNET_MessageHeader *msg)
  * @param existing_q In case this a transmission of previously queued data,
  *                   this should be TunnelQueue given to the client.
  *                   Otherwise, NULL.
- *
  * @return Handle to cancel message.
  *         NULL if @c cont is NULL or an error happens and message is dropped.
  */
 static struct CadetTunnelQueue *
 send_prebuilt_message (const struct GNUNET_MessageHeader *message,
-                       struct CadetTunnel *t, struct CadetConnection *c,
-                       int force, GCT_sent cont, void *cont_cls,
+                       struct CadetTunnel *t,
+                       struct CadetConnection *c,
+                       int force,
+                       GCT_sent cont,
+                       void *cont_cls,
                        struct CadetTunnelQueue *existing_q)
 {
   struct GNUNET_MessageHeader *msg;
-  struct GNUNET_CADET_Encrypted *otr_msg;
   struct GNUNET_CADET_AX *ax_msg;
   struct CadetTunnelQueue *tq;
   size_t size = ntohs (message->size);
-  const uint16_t max_overhead = sizeof (struct GNUNET_CADET_Encrypted)
-                                + sizeof (struct GNUNET_CADET_AX);
-  char cbuf[max_overhead + size];
+  char cbuf[sizeof (struct GNUNET_CADET_AX) + size] GNUNET_ALIGN;
   size_t esize;
   uint32_t mid;
-  uint32_t iv;
   uint16_t type;
   int fwd;
 
@@ -1831,30 +1375,17 @@ send_prebuilt_message (const struct GNUNET_MessageHeader *message,
 
   GNUNET_assert (GNUNET_NO == GCT_is_loopback (t));
 
-  if (CADET_Axolotl == t->enc_type)
-  {
-    ax_msg = (struct GNUNET_CADET_AX *) cbuf;
-    msg = &ax_msg->header;
-    msg->size = htons (sizeof (struct GNUNET_CADET_AX) + size);
-    msg->type = htons (GNUNET_MESSAGE_TYPE_CADET_AX);
-    esize = t_ax_encrypt (t, &ax_msg[1], message, size);
-    ax_msg->Ns = htonl (t->ax->Ns++);
-    ax_msg->PNs = htonl (t->ax->PNs);
-    GNUNET_CRYPTO_ecdhe_key_get_public (t->ax->DHRs, &ax_msg->DHRs);
-    t_h_encrypt (t, ax_msg);
-    t_hmac (&ax_msg->Ns, AX_HEADER_SIZE + esize, 0, &t->ax->HKs, &ax_msg->hmac);
-  }
-  else
-  {
-    otr_msg = (struct GNUNET_CADET_Encrypted *) cbuf;
-    msg = &otr_msg->header;
-    iv = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, UINT32_MAX);
-    otr_msg->iv = iv;
-    esize = t_encrypt (t, &otr_msg[1], message, size, iv, GNUNET_NO);
-    t_hmac (&otr_msg[1], size, iv, select_key (t), &otr_msg->hmac);
-    msg->size = htons (sizeof (struct GNUNET_CADET_Encrypted) + size);
-    msg->type = htons (GNUNET_MESSAGE_TYPE_CADET_ENCRYPTED);
-  }
+  GNUNET_assert (CADET_Axolotl == t->enc_type);
+  ax_msg = (struct GNUNET_CADET_AX *) cbuf;
+  msg = &ax_msg->header;
+  msg->size = htons (sizeof (struct GNUNET_CADET_AX) + size);
+  msg->type = htons (GNUNET_MESSAGE_TYPE_CADET_AX);
+  esize = t_ax_encrypt (t, &ax_msg[1], message, size);
+  ax_msg->Ns = htonl (t->ax->Ns++);
+  ax_msg->PNs = htonl (t->ax->PNs);
+  GNUNET_CRYPTO_ecdhe_key_get_public (t->ax->DHRs, &ax_msg->DHRs);
+  t_h_encrypt (t, ax_msg);
+  t_hmac (&ax_msg->Ns, AX_HEADER_SIZE + esize, 0, &t->ax->HKs, &ax_msg->hmac);
   GNUNET_assert (esize == size);
 
   if (NULL == c)
@@ -1897,8 +1428,8 @@ send_prebuilt_message (const struct GNUNET_MessageHeader *message,
 
   if (NULL == cont)
   {
-    GNUNET_break (NULL == GCC_send_prebuilt_message (msg, type,
-                                                     mid, c, fwd, force, NULL, NULL));
+    GNUNET_break (NULL == GCC_send_prebuilt_message (msg, type, mid, c, fwd,
+                                                     force, NULL, NULL));
     return NULL;
   }
   if (NULL == existing_q)
@@ -1942,7 +1473,7 @@ send_queued_data (struct CadetTunnel *t)
 
   if (GNUNET_NO == is_ready (t))
   {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "  not ready yet: %s/%s\n",
+    LOG (GNUNET_ERROR_TYPE_WARNING, "  not ready yet: %s/%s\n",
          estate2s (t->estate), cstate2s (t->cstate));
     return;
   }
@@ -1967,25 +1498,27 @@ send_queued_data (struct CadetTunnel *t)
 
 
 /**
- * Callback called when a queued message is sent.
+ * @brief Resend the AX KX until we complete the handshake.
  *
- * @param cls Closure.
- * @param c Connection this message was on.
- * @param type Type of message sent.
- * @param fwd Was this a FWD going message?
- * @param size Size of the message.
+ * @param cls Closure (tunnel).
  */
 static void
-ephm_sent (void *cls,
-         struct CadetConnection *c,
-         struct CadetConnectionQueue *q,
-         uint16_t type, int fwd, size_t size)
+ax_kx_resend (void *cls)
 {
   struct CadetTunnel *t = cls;
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "ephemeral sent %s\n", GC_m2s (type));
-  t->ephm_h = NULL;
+
+  t->rekey_task = NULL;
+  if (CADET_TUNNEL_KEY_OK == t->estate)
+  {
+    /* Should have been canceled on estate change */
+    GNUNET_break (0);
+    return;
+  }
+
+  GCT_send_ax_kx (t, CADET_TUNNEL_KEY_SENT >= t->estate);
 }
 
+
 /**
  * Callback called when a queued message is sent.
  *
@@ -1996,17 +1529,33 @@ ephm_sent (void *cls,
  * @param size Size of the message.
  */
 static void
-pong_sent (void *cls,
+ephm_sent (void *cls,
            struct CadetConnection *c,
            struct CadetConnectionQueue *q,
            uint16_t type, int fwd, size_t size)
 {
   struct CadetTunnel *t = cls;
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "pong_sent %s\n", GC_m2s (type));
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "ephemeral sent %s\n", GC_m2s (type));
+
+  t->ephm_h = NULL;
 
-  t->pong_h = NULL;
+  if (CADET_TUNNEL_KEY_OK == t->estate)
+    return;
+
+  if (CADET_Axolotl == t->enc_type)
+  {
+    if (NULL != t->rekey_task)
+    {
+      GNUNET_break (0);
+      GCT_debug (t, GNUNET_ERROR_TYPE_WARNING);
+      GNUNET_SCHEDULER_cancel (t->rekey_task);
+    }
+    t->rekey_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_SECONDS,
+                                                  &ax_kx_resend, t);
+  }
 }
 
+
 /**
  * Sends key exchange message on a tunnel, choosing the best connection.
  * Should not be called on loopback tunnels.
@@ -2051,7 +1600,6 @@ send_kx (struct CadetTunnel *t,
     {
       GNUNET_break (0);
       GCT_debug (t, GNUNET_ERROR_TYPE_ERROR);
-      GCP_debug (t->peer, GNUNET_ERROR_TYPE_ERROR);
     }
     return NULL;
   }
@@ -2071,243 +1619,21 @@ send_kx (struct CadetTunnel *t,
   }
   switch (type)
   {
-    case GNUNET_MESSAGE_TYPE_CADET_KX_EPHEMERAL:
     case GNUNET_MESSAGE_TYPE_CADET_AX_KX:
       GNUNET_assert (NULL == t->ephm_h);
       cont = &ephm_sent;
-      break;
-    case GNUNET_MESSAGE_TYPE_CADET_KX_PONG:
-      GNUNET_assert (NULL == t->pong_h);
-      cont = &pong_sent;
-      break;
-
-    default:
-      LOG (GNUNET_ERROR_TYPE_DEBUG, "unkown type %s\n", GC_m2s (type));
-      GNUNET_assert (0);
-  }
-  memcpy (&msg[1], message, size);
-
-  fwd = GCC_is_origin (c, GNUNET_YES);
-
-  return GCC_send_prebuilt_message (&msg->header, type, 0, c,
-                                    fwd, GNUNET_YES,
-                                    cont, t);
-}
-
-
-/**
- * Send the ephemeral key on a tunnel.
- *
- * @param t Tunnel on which to send the key.
- */
-static void
-send_ephemeral (struct CadetTunnel *t)
-{
-  LOG (GNUNET_ERROR_TYPE_INFO, "===> EPHM for %s\n", GCT_2s (t));
-  if (NULL != t->ephm_h)
-  {
-    LOG (GNUNET_ERROR_TYPE_INFO, "     already queued\n");
-    return;
-  }
-
-  otr_kx_msg.sender_status = htonl (t->estate);
-  otr_kx_msg.iv = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, UINT32_MAX);
-  otr_kx_msg.nonce = t->kx_ctx->challenge;
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  send nonce c %u\n", otr_kx_msg.nonce);
-  t_encrypt (t, &otr_kx_msg.nonce, &otr_kx_msg.nonce,
-             ping_encryption_size(), otr_kx_msg.iv, GNUNET_YES);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  send nonce e %u\n", otr_kx_msg.nonce);
-  t->ephm_h = send_kx (t, &otr_kx_msg.header);
-}
-
-
-/**
- * Send a pong message on a tunnel.
- *d_
- * @param t Tunnel on which to send the pong.
- * @param challenge Value sent in the ping that we have to send back.
- */
-static void
-send_pong (struct CadetTunnel *t, uint32_t challenge)
-{
-  struct GNUNET_CADET_KX_Pong msg;
-
-  LOG (GNUNET_ERROR_TYPE_INFO, "===> PONG for %s\n", GCT_2s (t));
-  if (NULL != t->pong_h)
-  {
-    LOG (GNUNET_ERROR_TYPE_INFO, "     already queued\n");
-    return;
-  }
-  msg.header.size = htons (sizeof (msg));
-  msg.header.type = htons (GNUNET_MESSAGE_TYPE_CADET_KX_PONG);
-  msg.iv = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, UINT32_MAX);
-  msg.nonce = challenge;
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  sending %u\n", msg.nonce);
-  t_encrypt (t, &msg.nonce, &msg.nonce,
-             sizeof (msg.nonce), msg.iv, GNUNET_YES);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  e sending %u\n", msg.nonce);
-
-  t->pong_h = send_kx (t, &msg.header);
-}
-
-
-/**
- * Initiate a rekey with the remote peer.
- *
- * @param cls Closure (tunnel).
- * @param tc TaskContext.
- */
-static void
-rekey_tunnel (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
-{
-  struct CadetTunnel *t = cls;
-
-  t->rekey_task = NULL;
-
-  LOG (GNUNET_ERROR_TYPE_INFO, "Re-key Tunnel %s\n", GCT_2s (t));
-  if (NULL != tc && 0 != (GNUNET_SCHEDULER_REASON_SHUTDOWN & tc->reason))
-    return;
-
-  GNUNET_assert (NULL != t->kx_ctx);
-  struct GNUNET_TIME_Relative duration;
-
-  duration = GNUNET_TIME_absolute_get_duration (t->kx_ctx->rekey_start_time);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, " kx started %s ago\n",
-        GNUNET_STRINGS_relative_time_to_string (duration, GNUNET_YES));
-
-  // FIXME make duration of old keys configurable
-  if (duration.rel_value_us >= GNUNET_TIME_UNIT_MINUTES.rel_value_us)
-  {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, " deleting old keys\n");
-    memset (&t->kx_ctx->d_key_old, 0, sizeof (t->kx_ctx->d_key_old));
-    memset (&t->kx_ctx->e_key_old, 0, sizeof (t->kx_ctx->e_key_old));
-  }
-
-  send_ephemeral (t);
-
-  switch (t->estate)
-  {
-    case CADET_TUNNEL_KEY_UNINITIALIZED:
-      GCT_change_estate (t, CADET_TUNNEL_KEY_SENT);
-      break;
-
-    case CADET_TUNNEL_KEY_SENT:
-      break;
-
-    case CADET_TUNNEL_KEY_OK:
-      /* Inconsistent!
-       * - state should have changed during rekey_iterator
-       * - task should have been canceled at pong_handle
-       */
-      GNUNET_break (0);
-      GCT_change_estate (t, CADET_TUNNEL_KEY_REKEY);
-      break;
-
-    case CADET_TUNNEL_KEY_PING:
-    case CADET_TUNNEL_KEY_REKEY:
-      break;
-
-    default:
-      LOG (GNUNET_ERROR_TYPE_DEBUG, "Unexpected state %u\n", t->estate);
-  }
-
-  // FIXME exponential backoff
-  struct GNUNET_TIME_Relative delay;
-
-  delay = GNUNET_TIME_relative_divide (rekey_period, 16);
-  delay = GNUNET_TIME_relative_min (delay, REKEY_WAIT);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "  next call in %s\n",
-       GNUNET_STRINGS_relative_time_to_string (delay, GNUNET_YES));
-  t->rekey_task = GNUNET_SCHEDULER_add_delayed (delay, &rekey_tunnel, t);
-}
-
-
-/**
- * Our ephemeral key has changed, create new session key on all tunnels.
- *
- * Each tunnel will start the Key Exchange with a random delay between
- * 0 and number_of_tunnels*100 milliseconds, so there are 10 key exchanges
- * per second, on average.
- *
- * @param cls Closure (size of the hashmap).
- * @param key Current public key.
- * @param value Value in the hash map (tunnel).
- *
- * @return #GNUNET_YES, so we should continue to iterate,
- */
-static int
-rekey_iterator (void *cls,
-                const struct GNUNET_PeerIdentity *key,
-                void *value)
-{
-  struct CadetTunnel *t = value;
-  struct GNUNET_TIME_Relative delay;
-  long n = (long) cls;
-  uint32_t r;
-
-  if (NULL != t->rekey_task)
-    return GNUNET_YES;
-
-  if (GNUNET_YES == GCT_is_loopback (t))
-    return GNUNET_YES;
-
-  if (CADET_OTR != t->enc_type)
-    return GNUNET_YES;
-
-  r = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, (uint32_t) n * 100);
-  delay = GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MILLISECONDS, r);
-  t->rekey_task = GNUNET_SCHEDULER_add_delayed (delay, &rekey_tunnel, t);
-  if (GNUNET_OK == create_kx_ctx (t))
-    GCT_change_estate (t, CADET_TUNNEL_KEY_REKEY);
-  else
-  {
-    GNUNET_break (0);
-    // FIXME restart kx
+      break;
+    default:
+      LOG (GNUNET_ERROR_TYPE_DEBUG, "unkown type %s\n", GC_m2s (type));
+      GNUNET_assert (0);
   }
+  GNUNET_memcpy (&msg[1], message, size);
 
-  return GNUNET_YES;
-}
-
-
-/**
- * Create a new ephemeral key and key message, schedule next rekeying.
- *
- * @param cls Closure (unused).
- * @param tc TaskContext.
- */
-static void
-global_otr_rekey (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
-{
-  struct GNUNET_TIME_Absolute time;
-  long n;
-
-  rekey_task = NULL;
-
-  if (0 != (GNUNET_SCHEDULER_REASON_SHUTDOWN & tc->reason))
-    return;
-
-  GNUNET_free_non_null (otr_ephemeral_key);
-  otr_ephemeral_key = GNUNET_CRYPTO_ecdhe_key_create ();
-
-  time = GNUNET_TIME_absolute_get ();
-  otr_kx_msg.creation_time = GNUNET_TIME_absolute_hton (time);
-  time = GNUNET_TIME_absolute_add (time, rekey_period);
-  time = GNUNET_TIME_absolute_add (time, GNUNET_TIME_UNIT_MINUTES);
-  otr_kx_msg.expiration_time = GNUNET_TIME_absolute_hton (time);
-  GNUNET_CRYPTO_ecdhe_key_get_public (otr_ephemeral_key, &otr_kx_msg.ephemeral_key);
-  LOG (GNUNET_ERROR_TYPE_INFO, "GLOBAL OTR RE-KEY, NEW EPHM: %s\n",
-       GNUNET_h2s ((struct GNUNET_HashCode *) &otr_kx_msg.ephemeral_key));
-
-  GNUNET_assert (GNUNET_OK ==
-                 GNUNET_CRYPTO_eddsa_sign (id_key,
-                                           &otr_kx_msg.purpose,
-                                           &otr_kx_msg.signature));
-
-  n = (long) GNUNET_CONTAINER_multipeermap_size (tunnels);
-  GNUNET_CONTAINER_multipeermap_iterate (tunnels, &rekey_iterator, (void *) n);
+  fwd = GCC_is_origin (c, GNUNET_YES);
 
-  rekey_task = GNUNET_SCHEDULER_add_delayed (rekey_period,
-                                             &global_otr_rekey, NULL);
+  return GCC_send_prebuilt_message (&msg->header, type, 0, c,
+                                    fwd, GNUNET_YES,
+                                    cont, t);
 }
 
 
@@ -2327,7 +1653,8 @@ destroy_iterator (void *cls,
 {
   struct CadetTunnel *t = value;
 
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "GCT_shutdown destroying tunnel at %p\n", t);
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "GCT_shutdown destroying tunnel at %p\n", t);
   GCT_destroy (t);
   return GNUNET_YES;
 }
@@ -2372,7 +1699,9 @@ handle_data (struct CadetTunnel *t,
              int fwd)
 {
   struct CadetChannel *ch;
+  char buf[128];
   size_t size;
+  uint16_t type;
 
   /* Check size */
   size = ntohs (msg->header.size);
@@ -2383,8 +1712,11 @@ handle_data (struct CadetTunnel *t,
     GNUNET_break (0);
     return;
   }
-  LOG (GNUNET_ERROR_TYPE_DEBUG, " payload of type %s\n",
-              GC_m2s (ntohs (msg[1].header.type)));
+  type = ntohs (msg[1].header.type);
+  LOG (GNUNET_ERROR_TYPE_DEBUG, " payload of type %s\n", GC_m2s (type));
+  SPRINTF (buf, "# received payload of type %hu", type);
+  GNUNET_STATISTICS_update (stats, buf, 1, GNUNET_NO);
+
 
   /* Check channel */
   ch = GCT_get_channel (t, ntohl (msg->chid));
@@ -2392,8 +1724,7 @@ handle_data (struct CadetTunnel *t,
   {
     GNUNET_STATISTICS_update (stats, "# data on unknown channel",
                               1, GNUNET_NO);
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "WARNING channel 0x%X unknown\n",
-         ntohl (msg->chid));
+    LOG (GNUNET_ERROR_TYPE_DEBUG, "channel 0x%X unknown\n", ntohl (msg->chid));
     send_channel_destroy (t, ntohl (msg->chid));
     return;
   }
@@ -2446,8 +1777,8 @@ handle_data_ack (struct CadetTunnel *t,
 /**
  * Handle channel create.
  *
- * @param t Tunnel on which the data came.
- * @param msg Data message.
+ * @param t Tunnel on which the message came.
+ * @param msg ChannelCreate message.
  */
 static void
 handle_ch_create (struct CadetTunnel *t,
@@ -2460,7 +1791,7 @@ handle_ch_create (struct CadetTunnel *t,
   size = ntohs (msg->header.size);
   if (size != sizeof (struct GNUNET_CADET_ChannelCreate))
   {
-    GNUNET_break (0);
+    GNUNET_break_op (0);
     return;
   }
 
@@ -2593,19 +1924,6 @@ handle_ch_destroy (struct CadetTunnel *t,
 }
 
 
-/**
- * Create a new Axolotl ephemeral (ratchet) key.
- *
- * @param t Tunnel.
- */
-static void
-new_ephemeral (struct CadetTunnel *t)
-{
-  GNUNET_free_non_null (t->ax->DHRs);
-  t->ax->DHRs = GNUNET_CRYPTO_ecdhe_key_create();
-}
-
-
 /**
  * Free Axolotl data.
  *
@@ -2619,142 +1937,23 @@ destroy_ax (struct CadetTunnel *t)
 
   GNUNET_free_non_null (t->ax->DHRs);
   GNUNET_free_non_null (t->ax->kx_0);
+  while (NULL != t->ax->skipped_head)
+    delete_skipped_key (t, t->ax->skipped_head);
+  GNUNET_assert (0 == t->ax->skipped);
 
   GNUNET_free (t->ax);
   t->ax = NULL;
-}
-
-
-
-/**
- * The peer's ephemeral key has changed: update the symmetrical keys.
- *
- * @param t Tunnel this message came on.
- * @param msg Key eXchange message.
- */
-static void
-handle_ephemeral (struct CadetTunnel *t,
-                  const struct GNUNET_CADET_KX_Ephemeral *msg)
-{
-  LOG (GNUNET_ERROR_TYPE_INFO, "<=== EPHM for %s\n", GCT_2s (t));
-
-  if (GNUNET_OK != check_ephemeral (t, msg))
-  {
-    GNUNET_break_op (0);
-    return;
-  }
-
-  /* If we get a proper OTR-style ephemeral, fallback to old crypto. */
-  if (NULL != t->ax)
-  {
-    destroy_ax (t);
-    t->enc_type = CADET_OTR;
-    if (NULL != t->rekey_task)
-      GNUNET_SCHEDULER_cancel (t->rekey_task);
-    if (GNUNET_OK != create_kx_ctx (t))
-    {
-      // FIXME restart kx
-      GNUNET_break (0);
-      return;
-    }
-    rekey_tunnel (t, NULL);
-  }
-
-  /**
-   * If the key is different from what we know, derive the new E/D keys.
-   * Else destroy the rekey ctx (duplicate EPHM after successful KX).
-   */
-  if (0 != memcmp (&t->peers_ephemeral_key, &msg->ephemeral_key,
-                   sizeof (msg->ephemeral_key)))
-  {
-    #if DUMP_KEYS_TO_STDERR
-    LOG (GNUNET_ERROR_TYPE_INFO, "OLD: %s\n",
-         GNUNET_h2s ((struct GNUNET_HashCode *) &t->peers_ephemeral_key));
-    LOG (GNUNET_ERROR_TYPE_INFO, "NEW: %s\n",
-         GNUNET_h2s ((struct GNUNET_HashCode *) &msg->ephemeral_key));
-    #endif
-    t->peers_ephemeral_key = msg->ephemeral_key;
-
-    if (GNUNET_OK != create_kx_ctx (t))
-    {
-      // FIXME restart kx
-      GNUNET_break (0);
-      return;
-    }
-
-    if (CADET_TUNNEL_KEY_OK == t->estate)
-    {
-      GCT_change_estate (t, CADET_TUNNEL_KEY_REKEY);
-    }
-    if (NULL != t->rekey_task)
-      GNUNET_SCHEDULER_cancel (t->rekey_task);
-    t->rekey_task = GNUNET_SCHEDULER_add_now (rekey_tunnel, t);
-  }
-  if (CADET_TUNNEL_KEY_SENT == t->estate)
-  {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "  our key was sent, sending challenge\n");
-    send_ephemeral (t);
-    GCT_change_estate (t, CADET_TUNNEL_KEY_PING);
-  }
-
-  if (CADET_TUNNEL_KEY_UNINITIALIZED != ntohl(msg->sender_status))
-  {
-    uint32_t nonce;
-
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "  recv nonce e %u\n", msg->nonce);
-    t_decrypt (t, &nonce, &msg->nonce, ping_encryption_size (), msg->iv);
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "  recv nonce c %u\n", nonce);
-    send_pong (t, nonce);
-  }
-}
-
-
-/**
- * Peer has answer to our challenge.
- * If answer is successful, consider the key exchange finished and clean
- * up all related state.
- *
- * @param t Tunnel this message came on.
- * @param msg Key eXchange Pong message.
- */
-static void
-handle_pong (struct CadetTunnel *t, const struct GNUNET_CADET_KX_Pong *msg)
-{
-  uint32_t challenge;
 
-  LOG (GNUNET_ERROR_TYPE_INFO, "<=== PONG for %s\n", GCT_2s (t));
-  if (NULL == t->rekey_task)
-  {
-    GNUNET_STATISTICS_update (stats, "# duplicate PONG messages", 1, GNUNET_NO);
-    return;
-  }
-  if (NULL == t->kx_ctx)
+  if (NULL != t->rekey_task)
   {
-    GNUNET_STATISTICS_update (stats, "# stray PONG messages", 1, GNUNET_NO);
-    return;
+    GNUNET_SCHEDULER_cancel (t->rekey_task);
+    t->rekey_task = NULL;
   }
-
-  t_decrypt (t, &challenge, &msg->nonce, sizeof (uint32_t), msg->iv);
-  if (challenge != t->kx_ctx->challenge)
+  if (NULL != t->ephm_h)
   {
-    LOG (GNUNET_ERROR_TYPE_WARNING, "Wrong PONG challenge on %s\n", GCT_2s (t));
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "PONG: %u (e: %u). Expected: %u.\n",
-         challenge, msg->nonce, t->kx_ctx->challenge);
-    send_ephemeral (t);
-    return;
+    GCC_cancel (t->ephm_h);
+    t->ephm_h = NULL;
   }
-  GNUNET_SCHEDULER_cancel (t->rekey_task);
-  t->rekey_task = NULL;
-
-  /* Don't free the old keys right away, but after a delay.
-   * Rationale: the KX could have happened over a very fast connection,
-   * with payload traffic still signed with the old key stuck in a slower
-   * connection.
-   * Don't keep the keys longer than 1/4 the rekey period, and no longer than
-   * one minute.
-   */
-  destroy_kx_ctx (t);
-  GCT_change_estate (t, CADET_TUNNEL_KEY_OK);
 }
 
 
@@ -2770,28 +1969,19 @@ handle_kx_ax (struct CadetTunnel *t, const struct GNUNET_CADET_AX_KX *msg)
   struct CadetTunnelAxolotl *ax;
   struct GNUNET_HashCode key_material[3];
   struct GNUNET_CRYPTO_SymmetricSessionKey keys[5];
-  const struct GNUNET_CRYPTO_EcdhePublicKey *pub;
-  const struct GNUNET_CRYPTO_EcdhePrivateKey *priv;
   const char salt[] = "CADET Axolotl salt";
   const struct GNUNET_PeerIdentity *pid;
   int am_I_alice;
 
-  LOG (GNUNET_ERROR_TYPE_INFO, "<=== AX_KX on %s\n", GCT_2s (t));
+  LOG (GNUNET_ERROR_TYPE_INFO, "<== {     AX_KX} on %s\n", GCT_2s (t));
 
   if (NULL == t->ax)
   {
     /* Something is wrong if ax is NULL. Whose fault it is? */
-    GNUNET_break_op (CADET_OTR == t->enc_type);
     GNUNET_break (CADET_Axolotl == t->enc_type);
     return;
   }
-
-  if (GNUNET_OK != GCP_check_key (t->peer, &msg->permanent_key,
-                                  &msg->purpose, &msg->signature))
-  {
-    GNUNET_break_op (0);
-    return;
-  }
+  ax = t->ax;
 
   pid = GCT_get_destination (t);
   if (0 > GNUNET_CRYPTO_cmp_peer_identity (&my_full_id, pid))
@@ -2804,42 +1994,62 @@ handle_kx_ax (struct CadetTunnel *t, const struct GNUNET_CADET_AX_KX *msg)
     return;
   }
 
+  if (0 != (GNUNET_CADET_AX_KX_FLAG_FORCE_REPLY & ntohl (msg->flags)))
+  {
+    if (NULL != t->rekey_task)
+    {
+      GNUNET_SCHEDULER_cancel (t->rekey_task);
+      t->rekey_task = NULL;
+    }
+    GCT_send_ax_kx (t, GNUNET_NO);
+  }
+
+  if (0 == memcmp (&ax->DHRr, &msg->ratchet_key, sizeof(msg->ratchet_key)))
+  {
+    LOG (GNUNET_ERROR_TYPE_INFO, " known ratchet key, exit\n");
+    return;
+  }
+
   LOG (GNUNET_ERROR_TYPE_INFO, " is Alice? %s\n", am_I_alice ? "YES" : "NO");
 
-  ax = t->ax;
   ax->DHRr = msg->ratchet_key;
-  ax->DHIr = msg->permanent_key;
 
   /* ECDH A B0 */
   if (GNUNET_YES == am_I_alice)
   {
-    priv = ax_key;                                              /* A */
-    pub = &msg->ephemeral_key;                                  /* B0 */
+    GNUNET_CRYPTO_eddsa_ecdh (id_key,              /* A */
+                              &msg->ephemeral_key, /* B0 */
+                              &key_material[0]);
   }
   else
   {
-    priv = ax->kx_0;                                            /* B0 */
-    pub = &ax->DHIr;                                            /* A */
+    GNUNET_CRYPTO_ecdh_eddsa (ax->kx_0,            /* B0 */
+                              &pid->public_key,    /* A */
+                              &key_material[0]);
   }
-  GNUNET_CRYPTO_ecc_ecdh (priv, pub, &key_material[0]);
 
   /* ECDH A0 B */
   if (GNUNET_YES == am_I_alice)
   {
-    priv = ax->kx_0;                                            /* A0 */
-    pub = &ax->DHIr;                                            /* B */
+    GNUNET_CRYPTO_ecdh_eddsa (ax->kx_0,            /* A0 */
+                              &pid->public_key,    /* B */
+                              &key_material[1]);
   }
   else
   {
-    priv = ax_key;                                              /* B */
-    pub = &msg->ephemeral_key;                                  /* A0 */
+    GNUNET_CRYPTO_eddsa_ecdh (id_key,              /* A */
+                              &msg->ephemeral_key, /* B0 */
+                              &key_material[1]);
+
+
   }
-  GNUNET_CRYPTO_ecc_ecdh (priv, pub, &key_material[1]);
 
-  /* ECDH A0 B0*/
-  priv = ax->kx_0;                                              /* A0 or B0 */
-  pub = &msg->ephemeral_key;                                    /* B0 or A0 */
-  GNUNET_CRYPTO_ecc_ecdh (priv, pub, &key_material[2]);
+  /* ECDH A0 B0 */
+  /* (This is the triple-DH, we could probably safely skip this,
+     as A0/B0 are already in the key material.) */
+  GNUNET_CRYPTO_ecc_ecdh (ax->kx_0,             /* A0 or B0 */
+                          &msg->ephemeral_key,  /* B0 or A0 */
+                          &key_material[2]);
 
   #if DUMP_KEYS_TO_STDERR
   {
@@ -2855,6 +2065,11 @@ handle_kx_ax (struct CadetTunnel *t, const struct GNUNET_CADET_AX_KX *msg)
                      salt, sizeof (salt),
                      &key_material, sizeof (key_material), NULL);
 
+  if (0 == memcmp (&ax->RK, &keys[0], sizeof(ax->RK)))
+  {
+    LOG (GNUNET_ERROR_TYPE_INFO, " known handshake key, exit\n");
+    return;
+  }
   ax->RK = keys[0];
   if (GNUNET_YES == am_I_alice)
   {
@@ -2871,8 +2086,16 @@ handle_kx_ax (struct CadetTunnel *t, const struct GNUNET_CADET_AX_KX *msg)
     ax->NHKs = keys[3];
     ax->CKs = keys[4];
     ax->ratchet_flag = GNUNET_NO;
+    ax->ratchet_allowed = GNUNET_NO;
+    ax->ratchet_counter = 0;
+    ax->ratchet_expiration =
+      GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get(), ratchet_time);
   }
-  GCT_change_estate (t, CADET_TUNNEL_KEY_OK);
+  ax->PNs = 0;
+  ax->Nr = 0;
+  ax->Ns = 0;
+  GCT_change_estate (t, CADET_TUNNEL_KEY_PING);
+  send_queued_data (t);
 }
 
 
@@ -2893,9 +2116,12 @@ handle_decrypted (struct CadetTunnel *t,
                   int fwd)
 {
   uint16_t type;
+  char buf[256];
 
   type = ntohs (msgh->type);
-  LOG (GNUNET_ERROR_TYPE_INFO, "<=== %s on %s\n", GC_m2s (type), GCT_2s (t));
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "<-- %s on %s\n", GC_m2s (type), GCT_2s (t));
+  SPRINTF (buf, "# received encrypted of type %hu (%s)", type, GC_m2s (type));
+  GNUNET_STATISTICS_update (stats, buf, 1, GNUNET_NO);
 
   switch (type)
   {
@@ -2938,6 +2164,7 @@ handle_decrypted (struct CadetTunnel *t,
   }
 }
 
+
 /******************************************************************************/
 /********************************    API    ***********************************/
 /******************************************************************************/
@@ -2954,48 +2181,58 @@ GCT_handle_encrypted (struct CadetTunnel *t,
 {
   uint16_t size = ntohs (msg->size);
   char cbuf [size];
-  size_t payload_size;
   int decrypted_size;
   uint16_t type;
-  struct GNUNET_MessageHeader *msgh;
+  const struct GNUNET_MessageHeader *msgh;
   unsigned int off;
 
   type = ntohs (msg->type);
-  if (GNUNET_MESSAGE_TYPE_CADET_ENCRYPTED == type)
-  {
-    const struct GNUNET_CADET_Encrypted *emsg;
-
-    emsg = (struct GNUNET_CADET_Encrypted *) msg;
-    payload_size = size - sizeof (struct GNUNET_CADET_Encrypted);
-    decrypted_size = t_decrypt_and_validate (t, cbuf, &emsg[1], payload_size,
-                                             emsg->iv, &emsg->hmac);
-  }
-  else if (GNUNET_MESSAGE_TYPE_CADET_AX == type)
+  switch (type)
   {
-    const struct GNUNET_CADET_AX *emsg;
+  case GNUNET_MESSAGE_TYPE_CADET_AX:
+    {
+      const struct GNUNET_CADET_AX *emsg;
 
-    emsg = (struct GNUNET_CADET_AX *) msg;
-    decrypted_size = t_ax_decrypt_and_validate (t, cbuf, emsg, size);
+      GNUNET_STATISTICS_update (stats, "# received Axolotl", 1, GNUNET_NO);
+      emsg = (const struct GNUNET_CADET_AX *) msg;
+      decrypted_size = t_ax_decrypt_and_validate (t, cbuf, emsg, size);
+    }
+    break;
+  default:
+    GNUNET_break_op (0);
+    return;
   }
 
   if (-1 == decrypted_size)
   {
     GNUNET_break_op (0);
+    GNUNET_STATISTICS_update (stats, "# unable to decrypt", 1, GNUNET_NO);
+    LOG (GNUNET_ERROR_TYPE_WARNING, "Wrong crypto on tunnel %s\n", GCT_2s (t));
+    GCT_debug (t, GNUNET_ERROR_TYPE_WARNING);
     return;
   }
+  GCT_change_estate (t, CADET_TUNNEL_KEY_OK);
 
+  /* FIXME: this is bad, as the structs returned from
+     this loop may be unaligned, see util's MST for
+     how to do this right. */
   off = 0;
-  while (off < decrypted_size)
+  while (off + sizeof (struct GNUNET_MessageHeader) <= decrypted_size)
   {
     uint16_t msize;
 
-    msgh = (struct GNUNET_MessageHeader *) &cbuf[off];
+    msgh = (const struct GNUNET_MessageHeader *) &cbuf[off];
     msize = ntohs (msgh->size);
     if (msize < sizeof (struct GNUNET_MessageHeader))
     {
       GNUNET_break_op (0);
       return;
     }
+    if (off + msize < decrypted_size)
+    {
+      GNUNET_break_op (0);
+      return;
+    }
     handle_decrypted (t, msgh, GNUNET_SYSERR);
     off += msize;
   }
@@ -3007,29 +2244,27 @@ GCT_handle_encrypted (struct CadetTunnel *t,
  *
  * @param t Tunnel on which the message came.
  * @param message Payload of KX message.
+ *
+ * FIXME: not needed anymore
+ *  - substitute with call to kx_ax
+ *  - eliminate encapsulation
  */
 void
 GCT_handle_kx (struct CadetTunnel *t,
                const struct GNUNET_MessageHeader *message)
 {
   uint16_t type;
+  char buf[256];
 
   type = ntohs (message->type);
   LOG (GNUNET_ERROR_TYPE_DEBUG, "kx message received: %s\n", GC_m2s (type));
+  sprintf (buf, "# received KX of type %hu (%s)", type, GC_m2s (type));
+  GNUNET_STATISTICS_update (stats, buf, 1, GNUNET_NO);
   switch (type)
   {
-    case GNUNET_MESSAGE_TYPE_CADET_KX_EPHEMERAL:
-      handle_ephemeral (t, (const struct GNUNET_CADET_KX_Ephemeral *) message);
-      break;
-
-    case GNUNET_MESSAGE_TYPE_CADET_KX_PONG:
-      handle_pong (t, (const struct GNUNET_CADET_KX_Pong *) message);
-      break;
-
     case GNUNET_MESSAGE_TYPE_CADET_AX_KX:
       handle_kx_ax (t, (const struct GNUNET_CADET_AX_KX *) message);
       break;
-
     default:
       GNUNET_break_op (0);
       LOG (GNUNET_ERROR_TYPE_WARNING, "kx message %s unknown\n", GC_m2s (type));
@@ -3046,49 +2281,41 @@ void
 GCT_init (const struct GNUNET_CONFIGURATION_Handle *c,
           const struct GNUNET_CRYPTO_EddsaPrivateKey *key)
 {
-  int expected_overhead;
+  unsigned int expected_overhead;
 
   LOG (GNUNET_ERROR_TYPE_DEBUG, "init\n");
 
   expected_overhead = 0;
-  expected_overhead += sizeof (struct GNUNET_CADET_Encrypted);
+  expected_overhead += sizeof (struct GNUNET_CADET_AX);
   expected_overhead += sizeof (struct GNUNET_CADET_Data);
   expected_overhead += sizeof (struct GNUNET_CADET_ACK);
   GNUNET_assert (GNUNET_CONSTANTS_CADET_P2P_OVERHEAD == expected_overhead);
 
   if (GNUNET_OK !=
-      GNUNET_CONFIGURATION_get_value_number (c, "CADET", "DEFAULT_TTL",
-                                             &default_ttl))
+      GNUNET_CONFIGURATION_get_value_number (c,
+                                             "CADET",
+                                             "RATCHET_MESSAGES",
+                                             &ratchet_messages))
   {
     GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_WARNING,
-                               "CADET", "DEFAULT_TTL", "USING DEFAULT");
-    default_ttl = 64;
+                               "CADET",
+                               "RATCHET_MESSAGES",
+                               "USING DEFAULT");
+    ratchet_messages = 64;
   }
   if (GNUNET_OK !=
-      GNUNET_CONFIGURATION_get_value_time (c, "CADET", "REKEY_PERIOD",
-                                           &rekey_period))
+      GNUNET_CONFIGURATION_get_value_time (c,
+                                           "CADET",
+                                           "RATCHET_TIME",
+                                           &ratchet_time))
   {
-    rekey_period = GNUNET_TIME_UNIT_DAYS;
+    GNUNET_log_config_invalid (GNUNET_ERROR_TYPE_WARNING,
+                               "CADET", "RATCHET_TIME", "USING DEFAULT");
+    ratchet_time = GNUNET_TIME_UNIT_HOURS;
   }
 
-  id_key = key;
-
-  otr_kx_msg.header.size = htons (sizeof (otr_kx_msg));
-  otr_kx_msg.header.type = htons (GNUNET_MESSAGE_TYPE_CADET_KX_EPHEMERAL);
-  otr_kx_msg.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_CADET_KX);
-  otr_kx_msg.purpose.size = htonl (ephemeral_purpose_size ());
-  otr_kx_msg.origin_identity = my_full_id;
-  rekey_task = GNUNET_SCHEDULER_add_now (&global_otr_rekey, NULL);
-
-  ax_key = GNUNET_CRYPTO_ecdhe_key_create ();
-  GNUNET_CRYPTO_ecdhe_key_get_public (ax_key, &ax_identity.permanent_key);
-  ax_identity.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_CADET_AXKX);
-  ax_identity.purpose.size = htonl (ax_purpose_size ());
-  GNUNET_assert (GNUNET_OK ==
-                 GNUNET_CRYPTO_eddsa_sign (id_key,
-                                           &ax_identity.purpose,
-                                           &ax_identity.signature));
 
+  id_key = key;
   tunnels = GNUNET_CONTAINER_multipeermap_create (128, GNUNET_YES);
 }
 
@@ -3099,14 +2326,9 @@ GCT_init (const struct GNUNET_CONFIGURATION_Handle *c,
 void
 GCT_shutdown (void)
 {
-  if (NULL != rekey_task)
-  {
-    GNUNET_SCHEDULER_cancel (rekey_task);
-    rekey_task = NULL;
-  }
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "Shutting down tunnels\n");
   GNUNET_CONTAINER_multipeermap_iterate (tunnels, &destroy_iterator, NULL);
   GNUNET_CONTAINER_multipeermap_destroy (tunnels);
-  GNUNET_free (ax_key);
 }
 
 
@@ -3165,7 +2387,7 @@ GCT_change_cstate (struct CadetTunnel* t, enum CadetTunnelCState cstate)
     else if (CADET_TUNNEL_KEY_UNINITIALIZED == t->estate)
     {
       LOG (GNUNET_ERROR_TYPE_DEBUG, "  cstate triggered kx\n");
-      GCT_send_ax_kx (t);
+      GCT_send_ax_kx (t, GNUNET_NO);
     }
     else
     {
@@ -3186,6 +2408,8 @@ GCT_change_cstate (struct CadetTunnel* t, enum CadetTunnelCState cstate)
 /**
  * Change the tunnel encryption state.
  *
+ * If the encryption state changes to OK, stop the rekey task.
+ *
  * @param t Tunnel whose encryption state to change, or NULL.
  * @param state New encryption state.
  */
@@ -3204,11 +2428,16 @@ GCT_change_estate (struct CadetTunnel* t, enum CadetTunnelEState state)
   LOG (GNUNET_ERROR_TYPE_DEBUG, "Tunnel %s estate is now %s\n",
        GCP_2s (t->peer), estate2s (t->estate));
 
-  /* Send queued data if enc state changes to OK */
-  if (myid != GCP_get_short_id (t->peer) &&
-      CADET_TUNNEL_KEY_OK != old && CADET_TUNNEL_KEY_OK == t->estate)
+  if (CADET_TUNNEL_KEY_OK != old && CADET_TUNNEL_KEY_OK == t->estate)
   {
-    send_queued_data (t);
+    if (NULL != t->rekey_task)
+    {
+      GNUNET_SCHEDULER_cancel (t->rekey_task);
+      t->rekey_task = NULL;
+    }
+    /* Send queued data if tunnel is not loopback */
+    if (myid != GCP_get_short_id (t->peer))
+      send_queued_data (t);
   }
 }
 
@@ -3221,18 +2450,13 @@ GCT_change_estate (struct CadetTunnel* t, enum CadetTunnelEState state)
  * of being created/processed.
  *
  * @param cls Closure (Tunnel to check).
- * @param tc Task context.
  */
 static void
-trim_connections (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
+trim_connections (void *cls)
 {
   struct CadetTunnel *t = cls;
 
   t->trim_connections_task = NULL;
-
-  if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
-    return;
-
   if (GCT_count_connections (t) > 2 * CONNECTIONS_PER_TUNNEL)
   {
     struct CadetTConnection *iter;
@@ -3335,7 +2559,6 @@ GCT_remove_connection (struct CadetTunnel *t,
 
   /* Start new connections if needed */
   if (CONNECTIONS_PER_TUNNEL > conns
-      && NULL == t->destroy_task
       && CADET_TUNNEL_SHUTDOWN != t->cstate
       && GNUNET_NO == shutting_down)
   {
@@ -3379,8 +2602,11 @@ GCT_add_channel (struct CadetTunnel *t, struct CadetChannel *ch)
 
   aux = GNUNET_new (struct CadetTChannel);
   aux->ch = ch;
-  LOG (GNUNET_ERROR_TYPE_DEBUG, " adding %p to %p\n", aux, t->channel_head);
-  GNUNET_CONTAINER_DLL_insert_tail (t->channel_head, t->channel_tail, aux);
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       " adding %p to %p\n", aux, t->channel_head);
+  GNUNET_CONTAINER_DLL_insert_tail (t->channel_head,
+                                   t->channel_tail,
+                                   aux);
 
   if (NULL != t->destroy_task)
   {
@@ -3408,7 +2634,9 @@ GCT_remove_channel (struct CadetTunnel *t, struct CadetChannel *ch)
     if (aux->ch == ch)
     {
       LOG (GNUNET_ERROR_TYPE_DEBUG, " found! %s\n", GCCH_2s (ch));
-      GNUNET_CONTAINER_DLL_remove (t->channel_head, t->channel_tail, aux);
+      GNUNET_CONTAINER_DLL_remove (t->channel_head,
+                                  t->channel_tail,
+                                  aux);
       GNUNET_free (aux);
       return;
     }
@@ -3450,25 +2678,18 @@ GCT_get_channel (struct CadetTunnel *t, CADET_ChannelNumber chid)
  * the tunnel. This way we avoid a new public key handshake.
  *
  * @param cls Closure (tunnel to destroy).
- * @param tc Task context.
  */
 static void
-delayed_destroy (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
+delayed_destroy (void *cls)
 {
   struct CadetTunnel *t = cls;
   struct CadetTConnection *iter;
 
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "delayed destroying tunnel %p\n", t);
-  if (0 != (GNUNET_SCHEDULER_REASON_SHUTDOWN & tc->reason))
-  {
-    LOG (GNUNET_ERROR_TYPE_WARNING,
-         "Not destroying tunnel, due to shutdown. "
-         "Tunnel at %p should have been freed by GCT_shutdown\n", t);
-    return;
-  }
   t->destroy_task = NULL;
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "delayed destroying tunnel %p\n",
+       t);
   t->cstate = CADET_TUNNEL_SHUTDOWN;
-
   for (iter = t->connection_head; NULL != iter; iter = iter->next)
   {
     GCC_send_destroy (iter->c);
@@ -3510,7 +2731,7 @@ GCT_destroy_empty (struct CadetTunnel *t)
   // FIXME make delay a config option
   t->destroy_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
                                                   &delayed_destroy, t);
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "Scheduled destroy of %p as %llu\n",
+  LOG (GNUNET_ERROR_TYPE_DEBUG, "Scheduled destroy of %p as %p\n",
        t, t->destroy_task);
 }
 
@@ -3549,12 +2770,14 @@ GCT_destroy (struct CadetTunnel *t)
   struct CadetTConnection *next_c;
   struct CadetTChannel *iter_ch;
   struct CadetTChannel *next_ch;
+  unsigned int keepalives_queued;
 
   if (NULL == t)
     return;
 
-  LOG (GNUNET_ERROR_TYPE_DEBUG, "destroying tunnel %s\n", GCP_2s (t->peer));
-
+  LOG (GNUNET_ERROR_TYPE_DEBUG,
+       "destroying tunnel %s\n",
+       GCP_2s (t->peer));
   GNUNET_break (GNUNET_YES ==
                 GNUNET_CONTAINER_multipeermap_remove (tunnels,
                                                       GCP_get_id (t->peer), t));
@@ -3570,17 +2793,49 @@ GCT_destroy (struct CadetTunnel *t)
     GCCH_destroy (iter_ch->ch);
     /* Should only happen on shutdown, but it's ok. */
   }
+  keepalives_queued = 0;
+  while (NULL != t->tq_head)
+  {
+    /* Should have been cleaned by destuction of channel. */
+    struct GNUNET_MessageHeader *mh;
+    uint16_t type;
+
+    mh = (struct GNUNET_MessageHeader *) &t->tq_head[1];
+    type = ntohs (mh->type);
+    if (0 == keepalives_queued && GNUNET_MESSAGE_TYPE_CADET_KEEPALIVE == type)
+    {
+      keepalives_queued = 1;
+      LOG (GNUNET_ERROR_TYPE_DEBUG,
+           "one keepalive left behind on tunnel shutdown\n");
+    }
+    else if (GNUNET_MESSAGE_TYPE_CADET_CHANNEL_DESTROY == type)
+    {
+      LOG (GNUNET_ERROR_TYPE_WARNING,
+           "tunnel destroyed before a CHANNEL_DESTROY was sent to peer\n");
+    }
+    else
+    {
+      GNUNET_break (0);
+      LOG (GNUNET_ERROR_TYPE_ERROR,
+           "message left behind on tunnel shutdown: %s\n",
+           GC_m2s (type));
+    }
+    unqueue_data (t->tq_head);
+  }
+
 
   if (NULL != t->destroy_task)
   {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "cancelling dest: %llX\n", t->destroy_task);
+    LOG (GNUNET_ERROR_TYPE_DEBUG,
+        "cancelling dest: %p\n",
+        t->destroy_task);
     GNUNET_SCHEDULER_cancel (t->destroy_task);
     t->destroy_task = NULL;
   }
 
   if (NULL != t->trim_connections_task)
   {
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "cancelling trim: %llX\n",
+    LOG (GNUNET_ERROR_TYPE_DEBUG, "cancelling trim: %p\n",
          t->trim_connections_task);
     GNUNET_SCHEDULER_cancel (t->trim_connections_task);
     t->trim_connections_task = NULL;
@@ -3594,13 +2849,6 @@ GCT_destroy (struct CadetTunnel *t)
     GNUNET_SCHEDULER_cancel (t->rekey_task);
     t->rekey_task = NULL;
   }
-  if (NULL != t->kx_ctx)
-  {
-    if (NULL != t->kx_ctx->finish_task)
-      GNUNET_SCHEDULER_cancel (t->kx_ctx->finish_task);
-    GNUNET_free (t->kx_ctx);
-  }
-
   if (NULL != t->ax)
     destroy_ax (t);
 
@@ -3619,13 +2867,13 @@ GCT_destroy (struct CadetTunnel *t)
  * @return Connection created.
  */
 struct CadetConnection *
-GCT_use_path (struct CadetTunnel *t, struct CadetPeerPath *p)
+GCT_use_path (struct CadetTunnel *t, struct CadetPeerPath *path)
 {
   struct CadetConnection *c;
   struct GNUNET_CADET_Hash cid;
   unsigned int own_pos;
 
-  if (NULL == t || NULL == p)
+  if (NULL == t || NULL == path)
   {
     GNUNET_break (0);
     return NULL;
@@ -3637,19 +2885,19 @@ GCT_use_path (struct CadetTunnel *t, struct CadetPeerPath *p)
     return NULL;
   }
 
-  for (own_pos = 0; own_pos < p->length; own_pos++)
+  for (own_pos = 0; own_pos < path->length; own_pos++)
   {
-    if (p->peers[own_pos] == myid)
+    if (path->peers[own_pos] == myid)
       break;
   }
-  if (own_pos >= p->length)
+  if (own_pos >= path->length)
   {
     GNUNET_break_op (0);
     return NULL;
   }
 
   GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_NONCE, &cid, sizeof (cid));
-  c = GCC_new (&cid, t, p, own_pos);
+  c = GCC_new (&cid, t, path, own_pos);
   if (NULL == c)
   {
     /* Path was flawed */
@@ -3783,7 +3031,7 @@ GCT_get_channels_buffer (struct CadetTunnel *t)
   {
     /* Probably getting buffer for a channel create/handshake. */
     LOG (GNUNET_ERROR_TYPE_DEBUG, "  no channels, allow max\n");
-    return 64;
+    return MIN_TUNNEL_BUFFER;
   }
 
   buffer = 0;
@@ -3793,6 +3041,14 @@ GCT_get_channels_buffer (struct CadetTunnel *t)
     if (ch_buf > buffer)
       buffer = ch_buf;
   }
+  if (MIN_TUNNEL_BUFFER > buffer)
+    return MIN_TUNNEL_BUFFER;
+
+  if (MAX_TUNNEL_BUFFER < buffer)
+  {
+    GNUNET_break (0);
+    return MAX_TUNNEL_BUFFER;
+  }
   return buffer;
 }
 
@@ -3812,7 +3068,7 @@ GCT_get_connections_buffer (struct CadetTunnel *t)
 
   if (GNUNET_NO == is_ready (t))
   {
-    if (count_queued_data (t) > 3)
+    if (count_queued_data (t) >= 3)
       return 0;
     else
       return 1;
@@ -3904,6 +3160,9 @@ GCT_unchoke_channels (struct CadetTunnel *t)
   if (NULL != t->channel_head)
     LOG (GNUNET_ERROR_TYPE_DEBUG, " head ch: %p\n", t->channel_head->ch);
 
+  if (NULL != t->tq_head)
+    send_queued_data (t);
+
   /* Get buffer space */
   buffer = GCT_get_connections_buffer (t);
   if (0 == buffer)
@@ -3990,6 +3249,7 @@ GCT_send_connection_acks (struct CadetTunnel *t)
     {
       continue;
     }
+    GNUNET_assert(cs != 0);
     allow_per_connection = to_allow/cs;
     to_allow -= allow_per_connection;
     cs--;
@@ -4019,6 +3279,7 @@ GCT_cancel (struct CadetTunnelQueue *q)
 {
   if (NULL != q->cq)
   {
+    GNUNET_assert (NULL == q->tqd);
     GCC_cancel (q->cq);
     /* tun_message_sent() will be called and free q */
   }
@@ -4037,6 +3298,21 @@ GCT_cancel (struct CadetTunnelQueue *q)
 }
 
 
+/**
+ * Check if the tunnel has queued traffic.
+ *
+ * @param t Tunnel to check.
+ *
+ * @return #GNUNET_YES if there is queued traffic
+ *         #GNUNET_NO otherwise
+ */
+int
+GCT_has_queued_traffic (struct CadetTunnel *t)
+{
+  return (NULL != t->tq_head) ? GNUNET_YES : GNUNET_NO;
+}
+
+
 /**
  * Sends an already built message on a tunnel, encrypting it and
  * choosing the best connection if not provided.
@@ -4063,51 +3339,33 @@ GCT_send_prebuilt_message (const struct GNUNET_MessageHeader *message,
  * Send an Axolotl KX message.
  *
  * @param t Tunnel on which to send it.
+ * @param force_reply Force the other peer to reply with a KX message.
  */
 void
-GCT_send_ax_kx (struct CadetTunnel *t)
+GCT_send_ax_kx (struct CadetTunnel *t, int force_reply)
 {
   struct GNUNET_CADET_AX_KX msg;
+  enum GNUNET_CADET_AX_KX_Flags flags;
 
-  LOG (GNUNET_ERROR_TYPE_INFO, "===> AX_KX for %s\n", GCT_2s (t));
+  LOG (GNUNET_ERROR_TYPE_INFO, "==> {     AX_KX} on %s\n", GCT_2s (t));
+  if (NULL != t->ephm_h)
+  {
+    LOG (GNUNET_ERROR_TYPE_INFO, "     already queued\n");
+    return;
+  }
 
   msg.header.size = htons (sizeof (msg));
   msg.header.type = htons (GNUNET_MESSAGE_TYPE_CADET_AX_KX);
-  msg.permanent_key = ax_identity.permanent_key;
-  msg.purpose = ax_identity.purpose;
-  msg.signature = ax_identity.signature;
+  flags = GNUNET_CADET_AX_KX_FLAG_NONE;
+  if (force_reply)
+    flags |= GNUNET_CADET_AX_KX_FLAG_FORCE_REPLY;
+  msg.flags = htonl (flags);
   GNUNET_CRYPTO_ecdhe_key_get_public (t->ax->kx_0, &msg.ephemeral_key);
   GNUNET_CRYPTO_ecdhe_key_get_public (t->ax->DHRs, &msg.ratchet_key);
 
   t->ephm_h = send_kx (t, &msg.header);
-  GCT_change_estate (t, CADET_TUNNEL_KEY_SENT);
-}
-
-
-/**
- * Sends an already built and encrypted message on a tunnel, choosing the best
- * connection. Useful for re-queueing messages queued on a destroyed connection.
- *
- * @param message Message to send. Function modifies it.
- * @param t Tunnel on which this message is transmitted.
- */
-void
-GCT_resend_message (const struct GNUNET_MessageHeader *message,
-                    struct CadetTunnel *t)
-{
-  struct CadetConnection *c;
-  int fwd;
-
-  c = tunnel_get_connection (t);
-  if (NULL == c)
-  {
-    /* TODO queue in tunnel, marked as encrypted */
-    LOG (GNUNET_ERROR_TYPE_DEBUG, "No connection available, dropping.\n");
-    return;
-  }
-  fwd = GCC_is_origin (c, GNUNET_YES);
-  GNUNET_break (NULL == GCC_send_prebuilt_message (message, 0, 0, c, fwd,
-                                                   GNUNET_YES, NULL, NULL));
+  if (CADET_TUNNEL_KEY_UNINITIALIZED == t->estate)
+    GCT_change_estate (t, CADET_TUNNEL_KEY_SENT);
 }
 
 
@@ -4219,34 +3477,28 @@ ax_debug (const struct CadetTunnelAxolotl *ax, enum GNUNET_ErrorType level)
   struct GNUNET_CRYPTO_EcdhePublicKey pub;
   struct CadetTunnelSkippedKey *iter;
 
+  LOG2 (level, "TTT  RK  \t %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->RK));
 
-  LOG2 (level, "TTT  RK\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->RK));
-
-  LOG2 (level, "TTT  HKs\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->HKs));
-  LOG2 (level, "TTT  HKr\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->HKr));
+  LOG2 (level, "TTT  HKs \t %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->HKs));
+  LOG2 (level, "TTT  HKr \t %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->HKr));
   LOG2 (level, "TTT  NHKs\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->NHKs));
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->NHKs));
   LOG2 (level, "TTT  NHKr\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->NHKr));
-
-  LOG2 (level, "TTT  CKs\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->CKs));
-  LOG2 (level, "TTT  CKr\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->CKr));
-
-  GNUNET_CRYPTO_ecdhe_key_get_public (ax_key, &pub);
-  LOG2 (level, "TTT  DHIs\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &pub));
-  LOG2 (level, "TTT  DHIr\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->DHIr));
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->NHKr));
+
+  LOG2 (level, "TTT  CKs \t %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->CKs));
+  LOG2 (level, "TTT  CKr \t %s\n",
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->CKr));
+
   GNUNET_CRYPTO_ecdhe_key_get_public (ax->DHRs, &pub);
   LOG2 (level, "TTT  DHRs\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &pub));
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &pub));
   LOG2 (level, "TTT  DHRr\t %s\n",
-        GNUNET_h2s ((struct GNUNET_HashCode *) &ax->DHRr));
+        GNUNET_i2s ((struct GNUNET_PeerIdentity *) &ax->DHRr));
 
   LOG2 (level, "TTT  Nr\t %u\tNs\t%u\n", ax->Nr, ax->Ns);
   LOG2 (level, "TTT  PNs\t %u\tSkipped\t%u\n", ax->PNs, ax->skipped);
@@ -4255,9 +3507,9 @@ ax_debug (const struct CadetTunnelAxolotl *ax, enum GNUNET_ErrorType level)
   for (iter = ax->skipped_head; NULL != iter; iter = iter->next)
   {
     LOG2 (level, "TTT    HK\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &iter->HK));
+          GNUNET_i2s ((struct GNUNET_PeerIdentity *) &iter->HK));
     LOG2 (level, "TTT    MK\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &iter->MK));
+          GNUNET_i2s ((struct GNUNET_PeerIdentity *) &iter->MK));
   }
 }
 
@@ -4283,8 +3535,6 @@ GCT_debug (const struct CadetTunnel *t, enum GNUNET_ErrorType level)
   LOG2 (level, "TTT DEBUG TUNNEL TOWARDS %s\n", GCT_2s (t));
   LOG2 (level, "TTT  cstate %s, estate %s\n",
        cstate2s (t->cstate), estate2s (t->estate));
-  LOG2 (level, "TTT  kx_ctx %p, rekey_task %u, finish task %u\n",
-        t->kx_ctx, t->rekey_task, t->kx_ctx ? t->kx_ctx->finish_task : 0);
 #if DUMP_KEYS_TO_STDERR
   if (CADET_Axolotl == t->enc_type)
   {
@@ -4292,30 +3542,21 @@ GCT_debug (const struct CadetTunnel *t, enum GNUNET_ErrorType level)
   }
   else
   {
-    LOG2 (level, "TTT  my EPHM\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &otr_kx_msg.ephemeral_key));
     LOG2 (level, "TTT  peers EPHM:\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &t->peers_ephemeral_key));
+          GNUNET_i2s ((struct GNUNET_PeerIdentity *) &t->peers_ephemeral_key));
     LOG2 (level, "TTT  ENC key:\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &t->e_key));
+          GNUNET_i2s ((struct GNUNET_PeerIdentity *) &t->e_key));
     LOG2 (level, "TTT  DEC key:\t %s\n",
-          GNUNET_h2s ((struct GNUNET_HashCode *) &t->d_key));
-    if (t->kx_ctx)
-    {
-      LOG2 (level, "TTT  OLD ENC key:\t %s\n",
-            GNUNET_h2s ((struct GNUNET_HashCode *) &t->kx_ctx->e_key_old));
-      LOG2 (level, "TTT  OLD DEC key:\t %s\n",
-            GNUNET_h2s ((struct GNUNET_HashCode *) &t->kx_ctx->d_key_old));
-    }
+          GNUNET_i2s ((struct GNUNET_PeerIdentity *) &t->d_key));
   }
 #endif
   LOG2 (level, "TTT  tq_head %p, tq_tail %p\n", t->tq_head, t->tq_tail);
-  LOG2 (level, "TTT  destroy %u\n", t->destroy_task);
+  LOG2 (level, "TTT  destroy %p\n", t->destroy_task);
 
   LOG2 (level, "TTT  channels:\n");
   for (iterch = t->channel_head; NULL != iterch; iterch = iterch->next)
   {
-    LOG2 (level, "TTT  - %s\n", GCCH_2s (iterch->ch));
+    GCCH_debug (iterch->ch, level);
   }
 
   LOG2 (level, "TTT  connections:\n");