Cryptography-Digest Digest #780, Volume #9 Sat, 26 Jun 99 01:13:02 EDT
Contents:
Re: IDEA-128 (BORIS KAZAK)
----------------------------------------------------------------------------
From: BORIS KAZAK <[EMAIL PROTECTED]>
Subject: Re: IDEA-128
Date: Fri, 25 Jun 1999 21:39:38 -0400
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
>
> Casey Sybrandy <[EMAIL PROTECTED]> wrote, in part:
>
> >That's it. Decryption is done similarly to normal IDEA, you just have
> >to take into account the different operations. The reasoning behind
> >this is simple: the reversible multiplications of IDEA, where all
> >multiplication was done mod 2^16 + 1, had to be replaced with something
> >more reversible. I selected the keyed rotate function because it has
> >been proven to work well with multiplications and it is simple.
>
> I just came across something similar: the cipher Akelarre. But
> apparently it had some problems.
>
> John Savard ( teneerf<- )
> http://members.xoom.com/quadibloc/crypto.htm
=============================
If you are interested in 128-bit block size IDEA, here is a working
model which is much closer to original design, it uses multiplication
(mod 2^32+1).
*************************************************************
"A naive variation might double the block size.
The algorithm (IDEA) would work just as well with
32-bit sub-blocks instead of 16-bit sub-blocks
and
a 256-bit key. Encryption would be quicker and
security would increase 2^32 times. Or would it?
The theory behind the algorithm hinges on the
fact
that 2^16 + 1 is a prime, 2^32 + 1 is not.
Perhaps
the algorithm could be modified to work, but it
would have very different security properties.
Lai says it would be difficult to make it
work..."
(B. Schneier "Applied Cryptography" 2-nd ed.
p.325)
Let's say that I was naive...
**************************************************************
From the point of view of encryption modular multiplication is just
equivalent to the S-box with the corresponding number of entries. It
maps
the input subblock to the output subblock of the same size (16 or 32
bits).
The inverse transformation must be always possible, otherwise the
subblock
will become undecryptable.
However, 2^32 + 1 is a composite number, equal to 641 x 6700417,
and
there are 32-bit numbers which have no multiplicative inverses
(multiples
of 641 or of 6700417). There are not a lot of numbers like this, but
they
exist, and the algorithm must have an automatic way to avoid those.
The situation has another aspect. In 8 full rounds of IDEA only 34
multipliers are used for encryption. Thus if it would be possible to
come
up with the way to set up 34 key-derived long multipliers and 34
inverses,
the algorithm would work with the double block length as easy as with
the
original one.
The premises were as follows. All operations (mod 2^32 + 1).
1. If a 32-bit number is repeatedly multiplied by itself,
yielding
consecutive powers (mod 2^32 + 1), this process cannot go forever.
(The number must be relatively prime to 2^32 + 1). After a certain
number of multiplications the product will become equal to 1, and
then the whole cycle will repeat. This is a 200-year old fact, due
to Euler, and the maximum possible length of the loop is equal to
the
least common multiple of (641 - 1) and (6700417 - 1). This common
multiple is 33502080.
2. The actual length of the loop can be a fraction of the
maximum
possible, depending on the initial starting number (in future
discussion
this number will be called SEED).
3. If the length of the loop is N, then SEED^N = 1. Also it
follows
that SEED^(N-1) * SEED = 1, consequently SEED^(N-1) and SEED are
multiplicative inverses of one another, same is true for SEED^(N-2)
and
SEED^2, for SEED^(N-3) and SEED^3, and so on. Interesting enough,
SEED^(N/2) is its own multiplicative inverse, just like 1.
4. The necessary multipliers can be set up as powers of an
appropriately chosen SEED, where the 16-bit subkeys will determine
the
power to raise the SEED. Inverses can be set up in the same way.
Finding the necessary numbers turned out to be easy. I stopped
after
finding 4 appropriate values for SEED, although probably could find a
dozen
more without effort. Here are the numbers and inverses.
SEED INVERSE
0x6A5F92D5 0xB28409BC
0x25E6D746 0xC9868267
0x8B34DD6A 0x3EB4FD73
0x6A09E667 0x4520A9C6
(this last number pair is especially interesting. The SEED happens to be
the first 8 hex digits of SQRT(2), less initial 1, the use of this
number
will dispel any suspicions about a "trap door" built into SEED).
From now on everything was clear. Each of the above numbers
produces a
33502080 long cycle of its powers, the same is true for inverses. It is
sufficient to take the 16-bit IDEA subkey, raise the SEED to the
corresponding
power, raise the INVERSE to the same power, and "lo and behold!", here
are
two fully functional modular multipliers, derived from the key and ready
to be
used for encryption and decryption.
Practically it turned out that computations could be done very fast
if
"fundamental" powers of SEED and INVERSE were precomputed and arranged
into a table.
The algorithm works on the 128-bit block divided into 4 32-bit
subblocks.
The sequence of operations is the same as in the original IDEA, the
number of
rounds can be made variable by redefining the constant ROUNDS.
Key scheduling is different from original IDEA. It uses the same
modular
multiplication and the same SEED to produce a randomized stream of
subkeys. This
program will accept any length of key up to 64 bytes, in the posted
version the
constant MAXKEY is #defined as 7, limiting the length of the user key to
7
characters (56 bytes), in order to comply with the USA export
restrictions.
Any ANSI-compliant version of C will compile this program. The
short
"main" is used for illustration of the program functioning.
No attempt was made to optimize the program in any way. It is
intended to
serve as a working model, not as a racing car.
/********************** Start of code *****************************/
/* idea_128.h */
#include <stdio.h>
#include <time.h>
#include <process.h>
#include <io.h>
#include <string.h>
#include <conio.h>
#define IDEABLOCKSIZE 16
#define byte unsigned char
#define word16 unsigned int
#define word32 unsigned long int
#define ROUNDS 8
#define MAXKEY 7 /* Compliance with 56-bit export requirements */
#define SUBKEYBYTES (16*ROUNDS+12)
#define LO 0x0000FFFFUL
#define HI 0xFFFF0000UL
#define SEED 0x6A09E667UL /* Modular Multiplier seed */
/* First 8 hex digits of SQRT(2), less initial 1 */
#define INVERSE 0x4520A9C6UL /* corresponding inverse MOD 2^32+1 */
/* Powers of SEED and INVERSE will be used */
#define low16(x) ((x) & 0xffff)
#define DEBUG
/*IDEA Algorithm functions */
void MasterBooze ( int );
void Idea_set_key (void);
void cipher_idea(word32 in[],word32 out[],word32 subkey[]);
word32 Mul(word32 a,word32 b);
/*global vars*/
word32 enckey[6*ROUNDS+4],deckey[6*ROUNDS+4]; /* Actual IDEA_128 subkeys
*/
byte key[64]; /* This will hold the user key. */
byte ss[SUBKEYBYTES]; /* This will hold the subkey bytes */
/******************************************************/
/* IDEA_128.C
C source code for IDEA_128 block cipher.
IDEA (International Data Encryption Algorithm),
formerly known as IPES (Improved Proposed Encryption Standard).
Algorithm developed by Xuejia Lai and James L. Massey, of ETH Zurich.
This implementation modified and derived from original C code
developed by Xuejia Lai. Zero-based indexing added, key scheduling
uses the same modular multiplication algorithm mod(2^32+1).
Plaintext bytes and subkey bytes are rearranged so that result must be
independent of the native byte ordering of the processor.
The main() used here as illustration reads the key
from the input string, and encrypts-decrypts two plaintext
blocks. The first block consists of all 0-s, the second
block has 1 in the 4-th plaintext byte.
Plaintext, ciphertext, and decrypted plaintext are shown
on screen if DEBUG is #defined.
Also shown are the user key with padding up to 64 bytes
and the hash of the key, which is subsequently used for the
derivation of subkey bytes.
This code is explicitly and irrevocably placed into public domain
starting from January, 20, 1999 */
#include "idea_128.h"
static word32 Mul_Power[16] =
{
0x6A09E667UL, 0x22AF0A42UL, 0x89F2429CUL, 0xADEF9E84UL,
0x4E717789UL, 0x22B9502FUL, 0x7455A930UL, 0x14D2AB03UL,
0x797769F4UL, 0x1B0FF6B4UL, 0xCBFA0F88UL, 0x640AAF5DUL,
0xAC4BEE57UL, 0xF8E9C2C8UL, 0xB23DFD6AUL, 0xAB446C7BUL
}; /* SEED^1, SEED^2, SEED^4,...,SEED^(2^15), all MOD(2^32 + 1) */
static word32 Inv_Power[16] =
{
0x4520A9C6UL, 0x8B6C6575UL, 0x84FEA367UL, 0x9B98BDA7UL,
0x9E3DB228UL, 0x613B6F79UL, 0x1F620EEBUL, 0x52F1A68DUL,
0x3AF576DCUL, 0x5AB367D8UL, 0x220CE382UL, 0xA1D860F0UL,
0x3363002FUL, 0xD4097046UL, 0x5689B0D8UL, 0xC418E961UL
}; /* INVERSE^1, INVERSE^2,...,INVERSE^(2^15), all MOD(2^32 + 1) */
word32 Mul (word32 x, word32 y)
/* Returns (x * y) mod (2^32+1)
For the purposes of this algorithm 0 = 2^32 */
/* Modular Multiplication "CORRECT BUT SLOW" mod 2^32+1
If your compiler does not handle the "double long"
integers (64 bit), you have to split the 32-bit words
into 16-bit halves, multiply them, then juggle the
intermediate products until you get the correct result.
*/
{
word32 t[6]; word16 u[2], v[2];
if (x == 0) return (1 - y);
if (y == 0) return (1 - x);
u[0] = x & LO; v[0] = y & LO;
u[1] = (x >> 16) & LO; v[1] = (y >> 16) & LO;
t[0] = (word32) u[0] * (word32) v[0] ;
t[1] = (word32) u[1] * (word32) v[0] ;
t[2] = (word32) u[0] * (word32) v[1] ;
t[3] = (word32) u[1] * (word32) v[1] ;
/* intermediate 32-bit products */
t[3] = t[3] + ((t[1] >> 16) & LO)
+ ((t[2] >> 16) & LO);
/* no overflow possible here */
t[1] = (t[1] & LO) + (t[2] & LO)
+ ((t[0] >> 16) & LO);
/* collect them all in t[1]. Overflow into the
17-th bit possible here */
t[0] = (t[0] & LO) + ((t[1] << 16) & HI);
t[3] = t[3] + ((t[1] >> 16) & LO); /* add eventual overflow */
return (t[0] - t[3] + (t[3] > t[0]));
} /* Mul */
#define MUL(x,y) (x=Mul(x,y))
void Make_2_Multi ( word16 source, word32 *mul, word32 *inv )
{
word16 mulpower;
int k;
mulpower = source; /* This is the integer power to which SEED
and INVERSE are
raised */
*mul = SEED; *inv = INVERSE;
/* Initialize multiplier and inverse */
for (k = 0; k < 16; k++)
{
if ((mulpower & 0x0001) == 1)
{ *mul = Mul(*mul, Mul_Power[k]);
*inv = Mul(*inv, Inv_Power[k]);
} /* Contribute to the multipliers */
mulpower = mulpower/2; /* Get the next bit of source */
}
} /* Make_2_Multi */
void DissH1( word32 H, byte *D )
/*
Disassemble the given word32 into 4 bytes.
We want it to work on all kinds of machines,
Little-Endian or Big-Endian.
*/
{
word32 T ;
T = H ;
*D++ = ((T & 0xff000000UL) >> 24) ;
*D++ = ((T & 0x00ff0000UL) >> 16) ;
*D++ = ((T & 0x0000ff00UL) >> 8) ;
*D = (T & 0x000000ffUL) ;
}
word32 MakeH1( byte *B )
/*
Assemble a word32 from the four bytes provided.
We want it to work on all kinds of machines,
Little-Endian or Big-Endian.
*/
{
word32 RetVal, temp ;
temp = *B++ ;
RetVal = (temp << 24) ;
temp = *B++ ;
RetVal += (temp << 16) ;
temp = *B++ ;
RetVal += (temp << 8) ;
RetVal += *B ;
return RetVal ;
}
void Idea_set_key (void)
{
int i, source; /* "source" is the power to raise the SEED */
word32 temp; /* this will keep the unneeded multiplicative inverse */
for (i = 0; i <= ROUNDS; i++)
{
source = (word16) ss[16*i]*256 + (word16) ss[16*i + 1];
Make_2_Multi(source, (enckey+6*i),
(deckey+6*(ROUNDS-i)));
/* set up mul
and inv */
enckey[6*i + 1] = MakeH1(ss+16*i + 2);
enckey[6*i + 2] = MakeH1(ss+16*i + 6);
/* set up 2
additives */
if((i > 0) && (i < ROUNDS))
{
deckey[6*(ROUNDS - i) + 1] = -enckey[6*i + 2];
deckey[6*(ROUNDS - i) + 2] = -enckey[6*i + 1];
} /* flip the order of 2 inverses for inner
rounds */
else
{
deckey[6*(ROUNDS - i) + 1] = -enckey[6*i + 1];
deckey[6*(ROUNDS - i) + 2] = -enckey[6*i + 2];
} /* straight order for 1-st and last round */
source = (word16) ss[16*i + 10]*256 + (word16) ss[16*i + 11];
Make_2_Multi(source, (enckey+6*i+3), (deckey+6*(ROUNDS-i)+3));
/* set up mul and inv */
if (i < ROUNDS)
{ /* These 2 multipliers are not needed for the last round
*/
source = (word16) ss[16*i + 12]*256 + (word16) ss[16*i
+ 13];
Make_2_Multi(source, (enckey+6*i+4), &temp);
source = (word16) ss[16*i + 14]*256 + (word16) ss[16*i
+ 15];
Make_2_Multi(source, (enckey+6*i+5), &temp);
/* last 2 muls are used directly
without inversion */
deckey[6*(ROUNDS-i-1) + 4] = enckey[6*i + 4];
deckey[6*(ROUNDS-i-1) + 5] = enckey[6*i + 5];
}
}
}
static void cipher_idea(word32 in[4],word32 out[4],word32 subkey[])
{
word32 x1,x2,x3,x4,t1,t2;
int r=ROUNDS;
x1=*in++; x2=*in++;
x3=*in++; x4=*in;
do
{
MUL(x1,*subkey++);
x2+=*subkey++;
x3+=*subkey++;
MUL(x4,*subkey++);
t2=x1^x3;
MUL(t2,*subkey++);
t1=t2+(x2^x4);
MUL(t1,*subkey++);
t2=t1+t2;
x1^=t1;
x4^=t2;
t2^=x2;
x2=x3^t1;
x3=t2;
} while (--r);
MUL(x1,*subkey++);
*out++=x1;
*out++=(x3+*subkey++);
*out++=(x2+*subkey++);
MUL(x4,*subkey);
*out=x4;
}
void Idea_Encrypt (byte pt[], byte ct[])
{
int i;
word32 text[4];
for (i = 0; i < 4 ; i++) text[i] = MakeH1(pt + 4*i);
/* Assemble 4 32-bit words for encryption */
#ifdef DEBUG
printf("plain= %08lx %08lx %08lx %08lx
\n",text[0],text[1],text[2],text[3]);
#endif /* DEBUG */
cipher_idea ( text, text, enckey);
#ifdef DEBUG
printf("cipher= %08lx %08lx %08lx %08lx
\n",text[0],text[1],text[2],text[3]);
#endif /* DEBUG */
for (i = 0; i < 4 ; i++) DissH1(text[i], (ct + 4*i));
/* Forward encrypted bytes to where they belong */
}
void Idea_Decrypt (byte ct[], byte pt[])
{
int i;
word32 text[4];
for (i = 0; i < 4 ; i++) text[i] = MakeH1(ct + 4*i);
/* Assemble 4 32-bit words for decryption */
#ifdef DEBUG
printf("cipher= %08lx %08lx %08lx %08lx
\n",text[0],text[1],text[2],text[3]);
#endif /* DEBUG */
cipher_idea ( text, text, deckey);
#ifdef DEBUG
printf("plain= %08lx %08lx %08lx %08lx
\n",text[0],text[1],text[2],text[3]);
#endif /* DEBUG */
for (i = 0; i < 4 ; i++) DissH1(text[i], (pt + 4*i));
/* Forward decrypted bytes to where they belong */
}
/* Here is the procedure for Subkey generation.
It uses the same modular multiplication mod(2^32+1) and
the same SEED = 0x6A09E667 in order to generate necessary
subkey bytes.
First cycle of modular multiplication is needed to compute the
"hash" of the key together with padding, this makes every one
of the subkeys dependent of every bit of the key.
During the computation of subkeys, index is circular mod 64.
Variables:
key[64] - unsigned character array, contains the user key.
(Compiler grumbles about "mixing pointers to
different CHAR types" - disregard)
ff[64] - function F[n], contains the user key and padding
(if the external user key is shorter than 64 bytes,
it is padded with bytes 0x01, 0x02, 0x03 and so on,
as many as needed to make the total equal to 64 bytes)
ss[SUBKEYBYTES] - unsigned character array, contains subkeys
(size of this array is at the discretion of the
programmer, constant SUBKEYBYTES must be defined somewhere)
*/
void MasterBooze ( l ) /* This subroutine needs the length of the
keystring, */
/* it uses the global variables key[] and ss[] for input and output
*/
{
int k,m;
word32 temp1, temp2;
unsigned char ff[64]; /* This will contain the key */
for (m=0; m < l; m++) ff[m] = key[m]; /* copying the user key until */
/* "l" bytes are copied */
for (k=0; (m+k)<64; k++) ff[m+k] = k+1; /* padding the key with
1,2,3... */
#ifdef DEBUG
printf("\nkey =");
for(k=0; k<64 ; k++)
{
printf("%2x",ff[k]);
if(k==31) printf("\n ");
}
#endif /* DEBUG */
/* computing key
hash */
for (k=0; k<64; k+= 2)
{
temp2 = ff[k % 64] ; /* Essenntially this procedure */
temp1 = (temp2 << 24) ; /* is identical to MakeH2 function */
temp2 = ff[(k+1) % 64] ; /* However, it is impossible to use */
temp1 += (temp2 << 16) ; /* MakeH2 function directly, because */
temp2 = ff[(k+2) % 64] ; /* the index must be wrapped mod 64, */
temp1 += (temp2 << 8) ; /* which is not provided in MakeH2 */
temp1 += ff[(k+3) % 64] ;
MUL(temp1, SEED); /* Get the modular product into "temp1" */
ff[k % 64] = ((temp1 & 0xff000000UL) >> 24) ;
ff[(k+1) % 64] = ((temp1 & 0x00ff0000UL) >> 16) ;
ff[(k+2) % 64] = ((temp1 & 0x0000ff00UL) >> 8) ;
ff[(k+3) % 64] = (temp1 & 0x000000ffUL) ;
/* Return the bytes where
they belong */
}
#ifdef DEBUG
printf("\nhash =");
for (k=0; k<64; k++)
{
printf("%02x", ff[k]);
if(k==31) printf("\n ");
}
printf("\n");
#endif
/* Now that the hashed key is computed, the same routine
is used to produce the actual subkey bytes */
for (k=0; k<SUBKEYBYTES; k+= 2)
{
temp2 = ff[k % 64] ; /* Essenntially this procedure */
temp1 = (temp2 << 24) ; /* is identical to MakeH2 function */
temp2 = ff[(k+1) % 64] ; /* However, it is impossible to use */
temp1 += (temp2 << 16) ; /* MakeH2 function directly, because */
temp2 = ff[(k+2) % 64] ; /* the index must be wrapped mod 64, */
temp1 += (temp2 << 8) ; /* which is not provided in MakeH2 */
temp1 += ff[(k+3) % 64] ;
MUL(temp1, SEED); /* Get the modular product into "temp1" */
ff[k % 64] = ((temp1 & 0xff000000UL) >> 24) ;
ff[(k+1) % 64] = ((temp1 & 0x00ff0000UL) >> 16) ;
ff[(k+2) % 64] = ((temp1 & 0x0000ff00UL) >> 8) ;
ff[(k+3) % 64] = (temp1 & 0x000000ffUL) ;
/* Return the bytes where
they belong */
ss[k] = ff[k % 64]; /* subkey byte */
ss[k + 1] = ff[(k+1) % 64]; /* one more subkey byte */
}
} /* MasterBooze */
void main ()
{
int k;
byte pt[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, ct[16];
/* plaintext and
ciphertext */
printf ("\n Enter your password:");
gets(key);
k = strlen(key);
if (k > MAXKEY)
{
printf("\n The key contains more than %i characters.",MAXKEY);
printf("\n Excess characters will be truncated.");
k = MAXKEY; key[k] = 0;
} /* Compliance with export requirements */
MasterBooze( k );
/* These lines are for testing "idea_128" */
Idea_set_key ();
printf ("\n");
Idea_Encrypt ( pt, ct );
Idea_Decrypt ( ct, pt );
pt[4] = 1;
printf ("\n");
Idea_Encrypt ( pt, ct );
Idea_Decrypt ( ct, pt );
} /* main */
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
