“DEStiny”

UNIX password encryption on a TinyChip

Progress Report

David Ljung <ljung@cae.wisc.edu>
and Zhenyu Liu <zhenyu@cae.wisc.edu>
CS755 - VLSI System Design
April 10, 1994

Introduction
We are designing an implementation of the UNIX crypt() function in a single TinyChip (2.25mm x 2 mm) in a 2 micron technology using two layers of metallization.

Interfaces
The interfaces to our chip are very simple.  The only interfaces required are:
•	power and ground
•	external clock and external reset
•	password and salt inputs (10 bytes total per crypt)
•	encrypted password output (either 64 bits or 11 bytes)
•	(optional) function complete output

Since the crypt algorithm is so time consuming, and since the main core of the algorithm is executed 400 times, we are going to make the interface as small as possible, since speed isn’t much of a concern.  In order to do the inputs and outputs, we are going to use shift registers to load/drive one byte at a time.  The only complexity comes from the output shift, which is done in a different order.  We discovered that the final permutation of bits before output could be implemented in the shift-out registers.  Since permutations can take up a lot of space, we decided to use a shift method instead.  To understand this, we can take a look at the final permutation (IP-1):

  { 40,  8, 48, 16, 56, 24, 64, 32,
    39,  7, 47, 15, 55, 23, 63, 31,
    38,  6, 46, 14, 54, 22, 62, 30,
    37,  5, 45, 13, 53, 21, 61, 29,
    36,  4, 44, 12, 52, 20, 60, 28,
    35,  3, 43, 11, 51, 19, 59, 27,
    34,  2, 42, 10, 50, 18, 58, 26,
    33,  1, 41,  9, 49, 17, 57, 25
  };

If we shift out the bytes in the order specified by the last row, we will obtain the effect of the final permutation.
The only other complication involves a character to 6-bit translation done on the salt inputs and on the final output.  Hopefully we will be able to create this as a a small permutation so as to keep the interface as simple as possible.  In order to use the chip, the user does the following:
•	apply power and ground
•	reset the chip
•	start clock
•	for each clock, load a byte from the password, then from the salt
•	wait until the specified number of clocks (a constant we don’t know yet, it will be 400+overhead) or until the function complete signal
•	for each clock, shift out each byte of the result

Data Path
The majority of the data path follows the vertical of the floorplan.  The iteration is mainly from top to bottom, except for the key generation, which occurs at the bottom and is fed upwards over the top of the S-blocks in metal2.
We design each block of the chip seperately, since we don’t have to worry much about pitch matching.  Instead, the pitch matching can be done by slight variations of the widths of the permutations that are found between almost all the sub blocks.
Control part for each block will be at side of the block and the control signal goes vertical to the data flow.  The control signal is needed only by the key generation, the I/O and the left and right registers.

Clocking Strategy
The clocking strategy is a two phase clock as shown:

Clocking Scheme

Since we need to keep the old R register for the write into the L register, we will use an intermediate temporary register.  This won’t take up much space, and we feel that it is better than requiring a more complicated clocking mechanism

Timing Goals
One of the main issues in a crypt implementation is timing.  Our final goal is to be able to fit the crypt function in a small chip space, so our final timing results will be nowhere near the kind of results that VLSI crypt would be able to achieve.  For this reason, our main comparison will be against other software implementations.  Current ‘straight’ implementations of crypt take approximately 100ms on a RISC workstation.  A number of people have sped up the crypt algorithm in software, using mostly space-for-time trade-offs.  One of the best examples we have seen was able to run at approximately 1ms for a crypt (UNIX Password Security - Ten Years Later, David C. Feldemeier and Philip R. Karn).  We are hoping to easily surpass this speed.
Considering the timing of the designs we have completed so far, we believe that our final design will be able to do a DES iteration in approximately 50ns.  This will give us a total time (ignoring overhead) of 20µs.

Design Strategy
Our biggest concern is overall area.  Speed is a secondary issue, since we have so little room to work with.  Since our design path is vertical, we are trying to stretch each segment of the algorithm to almost the width of the chip.  This gives us the minimum total height which obviously needs to be less than the total height of the chip.  The only space we need on the side of the design path is taken up by the 9-bit counter.  The rest of the control is distributed along the length of the data path.
In general we will always sacrifice speed for space, with the hope of gaining some speed back with extra space after we have a complete design.  Our decoder for our S-blocks is a pseudo-nmos nor gate design, even though a dynamic design we tried was much faster, simply because of the area that pseudo-nmos saved us.  Hopefully we will have enough extra room to change the decoder to dynamic logic in the end, because the S-blocks are assured to be on the critical path.  
All of our registers are simple six transistor, static logic registers.  Since we never need to select between a set of registers (our registers are all single registers in a single datapath) we only need to have a write-enable, and the read is always enabled (transparent).  This actually helps us with our timing, since we can’t afford the space for edge-triggered designs.  Instead, our register writes occur at the end of the clock high.  We then have to make sure that the minimum time to propagate through the cycle that the register is on is more than the width of the clock high (otherwise we will write in two iterations when we want one).
Another space saver we are working on are the xor blocks.  The xor (modulo 2 addition) function is used many times throughout the algorithm.  We are working on a 6 transistor switch-logic implementation to avoid the 12 transistor complimentary logic xor.
As described in our data path, we put the subkey generator at the bottom of the chip.  This was done because we hadn’t used metal2 in the S-blocks, so it wouldn’t be hard to pass the key over the top, but it would have been difficult to generate the keys in the middle of the chip and have to pass the result of the E permutation over the key generator and still keep within the width of the chip.
We started to design some of the permutations, but we stopped when we realized it would be worth our time to write a tool which would optimize the permutations using row-sharing.

Verification Strategy
We will be doing two types of verification, subblock verification and final verification.  The subblock verification can only be done through simulation.  As we build each segment of the crypt function, we will simulate and compare against the behavioral model that we have written in C.  The behavioral model was written using the same segments that we are going to be designing, so comparison will be fairly trivial.
After completing the design, we will do final verification on the entire design, as well as on the chip if we are able to fabricate.  This will also be through comparison to the behavioral model.
Because of the nature of the crypt function, we won’t need to do an exhaustive test of inputs for our final verification.  An example of this is the fact that the crypt function is a very good pseudo-random number generator, in a sense, just by using it, it is randomly testing its own bits.

Current Project State
So far the following subprojects have been done:

S-blocks
The decoder and rom of the S-blocks have been designed using a genie generator and a tool we wrote in C.

Tools
crypt.c  (behavioral model)
A behavioral model was created which is included at the end of this report.

blk.c  (s-block bit creator)
To facilitate the creation of the S-blocks, we created a C program that generated the array that the genie program used to build the rom.

Key Logic
The initial design of the key register and some of the key shift logic is complete.

“DEStiny”

UNIX password encryption on a TinyChip

Project Plan ][

Changes from previous:	Goal section
	Floorplan
	Schedule
	Block Diagram

David Ljung <ljung@cae.wisc.edu>
and Zhenyu Liu <zhenyu@cae.wisc.edu>
CS755 - VLSI System Design
April 10, 1994

Goals
After further consideration and design of our project we have given ourselves clearer goals of what we can realistically expect to complete.  Previously, we had a ‘ladder’ of projects we were considering.  At this point we are aiming for one of the specific projects, that of implementing the UNIX crypt() function in a single chip.  We have found that because of size restrictions, it is unlikely that we will be able to fit anything more complex into a single chip.  We are also fairly sure that we can complete the crypt function in the time allotted.

Architecture
The crypt function uses a variation of the DES algorithm.  Both algorithms are described here.  The crypt algorithm is implemented in our behavioral model.

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 encypted 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

A DES iteration is as shown:

Iteration of the DES algorithm

This iteration is performed 400 times for crypt (for 25 times the DES 16 iterations).  The function used in the iteration 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 DES double-iteration is performed 200 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.

Preliminary Floor Plan

Schedule and Responsibility

Our schedule (in chronological order) with job duties is as follows:

What	Who	Done	Date	
Research crypt algorithm	D&Z	X	4/1	
Behavioral model	David	X	4/7	
Improve our initial floor plan	Zhenyu	1/2	(cont.)	
Develop sections:				
permutations (optimized)	David		4/21	
adders	Zhenyu		4/17	
S blocks	Zhenyu	X	4/10	
Key Scheduling	David	1/2	4/17	
registers	Zhenyu	X	4/4	
global routing	D&Z		4/28	
I/O	D&Z		5/7	
control	D&Z		5/2	
Testing	D&Z		(cont.)	
Final report	D&Z		5/13	

Behavioral Model

file: crypt.c

/*#define DEBUG
/*
 * Behavioral model for the DEStiny chip
 *
 * DEStiny is an implementation of the crypt()
 * algorithm of DES encryption
 * It is being created as a project for CS755 by Zhenyu
 * Liu and David Ljung
 *
 * Code written by David Ljung, 3/25/94
 *
 * Tables were taken from simple_crypt.c by Michael 
 * Glad (glad@daimi.aau.dk)
 * (Copyright 1992 under GNU Public License)
 *
 * I used integer tables for bits instead of a more 
 * packed representation
 * for the sake of clarity, and to be more analogous to 
 * a VLSI representation
 *
 */

/* Includes
 */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>  /* for crypt(), for final comparison */

/* Tables
 */

/* Expansion table (32 to 48) */
int E_p[48]=
{32,1,2,3,4,5,4,5,6,7,8,9,
8,9,10,11,12,13,12,13,14,15,16,17,
16,17,18,19,20,21,20,21,22,23,24,25,
24,25,26,27,28,29,28,29,30,31,32,1};

/* Permutation Choice 1 for subkey generation (64/56 to 56) */
int PC1_p[56]=
{57,49,41,33,25,17,9,1,58,50,42,34,26,18,
10,2,59,51,43,35,27,19,11,3,60,52,44,36,
63,55,47,39,31,23,15,7,62,54,46,38,30,22,
14,6,61,53,45,37,29,21,13,5,28,20,12,4};

/* Permutation Choice 2 for subkey generation (56 to 48) */
int PC2_p[56]=
{14,17,11,24,1,5,3,28,15,6,21,10,
23,19,12,4,26,8,16,7,27,20,13,2,
41,52,31,37,47,55,30,40,51,45,33,48,
44,49,39,56,34,53,46,42,50,36,29,32};

/* Number of rotations for the iteration of key scheduling */
/* The concept of a table here doesn't fit our behavioral model */
/* This will be logic in our final design */
int keyrots[16]={1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};

/* Selection blocks
 * There are 8 sblocks, each of which is referenced by a 2 bit value
 * which picks the row, and a 4 bit value which picks the column
 * This number is then the 4 bit output for that select block
 */
int sblocks[8][4][16]=
{{{14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7},
{0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8},
{4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0},
{15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13}
},

{{15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10},
{3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5},
{0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15},
{13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9}
},

{{10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8},
{13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1},
{13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7},
{1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12}
},

{{7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15},
{13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9},
{10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4},
{3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14}
},

{{2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9},
{14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6},
{4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14},
{11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3}
},

{{12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11},
{10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8},
{9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6},
{4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13}
},

{{4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1},
{13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6},
{1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2},
{6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12}
},

{{13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7},
{1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2},
{7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8},
{2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11}
}
};

/* Permutation P for after sblocks */
int P_p[32] =
{16,7,20,21,29,12,28,17,1,15,23,26,5,18,31,10,
2,8,24,14,32,27,3,9,19,13,30,6,22,11,4,25};

/* Inverse permutation of IP for end
 * Temporary - the true behavior will be implemented in a shift out register
 * (Look at the pattern obvious in an 8x8 layout)
 */
int IPinv_p[64] =
{40,8,48,16,56,24,64,32,
39,7,47,15,55,23,63,31,
38,6,46,14,54,22,62,30,
37,5,45,13,53,21,61,29,
36,4,44,12,52,20,60,28,
35,3,43,11,51,19,59,27,
34,2,42,10,50,18,58,26,
33,1,41,9,49,17,57,25};

/* Code
 */

/* header
 * Print out a header for print_bits
 * For debugging/testing
 */
header(amt)
  int amt;
{
  int i;
  if(amt/10>0) {
    for(i=1;i<=amt;i++) 
      if(i/10>0 && i/10*10==i) printf("%d",i/10);
      else printf(" ");
    printf("\n");
  }
  for(i=1;i<=amt;i++) fprintf(stdout,"%d",i-i/10*10);
  fprintf(stdout,"\n");
}

/* print_bits
 * Prints out the bits of a string in binary format
 */
print_bits(s,amt)
  int *s,amt;
{
  int i;

  for(i=0;i<amt;i++) fprintf(stdout,"%d",s[i]);
  fprintf(stdout,"\n");
}

/* pr_bits
 * print bits in hex format (to compare to simple_crypt.c)
 * Thanks to Mike Glad
 */
pr_bits(s,amt)
  int *s,amt;
{
  int i,j,x;
  amt/=8;
  for(i=0;i<amt;i++) {
    x=0;
    for(j=0;j<8;j++)
      x|=s[i*8+j]<<(7-j);
    printf("%02x ",x);
  }
  printf("\n");
}

/* permute
 * output=permutation(input)
 * the permutation tables start at bit 1, so we need to subtract 1
 */
permute(by,amt,in,out)
  int *by,amt,*in,*out;
{
  for(amt--;amt>=0;amt--)
    out[amt]=in[by[amt]-1];
}

/* do_sblocks
 * Convert the 48 bit value into 32 bits with the selection blocks
 */
do_sblocks(in,out)
  int *in,*out;
{
  int i,j,val;

  for(i=0;i<8;i++) {
    val=sblocks[i] [ in[i*6]<<1 | in[i*6+5] ]
                   [ in[i*6+1]<<3 | in[i*6+2]<<2 |in[i*6+3]<<1 |in[i*6+4] ];
    out[i*4]=val>>3&1;
    out[i*4+1]=val>>2&1;
    out[i*4+2]=val>>1&1;
    out[i*4+3]=val&1;
  }
/*
printf("Before SB: "); pr_bits(in,48);
printf("After SB:  "); pr_bits(out,32);
*/
}

/* load_salt
 * load the salt mask with the salt bits
 *
 * We either need to figure out a good VLSI 
 * implementation of ascii_to_bin
 * or else just take the salt as the converted 12 bits 
 * and not 2 chars
 * hmm..  we also need bin_to_ascii - for output
 */
#define ascii_to_bin(c) (c>='a'?(c-59):c>='A'?(c-53):c-'.')
#define bin_to_ascii(c) (c>=38?(c-38+'a'):c>=12?(c-12+'A'):c+'.')

load_salt(saltmask,salt)
  int *saltmask;
  char *salt;
{
  int tot,i;

  tot=ascii_to_bin(salt[0]) | (ascii_to_bin(salt[1])<<6);

  for(i=0;i<12;i++)
    saltmask[i]=tot>>i&1;

#ifdef DEBUG
printf("Salt mask: "); print_bits(saltmask,12);
#endif
}

/* salt
 * the salting function
 * switch bits according to salt
 */
do_salt(bits,saltmask)
  int *bits,*saltmask;
{
  int i,t;

  for(i=0;i<12;i++)
    if(saltmask[i]) {
      t=bits[i];
      bits[i]=bits[24+i];
      bits[24+i]=t;
    }
}

/* load the intermediate key with the password bits permuted by PC1
 *
 * bit 1 is MSB of first char
 */
load_key(ikey,password)
  int *ikey;
  char *password;
{
  int i,j;
  int tmp[64];

  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      tmp[i*8+j]=(password[i]>>(6-j)) &1;

  permute(PC1_p,56,tmp,ikey);
#ifdef DEBUG
  printf("Password bits: "); pr_bits(tmp,64);
  printf("Intermediate key: "); pr_bits(ikey,56);
#endif
}

/* generate a subkey for iteration: iter
 * the subkey is kept in the same memory space, so
 * subsequent calls will be destructive to the last 
 * subkey.
 * This also means that subkey() counts on the memory 
 * space being unchanged.
 * This call will change the intermediate key (by a 
 * rotate)
 *
 * (It would be more efficient to generate the 16 
 *  subkeys at once and save them, but this should be 
 *  close to the behavior of the chip, which can do 
 *  this in parallel)
 */
int *subkey(ikey,iter)
  int *ikey,iter;
{
  static int sub[48];
  int rots,i,tmp0l,tmp1l,tmp0r,tmp1r;

  rots=keyrots[iter];  /* number of rotates - 1 or 2 */

  tmp0l=ikey[0];
  tmp1l=ikey[1];
  tmp0r=ikey[28];
  tmp1r=ikey[29];
  for(i=0;i<28-rots;i++) {
    ikey[i]=ikey[i+rots];
    ikey[28+i]=ikey[28+i+rots];
  }
  if(rots==2) {
    ikey[26]=tmp0l;
    ikey[27]=tmp1l;
    ikey[54]=tmp0r;
    ikey[55]=tmp1r;
  } else {
    ikey[27]=tmp0l;
    ikey[55]=tmp0r;
  }
  permute(PC2_p,48,ikey, sub);
  return sub;
}

/* xor
 * src1 <- src1 xor src2
 */
xor(src1,src2,num)
  int *src1,*src2,num;
{
  int i;

  for(i=0;i<num;i++)
    src1[i]=(src1[i]^src2[i]) & 1;
}

/* do_f
 * does the function "f"
 * input: 32 bits   output: 32 bits
 * needed params: intermediate key, salt mask
 */
do_f(in,out,iter,ikey,saltmask)
  int *in,*out,iter,*ikey,*saltmask;
{
  int i,tmp48[48],tmp32[32],*skey;

  for(i=0;i<32;i++) tmp32[i]=in[i];

  permute(E_p,48,tmp32,tmp48);

#ifdef DEBUG
  printf("Expansion: ");  pr_bits(tmp48,48);
#endif

  do_salt(tmp48,saltmask);

#ifdef DEBUG
  printf("After salt: ");  pr_bits(tmp48,48);
#endif

  /* get the subkey for this iteration */
  skey=subkey(ikey,iter);

  /* xor with the 48 bit value */
  xor(tmp48,skey,48);

#ifdef DEBUG
  printf("Subkey[%2d]\n",iter); print_bits(skey,48);
  printf("xor:\n"); print_bits(tmp48,48);
#endif

  do_sblocks(tmp48,tmp32);
  permute(P_p,32,tmp32,out);
}

/* mycrypt
 * do encryption of password with salt
 * return the encrypted string
 * salt is assumed to be two characters, and password 
 * is assumed to be null filled to eight characters
 * (This is comparable to the control and the datapath 
 * in the chip)
 */
char *mycrypt(password,salt)
  char *password,*salt;
{
  int bits[64],outl[32],outr[32],done[64];
  int i,j,dess,iters;
  /* Used by f[i] */
  int ikey[56];     /* intermediate key (before rotates and PC2) */
  int saltmask[12]; /* salt mask for salting function */
  char answer[14];

  /* starting bits are all zeros */
  for(i=0;i<64;i++) bits[i]=0;

  load_key(ikey,password);
  load_salt(saltmask,salt);

  for(dess=0;dess<25;dess++) {

    /* do 8 times two DES rounds without the IP and IP-1 */
    for(iters=0;iters<16;iters+=2) {
/*printf("Mycrypt[%2d]: ",iters); pr_bits(bits,64);*/
      /* f[i] on right 32 bits (hold in outl) */
      do_f(bits+32,outl,iters,ikey,saltmask);
      /* xor with original left 32 bits */
      xor(outl,bits,32);

      /* f[i+1] on that result */
      do_f(outl,outr,iters+1,ikey,saltmask);
      /* xor with original right 32 bits */
      xor(outr,bits+32,32);

      /* now copy outl:outr into bits */
if(iters!=14)
      for(i=0;i<32;i++) {
        bits[i]=outl[i];
        bits[i+32]=outr[i];
      }
else
      for(i=0;i<32;i++) {
        bits[i]=outr[i];
        bits[i+32]=outl[i];
      }

/*
if(iters==14) {
  printf("End:         "); pr_bits(bits,64);
}
*/
    }

  }

  permute(IPinv_p,64,bits,done);
  printf("OUT BITS: "); pr_bits(done,64);

  answer[0]=salt[0]; answer[1]=salt[1];
  for(i=0;i<11;i++) {
    char c=0;
    for(j=0;j<6;j++) c|=done[6*i+j]<<(5-j);
    answer[i+2]=bin_to_ascii(c);
  }
  answer[i+2]='\0';

  return answer;
}

/* usage
 * Print out a usage string and quit
 * This is all just behavioral model interface
 */
usage(name)
  char *name;
{
  fprintf(stderr,"\
usage: %s <password> <salt>\n\
       password is a string up to 8 characters\n\
       salt is two characters\n\
",name);
  exit(-1); 
}

/* main
 *
 * This is all just behavioral model interface
 */
main(argc,argv)
  int argc;
  char **argv;
{
  char password[9];
  char salt[3];
  char *answer;

  if(argc!=3) usage(argv[0]);
  if(argv[2][0]=='\0' || argv[2][1]=='\0') usage(argv[0]);
  strcpy(password,"\0\0\0\0\0\0\0\0\0");
  strncpy(password,argv[1],8);
  salt[0]=argv[2][0];  salt[1]=argv[2][1];  salt[2]='\0';
  fprintf(stdout,"Encrypting [%s] with salt [%s]\n",password,salt);
  answer=mycrypt(password,salt);
  fprintf(stdout,"Comparison:\n"
                 "UNIX crypt()         mycrypt()\n"
                 "[%s]      [%s]\n",
                 crypt(password,salt),answer);
  fprintf(stdout,"\nDone.\n");
  exit(0);
}