home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / crypt / README < prev    next >
Encoding:
Text File  |  1992-10-06  |  7.7 KB  |  222 lines
  1.  
  2.  
  3.     UFC-crypt: ultra fast 'crypt' implementation
  4.     ============================================
  5.  
  6.     @(#)README    2.21 10/07/92
  7.  
  8. Design goals/non goals:
  9. ----------------------
  10.  
  11. - Crypt implementation plugin compatible with crypt(3)/fcrypt.
  12.  
  13. - High performance when used for password cracking.
  14.  
  15. - Portable to most 32/64 bit machines.
  16.  
  17. - Startup time/mixed salt performance not critical.
  18.  
  19. Features of the implementation:
  20. ------------------------------
  21.  
  22. - On most machines, UFC-crypt runs 30-60 times faster than crypt(3) when
  23.   invoked repeated times with the same salt and varying passwords.
  24.  
  25. - With mostly constant salts, performance is about two to three times
  26.   that of the default fcrypt implementation shipped with Alec 
  27.   Muffets 'Crack' password cracker. For instructions on how to
  28.   plug UFC-crypt into 'Crack', see below.
  29.  
  30. - With alternating salts, performance is only about twice
  31.   that of crypt(3).
  32.  
  33. - Tested on 680x0, 386, SPARC, MIPS, HP-PA, Convex, Cray,
  34.   Pyramid and IBM RS/6000 systems as well as with gcc on IBM PS/2(DOS)
  35.   and Linux on a 386 PC.
  36.  
  37. - Requires 165 kb for tables.
  38.  
  39. - UFC-crypt is known to have compilation problems with some micro computer
  40.   C compilers (e.g. Turbo C++) due to its table sizes. Flame the vendors
  41.   for placing arbitrary limitations on their products. Use & support the
  42.   GNU C compiler, gcc.
  43.  
  44. - Also includes 'fcrypt16' - the function used with DEC's enhanced
  45.   security setup.
  46.  
  47. Author & licensing etc
  48. ----------------------
  49.  
  50. UFC-crypt is created by Michael Glad, email: glad@daimi.aau.dk, and has
  51. been donated to the Free Software Foundation, Inc. It is covered by the 
  52. GNU library license version 2, see the file 'COPYING'.
  53.  
  54. NOTES FOR USERS OUTSIDE THE US:
  55. ------------------------------
  56.  
  57. The US government limits the export of DES based software/hardware.
  58. This software is written in Aarhus, Denmark. It can therefore be retrieved
  59. from ftp sites outside the US without breaking US law. Please do not
  60. ftp it from american sites.
  61.  
  62. Installing UFC-crypt
  63. --------------------
  64.  
  65. Installing as part of the GNU C Library:
  66. ***************************************
  67.  
  68. Unpack UFC-crypt and move the directory holding the sources into the
  69. C library source directory as 'crypt'.
  70.  
  71. UNIX install
  72. ************
  73.  
  74. Edit the Makefile setting the variables
  75.  
  76. CRYPT:    The encryption module to use; crypt.o should always work.
  77.         If compiling for one of the machines for which special support
  78.     is available, select the appropriate module.
  79.  
  80. CC:    The compiler to use.
  81.  
  82. OFLAGS: The highest level of optimization available.
  83.  
  84. Now run 'make'. UFC-crypt is compiled into 'libufc.a'. A test program: ufc
  85. is also linked. Try it out: './ufc 1' to test proper operation.
  86.  
  87. For a more thorough test, run 'make tests'. This compiles and invokes
  88. a DES validation suite as well as two benchmark programs comparing 
  89. UFC-crypt with the native crypt(3) implementation. 
  90.  
  91. If your friendly vendor has omitted crypt(3) from libc, compilation of 
  92. the native benchmark program 'speedc' will fail. Compilation of the 
  93. 'speed*' programs may also fail as they use timer facilities not present
  94. in the same form in all UNIX implementations. If so is, you may choose to
  95.  run '/bin/time ./ufc 10000' and divide the CPU time used by 10000.
  96.  
  97. 'libufc.a' can be linked into your applications. It is compatible with
  98. both crypt(3) and the fcrypt shipped with Alec Muffett's Crack program.
  99.  
  100. DOS install
  101. ***********
  102.  
  103. UFC-crypt compiles under DOS at least with MSC 6.00A. To compile,
  104. move 'patchlevel.h' to 'pl.h', 'ufc-crypt.h' to 'ufc.h' and 'crypt_util.c'
  105. to 'cryptutl.c'. When compiling, define the macro 'DOS' ( -DDOS ). 
  106. You should compile & link the programs by hand. Refer to the Makefile to
  107. see which modules is needed for a program. You should be able to compile &
  108. run the verification programs 'cert' and 'ufc' but not the benchmark program 
  109. 'speedf'. For benchmarking, measure the running time of 'ufc 10000'.
  110. Having compiled the modules, you can link 'cryptutl.o' and 'crypt.o' into 
  111. your application programs or put them into a library.
  112.  
  113. Installing UFC-crypt into Crack:
  114. *******************************
  115.  
  116. Crack Release 4.0a: in 'Sources/Makefile', change the CRACKCRYPT macro
  117.             to a path leading to 'libufc.a' and invoke the Crack
  118.             script as usual.
  119.  
  120. 4.1 and later:      Crack knows about UFC-crypt. Refer to the Crack docs
  121.             for instructions.
  122.  
  123. Benchmark table:
  124. ---------------
  125.  
  126. The table shows how many operations per second UFC-crypt can
  127. do on various machines. 
  128.  
  129. |--------------|-------------------------------------------|
  130. |Machine       |  SUN*  SUN*   HP*     DecStation   HP     |
  131. |              | 3/50   ELC  9000/425e    3100    9000/720 |
  132. |--------------|-------------------------------------------|
  133. | Crypt(3)/sec |  4.6    30     15         25        57    |
  134. | Ufc/sec      |  220   990    780       1015      3500    |
  135. |--------------|-------------------------------------------|
  136. | Speedup      |   48    30     52         40        60    |
  137. |--------------|-------------------------------------------|
  138.  
  139. *) Compiled using special assembly language support module.
  140.  
  141. It seems as if performance is limited by CPU bus and data cache capacity. 
  142. This also makes the benchmarks debatable compared to a real test with
  143. UFC-crypt wired into Crack. However, the table gives an outline of
  144. what can be expected.
  145.  
  146. Optimizations:
  147. -------------
  148.  
  149. Here are the optimizations used relative to an ordinary implementation
  150. such as the one said to be used in crypt(3).
  151.  
  152. Major optimizations
  153. *******************
  154.  
  155. - Keep data packed as bits in integer variables -- allows for
  156.   fast permutations & parallel xor's in CPU hardware.
  157.  
  158. - Let adjacent final & initial permutations collapse.
  159.  
  160. - Keep working data in 'E expanded' format all the time.
  161.  
  162. - Implement DES 'f' function mostly by table lookup
  163.  
  164. - Calculate the above function on 12 bit basis rather than 6
  165.   as would be the most natural.
  166.  
  167. - Implement setup routines so that performance is limited by the DES
  168.   inner loops only.
  169.  
  170. - Instead of doing salting in the DES inner loops, modify the above tables
  171.   each time a new salt is seen. According to the BSD crypt code this is
  172.   ugly :-)
  173.  
  174. Minor (dirty) optimizations
  175. ***************************
  176.  
  177. - combine iterations of DES inner loop so that DES only loops
  178.   8 times. This saves a lot of variable swapping.
  179.  
  180. - Implement key access by a walking pointer rather than coding
  181.   as array indexing.
  182.  
  183. - As described, the table based f function uses a 3 dimensional array:
  184.  
  185.     sb ['number of 12 bit segment']['12 bit index']['48 bit half index']
  186.  
  187.   Code the routine with 4 (one dimensional) vectors.
  188.  
  189. - Design the internal data format & uglify the DES loops so that
  190.   the compiler does not need to do bit shifts when indexing vectors.
  191.  
  192. Portability issues
  193. ******************
  194.  
  195. UFC-crypt does not need to know the byte endianness of the machine is runs on.
  196.  
  197. To speed up the DES inner loop, it does a dirty trick requiring the
  198. availability of a integer flavoured data type occupying exactly 32 (or 64)
  199. bits. This is normally the case of 'long'. The header file 'ufc-crypt.h'
  200. contains typedefs for this type. If you have to change it (or any other part)
  201. to get things working, please drop me a note.
  202.  
  203. UFC-crypt can take advantage of 64 bit integers. At the moment, it is
  204. configured to do so automatically for Convex & Cray machines.
  205.  
  206. Revision history
  207. ****************
  208.  
  209. UFC patchlevel 0: base version; released to alt.sources on Sep 24 1991
  210. UFC patchlevel 1: patch released to alt.sources on Sep 27 1991.
  211.           No longer rebuilds sb tables when seeing a new salt.
  212. UFC-crypt pl0:      Essentially UFC pl 1. Released to comp.sources.misc
  213.           on Oct 22 1991.
  214. UFC-crypt pl1:    Released to comp.sources.misc in march 1992
  215.           * setkey/encrypt routines added
  216.           * added validation/benchmarking programs
  217.           * reworked keyschedule setup code
  218.           * memory demands reduced
  219.           * 64 bit support added
  220.  
  221.  
  222.