Generating X-CR-HashedPuzzle

The puzzle P takes the following parameters as input (see section

  • Number of recipients r.

  • E-mail addresses of the recipients t.

  • Algorithm type a.

  • A 'degree of difficulty' n.

  • A message id m.

  • An e-mail 'From: address' f.

  • A datetime d.

  • A subject line s.

From these parameters, a document D is formed by concatenating all the parameters together, separating each field with ';'. The constructed document D is represented in a non-Unicode string.

Given the sequence of bytes comprising a document D, the computational task involved in the puzzle is to find and exhibit a set of sixteen documents δ such that both of the following are true:

  • When each δ is prepended to the hash under the Son-of-SHA-1 hash algorithm H (see section 2.3.3) of D with its whitespace removed and then hashed again to form H(δ o H(NWS(D))), the result is zero in at least the first n bits (taken most significant bit first within each byte taken in order). Here, NWS is the function that takes a sequence of bytes as input, removes all those that are legal characters that could match the FWS production specified in [RFC2822], and produces the remaining as output.

  • The last 12 bits of each H(δ o H(NWS(D)) are the same (the particular 12-bit suffix value shared by these documents does not matter).

Note In the previous two computations, the o operator denotes string concatenation.

That is, the answer to the puzzle P(t, n, m, f, d, s) is a set of 16 documents δ each with these characteristics. The hash H(NWS(D)) is used as the suffix to which each δ is prepended rather than simply D in order to minimize the effect of variation in the length of D on the length of time required to solve the puzzle. Whitespace is stripped from D before being input to the hash in order to minimize sensitivity to the encoding of D in header fields where it can be subjected to folding.

No means other than brute force is known to locate satisfactory δ; however, that a given set of δ indeed answers the puzzle can be quickly verified. The particular brute force approach of first trying all one-byte solutions, then trying all two-byte solutions, then all three-byte solutions, and so on, is as good a solution algorithm as any other, but has the additional benefit that the solutions found will be as small as possible. Furthermore, for puzzles that have reasonable degrees of difficulty, solutions with four or fewer bytes will be typical.

Specifically, the following pseudocode describes the brute force algorithm:

 Solution = 0;
     Hash = H(concatenate(Solution, H(NWS(D))))
     If Verify(Solution, Puzzle) succeeds {
         Remember this solution and Hash
         If we have 16 solutions whose last 12 bits of their 
         corresponding Hash are the same {
             Return these 16 solutions
 Solution ++

After the solutions for puzzle P are found, a presolution header is generated. The presolution header MUST be the concatenation of the solutions string and the document D separated by a semicolon. The solutions string MUST be a string formed by base64 encoding each of the 16 puzzle solutions and concatenating them together, with a ''" (space) delimiter.

The value of X-CR-HashedPuzzle MUST be set to the presolution header. See section 3 for examples.