CheckPoint Puzzles DoS Protection

CheckPoint implements an IKE DoS protection mechanism called puzzles, which is enabled by default for remote access VPNs. This is based on Puzzles: A Cryptographic Countermeasure Against Connection Depletion Attacks.

When the VPN server is under heavy load, it requires the client to solve a mathematical puzzle before being allowed to connect. The CheckPoint remote access VPN client is able to solve the puzzle, so remote access users can continue to connect even if an attacker is launching a resource exhaustion DoS attack. The server indicates that it is under load by responding to an IKE Phase-1 initiation with a notify message. The example below shows three of these notification messages as decoded by ike-scan:

172.16.2.2      Notify message 9110 (Firewall-1) Message="Server under heavy load.
        \000\000\000\000\000\000\000\000\257D\220\323\212\220W\202k\023\270\331\307\210\2529\023"
        HDR=(CKY-R=80a0b55b5e500000, msgid=a13325e7)
172.16.2.2      Notify message 9110 (Firewall-1) Message="Server under heavy load.
        \000\000\000\000\000\000\000\0006\352\313Kt\225Am\335,!\2520D\310\340\023"
        HDR=(CKY-R=4fb29c823ef80000, msgid=a1e7d366)
172.16.2.2      Notify message 9110 (Firewall-1) Message="Server under heavy load.
        \000\000\000\000\000\000\000\000\335\\\223*\236N\362\220\004\310\214\343\n\177\266\361\023"
        HDR=(CKY-R=afb4fc13ff500000, msgid=b2f5242a)
172.16.2.2      Notify message 9110 (Firewall-1) Message="Server under heavy load.
        \000\000\000\000\000\000\000\000\276a+\220\310\025\220\316\274Y\360\360\nA\333\253\023"
        HDR=(CKY-R=105cda7412c00000, msgid=2b834f5b)

Each of these notify messages represents a puzzle. The data needed to solve the puzzle is contained in the notify message and the responder cookie CKY-R. When the server is under load, it will only enter into Phase-1 negotiations with a system that provides the answer to the puzzle in the responder cookie of its first message.

The notification message consists of the ASCII string "Server under heavy load." followed by twenty five bytes containing binary data. In the examples above, this binary data is shown as C Escape sequences. The table below shows the format of this binary data, using the first example above but representing the data as hex:

Byte Position	Field Length	Example Data (hex)	Meaning
1 to 8	8	00 00 00 00 00 00 00 00	Eight zero bytes
9 to 24	16	af 44 90 d3 8a 90 57 82 6b 13 b8 d9 c7 88 aa 39	MD5 hash
25	1	13	Puzzle complexity

The answer to the puzzle is the 64-bit (8-byte) value whos MD5 hash is that specified in the notification message. The responder cookie from the notification message contains a partial answer with the number of bits specified by the puzzle complexity being unknown. These unknown bits are set to zero in the notify message responder cookie.

Responder Cookie (hex)	Responder Cookie (binary)
80 a0 b5 5b 5e 50 00 00	10000000 10100000 10110101 01011011 01011110 01010000 00000000 00000000

In the example above the complexity is 19 (0x13), so the low-order 19 bits of the responder cookie are unknown. So the question is:

MD5(10000000 10100000 10110101 01011011 01011110 01010??? ???????? ????????) = 0xaf 44 90 d3 8a 90 57 82 6b 13 b8 d9 c7 88 aa 39

The only known way to find the answer is by brute force, which will take up to 2^19 MD5 operations. The following C program could be used to find the answer:

int main(void) {
   unsigned char cookie_data[] = {0x80, 0xa0, 0xb5, 0x5b, 0x5e, 0x50, 0x00, 0x00};
   unsigned char hash[] = {0xaf, 0x44, 0x90, 0xd3, 0x8a, 0x90, 0x57, 0x82,
                           0x6b, 0x13, 0xb8, 0xd9, 0xc7, 0x88, 0xaa, 0x39};
   unsigned cookie[2];          /* Cookie as two 32-bit values */
   unsigned nbits = 19;         /* 1 <= nbits <= 32 */
   unsigned char *test_hash;
   unsigned min, max, count;

   memcpy(cookie, cookie_data, 8);
   min = ntohl(cookie[1]);
   max = min + (1 << nbits) - 1;

   for (count=min; count<=max; count++) {
      cookie[1] = htonl(count);
      test_hash = MD5((unsigned char *)cookie, 8, NULL);
      if (memcmp(hash, test_hash, 16) == 0) {
         printf("%s\n", hexstring((unsigned char *)cookie, 8));
         break;
      }
   }
   return 0;
}

Running the program gives us the answer to the puzzle:

$ time ./solve-puzzle
80a0b55b5e51d0f8

real    0m0.158s
user    0m0.148s
sys     0m0.008s

We can double-check the answer by checking that the MD5 hash of the answer is the same as the hash in the notify data.

$ perl -e 'print pack "H*", "80a0b55b5e51d0f8"' | md5sum
af4490d38a9057826b13b8d9c788aa39  -