/*% cc -O -o decryptdb decryptdb.c */

/*  The command above should be all you need to install this on a
 Unix system (using the vendor-supplied library functions setkey and
 encrypt, defined in Research Unix 7th Edition, BSD 4.3, and SVID.)  
 On some not-quite-Unix systems, or on Unix systems hobbled by US export
 regulations, these functions may not be available.  In that case
 get Stig Ostholm's DES implementation, available by
	ftp chalmers.se
	login: anonymous
	password: <your email address>
	binary
	cd pub/unix/des
	get des-2.2.tar.Z
	quit
  Install by
	gzcat des-2.2.tar.Z | tar xf -
	cd des-2.2/lib
	make
  (perhaps after editing makefiles in subdirectories)
  and finally compile the program below by
	cc -O -o decryptdb decryptdb.c des/lib/libdes.a
  If you have trouble with this, or have suggestions for improvements,
  send email to ehg@research.bell-labs.com.   The method is described in

@article{siamdb91,
author="Joan Feigenbaum and Eric Grosse and James A. Reeds",
title="Cryptographic Protection of Membership Lists",
year="1992",
journal="Newsletter of the International Association for Cryptologic Research",
volume="9:1",
pages="16-20"}

also available from http://cm.bell-labs.com/cm/cs/doc/91/4-12.ps.gz.

The database itself is obtained by ftp as follows
	ftp netlib.bell-labs.com
	login: anonymous
	password: <your email address>
	binary
	cd research
	get siamdb.enc
	quit

Finally, to run the program, say "decryptdb siamdb.enc Grosse".
The first argument is a pathname, the second is the search string,
which may be either the last name (spelled correctly and properly
capitalized) or a telephone number.

The membership list protected by this program is also copyrighted
by its owning organization.  So even if you break through our scheme,
you still have the lawyers to contend with.
*/

/*
 * The authors of this are Joan Feigenbaum, Eric Grosse, and Jim Reeds.
 * Copyright (c) 1991 by AT&T.
 * 
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 * 
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

/*
 * file layout:
 *
 * encr_rnd	(4 bytes, number of encrypt() rounds)
 * datstart	(4 bytes, addr of first data record)
 * key records	(24 bytes apiece, last 16 encrypted)
 * data records (each described by one or more key records)
 *
 * all numbers are 4 bytes, high byte first
 */

#define KRECLEN 24	/* length of a keyrecord */
#define KHASH	0	/* offset of hash value */
#define	KKEY	8	/* offset of crypto key for data */
#define	KPTR	16	/* offset of data address (rel to datstart) */
#define	KLEN	20	/* offset of data length */

#define ENC	0
#define DEC	1
#include <stdio.h>
#ifndef NULL
#define NULL 0
#endif
extern char *calloc(), *realloc();

long datstart;			/* start of data records in file */
FILE *kp;			/* to read key parts of file */
FILE *dp;			/* to read data parts of file */

unsigned long toc[256];		/* table of contents */
unsigned long encr_rnd;	/* number of times to encrypt() */
unsigned long makelong();
unsigned char *hash();

main(argc, argv)
char *argv[];
{
	int i;

	if(argc<3)
		error("usage: decrypt_db file searchkey...\n","");
	if((kp = fopen(argv[1], "r"))==NULL)
		error("cannot open %s\n", argv[1]);
	if((dp = fopen(argv[1], "r"))==NULL)
		error("cannot re-open %s\n", argv[1]);

	setup();
	for(i=2; i<argc; i++)
		lookup(argv[i]);
	exit(0);
}

/*
 * ingest table of contents
 */
setup(){
	unsigned char buf[4*258];
	int i;
	
	if(fread((char*)buf, 4, 258, kp)!=258)
		error("cannot parse db\n", "");
	encr_rnd = makelong(&buf[0]);
	datstart = makelong(&buf[4]);
	for(i=0; i<256; i++)
		toc[i] = makelong(&buf[8+4*i]);
}

/*
 * look up all items with key 'name'
 */
lookup(name)
char *name;
{
	unsigned char hbuf[8], buf[KRECLEN];
	int k, foundit = 0;

	memcpy((char*)hbuf, (char*)hash(name,"hash"), 8);
	
	if(toc[hbuf[0]]!=0) {
		fseek(kp, toc[hbuf[0]], 0);
		while(ftell(kp)<datstart 
		    && fread((char*)buf, 1, KRECLEN, kp) == KRECLEN) {
			k = umemcmp(hbuf, &buf[KHASH]);
			if(k==0)
				foundit += further(name, buf);
			else if(k<0)
				break;
		}
	}
	/* if(!foundit) printf("%s not found\n", name); /**/
}

/*
 * interpret a key record for key 'name'.
 * for now, just print out the record
 */
further(name, krec)
char *name;
unsigned char *krec;
{
	static char *dbuf;
	static dlen = 0; 
	int len;
	unsigned long ptr;

	cipher(&krec[KKEY], 16, hash(name,"crypto"), ENC, encr_rnd);
	ptr = makelong(&krec[KPTR]);
	len = makelong(&krec[KLEN]);
	if(len<0 || len>100000 || ptr>100000000)
		error("hash collision?\n","");
	if(dbuf==NULL)
		dbuf = calloc(1, dlen = len+1);
	if(len>=dlen)
		dbuf = realloc(dbuf, dlen = len+1);
	if(dbuf==NULL) 
		error("mem alloc trouble\n", "");
	fseek(dp, (long)datstart+ptr, 0);
	if(fread(dbuf, 1, len, dp) != len) return 0;
	dbuf[len] = 0;
	cipher((unsigned char*)dbuf, len, &krec[KKEY], ENC, 1);
	fputs(dbuf,stdout);
	return 1;
}






/* 
  Some vendors that supply encrypt() allow only the ENC direction,
  so decryptdb only uses this.
*/

unsigned long makelong();
unsigned char *hash();




/* Here are a couple functions to crunch the search key into 8 bytes ready
   for DES.  When we used purely DES, there were problems because distinct
   search keys commonly share a prefix (think about phone numbers of
   people in a math department).
*/

unsigned long
hashasu(key)
char *key;
{
	unsigned long h;

	h = 0;
	while (*key != 0) {
		h = 65599 * h + (unsigned char)*key;
		key++;
	}
	return(h);
}


unsigned long
hashpjw(key)
char *key;
{
	unsigned long h;

	h = 0;
	while ((unsigned char)*key != 0) {
		h = (h << 4) + (unsigned char)*key;
		key++;
	}
	return(h);
}


/*
 * hash the 'name' string, by using it as key for encryption of 'param'.
 */
unsigned char *
hash(name,param)
char *param, *name;
{
	static unsigned char a[8], b[8];

	strncpy((char*)a,param,8);
	nput(hashpjw(name),b);
	nput(hashasu(name),b+4);
	cipher(a, 8, b, ENC, encr_rnd);
	return a;
}


/*
 * machine independent repn to native repn
 */
unsigned long
makelong(s)
unsigned char *s;
{
	unsigned long val;

	val =  *s++;
	val = (val << 8) +  *s++;
	val = (val << 8) +  *s++;
	val = (val << 8) +  *s;
	return(val);
}


/*
 * native repn to machine independent repn
 */
nput(val, s)
unsigned long val;
unsigned char *s;
{
	*s++ = (val>>24)&0xff;
	*s++ = (val>>16)&0xff;
	*s++ = (val>>8)&0xff;
	*s   = (val>>0)&0xff;
}

/*
 * encrypt n chars at s, using 8-char key8
 */

cipher(s, n, key8, edflag, rnds)
unsigned char *s, *key8;
int rnds;
{
	char *b, block[64], key[64];
	int c, i, j, k;
	if(n&7)error("bad block len to cipher\n","");
	
	s_pre(key8, key);
	setkey(key);

	n /= 8;
	for(i=0; i<n; i++){
		s_pre(s, block);
		b = block;
		for(k=0; k<rnds; k++)
			encrypt(b, edflag);
		for(j=0; j<8; j++) {
			c = 0;
			for(k=0; k<8; k++)
				c = c + c + *b++;
			*s++ = c;
		}
	}
}

/*
 * expand an 8 char block into a 64 bit block.
 */
s_pre(s, b)
unsigned char *s;
char *b;
{
	int c, i, j;

	for(i=0; i<8; i++) {
		c = *s++;
		for(j=0; j<8; j++) {
			*b++ = (c>>7)&1;
			c += c;
		}
	}
}

/*
 * lexicographic comparison of 8 unsigned char strings 
 * (don't seem to be in C libe)
 */
umemcmp(s,t)
unsigned char *s, *t;
{
	int i;

	for(i=0; i<8; i++){
		if(*s>*t)return 1;
		if(*s++<*t++)return -1;
	}
	return 0;
}

/*
 * bleat and die
 */
error(s,t)
char *s, *t;
{
	fprintf(stderr, s, t);
	exit(1);
}