[FFmpeg-devel] [PATCH] DES en-/decryption
Reimar Döffinger
Reimar.Doeffinger
Sat Oct 13 22:15:42 CEST 2007
Hello,
some DES implementation is needed for asf decryption support.
This version, compared to the one contained in the previous asf patch,
should be quite a bit faster (not benchmarked though).
If you think this is not optimized well enough to belong in libavutil I
tend to suggest to leave it in libavformat unless someone else is
interested in improving it.
I am interested in hearing your comments either way.
Btw.: this code would allow for the S_boxes_P_shuffle table to be
generated at compile time, which is an approach I would greatly prefer,
but I don't know how to implement this in a non-messy way.
If any of the "Makefile-guys" have some time, maybe you could see if you
can come up with something? I'd expect this could be used in some other
code as well (I hope others agree this would be nice).
Greetings,
Reimar D?ffinger
-------------- next part --------------
Index: libavutil/Makefile
===================================================================
--- libavutil/Makefile (revision 10723)
+++ libavutil/Makefile (working copy)
@@ -4,6 +4,7 @@
aes.o \
base64.o \
crc.o \
+ des.o \
intfloat_readwrite.o \
fifo.o \
lls.o \
Index: libavutil/des.c
===================================================================
--- libavutil/des.c (revision 0)
+++ libavutil/des.c (revision 0)
@@ -0,0 +1,337 @@
+#include <inttypes.h>
+#include "des.h"
+
+#define T(a, b, c, d, e, f, g, h) 64-a,64-b,64-c,64-d,64-e,64-f,64-g,64-h
+static const uint8_t IP_shuffle[] = {
+ T(58, 50, 42, 34, 26, 18, 10, 2),
+ T(60, 52, 44, 36, 28, 20, 12, 4),
+ T(62, 54, 46, 38, 30, 22, 14, 6),
+ T(64, 56, 48, 40, 32, 24, 16, 8),
+ T(57, 49, 41, 33, 25, 17, 9, 1),
+ T(59, 51, 43, 35, 27, 19, 11, 3),
+ T(61, 53, 45, 37, 29, 21, 13, 5),
+ T(63, 55, 47, 39, 31, 23, 15, 7)
+};
+#undef T
+
+#define T(a, b, c, d, e, f) 32-a,32-b,32-c,32-d,32-e,32-f
+static const uint8_t E_shuffle[] = {
+ T(32, 1, 2, 3, 4, 5),
+ T( 4, 5, 6, 7, 8, 9),
+ T( 8, 9, 10, 11, 12, 13),
+ T(12, 13, 14, 15, 16, 17),
+ T(16, 17, 18, 19, 20, 21),
+ T(20, 21, 22, 23, 24, 25),
+ T(24, 25, 26, 27, 28, 29),
+ T(28, 29, 30, 31, 32, 1)
+};
+#undef T
+
+#define T(a, b, c, d) 32-a,32-b,32-c,32-d
+static const uint8_t P_shuffle[] = {
+ T(16, 7, 20, 21),
+ T(29, 12, 28, 17),
+ T( 1, 15, 23, 26),
+ T( 5, 18, 31, 10),
+ T( 2, 8, 24, 14),
+ T(32, 27, 3, 9),
+ T(19, 13, 30, 6),
+ T(22, 11, 4, 25)
+};
+#undef T
+
+#define T(a, b, c, d, e, f, g) 64-a,64-b,64-c,64-d,64-e,64-f,64-g
+static const uint8_t PC1_shuffle[] = {
+ T(57, 49, 41, 33, 25, 17, 9),
+ T( 1, 58, 50, 42, 34, 26, 18),
+ T(10, 2, 59, 51, 43, 35, 27),
+ T(19, 11, 3, 60, 52, 44, 36),
+ T(63, 55, 47, 39, 31, 23, 15),
+ T( 7, 62, 54, 46, 38, 30, 22),
+ T(14, 6, 61, 53, 45, 37, 29),
+ T(21, 13, 5, 28, 20, 12, 4)
+};
+#undef T
+
+#define T(a, b, c, d, e, f) 56-a,56-b,56-c,56-d,56-e,56-f
+static const uint8_t PC2_shuffle[] = {
+ T(14, 17, 11, 24, 1, 5),
+ T( 3, 28, 15, 6, 21, 10),
+ T(23, 19, 12, 4, 26, 8),
+ T(16, 7, 27, 20, 13, 2),
+ T(41, 52, 31, 37, 47, 55),
+ T(30, 40, 51, 45, 33, 48),
+ T(44, 49, 39, 56, 34, 53),
+ T(46, 42, 50, 36, 29, 32)
+};
+#undef T
+
+#ifdef CONFIG_SMALL
+static const uint8_t S_boxes[8][32] = {
+ {
+ 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18, 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
+ 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b, 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
+ }, {
+ 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4, 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
+ 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21, 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
+ }, {
+ 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5, 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
+ 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70, 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
+ }, {
+ 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a, 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
+ 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d, 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
+ }, {
+ 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16, 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
+ 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8, 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
+ }, {
+ 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58, 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
+ 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3, 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
+ }, {
+ 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad, 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
+ 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e, 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
+ }, {
+ 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41, 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
+ 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2, 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
+ }
+};
+#else
+/**
+ * This table contains the results of applying both the S-box and P-shuffle.
+ * It can be regenerated by compiling this file with -DCONFIG_SMALL -DTEST -DGENTABLES
+ */
+static const uint32_t S_boxes_P_shuffle[8][64] = {
+ {
+ 0x00808200, 0x00000000, 0x00008000, 0x00808202, 0x00808002, 0x00008202, 0x00000002, 0x00008000,
+ 0x00000200, 0x00808200, 0x00808202, 0x00000200, 0x00800202, 0x00808002, 0x00800000, 0x00000002,
+ 0x00000202, 0x00800200, 0x00800200, 0x00008200, 0x00008200, 0x00808000, 0x00808000, 0x00800202,
+ 0x00008002, 0x00800002, 0x00800002, 0x00008002, 0x00000000, 0x00000202, 0x00008202, 0x00800000,
+ 0x00008000, 0x00808202, 0x00000002, 0x00808000, 0x00808200, 0x00800000, 0x00800000, 0x00000200,
+ 0x00808002, 0x00008000, 0x00008200, 0x00800002, 0x00000200, 0x00000002, 0x00800202, 0x00008202,
+ 0x00808202, 0x00008002, 0x00808000, 0x00800202, 0x00800002, 0x00000202, 0x00008202, 0x00808200,
+ 0x00000202, 0x00800200, 0x00800200, 0x00000000, 0x00008002, 0x00008200, 0x00000000, 0x00808002,
+ },
+ {
+ 0x40084010, 0x40004000, 0x00004000, 0x00084010, 0x00080000, 0x00000010, 0x40080010, 0x40004010,
+ 0x40000010, 0x40084010, 0x40084000, 0x40000000, 0x40004000, 0x00080000, 0x00000010, 0x40080010,
+ 0x00084000, 0x00080010, 0x40004010, 0x00000000, 0x40000000, 0x00004000, 0x00084010, 0x40080000,
+ 0x00080010, 0x40000010, 0x00000000, 0x00084000, 0x00004010, 0x40084000, 0x40080000, 0x00004010,
+ 0x00000000, 0x00084010, 0x40080010, 0x00080000, 0x40004010, 0x40080000, 0x40084000, 0x00004000,
+ 0x40080000, 0x40004000, 0x00000010, 0x40084010, 0x00084010, 0x00000010, 0x00004000, 0x40000000,
+ 0x00004010, 0x40084000, 0x00080000, 0x40000010, 0x00080010, 0x40004010, 0x40000010, 0x00080010,
+ 0x00084000, 0x00000000, 0x40004000, 0x00004010, 0x40000000, 0x40080010, 0x40084010, 0x00084000,
+ },
+ {
+ 0x00000104, 0x04010100, 0x00000000, 0x04010004, 0x04000100, 0x00000000, 0x00010104, 0x04000100,
+ 0x00010004, 0x04000004, 0x04000004, 0x00010000, 0x04010104, 0x00010004, 0x04010000, 0x00000104,
+ 0x04000000, 0x00000004, 0x04010100, 0x00000100, 0x00010100, 0x04010000, 0x04010004, 0x00010104,
+ 0x04000104, 0x00010100, 0x00010000, 0x04000104, 0x00000004, 0x04010104, 0x00000100, 0x04000000,
+ 0x04010100, 0x04000000, 0x00010004, 0x00000104, 0x00010000, 0x04010100, 0x04000100, 0x00000000,
+ 0x00000100, 0x00010004, 0x04010104, 0x04000100, 0x04000004, 0x00000100, 0x00000000, 0x04010004,
+ 0x04000104, 0x00010000, 0x04000000, 0x04010104, 0x00000004, 0x00010104, 0x00010100, 0x04000004,
+ 0x04010000, 0x04000104, 0x00000104, 0x04010000, 0x00010104, 0x00000004, 0x04010004, 0x00010100,
+ },
+ {
+ 0x80401000, 0x80001040, 0x80001040, 0x00000040, 0x00401040, 0x80400040, 0x80400000, 0x80001000,
+ 0x00000000, 0x00401000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00400040, 0x80400000,
+ 0x80000000, 0x00001000, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x80001000, 0x00001040,
+ 0x80400040, 0x80000000, 0x00001040, 0x00400040, 0x00001000, 0x00401040, 0x80401040, 0x80000040,
+ 0x00400040, 0x80400000, 0x00401000, 0x80401040, 0x80000040, 0x00000000, 0x00000000, 0x00401000,
+ 0x00001040, 0x00400040, 0x80400040, 0x80000000, 0x80401000, 0x80001040, 0x80001040, 0x00000040,
+ 0x80401040, 0x80000040, 0x80000000, 0x00001000, 0x80400000, 0x80001000, 0x00401040, 0x80400040,
+ 0x80001000, 0x00001040, 0x00400000, 0x80401000, 0x00000040, 0x00400000, 0x00001000, 0x00401040,
+ },
+ {
+ 0x00000080, 0x01040080, 0x01040000, 0x21000080, 0x00040000, 0x00000080, 0x20000000, 0x01040000,
+ 0x20040080, 0x00040000, 0x01000080, 0x20040080, 0x21000080, 0x21040000, 0x00040080, 0x20000000,
+ 0x01000000, 0x20040000, 0x20040000, 0x00000000, 0x20000080, 0x21040080, 0x21040080, 0x01000080,
+ 0x21040000, 0x20000080, 0x00000000, 0x21000000, 0x01040080, 0x01000000, 0x21000000, 0x00040080,
+ 0x00040000, 0x21000080, 0x00000080, 0x01000000, 0x20000000, 0x01040000, 0x21000080, 0x20040080,
+ 0x01000080, 0x20000000, 0x21040000, 0x01040080, 0x20040080, 0x00000080, 0x01000000, 0x21040000,
+ 0x21040080, 0x00040080, 0x21000000, 0x21040080, 0x01040000, 0x00000000, 0x20040000, 0x21000000,
+ 0x00040080, 0x01000080, 0x20000080, 0x00040000, 0x00000000, 0x20040000, 0x01040080, 0x20000080,
+ },
+ {
+ 0x10000008, 0x10200000, 0x00002000, 0x10202008, 0x10200000, 0x00000008, 0x10202008, 0x00200000,
+ 0x10002000, 0x00202008, 0x00200000, 0x10000008, 0x00200008, 0x10002000, 0x10000000, 0x00002008,
+ 0x00000000, 0x00200008, 0x10002008, 0x00002000, 0x00202000, 0x10002008, 0x00000008, 0x10200008,
+ 0x10200008, 0x00000000, 0x00202008, 0x10202000, 0x00002008, 0x00202000, 0x10202000, 0x10000000,
+ 0x10002000, 0x00000008, 0x10200008, 0x00202000, 0x10202008, 0x00200000, 0x00002008, 0x10000008,
+ 0x00200000, 0x10002000, 0x10000000, 0x00002008, 0x10000008, 0x10202008, 0x00202000, 0x10200000,
+ 0x00202008, 0x10202000, 0x00000000, 0x10200008, 0x00000008, 0x00002000, 0x10200000, 0x00202008,
+ 0x00002000, 0x00200008, 0x10002008, 0x00000000, 0x10202000, 0x10000000, 0x00200008, 0x10002008,
+ },
+ {
+ 0x00100000, 0x02100001, 0x02000401, 0x00000000, 0x00000400, 0x02000401, 0x00100401, 0x02100400,
+ 0x02100401, 0x00100000, 0x00000000, 0x02000001, 0x00000001, 0x02000000, 0x02100001, 0x00000401,
+ 0x02000400, 0x00100401, 0x00100001, 0x02000400, 0x02000001, 0x02100000, 0x02100400, 0x00100001,
+ 0x02100000, 0x00000400, 0x00000401, 0x02100401, 0x00100400, 0x00000001, 0x02000000, 0x00100400,
+ 0x02000000, 0x00100400, 0x00100000, 0x02000401, 0x02000401, 0x02100001, 0x02100001, 0x00000001,
+ 0x00100001, 0x02000000, 0x02000400, 0x00100000, 0x02100400, 0x00000401, 0x00100401, 0x02100400,
+ 0x00000401, 0x02000001, 0x02100401, 0x02100000, 0x00100400, 0x00000000, 0x00000001, 0x02100401,
+ 0x00000000, 0x00100401, 0x02100000, 0x00000400, 0x02000001, 0x02000400, 0x00000400, 0x00100001,
+ },
+ {
+ 0x08000820, 0x00000800, 0x00020000, 0x08020820, 0x08000000, 0x08000820, 0x00000020, 0x08000000,
+ 0x00020020, 0x08020000, 0x08020820, 0x00020800, 0x08020800, 0x00020820, 0x00000800, 0x00000020,
+ 0x08020000, 0x08000020, 0x08000800, 0x00000820, 0x00020800, 0x00020020, 0x08020020, 0x08020800,
+ 0x00000820, 0x00000000, 0x00000000, 0x08020020, 0x08000020, 0x08000800, 0x00020820, 0x00020000,
+ 0x00020820, 0x00020000, 0x08020800, 0x00000800, 0x00000020, 0x08020020, 0x00000800, 0x00020820,
+ 0x08000800, 0x00000020, 0x08000020, 0x08020000, 0x08020020, 0x08000000, 0x00020000, 0x08000820,
+ 0x00000000, 0x08020820, 0x00020020, 0x08000020, 0x08020000, 0x08000800, 0x08000820, 0x00000000,
+ 0x08020820, 0x00020800, 0x00020800, 0x00000820, 0x00000820, 0x00020020, 0x08000000, 0x08020800,
+ },
+};
+#endif
+
+static uint64_t shuffle(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
+ int i;
+ uint64_t res = 0;
+ for (i = 0; i < shuffle_len; i++)
+ res = (res << 1) | ((in >> *shuffle++) & 1);
+ return res;
+}
+
+static uint64_t shuffle_inv(uint64_t in, const uint8_t *shuffle, int shuffle_len) {
+ int i;
+ uint64_t res = 0;
+ shuffle += shuffle_len - 1;
+ for (i = 0; i < shuffle_len; i++) {
+ res |= (in & 1) << *shuffle--;
+ in >>= 1;
+ }
+ return res;
+}
+
+static uint32_t f_func(uint32_t r, uint64_t k) {
+ int i;
+ uint32_t out = 0;
+ // expand 32 bit data to 8 * 6 bit blocks
+ uint64_t tmp = shuffle(r, E_shuffle, sizeof(E_shuffle));
+ tmp ^= k;
+ // apply S-boxes, those compress the data again from 8 * 6 to 8 * 4 bits
+#ifdef CONFIG_SMALL
+ for (i = 0; i < 8; i++) {
+ uint32_t v = S_boxes[i][(tmp >> 43) & 0x1f];
+ if (tmp & ((uint64_t)1 << 42)) v >>= 4;
+ else v &= 0x0f;
+ tmp <<= 6;
+ out = (out << 4) | v;
+ }
+ out = shuffle(out, P_shuffle, sizeof(P_shuffle));
+#else
+ for (i = 7; i >= 0; i--) {
+ out |= S_boxes_P_shuffle[i][tmp & 0x3f];
+ tmp >>= 6;
+ }
+#endif
+ return out;
+}
+
+/**
+ * \brief rotate the two halves of the expanded 56 bit key each 1 bit left
+ *
+ * Note: the specification calls this "shift", so I kept it although
+ * it is confusing.
+ */
+static uint64_t key_shift_left(uint64_t CDn) {
+ uint64_t carries = (CDn >> 27) & 0x10000001;
+ CDn <<= 1;
+ CDn &= ~0x10000001;
+ CDn |= carries;
+ return CDn;
+}
+
+/**
+ * \brief rotate the two halves of the expanded 56 bit key each 1 bit right
+ *
+ * Note: the specification calls this "shift", so I kept it although
+ * it is confusing.
+ */
+static uint64_t key_shift_right(uint64_t CDn) {
+ uint64_t carries = (CDn & 0x10000001) << 27;
+ CDn >>= 1;
+ CDn &= ~(0x10000001ULL << 27);
+ CDn |= carries;
+ return CDn;
+}
+
+uint64_t ff_des_encdec(uint64_t in, uint64_t key, int decrypt) {
+ int i;
+ // discard parity bits from key and shuffle it into C and D parts
+ uint64_t CDn = shuffle(key, PC1_shuffle, sizeof(PC1_shuffle));
+ // shuffle irrelevant to security but to ease hardware implementations
+ in = shuffle(in, IP_shuffle, sizeof(IP_shuffle));
+ for (i = 0; i < 16; i++) {
+ uint64_t Kn;
+ uint32_t f_res;
+ if (!decrypt) {
+ CDn = key_shift_left(CDn);
+ if (i > 1 && i != 8 && i != 15)
+ CDn = key_shift_left(CDn);
+ }
+ Kn = shuffle(CDn, PC2_shuffle, sizeof(PC2_shuffle));
+ f_res = f_func(in, Kn);
+ in = (in << 32) | (in >> 32);
+ in ^= f_res;
+ if (decrypt) {
+ CDn = key_shift_right(CDn);
+ if (i != 0 && i != 7 && i < 14)
+ CDn = key_shift_right(CDn);
+ }
+ }
+ in = (in << 32) | (in >> 32);
+ // reverse shuffle used to ease hardware implementations
+ in = shuffle_inv(in, IP_shuffle, sizeof(IP_shuffle));
+ return in;
+}
+
+#ifdef TEST
+#include <stdlib.h>
+#include <stdio.h>
+#include <sys/time.h>
+static uint64_t rand64(void) {
+ uint64_t r = rand();
+ r = (r << 32) | rand();
+ return r;
+}
+
+int main(void) {
+ int i, j;
+ struct timeval tv;
+ uint64_t key;
+ uint64_t data;
+ uint64_t ct;
+ gettimeofday(&tv, NULL);
+ srand(tv.tv_sec * 1000 * 1000 + tv.tv_usec);
+ key = 0x123456789abcdef0ULL;
+ data = 0xfedcba9876543210ULL;
+ if (ff_des_encdec(data, key, 0) != 0x4ab65b3d4b061518ULL) {
+ printf("Test 1 failed\n");
+ return 1;
+ }
+ key = rand64();
+ data = rand64();
+ ct = ff_des_encdec(data, key, 0);
+ if (ff_des_encdec(ct, key, 1) != data) {
+ printf("Test 2 failed\n");
+ return 1;
+ }
+#ifdef GENTABLES
+ printf("static const uint32_t S_boxes_P_shuffle[8][64] = {\n");
+ for (i = 0; i < 8; i++) {
+ printf(" {");
+ for (j = 0; j < 64; j++) {
+ uint32_t v = S_boxes[i][j >> 1];
+ v = j & 1 ? v >> 4 : v & 0xf;
+ v <<= 28 - 4 * i;
+ v = shuffle(v, P_shuffle, sizeof(P_shuffle));
+ printf((j & 7) == 0 ? "\n " : " ");
+ printf("0x%08X,", v);
+ }
+ printf("\n },\n");
+ }
+ printf("};\n");
+#endif
+ return 0;
+}
+#endif
Index: libavutil/des.h
===================================================================
--- libavutil/des.h (revision 0)
+++ libavutil/des.h (revision 0)
@@ -0,0 +1 @@
+uint64_t ff_des_encdec(uint64_t in, uint64_t key, int decrypt);
More information about the ffmpeg-devel
mailing list