Re: encrypted email software

> 
> > DES isnt secure?  And where was it that you got this precious
> > little piece of information?
> > 
> You mean to tell me you believe what your government tells you about DES?
> Come on now!  It's been public knowledge for quite some time that the NSA
> has a backdoor to DES and the FBI and other agencys know it.

Its public knowledge?
were's the proof?
Not one academic researcher has found it (and lived to publish
about it).
On the other hand some very respectable cryptographers have
been able to show that the design critereon has made for
very well chosen parameters.

The FBI has shown that they dont know a backdoor in DES or at least
they wont use it against suspects.  There have been cases were
data was encrypted with DES and the suspect refused to turn over
the keys. 

> 
> I certainly hope you were kidding! 
> 
> -- 
> Bob Tannen
> Borland International
> 1800 Greenhills Rd.
> Scotts Valley, CA. 95066
> 
> rtannen@borland.com
> RTANNEN @ BORLAND (MHS)
>

Timothy Newsham says:
> > 
> > > DES isnt secure?  And where was it that you got this precious
> > > little piece of information?
> > > 
> > You mean to tell me you believe what your government tells you about DES?
> > Come on now!  It's been public knowledge for quite some time that the NSA
> > has a backdoor to DES and the FBI and other agencys know it.
> 
> Its public knowledge?
> were's the proof?
> Not one academic researcher has found it (and lived to publish
> about it).

100% correct. Although DES is likely breakable by brute force, that
can only be done at tremendous expense. The back door notion, although
still possible, is now not believed to be true.

Perry

"Perry E. Metzger" <pmetzger@lehman.com> writes:

> 100% correct. Although DES is likely breakable by brute force, that
> can only be done at tremendous expense. The back door notion, although
> still possible, is now not believed to be true.

People first thought there was a back door because they wouldn't release 
enough info on the algorithm to give people a chance to see if they 
trusted it or not.  After it was all common knowledge, people examined 
it and came to the conclusion that it was secure, though questions are 
still around about why it was changed from 64 bit to 56 bit, which is 
also why it is believed that the NSA has computers that can break it by 
brute force in a reasonable amount of time, but nevertheless it is a 
brute force attack.

That's how I've heard (from various sources) the whole story with DES 
goes, and it seems like a reasonable one.

--
Mike Sherwood
internet: mike@EGFABT.ORG     uucp: ...!sgiblab!egfabt!mike

>> it and came to the conclusion that it was secure, though questions are 
>> still around about why it was changed from 64 bit to 56 bit, ...
	Didn't someone figure out a way that the 64 bit version would
be more vulnerable to differential cryptanalysis (which was known to
IBM as the "sliding attack" back when DES was being developed) than
the 56 bit one was? And I've heard indications that the predecessor
"Lucifer" at 128 bits had some trivial "meet-in-the-middle" attack
that left it at least as weak as 64 bits.
	The only "backdoor" concept I've heard which had a technical
basis behind it was a few years back, when some researcher figured out
a way to *produce* S-boxes with particular types of holes, and
concluded that it was impossible to identify if the holes where there
or not unless you knew the precise formulation... I think it even had
a two-of-three challenge, ie, published 3 sets of s-boxes, one or two
of which were "trapped" in this way, as a challenge for people to find
methods of locating them. (The technical basis stops there -- the
psychological or political question that follows is "did NSA/IBM know
about this technique? Assuming they did, did they choose the s-boxes
with or without holes?")

				_Mark_ <eichin@athena.mit.edu>
				MIT Student Information Processing Board
				Cygnus Support <eichin@cygnus.com>

According to Mark Eichin:
> 
> 	The only "backdoor" concept I've heard which had a technical
> basis behind it was a few years back, when some researcher figured out
> a way to *produce* S-boxes with particular types of holes, and
> concluded that it was impossible to identify if the holes where there
> or not unless you knew the precise formulation... I think it even had
> a two-of-three challenge, ie, published 3 sets of s-boxes, one or two
> of which were "trapped" in this way, as a challenge for people to find
> methods of locating them. (The technical basis stops there -- the
> psychological or political question that follows is "did NSA/IBM know
> about this technique? Assuming they did, did they choose the s-boxes
> with or without holes?")

Could someone tell me what an s-box is?  Thanx in advance.
+-----------------------+-----------------------------+---------+
| 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---+

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

> People first thought there was a back door because they wouldn't release 
> enough info on the algorithm to give people a chance to see if they 
> trusted it or not.

not the algorithm, which was public from the start, but the rationale behind
the selection of its parameters.

>                     After it was all common knowledge, people examined 
> it and came to the conclusion that it was secure, 

the rationale remains classified; some people question nsa's motivation
in keeping that aspect of des secret.  i believe nsa keeps it secret to
avoid teaching potential (or imaginary) adversaries advanced cryptographic
techniques.   (and also because keeping secrets is what nsa is all about.
they seem to be very, very good at it.)

>                                                   though questions are 
> still around about why it was changed from 64 bit to 56 bit,

you mean 112 -> 56.  this has been resolved -- it seems that longer keys
don't impose any additional complexity on des attacks.  although these
attacks were discovered by the open crypto community only a few years ago,
nsa had these techniques in hand long before.  the bottom line is that
additional key bits would not make des more secure.  double des or triple
des do.

>                                                              which is 
> also why it is believed that the NSA has computers that can break it by 
> brute force in a reasonable amount of time, but nevertheless it is a 
> brute force attack.

it has long been believed that a dedicated des-cracker is within the budget
of extremely well financed organizations.  

> That's how I've heard (from various sources) the whole story with DES 
> goes, and it seems like a reasonable one.

your story is pretty close to the spin i'm familiar with.

	peter

peter honeyman says:
> > still around about why it was changed from 64 bit to 56 bit,
> you mean 112 -> 56.  this has been resolved -- it seems that longer keys
> don't impose any additional complexity on des attacks.  although these
> attacks were discovered by the open crypto community only a few years ago,
> nsa had these techniques in hand long before.  the bottom line is that
> additional key bits would not make des more secure.  double des or triple
> des do.

Well, first - I believe DES was designed with 64 bit keys in mind,
and then due to some technical (unspecified :-) reasons he key was
shortened to 56 bits (and 56-bit version was submitted to NBS).

While longer key indeed offers little protection against attacks
like differential cryptanalysis - it's hard to argue that it can
blow brute-force attack out of the water...  And I'd be somewhat
more concerned about an adversary cracking my DES-encrypted mail
via brute force, than tapping my channel and collecting  2^45 of
plaintext-ciphertext pairs to deduce my  DES [randomly selected]
key (:-).

N'est pas?

> it has long been believed that a dedicated des-cracker is within the budget
> of extremely well financed organizations.

Well, of course a government (any government :-) could build such a
thing... After all, don't they get all those tax money? (:-)
--
Regards,
Uri         uri@watson.ibm.com      scifi!angmar!uri 	N2RIU
-----------
<Disclamer>

>> Well, first - I believe DES was designed with 64 bit keys in mind,
	and then they apparently discovered it to be sensitive to the
"sliding attack", ie. differential cryptanalysis...

>> While longer key indeed offers little protection against attacks
>> like differential cryptanalysis - it's hard to argue that it can
>> blow brute-force attack out of the water...  
	But isn't the idea differential cryptanalysis *can* blow
brute-force out of the water if the algorithm is sensitive to it, and
the symmetries that could be introduced by 64-bit DES keying might
have made it thus sensitive. It isn't just that extra key "offers
little protection", it might actually *weaken* the algorithm. (No, I'm
not an expert on DES, but I've followed the net, read the FIPS, read
Biham-Shamir, and thought about it a bit for myself.)
								_Mark_

Mark Eichin says:
> >> While longer key indeed offers little protection against attacks
> >> like differential cryptanalysis - it's hard to argue that it can
> >> blow brute-force attack out of the water...
> 	But isn't the idea differential cryptanalysis *can* blow
> brute-force out of the water if the algorithm is sensitive to it, and
> the symmetries that could be introduced by 64-bit DES keying might
> have made it thus sensitive. It isn't just that extra key "offers
> little protection", it might actually *weaken* the algorithm. (No, I'm
> not an expert on DES, but I've followed the net, read the FIPS, read
> Biham-Shamir, and thought about it a bit for myself.)

Well, to the best of my knowledge, "sliding attack" does NOT
care about the length of a key - because it deduces the
subkeys DIRECTLY. This means - one doesn't WEAKEN an
algorithm by increasing the key length, it just
doesn't help against "sliding attack"...

And in order to pull out this "sliding attack" one HAS to
have either enough of PLAINTEXT-CIPHERTEXT pairs, or even
better - to be able to run CHOSEN-PLAINTEXT attack.   How
much are you afraid of such an attack against your e-mail?
[Assuming you use one-time RSA-encrypted DES key, of
course :-]
--
Regards,
Uri         uri@watson.ibm.com      scifi!angmar!uri 	N2RIU
-----------
<Disclamer>


From cypherpunks-request  Sun Jul 11 20:17:07 1993

> The FBI has shown that they dont know a backdoor in DES or at least
> they wont use it against suspects. 

	For what it is worth, an FBI agent here in Boston once told me
a story (over lunch) about a drug case involving a seized PC with DES
encrypted files.  The FBI folks called up "some friends" at NSA, who
were able to decrypt the files.  They couldn't use the info in court
(since that would reveal what the NSA could do), but the information
was valuable to them nonetheless.

	Now, I don't know whether to believe this or not.  There was
at least one interesting detail/inconsistency in the story (he
mentioned that when they got the PC back from NSA they were somehow
able to tell by examining some file-modification times that the
decrypt had taken 12 minutes.  It's not immediately obvious to me why
this would be so.)  The guy who told me the story isn't particularly
technical; neither is he totally non-technical (at one point he told
another story about how difficult it is to explain hexadecimal to a
jury.)  I don't think he would be above a little desinformatsiya.  I
don't see what he would gain from it, other than appearing to be more
technical/powerful/in-the-know than he really is.

	That NSA can break DES is widely suspected, even if unproved.


		Cheers,


			- nick

P.s. 	The truly funny postscript to this story is that halfway
through the aforementioned lunch with this FBI fellow, I looked down
and realized I was wearing one of the hack LOD T-Shirts.  After I
finished choking on my biriyani, he wanted to know where *he* could
get one ...