Merge lp:~rene-hummen/hipl/puzzle-fixes into lp:hipl
- puzzle-fixes
- Merge into trunk
Status: | Superseded |
---|---|
Proposed branch: | lp:~rene-hummen/hipl/puzzle-fixes |
Merge into: | lp:hipl |
Diff against target: |
960 lines (+464/-156) 17 files modified
Makefile.am (+1/-0) hipd/cookie.c (+12/-8) hipd/cookie.h (+2/-2) hipd/input.c (+10/-9) hipd/keymat.c (+10/-11) hipd/keymat.h (+3/-1) hipd/output.c (+4/-5) lib/core/builder.c (+8/-5) lib/core/builder.h (+6/-6) lib/core/protodefs.h (+7/-3) lib/core/solve.c (+169/-91) lib/core/solve.h (+18/-5) lib/core/state.h (+2/-2) lib/tool/pk.c (+10/-8) test/check_lib_core.c (+1/-0) test/lib/core/solve.c (+200/-0) test/lib/core/test_suites.h (+1/-0) |
To merge this branch: | bzr merge lp:~rene-hummen/hipl/puzzle-fixes |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Miika Komu | Approve | ||
Christof Mroz | Approve | ||
Diego Biurrun | Pending | ||
Stefan Götz | Pending | ||
Review via email: mp+57363@code.launchpad.net |
This proposal supersedes a proposal from 2011-04-08.
This proposal has been superseded by a proposal from 2011-04-13.
Commit message
Description of the change
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.
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
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[
>> 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) wrote : Posted in a previous version of this proposal | # |
The algorithm seems changed. Did you test it against the old, interoperable implementation?
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
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_
>> + unsigned char sha_digest[
>> + 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(
>> - (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(
>> -
>> - if (mode == HIP_VERIFY_PUZZLE) {
>> - ipv6_addr_
>> - ipv6_addr_
>> - randval = u->sl.J;
>> - maxtries = 1;
>> - } else if (mode == HIP_SOLVE_PUZZLE) {
>> - ipv6_addr_
>> - ipv6_addr_
>> - maxtries = 1ULL << (u->pz.K + 3);
>> - get_random_
>> + uint32_t truncated_digest = 0;
>> + int err = -1;
>> +
>> + HIP_IFEL(difficulty > max_puzzle_
>> + 1, "difficulty exceeds max. configured difficulty\n");
>> +
>> + HIP_IFEL(
>> + 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[
>
> The 8 least significant bytes have index 0..7. Also, sizeof(uint32_t) is 4, not 8.
>
>> +int hip_solve_
>> + const int difficulty,
>> + const hip_hit_t...
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
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: +49 241 80 20772
web: http://
Diego Biurrun (diego-biurrun) wrote : Posted in a previous version of this proposal | # |
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_
> + unsigned char sha_digest[
> + const int difficulty)
> {
> + HIP_IFEL(difficulty > max_puzzle_
> + -1, "difficulty exceeds max. configured difficulty\n");
> +
> + HIP_IFEL(
> + 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_
> + 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_
> + */
> +int hip_solve_
> + const int difficulty,
> + const hip_hit_t initiator_hit,
> + const hip_hit_t responder_hit,
> + uint8_t solution[
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_
> + const uint8_t difficulty,
> + const hip_hit_t initiator_hit,
> + const hip_hit_t responder_hit,
> + const uint8_t solution[
Having solution as third paramete...
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
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_
> + */
Prepend :: to create a hyperlink to a global in doxygen, e.g.
::MAX_PUZZLE_
> + ipv6_addr_
> + ipv6_addr_
struct in6_addr can be copied using assignment AFAIK (there are more instances of this).
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
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_
> +static int hip_cookie_
[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_
[M] 'const int k' for const correctness and boyscouting
> {
> - if (k > HIP_PUZZLE_MAX_K || k < 1) {
> + if (k > max_puzzle_
[M] k is not ever supposed to be < 0, correct? If yes, please give it
an unsigned type.
> === modified file 'lib/core/
> --- 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_
> - uint8_t lifetime, uint32_t opaque, uint64_t random_i)
> + uint8_t lifetime, uint32_t opaque,
> + const uint8_t random_
[M] const correctness for boyscouting
> === modified file 'lib/core/
> --- 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_
> const struct hip_puzzle *,
> - uint64_t);
> + uint8_t *);
[M] 'uint8_t *const'?
> === modified file 'lib/core/
> --- lib/core/
> +++ lib/core/
> @@ -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[
> + hip_hit_t initiator_hit;
> + hip_hit_t responder_hit;
> + uint8_t solution[
> +} __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) wrote : Posted in a previous version of this proposal | # |
Forgot my verdict on this merge proposal.
René Hummen (rene-hummen) wrote : Posted in a previous version of this proposal | # |
On 08.04.2011, at 20:08, Christof Mroz wrote:
> Review: Approve
> Looks good; feel free to address the following points.
>
>> + ipv6_addr_
>> + ipv6_addr_
>
> 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: +49 241 80 20772
web: http://
Christof Mroz (christof-mroz) wrote : Posted in a previous version of this proposal | # |
On Tue, 12 Apr 2011 13:15:56 +0200, René Hummen
<email address hidden> wrote:
>>> + ipv6_addr_
>>> + ipv6_addr_
>>
>> 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) wrote : Posted in a previous version of this proposal | # |
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_
>> +static int hip_cookie_
>
> [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_
>> === modified file 'lib/core/
>> --- lib/core/
>> +++ lib/core/
>> @@ -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_
>> + unsigned char sha_digest[
>> + 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_
>> + const uint8_t difficulty,
>> + const hip_hit_t initiator_hit,
>> + const hip_hit_t responder_hit,
>> + const uint8_t solution[
>
> [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_
>> - ...
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : Posted in a previous version of this proposal | # |
>> 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) wrote : Posted in a previous version of this proposal | # |
Hi Rene!
Anything I haven't commented on I agree with and consider my previous
comments to be void.
>>> +static int hip_calculate_
>>> + unsigned char sha_digest[
>>> + 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_
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) wrote : | # |
Looks good to me.
- 5876. By René Hummen
-
replace ipv6_addr_copy() by simple assignment
- 5877. By René Hummen
-
declare sha_digest as a local variable
- 5878. By René Hummen
-
improve documentation of MAX_PUZZLE_
DIFFICULTY
Stefan Götz (stefan.goetz-deactivatedaccount) wrote : | # |
Hi René!
review:
> === 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_
> +static uint8_t hip_cookie_
[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_
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_
> + unsigned char sha_digest[
> + 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_
> + const uint8_t difficulty,
> + const hip_hit_t initiator_hit,
> + const hip_hit_t responder_hit,
> + uint8_t solution[
> +{
> + struct puzzle_hash_input compute_puzzle;
> + unsigned char sha_digest[
> + int err = -1;
> + unsigned long long i = 0;
> +
> + /* solution must reference allocated memory here */
> + HIP_ASSERT(
> +
> + HIP_IFEL(difficulty > MAX_PUZZLE_
> + "Cookie (K = %i) is higher than we are willing to calculate"
> + " (current max K = %i)\n", difficulty, MAX_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(
> + ipv6_addr_
> + ipv6_addr_
[L] Could these be assigned directly?
Stefan
René Hummen (rene-hummen) wrote : | # |
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_
>> +static uint8_t hip_cookie_
>
> [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_
> 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_
>> + unsigned char sha_digest[
>> + 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: +49 241 80 20772
web: http://
- 5879. By René Hummen
-
replace ipv6_addr_copy() by an assignment
- 5880. By René Hummen
-
minor change in local var ordering
- 5881. By René Hummen
-
change year of copyright
- 5882. By René Hummen
-
use struct puzzle_hash_input in puzzle api
- 5883. By René Hummen
-
fix doxygen
- 5884. By René Hummen
-
change output type from int to uint
- 5885. By René Hummen
-
directly exit hip_solve_puzzle instead of using break indirection
- 5886. By René Hummen
-
merge trunk revision 5878
Unmerged revisions
- 5886. By René Hummen
-
merge trunk revision 5878
- 5885. By René Hummen
-
directly exit hip_solve_puzzle instead of using break indirection
- 5884. By René Hummen
-
change output type from int to uint
- 5883. By René Hummen
-
fix doxygen
- 5882. By René Hummen
-
use struct puzzle_hash_input in puzzle api
- 5881. By René Hummen
-
change year of copyright
- 5880. By René Hummen
-
minor change in local var ordering
- 5879. By René Hummen
-
replace ipv6_addr_copy() by an assignment
- 5878. By René Hummen
-
improve documentation of MAX_PUZZLE_
DIFFICULTY - 5877. By René Hummen
-
declare sha_digest as a local variable
Preview Diff
1 | === modified file 'Makefile.am' |
2 | --- Makefile.am 2011-04-06 15:52:33 +0000 |
3 | +++ Makefile.am 2011-04-13 08:50:43 +0000 |
4 | @@ -207,6 +207,7 @@ |
5 | |
6 | test_check_lib_core_SOURCES = test/check_lib_core.c \ |
7 | test/lib/core/hit.c \ |
8 | + test/lib/core/solve.c \ |
9 | test/lib/core/straddr.c |
10 | |
11 | test_check_lib_tool_SOURCES = test/check_lib_tool.c \ |
12 | |
13 | === modified file 'hipd/cookie.c' |
14 | --- hipd/cookie.c 2011-04-05 16:44:22 +0000 |
15 | +++ hipd/cookie.c 2011-04-13 08:50:43 +0000 |
16 | @@ -56,7 +56,7 @@ |
17 | |
18 | #define HIP_R1TABLESIZE 3 /* precreate only this many R1s */ |
19 | |
20 | -static int hip_cookie_difficulty = 1ULL; /* a difficulty of i leads to approx. 2^(i-1) hash computations during BEX */ |
21 | +static uint8_t hip_cookie_difficulty = 0; /* a difficulty of i leads to approx. 2^(i-1) hash computations during BEX */ |
22 | |
23 | /** |
24 | * query for current puzzle difficulty |
25 | @@ -75,11 +75,11 @@ |
26 | * @param k the new puzzle difficulty |
27 | * @return the k value on success or negative on error |
28 | */ |
29 | -static int hip_set_cookie_difficulty(int k) |
30 | +static int hip_set_cookie_difficulty(const uint8_t k) |
31 | { |
32 | - if (k > HIP_PUZZLE_MAX_K || k < 1) { |
33 | + if (k > MAX_PUZZLE_DIFFICULTY) { |
34 | HIP_ERROR("Bad cookie value (%d), min=%d, max=%d\n", |
35 | - k, 1, HIP_PUZZLE_MAX_K); |
36 | + k, 1, MAX_PUZZLE_DIFFICULTY); |
37 | return -1; |
38 | } |
39 | hip_cookie_difficulty = k; |
40 | @@ -347,7 +347,7 @@ |
41 | |
42 | HIP_IFEL(solution->K != result->Ck, -1, |
43 | "Solution's K did not match any sent Ks.\n"); |
44 | - HIP_IFEL(solution->I != result->Ci, -1, |
45 | + HIP_IFEL(memcmp(solution->I, result->Ci, PUZZLE_LENGTH), -1, |
46 | "Solution's I did not match the sent I\n"); |
47 | HIP_IFEL(memcmp(solution->opaque, result->Copaque, |
48 | HIP_PUZZLE_OPAQUE_LEN), -1, |
49 | @@ -356,15 +356,19 @@ |
50 | } else { |
51 | HIP_HEXDUMP("solution", solution, sizeof(*solution)); |
52 | HIP_HEXDUMP("puzzle", puzzle, sizeof(*puzzle)); |
53 | - HIP_IFEL(solution->I != puzzle->I, -1, |
54 | + HIP_IFEL(memcmp(solution->I, puzzle->I, PUZZLE_LENGTH), -1, |
55 | "Solution's I did not match the sent I\n"); |
56 | HIP_IFEL(memcmp(solution->opaque, puzzle->opaque, |
57 | HIP_PUZZLE_OPAQUE_LEN), -1, |
58 | "Solution's opaque data does not match the opaque data sent\n"); |
59 | } |
60 | |
61 | - HIP_IFEL(!hip_solve_puzzle(solution, hdr, HIP_VERIFY_PUZZLE), -1, |
62 | - "Puzzle incorrectly solved.\n"); |
63 | + HIP_IFEL(hip_verify_puzzle_solution(solution->I, |
64 | + solution->J, |
65 | + solution->K, |
66 | + hdr->hits, |
67 | + hdr->hitr), |
68 | + -1, "Puzzle incorrectly solved.\n"); |
69 | |
70 | out_err: |
71 | return err; |
72 | |
73 | === modified file 'hipd/cookie.h' |
74 | --- hipd/cookie.h 2011-01-10 13:12:17 +0000 |
75 | +++ hipd/cookie.h 2011-04-13 08:50:43 +0000 |
76 | @@ -34,9 +34,9 @@ |
77 | struct hip_r1entry { |
78 | struct hip_common *r1; |
79 | uint32_t generation; |
80 | - uint64_t Ci; |
81 | + uint8_t Ci[PUZZLE_LENGTH]; |
82 | uint8_t Ck; |
83 | - uint8_t Copaque[3]; |
84 | + uint8_t Copaque[HIP_PUZZLE_OPAQUE_LEN]; |
85 | }; |
86 | |
87 | struct hip_common *hip_get_r1(struct in6_addr *ip_i, |
88 | |
89 | === modified file 'hipd/input.c' |
90 | --- hipd/input.c 2011-04-11 12:48:58 +0000 |
91 | +++ hipd/input.c 2011-04-13 08:50:43 +0000 |
92 | @@ -235,8 +235,8 @@ |
93 | * @return zero on success, or negative on error. |
94 | */ |
95 | static int hip_produce_keying_material(struct hip_packet_context *ctx, |
96 | - uint64_t I, |
97 | - uint64_t J) |
98 | + const uint8_t I[PUZZLE_LENGTH], |
99 | + const uint8_t J[PUZZLE_LENGTH]) |
100 | { |
101 | char *dh_shared_key = NULL; |
102 | int hip_transf_length, hmac_transf_length; |
103 | @@ -868,16 +868,17 @@ |
104 | /* Solve puzzle: if this is a retransmission, we have to preserve |
105 | * the old solution. */ |
106 | if (!retransmission) { |
107 | - const struct hip_puzzle *pz2 = NULL; |
108 | + const struct hip_puzzle *pz = NULL; |
109 | |
110 | - HIP_IFEL(!(pz2 = hip_get_param(ctx->input_msg, HIP_PARAM_PUZZLE)), -EINVAL, |
111 | + HIP_IFEL(!(pz = hip_get_param(ctx->input_msg, HIP_PARAM_PUZZLE)), -EINVAL, |
112 | "Malformed R1 packet. PUZZLE parameter missing\n"); |
113 | - HIP_IFEL((ctx->hadb_entry->puzzle_solution = |
114 | - hip_solve_puzzle(pz2, |
115 | - ctx->input_msg, |
116 | - HIP_SOLVE_PUZZLE)) == 0, |
117 | + HIP_IFEL(hip_solve_puzzle(pz->I, |
118 | + pz->K, |
119 | + ctx->input_msg->hitr, |
120 | + ctx->input_msg->hits, |
121 | + ctx->hadb_entry->puzzle_solution), |
122 | -EINVAL, "Solving of puzzle failed\n"); |
123 | - ctx->hadb_entry->puzzle_i = pz2->I; |
124 | + memcpy(ctx->hadb_entry->puzzle_i, pz->I, PUZZLE_LENGTH); |
125 | } |
126 | |
127 | HIP_DEBUG("Build normal I2.\n"); |
128 | |
129 | === modified file 'hipd/keymat.c' |
130 | --- hipd/keymat.c 2011-01-11 13:59:46 +0000 |
131 | +++ hipd/keymat.c 2011-04-13 08:50:43 +0000 |
132 | @@ -58,19 +58,18 @@ |
133 | static uint8_t *hip_create_keymat_buffer(char *kij, size_t kij_len, size_t hash_len, |
134 | struct in6_addr *smaller_hit, |
135 | struct in6_addr *bigger_hit, |
136 | - uint64_t I, uint64_t J) |
137 | + const uint8_t I[PUZZLE_LENGTH], |
138 | + const uint8_t J[PUZZLE_LENGTH]) |
139 | |
140 | { |
141 | uint8_t *buffer = NULL, *cur = NULL; |
142 | size_t requiredmem; |
143 | |
144 | - HIP_DEBUG("\n"); |
145 | - /* 2*sizeof(uint64_t) added to take care of I and J. */ |
146 | if (2 * sizeof(struct in6_addr) < hash_len) { |
147 | - requiredmem = kij_len + hash_len + sizeof(uint8_t) + 2 * sizeof(uint64_t); |
148 | + requiredmem = kij_len + hash_len + sizeof(uint8_t) + 2 * PUZZLE_LENGTH; |
149 | } else { |
150 | requiredmem = kij_len + 2 * sizeof(struct in6_addr) + |
151 | - sizeof(uint8_t) + 2 * sizeof(uint64_t); |
152 | + sizeof(uint8_t) + 2 * PUZZLE_LENGTH; |
153 | } |
154 | buffer = malloc(requiredmem); |
155 | if (!buffer) { |
156 | @@ -85,10 +84,10 @@ |
157 | cur += sizeof(struct in6_addr); |
158 | memcpy(cur, (uint8_t *) bigger_hit, sizeof(struct in6_addr)); |
159 | cur += sizeof(struct in6_addr); |
160 | - memcpy(cur, &I, sizeof(uint64_t)); // XX CHECK: network byte order? |
161 | - cur += sizeof(uint64_t); |
162 | - memcpy(cur, &J, sizeof(uint64_t)); // XX CHECK: network byte order? |
163 | - cur += sizeof(uint64_t); |
164 | + memcpy(cur, I, PUZZLE_LENGTH); |
165 | + cur += PUZZLE_LENGTH; |
166 | + memcpy(cur, J, PUZZLE_LENGTH); |
167 | + cur += PUZZLE_LENGTH; |
168 | *(cur) = 1; |
169 | cur += sizeof(uint8_t); |
170 | |
171 | @@ -138,8 +137,8 @@ |
172 | struct in6_addr *hit1, |
173 | struct in6_addr *hit2, |
174 | uint8_t *calc_index, |
175 | - uint64_t I, |
176 | - uint64_t J) |
177 | + const uint8_t I[PUZZLE_LENGTH], |
178 | + const uint8_t J[PUZZLE_LENGTH]) |
179 | { |
180 | int bufsize; |
181 | uint8_t index_nbr = 1; |
182 | |
183 | === modified file 'hipd/keymat.h' |
184 | --- hipd/keymat.h 2010-10-15 15:29:14 +0000 |
185 | +++ hipd/keymat.h 2011-04-13 08:50:43 +0000 |
186 | @@ -37,7 +37,9 @@ |
187 | void hip_make_keymat(char *kij, size_t kij_len, |
188 | struct hip_keymat_keymat *keymat, |
189 | void *dstbuf, size_t dstbuflen, struct in6_addr *hit1, |
190 | - struct in6_addr *hit2, uint8_t *calc_index, uint64_t I, uint64_t J); |
191 | + struct in6_addr *hit2, uint8_t *calc_index, |
192 | + const uint8_t I[PUZZLE_LENGTH], |
193 | + const uint8_t J[PUZZLE_LENGTH]); |
194 | int hip_keymat_draw_and_copy(unsigned char *dst, |
195 | struct hip_keymat_keymat *keymat, |
196 | int len); |
197 | |
198 | === modified file 'hipd/output.c' |
199 | --- hipd/output.c 2011-04-11 12:56:12 +0000 |
200 | +++ hipd/output.c 2011-04-13 08:50:43 +0000 |
201 | @@ -652,8 +652,10 @@ |
202 | /********** R1_COUNTER (OPTIONAL) *********/ |
203 | |
204 | /********** PUZZLE ************/ |
205 | + const uint8_t zero_i[PUZZLE_LENGTH] = { 0 }; |
206 | + |
207 | HIP_IFEL(hip_build_param_puzzle(err, cookie_k, |
208 | - 42 /* 2^(42-32) sec lifetime */, 0, 0), |
209 | + 42 /* 2^(42-32) sec lifetime */, 0, zero_i), |
210 | NULL, "Cookies were burned. Bummer!\n"); |
211 | |
212 | /* Parameter Diffie-Hellman */ |
213 | @@ -718,7 +720,6 @@ |
214 | /* Fill puzzle parameters */ |
215 | { |
216 | struct hip_puzzle *pz; |
217 | - uint64_t random_i; |
218 | |
219 | HIP_IFEL(!(pz = hip_get_param_readwrite(err, HIP_PARAM_PUZZLE)), NULL, |
220 | "Internal error\n"); |
221 | @@ -727,9 +728,7 @@ |
222 | pz->opaque[0] = 'H'; |
223 | pz->opaque[1] = 'I'; |
224 | //pz->opaque[2] = 'P'; |
225 | - /** @todo Remove random_i variable. */ |
226 | - get_random_bytes(&random_i, sizeof(random_i)); |
227 | - pz->I = random_i; |
228 | + get_random_bytes(pz->I, PUZZLE_LENGTH); |
229 | } |
230 | |
231 | /* Packet ready */ |
232 | |
233 | === modified file 'lib/core/builder.c' |
234 | --- lib/core/builder.c 2011-04-07 16:58:58 +0000 |
235 | +++ lib/core/builder.c 2011-04-13 08:50:43 +0000 |
236 | @@ -2384,8 +2384,11 @@ |
237 | * |
238 | * @return zero for success, or non-zero on error |
239 | */ |
240 | -int hip_build_param_puzzle(struct hip_common *msg, uint8_t val_K, |
241 | - uint8_t lifetime, uint32_t opaque, uint64_t random_i) |
242 | +int hip_build_param_puzzle(struct hip_common *const msg, |
243 | + const uint8_t val_K, |
244 | + const uint8_t lifetime, |
245 | + const uint32_t opaque, |
246 | + const uint8_t random_i[PUZZLE_LENGTH]) |
247 | { |
248 | struct hip_puzzle puzzle; |
249 | int err = 0; |
250 | @@ -2402,7 +2405,7 @@ |
251 | puzzle.lifetime = lifetime; |
252 | puzzle.opaque[0] = opaque & 0xFF; |
253 | puzzle.opaque[1] = (opaque & 0xFF00) >> 8; |
254 | - puzzle.I = random_i; |
255 | + memcpy(puzzle.I, random_i, PUZZLE_LENGTH); |
256 | |
257 | err = hip_build_generic_param(msg, &puzzle, |
258 | sizeof(struct hip_tlv_common), |
259 | @@ -2515,7 +2518,7 @@ |
260 | */ |
261 | int hip_build_param_solution(struct hip_common *msg, |
262 | const struct hip_puzzle *pz, |
263 | - uint64_t val_J) |
264 | + uint8_t val_J[PUZZLE_LENGTH]) |
265 | { |
266 | struct hip_solution cookie; |
267 | int err = 0; |
268 | @@ -2527,7 +2530,7 @@ |
269 | /* Type 2 (in R1) or 3 (in I2) */ |
270 | hip_set_param_type((struct hip_tlv_common *) &cookie, HIP_PARAM_SOLUTION); |
271 | |
272 | - cookie.J = val_J; |
273 | + memcpy(cookie.J, val_J, PUZZLE_LENGTH); |
274 | memcpy(&cookie.K, &pz->K, 12); /* copy: K (1), reserved (1), |
275 | * opaque (2) and I (8 bytes). */ |
276 | cookie.reserved = 0; |
277 | |
278 | === modified file 'lib/core/builder.h' |
279 | --- lib/core/builder.h 2011-04-02 20:38:36 +0000 |
280 | +++ lib/core/builder.h 2011-04-13 08:50:43 +0000 |
281 | @@ -126,11 +126,11 @@ |
282 | uint8_t, |
283 | void *, |
284 | size_t); |
285 | -int hip_build_param_puzzle(struct hip_common *, |
286 | - uint8_t, |
287 | - uint8_t, |
288 | - uint32_t, |
289 | - uint64_t); |
290 | +int hip_build_param_puzzle(struct hip_common *const msg, |
291 | + const uint8_t val_K, |
292 | + const uint8_t lifetime, |
293 | + const uint32_t opaque, |
294 | + const uint8_t *const random_i); |
295 | |
296 | int hip_build_param_challenge_request(struct hip_common *, |
297 | uint8_t, |
298 | @@ -150,7 +150,7 @@ |
299 | uint8_t); |
300 | int hip_build_param_solution(struct hip_common *, |
301 | const struct hip_puzzle *, |
302 | - uint64_t); |
303 | + uint8_t *const); |
304 | |
305 | int hip_build_param_challenge_response(struct hip_common *, |
306 | const struct hip_challenge_request *, |
307 | |
308 | === modified file 'lib/core/protodefs.h' |
309 | --- lib/core/protodefs.h 2011-02-04 14:44:37 +0000 |
310 | +++ lib/core/protodefs.h 2011-04-13 08:50:43 +0000 |
311 | @@ -737,13 +737,17 @@ |
312 | uint64_t generation; |
313 | } __attribute__ ((packed)); |
314 | |
315 | + |
316 | +/* puzzle and solutions are defined to have a length of 8 bytes */ |
317 | +#define PUZZLE_LENGTH 8 |
318 | + |
319 | struct hip_puzzle { |
320 | hip_tlv type; |
321 | hip_tlv_len length; |
322 | uint8_t K; |
323 | uint8_t lifetime; |
324 | uint8_t opaque[HIP_PUZZLE_OPAQUE_LEN]; |
325 | - uint64_t I; |
326 | + uint8_t I[PUZZLE_LENGTH]; |
327 | } __attribute__ ((packed)); |
328 | |
329 | struct hip_solution { |
330 | @@ -752,8 +756,8 @@ |
331 | uint8_t K; |
332 | uint8_t reserved; |
333 | uint8_t opaque[HIP_PUZZLE_OPAQUE_LEN]; |
334 | - uint64_t I; |
335 | - uint64_t J; |
336 | + uint8_t I[PUZZLE_LENGTH]; |
337 | + uint8_t J[PUZZLE_LENGTH]; |
338 | } __attribute__ ((packed)); |
339 | |
340 | |
341 | |
342 | === modified file 'lib/core/solve.c' |
343 | --- lib/core/solve.c 2011-01-24 10:21:17 +0000 |
344 | +++ lib/core/solve.c 2011-04-13 08:50:43 +0000 |
345 | @@ -28,11 +28,14 @@ |
346 | * @brief HIP computation puzzle solving algorithms |
347 | * |
348 | * @author Miika Komu <miika@iki.fi> |
349 | + * @author Rene Hummen |
350 | */ |
351 | |
352 | #include <errno.h> |
353 | #include <stdint.h> |
354 | #include <string.h> |
355 | +#include <strings.h> |
356 | +#include <openssl/rand.h> |
357 | |
358 | #include "config.h" |
359 | #include "builder.h" |
360 | @@ -43,108 +46,183 @@ |
361 | #include "protodefs.h" |
362 | #include "solve.h" |
363 | |
364 | +/** This data type represents the ordered input for the hash function used to |
365 | + * solve a given puzzle challenge as defined in RFC 5201 - Appendix A */ |
366 | +struct puzzle_hash_input { |
367 | + uint8_t puzzle[PUZZLE_LENGTH]; |
368 | + hip_hit_t initiator_hit; |
369 | + hip_hit_t responder_hit; |
370 | + uint8_t solution[PUZZLE_LENGTH]; |
371 | +} __attribute__ ((packed)); |
372 | + |
373 | +// max. 2^max_puzzle_difficulty tries to solve a puzzle |
374 | +#define MAX_PUZZLE_SOLUTION_TRIES (1ULL << MAX_PUZZLE_DIFFICULTY) |
375 | + |
376 | /** |
377 | - * solve a computational puzzle for HIP |
378 | - * |
379 | - * @param puzzle_or_solution Either a pointer to hip_puzzle or hip_solution structure |
380 | - * @param hdr The incoming R1/I2 packet header. |
381 | - * @param mode Either HIP_VERIFY_PUZZLE of HIP_SOLVE_PUZZLE |
382 | - * |
383 | - * @note The K and I is read from the @c puzzle_or_solution. |
384 | - * @note Regarding to return value of zero, I don't see why 0 couldn't solve the |
385 | - * puzzle too, but since the odds are 1/2^64 to try 0, I don't see the point |
386 | - * in improving this now. |
387 | - * @return The J that solves the puzzle is returned, or 0 to indicate an error. |
388 | + * Computes a single iteration for a computational puzzle |
389 | + * |
390 | + * @param compute_puzzle puzzle to be solved or verified |
391 | + * @param sha_digest buffer for hash digest |
392 | + * @param difficulty difficulty of the puzzle (number of leading zeros) |
393 | + * @return 0 when hash has >= @a difficulty least significant bits as zeros, 1 |
394 | + * when hash has < @a difficulty least significant bits as zeros, |
395 | + * -1 in case of an error |
396 | */ |
397 | -uint64_t hip_solve_puzzle(const void *puzzle_or_solution, |
398 | - const struct hip_common *hdr, |
399 | - int mode) |
400 | +static int hip_single_puzzle_computation(const struct puzzle_hash_input *const puzzle_input, |
401 | + const uint8_t difficulty) |
402 | { |
403 | - uint64_t mask = 0; |
404 | - uint64_t randval = 0; |
405 | - uint64_t maxtries = 0; |
406 | - uint64_t digest = 0; |
407 | - uint8_t cookie[48]; |
408 | - int err = 0; |
409 | - const union { |
410 | - struct hip_puzzle pz; |
411 | - struct hip_solution sl; |
412 | - } *u; |
413 | - |
414 | - HIP_HEXDUMP("puzzle", puzzle_or_solution, |
415 | - (mode == HIP_VERIFY_PUZZLE ? sizeof(struct hip_solution) : |
416 | - sizeof(struct hip_puzzle))); |
417 | - |
418 | - /* pre-create cookie */ |
419 | - u = puzzle_or_solution; |
420 | - |
421 | - HIP_IFEL(u->pz.K > HIP_PUZZLE_MAX_K, 0, |
422 | - "Cookie K %u is higher than we are willing to calculate" |
423 | - " (current max K=%d)\n", u->pz.K, HIP_PUZZLE_MAX_K); |
424 | - |
425 | - mask = hton64((1ULL << u->pz.K) - 1); |
426 | - memcpy(cookie, &u->pz.I, sizeof(uint64_t)); |
427 | - |
428 | - HIP_DEBUG("(u->pz.I: 0x%llx\n", u->pz.I); |
429 | - |
430 | - if (mode == HIP_VERIFY_PUZZLE) { |
431 | - ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hits); |
432 | - ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hitr); |
433 | - randval = u->sl.J; |
434 | - maxtries = 1; |
435 | - } else if (mode == HIP_SOLVE_PUZZLE) { |
436 | - ipv6_addr_copy((hip_hit_t *) (cookie + 8), &hdr->hitr); |
437 | - ipv6_addr_copy((hip_hit_t *) (cookie + 24), &hdr->hits); |
438 | - maxtries = 1ULL << (u->pz.K + 3); |
439 | - get_random_bytes(&randval, sizeof(uint64_t)); |
440 | + unsigned char sha_digest[SHA_DIGEST_LENGTH]; |
441 | + uint32_t truncated_digest = 0; |
442 | + int err = -1; |
443 | + |
444 | + /* any puzzle solution is acceptable for difficulty 0 */ |
445 | + if (difficulty == 0) { |
446 | + return 0; |
447 | + } |
448 | + |
449 | + HIP_IFEL(difficulty > MAX_PUZZLE_DIFFICULTY, |
450 | + -1, "difficulty exceeds max. configured difficulty\n"); |
451 | + |
452 | + HIP_IFEL(hip_build_digest(HIP_DIGEST_SHA1, |
453 | + puzzle_input, |
454 | + sizeof(struct puzzle_hash_input), |
455 | + sha_digest), |
456 | + -1, "failed to compute hash digest\n"); |
457 | + |
458 | + /* In reference to RFC 5201, we need to interpret the hash digest as an |
459 | + * integer in network byte-order. We are interested in least significant |
460 | + * bits here. */ |
461 | + truncated_digest = *(uint32_t *) &sha_digest[SHA_DIGEST_LENGTH - sizeof(truncated_digest)]; |
462 | + |
463 | + /* Make sure to interpret the solution equally across platforms |
464 | + * (i.e., network byte-order), when calculating the puzzle solution. |
465 | + * |
466 | + * The problem is that ffs() interprets its input not as a byte array |
467 | + * but as an integer with an encoding that depends on the host byte order. |
468 | + * htonl() ensures that ffs() performs the check in network byte order |
469 | + * independent from the actual host byte order. */ |
470 | + truncated_digest = htonl(truncated_digest); |
471 | + |
472 | + /* check if position of first least significant 1-bit is higher than |
473 | + * difficulty */ |
474 | + if (ffs(truncated_digest) > difficulty) { |
475 | + err = 0; |
476 | } else { |
477 | - HIP_OUT_ERR(0, "Unknown mode: %d\n", mode); |
478 | - } |
479 | - |
480 | - HIP_DEBUG("K=%u, maxtries (with k+2)=%llu\n", u->pz.K, maxtries); |
481 | - /* while loops should work even if the maxtries is unsigned |
482 | - * if maxtries = 1 ---> while(1 > 0) [maxtries == 0 now]... |
483 | - * the next round while (0 > 0) [maxtries > 0 now] |
484 | - */ |
485 | - while (maxtries-- > 0) { |
486 | - uint8_t sha_digest[HIP_AH_SHA_LEN]; |
487 | - |
488 | - /* must be 8 */ |
489 | - memcpy(cookie + 40, (uint8_t *) &randval, sizeof(uint64_t)); |
490 | - |
491 | - hip_build_digest(HIP_DIGEST_SHA1, cookie, 48, sha_digest); |
492 | - |
493 | - /* copy the last 8 bytes for checking */ |
494 | - memcpy(&digest, sha_digest + 12, sizeof(uint64_t)); |
495 | - |
496 | - /* now, in order to be able to do correctly the bitwise |
497 | - * AND-operation we have to remember that little endian |
498 | - * processors will interpret the digest and mask reversely. |
499 | - * digest is the last 64 bits of the sha1-digest.. how that is |
500 | - * ordered in processors registers etc.. does not matter to us. |
501 | - * If the last 64 bits of the sha1-digest is |
502 | - * 0x12345678DEADBEEF, whether we have 0xEFBEADDE78563412 |
503 | - * doesn't matter because the mask matters... if the mask is |
504 | - * 0x000000000000FFFF (or in other endianness |
505 | - * 0xFFFF000000000000). Either ways... the result is |
506 | - * 0x000000000000BEEF or 0xEFBE000000000000, which the cpu |
507 | - * interprets as 0xBEEF. The mask is converted to network byte |
508 | - * order (above). |
509 | - */ |
510 | - if ((digest & mask) == 0) { |
511 | - return randval; |
512 | + err = 1; |
513 | + } |
514 | + |
515 | +out_err: |
516 | + return err; |
517 | +} |
518 | + |
519 | +/** |
520 | + * Solve a computational puzzle for HIP |
521 | + * |
522 | + * @param puzzle puzzle to be solved |
523 | + * @param difficulty difficulty of the puzzle |
524 | + * @param initiator_hit initiator HIT of the message exchange |
525 | + * @param responder_hit responder HIT of the message exchange |
526 | + * @param[out] solution computed puzzle solution |
527 | + * @return 0 when solution was found, 1 in case no solution was found after |
528 | + * ::MAX_PUZZLE_SOLUTION_TRIES, -1 in case of an error |
529 | + */ |
530 | +int hip_solve_puzzle(const uint8_t puzzle[PUZZLE_LENGTH], |
531 | + const uint8_t difficulty, |
532 | + const hip_hit_t initiator_hit, |
533 | + const hip_hit_t responder_hit, |
534 | + uint8_t solution[PUZZLE_LENGTH]) |
535 | +{ |
536 | + struct puzzle_hash_input compute_puzzle; |
537 | + int err = -1; |
538 | + unsigned long long i = 0; |
539 | + |
540 | + /* solution must reference allocated memory here */ |
541 | + HIP_ASSERT(solution); |
542 | + |
543 | + HIP_IFEL(difficulty > MAX_PUZZLE_DIFFICULTY, -1, |
544 | + "Cookie (K = %i) is higher than we are willing to calculate" |
545 | + " (current max K = %i)\n", difficulty, MAX_PUZZLE_DIFFICULTY); |
546 | + |
547 | + /* solution is correct iff: |
548 | + * 0 == V := Ltrunc( RHASH( I2.I | I2.hit_i | I2.hit_r | I2.J ), K ) |
549 | + * (RFC 5201 - Appendix A) */ |
550 | + memcpy(compute_puzzle.puzzle, puzzle, PUZZLE_LENGTH); |
551 | + compute_puzzle.initiator_hit = initiator_hit; |
552 | + compute_puzzle.responder_hit = responder_hit; |
553 | + RAND_bytes(compute_puzzle.solution, PUZZLE_LENGTH); |
554 | + |
555 | + // any puzzle solution is acceptable for difficulty 0 |
556 | + if (difficulty == 0) { |
557 | + return 0; |
558 | + } |
559 | + |
560 | + /* If max_puzzle_difficulty >= 64, MAX_PUZZLE_SOLUTION_TRIES will be 0. |
561 | + * Hence, no solution will be found for these cases. */ |
562 | + HIP_ASSERT(MAX_PUZZLE_DIFFICULTY < sizeof(unsigned long long) * 8); |
563 | + |
564 | + for (i = 0; i < MAX_PUZZLE_SOLUTION_TRIES; i++) { |
565 | + // now do the computations |
566 | + err = hip_single_puzzle_computation(&compute_puzzle, |
567 | + difficulty); |
568 | + if (err == 0) { |
569 | + memcpy(solution, compute_puzzle.solution, PUZZLE_LENGTH); |
570 | + break; |
571 | + } else if (err > 0) { |
572 | + // increase random value by one and try again |
573 | + (*(uint64_t *) compute_puzzle.solution)++; |
574 | + } else { |
575 | + memset(solution, 0, PUZZLE_LENGTH); |
576 | + break; |
577 | } |
578 | - |
579 | - /* It seems like the puzzle was not correctly solved */ |
580 | - HIP_IFEL(mode == HIP_VERIFY_PUZZLE, 0, "Puzzle incorrect\n"); |
581 | - randval++; |
582 | } |
583 | |
584 | - HIP_ERROR("Could not solve the puzzle, no solution found\n"); |
585 | out_err: |
586 | + if (i == MAX_PUZZLE_SOLUTION_TRIES) { |
587 | + HIP_ERROR("Could not solve the puzzle, no solution found\n"); |
588 | + } |
589 | + |
590 | return err; |
591 | } |
592 | |
593 | +/** |
594 | + * Verify a computational puzzle for HIP |
595 | + * |
596 | + * @param puzzle puzzle to be verified |
597 | + * @param solution puzzle solution to be verified |
598 | + * @param difficulty difficulty of the puzzle |
599 | + * @param initiator_hit initiator HIT of the message exchange |
600 | + * @param responder_hit responder HIT of the message exchange |
601 | + * @return 0 when solution is correct, -1 otherwise |
602 | + */ |
603 | +int hip_verify_puzzle_solution(const uint8_t puzzle[PUZZLE_LENGTH], |
604 | + const uint8_t solution[PUZZLE_LENGTH], |
605 | + const uint8_t difficulty, |
606 | + const hip_hit_t initiator_hit, |
607 | + const hip_hit_t responder_hit) |
608 | +{ |
609 | + struct puzzle_hash_input compute_puzzle; |
610 | + |
611 | + // any puzzle solution is acceptable for difficulty 0 |
612 | + if (difficulty == 0) { |
613 | + return 0; |
614 | + } |
615 | + |
616 | + /* solution is correct iff: |
617 | + * 0 == V := Ltrunc( RHASH( I2.I | I2.hit_i | I2.hit_r | I2.J ), K ) |
618 | + * (RFC 5201 - Appendix A) */ |
619 | + memcpy(compute_puzzle.puzzle, puzzle, PUZZLE_LENGTH); |
620 | + ipv6_addr_copy(&compute_puzzle.initiator_hit, &initiator_hit); |
621 | + ipv6_addr_copy(&compute_puzzle.responder_hit, &responder_hit); |
622 | + memcpy(compute_puzzle.solution, solution, PUZZLE_LENGTH); |
623 | + |
624 | + if (hip_single_puzzle_computation(&compute_puzzle, difficulty)) { |
625 | + HIP_ERROR("failed to verify puzzle solution\n"); |
626 | + return -1; |
627 | + } |
628 | + |
629 | + return 0; |
630 | +} |
631 | + |
632 | #ifdef CONFIG_HIP_MIDAUTH |
633 | /** |
634 | * solve a midauth puzzle which is essentially a normal HIP cookie |
635 | |
636 | === modified file 'lib/core/solve.h' |
637 | --- lib/core/solve.h 2010-10-15 15:29:14 +0000 |
638 | +++ lib/core/solve.h 2011-04-13 08:50:43 +0000 |
639 | @@ -30,10 +30,23 @@ |
640 | |
641 | #include "protodefs.h" |
642 | |
643 | -#define HIP_PUZZLE_MAX_K 28 |
644 | - |
645 | -uint64_t hip_solve_puzzle(const void *puzzle, |
646 | - const struct hip_common *hdr, int mode); |
647 | -int hip_solve_puzzle_m(struct hip_common *out, struct hip_common *in); |
648 | +/* ensure that the max puzzle difficulty (here 28) is limited by sizeof(int), |
649 | + * as ffs() is working on int type. |
650 | + * |
651 | + * NOTE: ffsll() allowing for sizeof(long long int) is currently not available |
652 | + * on OpenWRT. */ |
653 | +static const uint8_t MAX_PUZZLE_DIFFICULTY = sizeof(int) * 8 >= 28 ? 28 : sizeof(int) * 8; |
654 | + |
655 | +int hip_solve_puzzle(const uint8_t puzzle[PUZZLE_LENGTH], |
656 | + const uint8_t difficulty, |
657 | + const hip_hit_t initiator_hit, |
658 | + const hip_hit_t responder_hit, |
659 | + uint8_t solution[PUZZLE_LENGTH]); |
660 | + |
661 | +int hip_verify_puzzle_solution(const uint8_t puzzle[PUZZLE_LENGTH], |
662 | + const uint8_t solution[PUZZLE_LENGTH], |
663 | + const uint8_t difficulty, |
664 | + const hip_hit_t initiator_hit, |
665 | + const hip_hit_t responder_hit); |
666 | |
667 | #endif /* HIP_LIB_CORE_SOLVE_H */ |
668 | |
669 | === modified file 'lib/core/state.h' |
670 | --- lib/core/state.h 2011-02-06 09:03:39 +0000 |
671 | +++ lib/core/state.h 2011-04-13 08:50:43 +0000 |
672 | @@ -294,13 +294,13 @@ |
673 | /** A function pointer to a function that verifies peer's host identity. */ |
674 | int (*verify)(void *, struct hip_common *); |
675 | /** For retransmission. */ |
676 | - uint64_t puzzle_solution; |
677 | + uint8_t puzzle_solution[PUZZLE_LENGTH]; |
678 | /** LOCATOR parameter. Just tmp save if sent in R1 no @c esp_info so |
679 | * keeping it here 'till the hip_update_locator_parameter can be done. |
680 | * @todo Remove this kludge. */ |
681 | struct hip_locator *locator; |
682 | /** For retransmission. */ |
683 | - uint64_t puzzle_i; |
684 | + uint8_t puzzle_i[PUZZLE_LENGTH]; |
685 | /** Used for UPDATE and CLOSE. When we sent multiple identical UPDATE |
686 | * packets between different address combinations, we don't modify |
687 | * the opaque data. */ |
688 | |
689 | === modified file 'lib/tool/pk.c' |
690 | --- lib/tool/pk.c 2011-04-04 13:59:21 +0000 |
691 | +++ lib/tool/pk.c 2011-04-13 08:50:43 +0000 |
692 | @@ -131,8 +131,8 @@ |
693 | uint8_t sha1_digest[HIP_AH_SHA_LEN]; |
694 | struct in6_addr tmpaddr; |
695 | struct hip_puzzle *pz = NULL; |
696 | - uint8_t opaque[3]; |
697 | - uint64_t randi = 0; |
698 | + uint8_t opaque[HIP_PUZZLE_OPAQUE_LEN]; |
699 | + uint8_t rand_i[PUZZLE_LENGTH]; |
700 | |
701 | ipv6_addr_copy(&tmpaddr, &msg->hitr); /* so update is handled, too */ |
702 | |
703 | @@ -146,11 +146,13 @@ |
704 | |
705 | HIP_IFEL(!(pz = hip_get_param_readwrite(msg, HIP_PARAM_PUZZLE)), |
706 | -ENOENT, "Illegal R1 packet (puzzle missing)\n"); |
707 | - memcpy(opaque, pz->opaque, sizeof(pz->opaque)); |
708 | - randi = pz->I; |
709 | |
710 | - memset(pz->opaque, 0, sizeof(pz->opaque)); |
711 | - pz->I = 0; |
712 | + /* temporarily store original puzzle values */ |
713 | + memcpy(opaque, pz->opaque, HIP_PUZZLE_OPAQUE_LEN); |
714 | + memcpy(rand_i, pz->I, PUZZLE_LENGTH); |
715 | + /* R1 signature is computed over zero values */ |
716 | + memset(pz->opaque, 0, HIP_PUZZLE_OPAQUE_LEN); |
717 | + memset(pz->I, 0, PUZZLE_LENGTH); |
718 | } else { |
719 | HIP_IFEL(!(sig = hip_get_param_readwrite(msg, HIP_PARAM_HIP_SIGNATURE)), |
720 | -ENOENT, "Could not find signature\n"); |
721 | @@ -182,8 +184,8 @@ |
722 | #endif |
723 | |
724 | if (hip_get_msg_type(msg) == HIP_R1) { |
725 | - memcpy(pz->opaque, opaque, sizeof(pz->opaque)); |
726 | - pz->I = randi; |
727 | + memcpy(pz->opaque, opaque, HIP_PUZZLE_OPAQUE_LEN); |
728 | + memcpy(pz->I, rand_i, PUZZLE_LENGTH); |
729 | } |
730 | |
731 | ipv6_addr_copy(&msg->hitr, &tmpaddr); |
732 | |
733 | === modified file 'test/check_lib_core.c' |
734 | --- test/check_lib_core.c 2011-02-18 14:39:38 +0000 |
735 | +++ test/check_lib_core.c 2011-04-13 08:50:43 +0000 |
736 | @@ -38,6 +38,7 @@ |
737 | { |
738 | int number_failed; |
739 | SRunner *sr = srunner_create(lib_core_hit()); |
740 | + srunner_add_suite(sr, lib_core_solve()); |
741 | srunner_add_suite(sr, lib_core_straddr()); |
742 | |
743 | srunner_run_all(sr, CK_NORMAL); |
744 | |
745 | === added file 'test/lib/core/solve.c' |
746 | --- test/lib/core/solve.c 1970-01-01 00:00:00 +0000 |
747 | +++ test/lib/core/solve.c 2011-04-13 08:50:43 +0000 |
748 | @@ -0,0 +1,200 @@ |
749 | +/* |
750 | + * Copyright (c) 2010 Aalto University and RWTH Aachen University. |
751 | + * |
752 | + * Permission is hereby granted, free of charge, to any person |
753 | + * obtaining a copy of this software and associated documentation |
754 | + * files (the "Software"), to deal in the Software without |
755 | + * restriction, including without limitation the rights to use, |
756 | + * copy, modify, merge, publish, distribute, sublicense, and/or sell |
757 | + * copies of the Software, and to permit persons to whom the |
758 | + * Software is furnished to do so, subject to the following |
759 | + * conditions: |
760 | + * |
761 | + * The above copyright notice and this permission notice shall be |
762 | + * included in all copies or substantial portions of the Software. |
763 | + * |
764 | + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
765 | + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
766 | + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
767 | + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
768 | + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
769 | + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
770 | + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
771 | + * OTHER DEALINGS IN THE SOFTWARE. |
772 | + */ |
773 | + |
774 | +/** |
775 | + * @file |
776 | + * @author Rene Hummen |
777 | + */ |
778 | + |
779 | +#include <check.h> |
780 | +#include <stdint.h> |
781 | +#include <stdio.h> |
782 | +#include <arpa/inet.h> |
783 | +#include <netinet/in.h> |
784 | +#include <openssl/rand.h> |
785 | + |
786 | +#include "lib/core/solve.h" |
787 | +#include "config.h" |
788 | +#include "test_suites.h" |
789 | + |
790 | +#ifdef HAVE_TCASE_ADD_EXIT_TEST |
791 | +START_TEST(test_hip_solve_puzzle_NULL_solution) |
792 | +{ |
793 | + uint8_t puzzle[PUZZLE_LENGTH] = { 0 }; |
794 | + uint8_t difficulty = 0; |
795 | + hip_hit_t initiator; |
796 | + hip_hit_t responder; |
797 | + |
798 | + RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t)); |
799 | + |
800 | + fail_unless(hip_solve_puzzle(puzzle, |
801 | + difficulty, |
802 | + initiator, |
803 | + responder, |
804 | + NULL) == -1, |
805 | + NULL); |
806 | +} |
807 | +END_TEST |
808 | +#endif /* HAVE_TCASE_ADD_EXIT_TEST */ |
809 | + |
810 | +START_TEST(test_hip_solve_puzzle_0_K) |
811 | +{ |
812 | + uint8_t puzzle[PUZZLE_LENGTH] = { 0 }; |
813 | + uint8_t difficulty = 0; |
814 | + hip_hit_t initiator; |
815 | + hip_hit_t responder; |
816 | + uint8_t solution[PUZZLE_LENGTH] = { 0 }; |
817 | + |
818 | + RAND_bytes((unsigned char *)&puzzle, sizeof(PUZZLE_LENGTH)); |
819 | + |
820 | + fail_unless(hip_solve_puzzle(puzzle, |
821 | + difficulty, |
822 | + initiator, |
823 | + responder, |
824 | + solution) == 0, |
825 | + NULL); |
826 | +} |
827 | +END_TEST |
828 | + |
829 | +START_TEST(test_hip_solve_puzzle_5_K) |
830 | +{ |
831 | + uint8_t puzzle[PUZZLE_LENGTH] = { 0 }; |
832 | + uint8_t difficulty = 5; |
833 | + hip_hit_t initiator; |
834 | + hip_hit_t responder; |
835 | + uint8_t solution[PUZZLE_LENGTH] = { 0 }; |
836 | + |
837 | + RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t)); |
838 | + |
839 | + fail_unless(hip_solve_puzzle(puzzle, |
840 | + difficulty, |
841 | + initiator, |
842 | + responder, |
843 | + solution) == 0, |
844 | + NULL); |
845 | +} |
846 | +END_TEST |
847 | + |
848 | +START_TEST(test_hip_solve_puzzle_exceeding_K) |
849 | +{ |
850 | + uint8_t puzzle[PUZZLE_LENGTH] = { 0 }; |
851 | + uint8_t difficulty = MAX_PUZZLE_DIFFICULTY + 1; |
852 | + hip_hit_t initiator; |
853 | + hip_hit_t responder; |
854 | + uint8_t solution[PUZZLE_LENGTH] = { 0 }; |
855 | + |
856 | + RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t)); |
857 | + |
858 | + fail_unless(hip_solve_puzzle(puzzle, |
859 | + difficulty, |
860 | + initiator, |
861 | + responder, |
862 | + solution) == -1, |
863 | + NULL); |
864 | +} |
865 | +END_TEST |
866 | + |
867 | +START_TEST(test_hip_verify_puzzle_solution_invalid) |
868 | +{ |
869 | + uint8_t puzzle[PUZZLE_LENGTH] = { 1 }; |
870 | + uint8_t difficulty = 20; |
871 | + hip_hit_t initiator; |
872 | + hip_hit_t responder; |
873 | + uint8_t solution[PUZZLE_LENGTH] = { 0 }; |
874 | + |
875 | + fail_unless(hip_verify_puzzle_solution(puzzle, |
876 | + solution, |
877 | + difficulty, |
878 | + initiator, |
879 | + responder) == -1, |
880 | + NULL); |
881 | +} |
882 | +END_TEST |
883 | + |
884 | +START_TEST(test_hip_verify_puzzle_solution_against_ourselves) |
885 | +{ |
886 | + uint8_t puzzle[PUZZLE_LENGTH] = { 0 }; |
887 | + uint8_t difficulty = 8; |
888 | + hip_hit_t initiator; |
889 | + hip_hit_t responder; |
890 | + uint8_t solution[PUZZLE_LENGTH] = { 0 }; |
891 | + |
892 | + RAND_bytes((unsigned char *)&puzzle, sizeof(uint64_t)); |
893 | + |
894 | + fail_unless(hip_solve_puzzle(puzzle, |
895 | + difficulty, |
896 | + initiator, |
897 | + responder, |
898 | + solution) == 0, |
899 | + NULL); |
900 | + |
901 | + fail_unless(hip_verify_puzzle_solution(puzzle, |
902 | + solution, |
903 | + difficulty, |
904 | + initiator, |
905 | + responder) == 0, |
906 | + NULL); |
907 | +} |
908 | +END_TEST |
909 | + |
910 | +START_TEST(test_hip_test_hip_verify_puzzle_solution_against_real_solution) |
911 | +{ |
912 | + char solution_dump[] = "\x01\x41\x00\x14\x05\x00\x48\x49\x0b\xbd\xd0\xb4" |
913 | + "\x92\xbb\xea\xe3\xa9\x71\x97\xdf\x12\xe1\x2c\x9f"; |
914 | + struct hip_solution *solution = (struct hip_solution *) solution_dump; |
915 | + const char *initiator_hit_str = "2001:1b:d8b0:77f0:c617:7170:ded7:f320"; |
916 | + const char *responder_hit_str = "2001:17:5df8:c426:98e5:5fa2:286d:2847"; |
917 | + struct in6_addr initiator_hit; |
918 | + struct in6_addr responder_hit; |
919 | + |
920 | + inet_pton(AF_INET6, initiator_hit_str, &initiator_hit); |
921 | + inet_pton(AF_INET6, responder_hit_str, &responder_hit); |
922 | + |
923 | + fail_unless(hip_verify_puzzle_solution(solution->I, |
924 | + solution->J, |
925 | + solution->K, |
926 | + initiator_hit, |
927 | + responder_hit) == 0); |
928 | +} |
929 | +END_TEST |
930 | + |
931 | +Suite *lib_core_solve(void) |
932 | +{ |
933 | + Suite *s = suite_create("lib/core/solve"); |
934 | + |
935 | + TCase *tc_core = tcase_create("Core"); |
936 | +#ifdef HAVE_TCASE_ADD_EXIT_TEST |
937 | + tcase_add_exit_test(tc_core, test_hip_solve_puzzle_NULL_solution, 1); |
938 | +#endif /* HAVE_TCASE_ADD_EXIT_TEST */ |
939 | + tcase_add_test(tc_core, test_hip_solve_puzzle_0_K); |
940 | + tcase_add_test(tc_core, test_hip_solve_puzzle_5_K); |
941 | + tcase_add_test(tc_core, test_hip_solve_puzzle_exceeding_K); |
942 | + tcase_add_test(tc_core, test_hip_verify_puzzle_solution_invalid); |
943 | + tcase_add_test(tc_core, test_hip_verify_puzzle_solution_against_ourselves); |
944 | + tcase_add_test(tc_core, test_hip_test_hip_verify_puzzle_solution_against_real_solution); |
945 | + suite_add_tcase(s, tc_core); |
946 | + |
947 | + return s; |
948 | +} |
949 | |
950 | === modified file 'test/lib/core/test_suites.h' |
951 | --- test/lib/core/test_suites.h 2011-02-18 14:39:38 +0000 |
952 | +++ test/lib/core/test_suites.h 2011-04-13 08:50:43 +0000 |
953 | @@ -29,6 +29,7 @@ |
954 | #include <check.h> |
955 | |
956 | Suite *lib_core_hit(void); |
957 | +Suite *lib_core_solve(void); |
958 | Suite *lib_core_straddr(void); |
959 | |
960 | #endif /* HIP_TEST_LIB_CORE_TEST_SUITES_H */ |
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, SHA_DIGEST_ LENGTH] , "puzzle" , puzzle_or_solution, "(u->pz. I: 0x%llx\n", u->pz.I); copy((hip_ hit_t *) (cookie + 8), &hdr->hits); copy((hip_ hit_t *) (cookie + 24), &hdr->hitr); copy((hip_ hit_t *) (cookie + 8), &hdr->hitr); copy((hip_ hit_t *) (cookie + 24), &hdr->hits); bytes(& randval, sizeof(uint64_t)); difficulty, hip_build_ digest( HIP_DIGEST_ SHA1,
> + unsigned char sha_digest[
> + 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(
> - (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(
> -
> - if (mode == HIP_VERIFY_PUZZLE) {
> - ipv6_addr_
> - ipv6_addr_
> - randval = u->sl.J;
> - maxtries = 1;
> - } else if (mode == HIP_SOLVE_PUZZLE) {
> - ipv6_addr_
> - ipv6_addr_
> - maxtries = 1ULL << (u->pz.K + 3);
> - get_random_
> + uint32_t truncated_digest = 0;
> + int err = -1;
> +
> + HIP_IFEL(difficulty > max_puzzle_
> + 1, "difficulty exceeds max. configured difficulty\n");
> +
> + HIP_IFEL(
> + 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 */ SHA_DIGEST_ LENGTH - sizeof(uint32_t)];
> + truncated_digest = *(uint32_t *) &sha_digest[
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...