| 1 |
|
|---|
| 2 |
|
|---|
| 3 | UFC-crypt: ultra fast 'crypt' implementation
|
|---|
| 4 | ============================================
|
|---|
| 5 |
|
|---|
| 6 | @(#)README 2.27 11 Sep 1996
|
|---|
| 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: [email protected], 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 GNU crypt Library:
|
|---|
| 66 | **********************(********
|
|---|
| 67 |
|
|---|
| 68 | Unpack the library in some place. The simplest place is the toplevel
|
|---|
| 69 | directory of the GNU C library sources. Now mention `crypt' as on
|
|---|
| 70 | of the add-ons used for GNU libc. I.e., when the sources are in the
|
|---|
| 71 | toplevel source directory simply run the `configure' script of the
|
|---|
| 72 | *libc* as:
|
|---|
| 73 |
|
|---|
| 74 | configure --enable-add-ons=crypt,XXX <usual configure options>
|
|---|
| 75 |
|
|---|
| 76 | where XXX are the names of possibly existing other add-ons.
|
|---|
| 77 |
|
|---|
| 78 | That's all.
|
|---|
| 79 |
|
|---|
| 80 |
|
|---|
| 81 | Ordinary UNIX install
|
|---|
| 82 | *********************
|
|---|
| 83 |
|
|---|
| 84 | Copy the file
|
|---|
| 85 |
|
|---|
| 86 | Makefile.non-gnu
|
|---|
| 87 |
|
|---|
| 88 | to
|
|---|
| 89 |
|
|---|
| 90 | Makefile
|
|---|
| 91 |
|
|---|
| 92 | Edit Makefile setting the variables
|
|---|
| 93 |
|
|---|
| 94 | CRYPT: The encryption module to use; crypt.o should always work.
|
|---|
| 95 | If compiling for one of the machines for which special support
|
|---|
| 96 | is available, select the appropriate module.
|
|---|
| 97 |
|
|---|
| 98 | CC: The compiler to use.
|
|---|
| 99 |
|
|---|
| 100 | OFLAGS: The highest level of optimization available.
|
|---|
| 101 |
|
|---|
| 102 | Now run 'make'. UFC-crypt is compiled into 'libufc.a'. A test program: ufc
|
|---|
| 103 | is also linked. Try it out: './ufc 1' to test proper operation.
|
|---|
| 104 |
|
|---|
| 105 | For a more thorough test, run 'make tests'. This compiles and invokes
|
|---|
| 106 | a DES validation suite as well as two benchmark programs comparing
|
|---|
| 107 | UFC-crypt with the native crypt(3) implementation.
|
|---|
| 108 |
|
|---|
| 109 | If your friendly vendor has omitted crypt(3) from libc, compilation of
|
|---|
| 110 | the native benchmark program 'speedc' will fail. Compilation of the
|
|---|
| 111 | 'speed*' programs may also fail as they use timer facilities not present
|
|---|
| 112 | in the same form in all UNIX implementations. If so is, you may choose to
|
|---|
| 113 | run '/bin/time ./ufc 10000' and divide the CPU time used by 10000.
|
|---|
| 114 |
|
|---|
| 115 | 'libufc.a' can be linked into your applications. It is compatible with
|
|---|
| 116 | both crypt(3) and the fcrypt shipped with Alec Muffett's Crack program.
|
|---|
| 117 |
|
|---|
| 118 | DOS install
|
|---|
| 119 | ***********
|
|---|
| 120 |
|
|---|
| 121 | UFC-crypt compiles under DOS at least with MSC 6.00A. To compile,
|
|---|
| 122 | move 'patchlevel.h' to 'pl.h', 'ufc-crypt.h' to 'ufc.h' and 'crypt_util.c'
|
|---|
| 123 | to 'cryptutl.c'. When compiling, define the macro 'DOS' ( -DDOS ).
|
|---|
| 124 | You should compile & link the programs by hand. Refer to the Makefile to
|
|---|
| 125 | see which modules is needed for a program. You should be able to compile &
|
|---|
| 126 | run the verification programs 'cert' and 'ufc' but not the benchmark program
|
|---|
| 127 | 'speedf'. For benchmarking, measure the running time of 'ufc 10000'.
|
|---|
| 128 | Having compiled the modules, you can link 'cryptutl.o' and 'crypt.o' into
|
|---|
| 129 | your application programs or put them into a library.
|
|---|
| 130 |
|
|---|
| 131 | Installing UFC-crypt into Crack:
|
|---|
| 132 | *******************************
|
|---|
| 133 |
|
|---|
| 134 | Crack Release 4.0a: in 'Sources/Makefile', change the CRACKCRYPT macro
|
|---|
| 135 | to a path leading to 'libufc.a' and invoke the Crack
|
|---|
| 136 | script as usual.
|
|---|
| 137 |
|
|---|
| 138 | 4.1 and later: Crack knows about UFC-crypt. Refer to the Crack docs
|
|---|
| 139 | for instructions.
|
|---|
| 140 |
|
|---|
| 141 | Benchmark table:
|
|---|
| 142 | ---------------
|
|---|
| 143 |
|
|---|
| 144 | The table shows how many operations per second UFC-crypt can
|
|---|
| 145 | do on various machines.
|
|---|
| 146 |
|
|---|
| 147 | |--------------|-------------------------------------------|
|
|---|
| 148 | |Machine | SUN* SUN* HP* DecStation HP |
|
|---|
| 149 | | | 3/50 ELC 9000/425e 3100 9000/720 |
|
|---|
| 150 | |--------------|-------------------------------------------|
|
|---|
| 151 | | Crypt(3)/sec | 4.6 30 15 25 57 |
|
|---|
| 152 | | Ufc/sec | 220 990 780 1015 3500 |
|
|---|
| 153 | |--------------|-------------------------------------------|
|
|---|
| 154 | | Speedup | 48 30 52 40 60 |
|
|---|
| 155 | |--------------|-------------------------------------------|
|
|---|
| 156 |
|
|---|
| 157 | *) Compiled using special assembly language support module.
|
|---|
| 158 |
|
|---|
| 159 | It seems as if performance is limited by CPU bus and data cache capacity.
|
|---|
| 160 | This also makes the benchmarks debatable compared to a real test with
|
|---|
| 161 | UFC-crypt wired into Crack. However, the table gives an outline of
|
|---|
| 162 | what can be expected.
|
|---|
| 163 |
|
|---|
| 164 | Optimizations:
|
|---|
| 165 | -------------
|
|---|
| 166 |
|
|---|
| 167 | Here are the optimizations used relative to an ordinary implementation
|
|---|
| 168 | such as the one said to be used in crypt(3).
|
|---|
| 169 |
|
|---|
| 170 | Major optimizations
|
|---|
| 171 | *******************
|
|---|
| 172 |
|
|---|
| 173 | - Keep data packed as bits in integer variables -- allows for
|
|---|
| 174 | fast permutations & parallel xor's in CPU hardware.
|
|---|
| 175 |
|
|---|
| 176 | - Let adjacent final & initial permutations collapse.
|
|---|
| 177 |
|
|---|
| 178 | - Keep working data in 'E expanded' format all the time.
|
|---|
| 179 |
|
|---|
| 180 | - Implement DES 'f' function mostly by table lookup
|
|---|
| 181 |
|
|---|
| 182 | - Calculate the above function on 12 bit basis rather than 6
|
|---|
| 183 | as would be the most natural.
|
|---|
| 184 |
|
|---|
| 185 | - Implement setup routines so that performance is limited by the DES
|
|---|
| 186 | inner loops only.
|
|---|
| 187 |
|
|---|
| 188 | - Instead of doing salting in the DES inner loops, modify the above tables
|
|---|
| 189 | each time a new salt is seen. According to the BSD crypt code this is
|
|---|
| 190 | ugly :-)
|
|---|
| 191 |
|
|---|
| 192 | Minor (dirty) optimizations
|
|---|
| 193 | ***************************
|
|---|
| 194 |
|
|---|
| 195 | - combine iterations of DES inner loop so that DES only loops
|
|---|
| 196 | 8 times. This saves a lot of variable swapping.
|
|---|
| 197 |
|
|---|
| 198 | - Implement key access by a walking pointer rather than coding
|
|---|
| 199 | as array indexing.
|
|---|
| 200 |
|
|---|
| 201 | - As described, the table based f function uses a 3 dimensional array:
|
|---|
| 202 |
|
|---|
| 203 | sb ['number of 12 bit segment']['12 bit index']['48 bit half index']
|
|---|
| 204 |
|
|---|
| 205 | Code the routine with 4 (one dimensional) vectors.
|
|---|
| 206 |
|
|---|
| 207 | - Design the internal data format & uglify the DES loops so that
|
|---|
| 208 | the compiler does not need to do bit shifts when indexing vectors.
|
|---|
| 209 |
|
|---|
| 210 | Portability issues
|
|---|
| 211 | ******************
|
|---|
| 212 |
|
|---|
| 213 | UFC-crypt does not need to know the byte endianness of the machine is runs on.
|
|---|
| 214 |
|
|---|
| 215 | To speed up the DES inner loop, it does a dirty trick requiring the
|
|---|
| 216 | availability of a integer flavoured data type occupying exactly 32 (or 64)
|
|---|
| 217 | bits. This is normally the case of 'long'. The header file 'ufc-crypt.h'
|
|---|
| 218 | contains typedefs for this type. If you have to change it (or any other part)
|
|---|
| 219 | to get things working, please drop me a note.
|
|---|
| 220 |
|
|---|
| 221 | UFC-crypt can take advantage of 64 bit integers. At the moment, it is
|
|---|
| 222 | configured to do so automatically for Convex & Cray machines.
|
|---|
| 223 |
|
|---|
| 224 | Revision history
|
|---|
| 225 | ****************
|
|---|
| 226 |
|
|---|
| 227 | UFC patchlevel 0: base version; released to alt.sources on Sep 24 1991
|
|---|
| 228 | UFC patchlevel 1: patch released to alt.sources on Sep 27 1991.
|
|---|
| 229 | No longer rebuilds sb tables when seeing a new salt.
|
|---|
| 230 | UFC-crypt pl0: Essentially UFC pl 1. Released to comp.sources.misc
|
|---|
| 231 | on Oct 22 1991.
|
|---|
| 232 | UFC-crypt pl1: Released to comp.sources.misc in march 1992
|
|---|
| 233 | * setkey/encrypt routines added
|
|---|
| 234 | * added validation/benchmarking programs
|
|---|
| 235 | * reworked keyschedule setup code
|
|---|
| 236 | * memory demands reduced
|
|---|
| 237 | * 64 bit support added
|
|---|
