[hipl-commit] [trunk] Rev 3860: Splitting misc.c continued (bug id 1139). Added a separate source and header file for puzzle solving.

  • From: Miika Komu <miika@xxxxxx>
  • To: hipl-commit@xxxxxxxxxxxxx
  • Date: Tue, 9 Mar 2010 10:57:49 +0200

Committer: Miika Komu <miika@xxxxxx>
Date: Tue Mar 09 10:57:46 2010 +0200
Revision: 3860
Revision-id: miika@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Branch nick: trunk

Log:
  Splitting misc.c continued (bug id 1139). Added a separate source and header 
file for puzzle solving.

Modified:
  A  lib/core/solve.c
  A  lib/core/solve.h
  M  Makefile.am
  M  firewall/midauth.c
  M  hipd/cookie.c
  M  hipd/cookie.h
  M  hipd/hadb.c
  M  hipd/icookie.c
  M  hipd/input.c
  M  hipd/update.c
  M  lib/core/misc.c
  M  lib/core/misc.h
  M  test/cookietest.c

=== modified file 'Makefile.am'
--- Makefile.am 2010-03-08 22:21:34 +0000
+++ Makefile.am 2010-03-09 08:57:46 +0000
@@ -256,6 +256,7 @@
                                  lib/core/hashchain.c \
                                  lib/core/hostid.c \
                                  lib/core/hip_udp.c \
+                                 lib/core/solve.c \
                                  lib/core/sqlitedbapi.c \
                                  lib/core/hashchain_store.c \
                                  lib/core/hip_statistics.c \

=== modified file 'firewall/midauth.c'
--- firewall/midauth.c  2010-02-18 12:26:08 +0000
+++ firewall/midauth.c  2010-03-09 08:57:46 +0000
@@ -30,6 +30,7 @@
 #include "midauth.h"
 #include "pisa.h"
 #include "lib/core/builder.h"
+#include "lib/core/solve.h"
 
 #ifdef CONFIG_HIP_PERFORMANCE
 #include "lib/performance/performance.h"

=== modified file 'hipd/cookie.c'
--- hipd/cookie.c       2010-03-05 09:10:50 +0000
+++ hipd/cookie.c       2010-03-09 08:57:46 +0000
@@ -17,6 +17,7 @@
 #endif /* HAVE_CONFIG_H */
 
 #include "cookie.h"
+#include "lib/core/solve.h"
 
 #define HIP_PUZZLE_MAX_LIFETIME 60 /* in seconds */
 #define HIP_DEFAULT_COOKIE_K    1ULL /* a difficulty of i leads to approx. 
2^(i-1) hash computations during BEX */

=== modified file 'hipd/cookie.h'
--- hipd/cookie.h       2010-02-17 17:38:08 +0000
+++ hipd/cookie.h       2010-03-09 08:57:46 +0000
@@ -16,7 +16,6 @@
 };
 
 #define HIP_R1TABLESIZE         3 /* precreate only this many R1s */
-#define HIP_PUZZLE_MAX_K        28
 struct hip_common *hip_get_r1(struct in6_addr *ip_i,
                               struct in6_addr *ip_r,
                               struct in6_addr *src_hit,

=== modified file 'hipd/hadb.c'
--- hipd/hadb.c 2010-03-08 22:21:34 +0000
+++ hipd/hadb.c 2010-03-09 08:57:46 +0000
@@ -14,6 +14,7 @@
 #include "lib/core/hostsfiles.h"
 #include "lib/core/hostid.h"
 #include "lib/core/hip_udp.h"
+#include "lib/core/solve.h"
 
 #define HIP_HADB_SIZE 53
 #define HIP_MAX_HAS 100

=== modified file 'hipd/icookie.c'
--- hipd/icookie.c      2010-03-05 08:47:53 +0000
+++ hipd/icookie.c      2010-03-09 08:57:46 +0000
@@ -14,6 +14,7 @@
 
 #ifdef CONFIG_HIP_ICOOKIE
 #include "icookie.h"
+#include "lib/core/solve.h"
 
 /* We need maintain a separate table for the K values of cookies because
  * otherwise they are just overwritten when R1s are recreated periodically. */

=== modified file 'hipd/input.c'
--- hipd/input.c        2010-03-08 22:21:34 +0000
+++ hipd/input.c        2010-03-09 08:57:46 +0000
@@ -29,6 +29,7 @@
 #include "lib/core/crypto.h"
 #include "lib/core/builder.h"
 #include "lib/core/hip_udp.h"
+#include "lib/core/solve.h"
 #include "dh.h"
 #include "lib/core/misc.h"
 #include "hidb.h"

=== modified file 'hipd/update.c'
--- hipd/update.c       2010-03-08 22:21:34 +0000
+++ hipd/update.c       2010-03-09 08:57:46 +0000
@@ -21,6 +21,7 @@
 
 #include "lib/core/protodefs.h"
 #include "lib/core/hip_udp.h"
+#include "lib/core/solve.h"
 #include "netdev.h"
 #include "lib/core/builder.h"
 #include "update_legacy.h"

=== modified file 'lib/core/misc.c'
--- lib/core/misc.c     2010-03-08 22:21:34 +0000
+++ lib/core/misc.c     2010-03-09 08:57:46 +0000
@@ -774,170 +774,6 @@
 
 
 
-/**
- * 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.
- */
-uint64_t hip_solve_puzzle(void *puzzle_or_solution,
-                          struct hip_common *hdr,
-                          int mode)
-{
-    uint64_t mask     = 0;
-    uint64_t randval  = 0;
-    uint64_t maxtries = 0;
-    uint64_t digest   = 0;
-    uint8_t cookie[48];
-    int err           = 0;
-    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)));
-
-    _HIP_DEBUG("\n");
-    /* pre-create cookie */
-    u = puzzle_or_solution;
-
-    _HIP_DEBUG("current hip_cookie_max_k_r1=%d\n", max_k);
-    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, (uint8_t *) &(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 = ntoh64(u->sl.J);
-        randval  = u->sl.J;
-        _HIP_DEBUG("u->sl.J: 0x%llx\n", randval);
-        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(u_int64_t));
-    } else {
-        HIP_IFEL(1, 0, "Unknown mode: %d\n", mode);
-    }
-
-    HIP_DEBUG("K=%u, maxtries (with k+2)=%llu\n", u->pz.K, maxtries);
-    /* while loops should work even if the maxtries is unsigned
-     * if maxtries = 1 ---> while(1 > 0) [maxtries == 0 now]...
-     * the next round while (0 > 0) [maxtries > 0 now]
-     */
-    while (maxtries-- > 0) {
-        uint8_t sha_digest[HIP_AH_SHA_LEN];
-
-        /* must be 8 */
-        memcpy(cookie + 40, (uint8_t *) &randval, sizeof(uint64_t));
-
-        hip_build_digest(HIP_DIGEST_SHA1, cookie, 48, sha_digest);
-
-        /* copy the last 8 bytes for checking */
-        memcpy(&digest, sha_digest + 12, sizeof(uint64_t));
-
-        /* now, in order to be able to do correctly the bitwise
-         * AND-operation we have to remember that little endian
-         * processors will interpret the digest and mask reversely.
-         * digest is the last 64 bits of the sha1-digest.. how that is
-         * ordered in processors registers etc.. does not matter to us.
-         * If the last 64 bits of the sha1-digest is
-         * 0x12345678DEADBEEF, whether we have 0xEFBEADDE78563412
-         * doesn't matter because the mask matters... if the mask is
-         * 0x000000000000FFFF (or in other endianness
-         * 0xFFFF000000000000). Either ways... the result is
-         * 0x000000000000BEEF or 0xEFBE000000000000, which the cpu
-         * interprets as 0xBEEF. The mask is converted to network byte
-         * order (above).
-         */
-        if ((digest & mask) == 0) {
-            _HIP_DEBUG("*** Puzzle solved ***: 0x%llx\n", randval);
-            _HIP_HEXDUMP("digest", sha_digest, HIP_AH_SHA_LEN);
-            _HIP_HEXDUMP("cookie", cookie, sizeof(cookie));
-            return randval;
-        }
-
-        /* It seems like the puzzle was not correctly solved */
-        HIP_IFEL(mode == HIP_VERIFY_PUZZLE, 0, "Puzzle incorrect\n");
-        randval++;
-    }
-
-    HIP_ERROR("Could not solve the puzzle, no solution found\n");
-out_err:
-    return err;
-}
-
-#ifdef CONFIG_HIP_MIDAUTH
-/**
- * solve a midauth puzzle which is essentially a normal HIP cookie
- * with some extra whipped cream on the top
- *
- * @param out the received R1 message
- * @param in an I2 message where the solution will be written
- * @param entry the related host association
- * @return zero on success and negative on error
- * @see <a
- * href="http://tools.ietf.org/id/draft-heer-hip-middle-auth";>Heer et
- * al, End-Host Authentication for HIP Middleboxes, Internet draft,
- * work in progress, February 2009</a>
- */
-int hip_solve_puzzle_m(struct hip_common *out,
-                       struct hip_common *in,
-                       hip_ha_t *entry)
-{
-    struct hip_challenge_request *pz;
-    struct hip_puzzle tmp;
-    uint64_t solution;
-    int err = 0;
-    uint8_t digist[HIP_AH_SHA_LEN];
-
-
-    pz = hip_get_param(in, HIP_PARAM_CHALLENGE_REQUEST);
-    while (pz) {
-        if (hip_get_param_type(pz) != HIP_PARAM_CHALLENGE_REQUEST) {
-            break;
-        }
-
-        HIP_IFEL(hip_build_digest(HIP_DIGEST_SHA1, pz->opaque, 24, digist) < 0,
-                 -1, "Building of SHA1 Random seed I failed\n");
-        tmp.type      = pz->type;
-        tmp.length    = pz->length;
-        tmp.K         = pz->K;
-        tmp.lifetime  = pz->lifetime;
-        tmp.opaque[0] = tmp.opaque[1] = 0;
-        tmp.I         = *digist & 0x40; //truncate I to 8 byte length
-
-        HIP_IFEL((solution = entry->hadb_misc_func->hip_solve_puzzle(
-                      &tmp, in, HIP_SOLVE_PUZZLE)) == 0,
-                 -EINVAL, "Solving of puzzle failed\n");
-
-        HIP_IFEL(hip_build_param_challenge_response(out, pz, ntoh64(solution)) 
< 0,
-                 -1,
-                 "Error while creating solution_m reply parameter\n");
-        pz = (struct hip_challenge_request *) hip_get_next_param(in,
-                                                                 (struct 
hip_tlv_common *) pz);
-    }
-
-out_err:
-    return err;
-}
-#endif /* CONFIG_HIP_MIDAUTH */
 
 /**
  * get the state of the bex for a pair of ip addresses.

=== modified file 'lib/core/misc.h'
--- lib/core/misc.h     2010-03-08 22:21:34 +0000
+++ lib/core/misc.h     2010-03-09 08:57:46 +0000
@@ -139,10 +139,6 @@
 
 int addr2ifindx(struct in6_addr *local_address);
 
-uint64_t hip_solve_puzzle(void *puzzle, struct hip_common *hdr, int mode);
-int hip_solve_puzzle_m(struct hip_common *out,
-                       struct hip_common *in,
-                       hip_ha_t *entry);
 /**
  * Converts a string to lowercase. Converts parameter @c from string to a
  * lowercase string and places the result in @c to. All alphabetic (isalpha())

=== added file 'lib/core/solve.c'
--- lib/core/solve.c    1970-01-01 00:00:00 +0000
+++ lib/core/solve.c    2010-03-09 08:57:46 +0000
@@ -0,0 +1,177 @@
+/**
+ * @file
+ *
+ * Distributed under <a href="http://www.gnu.org/licenses/gpl2.txt";>GNU/GPL</a>
+ *
+ * @brief HIP computation puzzle solving algorithms
+ *
+ * @author Miika Komu <miika@xxxxxx>
+ */
+
+#include "solve.h"
+
+/**
+ * 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.
+ */
+uint64_t hip_solve_puzzle(void *puzzle_or_solution,
+                          struct hip_common *hdr,
+                          int mode)
+{
+    uint64_t mask     = 0;
+    uint64_t randval  = 0;
+    uint64_t maxtries = 0;
+    uint64_t digest   = 0;
+    uint8_t cookie[48];
+    int err           = 0;
+    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)));
+
+    _HIP_DEBUG("\n");
+    /* pre-create cookie */
+    u = puzzle_or_solution;
+
+    _HIP_DEBUG("current hip_cookie_max_k_r1=%d\n", max_k);
+    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, (uint8_t *) &(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 = ntoh64(u->sl.J);
+        randval  = u->sl.J;
+        _HIP_DEBUG("u->sl.J: 0x%llx\n", randval);
+        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(u_int64_t));
+    } else {
+        HIP_IFEL(1, 0, "Unknown mode: %d\n", mode);
+    }
+
+    HIP_DEBUG("K=%u, maxtries (with k+2)=%llu\n", u->pz.K, maxtries);
+    /* while loops should work even if the maxtries is unsigned
+     * if maxtries = 1 ---> while(1 > 0) [maxtries == 0 now]...
+     * the next round while (0 > 0) [maxtries > 0 now]
+     */
+    while (maxtries-- > 0) {
+        uint8_t sha_digest[HIP_AH_SHA_LEN];
+
+        /* must be 8 */
+        memcpy(cookie + 40, (uint8_t *) &randval, sizeof(uint64_t));
+
+        hip_build_digest(HIP_DIGEST_SHA1, cookie, 48, sha_digest);
+
+        /* copy the last 8 bytes for checking */
+        memcpy(&digest, sha_digest + 12, sizeof(uint64_t));
+
+        /* now, in order to be able to do correctly the bitwise
+         * AND-operation we have to remember that little endian
+         * processors will interpret the digest and mask reversely.
+         * digest is the last 64 bits of the sha1-digest.. how that is
+         * ordered in processors registers etc.. does not matter to us.
+         * If the last 64 bits of the sha1-digest is
+         * 0x12345678DEADBEEF, whether we have 0xEFBEADDE78563412
+         * doesn't matter because the mask matters... if the mask is
+         * 0x000000000000FFFF (or in other endianness
+         * 0xFFFF000000000000). Either ways... the result is
+         * 0x000000000000BEEF or 0xEFBE000000000000, which the cpu
+         * interprets as 0xBEEF. The mask is converted to network byte
+         * order (above).
+         */
+        if ((digest & mask) == 0) {
+            _HIP_DEBUG("*** Puzzle solved ***: 0x%llx\n", randval);
+            _HIP_HEXDUMP("digest", sha_digest, HIP_AH_SHA_LEN);
+            _HIP_HEXDUMP("cookie", cookie, sizeof(cookie));
+            return randval;
+        }
+
+        /* It seems like the puzzle was not correctly solved */
+        HIP_IFEL(mode == HIP_VERIFY_PUZZLE, 0, "Puzzle incorrect\n");
+        randval++;
+    }
+
+    HIP_ERROR("Could not solve the puzzle, no solution found\n");
+out_err:
+    return err;
+}
+
+#ifdef CONFIG_HIP_MIDAUTH
+/**
+ * solve a midauth puzzle which is essentially a normal HIP cookie
+ * with some extra whipped cream on the top
+ *
+ * @param out the received R1 message
+ * @param in an I2 message where the solution will be written
+ * @param entry the related host association
+ * @return zero on success and negative on error
+ * @see <a
+ * href="http://tools.ietf.org/id/draft-heer-hip-middle-auth";>Heer et
+ * al, End-Host Authentication for HIP Middleboxes, Internet draft,
+ * work in progress, February 2009</a>
+ */
+int hip_solve_puzzle_m(struct hip_common *out,
+                       struct hip_common *in,
+                       hip_ha_t *entry)
+{
+    struct hip_challenge_request *pz;
+    struct hip_puzzle tmp;
+    uint64_t solution;
+    int err = 0;
+    uint8_t digist[HIP_AH_SHA_LEN];
+
+
+    pz = hip_get_param(in, HIP_PARAM_CHALLENGE_REQUEST);
+    while (pz) {
+        if (hip_get_param_type(pz) != HIP_PARAM_CHALLENGE_REQUEST) {
+            break;
+        }
+
+        HIP_IFEL(hip_build_digest(HIP_DIGEST_SHA1, pz->opaque, 24, digist) < 0,
+                 -1, "Building of SHA1 Random seed I failed\n");
+        tmp.type      = pz->type;
+        tmp.length    = pz->length;
+        tmp.K         = pz->K;
+        tmp.lifetime  = pz->lifetime;
+        tmp.opaque[0] = tmp.opaque[1] = 0;
+        tmp.I         = *digist & 0x40; //truncate I to 8 byte length
+
+        HIP_IFEL((solution = entry->hadb_misc_func->hip_solve_puzzle(
+                      &tmp, in, HIP_SOLVE_PUZZLE)) == 0,
+                 -EINVAL, "Solving of puzzle failed\n");
+
+        HIP_IFEL(hip_build_param_challenge_response(out, pz, ntoh64(solution)) 
< 0,
+                 -1,
+                 "Error while creating solution_m reply parameter\n");
+        pz = (struct hip_challenge_request *) hip_get_next_param(in,
+                                                                 (struct 
hip_tlv_common *) pz);
+    }
+
+out_err:
+    return err;
+}
+#endif /* CONFIG_HIP_MIDAUTH */
+

=== added file 'lib/core/solve.h'
--- lib/core/solve.h    1970-01-01 00:00:00 +0000
+++ lib/core/solve.h    2010-03-09 08:57:46 +0000
@@ -0,0 +1,21 @@
+#ifndef HIP_LIB_CORE_SOLVE_H
+#define HIP_LIB_CORE_SOLVE_H
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif /* HAVE_CONFIG_H */
+
+#include <sys/types.h>
+#include "lib/core/crypto.h"
+#include "protodefs.h"
+#include "state.h"
+#include "misc.h"
+
+#define HIP_PUZZLE_MAX_K        28
+
+uint64_t hip_solve_puzzle(void *puzzle, struct hip_common *hdr, int mode);
+int hip_solve_puzzle_m(struct hip_common *out,
+                       struct hip_common *in,
+                       hip_ha_t *entry);
+
+#endif /* HIP_LIB_CORE_SOLVE_H */

=== modified file 'test/cookietest.c'
--- test/cookietest.c   2010-02-17 17:38:08 +0000
+++ test/cookietest.c   2010-03-09 08:57:46 +0000
@@ -3,6 +3,7 @@
 
 #include "lib/core/debug.h"
 #include "lib/core/misc.h"
+#include "lib/core/solve.h"
 #include <sys/time.h>
 #include <time.h>

Other related posts:

  • » [hipl-commit] [trunk] Rev 3860: Splitting misc.c continued (bug id 1139). Added a separate source and header file for puzzle solving. - Miika Komu