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

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