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