Back in the 80s, Bob Baldwin was hacking cryptography at MIT and one hack he built was a streamlined DES implementation which tried to trim as many clock cycles as possible to do a DES encryption. Unix machines were using a salted DES password hashing scheme with a hardcoded constant of 64 zero bits that was encrypted 25 times.
In traditional Unix crypt(3), the salt—a 12-bit value derived from
a 2-character ASCII string—permutes the expansion function E in
the DES algorithm, swapping 24 bits of the round expansion so that
hardware DES chips couldn't be used to accelerate password
cracking.
Bob wrote a C implementation of the Unix crypt(3) DES that was fast enough to run
a dictionary attack on a password file in a few hours. This got me inspired.
The LMI Lambda processor had basically the same data paths as the CADR and the TI Explorer; in fact, both the Lambda and Explorer had a CADR compatibility mode so that they could run exactly the same microcode. Like the CADR, the ALU took inputs from two sources: an M-source (scratchpad and functional registers) and an A-source (main register memory and constants). But when the LMI Lambda was built, memory prices had dropped and the memory used for the register sets had an extra address line. This address line wasn't just grounded, it was tied to a register bit which was never changed by standard microcode. If you changed the bit, you would swap the stack cache to the extra, unused memory space. You had to be careful: if a micro page fault occurred, the handler would try to push something and clobber the M registers which were stored in the low part of that memory space. I realized that I could put the DES S-boxes in the unused memory space and then write microcode to do a DES encryption. Like the CADR, the LMI Lambda had a barrel shifter which comes in pretty handy for something like DES.
The LMI Lambda had pageable microcode, so you could write microcode at the REPL and dynamically load it into the machine. You'd call the microcode as you would any other function.
The macro define-micro-function defines a microcode
function, in this case called des-loop. The declare
statement indicates that this microcode should be compiled as a miscellaneous
instruction (one of the unassigned miscellaneous instructions would
be allocated). There was a compiler directive that caused it to emit
one of these miscellaneous instructions when the runtime system
compiled a call to your function.
The code is written with the assumption that the swapped out memory
has been laid out in a certain way, with the S-boxes in one block
and the key schedule in another, etc. The code just refers to
these memory locations freely, as if they were global variables.
Input and output blocks are handled through the global block buffer:
registers m-65 and m-64 hold the 32-bit left
and right halves of the block. The microcode assumes that no other
processes will be touching the memory while it is running. The
microcode does not check interrupts while running, so expect stutters.
A quick note on CADR/Lambda microinstruction syntax: in general, a
microinstruction takes the form ((destination) operation m-source a-source).
The register in parentheses is the destination, the rightmost term specifies the A-bus
source, and the second-to-rightmost term specifies the M-bus source.
(define-micro-function des-loop () (declare (:compile-as-misc-instruction t))
These lines save the stack pointer, set the mode bit to zero, thus swapping the stack cache and the hidden memory, then set the stack pointer to 100 (octal. It is the convention on the Lisp machines that numbers are in octal unless they end with a decimal point.) so that micro page faults won't clobber the M registers which were stored in the low part of the same memory.
;; Work in hidden memory. ((a-saved-pdl-pointer) pdl-pointer) ((dp-mode) m-zero) ((pdl-pointer) (a-constant 100)) ;; octal
Then we load the m-a register with a tagged fixnum zero.
This register serves as the master round counter across all 400 rounds of
DES (25 iterations of 16 rounds each, as required by crypt(3)).
We loop until the counter reaches 399 (decimal).
;; Initialize count. ((m-a) (a-constant (byte-value q-data-type dtp-fix))) ;m-a holds counter. des-round
Registers m-65 and m-64 hold the left and
right 32-bit halves of the cipher block. What follows is the round
expansion: using the barrel shifter and byte extraction/deposit
instructions, the 32-bit right half in m-64 is expanded into
48 bits across m-66 and m-67, then salted
according to the Unix salt permutation.
;; Expand the right half. ((m-66) ldb (byte 1. 31.) m-64 a-zero) ((m-tem) ldb (byte 5. 0.) m-64 a-zero) ((m-66) dpb (byte 5. 1.) m-tem a-66) ((m-tem) ldb (byte 6. 3.) m-64 a-zero) ((m-66) dpb (byte 6. 6.) m-tem a-66) ((m-tem) ldb (byte 6. 7.) m-64 a-zero) ((m-66) dpb (byte 6. 12.) m-tem a-66) ((m-tem) ldb (byte 6. 11.) m-64 a-zero) ((m-66) dpb (byte 6. 18.) m-tem a-66) ((m-67) ldb (byte 6. 15.) m-64 a-zero) ((m-tem) ldb (byte 6. 19.) m-64 a-zero) ((m-67) dpb (byte 6. 6.) m-tem a-67) ((m-tem) ldb (byte 6. 23.) m-64 a-zero) ((m-67) dpb (byte 6. 12.) m-tem a-67) ((m-tem) ldb (byte 5. 27.) m-64 a-zero) ((m-67) dpb (byte 5. 18.) m-tem a-67) ((m-67) dpb (byte 1. 23.) m-64 a-67) ;; Salt the expansion ;; Swap the bits by xoring the bits to swap, masking out ;; the non-swappping bits, and xoring the result back in. ((m-tem) xor m-66 a-67) ;find bits to swap ((m-tem) and m-tem a-57) ;mask non swapping bits ((m-66) xor m-66 a-tem) ((m-67) xor m-67 a-tem) ;; Xor in the key ((m-2) ldb (byte 4. 0.) m-a a-zero) ;get key number.
The low 4 bits of the round counter in m-a are extracted
into m-2, giving the current round key number (0 to 15).
The functional source c-pdl-buffer-index reads the PDL
buffer at the offset in the pdl-index register (indexing into
our hidden memory space). The m-66 and m-67
registers hold the salted, expanded right half, and we XOR in the low and
high halves of the scheduled key.
((pdl-index) add m-2 (a-constant 220)) ;read low key half ((m-66) xor c-pdl-buffer-index a-66) ((pdl-index) add pdl-index (a-constant 20)) ;read high key half ((m-67) xor c-pdl-buffer-index a-67)
This was the trick that made this implementation of DES so fast. The S-boxes
are stored in the hidden memory, and we use the stack cache to do the
lookups. The pdl-index register indexes into the stack cache,
and c-pdl-buffer-index reads the 32-bit table entry. The 4-bit
S-box outputs and the P-permutation were pre-compiled directly into these
table words, accumulating into m-1 via ior.
In the CADR/Lambda byte-extractor (ldb), when given an A-source
constant like 3000 (octal) and a 6-bit byte, it deposits the
extracted 6 bits directly into the low bits of the base address in
a single cycle without an ALU add. This is why the table base
addresses were aligned to octal boundaries 3000, 3100, 3200, etc.
(each table being 100 octal / 64 words long).
Here you also see a fundamental feature of the Knight architecture:
the M-registers write through to the A-memory registers so that their values
are available on both the A-bus and M-bus. When we accumulate S-box values in
((m-1) ior c-pdl-buffer-index a-1), we write to m-1, which
instantly writes through to a-1, allowing the next cycle to read that
accumulated value back in off the A-bus.
;; Pass through the s-boxes ((pdl-index) ldb (byte 6. 0.) m-66 (a-constant 3000)) ((m-1) c-pdl-buffer-index) ((pdl-index) ldb (byte 6. 6.) m-66 (a-constant 3100)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 12.) m-66 (a-constant 3200)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 18.) m-66 (a-constant 3300)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 0.) m-67 (a-constant 3400)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 6.) m-67 (a-constant 3500)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 12.) m-67 (a-constant 3600)) ((m-1) ior c-pdl-buffer-index a-1) ((pdl-index) ldb (byte 6. 18.) m-67 (a-constant 3700)) ((m-1) ior c-pdl-buffer-index a-1) ;; Xor the stuff in and swap halves. ((m-tem) m-65) ;m-tem<-L ((m-65) m-64) ;L<-R
The LMI Lambda micro-engine has visible delayed branches. In
jump-not-equal-xct-next, the instruction following the jump is
executed unconditionally in the delay slot. For rounds 0 through 14,
we jump ahead to check-if-done while computing the Feistel XOR
((m-64) xor m-tem a-1) in the delay slot (again reading the full 32-bit S-box
result from a-1). On round 15 (the end of a 16-round pass), we fall through
and execute the 3-instruction swap on m-65 and m-64 to set up
the block for the next iteration.
(jump-not-equal-xct-next m-2 (a-constant 15.) check-if-done) ((m-64) xor m-tem a-1) ;R<-gunk xor L ;; Swap halves every 16 iterations. ((m-tem) m-65) ((m-65) m-64) ((m-64) m-tem)
Finally, we check whether all 400 rounds have finished. The round counter
increment in ((m-a) add m-a (a-constant 1.)) is executed in the
delay slot of the branch back to des-round. Once the counter
hits 399, we fall through.
check-if-done
(jump-not-equal-xct-next m-a (a-constant (plus (byte-value q-data-type dtp-fix)
399.))
des-round)
((m-a) add m-a (a-constant 1.))
We set the DP mode back to 1 to restore the stack cache to normal,
restore the saved stack pointer, and return to Lisp. Returning with
(jump xfalse) yields nil; the resulting ciphertext
remains safely in the block buffer ready for retrieval.
;; Go back to lisp. ((dp-mode) (a-constant 1.)) ((pdl-pointer) a-saved-pdl-pointer) (jump xfalse))
Usage
To use this microcode, you would first need to load it into the LMI
Lambda processor (pretend you have one at your REPL). In all these examples,
I assume a salt of zero. If you want to use a different salt, you call
load-salt to load the salt mask into register m-57
(which writes through to a-57).
Next, you call load-key-char to load the key into the key buffer.
(dotimes (i 8.) (load-key-char i (elt "foobar\0\0" i)))
Then you generate-c0-and-d0 to generate the initial
key halves. Once you have the key halves, you
call generate-scheduled-key according to the DES key
schedule in user::key-shift-schedule.
(generate-c0-and-d0)
(do ((shift-list user::key-shift-schedule (rest shift-list))
(n 0 (1+ n)))
((null shift-list) nil)
(generate-scheduled-key n (first shift-list)))
Finally, you call (load-block 0 0) to initialize the
64 zero bits into the block buffer (registers m-65 and
m-64). Since the plaintext block is all zeros, we don't bother
with the initial permutation (IP(0) = 0, though Unix crypt(3)
deliberately omits both IP and FP anyway). Then we call (des-loop)
to run the 400-round encryption.
(load-block 0 0)
(des-loop)
The encryption of the empty block will be left in the block buffer
to be retrieved by retrieve-block and assembled into
the password hash.
Conclusion
The custom microcode achieved about parity with Bob Baldwin's C implementation on the VAX 11/780, so it was more of a hack value than a necessary implementation. Yes, I did run a dictionary attack on a password file with it and discovered that it was easily able to crack the passwords in a few hours. No, I didn't do anything too nefarious with it before patching that security hole.
No comments:
Post a Comment