1.. SPDX-License-Identifier: GPL-2.0 2.. include:: <isonum.txt> 3 4=========================================== 5Fast & Portable DES encryption & decryption 6=========================================== 7 8.. note:: 9 10 Below is the original README file from the descore.shar package, 11 converted to ReST format. 12 13------------------------------------------------------------------------------ 14 15des - fast & portable DES encryption & decryption. 16 17Copyright |copy| 1992 Dana L. How 18 19This program is free software; you can redistribute it and/or modify 20it under the terms of the GNU Library General Public License as published by 21the Free Software Foundation; either version 2 of the License, or 22(at your option) any later version. 23 24This program is distributed in the hope that it will be useful, 25but WITHOUT ANY WARRANTY; without even the implied warranty of 26MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 27GNU Library General Public License for more details. 28 29You should have received a copy of the GNU Library General Public License 30along with this program; if not, write to the Free Software 31Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 32 33Author'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, just ``make`` <<== 38 39This package was designed with the following goals: 40 411. Highest possible encryption/decryption PERFORMANCE. 422. PORTABILITY to any byte-addressable host with a 32bit unsigned C type 433. Plug-compatible replacement for KERBEROS's low-level routines. 44 45This second release includes a number of performance enhancements for 46register-starved machines. My discussions with Richard Outerbridge, 4771755.204@compuserve.com, sparked a number of these enhancements. 48 49To more rapidly understand the code in this package, inspect desSmallFips.i 50(created by typing ``make``) BEFORE you tackle desCode.h. The latter is set 51up in a parameterized fashion so it can easily be modified by speed-daemon 52hackers in pursuit of that last microsecond. You will find it more 53illuminating to inspect one specific implementation, 54and then move on to the common abstract skeleton with this one in mind. 55 56 57performance comparison to other available des code which i could 58compile on a SPARCStation 1 (cc -O4, gcc -O2): 59 60this code (byte-order independent): 61 62 - 30us per encryption (options: 64k tables, no IP/FP) 63 - 33us per encryption (options: 64k tables, FIPS standard bit ordering) 64 - 45us per encryption (options: 2k tables, no IP/FP) 65 - 48us per encryption (options: 2k tables, FIPS standard bit ordering) 66 - 275us to set a new key (uses 1k of key tables) 67 68 this has the quickest encryption/decryption routines i've seen. 69 since i was interested in fast des filters rather than crypt(3) 70 and password cracking, i haven't really bothered yet to speed up 71 the key setting routine. also, i have no interest in re-implementing 72 all the other junk in the mit kerberos des library, so i've just 73 provided my routines with little stub interfaces so they can be 74 used as drop-in replacements with mit's code or any of the mit- 75 compatible packages below. (note that the first two timings above 76 are highly variable because of cache effects). 77 78kerberos des replacement from australia (version 1.95): 79 80 - 53us per encryption (uses 2k of tables) 81 - 96us to set a new key (uses 2.25k of key tables) 82 83 so despite the author's inclusion of some of the performance 84 improvements i had suggested to him, this package's 85 encryption/decryption is still slower on the sparc and 68000. 86 more specifically, 19-40% slower on the 68020 and 11-35% slower 87 on the sparc, depending on the compiler; 88 in full gory detail (ALT_ECB is a libdes variant): 89 90 =============== ============== =============== ================= 91 compiler machine desCore libdes ALT_ECB slower by 92 =============== ============== =============== ================= 93 gcc 2.1 -O2 Sun 3/110 304 uS 369.5uS 461.8uS 22% 94 cc -O1 Sun 3/110 336 uS 436.6uS 399.3uS 19% 95 cc -O2 Sun 3/110 360 uS 532.4uS 505.1uS 40% 96 cc -O4 Sun 3/110 365 uS 532.3uS 505.3uS 38% 97 gcc 2.1 -O2 Sun 4/50 48 uS 53.4uS 57.5uS 11% 98 cc -O2 Sun 4/50 48 uS 64.6uS 64.7uS 35% 99 cc -O4 Sun 4/50 48 uS 64.7uS 64.9uS 35% 100 =============== ============== =============== ================= 101 102 (my time measurements are not as accurate as his). 103 104 the comments in my first release of desCore on version 1.92: 105 106 - 68us per encryption (uses 2k of tables) 107 - 96us to set a new key (uses 2.25k of key tables) 108 109 this is a very nice package which implements the most important 110 of the optimizations which i did in my encryption routines. 111 it's a bit weak on common low-level optimizations which is why 112 it's 39%-106% slower. because he was interested in fast crypt(3) and 113 password-cracking applications, he also used the same ideas to 114 speed up the key-setting routines with impressive results. 115 (at some point i may do the same in my package). he also implements 116 the rest of the mit des library. 117 118 (code from eay@psych.psy.uq.oz.au via comp.sources.misc) 119 120fast crypt(3) package from denmark: 121 122 the des routine here is buried inside a loop to do the 123 crypt function and i didn't feel like ripping it out and measuring 124 performance. his code takes 26 sparc instructions to compute one 125 des iteration; above, Quick (64k) takes 21 and Small (2k) takes 37. 126 he claims to use 280k of tables but the iteration calculation seems 127 to use only 128k. his tables and code are machine independent. 128 129 (code from glad@daimi.aau.dk via alt.sources or comp.sources.misc) 130 131swedish reimplementation of Kerberos des library 132 133 - 108us per encryption (uses 34k worth of tables) 134 - 134us to set a new key (uses 32k of key tables to get this speed!) 135 136 the tables used seem to be machine-independent; 137 he seems to have included a lot of special case code 138 so that, e.g., ``long`` loads can be used instead of 4 ``char`` loads 139 when the machine's architecture allows it. 140 141 (code obtained from chalmers.se:pub/des) 142 143crack 3.3c package from england: 144 145 as in crypt above, the des routine is buried in a loop. it's 146 also very modified for crypt. his iteration code uses 16k 147 of tables and appears to be slow. 148 149 (code obtained from aem@aber.ac.uk via alt.sources or comp.sources.misc) 150 151``highly optimized`` and tweaked Kerberos/Athena code (byte-order dependent): 152 153 - 165us per encryption (uses 6k worth of tables) 154 - 478us to set a new key (uses <1k of key tables) 155 156 so despite the comments in this code, it was possible to get 157 faster code AND smaller tables, as well as making the tables 158 machine-independent. 159 (code obtained from prep.ai.mit.edu) 160 161UC 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't look very small 166 (code obtained from wuarchive.wustl.edu) 167 168 169motivation and history 170====================== 171 172a while ago i wanted some des routines and the routines documented on sun's 173man pages either didn't exist or dumped core. i had heard of kerberos, 174and knew that it used des, so i figured i'd use its routines. but once 175i got it and looked at the code, it really set off a lot of pet peeves - 176it was too convoluted, the code had been written without taking 177advantage of the regular structure of operations such as IP, E, and FP 178(i.e. the author didn't sit down and think before coding), 179it was excessively slow, the author had attempted to clarify the code 180by adding MORE statements to make the data movement more ``consistent`` 181instead of simplifying his implementation and cutting down on all data 182movement (in particular, his use of L1, R1, L2, R2), and it was full of 183idiotic ``tweaks`` for particular machines which failed to deliver significant 184speedups but which did obfuscate everything. so i took the test data 185from his verification program and rewrote everything else. 186 187a while later i ran across the great crypt(3) package mentioned above. 188the fact that this guy was computing 2 sboxes per table lookup rather 189than one (and using a MUCH larger table in the process) emboldened me to 190do the same - it was a trivial change from which i had been scared away 191by the larger table size. in his case he didn't realize you don't need to keep 192the working data in TWO forms, one for easy use of half the sboxes in 193indexing, the other for easy use of the other half; instead you can keep 194it in the form for the first half and use a simple rotate to get the other 195half. this means i have (almost) half the data manipulation and half 196the table size. in fairness though he might be encoding something particular 197to crypt(3) in his tables - i didn't check. 198 199i'm glad that i implemented it the way i did, because this C version is 200portable (the ifdef's are performance enhancements) and it is faster 201than versions hand-written in assembly for the sparc! 202 203 204porting notes 205============= 206 207one thing i did not want to do was write an enormous mess 208which depended on endedness and other machine quirks, 209and which necessarily produced different code and different lookup tables 210for different machines. see the kerberos code for an example 211of what i didn't want to do; all their endedness-specific ``optimizations`` 212obfuscate the code and in the end were slower than a simpler machine 213independent approach. however, there are always some portability 214considerations of some kind, and i have included some options 215for varying numbers of register variables. 216perhaps some will still regard the result as a mess! 217 2181) i assume everything is byte addressable, although i don't actually 219 depend on the byte order, and that bytes are 8 bits. 220 i assume word pointers can be freely cast to and from char pointers. 221 note that 99% of C programs make these assumptions. 222 i always use unsigned char's if the high bit could be set. 2232) the typedef ``word`` means a 32 bit unsigned integral type. 224 if ``unsigned long`` is not 32 bits, change the typedef in desCore.h. 225 i assume sizeof(word) == 4 EVERYWHERE. 226 227the (worst-case) cost of my NOT doing endedness-specific optimizations 228in the data loading and storing code surrounding the key iterations 229is less than 12%. also, there is the added benefit that 230the input and output work areas do not need to be word-aligned. 231 232 233OPTIONAL performance optimizations 234================================== 235 2361) you should define one of ``i386,`` ``vax,`` ``mc68000,`` or ``sparc,`` 237 whichever one is closest to the capabilities of your machine. 238 see the start of desCode.h to see exactly what this selection implies. 239 note that if you select the wrong one, the des code will still work; 240 these are just performance tweaks. 2412) for those with functional ``asm`` keywords: you should change the 242 ROR and ROL macros to use machine rotate instructions if you have them. 243 this will save 2 instructions and a temporary per use, 244 or about 32 to 40 instructions per en/decryption. 245 246 note that gcc is smart enough to translate the ROL/R macros into 247 machine rotates! 248 249these optimizations are all rather persnickety, yet with them you should 250be able to get performance equal to assembly-coding, except that: 251 2521) with the lack of a bit rotate operator in C, rotates have to be synthesized 253 from shifts. so access to ``asm`` will speed things up if your machine 254 has rotates, as explained above in (3) (not necessary if you use gcc). 2552) if your machine has less than 12 32-bit registers i doubt your compiler will 256 generate good code. 257 258 ``i386`` tries to configure the code for a 386 by only declaring 3 registers 259 (it appears that gcc can use ebx, esi and edi to hold register variables). 260 however, if you like assembly coding, the 386 does have 7 32-bit registers, 261 and if you use ALL of them, use ``scaled by 8`` address modes with displacement 262 and other tricks, you can get reasonable routines for DesQuickCore... with 263 about 250 instructions apiece. For DesSmall... it will help to rearrange 264 des_keymap, i.e., now the sbox # is the high part of the index and 265 the 6 bits of data is the low part; it helps to exchange these. 266 267 since i have no way to conveniently test it i have not provided my 268 shoehorned 386 version. note that with this release of desCore, gcc is able 269 to put everything in registers(!), and generate about 370 instructions apiece 270 for the DesQuickCore... routines! 271 272coding notes 273============ 274 275the en/decryption routines each use 6 necessary register variables, 276with 4 being actively used at once during the inner iterations. 277if you don't have 4 register variables get a new machine. 278up to 8 more registers are used to hold constants in some configurations. 279 280i assume that the use of a constant is more expensive than using a register: 281 282a) additionally, i have tried to put the larger constants in registers. 283 registering priority was by the following: 284 285 - anything more than 12 bits (bad for RISC and CISC) 286 - greater than 127 in value (can't use movq or byte immediate on CISC) 287 - 9-127 (may not be able to use CISC shift immediate or add/sub quick), 288 - 1-8 were never registered, being the cheapest constants. 289 290b) the compiler may be too stupid to realize table and table+256 should 291 be assigned to different constant registers and instead repetitively 292 do the arithmetic, so i assign these to explicit ``m`` register variables 293 when possible and helpful. 294 295i assume that indexing is cheaper or equivalent to auto increment/decrement, 296where the index is 7 bits unsigned or smaller. 297this assumption is reversed for 68k and vax. 298 299i assume that addresses can be cheaply formed from two registers, 300or from a register and a small constant. 301for the 68000, the ``two registers and small offset`` form is used sparingly. 302all index scaling is done explicitly - no hidden shifts by log2(sizeof). 303 304the code is written so that even a dumb compiler 305should never need more than one hidden temporary, 306increasing the chance that everything will fit in the registers. 307KEEP THIS MORE SUBTLE POINT IN MIND IF YOU REWRITE ANYTHING. 308 309(actually, there are some code fragments now which do require two temps, 310but fixing it would either break the structure of the macros or 311require declaring another temporary). 312 313 314special efficient data format 315============================== 316 317bits are manipulated in this arrangement most of the time (S7 S5 S3 S1):: 318 319 003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx 320 321(the x bits are still there, i'm just emphasizing where the S boxes are). 322bits are rotated left 4 when computing S6 S4 S2 S0:: 323 324 282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx 325 326the rightmost two bits are usually cleared so the lower byte can be used 327as an index into an sbox mapping table. the next two x'd bits are set 328to various values to access different parts of the tables. 329 330 331how to use the routines 332 333datatypes: 334 pointer to 8 byte area of type DesData 335 used to hold keys and input/output blocks to des. 336 337 pointer to 128 byte area of type DesKeys 338 used to hold full 768-bit key. 339 must be long-aligned. 340 341DesQuickInit() 342 call this before using any other routine with ``Quick`` in its name. 343 it generates the special 64k table these routines need. 344DesQuickDone() 345 frees this table 346 347DesMethod(m, k) 348 m points to a 128byte block, k points to an 8 byte des key 349 which must have odd parity (or -1 is returned) and which must 350 not be a (semi-)weak key (or -2 is returned). 351 normally DesMethod() returns 0. 352 353 m is filled in from k so that when one of the routines below 354 is called with m, the routine will act like standard des 355 en/decryption with the key k. if you use DesMethod, 356 you supply a standard 56bit key; however, if you fill in 357 m yourself, you will get a 768bit key - but then it won't 358 be standard. it's 768bits not 1024 because the least significant 359 two bits of each byte are not used. note that these two bits 360 will be set to magic constants which speed up the encryption/decryption 361 on some machines. and yes, each byte controls 362 a specific sbox during a specific iteration. 363 364 you really shouldn't use the 768bit format directly; i should 365 provide a routine that converts 128 6-bit bytes (specified in 366 S-box mapping order or something) into the right format for you. 367 this would entail some byte concatenation and rotation. 368 369Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s) 370 performs des on the 8 bytes at s into the 8 bytes at 371 ``d. (d,s: char *)``. 372 373 uses m as a 768bit key as explained above. 374 375 the Encrypt|Decrypt choice is obvious. 376 377 Fips|Core determines whether a completely standard FIPS initial 378 and final permutation is done; if not, then the data is loaded 379 and stored in a nonstandard bit order (FIPS w/o IP/FP). 380 381 Fips slows down Quick by 10%, Small by 9%. 382 383 Small|Quick determines whether you use the normal routine 384 or the crazy quick one which gobbles up 64k more of memory. 385 Small is 50% slower then Quick, but Quick needs 32 times as much 386 memory. Quick is included for programs that do nothing but DES, 387 e.g., encryption filters, etc. 388 389 390Getting it to compile on your machine 391===================================== 392 393there are no machine-dependencies in the code (see porting), 394except perhaps the ``now()`` macro in desTest.c. 395ALL generated tables are machine independent. 396you should edit the Makefile with the appropriate optimization flags 397for your compiler (MAX optimization). 398 399 400Speeding up kerberos (and/or its des library) 401============================================= 402 403note that i have included a kerberos-compatible interface in desUtil.c 404through the functions des_key_sched() and des_ecb_encrypt(). 405to use these with kerberos or kerberos-compatible code put desCore.a 406ahead of the kerberos-compatible library on your linker's command line. 407you should not need to #include desCore.h; just include the header 408file provided with the kerberos library. 409 410Other uses 411========== 412 413the macros in desCode.h would be very useful for putting inline des 414functions in more complicated encryption routines. 415