1 .. SPDX-License-Identifier: GPL-2.0
2 .. include:: <isonum.txt>
3
4 ===========================================
5 Fast & Portable DES encryption & decryption
6 ===========================================
7
8 .. note::
9
10 Below is the original README file from the
11 converted to ReST format.
12
13 ----------------------------------------------
14
15 des - fast & portable DES encryption & decrypt
16
17 Copyright |copy| 1992 Dana L. How
18
19 This program is free software; you can redistr
20 it under the terms of the GNU Library General
21 the Free Software Foundation; either version 2
22 (at your option) any later version.
23
24 This program is distributed in the hope that i
25 but WITHOUT ANY WARRANTY; without even the imp
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PU
27 GNU Library General Public License for more de
28
29 You should have received a copy of the GNU Lib
30 along with this program; if not, write to the
31 Foundation, Inc., 675 Mass Ave, Cambridge, MA
32
33 Author's address: how@isl.stanford.edu
34
35 .. README,v 1.15 1992/05/20 00:25:32 how E
36
37 ==>> To compile after untarring/unsharring, ju
38
39 This package was designed with the following g
40
41 1. Highest possible encryption/decryption
42 2. PORTABILITY to any byte-addressable ho
43 3. Plug-compatible replacement for KERBER
44
45 This second release includes a number of perfo
46 register-starved machines. My discussions wit
47 71755.204@compuserve.com, sparked a number of
48
49 To more rapidly understand the code in this pa
50 (created by typing ``make``) BEFORE you tackle
51 up in a parameterized fashion so it can easily
52 hackers in pursuit of that last microsecond.
53 illuminating to inspect one specific implement
54 and then move on to the common abstract skelet
55
56
57 performance comparison to other available des
58 compile on a SPARCStation 1 (cc -O4, gcc -O2):
59
60 this code (byte-order independent):
61
62 - 30us per encryption (options: 64k tables,
63 - 33us per encryption (options: 64k tables,
64 - 45us per encryption (options: 2k tables,
65 - 48us per encryption (options: 2k tables,
66 - 275us to set a new key (uses 1k of key tab
67
68 this has the quickest encryption/decry
69 since i was interested in fast des fil
70 and password cracking, i haven't reall
71 the key setting routine. also, i have
72 all the other junk in the mit kerberos
73 provided my routines with little stub
74 used as drop-in replacements with mit'
75 compatible packages below. (note that
76 are highly variable because of cache e
77
78 kerberos des replacement from australia (versi
79
80 - 53us per encryption (uses 2k of tables)
81 - 96us to set a new key (uses 2.25k of key t
82
83 so despite the author's inclusion of s
84 improvements i had suggested to him, t
85 encryption/decryption is still slower
86 more specifically, 19-40% slower on th
87 on the sparc, depending on the compil
88 in full gory detail (ALT_ECB is a libd
89
90 =============== ============== ======
91 compiler machine desCor
92 =============== ============== ======
93 gcc 2.1 -O2 Sun 3/110 304 u
94 cc -O1 Sun 3/110 336 u
95 cc -O2 Sun 3/110 360 u
96 cc -O4 Sun 3/110 365 u
97 gcc 2.1 -O2 Sun 4/50 48 u
98 cc -O2 Sun 4/50 48 u
99 cc -O4 Sun 4/50 48 u
100 =============== ============== ======
101
102 (my time measurements are not as accur
103
104 the comments in my first release of desCore
105
106 - 68us per encryption (uses 2k of tables)
107 - 96us to set a new key (uses 2.25k of key
108
109 this is a very nice package which impl
110 of the optimizations which i did in my
111 it's a bit weak on common low-level op
112 it's 39%-106% slower. because he was
113 password-cracking applications, he al
114 speed up the key-setting routines with
115 (at some point i may do the same in my
116 the rest of the mit des library.
117
118 (code from eay@psych.psy.uq.oz.au via
119
120 fast crypt(3) package from denmark:
121
122 the des routine here is buried inside
123 crypt function and i didn't feel like
124 performance. his code takes 26 sparc i
125 des iteration; above, Quick (64k) take
126 he claims to use 280k of tables but th
127 to use only 128k. his tables and code
128
129 (code from glad@daimi.aau.dk via alt.s
130
131 swedish reimplementation of Kerberos des libra
132
133 - 108us per encryption (uses 34k worth of ta
134 - 134us to set a new key (uses 32k of key ta
135
136 the tables used seem to be machine-ind
137 he seems to have included a lot of spe
138 so that, e.g., ``long`` loads can be u
139 when the machine's architecture allows
140
141 (code obtained from chalmers.se:pub/de
142
143 crack 3.3c package from england:
144
145 as in crypt above, the des routine is
146 also very modified for crypt. his ite
147 of tables and appears to be slow.
148
149 (code obtained from aem@aber.ac.uk via
150
151 ``highly optimized`` and tweaked Kerberos/Athe
152
153 - 165us per encryption (uses 6k worth of tab
154 - 478us to set a new key (uses <1k of key ta
155
156 so despite the comments in this code,
157 faster code AND smaller tables, as wel
158 machine-independent.
159 (code obtained from prep.ai.mit.edu)
160
161 UC Berkeley code (depends on machine-endedness
162 - 226us per encryption
163 - 10848us to set a new key
164
165 table sizes are unclear, but they don'
166 (code obtained from wuarchive.wustl.ed
167
168
169 motivation and history
170 ======================
171
172 a while ago i wanted some des routines and the
173 man pages either didn't exist or dumped core.
174 and knew that it used des, so i figured i'd u
175 i got it and looked at the code, it really se
176 it was too convoluted, the code had been writt
177 advantage of the regular structure of operatio
178 (i.e. the author didn't sit down and think bef
179 it was excessively slow, the author had attem
180 by adding MORE statements to make the data mov
181 instead of simplifying his implementation and
182 movement (in particular, his use of L1, R1, L2
183 idiotic ``tweaks`` for particular machines whi
184 speedups but which did obfuscate everything.
185 from his verification program and rewrote ever
186
187 a while later i ran across the great crypt(3)
188 the fact that this guy was computing 2 sboxes
189 than one (and using a MUCH larger table in the
190 do the same - it was a trivial change from whi
191 by the larger table size. in his case he didn
192 the working data in TWO forms, one for easy us
193 indexing, the other for easy use of the other
194 it in the form for the first half and use a si
195 half. this means i have (almost) half the dat
196 the table size. in fairness though he might b
197 to crypt(3) in his tables - i didn't check.
198
199 i'm glad that i implemented it the way i did,
200 portable (the ifdef's are performance enhancem
201 than versions hand-written in assembly for the
202
203
204 porting notes
205 =============
206
207 one thing i did not want to do was write an en
208 which depended on endedness and other machine
209 and which necessarily produced different code
210 for different machines. see the kerberos code
211 of what i didn't want to do; all their endedne
212 obfuscate the code and in the end were slower
213 independent approach. however, there are alwa
214 considerations of some kind, and i have includ
215 for varying numbers of register variables.
216 perhaps some will still regard the result as a
217
218 1) i assume everything is byte addressable, al
219 depend on the byte order, and that bytes ar
220 i assume word pointers can be freely cast t
221 note that 99% of C programs make these assu
222 i always use unsigned char's if the high bi
223 2) the typedef ``word`` means a 32 bit unsigne
224 if ``unsigned long`` is not 32 bits, change
225 i assume sizeof(word) == 4 EVERYWHERE.
226
227 the (worst-case) cost of my NOT doing endednes
228 in the data loading and storing code surroundi
229 is less than 12%. also, there is the added be
230 the input and output work areas do not need to
231
232
233 OPTIONAL performance optimizations
234 ==================================
235
236 1) you should define one of ``i386,`` ``vax,``
237 whichever one is closest to the capabilitie
238 see the start of desCode.h to see exactly w
239 note that if you select the wrong one, the
240 these are just performance tweaks.
241 2) for those with functional ``asm`` keywords:
242 ROR and ROL macros to use machine rotate in
243 this will save 2 instructions and a tempora
244 or about 32 to 40 instructions per en/decry
245
246 note that gcc is smart enough to translate
247 machine rotates!
248
249 these optimizations are all rather persnickety
250 be able to get performance equal to assembly-c
251
252 1) with the lack of a bit rotate operator in C
253 from shifts. so access to ``asm`` will spe
254 has rotates, as explained above in (3) (not
255 2) if your machine has less than 12 32-bit reg
256 generate good code.
257
258 ``i386`` tries to configure the code for a
259 (it appears that gcc can use ebx, esi and e
260 however, if you like assembly coding, the 3
261 and if you use ALL of them, use ``scaled by
262 and other tricks, you can get reasonable ro
263 about 250 instructions apiece. For DesSmal
264 des_keymap, i.e., now the sbox # is the hig
265 the 6 bits of data is the low part; it help
266
267 since i have no way to conveniently test it
268 shoehorned 386 version. note that with thi
269 to put everything in registers(!), and gene
270 for the DesQuickCore... routines!
271
272 coding notes
273 ============
274
275 the en/decryption routines each use 6 necessar
276 with 4 being actively used at once during the
277 if you don't have 4 register variables get a n
278 up to 8 more registers are used to hold consta
279
280 i assume that the use of a constant is more ex
281
282 a) additionally, i have tried to put the large
283 registering priority was by the following:
284
285 - anything more than 12 bits (bad for
286 - greater than 127 in value (can't use
287 - 9-127 (may not be able to use CISC s
288 - 1-8 were never registered, being the
289
290 b) the compiler may be too stupid to realize t
291 be assigned to different constant registers
292 do the arithmetic, so i assign these to exp
293 when possible and helpful.
294
295 i assume that indexing is cheaper or equivalen
296 where the index is 7 bits unsigned or smaller.
297 this assumption is reversed for 68k and vax.
298
299 i assume that addresses can be cheaply formed
300 or from a register and a small constant.
301 for the 68000, the ``two registers and small o
302 all index scaling is done explicitly - no hidd
303
304 the code is written so that even a dumb compil
305 should never need more than one hidden tempora
306 increasing the chance that everything will fit
307 KEEP THIS MORE SUBTLE POINT IN MIND IF YOU REW
308
309 (actually, there are some code fragments now w
310 but fixing it would either break the structure
311 require declaring another temporary).
312
313
314 special efficient data format
315 ==============================
316
317 bits are manipulated in this arrangement most
318
319 003130292827xxxx242322212019xxxx161514
320
321 (the x bits are still there, i'm just emphasiz
322 bits are rotated left 4 when computing S6 S4 S
323
324 282726252423xxxx201918171615xxxx121110
325
326 the rightmost two bits are usually cleared so
327 as an index into an sbox mapping table. the ne
328 to various values to access different parts of
329
330
331 how to use the routines
332
333 datatypes:
334 pointer to 8 byte area of type DesData
335 used to hold keys and input/output blo
336
337 pointer to 128 byte area of type DesKe
338 used to hold full 768-bit key.
339 must be long-aligned.
340
341 DesQuickInit()
342 call this before using any other routi
343 it generates the special 64k table the
344 DesQuickDone()
345 frees this table
346
347 DesMethod(m, k)
348 m points to a 128byte block, k points
349 which must have odd parity (or -1 is r
350 not be a (semi-)weak key (or -2 is ret
351 normally DesMethod() returns 0.
352
353 m is filled in from k so that when one
354 is called with m, the routine will act
355 en/decryption with the key k. if you u
356 you supply a standard 56bit key; howev
357 m yourself, you will get a 768bit key
358 be standard. it's 768bits not 1024 be
359 two bits of each byte are not used. n
360 will be set to magic constants which s
361 on some machines. and yes, each byte
362 a specific sbox during a specific iter
363
364 you really shouldn't use the 768bit fo
365 provide a routine that converts 128 6-
366 S-box mapping order or something) into
367 this would entail some byte concatenat
368
369 Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d
370 performs des on the 8 bytes at s into
371 ``d. (d,s: char *)``.
372
373 uses m as a 768bit key as explained ab
374
375 the Encrypt|Decrypt choice is obvious.
376
377 Fips|Core determines whether a complet
378 and final permutation is done; if not,
379 and stored in a nonstandard bit order
380
381 Fips slows down Quick by 10%, Small by
382
383 Small|Quick determines whether you use
384 or the crazy quick one which gobbles u
385 Small is 50% slower then Quick, but Qu
386 memory. Quick is included for program
387 e.g., encryption filters, etc.
388
389
390 Getting it to compile on your machine
391 =====================================
392
393 there are no machine-dependencies in the code
394 except perhaps the ``now()`` macro in desTest.
395 ALL generated tables are machine independent.
396 you should edit the Makefile with the appropri
397 for your compiler (MAX optimization).
398
399
400 Speeding up kerberos (and/or its des library)
401 =============================================
402
403 note that i have included a kerberos-compatibl
404 through the functions des_key_sched() and des_
405 to use these with kerberos or kerberos-compati
406 ahead of the kerberos-compatible library on yo
407 you should not need to #include desCore.h; ju
408 file provided with the kerberos library.
409
410 Other uses
411 ==========
412
413 the macros in desCode.h would be very useful f
414 functions in more complicated encryption routi
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.