home *** CD-ROM | disk | FTP | other *** search
/ World of A1200 / World_Of_A1200.iso / programs / compress / misc / xpk / docs / idea.doc < prev    next >
Text File  |  1995-02-27  |  13KB  |  304 lines
  1.                                    IDEA
  2.                      ABPs IDEA implementation for XPK
  3.                                Version 1.00
  4.                          Copyright 1992 André Beck
  5.  
  6.  
  7.                             License/Disclaimer
  8.                             ------------------
  9.  
  10.     This library may be freely distributed with the XPK compression
  11.  package, as long as it is kept in its original, complete, and unmodified
  12.  form.  It may not be distributed by itself or in a commercial package of
  13.   any kind without my permission and the permission of the originators of
  14.      the International Data Encryption Algorithm, see section Patent.
  15.  
  16.     This program is distributed in the hope that it will be useful, but
  17. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18.                    or FITNESS FOR A PARTICULAR PURPOSE.
  19.  
  20.  
  21.                                   Patent
  22.                                   ------
  23.        IDEA is registered as the international patent  WO  91/18459
  24.        "Device for Converting a Digital Block and the Use thereof".
  25.               For commercial use of IDEA, one should contact
  26.  
  27.                                ASCOM TECH AG
  28.                             Freiburgstrasse 370
  29.                          CH-3018 Bern, Switzerland
  30.  
  31.  
  32.  
  33.  
  34.                                 Description
  35.                                 -----------
  36.  
  37.     IDEA is an XPK packer sublibrary which implements a highly optimized
  38. form of the IDEA encryption algorithm.
  39.  
  40. IDEA (International Data Encryption Algorithm)  is  a  block cipher
  41. developed by Xuejia Lai and Prof. Dr. J. L. Massey at the Swiss Federal
  42. Institute of Technology. See patent for information on any commercial
  43. use of this algorithm. Especially, this library is not only claimed by
  44. the copyright of the author and the copyright of the author of the used
  45. IDEA kernal routine, but by the copyright of the IDEA originators and
  46. their patent, too.
  47.  
  48. This implementation of the algorithm was done by André Beck, Dept. of
  49. Computer Science, Technical University of Dresden, Germany.
  50.  
  51. xpkIDEA.library gives a chunk based access to the most common encryption
  52. methods, using the IDEA cipher as the encryption function. The IDEA cipher
  53. is known to be somewhat slow. It performs 34 multiplications modulo 2^16+1
  54. for every 64 bit data packet, so it must have limited performance on a
  55. plain 68000 processor. This library uses the heavily hand optimized,
  56. permuted, macrotized and partially unrolled 68000 assembler implementation
  57. of IDEA by Colin Plumb. Therefore, the kernal IDEA routine and it's
  58. macros are copyright by Colin Plumb.
  59.  
  60. In difference to the most wide spread compressors distributed with XPK, one
  61. should know something about IDEA before using it. First, IDEA is completely
  62. no compressor, it only encrypts or decrypts data. A password must be
  63. specified with first calls to "pack" or "unpack" a chunk. Furthermore, the
  64. password given on encryption MUST restore the original chunk contents,
  65. otherwise the password will be treated as incorrect. This is a tribute
  66. to the XPK architecture and it's safety, but has the disadvantage of
  67. preventing you from doing things like a triple crypt, what means to first
  68. encrypt a chunk with password 1, then decrypting it with password 2 and
  69. last encrypting it with password 3, all three passwords different.
  70.  
  71.                             Encryption Methods
  72.                             ------------------
  73.  
  74.     IDEA is a cipher used for encryption in this library, what means
  75. it is a function taking one data block and an encryption key as input and
  76. producing one data block as output. The purpose of this function is to
  77. generate a very random result from normaly highly redundant input, in other
  78. words to make White Noise of bits from a regular, low entropic bit stream.
  79. The IDEA data blocks are sized 64 bits, where the key has 128 bits in it's
  80. unexpanded form (DES has a key of 56 bits). One now may use this function
  81. in different ways. The simplest encryption is to take the input chunk block
  82. by block, driving it through the IDEA function, and building the output
  83. chunk from the result. This mode is called Electronic Code Book (ECB).
  84. But an Code Book based encryption is not the state of the art, because it
  85. is somewhat easy to crack (even ECB using IDEA is not easy to crack, only
  86. a bit easier than the following modes). One can imagine, that including the
  87. chunks contents (which is to be crypted) itself into the encryption will be
  88. much safer. Consider a simple ECB to encrypt text, generated by the function
  89.  
  90.  out_character = (in_character + 1) MODULO num_of_characters.
  91.  
  92. This is nothing other than incrementing every character, f.i. making A to B,
  93. F to G and Z back to A. So the word FOOBAR will be crypted to GPPCBS, and
  94. nobody will see what it is on the first visit. But there are also people
  95. called Cryptologists, and cracking such codes is their job. Simple methods
  96. of cracking are especially based on the probability of characters in
  97. different languages. They know e is a very often found letter in indo
  98. european languages, and if they find one character very often in the
  99. crypted text, this one may be an e. If it's sure that it's an e, one can
  100. insert it in the complete crypted text where the cracked character was.
  101.  
  102. The method to prevent such simple cracks is based on chaining the produced
  103. output back into the crypt function with some delay.
  104. Consider
  105.  
  106.  out_character = ((in_character + last_out_char)+1) MODULO num_characters
  107.  
  108. with an initial last out character of 'C'.
  109.  
  110. FOOBAR gets JAQTVL using this code and nobody can see that an double O was
  111. in the input. So it's more complicated to crack messages crypted with this
  112. code, because one MUST start at the beginning of the text. It's also
  113. possible to increase the number of ,,states of remember'' we are using,
  114. for instance by not using the last_out_char but the seventh_last_out_char
  115. and using 7 different initial values for them.
  116.  
  117. The method used above is very similar to a common encryption method called
  118. Cipher Block Chaining (CBC) with one state of remember (CBC 1).
  119.  
  120. The difference to ECB in schematic view:
  121.  
  122. ECB electronic code book mode
  123.     y[i] = IDEA(z, x[i])
  124.     x[i] = IIDEA(z, y[i])
  125.  
  126. CBC cipher block chaining mode
  127.     y[i] = IDEA(z, x[i] ^ y[i-N])
  128.     x[i] = IIDEA(z, y[i]) ^ y[i-N]
  129.  
  130. with
  131.  
  132.   x[i] is the input block number i
  133.   y[i] is the output block number i
  134.   z    is the encryption key
  135.   N    is the number of states of remember (at least one)
  136.   IDEA is the encryption function using the IDEA cipher
  137.  IIDEA is the corresponding decryption function
  138.   ^    means the XOR of the operands (Bitwise Exclusive Or)
  139.  
  140. There are two additional modes often used with encryption. See the following
  141. schematics:
  142.  
  143. CFB ciphertext feedback mode
  144.     y[i] = x[i] ^ IDEA(z, y[i-N])
  145.     x[i] = y[i] ^ IDEA(z, y[i-N])
  146.  
  147. OFB output feedback mode
  148.     h[i] = IDEA(z, h[i-N])
  149.     y[i] = x[i] ^ h[i]
  150.     x[i] = y[i] ^ h[i]
  151.  
  152. As you see, all the chaining modes have additional parameters determining the
  153. result of the crypt. Not only the key determines the resulting chunk for a
  154. special input chunk, but also the number of states of remember used by the
  155. mode and the values used to initialize the states (in CBC 1 coding block
  156. #0, you need block #[i-1], but you have no block #-1, so you have to give
  157. some initial value for it). For CBC 8 you have to give 8 initailizers,
  158. and so on.
  159.  
  160. The xpkIDEA implementation uses the following XPK modes for different
  161. encryption methods:
  162.  
  163. XPK Mode    Encr. Method    Nr. States    68030/25    68000/7.14
  164. --------    ------------    ----------    --------    ----------
  165.  0..25        ECB        /        90 K/s        12 K/s
  166. --------------------------------------------------------------------------
  167.  26        CFB        1
  168.   .         .        .        87 K/s        11 K/s
  169.   .         .        .
  170.  50        CFB        25
  171. --------------------------------------------------------------------------
  172.  51        OFB        1
  173.   .         .        .        84 K/s        11 K/s
  174.   .         .        .
  175.  75        OFB        25
  176. --------------------------------------------------------------------------
  177.  76        CBC        1
  178.   .         .        .        84 K/s        11 K/s
  179.   .         .        .
  180.  100        CBC        25
  181. --------------------------------------------------------------------------
  182.  
  183. As you see, the modes were ordered to somehow match the scheme given by the
  184. most XPK packers, with 0..100 mapped to increasing efficiency and decreasing
  185. speed. There are neither big differences in speed nor in efficiency of the
  186. used modes, and the mapping used is easy to remember. Especially one gets
  187. very simple from the mode used to the encr. method and state number by
  188. subsequent subtractions of 25 from the mode:
  189.  
  190.   IDEA.79 -> 79 - (3*25) = 4 , so mode 3 (CBC) with 4 states applies.
  191.  
  192. The default method used when no mode is explicitely given is CBC1,
  193. i.e. the mode IDEA.76
  194.  
  195. The presented speed (in KByte/second) is not very exact. This is mainly
  196. caused by the varying cycle count of the 68000's mul instruction. The
  197. encryption will be faster with the all-zero-key and slower with the
  198. all-ones-key. Try around with key values
  199.  #0
  200.  #5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a5a
  201.  #ffffffffffffffffffffffffffffffff
  202. to see the differences.
  203.  
  204. Not only IDEA.100 is a very safe encryption, also IDEA.75 and IDEA.50 may
  205. be good for safe results. They are modes with 25 states, so one may give
  206. 25 (!) different initializers to the password, which must all be known to
  207. get this decrypted again. The code is developed in a way that no speed
  208. loss will occure even using much states. At the other hand, a open connection
  209. with this sublibrary for packing or unpacking forces the allocation of around
  210. 600 bytes of memory. If you are low on memory, the library may return a
  211. matching error condition.
  212.  
  213.  
  214.                                The Password
  215.                                ------------
  216.  
  217.     You may ask now, how to give different initializers to the encryption
  218. modes which use them ? Therefore, the password parsing routine within this
  219. library is more complicated than normal ones. An IDEA password consists
  220. of the key value and a optional set of initializers, both specified either
  221. as a plain ascii string to be hashed or as the explicite hexadecimal value.
  222.  
  223. The syntax is as follows:
  224.  
  225.  
  226.  <password>    ::=     <keyspec>[<initializer>]*.
  227.  <keyspec>    ::=    <valuespec>.
  228.  <initializer>    ::=    ":"<valuespec>.
  229.  <valuespec>    ::=    [<charstring>|<hexstring>].
  230.  <charstring>    ::=    ["!".."~"]*.
  231.  <hexstring>    ::=    "#"["0".."9"|"a".."f"|"A".."F"]*.
  232.  
  233.  so possible passwords are f.i.:
  234.  password
  235.  password:heut:ist:montag
  236.  #738494ad53ae2c1b736218ac12abaacc:nix:hexa:oder:doch:#4455663311223311
  237.  :            <-- this results in the all-zero-key.
  238.  passwd::::ini4        <-- initializers 1..3 are zero
  239.  
  240.  Its useless to specify any initializers with ECB
  241.  Its useless to specify more then N initializers for mode [CBC|CFB|OFB] N
  242.  The maximum number of initializers is 25
  243.  charstrings may have any number of characters
  244.  hexvalues for keyspec have to fit in an OCTAWORD. (16 Byte)
  245.  hexvalues for initializers must fit in a QUADWORD. (8 Byte)
  246.  unspecified values (key/initializers) are zero.
  247.  
  248.  
  249. If you don't initialize a value, it will be zero. Any syntactic or
  250. semantic error in the password specification will raise the error
  251. XPKERR_WRONGPW. The '#' character is used to introduce hex values because
  252. many shells would missinterpret $ even if it appears in doublequotes.
  253. The hash routine currently used in this password parser is not very strong.
  254. String passwords should be at least 12 characters long to give a nice
  255. key.
  256.  
  257.                               Technical Info
  258.                               --------------
  259. This lib is completely written in assembler using a68k and the 1.3 includes.
  260. It was developed within around 10 hours of work distributed over more than
  261. 14 days (better to say nights).
  262. The author could only test it on an 1 Meg chip no fast 7.14MHz 68000 A500
  263. under Kickstart 1.3. The source is now around 30000 bytes and may contain
  264. some bogus. If you find any bugs report them to me via the email address
  265. given below.
  266. Make sure the output buffer is at least the size of the input buffer plus
  267. XPK_MARGIN, even if this is on decompression more then the original chunk
  268. size. This library relies on this behavior, which is correctly done by
  269. xpkmaster.
  270.  
  271. As already stated in the section Disclaimer, the author gives no warranties
  272. for the proper function of this software. Additional, he cannot give any
  273. guarantee that IDEA itself is a useful encryption standard. It SEEMS to be
  274. very strong, but it's still under analyzation by some organizations like
  275. the NSA and similars. If you are interested in the theoretics of this
  276. algorithm, ask me for some hints.
  277.  
  278.  
  279.                               Version History
  280.                               ---------------
  281.  
  282. 1.00    ( 5-Aug-92 )
  283.  
  284.         First public release.
  285.  
  286.  
  287.  
  288.                               Contact Address
  289.                               ---------------
  290.  
  291.  
  292.     See section Patent for information on how to reach the authors of the
  293. IDEA cipher.
  294. The following mail address applies only until March '93. You will reach
  295. the author of this library there:
  296.  
  297.     beck@freia.inf.tu-dresden.de
  298.  
  299. If you want to get in contact with the author of the fast idea routine used
  300. within this library, contact Mr. Colin Plumb at:
  301.  
  302.  
  303.     colin@eecg.toronto.edu
  304.