Amiga ISO Collection

home *** CD-ROM | disk | FTP | other *** search

/ Amiga ISO Collection / AmigaUtilCD1.iso / Disk&HD / DCN-DP12.LHA / DiskProtection / Docs / IDEA.doc < prev

Wrap

Text File | 1995-05-07 | 12.8 KB | 304 lines

IDEA ABPs IDEA implementation for XPK Version 1.00 Copyright 1992 André Beck License/Disclaimer ------------------ This library may be freely distributed with the XPK compression package, as long as it is kept in its original, complete, and unmodified form. It may not be distributed by itself or in a commercial package of any kind without my permission and the permission of the originators of the International Data Encryption Algorithm, see section Patent. This program 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. Patent ------ IDEA is registered as the international patent WO 91/18459 "Device for Converting a Digital Block and the Use thereof". For commercial use of IDEA, one should contact ASCOM TECH AG Freiburgstrasse 370 CH-3018 Bern, Switzerland Description ----------- IDEA is an XPK packer sublibrary which implements a highly optimized form of the IDEA encryption algorithm. IDEA (International Data Encryption Algorithm) is a block cipher developed by Xuejia Lai and Prof. Dr. J. L. Massey at the Swiss Federal Institute of Technology. See patent for information on any commercial use of this algorithm. Especially, this library is not only claimed by the copyright of the author and the copyright of the author of the used IDEA kernal routine, but by the copyright of the IDEA originators and their patent, too. This implementation of the algorithm was done by André Beck, Dept. of Computer Science, Technical University of Dresden, Germany. xpkIDEA.library gives a chunk based access to the most common encryption methods, using the IDEA cipher as the encryption function. The IDEA cipher is known to be somewhat slow. It performs 34 multiplications modulo 2^16+1 for every 64 bit data packet, so it must have limited performance on a plain 68000 processor. This library uses the heavily hand optimized, permuted, macrotized and partially unrolled 68000 assembler implementation of IDEA by Colin Plumb. Therefore, the kernal IDEA routine and it's macros are copyright by Colin Plumb. In difference to the most wide spread compressors distributed with XPK, one should know something about IDEA before using it. First, IDEA is completely no compressor, it only encrypts or decrypts data. A password must be specified with first calls to "pack" or "unpack" a chunk. Furthermore, the password given on encryption MUST restore the original chunk contents, otherwise the password will be treated as incorrect. This is a tribute to the XPK architecture and it's safety, but has the disadvantage of preventing you from doing things like a triple crypt, what means to first encrypt a chunk with password 1, then decrypting it with password 2 and last encrypting it with password 3, all three passwords different. Encryption Methods ------------------ IDEA is a cipher used for encryption in this library, what means it is a function taking one data block and an encryption key as input and producing one data block as output. The purpose of this function is to generate a very random result from normaly highly redundant input, in other words to make White Noise of bits from a regular, low entropic bit stream. The IDEA data blocks are sized 64 bits, where the key has 128 bits in it's unexpanded form (DES has a key of 56 bits). One now may use this function in different ways. The simplest encryption is to take the input chunk block by block, driving it through the IDEA function, and building the output chunk from the result. This mode is called Electronic Code Book (ECB). But an Code Book based encryption is not the state of the art, because it is somewhat easy to crack (even ECB using IDEA is not easy to crack, only a bit easier than the following modes). One can imagine, that including the chunks contents (which is to be crypted) itself into the encryption will be much safer. Consider a simple ECB to encrypt text, generated by the function out_character = (in_character + 1) MODULO num_of_characters. This is nothing other than incrementing every character, f.i. making A to B, F to G and Z back to A. So the word FOOBAR will be crypted to GPPCBS, and nobody will see what it is on the first visit. But there are also people called Cryptologists, and cracking such codes is their job. Simple methods of cracking are especially based on the probability of characters in different languages. They know e is a very often found letter in indo european languages, and if they find one character very often in the crypted text, this one may be an e. If it's sure that it's an e, one can insert it in the complete crypted text where the cracked character was. The method to prevent such simple cracks is based on chaining the produced output back into the crypt function with some delay. Consider out_character = ((in_character + last_out_char)+1) MODULO num_characters with an initial last out character of 'C'. FOOBAR gets JAQTVL using this code and nobody can see that an double O was in the input. So it's more complicated to crack messages crypted with this code, because one MUST start at the beginning of the text. It's also possible to increase the number of ,,states of remember'' we are using, for instance by not using the last_out_char but the seventh_last_out_char and using 7 different initial values for them. The method used above is very similar to a common encryption method called Cipher Block Chaining (CBC) with one state of remember (CBC 1). The difference to ECB in schematic view: ECB electronic code book mode y[i] = IDEA(z, x[i]) x[i] = IIDEA(z, y[i]) CBC cipher block chaining mode y[i] = IDEA(z, x[i] ^ y[i-N]) x[i] = IIDEA(z, y[i]) ^ y[i-N] with x[i] is the input block number i y[i] is the output block number i z is the encryption key N is the number of states of remember (at least one) IDEA is the encryption function using the IDEA cipher IIDEA is the corresponding decryption function ^ means the XOR of the operands (Bitwise Exclusive Or) There are two additional modes often used with encryption. See the following schematics: CFB ciphertext feedback mode y[i] = x[i] ^ IDEA(z, y[i-N]) x[i] = y[i] ^ IDEA(z, y[i-N]) OFB output feedback mode h[i] = IDEA(z, h[i-N]) y[i] = x[i] ^ h[i] x[i] = y[i] ^ h[i] As you see, all the chaining modes have additional parameters determining the result of the crypt. Not only the key determines the resulting chunk for a special input chunk, but also the number of states of remember used by the mode and the values used to initialize the states (in CBC 1 coding block #0, you need block #[i-1], but you have no block #-1, so you have to give some initial value for it). For CBC 8 you have to give 8 initailizers, and so on. The xpkIDEA implementation uses the following XPK modes for different encryption methods: XPK Mode Encr. Method Nr. States 68030/25 68000/7.14 -------- ------------ ---------- -------- ---------- 0..25 ECB / 90 K/s 12 K/s -------------------------------------------------------------------------- 26 CFB 1 . . . 87 K/s 11 K/s . . . 50 CFB 25 -------------------------------------------------------------------------- 51 OFB 1 . . . 84 K/s 11 K/s . . . 75 OFB 25 -------------------------------------------------------------------------- 76 CBC 1 . . . 84 K/s 11 K/s . . . 100 CBC 25 -------------------------------------------------------------------------- As you see, the modes were ordered to somehow match the scheme given by the most XPK packers, with 0..100 mapped to increasing efficiency and decreasing speed. There are neither big differences in speed nor in efficiency of the used modes, and the mapping used is easy to remember. Especially one gets very simple from the mode used to the encr. method and state number by subsequent subtractions of 25 from the mode: IDEA.79 -> 79 - (3*25) = 4 , so mode 3 (CBC) with 4 states applies. The default method used when no mode is explicitely given is CBC1, i.e. the mode IDEA.76 The presented speed (in KByte/second) is not very exact. This is mainly caused by the varying cycle count of the 68000's mul instruction. The encryption will be faster with the all-zero-key and slower with the all-ones-key. Try around with key values #0 #5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a #ffffffffffffffffffffffffffffffff to see the differences. Not only IDEA.100 is a very safe encryption, also IDEA.75 and IDEA.50 may be good for safe results. They are modes with 25 states, so one may give 25 (!) different initializers to the password, which must all be known to get this decrypted again. The code is developed in a way that no speed loss will occure even using much states. At the other hand, a open connection with this sublibrary for packing or unpacking forces the allocation of around 600 bytes of memory. If you are low on memory, the library may return a matching error condition. The Password ------------ You may ask now, how to give different initializers to the encryption modes which use them ? Therefore, the password parsing routine within this library is more complicated than normal ones. An IDEA password consists of the key value and a optional set of initializers, both specified either as a plain ascii string to be hashed or as the explicite hexadecimal value. The syntax is as follows: <password> ::= <keyspec>[<initializer>]*. <keyspec> ::= <valuespec>. <initializer> ::= ":"<valuespec>. <valuespec> ::= [<charstring>|<hexstring>]. <charstring> ::= ["!".."~"]*. <hexstring> ::= "#"["0".."9"|"a".."f"|"A".."F"]*. so possible passwords are f.i.: password password:heut:ist:montag #738494ad53ae2c1b736218ac12abaacc:nix:hexa:oder:doch:#4455663311223311 : <-- this results in the all-zero-key. passwd::::ini4 <-- initializers 1..3 are zero Its useless to specify any initializers with ECB Its useless to specify more then N initializers for mode [CBC|CFB|OFB] N The maximum number of initializers is 25 charstrings may have any number of characters hexvalues for keyspec have to fit in an OCTAWORD. (16 Byte) hexvalues for initializers must fit in a QUADWORD. (8 Byte) unspecified values (key/initializers) are zero. If you don't initialize a value, it will be zero. Any syntactic or semantic error in the password specification will raise the error XPKERR_WRONGPW. The '#' character is used to introduce hex values because many shells would missinterpret $ even if it appears in doublequotes. The hash routine currently used in this password parser is not very strong. String passwords should be at least 12 characters long to give a nice key. Technical Info -------------- This lib is completely written in assembler using a68k and the 1.3 includes. It was developed within around 10 hours of work distributed over more than 14 days (better to say nights). The author could only test it on an 1 Meg chip no fast 7.14MHz 68000 A500 under Kickstart 1.3. The source is now around 30000 bytes and may contain some bogus. If you find any bugs report them to me via the email address given below. Make sure the output buffer is at least the size of the input buffer plus XPK_MARGIN, even if this is on decompression more then the original chunk size. This library relies on this behavior, which is correctly done by xpkmaster. As already stated in the section Disclaimer, the author gives no warranties for the proper function of this software. Additional, he cannot give any guarantee that IDEA itself is a useful encryption standard. It SEEMS to be very strong, but it's still under analyzation by some organizations like the NSA and similars. If you are interested in the theoretics of this algorithm, ask me for some hints. Version History --------------- 1.00 ( 5-Aug-92 ) First public release. Contact Address --------------- See section Patent for information on how to reach the authors of the IDEA cipher. The following mail address applies only until March '93. You will reach the author of this library there: beck@freia.inf.tu-dresden.de If you want to get in contact with the author of the fast idea routine used within this library, contact Mr. Colin Plumb at: colin@eecg.toronto.edu