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