[u/mdw/catacomb] / idea.c

/* -*-c-*-
 *
 * $Id: idea.c,v 1.3 2000/07/02 18:24:39 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.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;

  for (;;) {
    uint32 q, r, t;
    if (!(r = m % n))
      break;
    q = m / n;
    m = n; n = 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 = (U16(_a) << 16) | U16(_c);					\
  d = (U16(_b) << 16) | 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	*
a27430a2	3	* $Id: idea.c,v 1.3 2000/07/02 18:24:39 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 $
a27430a2	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	*
6ced98bd	37	* Revision 1.2 2000/06/17 11:24:08 mdw
	38	* New key size interface.
	39	*
d03ab969	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"
6ced98bd	55	#include "gcipher.h"
d03ab969	56	#include "idea.h"
d03ab969	57
6ced98bd	58	/----- Global variables --------------------------------------------------/
	59
	60	const octet idea_keysz[] = { KSZ_SET, IDEA_KEYSZ };
	61
d03ab969	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.
a27430a2	97	*
	98	* This code is from `Side Channel Attack Hardening of the IDEA Cipher',
	99	* published by Ascom Tech.
d03ab969	100	*/
	101
	102	#define MUL(x, y) do { \
a27430a2	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); \
d03ab969	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	{
6ced98bd	129	KSZ_ASSERT(idea, sz);
d03ab969	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 { \
a27430a2	215	MUL(a, k[0]); \
	216	b += k[1]; \
	217	c += k[2]; \
	218	MUL(d, k[3]); \
d03ab969	219	} while (0)
	220
	221	#define MA(k, a, b, c, d) do { \
a27430a2	222	unsigned _u = a ^ c; \
	223	unsigned _v = b ^ d; \
	224	MUL(_u, k[4]); \
d03ab969	225	_v += _u; \
a27430a2	226	MUL(_v, k[5]); \
d03ab969	227	_u += _v; \
a27430a2	228	a ^= _v; \
	229	b ^= _u; \
	230	c ^= _v; \
	231	d ^= _u; \
d03ab969	232	} while (0);
	233
	234	#define ROUND(k, a, b, c, d) do { \
a27430a2	235	MIX(k, a, b, c, d); \
a27430a2	236	MA(k, a, b, c, d); \
d03ab969	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); \
a27430a2	258	c = (U16(_a) << 16) \| U16(_c); \
a27430a2	259	d = (U16(_b) << 16) \| U16(_d); \
d03ab969	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 -------------------------------------------------/