README.ufc-crypt
1The following is the README for UFC-crypt, with those portions deleted
2that are known to be incorrect for the implementation used with the
3GNU C library.
4
5
6 UFC-crypt: ultra fast 'crypt' implementation
7 ============================================
8
9 @(#)README 2.27 11 Sep 1996
10
11Design 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
22Features 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
38Author & licensing etc
39----------------------
40
41UFC-crypt is created by Michael Glad, email: glad@daimi.aau.dk, and has
42been donated to the Free Software Foundation, Inc. It is covered by the
43GNU library license version 2, see the file 'COPYING.LIB'.
44
45NOTES FOR USERS OUTSIDE THE US:
46------------------------------
47
48The US government limits the export of DES based software/hardware.
49This software is written in Aarhus, Denmark. It can therefore be retrieved
50from ftp sites outside the US without breaking US law. Please do not
51ftp it from american sites.
52
53Benchmark table:
54---------------
55
56The table shows how many operations per second UFC-crypt can
57do 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
71It seems as if performance is limited by CPU bus and data cache capacity.
72This also makes the benchmarks debatable compared to a real test with
73UFC-crypt wired into Crack. However, the table gives an outline of
74what can be expected.
75
76Optimizations:
77-------------
78
79Here are the optimizations used relative to an ordinary implementation
80such as the one said to be used in crypt(3).
81
82Major 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
104Minor (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
122Revision history
123****************
124
125UFC patchlevel 0: base version; released to alt.sources on Sep 24 1991
126UFC patchlevel 1: patch released to alt.sources on Sep 27 1991.
127 No longer rebuilds sb tables when seeing a new salt.
128UFC-crypt pl0: Essentially UFC pl 1. Released to comp.sources.misc
129 on Oct 22 1991.
130UFC-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
136