🚀 go-pugleaf

In article <a3JHwB1w165w@west.darkside.com> sspy@west.darkside.com (mshannon) writes:
>As I can't find the proper place, I will pose a few questions here in the 
>chance that they might elicit some needed answers. 
This is the proper place. (At least until sci.crypt.research is formed ;-) )

>If I may quote you, please advise, otherwise I will assume that I may 
>not.

I am publishing my personal opinions, so no gurantee of correctness
is given. You may quote me, but this won't help you :-)

>1. Is there any real, actual, documented, case of the DES having been 
>cracked through brute force alone, in ECB or CBC mode?

Not heard of.

>2. Is there any hard evidence that this has not happened and isn't likely 
>to happen within n years?

No. surely not. Chances are high that this has already happened, but did
not reach my ears. Rivest(I am not sure about the name) has shown in a
recent paper, that he can reduce the complexity of breaking DES by diffe-
rential cryptanalysis from 56 bit keyspace to 47 (or was it 41?) bit key-
space. And I am sure, the NSA has constructed one of these machines, that
contain _many_ parallel working DES-chips...

>3. Can anyone state the amount of time a given computer would need to try 
>out all of the DES key combinations? For example, the Cray Y-MP C-90 
>which is supposedly the fastest computer on Earth.

To measure this, I took another approach. I assumed a cracker would have
access to the machines which are usally for students at some universities,
technical highschools, laboratories, etc. Thus he would have access to
some hundreds normal workstations. Some colleagues and I simulated this
by a brute-force attack, which relied on 44 sun's  (model 3/60), on a specific
password. This password was encrypted by using a sort of DES, doing 25
iterations on a standard DES. (Unix crypt (3)) 
Our implementation used ufc-crypt, which is actually the fastest crypt-
implementation known to me.
A sun 3/60 is able to test 2000 keys in 10.7 seconds.
A sparc Sun-4/40 tests 2000 keys in about 2.2 seconds.
Now you can calculate how many sparcs you would need to examine a substantial
part of the keyspace:
- If somebody uses a password on a unix-machine with the length of one
to five digits, containing only a-z,A-Z, and 0-9, (62 different digits)
(that means you have to test 931'151'402 different keys) it would take
you 366.6 'sparc-hours' to examine the keyspace. Thus somebody having access
to 366 sparcs or comaparable machines, would know such a password in
about 0.5 hours (on the average) [With the machines I have access to as a
normal student, it would take me about 7-10 hours (one night) to find such 
a password with a chance of 100%]
- Using 6 digits instead of five would result in 366.6*62 sparc-hours...
So, even this one could be found by someone who has access to a large
network or some stronger computers...
- If you use the complete keyspace of 56 bits, it would take:
Assuming your average machine could test 1024 keys per second
2^46 sparc-seconds that is about 2.23 Million Sparcyears. ;-))
Now if you can figure out, how much faster a Cray YMP C-90 does an
ufc-crypt than a sparc, or how much faster a multiprocessor-machine
like MUSIC etc. would behave, then I am sure, you could reduce these
2.23 * 10^6 Sparcyears to something reasonable, even without lots of
dollars spent.

>4. Does anyone know why the DES key was REALLY changed to 56 bits?

No. I suppose NSA forced IBM to reduce the keyspace of Lucifer which
was 768 bits to a keyspace of 56 bits to protect their own interests...

>5. Does double encryption, meaning enc with key A, dec with key B then 
>enc again with key A, actually increase the resistance to attack? Can 
>anyone put numbers on this?

Yes. It's widely agreed, that this would correspond to a DES using
a keyspace of 112 bits. Somebody with more theoretical knowledge - please
back me up ;-))

>6. Is it possible to state for a known fact that there are no weaknesses 
>or trap doors, or any other ways of comprimising the DES and that no 

I can not state this, as I actually do not *know* the design-principles
of parts of the DES.

>matter how carefully the DES was designed 15 years ago, today's 
>technology would without question, reveal any such weakness?

'Without question' sounds to strong for my ears. Let's say that the open
research community (as opposed to MIL&GOV institutions) has not been able
to find a sufficent weakness which would cause DES to be considered 'broken'
in the last 15 years, and that it's unprobable that there exists such
a weakness. Somebody in this newsgroup even said,that DES was strengthened(sp?)
by it's design-principles. But I do not remember more on this topic...

I hope these statements, which just represent my own opinion will help you,
and wish you a happy new year,

		Germano Caronni




-- 
Instruments register only through things they're designed to register.
Space still contains infinite unknowns.

Germano Caronni    caronni@nessie.cs.id.ethz.ch