tools: Fix option parsing for gpg-zip.
[gnupg.git] / cipher / idea.c
1 /* idea.c  -  IDEA function
2  *      Copyright (c) 1997, 1998, 1999, 2001 by Werner Koch (dd9jn)
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining a
5  * copy of this software and associated documentation files (the "Software"),
6  * to deal in the Software without restriction, including without limitation
7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8  * and/or sell copies of the Software, and to permit persons to whom the
9  * Software is furnished to do so, subject to the following conditions:
10  *
11  * The above copyright notice and this permission notice shall be included in
12  * all copies or substantial portions of the Software.
13  *
14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
17  * WERNER KOCH BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
18  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20  *
21  * Except as contained in this notice, the name of Werner Koch shall not be
22  * used in advertising or otherwise to promote the sale, use or other dealings
23  * in this Software without prior written authorization from Werner Koch.
24  *
25  * Patents on IDEA have expired:
26  *   Europe: EP0482154 on 2011-05-16,
27  *   Japan:  JP3225440 on 2011-05-16,
28  *   U.S.:   5,214,703 on 2012-01-07.
29  */
30
31 /*
32  * Please see http://www.noepatents.org/ to learn why software patents
33  * are bad for society and what you can do to fight them.
34  *
35  * The code herein is based on the one from:
36  *   Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
37  *   ISBN 0-471-11709-9.
38  */
39
40
41 #include <config.h>
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <assert.h>
46
47 #include "types.h"  /* for byte and u32 typedefs */
48 #include "util.h"
49 #include "errors.h"
50 #include "algorithms.h"
51
52
53 #define FNCCAST_SETKEY(f)  ((int(*)(void*, byte*, unsigned int))(f))
54 #define FNCCAST_CRYPT(f)   ((void(*)(void*, byte*, byte*))(f))
55
56 #define CIPHER_ALGO_IDEA         1
57
58 #define IDEA_KEYSIZE 16
59 #define IDEA_BLOCKSIZE 8
60 #define IDEA_ROUNDS 8
61 #define IDEA_KEYLEN (6*IDEA_ROUNDS+4)
62
63 typedef struct {
64     u16 ek[IDEA_KEYLEN];
65     u16 dk[IDEA_KEYLEN];
66     int have_dk;
67 } IDEA_context;
68
69 static const char *selftest(void);
70
71 static void
72 burn_stack (int bytes)
73 {
74     char buf[64];
75
76     wipememory(buf,sizeof buf);
77     bytes -= sizeof buf;
78     if (bytes > 0)
79         burn_stack (bytes);
80 }
81
82
83 static u16
84 mul_inv( u16 x )
85 {
86     u16 t0, t1;
87     u16 q, y;
88
89     if( x < 2 )
90         return x;
91     t1 = 0x10001L / x;
92     y =  0x10001L % x;
93     if( y == 1 )
94         return (1-t1) & 0xffff;
95
96     t0 = 1;
97     do {
98         q = x / y;
99         x = x % y;
100         t0 += q * t1;
101         if( x == 1 )
102             return t0;
103         q = y / x;
104         y = y % x;
105         t1 += q * t0;
106     } while( y != 1 );
107     return (1-t1) & 0xffff;
108 }
109
110
111
112 static void
113 expand_key( const byte *userkey, u16 *ek )
114 {
115     int i,j;
116
117     for(j=0; j < 8; j++ ) {
118         ek[j] = (*userkey << 8) + userkey[1];
119         userkey += 2;
120     }
121     for(i=0; j < IDEA_KEYLEN; j++ ) {
122         i++;
123         ek[i+7] = ek[i&7] << 9 | ek[(i+1)&7] >> 7;
124         ek += i & 8;
125         i &= 7;
126     }
127 }
128
129
130 static void
131 invert_key( u16 *ek, u16 dk[IDEA_KEYLEN] )
132 {
133     int i;
134     u16 t1, t2, t3;
135     u16 temp[IDEA_KEYLEN];
136     u16 *p = temp + IDEA_KEYLEN;
137
138     t1 = mul_inv( *ek++ );
139     t2 = -*ek++;
140     t3 = -*ek++;
141     *--p = mul_inv( *ek++ );
142     *--p = t3;
143     *--p = t2;
144     *--p = t1;
145
146     for(i=0; i < IDEA_ROUNDS-1; i++ ) {
147         t1 = *ek++;
148         *--p = *ek++;
149         *--p = t1;
150
151         t1 = mul_inv( *ek++ );
152         t2 = -*ek++;
153         t3 = -*ek++;
154         *--p = mul_inv( *ek++ );
155         *--p = t2;
156         *--p = t3;
157         *--p = t1;
158     }
159     t1 = *ek++;
160     *--p = *ek++;
161     *--p = t1;
162
163     t1 = mul_inv( *ek++ );
164     t2 = -*ek++;
165     t3 = -*ek++;
166     *--p = mul_inv( *ek++ );
167     *--p = t3;
168     *--p = t2;
169     *--p = t1;
170     memcpy(dk, temp, sizeof(temp) );
171     wipememory(temp, sizeof(temp) );  /* burn temp */
172 }
173
174
175 static void
176 cipher( byte *outbuf, const byte *inbuf, u16 *key )
177 {
178     u16 x1, x2, x3,x4, s2, s3;
179     u16 *in, *out;
180     int r = IDEA_ROUNDS;
181 #define MUL(x,y)                                    \
182         do {u16 _t16; u32 _t32;                     \
183             if( (_t16 = (y)) ) {                    \
184                 if( (x = (x)&0xffff) ) {            \
185                     _t32 = (u32)x * _t16;           \
186                     x = _t32 & 0xffff;              \
187                     _t16 = _t32 >> 16;              \
188                     x = ((x)-_t16) + (x<_t16?1:0);  \
189                 }                                   \
190                 else {                              \
191                     x = 1 - _t16;                   \
192                 }                                   \
193             }                                       \
194             else {                                  \
195                 x = 1 - x;                          \
196             }                                       \
197         } while(0)
198
199     in = (u16*)inbuf;
200     x1 = *in++;
201     x2 = *in++;
202     x3 = *in++;
203     x4 = *in;
204 #ifndef BIG_ENDIAN_HOST
205     x1 = (x1>>8) | (x1<<8);
206     x2 = (x2>>8) | (x2<<8);
207     x3 = (x3>>8) | (x3<<8);
208     x4 = (x4>>8) | (x4<<8);
209 #endif
210     do {
211         MUL(x1, *key++);
212         x2 += *key++;
213         x3 += *key++;
214         MUL(x4, *key++ );
215
216         s3 = x3;
217         x3 ^= x1;
218         MUL(x3, *key++);
219         s2 = x2;
220         x2 ^=x4;
221         x2 += x3;
222         MUL(x2, *key++);
223         x3 += x2;
224
225         x1 ^= x2;
226         x4 ^= x3;
227
228         x2 ^= s3;
229         x3 ^= s2;
230     } while( --r );
231     MUL(x1, *key++);
232     x3 += *key++;
233     x2 += *key++;
234     MUL(x4, *key);
235
236     out = (u16*)outbuf;
237 #ifndef BIG_ENDIAN_HOST
238     *out++ = (x1>>8) | (x1<<8);
239     *out++ = (x3>>8) | (x3<<8);
240     *out++ = (x2>>8) | (x2<<8);
241     *out   = (x4>>8) | (x4<<8);
242 #else
243     *out++ = x1;
244     *out++ = x3;
245     *out++ = x2;
246     *out   = x4;
247 #endif
248 #undef MUL
249 }
250
251
252 static int
253 do_setkey( IDEA_context *c, const byte *key, unsigned int keylen )
254 {
255     static int initialized = 0;
256     static const char *selftest_failed = 0;
257
258     if( !initialized ) {
259         initialized = 1;
260         selftest_failed = selftest();
261         if( selftest_failed )
262             log_error( "%s\n", selftest_failed );
263     }
264     if( selftest_failed )
265         return G10ERR_SELFTEST_FAILED;
266
267     assert(keylen == 16);
268     c->have_dk = 0;
269     expand_key( key, c->ek );
270     invert_key( c->ek, c->dk );
271     return 0;
272 }
273
274 static int
275 idea_setkey (void *context, const byte *key, unsigned int keylen)
276 {
277     IDEA_context *ctx = context;
278     int rc = do_setkey (ctx, key, keylen);
279     burn_stack (23+6*sizeof(void*));
280     return rc;
281 }
282
283 static void
284 encrypt_block( IDEA_context *c, byte *outbuf, const byte *inbuf )
285 {
286     cipher( outbuf, inbuf, c->ek );
287 }
288
289 static void
290 idea_encrypt (void *context, byte *out, const byte *in)
291 {
292     IDEA_context *ctx = context;
293     encrypt_block (ctx, out, in);
294     burn_stack (24+3*sizeof (void*));
295 }
296
297 static void
298 decrypt_block( IDEA_context *c, byte *outbuf, const byte *inbuf )
299 {
300     if( !c->have_dk ) {
301        c->have_dk = 1;
302        invert_key( c->ek, c->dk );
303     }
304     cipher( outbuf, inbuf, c->dk );
305 }
306
307 static void
308 idea_decrypt (void *context, byte *out, const byte *in)
309 {
310     IDEA_context *ctx = context;
311     decrypt_block (ctx, out, in);
312     burn_stack (24+3*sizeof (void*));
313 }
314
315
316 static const char *
317 selftest( void )
318 {
319 static struct {
320     byte key[16];
321     byte plain[8];
322     byte cipher[8];
323 } test_vectors[] = {
324     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
325         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
326       { 0x00, 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03 },
327       { 0x11, 0xFB, 0xED, 0x2B, 0x01, 0x98, 0x6D, 0xE5 } },
328     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
329         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
330       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
331       { 0x54, 0x0E, 0x5F, 0xEA, 0x18, 0xC2, 0xF8, 0xB1 } },
332     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
333         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
334       { 0x00, 0x19, 0x32, 0x4B, 0x64, 0x7D, 0x96, 0xAF },
335       { 0x9F, 0x0A, 0x0A, 0xB6, 0xE1, 0x0C, 0xED, 0x78 } },
336     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
337         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
338       { 0xF5, 0x20, 0x2D, 0x5B, 0x9C, 0x67, 0x1B, 0x08 },
339       { 0xCF, 0x18, 0xFD, 0x73, 0x55, 0xE2, 0xC5, 0xC5 } },
340     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
341         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
342       { 0xFA, 0xE6, 0xD2, 0xBE, 0xAA, 0x96, 0x82, 0x6E },
343       { 0x85, 0xDF, 0x52, 0x00, 0x56, 0x08, 0x19, 0x3D } },
344     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
345         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
346       { 0x0A, 0x14, 0x1E, 0x28, 0x32, 0x3C, 0x46, 0x50 },
347       { 0x2F, 0x7D, 0xE7, 0x50, 0x21, 0x2F, 0xB7, 0x34 } },
348     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
349         0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
350       { 0x05, 0x0A, 0x0F, 0x14, 0x19, 0x1E, 0x23, 0x28 },
351       { 0x7B, 0x73, 0x14, 0x92, 0x5D, 0xE5, 0x9C, 0x09 } },
352     { { 0x00, 0x05, 0x00, 0x0A, 0x00, 0x0F, 0x00, 0x14,
353         0x00, 0x19, 0x00, 0x1E, 0x00, 0x23, 0x00, 0x28 },
354       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
355       { 0x3E, 0xC0, 0x47, 0x80, 0xBE, 0xFF, 0x6E, 0x20 } },
356     { { 0x3A, 0x98, 0x4E, 0x20, 0x00, 0x19, 0x5D, 0xB3,
357         0x2E, 0xE5, 0x01, 0xC8, 0xC4, 0x7C, 0xEA, 0x60 },
358       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
359       { 0x97, 0xBC, 0xD8, 0x20, 0x07, 0x80, 0xDA, 0x86 } },
360     { { 0x00, 0x64, 0x00, 0xC8, 0x01, 0x2C, 0x01, 0x90,
361         0x01, 0xF4, 0x02, 0x58, 0x02, 0xBC, 0x03, 0x20 },
362       { 0x05, 0x32, 0x0A, 0x64, 0x14, 0xC8, 0x19, 0xFA },
363       { 0x65, 0xBE, 0x87, 0xE7, 0xA2, 0x53, 0x8A, 0xED } },
364     { { 0x9D, 0x40, 0x75, 0xC1, 0x03, 0xBC, 0x32, 0x2A,
365         0xFB, 0x03, 0xE7, 0xBE, 0x6A, 0xB3, 0x00, 0x06 },
366       { 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 },
367       { 0xF5, 0xDB, 0x1A, 0xC4, 0x5E, 0x5E, 0xF9, 0xF9 } }
368 };
369     IDEA_context c;
370     byte buffer[8];
371     int i;
372
373     for(i=0; i < DIM(test_vectors); i++ ) {
374         do_setkey( &c, test_vectors[i].key, 16 );
375         encrypt_block( &c, buffer, test_vectors[i].plain );
376         if( memcmp( buffer, test_vectors[i].cipher, 8 ) )
377             return "IDEA test encryption failed.";
378         decrypt_block( &c, buffer, test_vectors[i].cipher );
379         if( memcmp( buffer, test_vectors[i].plain, 8 ) )
380             return "IDEA test decryption failed.";
381     }
382
383     return NULL;
384 }
385
386
387 /****************
388  * Return some information about the algorithm.  We need algo here to
389  * distinguish different flavors of the algorithm.
390  * Returns: A pointer to string describing the algorithm or NULL if
391  *          the ALGO is invalid.
392  */
393 const char *
394 idea_get_info( int algo, size_t *keylen,
395                size_t *blocksize, size_t *contextsize,
396                int (**r_setkey)( void *c, const byte *key, unsigned keylen ),
397                void (**r_encrypt)( void *c, byte *outbuf, const byte *inbuf ),
398                void (**r_decrypt)( void *c, byte *outbuf, const byte *inbuf )
399                )
400 {
401     *keylen      = 128;
402     *blocksize   = IDEA_BLOCKSIZE;
403     *contextsize = sizeof(IDEA_context);
404     *r_setkey    = idea_setkey;
405     *r_encrypt   = idea_encrypt;
406     *r_decrypt   = idea_decrypt;
407
408     if( algo == CIPHER_ALGO_IDEA )
409         return "IDEA";
410     return NULL;
411 }