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_DIGEST_LENGTH];
> +    int                  err = -1;
> +    uint64_t             i   = 0;
> +
> +    HIP_IFEL(!solution, -1, "invalid parameter passed (NULL)\n");
> +
> +    HIP_IFEL(difficulty > max_puzzle_difficulty, -1,
> +             "Cookie (K = %i) is higher than we are willing to calculate"
> +             " (current max K = %i)\n", difficulty, max_puzzle_difficulty);

Again, we can exit early for difficulty = 0.

> +}
> +
> +int hip_verify_puzzle_solution(const uint64_t puzzle,
> +                               const uint8_t difficulty,
> +                               const hip_hit_t initiator_hit,
> +                               const hip_hit_t responder_hit,
> +                               const uint64_t solution)

Missing documentation (there are other instances too).
 
> +/* right now we only support difficulties up to sizeof(int), as only ffs
> + * is available on OpenWRT */

OpenSSL bignums (which are used in HIPL anyway) could be an alternative to ffs(), but a poor WRT is probably not gonna handle such a big puzzle anyway... so I'd say your Solution is OK.

> +// For unknown reasons, this file does not compile with the following,
> +// seemingly useless forward declaration
> +Suite *lib_core_solve(void);

What's the error message?