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

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