DEStiny

UNIX password encryption on a tinyChip

A VLSI chip designed by:

Zhenyu Liu and David Ljung

University Of Wisconsin – Madison

DEStiny

UNIX password encryption on a tinyChip

Zhenyu Liu and David Ljung

University Of Wisconsin – Madison

Abstract – A custom VLSI encryption chip is described.  The chip is designed in 2.0 µm CMOS technology with two levels of metalization and 5.0V power requirements.  The active die size is 1800 x 1820 µm and contains 5800 transistors.  The chip provides a hardware implementation of the UNIX crypt() algorithm.  It requires 400 cycles at 17 ns per cycle to complete the calculation, plus 8 cycles for simultaneous input and output.  This achieves an entire encryption in under 7µs.
I. System Overview
1.  Introduction
P
 assword encryption on UNIX systems is done with a variation of the DES algorithm called crypt() which we will refer to as “crypt” in this paper.  The DES and crypt algorithm provide a one-way encryption scheme, maintaining security with readable password files.  One danger of this system lies in password-guessing programs which do numerous encryptions of ‘guessed’ passwords to see if they have the same encryption as any passwords in the password file.  To avoid this security hole, it is important that such an encryption scheme has a significant delay, and that it is difficult to minimize this delay in software or hardware.  The crypt algorithm was designed with this in mind; however, improvements in hardware and software technology are beginning to decrease the security of the crypt algorithm to a dangerous level worth investigating.
Our chip is a low-cost implementation of the crypt algorithm which demonstrates these security problems.  A straightforward crypt implementation can do an encryption in software in about 100 ms on a standard workstation.  There are a number of techniques to speed this up, usually using a space-for-time tradeoff, since space (memory) is relatively cheap compared to the amount of processing time that an encryption takes.  An example of this is speed-crypt  written by David C. Feldmeier (Feld, 1989), which is able to achieve software encryption rates of approximately 1 ms on a Sun SPARCStation (1989), a full two orders of magnitude faster.  This is the same execution time (1 ms) that was given as the main reason to switch from the previous encryption algorithm (crypt Version 6) to the current one.  By designing crypt in hardware, even more orders of magnitude speedup have been obtained, to an encryption time of only 7µs.
Such results have a significant effect on the future of the crypt algorithm.  For example, assuming that a password is constructed of only alphanumeric characters (as the majority are), then a single DEStiny chip could find any 8 character password in 228 days.  This is now plausible, as compared to 91 years through software.  Exploiting parallelism,  a bank of 256 DEStiny chips can crack any such password in less than 1 day, with the average time being 11 hours.  This should easily point out the dangers of the crypt algorithm due to current technology.
The speedup we were able to obtain was only a taste of what was possible in hardware, since our die size limited our speed performance a great deal.  This was because our fabrication was limited to a tinyChip, with an active die size of only 1800x1820 µm.  In the research we did previous to designing this chip, we were unable to find any VLSI implementations of the DES algorithm in this small of a space.  The modifications on DES for crypt take up additional space, so we had our work cut out for us.  Also, in our research, we were unable to find a single example of the crypt algorithm on a chip, and we are under the impression that such a chip has not been fabricated before.

2.  Strategy
There are a number of design options available in designing a crypt chip to be used for multiple encryptions.  A basic password guessing algorithm is inherently parallel.  Each encryption is independent of any other encryptions, so the ability to do multiple encryptions provides a linear speedup.  We decided to design a small, low-cost implementation for performance reasons.  Faster crypt chips can be designed which can use larger die sizes and better technologies, but the cost is far beyond linear.  Consequently, by using multiple chips, we can achieve the same speeds as the faster crypt chips at a fraction of the cost.
3.  Challenge
The crypt algorithm was specifically designed to be difficult to implement in a small area or with a fast execution time.  By limiting ourselves to a smaller chip, our challenge was to design a reasonably fast implementation of the crypt algorithm within the small, fixed die size.
There are many examples of the design difficulties built into the algorithm.  The algorithm has many tables which are often  created as static arrays in software, which takes up lots of chip array in hardware.  In the final design, we only needed to represent one of the tables as a ROM, saving space.
Another challenge was the fact that our design technology had only two layers of metalization.  The algorithm is designed so that there is a great deal of complex routing that cannot be simplified.  Two layers of metalization and complex routing means a lot of chip area wasted on wiring.  In fact, although three layers of metalization is usually enough for most designs, there were numerous instances where five or more layers would have saved a great deal of space.  To make things worse, our technology wouldn’t allow M1M2 vias on top of other non-touching contacts.  This caused slightly larger dimensions for some of our bitslices (the registers in particular) that would then be multiplied by 32, 48 or 56 times.
In general, faster techniques were only used if a reasonable amount of area was required.  Because of this we were forced to ignore a number of speedups such as pipelining that we could have considered with more area.  Instead we concentrated on techniques which minimized area, while either maintaining or decreasing delay.  Because of this, we were able to fit crypt into a smaller chip without many speed losses due to area tradeoffs.
II.  Project Specification
Interface
The interface is very basic for two reasons:
•	It was more important to use area for improving the main loop block than for aiding input/output which only occurred once per encryption
•	The chip only does one function, and in a password-guessing system a minimal chip interface is desired.
The input and output deals with three sets of data:

1	A 12 bit salt (from two characters) which causes a modification of the E permutation in plain DES encryption
2	A 56 bit (8 characters without parity bits) password (clear text)
3	A 64 bit encrypted output (ciphered text)
Both the output and the salt are in a ‘bin’ format.  To convert to or from normal ASCII characters requires a simple table lookup.  However, since tables take up a great deal of area, we leave this up to the system.  Since this only occurs once at the beginning and end of the encryption, this shouldn’t cause a problem.
The steps for an encryption from a chip interface perspective are:
1.	Transform the two character salt into 12 bits.
2.	Raise the load signal for eight cycles:
3.	Load one of the eight 7-bit password characters each cycle.
4.	Load the salt in, two bits at a time, for the third through eighth cycles.
And:
5.	If the chip has just completed an encryption, read out a byte of the 64-bit output each cycle.  Convert the output to ascii with bin-to-ascii.
	For password guessing:
	Compare to the encrypted password from the password file.
8.	Lower the load signal and hold low for 400 cycles.
9.  Raise the load to get the output (step 5) and to possible enter another input (steps 3, 4).

III.  Algorithm Description
The crypt function uses a variation of the DES algorithm.  Both algorithms are described here in text form.  The crypt algorithm is then described in block format.

DES Algorithm
description:
DES (Data Encryption Standard) is a one-way encryption scheme that is resistant to plain text attack.  Because of the one-way characteristic of the scheme, it is impossible to decipher encrypted text without an exhaustive search of possible keys (of which there are 256). 
inputs:
8 bytes (64 bits) of a text stream (clear text)
8 byte key (56 bits with 8 bits for odd parity)
outputs:
8 byte encrypted text
definition of terms used in steps:
a permutation is a re-ordering of bits according to a table
all addition is modulo two (exclusive-or)
a subkey is generated from the original key using a permutation, a number of rotates and another permutation.
the key schedule is the set of permutations and rotates required to create each subkey for each iteration
IP is the initial DES permutation, IP-1 is the inverse of this permutation
E is a permutation which mixes and expands 32 bits to 48 bits
P is a permutation from 32 bits to 32 bits
The S blocks are selection functions which convert 48 bits to 32 bits.  This part of the algorithm cannot be reversed without creating many possible inputs.
The tables for the permutations and the S blocks are not included here for the sake of space.
overview of steps:
The 8 byte clear text is permuted by IP.
The following is done 16 times:
The rightmost 32 bits are permuted and expanded by E to 48 bits
This value is added to the subkey generated by this iteration of the key schedule
This 48 bit value is changed to 32 bits with the S blocks.
This value is permuted by P
We add this value to the leftmost 32 bits to get our next rightmost 32 bits.
Our next leftmost 32 bits are just the original rightmost 32 bits from the beginning of this step.
After the completion of the 16 iterations, we permute the final value with IP-1

crypt Algorithm
description:
crypt is a modification of the DES algorithm used for passwords.  crypt runs DES on a constant string a number of times using the password as a key.  crypt also uses a salt to vary the encryption routine at run-time for each password.  This makes an exhaustive massive-password-file search impossible since most passwords will use different salts. 
inputs:
8 byte password
2 byte ‘salt’
outputs:
8 byte encrypted password (with the original salt)
definition of terms used in steps:
the salt is used to permute bits 1-12 with bits 25-36 of the 48 bit intermediate value
overview of steps:
Do DES 25 times using the password as a key and the last value of the DES encryption as the input text (the first input text to use is just a string of 8 zeros).
Use the following modification to DES:
 After each E permutation, swap each bit 1-12 with bit 25-36 if the corresponding bit of the salt is a 1.

There are a number of optimizations we will be attempting  to improve the crypt algorithm to save time, and more importantly, space.  A simple example of this is the ability to remove all of the IP and IP-1 permutations except for the final IP-1, since IP * IP-1 is the identity.

Block Diagram
The basic DES iteration is as shown:

Iteration of the DES algorithm
This iteration is performed 25 times the DES 16 iterations.  The iteration function is:

the product function – f[i]
The subkeys used in the product function are determined by the key scheduling routine:

key scheduling
The rotate amount is decided by a key scheduling table (not included in this text).
To do the crypt routine, the modified DES (16 iterations) is done 25 times, starting with an input of all zeros and using the password as a key.  The final result is run through IP-1 to get the encrypted password.  Between each 16 iterations of DES, the right and left registers are switched back.
IV.  Cell Design
Our entire floorplan follows.  Each component was designed differently, depending on area requirements.
It can be seen from the floorplan diagram that all of the components used the entire width of the chip except in the LRX, even though most of the components have a different number of bits.  To solve this problem we used the permutations between  components to do pitch-matching as well as permutations.

Floorplan
registers
All the registers are dynamic master-slave registers with no feedback (not pseudo-static).  This is done for space and time and is made possible by our two-phase clock which we need for the dynamic Sblocks.
LRX (left, right, xor)
The left and right register as well as the final xor are combined into a single bit-slice, aiding in routing as well as giving a uniform space to the side of the LRX for the salt register.
Since we get the output by shifting bits from the left and right register, we connected the shift-in of each to ground, automatically giving us our all-zero starting value.  This way we don’t need a load signal for the LRX, saving us 64 pass-gates and enough area to put in the salt register.
E/Salt
The swapping done by the salt is built-in to the E permutation to save some space.  To achieve this, the E contains switch-logic muxes in the permutation to choose which bit of the swap to use.  The salt register is located on both sides of the LRX and connected directly to the select line of the mux, thereby ‘transforming’ the E permutation for the duration of the encryption.
48 bit xor
The 48 bit xor is a gate-logic xor because a switch-logic implementation would have caused too much of a delay.
Sblocks
The Sblocks are implemented as a ROM to simulate the non-affine Sblock table.  Originally we attempted to use a 4x2 layout, but it was too wide for the die size, so we moved to 5x1 to fit in the pad frame.
The decoder was one of the few examples where we used a larger design for the sake of speed.  We used a domino nand-gate decoder instead of a smaller pseudo-nmos we also designed because it was at least twice as fast with a cost of only 100 nm, which was within our height budget for the Sblocks.
The Sblock dynamic ROM was built using a combination of the genie generator and a homemade tool, blk.c.
The Sblocks were created entirely without using metal2 so we are able to pass the subkey result over the top.  This enables us to put the key logic at one end of the pad frame, next to the key input pads.
The output of the Sblock goes through the P permutation which was generated by a genie file and then hand-optimized for height by row-sharing.
key
The key register cells were designed to minimize height since the full chip width was available to the key.  The key has three major modules, the register, the control and the PC2 permutation.
Implementing PC1 as a straightforward permutation would have taken up more height than we had available.  Instead, we used a shift-load strategy which implements PC1 directly in the key register.  This doesn’t require any extra time as it occurs while the key is being loaded byte by byte.
Each subkey generation requires a rotate of either 1 or 2 bits based upon which of the 16 DES iterations the function is working on.  A minimal control would have had us designing a 4-bit state machine which would have taken up a lot of height above the key register.  Instead, we realized that we could string 16 registers in serial across the width of the chip.  Then we would just propagate a 1 along the line every clock cycle.  This way we would know what cycle we were in, and we could ‘or’ together which cycles required a rotate of 1 or 2.  We also use this chain to tell the LRX (see below) when we are on the 16th iteration.
Since the key can be generated in parallel, we decided to generate each subkey a cycle early so it would be ready for the next iteration.  To do this, we build a prerotate directly into the PC2 permutation so the first subkey is ready immediately after key loading.
The PC2 permutation was created in the same manner as the P permutation.
V.  Design Techniques
We used a mix of full-custom and generated layout for our components.  The majority of layout is full-custom.
		
key and key control	full-custom	
Sblock ROM	generated (genie, blk.c)	
ROM decoder	generated	
LRX	full-custom	
salt register	full-custom	
xor 48	full-custom	
permutations	generated and hand optimized	
routing	by hand	
As a general principle, we tried to do hand layout whenever reasonable, either because of area limitations, or because of specific shape limitations.
blk.c is a homemade tool that we wrote to create the tables from the behavioral model for the genie generator.
As part of our design, we wrote the entire behavioral model in 500 lines of C which helped us test and understand the encryption.
VI.  Timing
Our clock is a two-phase clock generated off-chip.  The following events occur in our stages:

Although the calculation is split into two clocks, pipelining would be very difficult to achieve.  Since each DES iteration is dependent on the previous iteration, pipelining can only be used to run multiple encryptions on the same chip.  However, each encryption would require a duplication of a number of resources, such as many registers, the entire key logic, and most notably, the Sblock.  Plus the pipelining logic, we essentially double the area necessary.
Most of the chip is a series calculation and therefore the critical path is the path for the entire function.  Only the key and Sblock precharge can be done in parallel.  Therefore, anything that could lower the delay of any of the other components without adding too much area had a high value.
VII.  Simulation Strategy
While we were designing the components, we would double-check simulation results against results from the behavioral model.
Simulation for more complex components was achieved using simulation script files, sometimes with data created by the behavioral model.  As components were combined, script files were merged to create new scripts.  This technique worked very well for us.
Test cases for smaller components were usually exhaustive, especially on bitslices.  This was either done by hand or with script files.
Final simulation of the entire chip was performed in switch and adept mode, with matching results.  Only a few iterations are needed to insure proper behavior, and any password/salt combination works as a test case.  The reason for this is because of the inherent chaotic nature of crypt.  Any small changes to the input causes massive changes in the output.  Therefore, any input will test all of the components of the chip.  The chances of a chip having a bug yet still giving proper output for one iteration is very small.  The chances of a chip having a bug and giving the correct output after the entire encryption for a few inputs is next to impossible.
VIII.  Test Strategy
We were unable to use scan pads for testing in order to adhere to security standards for DES chips.
If the chip doesn't immediately work (proper encryptions are not obtained):
1.	Test the LRX by keeping the load signal high for 16 cycles.  The output during the last 8 cycles should be all zero.
2.	Test one iteration of the chip.  Load for 8 cycles, run for 1 cycles and then raise load again to get the output. 
	If the key or either xor has a bug, it will cause a 1 bit error.
	If the Sblock has a bug, it will cause 4 bit errors.
3.	If the bug still can’t be located, it might be necessary to fabricate a subset of one of the iterations to allow space for scan pads.
IX.  Chip Statistics
		
die size	2.24 x 2.2 mm	
active area	3.3 mm2	
transistor count	5900	
contact count	11350	
layout density (xstrs)	1788 /mm2	
layout density (total)	5230 /mm2	
clock	17 ns	
encryption time	7 µs	
X.  Software Analysis
genie:	A powerful language for a generator.  We found it to be very helpful for some of our non-regular designs.  Regular designs could just be duplicated repeatedly.
Led:	Many excellent time-saving features which we found out about much too late, such as partial replot, partial error checking and ACAP.  Using ACAP manually (selecting target) is essential for good design.
Lsim:	Fairly fast even in adept mode, but having to restart for every design change is unreasonable.
XI.  Summary
A single chip which implements the UNIX crypt algorithm in a small area has been designed.  This chip used numerous design techniques to minimize area without sacrificing speed.  It is designed specifically for multiple-chip, multiple-encryption systems, but can be used as the crypt hardware support for a workstation or other such system.
This chip was created as a class project for an Introduction to VLSI design class at the University of Wisconsin, Madison.  Improvements to it have occured since then, most specifically in converting the design to a different CMOS technology in order to fabricate.
References
•	Michael Glad <glad@daimi.aau.dk>, simple-crypt.c source code
•	“UNIX Password Security - Ten Years Later,” David C. Feldmeier and Philip R. Karn, Bellcore. 1989
•	“Security and Performance Optimization of a New DES Data Encryption Chip,” Ingrid Verbauwhede, Frank Hoornaert, Hugo J. Deman, Joos Vandewalle.  IEEE Journal of Solid-State Circuits.  Vol 23, No 3.  June 1988
•	“Security Considerations in the Design and Implementation of a New DES Chip,” Verbauwhede, Hoornaert, Deman, Vandewalle.  Conference on Encryption, 1987.
About The Designers
Zhenyu “Jerry” Liu is a graduate student at the University of Wisconsin from China.  He is interested in getting a VLSI design job and winning this contest.
David “David” Ljung is still have discussions with the University of Wisconsin on whether he has graduated yet.  In August he will begin work for Hewlett-Packard on the HPPA processor design team.