Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!gatech!mit-eddie!baldwin
From: baldwin@eddie.MIT.EDU (Robert W. Baldwin)
Newsgroups: sci.crypt
Subject: Re: DES info wanted
Message-ID: <5747@eddie.MIT.EDU>
Date: Thu, 7-May-87 17:53:55 EDT
Article-I.D.: eddie.5747
Posted: Thu May  7 17:53:55 1987
Date-Received: Sat, 9-May-87 09:27:19 EDT
References: <2071@hoptoad.uucp> <599@umnd-cs.D.UMN.EDU>
Reply-To: ihnp4!mit-eddie!baldwin.UUCP (Robert W. Baldwin)
Followup-To: sci.crypt
Distribution: world
Organization: MIT, EE/CS Computer Facilities, Cambridge, MA
Lines: 85
Keywords: DES, UNIX
Summary: The true story of salted des

> From: pkenny1@ub.D.UMN.EDU (Pat "Hack #2" Kenny)
>1. How much is DES used and who uses it?
>3. Where is the DES implemented? I heard about it being put into those
>   instant cash machines, is that true?

	ATM machines use DES to validate the users Personal
Identification Number (password).  Your card has a number on it which
is the result of applying a DES based function to your PIN and your
account number.  When you type in your PIN, the ATM performs this
function and lets you continue if the result matches the number on the
card.  The DES function uses a secret key that is coded in the ATM's
DES circuits.  If you know this master key you can manufacture fake
ATM cards.  If you find/make an ATM that cannot speak to the bank to
verify account numbers, then you can withdraw money using the fake
card.  The situation is more complicated for inter-bank transactions
that require remote verification of the PIN.
	The link between the bank and the ATM is not encrypted.  The
machines could be designed in such a way that this is not a security
hole, but I have heard that this is not the case.  In order to make it
easier for the banks to change the behavior of ATMs, they included
features that make it possible to spoof the machine into despensing
money provided the ATM has been given a valid card and somehow ended
up in an error state (e.g., cash was not removed from the cash
drawer).

>2. Does anybody really know what the numbers in the S-Boxes are and where
>   they got them.

	Adi Shamir noticed an interesting pattern in the s-boxes, but
he has not come up with a way to exploit the pattern.  In fact, the
pattern may be a strength.  Basically, the parity of the output of
each s-box (the xor of all four bits) is almost completely controlled
by one of the input bits.  That is, if you tell me the value of just
one of the input bits, I can predict the parity of the output bits,
and I will almost always be right.  There are values for the other 5
input bits that will make me wrong, but I will be right for most of
the 32 possible values of the 5 other input bits.

>4. Does anybody know about the DES and unix, I know they use it there, but
>   how much did they change it?

	The Unix file encryption program uses a weak variant of the
Enigma cipher system which the Germans used during WWII.  The October
1984 issue (v63 n8) of the ATT Bell Labs Technical Journal (pg
1673-1683) has an article by Jim Reeds and Peter Weinberger on
breaking this cipher system.  I wrote an interactive workbench, CBW,
for break the cipher and it is about to be distributed on
mod.sources.  If you must use the Unix file encryptor, run your file
through compress or compact first.
	The Unix password hashing function is based on DES.
Basically, your password is used as the key to encrypt the constant
zero 25 times.  The result is compared against a number in
/etc/passwd, and if they match, you are let in.  More precisely, there
are 4096 variants of DES and the specific one that is used is
specified by two 'salting' characters that are in your line of the
password file.  Thus, the login program asks for your username, looks you
up in the password file to find out which variant to use, and then ask
for your password.  The password and the two salting characters are
passed to a function called crypt (not to be confused with the file
encryption program with the same name) that performs the 25 iterations
of the salted DES and returns a result that can be compared with the
'encrypted' ('hashed' would be a better term) password in your line
of /etc/passwd.
	The salting effects the expansion function, E, not the
S-Boxes, as simson@amt said, nor the initial permutation, IP, as
rotondo@ernie said.  The strength of DES depends on the details of the
S-boxes so fooling with those is a bad idea.  Changing the IP would
still allow an attacker to use DES chips to crack password files.
	A high speed implementation of the salted des transform is
available on eddie.mit.edu (ihnp4!mit-eddie) in
/usr/spool/uucppublic/fdes.tar.  This includes documentation that
explains the tricks used to get the factor of 40 increase in speed.
Most of the tricks have been published by Marc Davio, Yvo Desmedt, et
al. in the proceedings of EuroCrypt 1983.  The new trick is a
five instruction implementation of the salting.

>6. Are there any DES jokes or other names for DES?
	Does Everyone Spy?
	Do Encryption Spell (stuff) (shit) (slowly)
	Decryption Extra Simple (slow) (speedy)


		--Bob Baldwin
		baldwin@xx.lcs.mit.edu
		ihnp4!mit-eddie!baldwin.UUCP