[u/mdw/catacomb] / idea.c

/* -*-c-*-
 *
 * $Id: idea.c,v 1.4 2000/07/15 17:47:58 mdw Exp $
 *
 * Implementation of the IDEA cipher
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: idea.c,v $
 * Revision 1.4  2000/07/15 17:47:58  mdw
 * Fix bug in decryption key scheduling.
 *
 * Revision 1.3  2000/07/02 18:24:39  mdw
 * Use a new multiplication function from an Ascom white paper to resist
 * timing attacks.
 *
 * Revision 1.2  2000/06/17 11:24:08  mdw
 * New key size interface.
 *
 * Revision 1.1  1999/09/03 08:41:12  mdw
 * Initial import.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mLib/bits.h>

#include "blkc.h"
#include "gcipher.h"
#include "idea.h"

/*----- Global variables --------------------------------------------------*/

const octet idea_keysz[] = { KSZ_SET, IDEA_KEYSZ };

/*----- Main code ---------------------------------------------------------*/

/* --- @inv@ --- *
 *
 * Arguments:	@uint16 n@ = number to invert
 *
 * Returns:	Multiplicative inverse of @n@ %$\pmod{2^{16} + 1}$%.
 *
 * Use:		Computes multiplicative inverses.  This is handy for the
 *		decryption key scheduling.
 */

static uint16 inv(uint16 n)
{
  uint32 m = 0x10001;
  uint32 a = 1, b = 0;
  uint32 nn = n;

  if (!nn)
    nn = 0x10000;
  for (;;) {
    uint32 q, r, t;
    if (!(r = m % nn))
      break;
    q = m / nn;
    m = nn; nn = r;
    t = a; a = b - q * a; b = t;
  }
  if (a > MASK16)
    a += 1;
  return (U16(a));
}

/* --- @MUL@ --- *
 *
 * Arguments @x@ and @y@ are two 32-bit values to multiply.  On exit, @x@ is
 * the product of the two arguments.  The result is not normalized back to 16
 * bits; the arguments are not expected to be normalized.
 *
 * This code is from `Side Channel Attack Hardening of the IDEA Cipher',
 * published by Ascom Tech.
 */

#define MUL(x, y) do {							\
  unsigned _t;								\
  uint32 _tt;								\
									\
  x = U16(x - 1);							\
  _t = U16(y - 1);							\
  _tt = (uint32)x * (uint32)_t + (uint32)x + (uint32)_t + 1;		\
  x = U16(_tt);								\
  _t = U16(_tt >> 16);							\
  x = x - _t + (x <= _t);						\
} while (0)

/* --- @idea_init@ --- *
 *
 * Arguments:	@idea_ctx *k@ = pointer to key block
 *		@const void *buf@ = pointer to key buffer
 *		@size_t sz@ = size of key material
 *
 * Returns:	---
 *
 * Use:		Initializes an IDEA key buffer.  The buffer must be exactly
 *		16 bytes in size, because IDEA is only defined with a key
 *		size of 128 bits.
 */

void idea_init(idea_ctx *k, const void *buf, size_t sz)
{
  KSZ_ASSERT(idea, sz);

  /* --- Unpack the encryption key --- */

  {
    const octet *p = buf;
    uint16 *q = k->e;
    uint32 a = LOAD32(p +  0);
    uint32 b = LOAD32(p +  4);
    uint32 c = LOAD32(p +  8);
    uint32 d = LOAD32(p + 12);
    int i;

    /* --- Main unpacking loop --- */

    for (i = 0; i < 6; i++) {

      /* --- Spit out the next 8 subkeys --- */

      q[0] = U16(a >> 16);
      q[1] = U16(a >>  0);
      q[2] = U16(b >> 16);
      q[3] = U16(b >>  0);
      q[4] = U16(c >> 16);
      q[5] = U16(c >>  0);
      q[6] = U16(d >> 16);
      q[7] = U16(d >>  0);
      q += 8;

      /* --- Rotate and permute the subkeys --- */

      {
	uint32 t = a;
	a = U32((a << 25) | (b >> 7));
	b = U32((b << 25) | (c >> 7));
	c = U32((c << 25) | (d >> 7));
	d = U32((d << 25) | (t >> 7));
      }
    }

    /* --- Write out the tail-enders --- */

    q[0] = U16(a >> 16);
    q[1] = U16(a >>  0);
    q[2] = U16(b >> 16);
    q[3] = U16(b >>  0);
  }

  /* --- Convert this into the decryption key --- */

  {
    uint16 *p = k->e + 52;
    uint16 *q = k->d;
    int i;

    /* --- Translate the main round keys --- */

    for (i = 0; i < 8; i++) {
      p -= 6;
      q[4] = p[0];
      q[5] = p[1];
      q[0] = inv(p[2]);
      q[3] = inv(p[5]);
      if (i) {
	q[1] = 0x10000 - p[4];
	q[2] = 0x10000 - p[3];
      } else {
	q[1] = 0x10000 - p[3];
	q[2] = 0x10000 - p[4];
      }
      q += 6;
    }

    /* --- Translate the tail-enders --- */

    p -= 4;
    q[0] = inv(p[0]);
    q[1] = 0x10000 - p[1];
    q[2] = 0x10000 - p[2];
    q[3] = inv(p[3]);
  }
}

/* --- @ROUND@ --- */

#define MIX(k, a, b, c, d) do {						\
  MUL(a, k[0]);								\
  b += k[1];								\
  c += k[2];								\
  MUL(d, k[3]);								\
} while (0)

#define MA(k, a, b, c, d) do {						\
  unsigned _u = a ^ c;							\
  unsigned _v = b ^ d;							\
  MUL(_u, k[4]);							\
  _v += _u;								\
  MUL(_v, k[5]);							\
  _u += _v;								\
  a ^= _v;								\
  b ^= _u;								\
  c ^= _v;								\
  d ^= _u;								\
} while (0);

#define ROUND(k, a, b, c, d) do {					\
  MIX(k, a, b, c, d);							\
  MA(k, a, b, c, d);							\
  (k) += 6;								\
} while (0)

/* --- Encryption --- */

#define EBLK(k, a, b, c, d) do {					\
  unsigned _a = U16(a >> 16);						\
  unsigned _b = U16(a >>  0);						\
  unsigned _c = U16(b >> 16);						\
  unsigned _d = U16(b >>  0);						\
  const uint16 *_k = (k);						\
									\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  ROUND(_k, _a, _b, _c, _d);						\
  ROUND(_k, _a, _c, _b, _d);						\
  MIX  (_k, _a, _c, _b, _d);						\
  c = ((uint32)U16(_a) << 16) | (uint32)U16(_c);			\
  d = ((uint32)U16(_b) << 16) | (uint32)U16(_d);			\
} while (0)

#define DBLK(k, a, b) EBLK((k), (a), (b))

/* --- @idea_eblk@, @idea_dblk@ --- *
 *
 * Arguments:	@const idea_ctx *k@ = pointer to a key block
 *		@const uint32 s[2]@ = pointer to source block
 *		@uint32 d[2]@ = pointer to destination block
 *
 * Returns:	---
 *
 * Use:		Low-level block encryption and decryption.
 */

void idea_eblk(const idea_ctx *k, const uint32 *s, uint32 *d)
{
  EBLK(k->e, s[0], s[1], d[0], d[1]);
}

void idea_dblk(const idea_ctx *k, const uint32 *s, uint32 *d)
{
  EBLK(k->d, s[0], s[1], d[0], d[1]);
}

BLKC_TEST(IDEA, idea)

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
d03ab969	1	/* --c--
d03ab969	2	*
e4e3ed70	3	* $Id: idea.c,v 1.4 2000/07/15 17:47:58 mdw Exp $
d03ab969	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 $
e4e3ed70	33	* Revision 1.4 2000/07/15 17:47:58 mdw
	34	* Fix bug in decryption key scheduling.
	35	*
a27430a2	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	*
6ced98bd	40	* Revision 1.2 2000/06/17 11:24:08 mdw
	41	* New key size interface.
	42	*
d03ab969	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"
6ced98bd	58	#include "gcipher.h"
d03ab969	59	#include "idea.h"
d03ab969	60
6ced98bd	61	/----- Global variables --------------------------------------------------/
	62
	63	const octet idea_keysz[] = { KSZ_SET, IDEA_KEYSZ };
	64
d03ab969	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;
e4e3ed70	81	uint32 nn = n;
d03ab969	82
e4e3ed70	83	if (!nn)
e4e3ed70	84	nn = 0x10000;
d03ab969	85	for (;;) {
d03ab969	86	uint32 q, r, t;
e4e3ed70	87	if (!(r = m % nn))
d03ab969	88	break;
e4e3ed70	89	q = m / nn;
e4e3ed70	90	m = nn; nn = r;
d03ab969	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.
a27430a2	103	*
	104	* This code is from `Side Channel Attack Hardening of the IDEA Cipher',
	105	* published by Ascom Tech.
d03ab969	106	*/
	107
	108	#define MUL(x, y) do { \
a27430a2	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); \
d03ab969	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	{
6ced98bd	135	KSZ_ASSERT(idea, sz);
d03ab969	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 { \
a27430a2	221	MUL(a, k[0]); \
	222	b += k[1]; \
	223	c += k[2]; \
	224	MUL(d, k[3]); \
d03ab969	225	} while (0)
	226
	227	#define MA(k, a, b, c, d) do { \
a27430a2	228	unsigned _u = a ^ c; \
	229	unsigned _v = b ^ d; \
	230	MUL(_u, k[4]); \
d03ab969	231	_v += _u; \
a27430a2	232	MUL(_v, k[5]); \
d03ab969	233	_u += _v; \
a27430a2	234	a ^= _v; \
	235	b ^= _u; \
	236	c ^= _v; \
	237	d ^= _u; \
d03ab969	238	} while (0);
	239
	240	#define ROUND(k, a, b, c, d) do { \
a27430a2	241	MIX(k, a, b, c, d); \
a27430a2	242	MA(k, a, b, c, d); \
d03ab969	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); \
e4e3ed70	264	c = ((uint32)U16(_a) << 16) \| (uint32)U16(_c); \
e4e3ed70	265	d = ((uint32)U16(_b) << 16) \| (uint32)U16(_d); \
d03ab969	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 -------------------------------------------------/