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.

Additionally, I now changed the data types for the puzzle and solution values from uint64_t to uint8_t[8].

[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

[René Hummen (rene-hummen)]

On 07.04.2011, at 21:59, Christof Mroz wrote:
> Review: Needs Fixing
> 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.

Done. I don't see your point in adding an assertion here.

>> + /* 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...

[René Hummen (rene-hummen)]

On 08.04.2011, at 06:35, Miika Komu wrote:
> Review: Needs Information
> The algorithm seems changed. Did you test it against the old, interoperable implementation?

I had already tested the following scenarios:
1.) puzzle-fixes <-> trunk
2.) trunk <-> puzzle-fixes
3.) puzzle-fixes <-> puzzle-fixes

All worked fine for me.

--
Dipl.-Inform. Rene Hummen, Ph.D. Student
Chair of Communication and Distributed Systems
RWTH Aachen University, Germany
tel: [phone]
web: http://www.comsys.rwth-aachen.de/team/rene-hummen/

[Diego Biurrun (diego-biurrun)]

 review abstain

I have no opinion on this merge request, just some minor comments
that you may wish to ignore or adapt at your discretion...

On Fri, Apr 08, 2011 at 03:41:24PM +0000, René Hummen wrote:
>
> --- lib/core/solve.c 2011-01-24 10:21:17 +0000
> +++ lib/core/solve.c 2011-04-08 15:41:17 +0000
> @@ -28,11 +28,14 @@
>
> #include <errno.h>
> +#include <openssl/rand.h>
> #include <stdint.h>
> #include <string.h>
> +#include <strings.h>

nit:

#include <errno.h>
#include <stdint.h>
#include <string.h>
#include <strings.h>
#include <openssl/rand.h>

> @@ -43,104 +46,170 @@
> +static int hip_calculate_puzzle_solution(const struct puzzle_common *const compute_puzzle,
> + unsigned char sha_digest[SHA_DIGEST_LENGTH],
> + const int difficulty)
> {
> + 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");
> +
> + /* check if position of first least significant 1-bit is higher than
> + * difficulty */
> + if (ffs(truncated_digest) > difficulty) {
> + err = 0;
> } else {
> + err = 1;
> + }
> +
> +out_err:
> + return err;
> +}

I would suggest doing that without HIP_IFEL, that would even save two
lines in the if/else clause.

> +/**
> + * 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])

Having solution as third parameter would feel more natural to me.

> +/**
> + * 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])

Having solution as third paramete...

review: Abstain

[Christof Mroz (christof-mroz)]

Looks good; feel free to address the following points.

> + * 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
> */

@a difficulty

> +/**
> + * 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
> + */

Prepend :: to create a hyperlink to a global in doxygen, e.g.
::MAX_PUZZLE_SOLUTION_TRIES in this case.

> + ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit);
> + ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit);

struct in6_addr can be copied using assignment AFAIK (there are more instances of this).

review: Approve

[Stefan Götz (stefan.goetz-deactivatedaccount)]

Hi René!

> === modified file 'hipd/cookie.c'
> --- hipd/cookie.c 2011-04-05 16:44:22 +0000
> +++ hipd/cookie.c 2011-04-08 15:41:17 +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 */

[L] 'cookie' and 'puzzle' seem to refer to the same thing. It would be
great if this ambiguity were removed from the code and only a single
name was used.

> @@ -77,9 +77,9 @@
> */
> static int hip_set_cookie_difficulty(int k)

[M] 'const int k' for const correctness and boyscouting

> {
> - if (k > HIP_PUZZLE_MAX_K || k < 1) {
> + if (k > max_puzzle_difficulty || k < 0) {

[M] k is not ever supposed to be < 0, correct? If yes, please give it
an unsigned type.

> === 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:41:17 +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])

[M] const correctness for boyscouting

> === 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:41:17 +0000
> @@ -130,7 +130,7 @@
> uint8_t,
> uint8_t,
> uint32_t,
> - uint64_t);
> + const uint8_t *);

[M] 'const uint8_t *const'?

> @@ -150,7 +150,7 @@
> uint8_t);
> int hip_build_param_solution(struct hip_common *,
> const struct hip_puzzle *,
> - uint64_t);
> + uint8_t *);

[M] 'uint8_t *const'?

> === 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:41:17 +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

[M] 'const unsigned PUZZLE_LENGTH = 8;'

> === 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:41:17 +0000
> @@ -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));

[M] The type is undocumented.

[M] The name 'puzzle_common' is not very descriptive (its opposite
'puzzle_uncommon' would be similarly helpful in understanding the
struct's purpose)...

[Stefan Götz (stefan.goetz-deactivatedaccount)]

Forgot my verdict on this merge proposal.

review: Needs Fixing

[René Hummen (rene-hummen)]

On 08.04.2011, at 20:08, Christof Mroz wrote:
> Review: Approve
> Looks good; feel free to address the following points.
>
>> + ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit);
>> + ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit);
>
> struct in6_addr can be copied using assignment AFAIK (there are more instances of this).

I don't see why a simple assignment should be sufficient with the following struct definition:

/*
 * IPv6 address
 */
struct in6_addr {
 union {
  __uint8_t __u6_addr8[16];
  __uint16_t __u6_addr16[8];
  __uint32_t __u6_addr32[4];
 } __u6_addr; /* 128-bit IP6 address */
};

In each case, in6_addr contains array, so we would merely copy pointers, right?

Ciao,
René

--
Dipl.-Inform. Rene Hummen, Ph.D. Student
Chair of Communication and Distributed Systems
RWTH Aachen University, Germany
tel: [phone]
web: http://www.comsys.rwth-aachen.de/team/rene-hummen/

[Christof Mroz (christof-mroz)]

On Tue, 12 Apr 2011 13:15:56 +0200, René Hummen
<email address hidden> wrote:

>>> + ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit);
>>> + ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit);
>>
>> struct in6_addr can be copied using assignment AFAIK (there are more
>> instances of this).
>
> I don't see why a simple assignment should be sufficient with the
> following struct definition:

All I know is that the following works:

struct in6_addr a,b;
// ...
a = b;

I personally prefer this over an explicit byte copy... unless
ipv6_addr_copy does something extra. Assignment of structs is really
nothing else than a typesafe version of memcpy(&a, &b, sizeof(a)).

> In each case, in6_addr contains array, so we would merely copy pointers,
> right?

I'd say yes: an IPv6 address is essentially an opaque array of 16 bytes.

[René Hummen (rene-hummen)]

Thanks for this detailed review! Below the comments I did not address in the branch.

On 09.04.2011, at 02:04, Stefan Götz wrote:
> Hi René!
>
>> === modified file 'hipd/cookie.c'
>> --- hipd/cookie.c 2011-04-05 16:44:22 +0000
>> +++ hipd/cookie.c 2011-04-08 15:41:17 +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 */
>
> [L] 'cookie' and 'puzzle' seem to refer to the same thing. It would be
> great if this ambiguity were removed from the code and only a single
> name was used.

Agreed, but that's not in the focus of this branch. I wouldn't want to change hip_cookie_difficulty to hip_puzzle_difficulty here, as the variable is located in cookie.c. Instead, we should probably rename the whole cookie functionality to puzzle.

>> === 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:41:17 +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
>
> [M] 'const unsigned PUZZLE_LENGTH = 8;'

This won't work as I'm using PUZZLE_LENGTH for array definitions in structs, etc.

>> +static int hip_calculate_puzzle_solution(const struct puzzle_common *const compute_puzzle,
>> + unsigned char sha_digest[SHA_DIGEST_LENGTH],
>> + const int difficulty)
>> {
>
> [M] It seems that 'sha_digest' is accessed only within this function
> but never by any of its callers. Please declare it as a local variable
> instead of a function parameter.

It's called in a for loop by hip_solve_puzzle(). I don't want memory to be
allocated each time.

> [M] Since this function returns only two distinct values, please use
> 'bool' instead of 'int'

It returns -1, 0, and 1.

>> +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])
>
> [M] This function only returns two distinct values. Please use 'bool'
> as the return type instead.

It's done like this everywhere in HIPL for notifying about errors. I don't want to introduce a "new way" of doing that in this branch.

> Btw. I like it that hip_hit_t's are passed around by value as opposed
> by error-prone reference.

Me too :)

>> === 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:41:17 +0000
>> @@ -30,10 +30,20 @@
>>
>> #include "protodefs.h"
>>
>> -#define HIP_PUZZLE_MAX_K 28
>> -
>> -uint64_t hip_solve_puzzle(const void *puzzle,
>> - ...

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

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

[Stefan Götz (stefan.goetz-deactivatedaccount)]

>> struct in6_addr can be copied using assignment AFAIK (there are more instances of this).
>
> I don't see why a simple assignment should be sufficient with the following struct definition:
>
> /*
>  * IPv6 address
>  */
> struct in6_addr {
>        union {
>                __uint8_t   __u6_addr8[16];
>                __uint16_t  __u6_addr16[8];
>                __uint32_t  __u6_addr32[4];
>        } __u6_addr;                    /* 128-bit IP6 address */
> };
>
> In each case, in6_addr contains array, so we would merely copy pointers, right?

No. The struct contains the actual array data. If you have the following:

int a[2];

Then you can use 'a' as if it was a pointer. However, the memory for
two integers is definitely allocated through this statement, be it in
a struct or as a variable.

Another way to look at it: if you really want a struct to contain an
array of uint32_t's (maybe plus some other data), there simply is no
other way of doing that than saying:

struct x {
     uint32_t a[4];
};

That array is 16 bytes long - sizeof will say the same.

Due to that: in6_addr should be assignable without a problem.

Yet another reason why it is possible: you can pass in6_addr structs
as function parameters by value. That implies that they can be copied
by assignment.

Stefan

[Stefan Götz (stefan.goetz-deactivatedaccount)]

Hi Rene!

Anything I haven't commented on I agree with and consider my previous
comments to be void.

>>> +static int hip_calculate_puzzle_solution(const struct puzzle_common *const compute_puzzle,
>>> +                                         unsigned char sha_digest[SHA_DIGEST_LENGTH],
>>> +                                         const int difficulty)
>>> {
>>
>> [M] It seems that 'sha_digest' is accessed only within this function
>> but never by any of its callers. Please declare it as a local variable
>> instead of a function parameter.
>
> It's called in a for loop by hip_solve_puzzle(). I don't want memory to be
> allocated each time.

Ok - please fix this, nevertheless:

1) If malloc() were to be used in each iteration, I'd agree. But as a
local variable, there is zero allocation overhead. The 'allocation'
happens on the stack and is essentially taken care of by the compiler
at compile time, as with any other local variable.

2) The next best option would be to declare sha_digest as a static
local variable - then that memory would be kept around in a fixed
location between calls. I'm pretty sure though that this solution is
still inferior to a non-static local variable because the non-static
local variable on the stack has better chances of being in the cache
and fewer chances for hash collisions.

>>> +/* right now we only support difficulties up to sizeof(int), as only ffs
>>> + * is available on OpenWRT */
>>
>> [M] 'difficulties of up to sizeof(int)' is incorrect because in fact
>> it is 'MIN(28, sizeof(int))'.
>
> Nope, the difficulty can be max sizeof(int). It might be any lower value though.
>
>>> +static const int max_puzzle_difficulty = sizeof(int) * 8 >= 28 ? 28 : sizeof(int) * 8;

Hm - maybe we misunderstand each other. What I'm trying to say is that
I read the code as follows:

if (sizeof(int) * 8) is greater than or equal to 28, then mpd is set to 28.
if (sizeof(int) * 8) is less than 28, then mpd is set to (sizeof(int)
* 8), i.e., a number smaller than 28.

So on 32-bit and 64-bit machines, we end up with 28. 16-bit machine: 16.

My complaint is the following: the comment says that a difficulty of
up to sizeof(int) [*8 I guess] is supported. On 32-bit and 64-bit
machines, that is incorrect as the maximum supported difficulty is 28
bits, not 32 or 64.

I guess the code is alright - it's the comment that bugs me, because
to me, it contradicts the code.

Stefan

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

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-12 17:04:29 +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-12 17:04:29 +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 uint8_t hip_cookie_difficulty = 0; /* a difficulty of i leads to approx. 2^(i-1) hash computations during BEX */
 
 /**
  * query for current puzzle difficulty
@@ -75,11 +75,11 @@
  * @param k the new puzzle difficulty
  * @return the k value on success or negative on error
  */
-static int hip_set_cookie_difficulty(int k)
+static int hip_set_cookie_difficulty(const uint8_t k)
 {
-    if (k > HIP_PUZZLE_MAX_K || k < 1) {
+    if (k > MAX_PUZZLE_DIFFICULTY) {
         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->J,
+                                        solution->K,
+                                        hdr->hits,
+                                        hdr->hitr),
+             -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-12 17:04:29 +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-11 12:48:58 +0000
+++ hipd/input.c	2011-04-12 17:04:29 +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-12 17:04:29 +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-12 17:04:29 +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-11 12:56:12 +0000
+++ hipd/output.c	2011-04-12 17:04:29 +0000
@@ -652,8 +652,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 */
@@ -718,7 +720,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");
@@ -727,9 +728,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-12 17:04:29 +0000
@@ -2384,8 +2384,11 @@
  *
  * @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)
+int hip_build_param_puzzle(struct hip_common *const msg,
+                           const uint8_t val_K,
+                           const uint8_t lifetime,
+                           const uint32_t opaque,
+                           const uint8_t random_i[PUZZLE_LENGTH])
 {
     struct hip_puzzle puzzle;
     int               err = 0;
@@ -2402,7 +2405,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 +2518,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 +2530,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-12 17:04:29 +0000
@@ -126,11 +126,11 @@
                          uint8_t,
                          void *,
                          size_t);
-int hip_build_param_puzzle(struct hip_common *,
-                           uint8_t,
-                           uint8_t,
-                           uint32_t,
-                           uint64_t);
+int hip_build_param_puzzle(struct hip_common *const msg,
+                           const uint8_t val_K,
+                           const uint8_t lifetime,
+                           const uint32_t opaque,
+                           const uint8_t *const random_i);
 
 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 *const);
 
 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-12 17:04:29 +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-12 17:04:29 +0000
@@ -28,11 +28,14 @@
  * @brief HIP computation puzzle solving algorithms
  *
  * @author Miika Komu <[e-mail]>
+ * @author Rene Hummen
  */
 
 #include <errno.h>
 #include <stdint.h>
 #include <string.h>
+#include <strings.h>
+#include <openssl/rand.h>
 
 #include "config.h"
 #include "builder.h"
@@ -43,108 +46,186 @@
 #include "protodefs.h"
 #include "solve.h"
 
+/** This data type represents the ordered input for the hash function used to
+ *  solve a given puzzle challenge as defined in RFC 5201 - Appendix A */
+struct puzzle_hash_input {
+    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 >= @a difficulty least significant bits as zeros, 1
+ *         when hash has < @a 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_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input,
+                                         unsigned char sha_digest[SHA_DIGEST_LENGTH],
+                                         const uint8_t 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,
+                              puzzle_input,
+                              sizeof(struct puzzle_hash_input),
+                              sha_digest),
+             -1, "failed to compute hash digest\n");
+
+    /* In reference to RFC 5201, we need to interpret the hash digest as an
+     * integer in network byte-order. We are interested in least significant
+     * bits here. */
+    truncated_digest = *(uint32_t *) &sha_digest[SHA_DIGEST_LENGTH - sizeof(truncated_digest)];
+
+    /* Make sure to interpret the solution equally across platforms
+     * (i.e., network byte-order), when calculating the puzzle solution.
+     *
+     * The problem is that ffs() interprets its input not as a byte array
+     * but as an integer with an encoding that depends on the host byte order.
+     * htonl() ensures that ffs() performs the check in network byte order
+     * independent from the actual host byte order. */
+    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[out] 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 uint8_t difficulty,
+                     const hip_hit_t initiator_hit,
+                     const hip_hit_t responder_hit,
+                     uint8_t solution[PUZZLE_LENGTH])
+{
+    struct puzzle_hash_input compute_puzzle;
+    unsigned char            sha_digest[SHA_DIGEST_LENGTH];
+    int                      err = -1;
+    unsigned long long       i   = 0;
+
+    /* solution must reference allocated memory here */
+    HIP_ASSERT(solution);
+
+    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;
+    }
+
+    /* If max_puzzle_difficulty >= 64, MAX_PUZZLE_SOLUTION_TRIES will be 0.
+     * Hence, no solution will be found for these cases. */
+    HIP_ASSERT(MAX_PUZZLE_DIFFICULTY < sizeof(unsigned long long) * 8);
+
+    for (i = 0; i < MAX_PUZZLE_SOLUTION_TRIES; i++) {
+        // now do the computations
+        err = hip_single_puzzle_computation(&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 solution      puzzle solution 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
+ * @return 0 when solution is correct, -1 otherwise
+ */
+int hip_verify_puzzle_solution(const uint8_t puzzle[PUZZLE_LENGTH],
+                               const uint8_t solution[PUZZLE_LENGTH],
+                               const uint8_t difficulty,
+                               const hip_hit_t initiator_hit,
+                               const hip_hit_t responder_hit)
+{
+    struct puzzle_hash_input compute_puzzle;
+    unsigned char            sha_digest[SHA_DIGEST_LENGTH];
+
+    // 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);
+
+    if (hip_single_puzzle_computation(&compute_puzzle, sha_digest, difficulty)) {
+        HIP_ERROR("failed to verify puzzle solution\n");
+        return -1;
+    }
+
+    return 0;
+}
+
 #ifdef CONFIG_HIP_MIDAUTH
 /**
  * solve a midauth puzzle which is essentially a normal HIP cookie

=== modified file 'lib/core/solve.h'
--- lib/core/solve.h	2010-10-15 15:29:14 +0000
+++ lib/core/solve.h	2011-04-12 17:04:29 +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 e.g. ffsll()
+ * allowing for sizeof(long long int) is currently not available on OpenWRT. */
+static const uint8_t MAX_PUZZLE_DIFFICULTY = sizeof(int) * 8 >= 28 ? 28 : sizeof(int) * 8;
+
+int hip_solve_puzzle(const uint8_t puzzle[PUZZLE_LENGTH],
+                     const uint8_t 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 solution[PUZZLE_LENGTH],
+                               const uint8_t difficulty,
+                               const hip_hit_t initiator_hit,
+                               const hip_hit_t responder_hit);
 
 #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-12 17:04:29 +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-12 17:04:29 +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-12 17:04:29 +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-12 17:04:29 +0000
@@ -0,0 +1,200 @@
+/*
+ * 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 <stdint.h>
+#include <stdio.h>
+#include <arpa/inet.h>
+#include <netinet/in.h>
+#include <openssl/rand.h>
+
+#include "lib/core/solve.h"
+#include "config.h"
+#include "test_suites.h"
+
+#ifdef HAVE_TCASE_ADD_EXIT_TEST
+START_TEST(test_hip_solve_puzzle_NULL_solution)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    uint8_t 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
+#endif /* HAVE_TCASE_ADD_EXIT_TEST */
+
+START_TEST(test_hip_solve_puzzle_0_K)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    uint8_t 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 };
+    uint8_t 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 };
+    uint8_t 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_verify_puzzle_solution_invalid)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 1 };
+    uint8_t difficulty = 20;
+    hip_hit_t initiator;
+    hip_hit_t responder;
+    uint8_t solution[PUZZLE_LENGTH] = { 0 };
+
+    fail_unless(hip_verify_puzzle_solution(puzzle,
+                                           solution,
+                                           difficulty,
+                                           initiator,
+                                           responder) == -1,
+                NULL);
+}
+END_TEST
+
+START_TEST(test_hip_verify_puzzle_solution_against_ourselves)
+{
+    uint8_t puzzle[PUZZLE_LENGTH] = { 0 };
+    uint8_t 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,
+                                           solution,
+                                           difficulty,
+                                           initiator,
+                                           responder) == 0,
+                NULL);
+}
+END_TEST
+
+START_TEST(test_hip_test_hip_verify_puzzle_solution_against_real_solution)
+{
+    char solution_dump[] = "\x01\x41\x00\x14\x05\x00\x48\x49\x0b\xbd\xd0\xb4"
+                           "\x92\xbb\xea\xe3\xa9\x71\x97\xdf\x12\xe1\x2c\x9f";
+    struct hip_solution *solution = (struct hip_solution *) solution_dump;
+    const char *initiator_hit_str = "2001:1b:d8b0:77f0:c617:7170:ded7:f320";
+    const char *responder_hit_str = "2001:17:5df8:c426:98e5:5fa2:286d:2847";
+    struct in6_addr initiator_hit;
+    struct in6_addr responder_hit;
+
+    inet_pton(AF_INET6, initiator_hit_str, &initiator_hit);
+    inet_pton(AF_INET6, responder_hit_str, &responder_hit);
+
+    fail_unless(hip_verify_puzzle_solution(solution->I,
+                                           solution->J,
+                                           solution->K,
+                                           initiator_hit,
+                                           responder_hit) == 0);
+}
+END_TEST
+
+Suite *lib_core_solve(void)
+{
+    Suite *s = suite_create("lib/core/solve");
+
+    TCase *tc_core = tcase_create("Core");
+#ifdef HAVE_TCASE_ADD_EXIT_TEST
+    tcase_add_exit_test(tc_core, test_hip_solve_puzzle_NULL_solution, 1);
+#endif /* HAVE_TCASE_ADD_EXIT_TEST */
+    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_verify_puzzle_solution_invalid);
+    tcase_add_test(tc_core, test_hip_verify_puzzle_solution_against_ourselves);
+    tcase_add_test(tc_core, test_hip_test_hip_verify_puzzle_solution_against_real_solution);
+    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-12 17:04:29 +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 */