home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume23 / ufc-crypt / part01 / README < prev    next >
Encoding:
Text File  |  1991-10-21  |  4.4 KB  |  134 lines
  1.  
  2.  
  3.     UFC-crypt: ultra fast 'crypt' implementation
  4.     ============================================
  5.  
  6.     @(#)README    2.3 10/04/91
  7.  
  8. Design goals/non goals:
  9. -----------------------
  10.  
  11. - Crypt implementation plugin compatible with crypt(3)/fcrypt
  12.  
  13. - Extremely high performance when used for password cracking.
  14.  
  15. - Portable to most 32 bit machines
  16.  
  17. - Startup time/mixed salt performance not critical
  18.  
  19. Features of the implementation:
  20. ------------------------------
  21.  
  22. - Runs 25-45 times faster than crypt(3) when invoked repeated
  23.   times with the same salt and varying passwords.
  24.   With alternating salts, performance is only about 4 times
  25.   that of crypt(3).
  26.  
  27. - Tested on 68000,386,SPARC,MIPS,HP-PA and RS/6000 systems
  28.  
  29. - Requires 280 kb for tables.
  30.  
  31. Author & licensing etc
  32. ----------------------
  33.  
  34. UFC-crypt is written by Michael Glad, email: glad@daimi.aau.dk.
  35. It is covered by the GNU library license version 2, see the file 'COPYING'.
  36.  
  37. Installing
  38. ----------
  39.  
  40. Edit the Makefile setting the variables
  41.  
  42. CRYPT:    The encryption module to use; crypt.o should always work.
  43.         If running on one of the machines for which special support
  44.     is available, select the appropriate module.
  45.  
  46. FL:     If your OS does not have the routines bcopy/bzero in libc,
  47.     try '-DSYSV'.
  48.  
  49. CC:    The compiler to use
  50.  
  51. OFLAG:    The highest level of optimization available
  52.  
  53. Now run 'make'. The files 'ufc' and 'libufa.c' are produced.
  54. Try 'ufc <number>' to test proper operation and to do benchmarks.
  55. If you link 'ufc' without 'libufc.a' you can benchmark your crypt(3).
  56.  
  57. 'libufc.a' can be linked into your applications. It is compatible with
  58. both crypt(3) and the fcrypt shipped with Alec Muffett's Crack program.
  59.  
  60. For use in Crack: in 'Sources/Makefile', substitute crack-fcrypt.o with
  61. a path to libufc.a in the CRACKMOD declaration. For benchmarking, use
  62. the 'speedcrypt' program in the same directory.
  63.  
  64. Benchmark table:
  65. ---------------
  66.  
  67. If special assembly language support was used, the machine name is marked
  68. with '*'. Times are in milliseconds, a line gives how many encryptions UFC-crypt
  69. can perform per second on the various architectures.
  70.  
  71. |----------|---------------------------------------------|
  72. |Machine   |  SUN*  SUN*   HP*      DIGITAL       HP     |
  73. |          | 3/50   ELC  9000/425e DecStation   9000/720 |
  74. |----------|---------------------------------------------|
  75. | Crypt(3) |  230    37    60         38          17     |
  76. | Ufc      |  5.2   1.5   1.4        1.2         0,36    |
  77. | Ufc/sec  |  190   670   715        830         2700    |
  78. |----------|---------------------------------------------|
  79. | Speedup  |   45    25    43         32           47    |
  80. |----------|---------------------------------------------|
  81.  
  82. It seems as if performance is limited by CPU bus and data cache capacity. 
  83. E.g. on a SUN4, UFC-crypt reads almost 10 mb/sec into the CPU
  84. registers. As 128kb of memory are swept during an encryption, it may also
  85. misbehave with datacaches.
  86.  
  87. Optimizations:
  88. -------------
  89.  
  90. Here are the optimizations used relative to an ordinary implementation
  91. such as the one said to be used in crypt(3).
  92.  
  93. Major optimizations
  94. *******************
  95.  
  96. - Keep data packed as bits in integer variables -- allows for
  97.   fast permutations & parallel xor's in CPU hardware.
  98.  
  99. - Let adjacent final & initial permutations collapse.
  100.  
  101. - Keep working data in 'E expanded' format all the time.
  102.  
  103. - Implement DES 'f' function mostly by table lookup
  104.  
  105. - Calculate the above function on 12 bit basis rather than 6
  106.   as would be the most natural. This eats core for tables
  107.   but it's critical for performance.
  108.  
  109. - Implement setup routines so that performance is limited by the DES
  110.   inner loops only. At the moment the key calculation routine accounts for
  111.   a rather unavoidable 16% of the CPU usage.
  112.  
  113. Minor (dirty) optimizations
  114. ***************************
  115.  
  116. - combine iterations of DES inner loop so that DES only loops
  117.   8 times. This saves a lot of variable swapping.
  118.  
  119. - Implement key access by a walking pointer rather than coding
  120.   as array indexing.
  121.  
  122. - As described, the table based f function uses a 3 dimensional array:
  123.  
  124.     sb ['number of 12 bit segment']['12 bit index']['48 bit half index']
  125.  
  126.   Code the routine with 4 (one dimensional) vectors.
  127.  
  128. - Design the internal data format & uglify the DES loops so that
  129.   the compiler does not need to do bit shifts when indexing vectors.
  130.  
  131. - For selected architectures, code the quite little crypt function itself 
  132.   in assembly language but keep the support routines in C.
  133.  
  134.