src/TortoisePlink/SSHCRC.C

   1 /*\r
   2  * CRC32 implementation, as used in SSH-1.\r
   3  *\r
   4  * This particular form of the CRC uses the polynomial\r
   5  * P(x) = x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x^1+1\r
   6  * and represents polynomials in bit-reversed form, so that the x^0\r
   7  * coefficient (constant term) appears in the bit with place value\r
   8  * 2^31, and the x^31 coefficient in the bit with place value 2^0. In\r
   9  * this representation, (x^32 mod P) = 0xEDB88320, so multiplying the\r
  10  * current state by x is done by shifting right by one bit, and XORing\r
  11  * that constant into the result if the bit shifted out was 1.\r
  12  *\r
  13  * There's a bewildering array of subtly different variants of CRC out\r
  14  * there, using different polynomials, both bit orders, and varying\r
  15  * the start and end conditions. There are catalogue websites such as\r
  16  * http://reveng.sourceforge.net/crc-catalogue/ , which generally seem\r
  17  * to have the convention of indexing CRCs by their 'check value',\r
  18  * defined as whatever you get if you hash the 9-byte test string\r
  19  * "123456789".\r
  20  *\r
  21  * The crc32_rfc1662() function below, which starts off the CRC state\r
  22  * at 0xFFFFFFFF and complements it after feeding all the data, gives\r
  23  * the check value 0xCBF43926, and matches the hash function that the\r
  24  * above catalogue refers to as "CRC-32/ISO-HDLC"; among other things,\r
  25  * it's also the "FCS-32" checksum described in RFC 1662 section C.3\r
  26  * (hence the name I've given it here).\r
  27  *\r
  28  * The crc32_ssh1() function implements the variant form used by\r
  29  * SSH-1, which uses the same update function, but starts the state at\r
  30  * zero and doesn't complement it at the end of the computation. The\r
  31  * check value for that version is 0x2DFD2D88, which that CRC\r
  32  * catalogue doesn't list at all.\r
  33  */\r
  34 \r
  35 #include <stdint.h>\r
  36 #include <stdlib.h>\r
  37 \r
  38 #include "ssh.h"\r
  39 \r
  40 /*\r
  41  * Multiply a CRC value by x^4. This implementation strategy avoids\r
  42  * using a lookup table (which would be a side-channel hazard, since\r
  43  * SSH-1 applies this CRC to decrypted session data).\r
  44  *\r
  45  * The basic idea is that you'd like to "multiply" the shifted-out 4\r
  46  * bits by the CRC polynomial value 0xEDB88320, or rather by that\r
  47  * value shifted right 3 bits (since you want the _last_ bit shifted\r
  48  * out, i.e. the one originally at the 2^3 position, to generate\r
  49  * 0xEDB88320 itself). But the scare-quoted "multiply" would have to\r
  50  * be a multiplication of polynomials over GF(2), which differs from\r
  51  * integer multiplication in that you don't have any carries. In other\r
  52  * words, you make a copy of one input shifted left by the index of\r
  53  * each set bit in the other, so that adding them all together would\r
  54  * give you the ordinary integer product, and then you XOR them\r
  55  * together instead.\r
  56  *\r
  57  * With a 4-bit multiplier, the two kinds of multiplication coincide\r
  58  * provided the multiplicand has no two set bits at positions\r
  59  * differing by less than 4, because then no two copies of the\r
  60  * multiplier can overlap to generate a carry. So I break up the\r
  61  * intended multiplicand K = 0xEDB88320 >> 3 into three sub-constants\r
  62  * a,b,c with that property, such that a^b^c = K. Then I can multiply\r
  63  * m by each of them separately, and XOR together the results.\r
  64  */\r
  65 static inline uint32_t crc32_shift_4(uint32_t v)\r
  66 {\r
  67     const uint32_t a = 0x11111044, b = 0x08840020, c = 0x04220000;\r
  68     uint32_t m = v & 0xF;\r
  69     return (v >> 4) ^ (a*m) ^ (b*m) ^ (c*m);\r
  70 }\r
  71 \r
  72 /*\r
  73  * The 8-bit shift you need every time you absorb an input byte,\r
  74  * implemented simply by iterating the 4-bit shift twice.\r
  75  */\r
  76 static inline uint32_t crc32_shift_8(uint32_t v)\r
  77 {\r
  78     return crc32_shift_4(crc32_shift_4(v));\r
  79 }\r
  80 \r
  81 /*\r
  82  * Update an existing hash value with extra bytes of data.\r
  83  */\r
  84 uint32_t crc32_update(uint32_t crc, ptrlen data)\r
  85 {\r
  86     const uint8_t *p = (const uint8_t *)data.ptr;\r
  87     for (size_t len = data.len; len-- > 0 ;)\r
  88         crc = crc32_shift_8(crc ^ *p++);\r
  89     return crc;\r
  90 }\r
  91 \r
  92 /*\r
  93  * The SSH-1 variant of CRC-32.\r
  94  */\r
  95 uint32_t crc32_ssh1(ptrlen data)\r
  96 {\r
  97     return crc32_update(0, data);\r
  98 }\r
  99 \r
 100 /*\r
 101  * The official version of CRC-32. Nothing in PuTTY proper uses this,\r
 102  * but it's useful to expose it to testcrypt so that we can implement\r
 103  * standard test vectors.\r
 104  */\r
 105 uint32_t crc32_rfc1662(ptrlen data)\r
 106 {\r
 107     return crc32_update(0xFFFFFFFF, data) ^ 0xFFFFFFFF;\r
 108 }\r