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

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