1: The following is the README for UFC-crypt, with those portions deleted
    2: that are known to be incorrect for the implementation used with the
    3: GNU C library.
    4: 
    5: 
    6:         UFC-crypt: ultra fast 'crypt' implementation
    7:         ============================================
    8: 
    9:         @(#)README     2.27 11 Sep 1996
   10: 
   11: Design goals/non goals:
   12: ----------------------
   13: 
   14: - Crypt implementation plugin compatible with crypt(3)/fcrypt.
   15: 
   16: - High performance when used for password cracking.
   17: 
   18: - Portable to most 32/64 bit machines.
   19: 
   20: - Startup time/mixed salt performance not critical.
   21: 
   22: Features of the implementation:
   23: ------------------------------
   24: 
   25: - On most machines, UFC-crypt runs 30-60 times faster than crypt(3) when
   26:   invoked repeated times with the same salt and varying passwords.
   27: 
   28: - With mostly constant salts, performance is about two to three times
   29:   that of the default fcrypt implementation shipped with Alec
   30:   Muffets 'Crack' password cracker. For instructions on how to
   31:   plug UFC-crypt into 'Crack', see below.
   32: 
   33: - With alternating salts, performance is only about twice
   34:   that of crypt(3).
   35: 
   36: - Requires 165 kb for tables.
   37: 
   38: Author & licensing etc
   39: ----------------------
   40: 
   41: UFC-crypt is created by Michael Glad, email: glad@daimi.aau.dk, and has
   42: been donated to the Free Software Foundation, Inc. It is covered by the
   43: GNU library license version 2, see the file 'COPYING.LIB'.
   44: 
   45: NOTES FOR USERS OUTSIDE THE US:
   46: ------------------------------
   47: 
   48: The US government limits the export of DES based software/hardware.
   49: This software is written in Aarhus, Denmark. It can therefore be retrieved
   50: from ftp sites outside the US without breaking US law. Please do not
   51: ftp it from american sites.
   52: 
   53: Benchmark table:
   54: ---------------
   55: 
   56: The table shows how many operations per second UFC-crypt can
   57: do on various machines.
   58: 
   59: |--------------|-------------------------------------------|
   60: |Machine       |  SUN*  SUN*   HP*     DecStation   HP     |
   61: |              | 3/50   ELC  9000/425e    3100    9000/720 |
   62: |--------------|-------------------------------------------|
   63: | Crypt(3)/sec |  4.6    30     15         25        57    |
   64: | Ufc/sec      |  220   990    780       1015      3500    |
   65: |--------------|-------------------------------------------|
   66: | Speedup      |   48    30     52         40        60    |
   67: |--------------|-------------------------------------------|
   68: 
   69: *) Compiled using special assembly language support module.
   70: 
   71: It seems as if performance is limited by CPU bus and data cache capacity.
   72: This also makes the benchmarks debatable compared to a real test with
   73: UFC-crypt wired into Crack. However, the table gives an outline of
   74: what can be expected.
   75: 
   76: Optimizations:
   77: -------------
   78: 
   79: Here are the optimizations used relative to an ordinary implementation
   80: such as the one said to be used in crypt(3).
   81: 
   82: Major optimizations
   83: *******************
   84: 
   85: - Keep data packed as bits in integer variables -- allows for
   86:   fast permutations & parallel xor's in CPU hardware.
   87: 
   88: - Let adjacent final & initial permutations collapse.
   89: 
   90: - Keep working data in 'E expanded' format all the time.
   91: 
   92: - Implement DES 'f' function mostly by table lookup
   93: 
   94: - Calculate the above function on 12 bit basis rather than 6
   95:   as would be the most natural.
   96: 
   97: - Implement setup routines so that performance is limited by the DES
   98:   inner loops only.
   99: 
  100: - Instead of doing salting in the DES inner loops, modify the above tables
  101:   each time a new salt is seen. According to the BSD crypt code this is
  102:   ugly :-)
  103: 
  104: Minor (dirty) optimizations
  105: ***************************
  106: 
  107: - combine iterations of DES inner loop so that DES only loops
  108:   8 times. This saves a lot of variable swapping.
  109: 
  110: - Implement key access by a walking pointer rather than coding
  111:   as array indexing.
  112: 
  113: - As described, the table based f function uses a 3 dimensional array:
  114: 
  115:         sb ['number of 12 bit segment']['12 bit index']['48 bit half index']
  116: 
  117:   Code the routine with 4 (one dimensional) vectors.
  118: 
  119: - Design the internal data format & uglify the DES loops so that
  120:   the compiler does not need to do bit shifts when indexing vectors.
  121: 
  122: Revision history
  123: ****************
  124: 
  125: UFC patchlevel 0: base version; released to alt.sources on Sep 24 1991
  126: UFC patchlevel 1: patch released to alt.sources on Sep 27 1991.
  127:                   No longer rebuilds sb tables when seeing a new salt.
  128: UFC-crypt pl0:    Essentially UFC pl 1. Released to comp.sources.misc
  129:                   on Oct 22 1991.
  130: UFC-crypt pl1:    Released to comp.sources.misc in march 1992
  131:                   * setkey/encrypt routines added
  132:                   * added validation/benchmarking programs
  133:                   * reworked keyschedule setup code
  134:                   * memory demands reduced
  135:                   * 64 bit support added