🚀 go-pugleaf

In article <6681@tuegate.tue.nl>, bartjan@blade.stack.urc.tue.nl (Bartjan Wattel) writes:
> Hi,
> 
> I'm currently working on a project which involves the design of a DES cryto-
> chip. When reading some papers on this subject, it appeared to me that there
> is a great need for enlarging the number of bits used in the cipher key. I read
> about an implementation of the DES with a cipher key of 768 bits in the paper
> of T.Kropf, J.Fr"ossl, W.Beller and T.Giesler: A hardware implementation of a
> modified DES-algorithm, in North-Holland Micorprocessing and Microprogramming
> 30, 1990.
> 
> Questions:
> 
>   1)  Does anybody know the reason(s) for the number of circular left shifts
>       which are performed on the cipher key each iteration in the original
>       DES algorithm ?
>   2)  Does anybody know of other modifications concerning the key size ?
>   3)  Do modifications exist which have been published or proposed by the
>       NBS, or do other (de facto) standard modifications exist ?

First of all, when adopting any sort of cryptosystem, you have to decide
who the enemy is.  Increasing the key size is useful in defending against
brute-force attacks.  The Biham/Shamir paper showed that picking all 768
bits independently did not make a significant difference in how long it took
to use differential cryptanalysis.  To me, that says that the strength
of DES, under that attack at least, is something on the close order of 56
bits.  I would not be at all surprised to learn of other attacks that
showed the same property.

There are weaknesses that come about from picking the bits independently.
Specifically, DES now has the property that changing 1 key bit will change,
on the average, 50% of the bits in the output for constant inputs.  That
wouldn't be the case with the proposed change.  Key bits near the end
of the 768 bits should be much easier to recover.

And that, in turn, brings up the reason for shifting the key bits around
to produce the 16 subkeys.  The intent is to have each key bit operate
on each plaintext bit as soon as possible.  The E-box is tied in to this,
too, and as I recall Shamir's talk it in turn interacts with the S-boxes.

I'm certainly not saying that you can't design a better cipher than DES.
But I doubt that the sort of localized tampering you're suggesting is
likely to result in a cipher that's stronger overall.  What you may
accomplish is to confound some canned techniques -- possibly even including
NSA's -- simply because the attacker has bothered to invest the upfront capital
to attack DES.  Your system may be more effective in practice, though not
stronger in theory, simply because it may not be worth attacking.

In article <6681@tuegate.tue.nl> bartjan@blade.stack.urc.tue.nl (Bartjan Wattel) writes:
>Hi,
>
>I'm currently working on a project which involves the design of a DES cryto-
>chip. When reading some papers on this subject, it appeared to me that there
>is a great need for enlarging the number of bits used in the cipher key. I read
>about an implementation of the DES with a cipher key of 768 bits in the paper
>of T.Kropf, J.Fr"ossl, W.Beller and T.Giesler: A hardware implementation of a
>modified DES-algorithm, in North-Holland Micorprocessing and Microprogramming
>30, 1990.
>
>Questions:
>
>  1)  Does anybody know the reason(s) for the number of circular left shifts
>      which are performed on the cipher key each iteration in the original
>      DES algorithm ?

They are designed to mix up the key.  As to the actual reason that particular
number was chosen...that is shrouded in mystery.

>  2)  Does anybody know of other modifications concerning the key size ?

There have been many.  None of them are any good.  Biham and Shamir showed
that DES with independent subkeys (the 768-bit key variant you mentnion) is no
more secure than DES.  Something else called GDES was also shown to be no more
secure than DES.  The security of DES seems pretty much limited to a 56-bit
key.

>  3)  Do modifications exist which have been published or proposed by the
>      NBS, or do other (de facto) standard modifications exist ?

No.

By the way, I knew about the DES-with-independent-subkeys variant, but I did
not have a reference for it.  Could you please E-Mail me with the complete
citation for the article you mentioned in your post.  A physical copy of the
article in my mailbox would be even better.

Thanks,
Bruce

*****************************************************************************
* Bruce Schneier            2,000,000,000,000,000,000,000,000,002,000,000,000 
* Counterpane Systems       000,000,000,000,002,000,000,002,293 
* schneier@chinet.chi.il.us The largest prime number...alphabetically!
* (708) 524-9461            Two vigintillion, two undecillion, two trillion,
* 730 Fair Oaks Ave.        two thousand, two hundred and ninety three.
* Oak Park, IL  60302
*****************************************************************************

In article <BzDp6F.6zn@chinet.chi.il.us>, schneier@chinet.chi.il.us (Bruce Schneier) writes:
|> >  2)  Does anybody know of other modifications concerning the key size ?
|> 
|> There have been many.  None of them are any good.  Biham and Shamir showed
|> that DES with independent subkeys (the 768-bit key variant you mentnion) is no
|> more secure than DES.  Something else called GDES was also shown to be no more
|> secure than DES.  The security of DES seems pretty much limited to a 56-bit
|> key.

I beg to differentiate! (:-)

There are two feasible attacks [on DES]: exhaustive search and differential
cryptanalysis.

While indeed Biham-Shamir attack produces a key with probability 1 with every
2^47 chosen plaintexts - how good a chance is, that your adversary can get 
that many encryption of his stuff performed on your DES engine? Or how
likely is it for him to have similar amount of known plaintexts (and
if he does have that much of it - probably there's no need for the
key anyway, all the data passed is there :-).

Thus the only practical threat left is an exhaustive search. And
I fail to understand why the DES with independent subkeys 
(760-bit key) is "limited to 56-bit key". I'd say
it's wrong, at least from practical point 
of view.
-- 
Regards,
Uri.		uri@watson.ibm.com
------------
<Disclaimer>

The differential analysis results suggest to me that the DES transformations
divide into approximately 2^47 equivalence classes.  It does not seem at all
obvious to me that using the S-box bits as a key would produce a system
with 2^768 distinct equivalence classes.  It does no good at all to have
an enormous key space if many keys produce the same transformation.
-- 
Joseph A. Reuter, Wizard-in-Training
Speaking for myself from reuter@venice.sedd.trw.com
"Olorin I was in my youth in the West that is forgotten." -- J.R.R. Tolkien
"You can't win, you can't break even, and it's the only game in town."