Merge lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl

[René Hummen]

This branch refactors HIPL's puzzle handling functionality and generalizes the API for use with the midauth extension. It has been tested with unit tests and on virtual machines.

[Christof Mroz (christof-mroz)]

Overall, this is definately cleaner than the old code.

There is one piece of code that does not match its corresponding comment; as soon as this is clarified (or fixed), I'll approve.
Would be nice if you could address the other points too (mainly missing documentation for newly added functions).

> +static int hip_calculate_puzzle_solution(const struct puzzle_common *const compute_puzzle,
> + unsigned char sha_digest[SHA_DIGEST_LENGTH],
> + const int difficulty)
> {
> - uint64_t mask = 0;
> - uint64_t randval = 0;
> - uint64_t maxtries = 0;
> - uint64_t digest = 0;
> - uint8_t cookie[48];
> - int err = 0;
> - const union {
> - struct hip_puzzle pz;
> - struct hip_solution sl;
> - } *u;
> -
> - HIP_HEXDUMP("puzzle", puzzle_or_solution,
> - (mode == HIP_VERIFY_PUZZLE ? sizeof(struct hip_solution) :
> - sizeof(struct hip_puzzle)));
> -
> - /* pre-create cookie */
> - u = puzzle_or_solution;
> -
> - HIP_IFEL(u->pz.K > HIP_PUZZLE_MAX_K, 0,
> - "Cookie K %u is higher than we are willing to calculate"
> - " (current max K=%d)\n", u->pz.K, HIP_PUZZLE_MAX_K);
> -
> - mask = hton64((1ULL << u->pz.K) - 1);
> - memcpy(cookie, &u->pz.I, sizeof(uint64_t));
> -
> - HIP_DEBUG("(u->pz.I: 0x%llx\n", u->pz.I);
> -
> - if (mode == HIP_VERIFY_PUZZLE) {
> - ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hits);
> - ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hitr);
> - randval = u->sl.J;
> - maxtries = 1;
> - } else if (mode == HIP_SOLVE_PUZZLE) {
> - ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hitr);
> - ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hits);
> - maxtries = 1ULL << (u->pz.K + 3);
> - get_random_bytes(&randval, sizeof(uint64_t));
> + uint32_t truncated_digest = 0;
> + int err = -1;
> +
> + HIP_IFEL(difficulty > max_puzzle_difficulty,
> + 1, "difficulty exceeds max. configured difficulty\n");
> +
> + HIP_IFEL(hip_build_digest(HIP_DIGEST_SHA1,
> + compute_puzzle,
> + sizeof(struct puzzle_common),
> + sha_digest),
> + -1, "failed to compute hash digest\n");

You could return early with a (successful) solution of zero if difficulty == 0.
If the caller is responsible of taking that shortcut, I'd add an assertion here to catch future callers who forget about this.

> + /* we are interested in the 8 least significant bytes */
> + truncated_digest = *(uint32_t *) &sha_digest[SHA_DIGEST_LENGTH - sizeof(uint32_t)];

The 8 least significant bytes have index 0..7. Also, sizeof(uint32_t) is 4, not 8.

> +int hip_solve_puzzle(const uint64_t puzzle,
> + const int difficulty,
> + const hip_hit_t initiator_hit,
> + const hip_hit_t responder_hit,
> + uint64_t *solution)
> +{
> + struct puzzle_common compute_puzzle;
> + unsigned char sha_digest[SHA...

review: Needs Fixing

[Christof Mroz (christof-mroz)]

On Thu, 07 Apr 2011 21:59:22 +0200, Christof Mroz
<email address hidden> wrote:

>> + /* we are interested in the 8 least significant bytes */
>> + truncated_digest = *(uint32_t *) &sha_digest[SHA_DIGEST_LENGTH -
>> sizeof(uint32_t)];
>
> The 8 least significant bytes have index 0..7. Also, sizeof(uint32_t) is
> 4, not 8.

Note: I'm aware that things look differently if you interpret the digest
as a big-endian number with SHA_DIGEST_LENGTH * 8 bits; what I'm trying to
say here is: if that's what you meant in the comment, then you should
state it more verbosely (i.e. mention byte order).

[Miika Komu (miika-iki)]

The algorithm seems changed. Did you test it against the old, interoperable implementation?

review: Needs Information

[lp:~rene-hummen/hipl/puzzle-fixes]

5855. By René Hummen on 2011-04-08

remove write-only variables solved_puzzle and I

5859. By René Hummen on 2011-04-08

fix forward declaration in unit-tests for lib/core/solve.c

5860. By René Hummen on 2011-04-08

make difficulty > max_puzzle_difficulty an error

5861. By René Hummen on 2011-04-08

add missing doxygen documentation

5862. By René Hummen on 2011-04-08

replace uint64_t by uint8_t[8] for puzzle and solution values

puzzle and solution values are bit.fields and do not need to be
interpreted. Hence, uint64_t is not the correct data type and
leads to endianess problems for these values.

5863. By René Hummen on 2011-04-08

allow for early exit for puzzle difficulty 0

5864. By René Hummen on 2011-04-08

reflect API changes in unit-tests

5865. By René Hummen on 2011-04-08

clarify comments of on endianness

5866. By René Hummen on 2011-04-08

merged with trunk revision 5854

5867. By René Hummen on 2011-04-08

fix comparison of solution and puzzle values

5868. By René Hummen on 2011-04-12

reorder includes as suggested by Diego

5869. By René Hummen on 2011-04-12

fix doxygen comments

5870. By René Hummen on 2011-04-12

convert HIP_IFEL into if statement

5871. By René Hummen on 2011-04-12

reorder parameters of hip_verify_puzzle_solution()

5872. By René Hummen on 2011-04-12

change type of puzzle difficulty from int to uint8_t

The puzzle difficulty is transported as uint8_t on the wire.

5873. By René Hummen on 2011-04-12

address comments and improvements by Stefan

5874. By René Hummen on 2011-04-12

fix unit-tests according to previous changes

5875. By René Hummen on 2011-04-12

add solution verification unit-test for real/captured solution

5876. By René Hummen on 2011-04-13

replace ipv6_addr_copy() by simple assignment

5877. By René Hummen on 2011-04-13

declare sha_digest as a local variable

5878. By René Hummen on 2011-04-13

improve documentation of MAX_PUZZLE_DIFFICULTY

5879. By René Hummen on 2011-04-14

replace ipv6_addr_copy() by an assignment

5880. By René Hummen on 2011-04-14

minor change in local var ordering

5881. By René Hummen on 2011-04-14

change year of copyright

5882. By René Hummen on 2011-04-18

use struct puzzle_hash_input in puzzle api

5883. By René Hummen on 2011-04-18

fix doxygen

5884. By René Hummen on 2011-04-19

change output type from int to uint

5885. By René Hummen on 2011-04-19

directly exit hip_solve_puzzle instead of using break indirection

5886. By René Hummen on 2011-04-19

merge trunk revision 5878

Unmerged revisions

5886. By René Hummen on 2011-04-19

merge trunk revision 5878

5885. By René Hummen on 2011-04-19

directly exit hip_solve_puzzle instead of using break indirection

5884. By René Hummen on 2011-04-19

change output type from int to uint

5883. By René Hummen on 2011-04-18

fix doxygen

5882. By René Hummen on 2011-04-18

use struct puzzle_hash_input in puzzle api

5881. By René Hummen on 2011-04-14

change year of copyright

5880. By René Hummen on 2011-04-14

minor change in local var ordering

5879. By René Hummen on 2011-04-14

replace ipv6_addr_copy() by an assignment

5878. By René Hummen on 2011-04-13

improve documentation of MAX_PUZZLE_DIFFICULTY

5877. By René Hummen on 2011-04-13

declare sha_digest as a local variable

=== modified file 'Makefile.am'
--- Makefile.am	2011-04-06 15:52:33 +0000
+++ Makefile.am	2011-04-08 15:38:33 +0000
@@ -207,6 +207,7 @@
 
 test_check_lib_core_SOURCES = test/check_lib_core.c          \
                               test/lib/core/hit.c            \
+                              test/lib/core/solve.c          \
                               test/lib/core/straddr.c
 
 test_check_lib_tool_SOURCES = test/check_lib_tool.c          \

=== modified file 'hipd/cookie.c'
--- hipd/cookie.c	2011-04-05 16:44:22 +0000
+++ hipd/cookie.c	2011-04-08 15:38:33 +0000
@@ -56,7 +56,7 @@
 
 #define HIP_R1TABLESIZE 3 /* precreate only this many R1s */
 
-static int hip_cookie_difficulty = 1ULL; /* a difficulty of i leads to approx. 2^(i-1) hash computations during BEX */
+static int hip_cookie_difficulty = 0; /* a difficulty of i leads to approx. 2^(i-1) hash computations during BEX */
 
 /**
  * query for current puzzle difficulty
@@ -77,9 +77,9 @@
  */
 static int hip_set_cookie_difficulty(int k)
 {
-    if (k > HIP_PUZZLE_MAX_K || k < 1) {
+    if (k > max_puzzle_difficulty || k < 0) {
         HIP_ERROR("Bad cookie value (%d), min=%d, max=%d\n",
-                  k, 1, HIP_PUZZLE_MAX_K);
+                  k, 1, max_puzzle_difficulty);
         return -1;
     }
     hip_cookie_difficulty = k;
@@ -347,7 +347,7 @@
 
         HIP_IFEL(solution->K != result->Ck, -1,
                  "Solution's K did not match any sent Ks.\n");
-        HIP_IFEL(solution->I != result->Ci, -1,
+        HIP_IFEL(memcmp(solution->I, result->Ci, PUZZLE_LENGTH), -1,
                  "Solution's I did not match the sent I\n");
         HIP_IFEL(memcmp(solution->opaque, result->Copaque,
                         HIP_PUZZLE_OPAQUE_LEN), -1,
@@ -356,15 +356,19 @@
     } else {
         HIP_HEXDUMP("solution", solution, sizeof(*solution));
         HIP_HEXDUMP("puzzle", puzzle, sizeof(*puzzle));
-        HIP_IFEL(solution->I != puzzle->I, -1,
+        HIP_IFEL(memcmp(solution->I, puzzle->I, PUZZLE_LENGTH), -1,
                  "Solution's I did not match the sent I\n");
         HIP_IFEL(memcmp(solution->opaque, puzzle->opaque,
                         HIP_PUZZLE_OPAQUE_LEN), -1,
                  "Solution's opaque data does not match the opaque data sent\n");
     }
 
-    HIP_IFEL(!hip_solve_puzzle(solution, hdr, HIP_VERIFY_PUZZLE), -1,
-             "Puzzle incorrectly solved.\n");
+    HIP_IFEL(hip_verify_puzzle_solution(solution->I,
+                                        solution->K,
+                                        hdr->hits,
+                                        hdr->hitr,
+                                        solution->J),
+             -1, "Puzzle incorrectly solved.\n");
 
 out_err:
     return err;

=== modified file 'hipd/cookie.h'
--- hipd/cookie.h	2011-01-10 13:12:17 +0000
+++ hipd/cookie.h	2011-04-08 15:38:33 +0000
@@ -34,9 +34,9 @@
 struct hip_r1entry {
     struct hip_common *r1;
     uint32_t           generation;
-    uint64_t           Ci;
+    uint8_t            Ci[PUZZLE_LENGTH];
     uint8_t            Ck;
-    uint8_t            Copaque[3];
+    uint8_t            Copaque[HIP_PUZZLE_OPAQUE_LEN];
 };
 
 struct hip_common *hip_get_r1(struct in6_addr *ip_i,

=== modified file 'hipd/input.c'
--- hipd/input.c	2011-04-08 08:47:50 +0000
+++ hipd/input.c	2011-04-08 15:38:33 +0000
@@ -235,8 +235,8 @@
  * @return zero on success, or negative on error.
  */
 static int hip_produce_keying_material(struct hip_packet_context *ctx,
-                                       uint64_t I,
-                                       uint64_t J)
+                                       const uint8_t I[PUZZLE_LENGTH],
+                                       const uint8_t J[PUZZLE_LENGTH])
 {
     char                        *dh_shared_key = NULL;
     int                          hip_transf_length, hmac_transf_length;
@@ -868,16 +868,17 @@
     /* Solve puzzle: if this is a retransmission, we have to preserve
      * the old solution. */
     if (!retransmission) {
-        const struct hip_puzzle *pz2 = NULL;
+        const struct hip_puzzle *pz = NULL;
 
-        HIP_IFEL(!(pz2 = hip_get_param(ctx->input_msg, HIP_PARAM_PUZZLE)), -EINVAL,
+        HIP_IFEL(!(pz = hip_get_param(ctx->input_msg, HIP_PARAM_PUZZLE)), -EINVAL,
                  "Malformed R1 packet. PUZZLE parameter missing\n");
-        HIP_IFEL((ctx->hadb_entry->puzzle_solution =
-                      hip_solve_puzzle(pz2,
-                                       ctx->input_msg,
-                                       HIP_SOLVE_PUZZLE)) == 0,
+        HIP_IFEL(hip_solve_puzzle(pz->I,
+                                  pz->K,
+                                  ctx->input_msg->hitr,
+                                  ctx->input_msg->hits,
+                                  ctx->hadb_entry->puzzle_solution),
                  -EINVAL, "Solving of puzzle failed\n");
-        ctx->hadb_entry->puzzle_i = pz2->I;
+        memcpy(ctx->hadb_entry->puzzle_i, pz->I, PUZZLE_LENGTH);
     }
 
     HIP_DEBUG("Build normal I2.\n");

=== modified file 'hipd/keymat.c'
--- hipd/keymat.c	2011-01-11 13:59:46 +0000
+++ hipd/keymat.c	2011-04-08 15:38:33 +0000
@@ -58,19 +58,18 @@
 static uint8_t *hip_create_keymat_buffer(char *kij, size_t kij_len, size_t hash_len,
                                          struct in6_addr *smaller_hit,
                                          struct in6_addr *bigger_hit,
-                                         uint64_t I, uint64_t J)
+                                         const uint8_t I[PUZZLE_LENGTH],
+                                         const uint8_t J[PUZZLE_LENGTH])
 
 {
     uint8_t *buffer = NULL, *cur = NULL;
     size_t   requiredmem;
 
-    HIP_DEBUG("\n");
-    /* 2*sizeof(uint64_t) added to take care of I and J. */
     if (2 * sizeof(struct in6_addr) < hash_len) {
-        requiredmem = kij_len + hash_len + sizeof(uint8_t) + 2 * sizeof(uint64_t);
+        requiredmem = kij_len + hash_len + sizeof(uint8_t) + 2 * PUZZLE_LENGTH;
     } else {
         requiredmem = kij_len + 2 * sizeof(struct in6_addr) +
-                      sizeof(uint8_t) + 2 * sizeof(uint64_t);
+                      sizeof(uint8_t) + 2 * PUZZLE_LENGTH;
     }
     buffer = malloc(requiredmem);
     if (!buffer) {
@@ -85,10 +84,10 @@
     cur += sizeof(struct in6_addr);
     memcpy(cur, (uint8_t *) bigger_hit, sizeof(struct in6_addr));
     cur += sizeof(struct in6_addr);
-    memcpy(cur, &I, sizeof(uint64_t));     // XX CHECK: network byte order?
-    cur += sizeof(uint64_t);
-    memcpy(cur, &J, sizeof(uint64_t));     // XX CHECK: network byte order?
-    cur   += sizeof(uint64_t);
+    memcpy(cur, I, PUZZLE_LENGTH);
+    cur += PUZZLE_LENGTH;
+    memcpy(cur, J, PUZZLE_LENGTH);
+    cur   += PUZZLE_LENGTH;
     *(cur) = 1;
     cur   += sizeof(uint8_t);
 
@@ -138,8 +137,8 @@
                      struct in6_addr *hit1,
                      struct in6_addr *hit2,
                      uint8_t *calc_index,
-                     uint64_t I,
-                     uint64_t J)
+                     const uint8_t I[PUZZLE_LENGTH],
+                     const uint8_t J[PUZZLE_LENGTH])
 {
     int              bufsize;
     uint8_t          index_nbr = 1;

=== modified file 'hipd/keymat.h'
--- hipd/keymat.h	2010-10-15 15:29:14 +0000
+++ hipd/keymat.h	2011-04-08 15:38:33 +0000
@@ -37,7 +37,9 @@
 void hip_make_keymat(char *kij, size_t kij_len,
                      struct hip_keymat_keymat *keymat,
                      void *dstbuf, size_t dstbuflen, struct in6_addr *hit1,
-                     struct in6_addr *hit2, uint8_t *calc_index, uint64_t I, uint64_t J);
+                     struct in6_addr *hit2, uint8_t *calc_index,
+                     const uint8_t I[PUZZLE_LENGTH],
+                     const uint8_t J[PUZZLE_LENGTH]);
 int hip_keymat_draw_and_copy(unsigned char *dst,
                              struct hip_keymat_keymat *keymat,
                              int len);

=== modified file 'hipd/output.c'
--- hipd/output.c	2011-04-06 09:07:51 +0000
+++ hipd/output.c	2011-04-08 15:38:33 +0000
@@ -636,8 +636,10 @@
     /********** R1_COUNTER (OPTIONAL) *********/
 
     /********** PUZZLE ************/
+    const uint8_t zero_i[PUZZLE_LENGTH] = { 0 };
+
     HIP_IFEL(hip_build_param_puzzle(err, cookie_k,
-                                    42 /* 2^(42-32) sec lifetime */, 0, 0),
+                                    42 /* 2^(42-32) sec lifetime */, 0, zero_i),
              NULL, "Cookies were burned. Bummer!\n");
 
     /* Parameter Diffie-Hellman */
@@ -702,7 +704,6 @@
     /* Fill puzzle parameters */
     {
         struct hip_puzzle *pz;
-        uint64_t           random_i;
 
         HIP_IFEL(!(pz = hip_get_param_readwrite(err, HIP_PARAM_PUZZLE)), NULL,
                  "Internal error\n");
@@ -711,9 +712,7 @@
         pz->opaque[0] = 'H';
         pz->opaque[1] = 'I';
         //pz->opaque[2] = 'P';
-        /** @todo Remove random_i variable. */
-        get_random_bytes(&random_i, sizeof(random_i));
-        pz->I = random_i;
+        get_random_bytes(pz->I, PUZZLE_LENGTH);
     }
 
     /* Packet ready */

=== modified file 'lib/core/builder.c'
--- lib/core/builder.c	2011-04-07 16:58:58 +0000
+++ lib/core/builder.c	2011-04-08 15:38:33 +0000
@@ -2385,7 +2385,8 @@
  * @return zero for success, or non-zero on error
  */
 int hip_build_param_puzzle(struct hip_common *msg, uint8_t val_K,
-                           uint8_t lifetime, uint32_t opaque, uint64_t random_i)
+                           uint8_t lifetime, uint32_t opaque,
+                           const uint8_t random_i[PUZZLE_LENGTH])
 {
     struct hip_puzzle puzzle;
     int               err = 0;
@@ -2402,7 +2403,7 @@
     puzzle.lifetime  = lifetime;
     puzzle.opaque[0] = opaque & 0xFF;
     puzzle.opaque[1] = (opaque & 0xFF00) >> 8;
-    puzzle.I         = random_i;
+    memcpy(puzzle.I, random_i, PUZZLE_LENGTH);
 
     err = hip_build_generic_param(msg, &puzzle,
                                   sizeof(struct hip_tlv_common),
@@ -2515,7 +2516,7 @@
  */
 int hip_build_param_solution(struct hip_common *msg,
                              const struct hip_puzzle *pz,
-                             uint64_t val_J)
+                             uint8_t val_J[PUZZLE_LENGTH])
 {
     struct hip_solution cookie;
     int                 err = 0;
@@ -2527,7 +2528,7 @@
     /* Type 2 (in R1) or 3 (in I2) */
     hip_set_param_type((struct hip_tlv_common *) &cookie, HIP_PARAM_SOLUTION);
 
-    cookie.J = val_J;
+    memcpy(cookie.J, val_J, PUZZLE_LENGTH);
     memcpy(&cookie.K, &pz->K, 12);     /* copy: K (1), reserved (1),
                                         * opaque (2) and I (8 bytes). */
     cookie.reserved = 0;

=== modified file 'lib/core/builder.h'
--- lib/core/builder.h	2011-04-02 20:38:36 +0000
+++ lib/core/builder.h	2011-04-08 15:38:33 +0000
@@ -130,7 +130,7 @@
                            uint8_t,
                            uint8_t,
                            uint32_t,
-                           uint64_t);
+                           const uint8_t *);
 
 int hip_build_param_challenge_request(struct hip_common *,
                                       uint8_t,
@@ -150,7 +150,7 @@
                                        uint8_t);
 int hip_build_param_solution(struct hip_common *,
                              const struct hip_puzzle *,
-                             uint64_t);
+                             uint8_t *);
 
 int hip_build_param_challenge_response(struct hip_common *,
                                        const struct hip_challenge_request *,

=== modified file 'lib/core/protodefs.h'
--- lib/core/protodefs.h	2011-02-04 14:44:37 +0000
+++ lib/core/protodefs.h	2011-04-08 15:38:33 +0000
@@ -737,13 +737,17 @@
     uint64_t    generation;
 } __attribute__ ((packed));
 
+
+/* puzzle and solutions are defined to have a length of 8 bytes */
+#define PUZZLE_LENGTH 8
+
 struct hip_puzzle {
     hip_tlv     type;
     hip_tlv_len length;
     uint8_t     K;
     uint8_t     lifetime;
     uint8_t     opaque[HIP_PUZZLE_OPAQUE_LEN];
-    uint64_t    I;
+    uint8_t     I[PUZZLE_LENGTH];
 } __attribute__ ((packed));
 
 struct hip_solution {
@@ -752,8 +756,8 @@
     uint8_t     K;
     uint8_t     reserved;
     uint8_t     opaque[HIP_PUZZLE_OPAQUE_LEN];
-    uint64_t    I;
-    uint64_t    J;
+    uint8_t     I[PUZZLE_LENGTH];
+    uint8_t     J[PUZZLE_LENGTH];
 } __attribute__ ((packed));
 
 

=== modified file 'lib/core/solve.c'
--- lib/core/solve.c	2011-01-24 10:21:17 +0000
+++ lib/core/solve.c	2011-04-08 15:38:33 +0000
@@ -28,11 +28,14 @@
  * @brief HIP computation puzzle solving algorithms
  *
  * @author Miika Komu <[e-mail]>
+ * @author Rene Hummen
  */
 
 #include <errno.h>
+#include <openssl/rand.h>
 #include <stdint.h>
 #include <string.h>
+#include <strings.h>
 
 #include "config.h"
 #include "builder.h"
@@ -43,104 +46,170 @@
 #include "protodefs.h"
 #include "solve.h"
 
+struct puzzle_common {
+    uint8_t   puzzle[PUZZLE_LENGTH];
+    hip_hit_t initiator_hit;
+    hip_hit_t responder_hit;
+    uint8_t   solution[PUZZLE_LENGTH];
+} __attribute__ ((packed));
+
+// max. 2^max_puzzle_difficulty tries to solve a puzzle
+#define MAX_PUZZLE_SOLUTION_TRIES 1ULL << max_puzzle_difficulty
+
 /**
- * solve a computational puzzle for HIP
- *
- * @param puzzle_or_solution Either a pointer to hip_puzzle or hip_solution structure
- * @param hdr The incoming R1/I2 packet header.
- * @param mode Either HIP_VERIFY_PUZZLE of HIP_SOLVE_PUZZLE
- *
- * @note The K and I is read from the @c puzzle_or_solution.
- * @note Regarding to return value of zero, I don't see why 0 couldn't solve the
- *       puzzle too, but since the odds are 1/2^64 to try 0, I don't see the point
- *       in improving this now.
- * @return The J that solves the puzzle is returned, or 0 to indicate an error.
+ * Computes a single iteration for a computational puzzle
+ *
+ * @param compute_puzzle    puzzle to be solved or verified
+ * @param sha_digest        buffer for hash digest
+ * @param difficulty        difficulty of the puzzle (number of leading zeros)
+ * @return 0 when hash has >= #difficulty least significant bits as zeros, 1
+ *         when hash has < #difficulty least significant bits as zeros,
+ *         -1 in case of an error
  */
-uint64_t hip_solve_puzzle(const void *puzzle_or_solution,
-                          const struct hip_common *hdr,
-                          int mode)
+static int hip_calculate_puzzle_solution(const struct puzzle_common *const compute_puzzle,
+                                         unsigned char sha_digest[SHA_DIGEST_LENGTH],
+                                         const int difficulty)
 {
-    uint64_t mask     = 0;
-    uint64_t randval  = 0;
-    uint64_t maxtries = 0;
-    uint64_t digest   = 0;
-    uint8_t  cookie[48];
-    int      err = 0;
-    const union {
-        struct hip_puzzle   pz;
-        struct hip_solution sl;
-    } *u;
-
-    HIP_HEXDUMP("puzzle", puzzle_or_solution,
-                (mode == HIP_VERIFY_PUZZLE ? sizeof(struct hip_solution) :
-                 sizeof(struct hip_puzzle)));
-
-    /* pre-create cookie */
-    u = puzzle_or_solution;
-
-    HIP_IFEL(u->pz.K > HIP_PUZZLE_MAX_K, 0,
-             "Cookie K %u is higher than we are willing to calculate"
-             " (current max K=%d)\n", u->pz.K, HIP_PUZZLE_MAX_K);
-
-    mask = hton64((1ULL << u->pz.K) - 1);
-    memcpy(cookie, &u->pz.I, sizeof(uint64_t));
-
-    HIP_DEBUG("(u->pz.I: 0x%llx\n", u->pz.I);
-
-    if (mode == HIP_VERIFY_PUZZLE) {
-        ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hits);
-        ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hitr);
-        randval  = u->sl.J;
-        maxtries = 1;
-    } else if (mode == HIP_SOLVE_PUZZLE) {
-        ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hitr);
-        ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hits);
-        maxtries = 1ULL << (u->pz.K + 3);
-        get_random_bytes(&randval, sizeof(uint64_t));
+    uint32_t truncated_digest = 0;
+    int      err              = -1;
+
+    /* any puzzle solution is acceptable for difficulty 0 */
+    if (difficulty == 0) {
+        return 0;
+    }
+
+    HIP_IFEL(difficulty > max_puzzle_difficulty,
+             -1, "difficulty exceeds max. configured difficulty\n");
+
+    HIP_IFEL(hip_build_digest(HIP_DIGEST_SHA1,
+                              compute_puzzle,
+                              sizeof(struct puzzle_common),
+                              sha_digest),
+             -1, "failed to compute hash digest\n");
+
+    /* we are interested in least significant bytes in network byte-order */
+    truncated_digest = *(uint32_t *) &sha_digest[SHA_DIGEST_LENGTH - sizeof(uint32_t)];
+
+    /* make sure to interpret the solution equally across platforms
+     * (i.e., network byte-order), when calculating puzzle solution */
+    truncated_digest = htonl(truncated_digest);
+
+    /* check if position of first least significant 1-bit is higher than
+     * difficulty */
+    if (ffs(truncated_digest) > difficulty) {
+        err = 0;
     } else {
-        HIP_OUT_ERR(0, "Unknown mode: %d\n", mode);
-    }
-
-    HIP_DEBUG("K=%u, maxtries (with k+2)=%llu\n", u->pz.K, maxtries);
-    /* while loops should work even if the maxtries is unsigned
-     * if maxtries = 1 ---> while(1 > 0) [maxtries == 0 now]...
-     * the next round while (0 > 0) [maxtries > 0 now]
-     */
-    while (maxtries-- > 0) {
-        uint8_t sha_digest[HIP_AH_SHA_LEN];
-
-        /* must be 8 */
-        memcpy(cookie + 40, (uint8_t *) &randval, sizeof(uint64_t));
-
-        hip_build_digest(HIP_DIGEST_SHA1, cookie, 48, sha_digest);
-
-        /* copy the last 8 bytes for checking */
-        memcpy(&digest, sha_digest + 12, sizeof(uint64_t));
-
-        /* now, in order to be able to do correctly the bitwise
-         * AND-operation we have to remember that little endian
-         * processors will interpret the digest and mask reversely.
-         * digest is the last 64 bits of the sha1-digest.. how that is
-         * ordered in processors registers etc.. does not matter to us.
-         * If the last 64 bits of the sha1-digest is
-         * 0x12345678DEADBEEF, whether we have 0xEFBEADDE78563412
-         * doesn't matter because the mask matters... if the mask is
-         * 0x000000000000FFFF (or in other endianness
-         * 0xFFFF000000000000). Either ways... the result is
-         * 0x000000000000BEEF or 0xEFBE000000000000, which the cpu
-         * interprets as 0xBEEF. The mask is converted to network byte
-         * order (above).
-         */
-        if ((digest & mask) == 0) {
-            return randval;
+        err = 1;
+    }
+
+out_err:
+    return err;
+}
+
+/**
+ * Solve a computational puzzle for HIP
+ *
+ * @param puzzle        puzzle to be solved
+ * @param difficulty    difficulty of the puzzle
+ * @param initiator_hit initiator HIT of the message exchange
+ * @param responder_hit responder HIT of the message exchange
+ * @param solution      computed puzzle solution
+ * @return 0 when solution was found, 1 in case no solution was found after
+ *         MAX_PUZZLE_SOLUTION_TRIES, -1 in case of an error
+ */
+int hip_solve_puzzle(const uint8_t puzzle[PUZZLE_LENGTH],
+                     const int difficulty,
+                     const hip_hit_t initiator_hit,
+                     const hip_hit_t responder_hit,
+                     uint8_t solution[PUZZLE_LENGTH])
+{
+    struct puzzle_common compute_puzzle;
+    unsigned char        sha_digest[SHA_DIGEST_LENGTH];
+    int                  err = -1;
+    uint32_t             i   = 0;
+
+    HIP_IFEL(!solution, -1, "invalid parameter passed (NULL)\n");
+
+    HIP_IFEL(difficulty > max_puzzle_difficulty, -1,
+             "Cookie (K = %i) is higher than we are willing to calculate"
+             " (current max K = %i)\n", difficulty, max_puzzle_difficulty);
+
+    /* solution is correct iff:
+     * 0 == V := Ltrunc( RHASH( I2.I | I2.hit_i | I2.hit_r | I2.J ), K )
+     * (RFC 5201 - Appendix A) */
+    memcpy(compute_puzzle.puzzle, puzzle, PUZZLE_LENGTH);
+    ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit);
+    ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit);
+    RAND_bytes(compute_puzzle.solution, PUZZLE_LENGTH);
+
+    // any puzzle solution is acceptable for difficulty 0
+    if (difficulty == 0) {
+        return 0;
+    }
+
+    for (i = 0; i < MAX_PUZZLE_SOLUTION_TRIES; i++) {
+        // now do the computations
+        err = hip_calculate_puzzle_solution(&compute_puzzle,
+                                            sha_digest,
+                                            difficulty);
+        if (err == 0) {
+            memcpy(solution, compute_puzzle.solution, PUZZLE_LENGTH);
+            break;
+        } else if (err > 0) {
+            // increase random value by one and try again
+            (*(uint64_t *) compute_puzzle.solution)++;
+        } else {
+            memset(solution, 0, PUZZLE_LENGTH);
+            break;
         }
-
-        /* It seems like the puzzle was not correctly solved */
-        HIP_IFEL(mode == HIP_VERIFY_PUZZLE, 0, "Puzzle incorrect\n");
-        randval++;
-    }
-
-    HIP_ERROR("Could not solve the puzzle, no solution found\n");
+    }
+
+out_err:
+    if (i == MAX_PUZZLE_SOLUTION_TRIES) {
+        HIP_ERROR("Could not solve the puzzle, no solution found\n");
+    }
+
+    return err;
+}
+
+/**
+ * Verify a computational puzzle for HIP
+ *
+ * @param puzzle        puzzle to be verified
+ * @param difficulty    difficulty of the puzzle
+ * @param initiator_hit initiator HIT of the message exchange
+ * @param responder_hit responder HIT of the message exchange
+ * @param solution      puzzle solution to be verified
+ * @return 0 when solution is correct, -1 otherwise
+ */
+int hip_verify_puzzle_solution(const uint8_t puzzle[PUZZLE_LENGTH],
+                               const uint8_t difficulty,
+                               const hip_hit_t initiator_hit,
+                               const hip_hit_t responder_hit,
+                               const uint8_t solution[PUZZLE_LENGTH])
+{
+    struct puzzle_common compute_puzzle;
+    unsigned char        sha_digest[SHA_DIGEST_LENGTH];
+    int                  err = 0;
+
+    // any puzzle solution is acceptable for difficulty 0
+    if (difficulty == 0) {
+        return 0;
+    }
+
+    /* solution is correct iff:
+     * 0 == V := Ltrunc( RHASH( I2.I | I2.hit_i | I2.hit_r | I2.J ), K )
+     * (RFC 5201 - Appendix A) */
+    memcpy(compute_puzzle.puzzle, puzzle, PUZZLE_LENGTH);
+    ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit);
+    ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit);
+    memcpy(compute_puzzle.solution, solution, PUZZLE_LENGTH);
+
+    HIP_IFEL(hip_calculate_puzzle_solution(&compute_puzzle,
+                                           sha_digest,
+                                           difficulty),
+             -1, "failed to verify puzzle solution\n");
+
 out_err:
     return err;
 }

=== modified file 'lib/core/solve.h'
--- lib/core/solve.h	2010-10-15 15:29:14 +0000
+++ lib/core/solve.h	2011-04-08 15:38:33 +0000
@@ -30,10 +30,20 @@
 
 #include "protodefs.h"
 
-#define HIP_PUZZLE_MAX_K        28
-
-uint64_t hip_solve_puzzle(const void *puzzle,
-                          const struct hip_common *hdr, int mode);
-int hip_solve_puzzle_m(struct hip_common *out, struct hip_common *in);
+/* right now we only support difficulties up to sizeof(int), as only ffs
+ * is available on OpenWRT */
+static const int max_puzzle_difficulty = sizeof(int) * 8 >= 28 ? 28 : sizeof(int) * 8;
+
+int hip_solve_puzzle(const uint8_t puzzle[PUZZLE_LENGTH],
+                     const int difficulty,
+                     const hip_hit_t initiator_hit,
+                     const hip_hit_t responder_hit,
+                     uint8_t solution[PUZZLE_LENGTH]);
+
+int hip_verify_puzzle_solution(const uint8_t puzzle[PUZZLE_LENGTH],
+                               const uint8_t difficulty,
+                               const hip_hit_t initiator_hit,
+                               const hip_hit_t responder_hit,
+                               const uint8_t solution[PUZZLE_LENGTH]);
 
 #endif /* HIP_LIB_CORE_SOLVE_H */

=== modified file 'lib/core/state.h'
--- lib/core/state.h	2011-02-06 09:03:39 +0000
+++ lib/core/state.h	2011-04-08 15:38:33 +0000
@@ -294,13 +294,13 @@
     /** A function pointer to a function that verifies peer's host identity. */
     int (*verify)(void *, struct hip_common *);
     /** For retransmission. */
-    uint64_t puzzle_solution;
+    uint8_t puzzle_solution[PUZZLE_LENGTH];
     /** LOCATOR parameter. Just tmp save if sent in R1 no @c esp_info so
      *  keeping it here 'till the hip_update_locator_parameter can be done.
      *  @todo Remove this kludge. */
     struct hip_locator *locator;
     /** For retransmission. */
-    uint64_t puzzle_i;
+    uint8_t puzzle_i[PUZZLE_LENGTH];
     /** Used for UPDATE and CLOSE. When we sent multiple identical UPDATE
      * packets between different address combinations, we don't modify
      * the opaque data. */

=== modified file 'lib/tool/pk.c'
--- lib/tool/pk.c	2011-04-04 13:59:21 +0000
+++ lib/tool/pk.c	2011-04-08 15:38:33 +0000
@@ -131,8 +131,8 @@
     uint8_t            sha1_digest[HIP_AH_SHA_LEN];
     struct in6_addr    tmpaddr;
     struct hip_puzzle *pz = NULL;
-    uint8_t            opaque[3];
-    uint64_t           randi = 0;
+    uint8_t            opaque[HIP_PUZZLE_OPAQUE_LEN];
+    uint8_t            rand_i[PUZZLE_LENGTH];
 
     ipv6_addr_copy(&tmpaddr, &msg->hitr);     /* so update is handled, too */
 
@@ -146,11 +146,13 @@
 
         HIP_IFEL(!(pz = hip_get_param_readwrite(msg, HIP_PARAM_PUZZLE)),
                  -ENOENT, "Illegal R1 packet (puzzle missing)\n");
-        memcpy(opaque, pz->opaque, sizeof(pz->opaque));
-        randi = pz->I;
 
-        memset(pz->opaque, 0, sizeof(pz->opaque));
-        pz->I = 0;
+        /* temporarily store original puzzle values */
+        memcpy(opaque, pz->opaque, HIP_PUZZLE_OPAQUE_LEN);
+        memcpy(rand_i, pz->I, PUZZLE_LENGTH);
+        /* R1 signature is computed over zero values */
+        memset(pz->opaque, 0, HIP_PUZZLE_OPAQUE_LEN);
+        memset(pz->I, 0, PUZZLE_LENGTH);
     } else {
         HIP_IFEL(!(sig = hip_get_param_readwrite(msg, HIP_PARAM_HIP_SIGNATURE)),
                  -ENOENT, "Could not find signature\n");
@@ -182,8 +184,8 @@
 #endif
 
     if (hip_get_msg_type(msg) == HIP_R1) {
-        memcpy(pz->opaque, opaque, sizeof(pz->opaque));
-        pz->I = randi;
+        memcpy(pz->opaque, opaque, HIP_PUZZLE_OPAQUE_LEN);
+        memcpy(pz->I, rand_i, PUZZLE_LENGTH);
     }
 
     ipv6_addr_copy(&msg->hitr, &tmpaddr);

=== modified file 'test/check_lib_core.c'
--- test/check_lib_core.c	2011-02-18 14:39:38 +0000
+++ test/check_lib_core.c	2011-04-08 15:38:33 +0000
@@ -38,6 +38,7 @@
 {
     int      number_failed;
     SRunner *sr = srunner_create(lib_core_hit());
+    srunner_add_suite(sr, lib_core_solve());
     srunner_add_suite(sr, lib_core_straddr());
 
     srunner_run_all(sr, CK_NORMAL);

=== added file 'test/lib/core/solve.c'
--- test/lib/core/solve.c	1970-01-01 00:00:00 +0000
+++ test/lib/core/solve.c	2011-04-08 15:38:33 +0000
@@ -0,0 +1,170 @@
+/*
+ * Copyright (c) 2010 Aalto University and RWTH Aachen University.
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * @file
+ * @author Rene Hummen
+ */
+
+#include <check.h>
+#include <openssl/rand.h>
+#include <stdint.h>
+
+#include "lib/core/solve.h"
+#include "test_suites.h"
+
+START_TEST(test_hip_solve_puzzle_NULL_solution)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    int difficulty = 0;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+
+    RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t));
+
+    fail_unless(hip_solve_puzzle(puzzle,
+                                 difficulty,
+                                 initiator,
+                                 responder,
+                                 NULL) == -1,
+                 NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_0_K)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    int difficulty = 0;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    RAND_bytes((unsigned char *)&puzzle, sizeof(PUZZLE_LENGTH));
+
+    fail_unless(hip_solve_puzzle(puzzle,
+                                 difficulty,
+                                 initiator,
+                                 responder,
+                                 solution) == 0,
+                 NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_5_K)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    int difficulty = 5;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t));
+
+    fail_unless(hip_solve_puzzle(puzzle,
+                                 difficulty,
+                                 initiator,
+                                 responder,
+                                 solution) == 0,
+                 NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_exceeding_K)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    int difficulty = max_puzzle_difficulty + 1;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t));
+
+    fail_unless(hip_solve_puzzle(puzzle,
+                                 difficulty,
+                                 initiator,
+                                 responder,
+                                 solution) == -1,
+                 NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_invalid)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 1 };
+    int difficulty = 20;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    fail_unless(hip_verify_puzzle_solution(puzzle,
+                                           difficulty,
+                                           initiator,
+                                           responder,
+                                           solution) == -1,
+                NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_valid)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    int difficulty = 8;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t));
+
+    fail_unless(hip_solve_puzzle(puzzle,
+                                 difficulty,
+                                 initiator,
+                                 responder,
+                                 solution) == 0,
+                 NULL);
+
+    fail_unless(hip_verify_puzzle_solution(puzzle,
+                                           difficulty,
+                                           initiator,
+                                           responder,
+                                           solution) == 0,
+                NULL);
+}
+END_TEST
+
+Suite *lib_core_solve(void)
+{
+    Suite *s = suite_create("lib/core/solve");
+
+    TCase *tc_core = tcase_create("Core");
+    tcase_add_test(tc_core, test_hip_solve_puzzle_NULL_solution);
+    tcase_add_test(tc_core, test_hip_solve_puzzle_0_K);
+    tcase_add_test(tc_core, test_hip_solve_puzzle_5_K);
+    tcase_add_test(tc_core, test_hip_solve_puzzle_exceeding_K);
+    tcase_add_test(tc_core, test_hip_solve_puzzle_invalid);
+    tcase_add_test(tc_core, test_hip_solve_puzzle_valid);
+    suite_add_tcase(s, tc_core);
+
+    return s;
+}

=== modified file 'test/lib/core/test_suites.h'
--- test/lib/core/test_suites.h	2011-02-18 14:39:38 +0000
+++ test/lib/core/test_suites.h	2011-04-08 15:38:33 +0000
@@ -29,6 +29,7 @@
 #include <check.h>
 
 Suite *lib_core_hit(void);
+Suite *lib_core_solve(void);
 Suite *lib_core_straddr(void);
 
 #endif /* HIP_TEST_LIB_CORE_TEST_SUITES_H */