X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/blobdiff_plain/d9d9e6456f3f6d03a0ae1d1eb78e6796ecdb7fab..c7c44436a693ef63a2c7468e3b2104b8b74767f8:/symm/des.c?ds=sidebyside diff --git a/symm/des.c b/symm/des.c index e751cf0e..19ff667b 100644 --- a/symm/des.c +++ b/symm/des.c @@ -46,61 +46,6 @@ const octet des_keysz[] = { KSZ_SET, 7, 8, 0 }; /*----- Main code ---------------------------------------------------------*/ -/* --- @permute@ --- * - * - * Arguments: @const char *p@ = pointer to permutation table - * @uint32 a, b@ = source value to permute - * @uint32 *d@ = destination for value - * - * Returns: --- - * - * Use: Performs a 64-bit permutation. The table is given in the - * normal (but bizarre) DES bit numbering system. That's not to - * say that the tables in this source file are like the normal - * DES tables, because they're not. - */ - -static void permute(const char *p, uint32 a, uint32 b, uint32 *d) -{ - uint32 x = 0, y = 0; - int i; - - for (i = 0; i < 32; i++) { - int q = p[i]; - uint32 t; - if (!q) - continue; - else if (q <= 32) - t = a; - else { - t = b; - q -= 32; - } - if (t & (1 << (32 - q))) - x |= (1 << (31 - i)); - } - - p += 32; - - for (i = 0; i < 32; i++) { - int q = p[i]; - uint32 t; - if (!q) - continue; - else if (q <= 32) - t = a; - else { - t = b; - q -= 32; - } - if (t & (1 << (32 - q))) - y |= (1 << (31 - i)); - } - - d[0] = x; - d[1] = y; -} - /* --- @des_expand@ --- * * * Arguments: @const octet *k@ = pointer to key material @@ -155,64 +100,19 @@ void des_expand(const octet *k, size_t n, uint32 *xx, uint32 *yy) void des_init(des_ctx *k, const void *buf, size_t sz) { - uint32 x, y; +#define REGWD 32 + typedef uint32 regty; + + uint32 x, y, u, v; uint32 *kp = k->k; - uint32 ka[2]; int i; - /* --- @pc1@ --- * - * - * This cryptographically useless permutation is used to mangle the key - * before it's subjected to the key schedule proper. I've not actually - * messed it about much except for inserting padding at the beginning of - * the two halves of the key. - */ - - static const char pc1[] = { - 0, 0, 0, 0, - 57, 49, 41, 33, 25, 17, 9, - 1, 58, 50, 42, 34, 26, 18, - 10, 2, 59, 51, 43, 35, 27, - 19, 11, 3, 60, 52, 44, 36, - 0, 0, 0, 0, - 63, 55, 47, 39, 31, 23, 15, - 7, 62, 54, 46, 38, 30, 22, - 14, 6, 61, 53, 45, 37, 29, - 21, 13, 5, 28, 20, 12, 4 - }; - - /* --- @pc2@ --- * - * - * This irritating but necessary permutation mangles the key between the - * simple rotation-based schedule and the actual XOR with which it modifies - * the behaviour of the cipher. - * - * This version of the table doesn't look much like the original. This is - * because some parts of the world have been permuted in order to make - * things simpler for the round function. In particular, everything is - * rotated left one place to avoid problems with the wraparound of the - * expansion permutation, and the key is split between odd and even S-boxes - * rather than high and low ones. That's without the complication of the - * padding bits in the representation of the 56-bit proto-key. - */ - - static const char pc2[] = { - 0, 0, 3 + 4, 28 + 4, 15 + 4, 6 + 4, 21 + 4, 10 + 4, /* S-box 2 */ - 0, 0, 16 + 4, 7 + 4, 27 + 4, 20 + 4, 13 + 4, 2 + 4, /* S-box 4 */ - 0, 0, 30 + 8, 40 + 8, 51 + 8, 45 + 8, 33 + 8, 48 + 8, /* S-box 6 */ - 0, 0, 46 + 8, 42 + 8, 50 + 8, 36 + 8, 29 + 8, 32 + 8, /* S-box 8 */ - 0, 0, 14 + 4, 17 + 4, 11 + 4, 24 + 4, 1 + 4, 5 + 4, /* S-box 1 */ - 0, 0, 23 + 4, 19 + 4, 12 + 4, 4 + 4, 26 + 4, 8 + 4, /* S-box 3 */ - 0, 0, 41 + 8, 52 + 8, 31 + 8, 37 + 8, 47 + 8, 55 + 8, /* S-box 5 */ - 0, 0, 44 + 8, 49 + 8, 39 + 8, 56 + 8, 34 + 8, 53 + 8 /* S-box 7 */ - }; - - /* --- @v@ --- * + /* --- @r@ --- * * * Contains the rotation amounts for the key halves. */ - static const char v[] = { + static const char r[] = { 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 }; @@ -226,24 +126,106 @@ void des_init(des_ctx *k, const void *buf, size_t sz) KSZ_ASSERT(des, sz); des_expand(buf, sz, &x, &y); - /* --- Permute using the pointless PC1 --- */ + /* --- Permute using the pointless PC1 --- * + * + * For reference, the original PC1 permutation is + * + * Left half 57 49 41 33 25 17 9 + * 1 58 50 42 34 26 18 + * 10 2 59 51 43 35 27 + * 19 11 3 60 52 44 36 + * + * Right half 63 55 47 39 31 23 15 + * 7 62 54 46 38 30 22 + * 14 6 61 53 45 37 29 + * 21 13 5 28 20 12 4 + * + * The network below implements this pretty directly; the two 28-bit halves + * end up in the least significant bits of the two output words; the parity + * bits, which are formally discarded, end up in the top 4 bits of each + * half in some random order, and are finally masked off so that they don't + * interfere with the rotation below. (I did an exhaustive search, and + * there are no better Beneš networks.) + */ - permute(pc1, x, y, ka); - x = ka[0]; y = ka[1]; + SWIZZLE_2(x, y, 1, 0x55005401, 0x55005500); + SWIZZLE_2(x, y, 2, 0x32320101, 0x33330000); + TWIZZLE_0(x, y, 0xf0e1f0f1); + SWIZZLE_2(x, y, 4, 0x0f0e0f0f, 0x08050201); + SWIZZLE_2(x, y, 8, 0x005a003a, 0x005a005a); + SWIZZLE_2(x, y, 16, 0x00007c6c, 0x000023cc); + TWIZZLE_0(x, y, 0x20f1e0f0); + SWIZZLE_2(x, y, 2, 0x10000333, 0x33201013); + SWIZZLE_2(x, y, 1, 0x10055005, 0x10455005); + x &= 0x0fffffff; y &= 0x0fffffff; /* --- Now for the key schedule proper --- */ for (i = 0; i < 16; i++) { - if (v[i] == 1) { + if (r[i] == 1) { x = ((x << 1) | (x >> 27)) & 0x0fffffff; y = ((y << 1) | (y >> 27)) & 0x0fffffff; } else { x = ((x << 2) | (x >> 26)) & 0x0fffffff; y = ((y << 2) | (y >> 26)) & 0x0fffffff; } - permute(pc2, x, y, kp); - kp += 2; + + /* --- Apply PC2, which is another Beneš network --- * + * + * The original permutation is described as follows. + * + * S-box 1: 14 17 11 24 1 5 + * S-box 2: 3 28 15 6 21 10 + * S-box 3: 23 19 12 4 26 8 + * S-box 4: 16 7 27 20 13 2 + * S-box 5: 41 52 31 37 47 55 + * S-box 6: 30 40 51 45 33 48 + * S-box 7: 44 49 39 56 34 53 + * S-box 8: 46 42 50 36 29 32 + * + * Firstly, note the way that the key bits are arranged in the words @x@ + * and @y@: viewed from the way DES numbers bits from the most- + * significant end down, there are four padding bits in positions 1--4, + * and another four in positions 33--36. Because the bits in the left- + * hand half of the key all feed into the first four S-boxes, we must + * adjust the bit positions by 4; and we must adjust the positions of the + * bits in the right-hand half by 8. + * + * Secondly, this isn't how we want to apply the key. The formal + * description of DES includes an `expansion' %$E$%: essentially, we take + * each chunk of four bits in the 32-bit half block, and glue on the + * nearest bits from the preceding and following chunk to make a six-bit + * chunk, which we then XOR with six bits of key and feed into the S-box + * to collapse back down to four bits. We avoid having to do this in + * practice by doing the S-boxes in two steps: first, the even-numbered + * ones and then the odd-numbered ones. Because these two collections of + * S-boxes don't involve overlapping input bits, we can just XOR in the + * correct key bits and apply the substitution. There's one more little + * problem, which is that the input to the final S-box needs the topmost + * bit of the input half-block, which we handle by having previously + * rotated the message block left by one position. And that's the + * permutation that we implement here. + * + * There are too many blank spaces to search exhaustively for an optimal + * network. Based on my experience with PC1, I don't expect the optimal + * network to be significantly better than this one. + */ + + u = x; v = y; + SWIZZLE_2(u, v, 1, 0x10551050, 0x05500504); + SWIZZLE_2(u, v, 2, 0x12131230, 0x33102201); + SWIZZLE_2(u, v, 8, 0x00a200ec, 0x009100ba); + SWIZZLE_2(u, v, 16, 0x000012ab, 0x000028e0); + SWIZZLE_2(u, v, 4, 0x0a090805, 0x0b040002); + TWIZZLE_0(u, v, 0x33856c2a); + SWIZZLE_2(u, v, 16, 0x00003385, 0x00004c6a); + SWIZZLE_2(u, v, 8, 0x001500c8, 0x004700e8); + SWIZZLE_2(u, v, 2, 0x20130212, 0x00310022); + SWIZZLE_2(u, v, 1, 0x05404145, 0x54510510); + kp[0] = u; kp[1] = v; kp += 2; } + +#undef REGWD } /* --- @des_eblk@, @des_dblk@ --- *