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"" 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: 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 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!" | > +-----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