chiark - git - mdw - catacomb/blob - symm/idea.c

   1 /* -*-c-*-
   2  *
   3  * Implementation of the IDEA cipher
   4  *
   5  * (c) 1999 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <assert.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <mLib/bits.h>
  36
  37 #include "blkc.h"
  38 #include "gcipher.h"
  39 #include "idea.h"
  40
  41 /*----- Global variables --------------------------------------------------*/
  42
  43 const octet idea_keysz[] = { KSZ_SET, IDEA_KEYSZ };
  44
  45 /*----- Main code ---------------------------------------------------------*/
  46
  47 /* --- @inv@ --- *
  48  *
  49  * Arguments:   @uint16 n@ = number to invert
  50  *
  51  * Returns:     Multiplicative inverse of @n@ %$\pmod{2^{16} + 1}$%.
  52  *
  53  * Use:         Computes multiplicative inverses.  This is handy for the
  54  *              decryption key scheduling.
  55  */
  56
  57 static uint16 inv(uint16 n)
  58 {
  59   uint32 m = 0x10001;
  60   uint32 a = 1, b = 0;
  61   uint32 nn = n;
  62
  63   if (!nn)
  64     nn = 0x10000;
  65   for (;;) {
  66     uint32 q, r, t;
  67     if (!(r = m % nn))
  68       break;
  69     q = m / nn;
  70     m = nn; nn = r;
  71     t = a; a = b - q * a; b = t;
  72   }
  73   if (a > MASK16)
  74     a += 1;
  75   return (U16(a));
  76 }
  77
  78 /* --- @MUL@ --- *
  79  *
  80  * Arguments @x@ and @y@ are two 32-bit values to multiply.  On exit, @x@ is
  81  * the product of the two arguments.  The result is not normalized back to 16
  82  * bits; the arguments are not expected to be normalized.
  83  *
  84  * This code is from `Side Channel Attack Hardening of the IDEA Cipher',
  85  * published by Ascom Tech.
  86  */
  87
  88 #define MUL(x, y) do {                                                  \
  89   unsigned _t;                                                          \
  90   uint32 _tt;                                                           \
  91                                                                         \
  92   x = U16(x - 1);                                                       \
  93   _t = U16(y - 1);                                                      \
  94   _tt = (uint32)x * (uint32)_t + (uint32)x + (uint32)_t + 1;            \
  95   x = U16(_tt);                                                         \
  96   _t = U16(_tt >> 16);                                                  \
  97   x = x - _t + (x <= _t);                                               \
  98 } while (0)
  99
 100 /* --- @idea_init@ --- *
 101  *
 102  * Arguments:   @idea_ctx *k@ = pointer to key block
 103  *              @const void *buf@ = pointer to key buffer
 104  *              @size_t sz@ = size of key material
 105  *
 106  * Returns:     ---
 107  *
 108  * Use:         Initializes an IDEA key buffer.  The buffer must be exactly
 109  *              16 bytes in size, because IDEA is only defined with a key
 110  *              size of 128 bits.
 111  */
 112
 113 void idea_init(idea_ctx *k, const void *buf, size_t sz)
 114 {
 115   KSZ_ASSERT(idea, sz);
 116
 117   /* --- Unpack the encryption key --- */
 118
 119   {
 120     const octet *p = buf;
 121     uint16 *q = k->e;
 122     uint32 a = LOAD32(p +  0);
 123     uint32 b = LOAD32(p +  4);
 124     uint32 c = LOAD32(p +  8);
 125     uint32 d = LOAD32(p + 12);
 126     int i;
 127
 128     /* --- Main unpacking loop --- */
 129
 130     for (i = 0; i < 6; i++) {
 131
 132       /* --- Spit out the next 8 subkeys --- */
 133
 134       q[0] = U16(a >> 16);
 135       q[1] = U16(a >>  0);
 136       q[2] = U16(b >> 16);
 137       q[3] = U16(b >>  0);
 138       q[4] = U16(c >> 16);
 139       q[5] = U16(c >>  0);
 140       q[6] = U16(d >> 16);
 141       q[7] = U16(d >>  0);
 142       q += 8;
 143
 144       /* --- Rotate and permute the subkeys --- */
 145
 146       {
 147         uint32 t = a;
 148         a = U32((a << 25) | (b >> 7));
 149         b = U32((b << 25) | (c >> 7));
 150         c = U32((c << 25) | (d >> 7));
 151         d = U32((d << 25) | (t >> 7));
 152       }
 153     }
 154
 155     /* --- Write out the tail-enders --- */
 156
 157     q[0] = U16(a >> 16);
 158     q[1] = U16(a >>  0);
 159     q[2] = U16(b >> 16);
 160     q[3] = U16(b >>  0);
 161   }
 162
 163   /* --- Convert this into the decryption key --- */
 164
 165   {
 166     uint16 *p = k->e + 52;
 167     uint16 *q = k->d;
 168     int i;
 169
 170     /* --- Translate the main round keys --- */
 171
 172     for (i = 0; i < 8; i++) {
 173       p -= 6;
 174       q[4] = p[0];
 175       q[5] = p[1];
 176       q[0] = inv(p[2]);
 177       q[3] = inv(p[5]);
 178       if (i) {
 179         q[1] = 0x10000 - p[4];
 180         q[2] = 0x10000 - p[3];
 181       } else {
 182         q[1] = 0x10000 - p[3];
 183         q[2] = 0x10000 - p[4];
 184       }
 185       q += 6;
 186     }
 187
 188     /* --- Translate the tail-enders --- */
 189
 190     p -= 4;
 191     q[0] = inv(p[0]);
 192     q[1] = 0x10000 - p[1];
 193     q[2] = 0x10000 - p[2];
 194     q[3] = inv(p[3]);
 195   }
 196 }
 197
 198 /* --- @ROUND@ --- */
 199
 200 #define MIX(k, a, b, c, d) do {                                         \
 201   MUL(a, k[0]);                                                         \
 202   b += k[1];                                                            \
 203   c += k[2];                                                            \
 204   MUL(d, k[3]);                                                         \
 205 } while (0)
 206
 207 #define MA(k, a, b, c, d) do {                                          \
 208   unsigned _u = a ^ c;                                                  \
 209   unsigned _v = b ^ d;                                                  \
 210   MUL(_u, k[4]);                                                        \
 211   _v += _u;                                                             \
 212   MUL(_v, k[5]);                                                        \
 213   _u += _v;                                                             \
 214   a ^= _v;                                                              \
 215   b ^= _u;                                                              \
 216   c ^= _v;                                                              \
 217   d ^= _u;                                                              \
 218 } while (0);
 219
 220 #define ROUND(k, a, b, c, d) do {                                       \
 221   MIX(k, a, b, c, d);                                                   \
 222   MA(k, a, b, c, d);                                                    \
 223   (k) += 6;                                                             \
 224 } while (0)
 225
 226 /* --- Encryption --- */
 227
 228 #define EBLK(k, a, b, c, d) do {                                        \
 229   unsigned _a = U16(a >> 16);                                           \
 230   unsigned _b = U16(a >>  0);                                           \
 231   unsigned _c = U16(b >> 16);                                           \
 232   unsigned _d = U16(b >>  0);                                           \
 233   const uint16 *_k = (k);                                               \
 234                                                                         \
 235   ROUND(_k, _a, _b, _c, _d);                                            \
 236   ROUND(_k, _a, _c, _b, _d);                                            \
 237   ROUND(_k, _a, _b, _c, _d);                                            \
 238   ROUND(_k, _a, _c, _b, _d);                                            \
 239   ROUND(_k, _a, _b, _c, _d);                                            \
 240   ROUND(_k, _a, _c, _b, _d);                                            \
 241   ROUND(_k, _a, _b, _c, _d);                                            \
 242   ROUND(_k, _a, _c, _b, _d);                                            \
 243   MIX  (_k, _a, _c, _b, _d);                                            \
 244   c = ((uint32)U16(_a) << 16) | (uint32)U16(_c);                        \
 245   d = ((uint32)U16(_b) << 16) | (uint32)U16(_d);                        \
 246 } while (0)
 247
 248 #define DBLK(k, a, b) EBLK((k), (a), (b))
 249
 250 /* --- @idea_eblk@, @idea_dblk@ --- *
 251  *
 252  * Arguments:   @const idea_ctx *k@ = pointer to a key block
 253  *              @const uint32 s[2]@ = pointer to source block
 254  *              @uint32 d[2]@ = pointer to destination block
 255  *
 256  * Returns:     ---
 257  *
 258  * Use:         Low-level block encryption and decryption.
 259  */
 260
 261 void idea_eblk(const idea_ctx *k, const uint32 *s, uint32 *d)
 262 {
 263   EBLK(k->e, s[0], s[1], d[0], d[1]);
 264 }
 265
 266 void idea_dblk(const idea_ctx *k, const uint32 *s, uint32 *d)
 267 {
 268   EBLK(k->d, s[0], s[1], d[0], d[1]);
 269 }
 270
 271 BLKC_TEST(IDEA, idea)
 272
 273 /*----- That's all, folks -------------------------------------------------*/