From ld231782@longs.lance.colostate.edu Tue Jul 13 02:48:47 1993
Received: from sparc02.cc.ncsu.edu by scss3.cl.msu.edu (4.1/4.7) id AA05907; Tue, 13 Jul 93 02:48:46 EDT
Received: from math.ncsu.edu by sparc02.cc.ncsu.edu (4.1/SYSTEMS 12-28-92 15:15:00)
id AA13106; Tue, 13 Jul 93 02:48:48 EDT
Received: from longs.lance.colostate.edu by math.ncsu.edu (4.1/SAM 07-20-90 10:07:54/m)
id AA27660; Tue, 13 Jul 93 02:47:02 EDT
Posted-Date: Tue, 13 Jul 93 00:48:38 -0600
Received: from dark.lance.colostate.edu by longs.lance.colostate.edu (5.65/lance.1.5)
id AA06410; Tue, 13 Jul 93 00:48:31 -0600
Message-Id: <9307130648.AA06410@longs.lance.colostate.edu>
To: crypt-comments@math.ncsu.edu
Cc: ld231782@longs.lance.colostate.edu
Subject: SBox descriptions
Date: Tue, 13 Jul 93 00:48:38 -0600
From: ""L. Detweiler"" <ld231782@longs.lance.colostate.edu>
X-Mts: smtp
Status: OR

This is for free, but we should email the author if we use it.


------- Forwarded Message

>From cypherpunks-request@toad.com Sat Jul 10 13:42:07 1993
Received: from relay2.UU.NET by longs.lance.colostate.edu (5.65/lance.1.5)
id AA01379; Sat, 10 Jul 93 13:42:05 -0600
Received: from toad.com by relay2.UU.NET with SMTP
(5.61/UUNET-internet-primary) id AA10495; Sat, 10 Jul 93 15:34:43 -0400
Received: by toad.com id AA08585; Sat, 10 Jul 93 12:26:47 PDT
Return-Path: <newsham@wiliki.eng.hawaii.edu>
Received: from wiliki.eng.hawaii.edu ([128.171.60.1]) by toad.com id
AA08581; Sat, 10 Jul 93 12:26:43 PDT
Message-Id: <9307101926.AA08581@toad.com>
Received: by wiliki.eng.hawaii.edu
(1.37.109.4/15.6) id AA10074; Sat, 10 Jul 93 09:24:58 -1000
From: Timothy Newsham <newsham@wiliki.eng.hawaii.edu>
Subject: Re: encrypted email software
To: mdiehl@triton.unm.edu (J. Michael Diehl)
Date: Sat, 10 Jul 1993 09:24:58 -1000 (HST)
Cc: cypherpunks@toad.com
In-Reply-To: <9307100735.AA09015@triton.unm.edu> from "J. Michael
Diehl" at Jul 10, 93 01:35:28 am
X-Mailer: ELM [version 2.4 PL21]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Length: 4032

>
>
> Could someone tell me what an s-box is? Thanx in advance.


The Data Encryption Standard (any many other crypto systems devised
since) use a process of substitutions (replacing one block of bits
with another) and permutations (re-arranging the bits). This process
is iterated a number of times and the key is mixed in at different
points.


This R This L
| |
v |
[E Expansion] |
| |
\ |
XOR <------------- key for this round (subkey) |
| |
----------------------------------- |
| | | | | | | | |
v v v v v v v v |
========================================= |
| S1 | S2 | S3 | S4 | S5 | S6 | S7 | S8 | |
========================================= |
| | | | | | | | |
----------------------------------- /
| /
[P Permutation] /
| /
\____________________________________/__
| / \
v / \
XOR <----------- |
v v
Next R Next L

This is the basic structure of DES (if I didnt make a mistake, this
is from memory). Anyway the basic idea is you take half the key
(called L and R for Left and Right, but hey, I'm lysdexic). You
put it through an expansion, this just mixes up the order of the
bits and duplicates a few of them. Then you XOR it with the sub-key
(the Key Generator is not shown). Then you split it up into 8 6-bit
chunks and do a table lookup in the S-boxes, each Sbox has 6 inputs
and 4 outputs. Then you re-arrange the bits in the P permutation.
Finally you XOR that value with the L to get next R, and put the
pre-XOR'ed value into the next L.

This is 1 iteration and is done 16 times in DES, and 16*25 times in
crypt(3). Crypt(3) also has the salt values which cause the swapping
of two bits in the E expansion for every salt bit that is set. Before
pulling apart the 64 bit input into 2 32 bit halfs (L and R) the data
is passed through an Initial Permutation (IP), and at the end of the
whole thing passed through (IP^-1) its inverse (this permutation isnt
cryptographically that significant). The subkeys are generated
by taking the input 56 bits of key, mixing them up and then successively
rotating those bits, and passing them through a permutation. It outputs
48 bits of key each iteration to match the 48 bits after the E expansion.

I hope I didnt make too many mistakes in the above discussion, but
you get the general idea.

> +-----------------------+-----------------------------+---------+
> | J. Michael Diehl ;-) | I thought I was wrong once. | PGP KEY |
> | mdiehl@triton.unm.edu | But, I was mistaken. |available|
> | mike.diehl@fido.org | | Ask Me! |
> | (505) 299-2282 +-----------------------------+---------+
> | |
> +------"I'm just looking for the opportunity to be -------------+
> | Politically Incorrect!" <Me> |
> +-----If codes are outlawed, only criminals wil have codes.-----+
> +----Is Big Brother in your phone? If you don't know, ask me---+



------- End of Forwarded Message


From msuinfo!uwm.edu!cs.utexas.edu!asuvax!ukma!mont!mizzou1.missouri.edu!C445585 Tue Jul 20 21:06:57 1993
Newsgroups: sci.crypt
Path: msuinfo!uwm.edu!cs.utexas.edu!asuvax!ukma!mont!mizzou1.missouri.edu!C445585
From: C445585@mizzou1.missouri.edu (John Kelsey)
Subject: S-box question
Message-ID: <16C11FB41.C445585@mizzou1.missouri.edu>
Sender: news@mont.cs.missouri.edu
Nntp-Posting-Host: mizzou1.missouri.edu
Organization: University of Missouri
Date: Tue, 20 Jul 93 17:52:01 CDT
Lines: 64

Did anyone ever answer the question asked about how the DES s-boxes work?

I'll try to make this fairly quick, in case I'm covering old ground....

DES is a Feistel-type cipher, which you probably know. In case you don't:
Each round, the right half of the block being encrypted (32 bits) is used,
along with 48 bits derived from the key, to generate a 32-bit value to XOR
against the left half of the block. Then, the left and right halves are
swapped. There are 16 rounds.

You can think of each round as:
L = L XOR F(R, SK_i)
SWAP L,R

The S-boxes, along with the E expansion and the P permutation, make up
the F function. The F function in a nutshell:

1. The right 32 bits are expanded to 48 bits, in effect by duplicating half
the bits. First, the 32-bits are split into groups of 4 bits, then they
become groups of 6 bits by taking the outer bits from the two adjacent
groups. This is clearer by example: Part of our input word is:

... efgh ijkl mnop ...

it becomes:... defghi hijklm lmnopq ...

2. The 48 key bits are XORed into the expanded 48 bits.

3. The resulting 48 bits are put fed into the 8 S-boxes, which output
a total of 32 bits. The S-boxes are each 6-bit to 4-bit nonlinear
substitutions. Each one is set up as 4 nonlinear substitution tables
from 4-bits to 4-bits, and the outside two bits of each 6-bit group
are used to select which of the 4 possible tables to use. (There are
4 different tables for each of the 8 S-boxes.) Each 6-bit group is
fed into a different S-box.

4. The 32-bit output from the S-boxes is permuted, so that the output
from each S-box immediately affects as many others as possible,
on the next round. The output from this permutation is the output
from the F function, and is XORed directly into the left half of the
block.

Now, in case I wasn't clear above, the S-boxes are known to everyone.
There is no secrecy there--they are part of the published specifications
of the algorithm. They are also the only place in the whole cipher where
an output bit is ever the function of more than one input bit.

Quite a bit has been written about why the specific S-boxes used in DES
were chosen. At one point, there was a lot of concern that the NSA had
pressured IBM into accepting S-boxes with some kind of "trapdoor," ie some
non-obvious qualities that made it possible for an attacker to break the
cipher. Not many people seem to beleive that now, because a new form of
cryptanalytic attack, called differential cryptanalysis, was published in
(I think) 1989, and this method could be used to break a version of DES
with weak S-boxes. However, the S-boxes used in DES were quite resistant
to differential attack. There are several articles in the Crypto '90 -
'93 and Eurocrypt '90 - '92 collections that discuss differential attacks
against DES-like ciphers, and criteria for choosing S-boxes that resist
such attacks.

Well, I hope that cleared something up. I appologize in advance if I
made any weird typos or other errors.

--John Kelsey, c445585@mizzou1.missouri.edu