Note

Below is the original README file from the descore.shar package,converted to ReST format.

motivation and history¶

a while ago i wanted some des routines and the routines documented on sun’sman pages either didn’t exist or dumped core. i had heard of kerberos,and knew that it used des, so i figured i’d use its routines. but oncei got it and looked at the code, it really set off a lot of pet peeves -it was too convoluted, the code had been written without takingadvantage of the regular structure of operations such as IP, E, and FP(i.e. the author didn’t sit down and think before coding),it was excessively slow, the author had attempted to clarify the codeby adding MORE statements to make the data movement moreconsistentinstead of simplifying his implementation and cutting down on all datamovement (in particular, his use of L1, R1, L2, R2), and it was full ofidiotictweaks for particular machines which failed to deliver significantspeedups but which did obfuscate everything. so i took the test datafrom his verification program and rewrote everything else.

a while later i ran across the great crypt(3) package mentioned above.the fact that this guy was computing 2 sboxes per table lookup ratherthan one (and using a MUCH larger table in the process) emboldened me todo the same - it was a trivial change from which i had been scared awayby the larger table size. in his case he didn’t realize you don’t need to keepthe working data in TWO forms, one for easy use of half the sboxes inindexing, the other for easy use of the other half; instead you can keepit in the form for the first half and use a simple rotate to get the otherhalf. this means i have (almost) half the data manipulation and halfthe table size. in fairness though he might be encoding something particularto crypt(3) in his tables - i didn’t check.

i’m glad that i implemented it the way i did, because this C version isportable (the ifdef’s are performance enhancements) and it is fasterthan versions hand-written in assembly for the sparc!

porting notes¶

one thing i did not want to do was write an enormous messwhich depended on endedness and other machine quirks,and which necessarily produced different code and different lookup tablesfor different machines. see the kerberos code for an exampleof what i didn’t want to do; all their endedness-specificoptimizationsobfuscate the code and in the end were slower than a simpler machineindependent approach. however, there are always some portabilityconsiderations of some kind, and i have included some optionsfor varying numbers of register variables.perhaps some will still regard the result as a mess!

1. i assume everything is byte addressable, although i don’t actuallydepend on the byte order, and that bytes are 8 bits.i assume word pointers can be freely cast to and from char pointers.note that 99% of C programs make these assumptions.i always use unsigned char’s if the high bit could be set.
2. the typedefword means a 32 bit unsigned integral type.ifunsignedlong is not 32 bits, change the typedef in desCore.h.i assume sizeof(word) == 4 EVERYWHERE.

the (worst-case) cost of my NOT doing endedness-specific optimizationsin the data loading and storing code surrounding the key iterationsis less than 12%. also, there is the added benefit thatthe input and output work areas do not need to be word-aligned.

OPTIONAL performance optimizations¶

1. you should define one ofi386,vax,mc68000, orsparc,whichever one is closest to the capabilities of your machine.see the start of desCode.h to see exactly what this selection implies.note that if you select the wrong one, the des code will still work;these are just performance tweaks.

2. for those with functionalasm keywords: you should change theROR and ROL macros to use machine rotate instructions if you have them.this will save 2 instructions and a temporary per use,or about 32 to 40 instructions per en/decryption.

   note that gcc is smart enough to translate the ROL/R macros intomachine rotates!

these optimizations are all rather persnickety, yet with them you shouldbe able to get performance equal to assembly-coding, except that:

1. with the lack of a bit rotate operator in C, rotates have to be synthesizedfrom shifts. so access toasm will speed things up if your machinehas rotates, as explained above in (3) (not necessary if you use gcc).

2. if your machine has less than 12 32-bit registers i doubt your compiler willgenerate good code.

   i386 tries to configure the code for a 386 by only declaring 3 registers(it appears that gcc can use ebx, esi and edi to hold register variables).however, if you like assembly coding, the 386 does have 7 32-bit registers,and if you use ALL of them, usescaledby8 address modes with displacementand other tricks, you can get reasonable routines for DesQuickCore… withabout 250 instructions apiece. For DesSmall… it will help to rearrangedes_keymap, i.e., now the sbox # is the high part of the index andthe 6 bits of data is the low part; it helps to exchange these.

   since i have no way to conveniently test it i have not provided myshoehorned 386 version. note that with this release of desCore, gcc is ableto put everything in registers(!), and generate about 370 instructions apiecefor the DesQuickCore… routines!

coding notes¶

the en/decryption routines each use 6 necessary register variables,with 4 being actively used at once during the inner iterations.if you don’t have 4 register variables get a new machine.up to 8 more registers are used to hold constants in some configurations.

i assume that the use of a constant is more expensive than using a register:

1. additionally, i have tried to put the larger constants in registers.registering priority was by the following:

   • anything more than 12 bits (bad for RISC and CISC)
   • greater than 127 in value (can’t use movq or byte immediate on CISC)
   • 9-127 (may not be able to use CISC shift immediate or add/sub quick),
   • 1-8 were never registered, being the cheapest constants.

2. the compiler may be too stupid to realize table and table+256 shouldbe assigned to different constant registers and instead repetitivelydo the arithmetic, so i assign these to explicitm register variableswhen possible and helpful.

i assume that indexing is cheaper or equivalent to auto increment/decrement,where the index is 7 bits unsigned or smaller.this assumption is reversed for 68k and vax.

i assume that addresses can be cheaply formed from two registers,or from a register and a small constant.for the 68000, thetworegistersandsmalloffset form is used sparingly.all index scaling is done explicitly - no hidden shifts by log2(sizeof).

the code is written so that even a dumb compilershould never need more than one hidden temporary,increasing the chance that everything will fit in the registers.KEEP THIS MORE SUBTLE POINT IN MIND IF YOU REWRITE ANYTHING.

(actually, there are some code fragments now which do require two temps,but fixing it would either break the structure of the macros orrequire declaring another temporary).

special efficient data format¶

bits are manipulated in this arrangement most of the time (S7 S5 S3 S1):

003130292827xxxx242322212019xxxx161514131211xxxx080706050403xxxx

(the x bits are still there, i’m just emphasizing where the S boxes are).bits are rotated left 4 when computing S6 S4 S2 S0:

282726252423xxxx201918171615xxxx121110090807xxxx040302010031xxxx

the rightmost two bits are usually cleared so the lower byte can be usedas an index into an sbox mapping table. the next two x’d bits are setto various values to access different parts of the tables.

how to use the routines

datatypes:

pointer to 8 byte area of type DesDataused to hold keys and input/output blocks to des.

pointer to 128 byte area of type DesKeysused to hold full 768-bit key.must be long-aligned.

DesQuickInit()

call this before using any other routine withQuick in its name.it generates the special 64k table these routines need.

DesQuickDone()

frees this table

DesMethod(m, k)

m points to a 128byte block, k points to an 8 byte des keywhich must have odd parity (or -1 is returned) and which mustnot be a (semi-)weak key (or -2 is returned).normally DesMethod() returns 0.

m is filled in from k so that when one of the routines belowis called with m, the routine will act like standard desen/decryption with the key k. if you use DesMethod,you supply a standard 56bit key; however, if you fill inm yourself, you will get a 768bit key - but then it won’tbe standard. it’s 768bits not 1024 because the least significanttwo bits of each byte are not used. note that these two bitswill be set to magic constants which speed up the encryption/decryptionon some machines. and yes, each byte controlsa specific sbox during a specific iteration.

you really shouldn’t use the 768bit format directly; i shouldprovide a routine that converts 128 6-bit bytes (specified inS-box mapping order or something) into the right format for you.this would entail some byte concatenation and rotation.

Des{Small|Quick}{Fips|Core}{Encrypt|Decrypt}(d, m, s)

performs des on the 8 bytes at s into the 8 bytes atd.(d,s:char*).

uses m as a 768bit key as explained above.

the Encrypt|Decrypt choice is obvious.

Fips|Core determines whether a completely standard FIPS initialand final permutation is done; if not, then the data is loadedand stored in a nonstandard bit order (FIPS w/o IP/FP).

Fips slows down Quick by 10%, Small by 9%.

Small|Quick determines whether you use the normal routineor the crazy quick one which gobbles up 64k more of memory.Small is 50% slower then Quick, but Quick needs 32 times as muchmemory. Quick is included for programs that do nothing but DES,e.g., encryption filters, etc.

Getting it to compile on your machine¶

there are no machine-dependencies in the code (see porting),except perhaps thenow() macro in desTest.c.ALL generated tables are machine independent.you should edit the Makefile with the appropriate optimization flagsfor your compiler (MAX optimization).

Speeding up kerberos (and/or its des library)¶

note that i have included a kerberos-compatible interface in desUtil.cthrough the functions des_key_sched() and des_ecb_encrypt().to use these with kerberos or kerberos-compatible code put desCore.aahead of the kerberos-compatible library on your linker’s command line.you should not need to #include desCore.h; just include the headerfile provided with the kerberos library.

Other uses¶

the macros in desCode.h would be very useful for putting inline desfunctions in more complicated encryption routines.