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]. Also addressed remaining review comments.

Addressed Stefan's latest comments.

[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,
>> - ...

[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

[Christof Mroz (christof-mroz)]

Looks good to me.

review: Approve

[Miika Komu (miika-iki)]

Seems ok to me.

review: Approve

[René Hummen (rene-hummen)]

If there are no further comments, I will merge this branch tomorrow.

[Diego Biurrun (diego-biurrun)]

 review needs-fixing

On Wed, Apr 13, 2011 at 08:50:53AM +0000, René Hummen wrote:
> René Hummen has proposed merging lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl.
>
> --- lib/core/builder.h 2011-04-02 20:38:36 +0000
> +++ lib/core/builder.h 2011-04-13 08:50:40 +0000
> @@ -126,11 +126,11 @@
> -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);

nit:
Maybe you could add the parameter names while you're changing those
lines anyway? That one of the most important headers in HIPL lacks
parameter names in function declarations is extremely annoying.

> --- lib/core/solve.c 2011-01-24 10:21:17 +0000
> +++ lib/core/solve.c 2011-04-13 08:50:40 +0000
> @@ -43,108 +46,183 @@
>
> +static int hip_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input,
> + const uint8_t difficulty)
> {
> + unsigned char sha_digest[SHA_DIGEST_LENGTH];
> + uint32_t truncated_digest = 0;
> + int err = -1;
> +
> + 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");
> +
> + if (ffs(truncated_digest) > difficulty) {
> + err = 0;
> + } else {
> + err = 1;
> + }
> +
> +out_err:
> + return err;
> +}

You seem to insist on writing this with HIP_IFEL, but just compare how
much neater this is with plain if-return (slightly redacted):

  static int hip_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input,
                                           const uint8_t difficulty)
  {
      unsigned char sha_digest[SHA_DIGEST_LENGTH];
      uint32_t truncated_digest = 0;

      if (difficulty == 0) {
          return 0;
      }

      if (difficulty > MAX_PUZZLE_DIFFICULTY) {
          HIP_ERROR("difficulty exceeds max. configured difficulty\n");
          return -1;
      }

      if (hip_build_digest(HIP_DIGEST_SHA1, puzzle_input,
                           sizeof(struct puzzle_hash_input), sha_digest) {
          HIP_ERROR("failed to compute hash digest\n");
          return -1;
      }

      if (ffs(truncated_digest) > difficulty) {
          return 0;
      }

      return 1;
  }

If this does not convince you, I can quote the relevant heuristics from
"Clean Code" at you :)

You can also make it slightly more compact by merging the if blocks with
else statements if you prefer.

> +int hip_solve_pu...

review: Needs Fixing

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

Hi René!

 review:needs_fixing

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

[M] The change from int to uint8_t is a step backwards in my opinion
for two reasons:

1) built-in types should be used in preference to defined types,
unless specifically required to, e.g., achieve a guaranteed data
layout. In this case this means that 'unsigned short' is preferable to
'uint8_t'.

2) I assume that uint8_t was chosen to limit the range of supported
values to 256 instead of 2^32, correct? Is 256 indeed a useful
limitation? I thought it should not be greater than 32 due to the
limitations of OpenWRT, right? So if 'hip_cookie_difficulty' is 33
it's just as bad as if it was 257, right? If that is so, it seems to
me that the change to 'uint8_t' does not have an advantage.
It has a disadvantage though: 'uint8_t' is less efficient to handle
than 'int' or 'unsigned int'.
Thus, I'd recommend to change the type to 'unsigned int' or leave it
at 'int'. The same goes for all related 'uint8_t' variables and
function arguments.

> +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)

[M] I guess the fact that 'sha_digest' is still a function parameter
instead of a local variable is due to our bad review/fix timing
yesterday?

> +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);

[L] Could these be assigned directly?

Stefan

[René Hummen (rene-hummen)]

On 13.04.2011, at 19:15, Diego Biurrun wrote:

> Review: Needs Fixing
> review needs-fixing
>
> On Wed, Apr 13, 2011 at 08:50:53AM +0000, René Hummen wrote:
>> René Hummen has proposed merging lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl.
>>
>> --- lib/core/builder.h 2011-04-02 20:38:36 +0000
>> +++ lib/core/builder.h 2011-04-13 08:50:40 +0000
>> @@ -126,11 +126,11 @@
>> -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);
>
> nit:
> Maybe you could add the parameter names while you're changing those
> lines anyway? That one of the most important headers in HIPL lacks
> parameter names in function declarations is extremely annoying.

No, I'm not going to fix builder.h here.

>> --- lib/core/solve.c 2011-01-24 10:21:17 +0000
>> +++ lib/core/solve.c 2011-04-13 08:50:40 +0000
>> @@ -43,108 +46,183 @@
>>
>> +static int hip_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input,
>> + const uint8_t difficulty)
>> {
>> + unsigned char sha_digest[SHA_DIGEST_LENGTH];
>> + uint32_t truncated_digest = 0;
>> + int err = -1;
>> +
>> + 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");
>> +
>> + if (ffs(truncated_digest) > difficulty) {
>> + err = 0;
>> + } else {
>> + err = 1;
>> + }
>> +
>> +out_err:
>> + return err;
>> +}
>
> You seem to insist on writing this with HIP_IFEL, but just compare how
> much neater this is with plain if-return (slightly redacted):
>
> static int hip_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input,
> const uint8_t difficulty)
> {
> unsigned char sha_digest[SHA_DIGEST_LENGTH];
> uint32_t truncated_digest = 0;
>
> if (difficulty == 0) {
> return 0;
> }
>
> if (difficulty > MAX_PUZZLE_DIFFICULTY) {
> HIP_ERROR("difficulty exceeds max. configured difficulty\n");
> return -1;
> }
>
> if (hip_build_digest(HIP_DIGEST_SHA1, puzzle_input,
> sizeof(struct puzzle_hash_input), sha_digest) {
> HIP_ERROR("failed to compute hash digest\n");
> return -1;
> }
>
> if (ffs(truncated_digest) > difficulty) {
> return 0;
> }
>
> return 1;
> }
>
> If this doe...

[René Hummen (rene-hummen)]

On 14.04.2011, at 08:21, Stefan Götz wrote:
> Hi René!
>
> review:needs_fixing
>
>> === modified file 'hipd/cookie.c'
>> --- hipd/cookie.c 2011-04-05 16:44:22 +0000
>> +++ hipd/cookie.c 2011-04-12 17:04:30 +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 */
>
> [M] The change from int to uint8_t is a step backwards in my opinion
> for two reasons:
>
> 1) built-in types should be used in preference to defined types,
> unless specifically required to, e.g., achieve a guaranteed data
> layout. In this case this means that 'unsigned short' is preferable to
> 'uint8_t'.

I don't mind the data type so much as long as it is unsigned. However, the difficulty will never be higher than 256 (see below).

> 2) I assume that uint8_t was chosen to limit the range of supported
> values to 256 instead of 2^32, correct? Is 256 indeed a useful
> limitation? I thought it should not be greater than 32 due to the
> limitations of OpenWRT, right? So if 'hip_cookie_difficulty' is 33
> it's just as bad as if it was 257, right? If that is so, it seems to
> me that the change to 'uint8_t' does not have an advantage.
> It has a disadvantage though: 'uint8_t' is less efficient to handle
> than 'int' or 'unsigned int'.
> Thus, I'd recommend to change the type to 'unsigned int' or leave it
> at 'int'. The same goes for all related 'uint80_t' variables and
> function arguments.

uint8_t is simply the length of the header field on the wire. That seems like a natural limitation for me. The fact that we only support difficulties up to 32 is just an implementation issue of one function and might change in the future.

>> +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)
>
> [M] I guess the fact that 'sha_digest' is still a function parameter
> instead of a local variable is due to our bad review/fix timing
> yesterday?

Hmm, that's a bit strange. The merge proposal on launchpad already show my change here.

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/

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

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

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

I'm fine with the current version.

review: Approve

[Christof Mroz (christof-mroz)]

Looks good; just some comments.
You don't renew your merge proposal if you address any of these, as far as I'm concerned (to speed things up).

> + * 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,
> + const uint8_t difficulty)
> {

Parameter documentation is out of sync (run `make doxygen` to catch all other instances).

> + 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);

Use %u for unsigned integers.

> +
> + /* 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);
> + compute_puzzle.initiator_hit = initiator_hit;
> + 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;
> + }

This should be the very first thing to check, to avoid copying at all.

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

If you're trying to avoid MAX_PUZZLE_SOLUTION_TRIES == 0, you should assert on that specifically (in addition to the assertion you added).

> +/**
> + * 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;
> +
> + // any puzzle solution is acceptable for difficulty 0
> + if (difficulty == 0) {
> + return 0;
> + }
> +
> + /* solution is correct iff:
> + * 0 == V := Ltrunc( ...

review: Approve

[Diego Biurrun (diego-biurrun)]

On Thu, Apr 14, 2011 at 09:24:22AM +0000, René Hummen wrote:
>
> On 13.04.2011, at 19:15, Diego Biurrun wrote:
>
> > On Wed, Apr 13, 2011 at 08:50:53AM +0000, René Hummen wrote:
> >> René Hummen has proposed merging lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl.
> >>
> HIP_IFEL is the way errors are handled throughout the code. I won't
> change this here.

Unfortunately you missed our analysis of HIP_IFEL during the code review
session from Friday. Clearly, HIP_IFEL is something that must go away.
Period.

Of course elimating all HIP_IFE* from HIPL is a large task and I am not
asking anyone to do it here. What I am asking of you is not to make the
problem worse by introducing more instances of the problem, which I
consider reasonable.

Consistency is all nice and dandy if you have to choose between equal
alternatives. But if you have a problem, then consistency can never
be an argument for introducing more problem instances.

> >> +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;
> >> +
> >> + /* 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);
> >> + compute_puzzle.initiator_hit = initiator_hit;
> >> + compute_puzzle.responder_hit = responder_hit;
> >
> > Replace the memcpy by an assignment.
>
> Wouldn't that just copy references?

Yes, you are right, that will not work.

> >> --- lib/tool/pk.c 2011-04-04 13:59:21 +0000
> >> +++ lib/tool/pk.c 2011-04-13 08:50:40 +0000
> >> @@ -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);
> >
> > It seems these could be replaced by assignments as well...
>
> Same here.

pz->opaque is an array, but pz->I is a uint64_t, so at least the latter
could simply be assigned.

> >> --- test/lib/core/solve.c 1970-01-01 00:00:00 +0000
> >> +++ test/lib/core/solve.c 2011-04-13 08:50:40 +0000
> >
> > This file did not pass through uncrustify.
>
> Of course it did not. Did you have a look recently at what the output
> would look like?

Sure, but it's not hard to undo the merging of the macros onto single
lines...

> >> @@ -0,0 +1,200 @@
> >> +START_TEST(test_hip_solve_puzzle_NULL_solution)
> >> +{
> >> + uint8_...

[Diego Biurrun (diego-biurrun)]

 review needs-fixing

On Wed, Apr 13, 2011 at 08:50:53AM +0000, René Hummen wrote:
> René Hummen has proposed merging lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl.
>
> --- lib/core/solve.c 2011-01-24 10:21:17 +0000
> +++ lib/core/solve.c 2011-04-13 08:50:40 +0000
> @@ -43,108 +46,183 @@
>
> +/** 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));
> +
> +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])
> +{

Just pass a puzzle_hash_input struct to the function and you go down
from five to two parameters.

> +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)
> +{

same

Diego

review: Needs Fixing

[Diego Biurrun (diego-biurrun)]

On Mon, Apr 18, 2011 at 01:22:04PM +0200, Diego Biurrun wrote:
> On Thu, Apr 14, 2011 at 09:24:22AM +0000, René Hummen wrote:
> >
> > On 13.04.2011, at 19:15, Diego Biurrun wrote:
> >
> > > On Wed, Apr 13, 2011 at 08:50:53AM +0000, René Hummen wrote:
> > >> René Hummen has proposed merging lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl.
> > >>
> > >> --- lib/tool/pk.c 2011-04-04 13:59:21 +0000
> > >> +++ lib/tool/pk.c 2011-04-13 08:50:40 +0000
> > >> @@ -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);
> > >
> > > It seems these could be replaced by assignments as well...
> >
> > Same here.
>
> pz->opaque is an array, but pz->I is a uint64_t, so at least the latter
> could simply be assigned.

Scratch that comment, I forgot that you modified that struct..

Diego

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

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

[René Hummen (rene-hummen)]

Merged to trunk in revision 5879.

=== modified file 'Makefile.am'
--- Makefile.am	2011-04-06 15:52:33 +0000
+++ Makefile.am	2011-04-19 15:56:06 +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-19 15:56:06 +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;
@@ -322,7 +322,8 @@
     const struct hip_puzzle  *puzzle = NULL;
     struct hip_r1entry       *result = NULL;
     struct hip_host_id_entry *hid    = NULL;
-    int                       err    = 0;
+    struct puzzle_hash_input  puzzle_input;
+    int                       err = 0;
 
     /* Find the proper R1 table */
     HIP_IFEL(!(hid = hip_get_hostid_entry_by_lhi_and_algo(HIP_DB_LOCAL_HID,
@@ -347,7 +348,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 +357,20 @@
     } 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");
+    memcpy(puzzle_input.puzzle, solution->I, PUZZLE_LENGTH);
+    puzzle_input.initiator_hit = hdr->hits;
+    puzzle_input.responder_hit = hdr->hitr;
+    memcpy(puzzle_input.solution, solution->J, PUZZLE_LENGTH);
+
+    HIP_IFEL(hip_verify_puzzle_solution(&puzzle_input, solution->K),
+             -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-19 15:56:06 +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-14 08:55:31 +0000
+++ hipd/input.c	2011-04-19 15:56:06 +0000
@@ -50,6 +50,7 @@
 #include <arpa/inet.h>
 #include <netinet/in.h>
 #include <openssl/lhash.h>
+#include <openssl/rand.h>
 #include <sys/types.h>
 
 #include "lib/core/builder.h"
@@ -234,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;
@@ -794,6 +795,7 @@
 {
     int                          err    = 0, retransmission = 0;
     const struct hip_r1_counter *r1cntr = NULL;
+    struct puzzle_hash_input     puzzle_input;
 
     if (ha_state == HIP_STATE_I2_SENT) {
         HIP_DEBUG("Retransmission\n");
@@ -828,16 +830,23 @@
     /* 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,
+
+        memcpy(puzzle_input.puzzle, pz->I, PUZZLE_LENGTH);
+        puzzle_input.initiator_hit = ctx->input_msg->hitr;
+        puzzle_input.responder_hit = ctx->input_msg->hits;
+        RAND_bytes(puzzle_input.solution, PUZZLE_LENGTH);
+
+        HIP_IFEL(hip_solve_puzzle(&puzzle_input, pz->K),
                  -EINVAL, "Solving of puzzle failed\n");
-        ctx->hadb_entry->puzzle_i = pz2->I;
+
+        memcpy(ctx->hadb_entry->puzzle_i, pz->I, PUZZLE_LENGTH);
+        memcpy(ctx->hadb_entry->puzzle_solution,
+               puzzle_input.solution,
+               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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +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-04-18 11:59:17 +0000
+++ lib/core/solve.c	2011-04-19 15:56:06 +0000
@@ -28,11 +28,13 @@
  * @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 "config.h"
 #include "builder.h"
@@ -42,109 +44,134 @@
 #include "protodefs.h"
 #include "solve.h"
 
+// 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 puzzle_input      puzzle to be solved or verified
+ * @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,
+                                         const uint8_t difficulty)
 {
-    uint64_t mask     = 0;
-    uint64_t randval  = 0;
-    uint64_t maxtries = 0;
-    uint64_t digest   = 0;
-    uint8_t  cookie[48];
-    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;
-
-    if (u->pz.K > HIP_PUZZLE_MAX_K) {
-        HIP_ERROR("Cookie K %u is higher than we are willing to calculate"
-                  " (current max K=%d)\n", u->pz.K, HIP_PUZZLE_MAX_K);
+    unsigned char sha_digest[SHA_DIGEST_LENGTH];
+    uint32_t      truncated_digest = 0;
+    int           err              = -1;
+
+    /* any puzzle solution is acceptable for difficulty 0 */
+    if (difficulty == 0) {
         return 0;
     }
 
-    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));
+    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_ERROR("Unknown mode: %d\n", mode);
+        err = 1;
+    }
+
+out_err:
+    return err;
+}
+
+/**
+ * Solve a computational puzzle for HIP
+ *
+ * @param puzzle_input  puzzle to be solved or verified
+ * @param difficulty    difficulty of the puzzle
+ * @return 0 when solution was found, 1 in case no solution was found after
+ *         ::MAX_PUZZLE_SOLUTION_TRIES, -1 in case of an error
+ *
+ * @note provide data for all members of puzzle_input when calling this function
+ * @note puzzle_input will contain the solution on successful exit
+ */
+int hip_solve_puzzle(struct puzzle_hash_input *const puzzle_input,
+                     const uint8_t difficulty)
+{
+    int err = -1;
+
+    // any puzzle solution is acceptable for difficulty 0
+    if (difficulty == 0) {
         return 0;
     }
 
-    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;
-        }
-
-        /* It seems like the puzzle was not correctly solved */
-        if (mode == HIP_VERIFY_PUZZLE) {
-            HIP_ERROR("Puzzle incorrect\n");
+    /* 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);
+
+    if (difficulty > MAX_PUZZLE_DIFFICULTY) {
+        HIP_ERROR("Cookie (K = %u) is higher than we are willing to calculate "
+                  "(current max K = %u)\n", difficulty, MAX_PUZZLE_DIFFICULTY);
+        return -1;
+    }
+
+    for (unsigned long long i = 0; i < MAX_PUZZLE_SOLUTION_TRIES; i++) {
+        err = hip_single_puzzle_computation(puzzle_input,
+                                            difficulty);
+        if (err == 0) {
             return 0;
+        } else if (err > 0) {
+            // increase random value by one and try again
+            (*(uint64_t *) puzzle_input->solution)++;
+        } else {
+            HIP_ERROR("error while computing the puzzle solution\n");
+            memset(puzzle_input, 0, PUZZLE_LENGTH);
+            return -1;
         }
-        randval++;
     }
 
     HIP_ERROR("Could not solve the puzzle, no solution found\n");
+    return 1;
+}
+
+/**
+ * Verify a computational puzzle for HIP
+ *
+ * @param puzzle_input  puzzle to be solved or verified
+ * @param difficulty    difficulty of the puzzle
+ * @return 0 when solution is correct, -1 otherwise
+ */
+int hip_verify_puzzle_solution(const struct puzzle_hash_input *const puzzle_input,
+                               const uint8_t difficulty)
+{
+    // any puzzle solution is acceptable for difficulty 0
+    if (difficulty == 0) {
+        return 0;
+    }
+
+    if (hip_single_puzzle_computation(puzzle_input, difficulty)) {
+        HIP_ERROR("failed to verify puzzle solution\n");
+        return -1;
+    }
 
     return 0;
 }

=== modified file 'lib/core/solve.h'
--- lib/core/solve.h	2010-10-15 15:29:14 +0000
+++ lib/core/solve.h	2011-04-19 15:56:06 +0000
@@ -30,10 +30,29 @@
 
 #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);
+/* ensure that the max puzzle difficulty (here 28) is limited by sizeof(int),
+ * as ffs() is working on int type.
+ *
+ * NOTE: 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;
+
+/** 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
+ *
+ *  solution is correct iff:
+ *  0 == V := Ltrunc( RHASH( I2.I | I2.hit_i | I2.hit_r | I2.J ), K ) */
+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));
+
+int hip_solve_puzzle(struct puzzle_hash_input *puzzle_input,
+                     const uint8_t difficulty);
+
+int hip_verify_puzzle_solution(const struct puzzle_hash_input *const puzzle_input,
+                               const uint8_t difficulty);
 
 #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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +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-19 15:56:06 +0000
@@ -0,0 +1,136 @@
+/*
+ * Copyright (c) 2011 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"
+
+
+START_TEST(test_hip_solve_puzzle_0_K)
+{
+    struct puzzle_hash_input puzzle_input = { { 0 } };
+    uint8_t                  difficulty   = 0;
+
+    RAND_bytes(puzzle_input.puzzle, sizeof(PUZZLE_LENGTH));
+
+    fail_unless(hip_solve_puzzle(&puzzle_input, difficulty) == 0, NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_5_K)
+{
+    struct puzzle_hash_input puzzle_input = { { 0 } };
+    uint8_t                  difficulty   = 5;
+
+    RAND_bytes(puzzle_input.puzzle, sizeof(PUZZLE_LENGTH));
+
+    fail_unless(hip_solve_puzzle(&puzzle_input, difficulty) == 0, NULL);
+}
+END_TEST
+
+START_TEST(test_hip_solve_puzzle_exceeding_K)
+{
+    struct puzzle_hash_input puzzle_input = { { 0 } };
+    uint8_t                  difficulty   = MAX_PUZZLE_DIFFICULTY + 1;
+
+    RAND_bytes(puzzle_input.puzzle, sizeof(PUZZLE_LENGTH));
+
+    fail_unless(hip_solve_puzzle(&puzzle_input, difficulty) == -1, NULL);
+}
+END_TEST
+
+START_TEST(test_hip_verify_puzzle_solution_invalid)
+{
+    struct puzzle_hash_input puzzle_input = { { 0 } };
+    uint8_t                  difficulty   = 5;
+
+    memset(puzzle_input.puzzle, 1, PUZZLE_LENGTH);
+
+    fail_unless(hip_verify_puzzle_solution(&puzzle_input, difficulty) == -1, NULL);
+}
+END_TEST
+
+START_TEST(test_hip_verify_puzzle_solution_against_ourselves)
+{
+    struct puzzle_hash_input puzzle_input = { { 0 } };
+    uint8_t                  difficulty   = 5;
+
+    RAND_bytes(puzzle_input.puzzle, sizeof(PUZZLE_LENGTH));
+
+    fail_unless(hip_solve_puzzle(&puzzle_input, difficulty) == 0, NULL);
+    fail_unless(hip_verify_puzzle_solution(&puzzle_input, difficulty) == 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;
+    struct puzzle_hash_input puzzle_input;
+
+    inet_pton(AF_INET6, initiator_hit_str, &initiator_hit);
+    inet_pton(AF_INET6, responder_hit_str, &responder_hit);
+
+    memcpy(puzzle_input.puzzle, solution->I, PUZZLE_LENGTH);
+    puzzle_input.initiator_hit = initiator_hit;
+    puzzle_input.responder_hit = responder_hit;
+    memcpy(puzzle_input.solution, solution->J, PUZZLE_LENGTH);
+
+    fail_unless(hip_verify_puzzle_solution(&puzzle_input, solution->K) == 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_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-19 15:56:06 +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 */