Consider a puzzle with the following 23-character clue:
4lowercase+4digits+gz8L
The clue suggests a brute force attack of trying all strings aaaa0000gz8L through zzzz9999gz8L as possible solutions. (The final 4 characters gz8L were a random salt to thwart precomputation.) There are 26^4 * 10^4 = 4.6e9 possible strings.
Note well that the format is letters followed by digits, with no interleaving. We keep things simple.
The intended application is a puzzle encoded in the name of a wireless access point, with the solution being the password. Wifi access point names must be 32 characters or less. The 23 characters in puzzle above meets this constraint. This page says that a 2017 GPU can try about 400,000 passwords per second to offline-decrypt a captured WPA2 handshake. Therefore, this puzzle would take 4.6e9/400e3 = 11000 seconds = 190 minutes (in the worst case) to solve by brute force or half that, 95 minutes, on average. (This is of course after first sniffing a WPA2 handshake, which might take a while.)
A barrier of 3 hours might be enough to deter casual attackers but let through people deemed worthy, those willing to invest that amount of time and computational effort to get free wifi. Or maybe this is suitable for an escape-the-room style physical puzzle: connecting to the wifi reveals the next part of the puzzle.
(Or, one could troll the nerds by having the solution be completely unrelated to the clue: the clue was a red herring to send people off on a wild goose chase. Then, the rest of this post is a discussion of just how long a chase.)
Previous similar puzzles: factorization and discrete logarithm. The puzzle this time, internally about brute-forcing SHA1, is much easier to set up: it does not require the poser solve the puzzle first. However, brute forcing SHA1 seems a lot less sexy than integer factorization.
Below are some puzzle size parameters and the number of possibilities for those parameters, expressed as a power of 10 for ease of comparison. For example,
10 ^ 9.66 = 26 ^ 4 * 10 ^ 4
indicates that a puzzle of 4 lowercase letters followed by 4 digits has 10^9.66 = 4.6 * 10^9 possibilities. This list below is a guide for choosing puzzle parameters based on how much work you want the attacker to do. (It does require knowing the hardware capability of the attacker to estimate the time it will take an attacker.)
The final puzzle size on the list, 3lowercase+15digits, has over 10^19 possibilities, so it would take 508 days even with a million GPUs. This is doable by a national intelligence agency. Of course, national intelligence agencies typically operate above the law and apply rubber-hose cryptanalysis on you or your loved ones for less than 508 days to extract the answer more quickly.
For even larger puzzles, it is straightforward to increase the number of digits to scale the difficulty of a smaller puzzle by a power of 10. Or, use this Haskell source code to find parameters of a puzzle of desired difficulty. Solutions (WPA2 passwords) must be 63 characters or less, so there remains plenty of room to expand even if just using digits.
Initially, we considered restricting puzzles to just letters or to just numbers, but those result in puzzles that grow in difficulty by factors of 26 or 10, which we felt were too steep of increases between levels of difficulty. Doing letters followed by numbers allows finer gradations of difficulty. For example, we have 8 gradations between 10^8 and 10^9, so difficulty in that range grows by a factor of about 1.33 between gradations. Further along, the gradations (on a log scale) become even finer. What is the growth rate of this sequence? How close can consecutive numbers of this sequence be (important for comparing values for sorting)? How widely separated can consecutive numbers be?
Generating all numbers of the form 26^a * 10^b in sorted order is a classic algorithmic puzzle, which we solve in Haskell by using Data.List.Ordered.union in the data-ordlist package. (Previously on data-ordlist, which is quite handy.) Here is the source code used to generate the list below.
Below is a code excerpt demonstrating the call to Data.List.Ordered.union in the self-recursive nums function. Is there a more elegant way to write the nums function, not having to explicitly index into a list (which we do with the incn function)? (Though elegance is subjective.)
The code is generalized to be able to handle an arbitrary number of character classes of arbitrary sizes (not just our 2 classes of size 26 and 10). To do so, modify the variable bases.
bases :: [Integer];
bases = [26,10];
-- representing the exponents of a single number, e.g.,
-- N [3,4] represents 26^3 * 10^4 .
data N = N [Integer] deriving (Show,Eq);
value :: N -> Integer;
value (N x) = product $ zipWith (^) bases x;
instance Ord N where {
compare = comparing value;
-- OK if the values are not too large. Comparing logs would be faster, though that relies on floating point having enough precision.
};
nums :: [N];
nums = N (map (const 0) bases) : foldr Ordered.union [] (do {
index <- zipWith const [0..] bases; -- equivalent to [0 .. (length bases -1)]
return $ map (incn index) nums;
});
-- increment just the nth item in the list
incn :: Integer -> N -> N;
incn n (N x) = let {
(p,q:rest) = List.genericSplitAt n x;
} in N $ p ++ (succ q:rest);
10 ^ 0.00 = 26 ^ 0 * 10 ^ 0 10 ^ 1.00 = 26 ^ 0 * 10 ^ 1 10 ^ 1.41 = 26 ^ 1 * 10 ^ 0 10 ^ 2.00 = 26 ^ 0 * 10 ^ 2 10 ^ 2.41 = 26 ^ 1 * 10 ^ 1 10 ^ 2.83 = 26 ^ 2 * 10 ^ 0 10 ^ 3.00 = 26 ^ 0 * 10 ^ 3 10 ^ 3.41 = 26 ^ 1 * 10 ^ 2 10 ^ 3.83 = 26 ^ 2 * 10 ^ 1 10 ^ 4.00 = 26 ^ 0 * 10 ^ 4 10 ^ 4.24 = 26 ^ 3 * 10 ^ 0 10 ^ 4.41 = 26 ^ 1 * 10 ^ 3 10 ^ 4.83 = 26 ^ 2 * 10 ^ 2 10 ^ 5.00 = 26 ^ 0 * 10 ^ 5 10 ^ 5.24 = 26 ^ 3 * 10 ^ 1 10 ^ 5.41 = 26 ^ 1 * 10 ^ 4 10 ^ 5.66 = 26 ^ 4 * 10 ^ 0 10 ^ 5.83 = 26 ^ 2 * 10 ^ 3 10 ^ 6.00 = 26 ^ 0 * 10 ^ 6 10 ^ 6.24 = 26 ^ 3 * 10 ^ 2 10 ^ 6.41 = 26 ^ 1 * 10 ^ 5 10 ^ 6.66 = 26 ^ 4 * 10 ^ 1 10 ^ 6.83 = 26 ^ 2 * 10 ^ 4 10 ^ 7.00 = 26 ^ 0 * 10 ^ 7 10 ^ 7.07 = 26 ^ 5 * 10 ^ 0 10 ^ 7.24 = 26 ^ 3 * 10 ^ 3 10 ^ 7.41 = 26 ^ 1 * 10 ^ 6 10 ^ 7.66 = 26 ^ 4 * 10 ^ 2 10 ^ 7.83 = 26 ^ 2 * 10 ^ 5 10 ^ 8.00 = 26 ^ 0 * 10 ^ 8 10 ^ 8.07 = 26 ^ 5 * 10 ^ 1 10 ^ 8.24 = 26 ^ 3 * 10 ^ 4 10 ^ 8.41 = 26 ^ 1 * 10 ^ 7 10 ^ 8.49 = 26 ^ 6 * 10 ^ 0 10 ^ 8.66 = 26 ^ 4 * 10 ^ 3 10 ^ 8.83 = 26 ^ 2 * 10 ^ 6 10 ^ 9.00 = 26 ^ 0 * 10 ^ 9 10 ^ 9.07 = 26 ^ 5 * 10 ^ 2 10 ^ 9.24 = 26 ^ 3 * 10 ^ 5 10 ^ 9.41 = 26 ^ 1 * 10 ^ 8 10 ^ 9.49 = 26 ^ 6 * 10 ^ 1 10 ^ 9.66 = 26 ^ 4 * 10 ^ 4 10 ^ 9.83 = 26 ^ 2 * 10 ^ 7 10 ^ 9.90 = 26 ^ 7 * 10 ^ 0 10 ^ 10.00 = 26 ^ 0 * 10 ^ 10 10 ^ 10.07 = 26 ^ 5 * 10 ^ 3 10 ^ 10.24 = 26 ^ 3 * 10 ^ 6 10 ^ 10.41 = 26 ^ 1 * 10 ^ 9 10 ^ 10.49 = 26 ^ 6 * 10 ^ 2 10 ^ 10.66 = 26 ^ 4 * 10 ^ 5 10 ^ 10.83 = 26 ^ 2 * 10 ^ 8 10 ^ 10.90 = 26 ^ 7 * 10 ^ 1 10 ^ 11.00 = 26 ^ 0 * 10 ^ 11 10 ^ 11.07 = 26 ^ 5 * 10 ^ 4 10 ^ 11.24 = 26 ^ 3 * 10 ^ 7 10 ^ 11.32 = 26 ^ 8 * 10 ^ 0 10 ^ 11.41 = 26 ^ 1 * 10 ^ 10 10 ^ 11.49 = 26 ^ 6 * 10 ^ 3 10 ^ 11.66 = 26 ^ 4 * 10 ^ 6 10 ^ 11.83 = 26 ^ 2 * 10 ^ 9 10 ^ 11.90 = 26 ^ 7 * 10 ^ 2 10 ^ 12.00 = 26 ^ 0 * 10 ^ 12 10 ^ 12.07 = 26 ^ 5 * 10 ^ 5 10 ^ 12.24 = 26 ^ 3 * 10 ^ 8 10 ^ 12.32 = 26 ^ 8 * 10 ^ 1 10 ^ 12.41 = 26 ^ 1 * 10 ^ 11 10 ^ 12.49 = 26 ^ 6 * 10 ^ 4 10 ^ 12.66 = 26 ^ 4 * 10 ^ 7 10 ^ 12.73 = 26 ^ 9 * 10 ^ 0 10 ^ 12.83 = 26 ^ 2 * 10 ^ 10 10 ^ 12.90 = 26 ^ 7 * 10 ^ 3 10 ^ 13.00 = 26 ^ 0 * 10 ^ 13 10 ^ 13.07 = 26 ^ 5 * 10 ^ 6 10 ^ 13.24 = 26 ^ 3 * 10 ^ 9 10 ^ 13.32 = 26 ^ 8 * 10 ^ 2 10 ^ 13.41 = 26 ^ 1 * 10 ^ 12 10 ^ 13.49 = 26 ^ 6 * 10 ^ 5 10 ^ 13.66 = 26 ^ 4 * 10 ^ 8 10 ^ 13.73 = 26 ^ 9 * 10 ^ 1 10 ^ 13.83 = 26 ^ 2 * 10 ^ 11 10 ^ 13.90 = 26 ^ 7 * 10 ^ 4 10 ^ 14.00 = 26 ^ 0 * 10 ^ 14 10 ^ 14.07 = 26 ^ 5 * 10 ^ 7 10 ^ 14.15 = 26 ^ 10 * 10 ^ 0 10 ^ 14.24 = 26 ^ 3 * 10 ^ 10 10 ^ 14.32 = 26 ^ 8 * 10 ^ 3 10 ^ 14.41 = 26 ^ 1 * 10 ^ 13 10 ^ 14.49 = 26 ^ 6 * 10 ^ 6 10 ^ 14.66 = 26 ^ 4 * 10 ^ 9 10 ^ 14.73 = 26 ^ 9 * 10 ^ 2 10 ^ 14.83 = 26 ^ 2 * 10 ^ 12 10 ^ 14.90 = 26 ^ 7 * 10 ^ 5 10 ^ 15.00 = 26 ^ 0 * 10 ^ 15 10 ^ 15.07 = 26 ^ 5 * 10 ^ 8 10 ^ 15.15 = 26 ^ 10 * 10 ^ 1 10 ^ 15.24 = 26 ^ 3 * 10 ^ 11 10 ^ 15.32 = 26 ^ 8 * 10 ^ 4 10 ^ 15.41 = 26 ^ 1 * 10 ^ 14 10 ^ 15.49 = 26 ^ 6 * 10 ^ 7 10 ^ 15.56 = 26 ^ 11 * 10 ^ 0 10 ^ 15.66 = 26 ^ 4 * 10 ^ 10 10 ^ 15.73 = 26 ^ 9 * 10 ^ 3 10 ^ 15.83 = 26 ^ 2 * 10 ^ 13 10 ^ 15.90 = 26 ^ 7 * 10 ^ 6 10 ^ 16.00 = 26 ^ 0 * 10 ^ 16 10 ^ 16.07 = 26 ^ 5 * 10 ^ 9 10 ^ 16.15 = 26 ^ 10 * 10 ^ 2 10 ^ 16.24 = 26 ^ 3 * 10 ^ 12 10 ^ 16.32 = 26 ^ 8 * 10 ^ 5 10 ^ 16.41 = 26 ^ 1 * 10 ^ 15 10 ^ 16.49 = 26 ^ 6 * 10 ^ 8 10 ^ 16.56 = 26 ^ 11 * 10 ^ 1 10 ^ 16.66 = 26 ^ 4 * 10 ^ 11 10 ^ 16.73 = 26 ^ 9 * 10 ^ 4 10 ^ 16.83 = 26 ^ 2 * 10 ^ 14 10 ^ 16.90 = 26 ^ 7 * 10 ^ 7 10 ^ 16.98 = 26 ^ 12 * 10 ^ 0 10 ^ 17.00 = 26 ^ 0 * 10 ^ 17 10 ^ 17.07 = 26 ^ 5 * 10 ^ 10 10 ^ 17.15 = 26 ^ 10 * 10 ^ 3 10 ^ 17.24 = 26 ^ 3 * 10 ^ 13 10 ^ 17.32 = 26 ^ 8 * 10 ^ 6 10 ^ 17.41 = 26 ^ 1 * 10 ^ 16 10 ^ 17.49 = 26 ^ 6 * 10 ^ 9 10 ^ 17.56 = 26 ^ 11 * 10 ^ 2 10 ^ 17.66 = 26 ^ 4 * 10 ^ 12 10 ^ 17.73 = 26 ^ 9 * 10 ^ 5 10 ^ 17.83 = 26 ^ 2 * 10 ^ 15 10 ^ 17.90 = 26 ^ 7 * 10 ^ 8 10 ^ 17.98 = 26 ^ 12 * 10 ^ 1 10 ^ 18.00 = 26 ^ 0 * 10 ^ 18 10 ^ 18.07 = 26 ^ 5 * 10 ^ 11 10 ^ 18.15 = 26 ^ 10 * 10 ^ 4 10 ^ 18.24 = 26 ^ 3 * 10 ^ 14 10 ^ 18.32 = 26 ^ 8 * 10 ^ 7 10 ^ 18.39 = 26 ^ 13 * 10 ^ 0 10 ^ 18.41 = 26 ^ 1 * 10 ^ 17 10 ^ 18.49 = 26 ^ 6 * 10 ^ 10 10 ^ 18.56 = 26 ^ 11 * 10 ^ 3 10 ^ 18.66 = 26 ^ 4 * 10 ^ 13 10 ^ 18.73 = 26 ^ 9 * 10 ^ 6 10 ^ 18.83 = 26 ^ 2 * 10 ^ 16 10 ^ 18.90 = 26 ^ 7 * 10 ^ 9 10 ^ 18.98 = 26 ^ 12 * 10 ^ 2 10 ^ 19.00 = 26 ^ 0 * 10 ^ 19 10 ^ 19.07 = 26 ^ 5 * 10 ^ 12 10 ^ 19.15 = 26 ^ 10 * 10 ^ 5 10 ^ 19.24 = 26 ^ 3 * 10 ^ 15
No comments :
Post a Comment