Reverse engineering and the Clipper chip
David Boeren
David Murphy (murph...@osu.edu) wrote:
First, let me say I know VERY little about this area, everything I say is
based on hearsay.
: My questions are as follows:
: 1. How are "non-protected" chips reverse engineered? As I'm not too
: technical I'm looking for something in between "they take it apart"
: and a lab manual.
I'd imagine you try to see how it fits into the overall design, and you
set up a machine to run different inputs into the pins and record the
outputs you get. Of course there's a lot more involved, but I'd guess that's
the basics.
: 2. How are "protected chips" protected? What is different about a
: protected chip that makes the usual reverse engineering techniques
: asked for in question #1 not applicable to such protected chips?
I've only seen one such chip myself. They sealed it in some kind of resin
that hardens so that it's really hard to get the chip out without damaging
it. This alone is not sufficient for pro-level protection, but keeps out
the local joes. I've heard that on some chips it internally monitors
the inputs and if illegal inputs are detected the chip will burn itself
out, thus making it really hard to compile a list of in->out states or
analyze the chip by brute force.
: 3. What are some other "protected" chips? Are there any protected
: chips inside my pc?
I highly doubt there are any such chipes in a pc. Nothing in there is
important enough to spend the money to protect it. In higher-end computers
the CPU might be protected in some manner. If you have anything, it is
probably just resin-sealed.
: 4. Have any past methods of chip protection been broken?
I'm sure they have. Probably some smart-ass figured out how to dissolve
the old kind of resin, and some other guy probably broke the authentication
scheme that some old chip was using to detect tampering. I don't know of
any specific stories, but it's a very sure bet that it's been done.
David Murphy
Recently I read in some Clipper FAQ that the chip would be
manufactured so as to make discovery of Skipjack by reverse
engineering impossible. My questions may be more appropriately
addressed to some other group as they do not specifically concern
encryption and encryption hardware but I thought this would be a good
group to start in as it relates to the security of Clipper. If these
questions have already been covered I would appreciate it if someone
could point me to an info source.
My questions are as follows:
1. How are "non-protected" chips reverse engineered? As I'm not too
technical I'm looking for something in between "they take it apart"
and a lab manual.
protected chip that makes the usual reverse engineering techniques
asked for in question #1 not applicable to such protected chips?
chips inside my pc?
Thanks
Bill Sommerfeld
1. How are "non-protected" chips reverse engineered? As I'm not too
technical I'm looking for something in between "they take it apart"
and a lab manual.
Here's my "layman's understanding". Someone who actually did VLSI
would have a better answer.
"unwrap" the chip out of the package to get to the bare silicon, and
'photograph' it with an electron microscope.
If you're dealing with a multi-layer chip, you go into a "lather (with
acid?), rinse, photograph, repeat" cycle until the 'photos' get
boring.
2. How are "protected chips" protected? What is different about a
protected chip that makes the usual reverse engineering techniques
asked for in question #1 not applicable to such protected chips?
Lots of fun things.. for instance, instead of using plastic, use a
very hard epoxy with abrasives mixed in, so that attempts to remove
the epoxy also remove a good chunk of the surface of the chip.
Include stuff on the chip which is horrendously complex, uses lots of
power, but doesn't do anything, so people waste their time analysing
it :-)
program the "interesting" stuff (in the case of Clipper, things like
the family key, the chip key, the serial number, and the S-box
equivalents) into EEPROM, where you can't easily tell the difference
between a `1' and a `0' when the chip is powered off under an electron
microscope.
3. What are some other "protected" chips? Are there any protected
chips inside my pc?
almost certainly not.
Andrew Haley
non...@nowhere.com wrote:
: All this is common knowledge:
: >2. How are "protected chips" protected?
: The Clipper chip contains two "sensitive" things AFAIK: the Skipjack
: algorithm itself, and the secret key.
: The former will without any doubt be reverse-engineered eventually
: (see above) and indeed this is anticipated.
Mumble. Maybe.
: The latter is implemented with "antifuse" technology (I think)
The Skipjack algorithm is stored in antifuses; the chip itself is just
a general purpose encryption processor, and so can be made in an
unclassified fab. Also, there are oscillators on the surfce of the
chip to make observation with electron microscopes more difficult.
Andrew.
hal
"A strong algorithm is not weakened by publications" I've seen that
printed so often I think someone ought to comment on it. The statement is
true as far as it goers. But, I submit that by publishing DES, NSA (NIST
if you like that fiction) taught a whole generation of campus types about
good block cipher design. When DES was published it kicked off an entire
industry of research and gave it direction too. The bigger fish, of
course, are all those foreign "trade organizations" who snap up anything
cryptographic that makes it way into the public domain here in the US.
By publishing you teach your competitors. In business there is some
protection through patents. Even if some countries don't honor the system
much and use the patent gazette as some kind of free research journal.
In military ventures you would like to keep your technology out of your
competitors hands while preserving it for yourself. Unfair? You bet! I
will not offer the now unfashionable argument about war fighting and how
thats the true proving grounds and all that because with all our trade
ties war is no longer necessary or viable. :-
So why should NSA publish the guts of clipper? So they can gain your
trust( actually could they ever?) and at the same time give all those
nice trade missions a few real gems for their "customer". Consider that
cryptography is just one of a long list of dual use technologies thats got
the same problem. Cheers.
W T Shaw
> "A strong algorithm is not weakened by publications" I've seen that
> printed so often I think someone ought to comment on it. The statement is
> true as far as it goers. But, I submit that by publishing DES, NSA (NIST
> if you like that fiction) taught a whole generation of campus types about
> good block cipher design.
DES? I am not impressed. Something to remember about DES, it's not such a
great block cipher if you remember that which S-boxes used make a
difference. With the wrong ones in place, it's lousy. Many years ago, I
worked extensively on S-box evaluations and several related possible
ciphers, including one which later came out as DES, I decided with the
multiple flaws involved, it was not a promising course. Choice of certain
S-boxes can build in perculiar weaknesses, a backdoor if you like that
abnormally weakens the system. But don't ask me more, find it out on your
own.
A good cipher should not rely on hand picking its innards. Personaly, I
really consider DES to be a waste of time as I am out for something that
pushes the crypto envelope. But, the herd can't be wrong, can they?
So, I eventually found a algorithm family that meets some loftier criteria.
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
wts...@htcomp.net Mac Crypto Programs
You should at least know how to use ROT13.
"Fhpprff vf n Wbhearl, Abg n Qrfgvangvba."
http://www.htcomp.net/wts/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
Boudewijn W. Ch. Visser
a...@b.com writes:
>Arguably RSA was the biggest-ever hand-over of crypto capability, but
>one could hardly keep such a simple concept secret, given its many
>civilian applications.
Hand over ? Diffie,Hellman and Merkle (re) invented it all by themselves.
And Rivest,Shamir and Adleman also published their own work.
Perhaps the NSA knew about those systems before them,but it wasn't a
hand-over.
If there's anything they regret, it is DES. IBM designed it,but NSA
certified it "OK".
Boudewijn
--
+-------------------------------------------------------------------+
|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
|Dep. of Applied Physics,Delft University of Technology |PGP-key |
+-- my own opinions etc --------------------------------------------+
Roger Fleming
h...@clark.net (hal) wrote:
[...]
> true as far as it goers. But, I submit that by publishing DES, NSA (NIST
> if you like that fiction) taught a whole generation of campus types about
DES was designed by IBM, not the NSA or NIST. Many of the basic ideas were
worked out by the Lucifer project before NIST or the NSA even became
involved. At most, the NSA gave some hints.
> good block cipher design. When DES was published it kicked off an entire
> industry of research and gave it direction too. The bigger fish, of[...]
The way I read the history, the thing that gave everything the big kick was
FEAL - because it was strongish but not quite good enough, it motivated the
lines of attack which lead to much of our present understanding of block
cipher design. The only thing FEAL owed to DES was the Feistel network,
which was completely irrelevant from the point of view of developing DC.
> So why should NSA publish the guts of clipper? [...]
After all, the NSA knows its business. It doesn't need peer review, right?
Apart from the clipper protocol flaw that was discovered by Matt Blaze.
Stanley P. Miller
a...@b.com wrote:
>
>>So why should NSA publish the guts of clipper?
>
>I would say because they are trying to force everyone to use this
>system.
>
>>Consider that
>>cryptography is just one of a long list of dual use technologies thats got
>>the same problem. Cheers.
>
>Quite right, but I doubt Skipjack will ever be used for military and
>other sensitive govt applications anyway. Any "customers" will have
>already had the sources of PGP etc etc and this got out a long time
>ago.
>
>Arguably RSA was the biggest-ever hand-over of crypto capability, but
>one could hardly keep such a simple concept secret, given its many
>civilian applications.
>
Skipjack is being used by the military. The new Defense Message System
(AUTODIN and E-Mail replacement http://www.itsi.disa.mil/dmshome.html )
uses Skipjack exclusively (DSS for signatures) for unclassified but
sensitive and secret messages.
Skipjack incorporates methods of cryptographic technology that we do not
want to provide to others desigining different cryptographic systems.
(paraphrase of what the NSA guys said at the last MISSI road show
http://beta.missilab.com:9000/MISSI/index.html )
I believe that questions raised about the S box design that NSA provided to
IBM led to differential cryptanalysis (am I wrong on this?) but can't find
the info today.
Timothy Ham
Roger Fleming wrote:
> After all, the NSA knows its business. It doesn't need peer review, right?
> Apart from the clipper protocol flaw that was discovered by Matt Blaze.
The NSA knows what its doing. I'm sure they knew about the flaw in clipper
(easier ID forge) and the subliminal channel (to leak private keys) in DSA.
Thats why it was meant for 'unclassified but sensitive' catagory. When DES
first came out, it was the same classification, wasn't it? NSA knew it all
along DES was pretty weak... Do you think the government would give us a REAL
encryption system?
David Wagner
Aww, I'm willing to believe that the NSA didn't know about the protocol
flaw in Clipper that Matt Blaze found. (Apparently the protocol was
thrown together under time pressure from the politicos -- or so I've heard,
anyhow. Time pressure makes slipups easy.)
As to the subliminal channel, some folks have pointed out that DSA is
actually optimized to minimize the bandwidth of the subliminal channel:
i.e. the NSA apparently took special precautions to make DSA "as strong
as it could possibly be". (I forget who did this work, but I think
Ross Anderson & Bart Preneel were among the names, perhaps?)
DES is not pretty weak: it's an awfully solid algorithm, actually.
Sure, there's the 56 bit key length which looks pretty painful 20 years
later... but DES has stood up to an awful lot of scrutiny. Considering
the constraints on hardware resources that the IBM/NSA folks were under,
the DES design is pretty impressive.
aa-2@deltanet.com@deltanet.com
In <wtshaw-0908...@207.17.188.133>, wts...@htcomp.net (W T Shaw) writes:
>DES? I am not impressed. Something to remember about DES, it's not such a
>great block cipher if you remember that which S-boxes used make a
>difference. With the wrong ones in place, it's lousy. Many years ago, I
>worked extensively on S-box evaluations and several related possible
>ciphers, including one which later came out as DES, I decided with the
>multiple flaws involved, it was not a promising course. Choice of certain
>S-boxes can build in perculiar weaknesses, a backdoor if you like that
>abnormally weakens the system. But don't ask me more, find it out on your
>own.
Aw, why not tell us more about the weak S-boxes? Or at least, point us
to some further info on how to determine which S-boxes would be weak,
and which would be strong?
Rahul Dhesi
>The NSA knows what its doing.
Evidence, please.
--
Rahul Dhesi <dh...@rahul.net>
"please ignore Dhesi" -- Mark Crispin <m...@CAC.Washington.EDU>
Boudewijn W. Ch. Visser
roge...@postoffice.utas.edu.au (Roger Fleming) writes:
>h...@clark.net (hal) wrote:
>[...]
>> true as far as it goers. But, I submit that by publishing DES, NSA (NIST
>> if you like that fiction) taught a whole generation of campus types about
>DES was designed by IBM, not the NSA or NIST. Many of the basic ideas were
>worked out by the Lucifer project before NIST or the NSA even became
>involved. At most, the NSA gave some hints.
True,but the fact they OK'ed made it very interesting.
>> So why should NSA publish the guts of clipper? [...]
So that people can be certain that the escrowed keys are the *only*
backdoor ?
Boudewijn W. Ch. Visser
aa...@deltanet.com@deltanet.com writes:
>Aw, why not tell us more about the weak S-boxes? Or at least, point us
>to some further info on how to determine which S-boxes would be weak,
>and which would be strong?
Biham and Shamir's Differential Cryptanalysis of the Data Encryption
Standard should give you a lot of info on weak S boxes.
Stanley P. Miller
vis...@ph.tn.tudelft.nl (Boudewijn W. Ch. Visser) wrote:
<snip>
>
>So that people can be certain that the escrowed keys are the *only*
>backdoor ?
>
>Boudewijn
>--
>+-------------------------------------------------------------------+
>|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
>|Dep. of Applied Physics,Delft University of Technology |PGP-key |
>+-- my own opinions etc --------------------------------------------+
But then we would all be forging the headers (LEAF) and the backdoor
wouldn't open anymore.
some days weren't there at all
Stanley P. Miller wrote:
> I believe that questions raised about the S box design that NSA provided to
> IBM led to differential cryptanalysis (am I wrong on this?) but can't find
> the info today.
Actually, the way I read it was that differential cryptanalysis
was first conceived in the academic world as a new and revolutionary
kind of attack. Then Eli Biham and Adi Shamir, who were apparently
instrumental in its forumulation/description, tried it on DES. Among
other things, they noticed that the S-boxes in DES "just happen" to be
optimized against differential cryptanalysis; this is why it does not
gain you much over simple brute force.
As a result, the people at IBM who designed Lucifer and worked
on DES came forward and said, yes, they knew about differential crypto,
but didn't want the concept to be made public. So, in a way, questions
about the S-boxes raised the possibility of a different approach than
any yet known...but I'm not sure whether it would be fair to say that
they "led" to differential crypto.
Then again, I haven't read _anything_ detailed about the origins
of diff. cryptanalysis...is there a source avaliable which could shed
some light on how the, er, "moment of clarity" was arrived at?
-David Molnar
Rahul Dhesi
In <320D2C...@skylink.net> some days weren't there at all
<bigd...@skylink.net> writes:
>Among
>other things, they noticed that the S-boxes in DES "just happen" to be
>optimized against differential cryptanalysis; this is why it does not
>gain you much over simple brute force.
> As a result, the people at IBM who designed Lucifer and worked
>on DES came forward and said, yes, they knew about differential crypto,
>but didn't want the concept to be made public.
The way I read it, DES fails to differential cryptanalysis if only 15
rounds are used, but 16 rounds is sufficient to make it resistant. Some
people concluded from this that the DES designers knew about
differential cryptanalysis. I concluded that they simply used a power
of 2 as the number of rounds and got lucky.
Peter Gutmann
Rahul Dhesi <dh...@rahul.net> writes:
>The way I read it, DES fails to differential cryptanalysis if only 15
>rounds are used, but 16 rounds is sufficient to make it resistant. Some
>people concluded from this that the DES designers knew about
>differential cryptanalysis. I concluded that they simply used a power
>of 2 as the number of rounds and got lucky.
They knew about differential cryptanalysis ~15 years before anyone else
did, under the name "T attack" (I'm not sure where this terminology comes
from, but Walter Tuchman and Bryant Tuckerman were two of the people involved
in designing DES, maybe one of them came up with the idea). For more
information see:
"The data encryption standard and its strength against attacks", Don
Coppersmith, IBM Journal of Research and Development, Vol.38, No.3, May 1994,
p.243.
Peter.
Marc Thibault
st...@primenet.com (Stanley P. Miller) writes:
> Skipjack is being used by the military. The new Defense Message System
> uses Skipjack exclusively (DSS for signatures) for unclassified but
> sensitive and secret messages.
>
> (NSA says) Skipjack incorporates methods of cryptographic technology that
we do not
> want to provide to others desigining different cryptographic systems.
Those two statements don't hang together. Anyone who would borrow
Skipjack technology already has algorithms that are effective for highly
classified materials. If Skipjack is not usable to that level, what could
it possibly have of interest?
Cheers,
Marc
This is not a secure channel - Assume Nothing
http://www.hookup.net/~marct
Key fingerprint = 76 21 A3 B2 41 77 BC E8 C9 1C 74 02 80 48 A0 1A
W T Shaw
> In <wtshaw-0908...@207.17.188.133>, wts...@htcomp.net (W T
Shaw) writes:
> >DES? I am not impressed. Something to remember about DES, it's not such a
> >great block cipher if you remember that which S-boxes used make a
> >difference. With the wrong ones in place, it's lousy. Many years ago, I
> >worked extensively on S-box evaluations and several related possible
> >ciphers, including one which later came out as DES, I decided with the
> >multiple flaws involved, it was not a promising course. Choice of certain
> >S-boxes can build in perculiar weaknesses, a backdoor if you like that
> >abnormally weakens the system. But don't ask me more, find it out on your
> >own.
>
> Aw, why not tell us more about the weak S-boxes? Or at least, point us
> to some further info on how to determine which S-boxes would be weak,
> and which would be strong?
Dumb singleton S-boxes are too obvious, but the answer also often revolves
the combination of certain S-boxes which are not complementary but
individually may appear fine.
Boudewijn W. Ch. Visser
Timothy Ham <ham...@erols.com> writes:
>Thats why it was meant for 'unclassified but sensitive' catagory. When DES
>first came out, it was the same classification, wasn't it? NSA knew it all
>along DES was pretty weak... Do you think the government would give us a REAL
>encryption system?
DES is only "pretty weak" to those with BIG money. When DES came out,
a brute-force attack was estimated at $100-$200 million. That's not
"pretty weak",but not strong enough for really classified data.
DES was never meant to last as long as it has,and indeed now the cost
of a brute force attack has fallen to about $1 million,which puts
it in range for a much larger group of nosy people.
Boudewijn W. Ch. Visser
st...@primenet.com (Stanley P. Miller) writes:
>vis...@ph.tn.tudelft.nl (Boudewijn W. Ch. Visser) wrote:
><snip>
>>
>>So that people can be certain that the escrowed keys are the *only*
>>backdoor ?
>>
>>Boudewijn
>>--
>>+-------------------------------------------------------------------+
>>|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
>>|Dep. of Applied Physics,Delft University of Technology |PGP-key |
>>+-- my own opinions etc --------------------------------------------+
>But then we would all be forging the headers (LEAF) and the backdoor
>wouldn't open anymore.
Wow,that is a *strong* statement :-) . You are implying that the correct
headers MUST be known in order to exploit *any* backdoor .
AFAIK,the headers are necessary in order to retrieve the escrowed keys,
but I doubt if they would be necessary to exploit any *other* backdoor
in the algorithm, which may be there and would be almost impossible
to find as long as the algorithm remains secret.
Boudewijn W. Ch. Visser
Rahul Dhesi <dh...@rahul.net> writes:
>In <320D2C...@skylink.net> some days weren't there at all
><bigd...@skylink.net> writes:
>>Among
>>other things, they noticed that the S-boxes in DES "just happen" to be
>>optimized against differential cryptanalysis; this is why it does not
>>gain you much over simple brute force.
>> As a result, the people at IBM who designed Lucifer and worked
>>on DES came forward and said, yes, they knew about differential crypto,
>>but didn't want the concept to be made public.
>The way I read it, DES fails to differential cryptanalysis if only 15
>rounds are used, but 16 rounds is sufficient to make it resistant. Some
>people concluded from this that the DES designers knew about
>differential cryptanalysis. I concluded that they simply used a power
>of 2 as the number of rounds and got lucky.
After DC became public,the DES designers said that they knew about it
and had optimized DES against it.
The contents of the S boxes and their order are also optimized against
DC. And they choose 16 rounds,while DES would look fine with 8 rounds
too,if it weren't for DC.
They surely knew about DC when designing DES. Plain luck doesn't come
in this magnitude,and FWIW,I don't think they would boldly lie.
Stanley P. Miller
vis...@ph.tn.tudelft.nl (Boudewijn W. Ch. Visser) wrote:
>st...@primenet.com (Stanley P. Miller) writes:
>
>>vis...@ph.tn.tudelft.nl (Boudewijn W. Ch. Visser) wrote:
>
>><snip>
>>>
>>>So that people can be certain that the escrowed keys are the *only*
>>>backdoor ?
>>>
>>>Boudewijn
>>>--
>>>+-------------------------------------------------------------------+
>>>|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
>>>|Dep. of Applied Physics,Delft University of Technology |PGP-key |
>>>+-- my own opinions etc --------------------------------------------+
>
>
>>But then we would all be forging the headers (LEAF) and the backdoor
>>wouldn't open anymore.
>
>Wow,that is a *strong* statement :-) . You are implying that the correct
>headers MUST be known in order to exploit *any* backdoor .
>
>AFAIK,the headers are necessary in order to retrieve the escrowed keys,
>but I doubt if they would be necessary to exploit any *other* backdoor
>in the algorithm, which may be there and would be almost impossible
>to find as long as the algorithm remains secret.
>
>Boudewijn
>--
>+-------------------------------------------------------------------+
>|Boudewijn Visser |E-mail:vis...@ph.tn.tudelft.nl |finger for |
>|Dep. of Applied Physics,Delft University of Technology |PGP-key |
>+-- my own opinions etc --------------------------------------------+
I was thinking that with the backdoor of the escrowed keys why would they
bother with another, insufficiently parinoid? Probably!
st...@primenet.com - http://www.primenet.com/~stanm
Stanley P. Miller
ma...@tanda.on.ca (Marc Thibault) wrote:
>st...@primenet.com (Stanley P. Miller) writes:
>
I was responding to what looked like two different things, skipjack being
used by the military, and why NSA wouldn't release the code.
When the goverment mandates a crypto system (and clipper has ben mandated
within the defense department) you don't have any choice, and whatever
reason they provide is "good enough" unless you wish to change employers.
Let's hope they do not mandate clipper for civilian use, think of the mess
escrowed keys are going to cause.
Dr. Nicko van Someren
In article <4un80g$q...@cyber.tn.tudelft.nl>, Boudewijn W. Ch. Visser
<URL:mailto:vis...@ph.tn.tudelft.nl> wrote:
> DES is only "pretty weak" to those with BIG money. When DES came out,
> a brute-force attack was estimated at $100-$200 million. That's not
> "pretty weak",but not strong enough for really classified data.
> DES was never meant to last as long as it has,and indeed now the cost
> of a brute force attack has fallen to about $1 million,which puts
> it in range for a much larger group of nosy people.
People keep quoting a single price for the 'cost' of cracking DES. The
measure of strength should really be in some cost times time unit such as
dollar-hours. In 1993 Wiener said that it cost 3.5 million dollar hours to
build a cracker; that is to say a machine costing $1 million would take 3.5
hours to crack a known plaintext message while am machine costing $100,000
would take 35 hours, a machine costing $10,000 whould take about 14 days and
a machine costing $100 million would take a couple of minutes. Their are
some the cost relationship is not quite this simple due to the design costs
but it is pretty close.
I think that this suggests that DES is pretty week to people who have less
than BIG money.
Nicko
--
Dr. Nicko van Someren. Vox:(44)(1223) 567808 Fax:(44)(1223) 567801
mailto:ni...@ant.co.uk http://www.ant.co.uk/~nicko
W T Shaw
In article <320fa915...@news.primenet.com>, st...@primenet.com wrote:
>
> I was thinking that with the backdoor of the escrowed keys why would they
> bother with another, insufficiently parinoid? Probably!
Given this unknown black box of an alogorithm and time to consider what
might go into it, it would be a mark of stupidity to make it so easy to
defeat by making a simple change in the data. No, consider that it could
have other modes of operation. Publishing the structure of the algorithm
should not compromize it unless that would lead to means to discover other
modes or an overlooked defect. More than likely, it is just by force of
habit not to disclose. Is it an example of a lie by omission? Maybe.
Roger Fleming
"Dr. Nicko van Someren" <ni...@ant.co.uk> wrote:
[...]
> People keep quoting a single price for the 'cost' of cracking DES. The
> measure of strength should really be in some cost times time unit such as
> dollar-hours. In 1993 Wiener said that it cost 3.5 million dollar hours to
> build a cracker; that is to say a machine costing $1 million would take 3.5
> hours [...]
Also, of course, this is for breaking just one message. Anyone who built
such a machine would likely have it running constantly.
Suppose you borrow $C (in 1993 US$) to build a Wiener machine at, say, 10%
interest. Then, on average, it will take 3.5million/C hours to crack a key,
which means it will crack about C/400 keys p.a. If the value (to you) of
all those keys is just equal to C/10 (the annual interest), the machine
will pay for itself.
Thus the "BIG money" for breaking DES keys by brute force is around forty
dollars a key.
Padgett 0sirius
In article <320fa915...@news.primenet.com> st...@primenet.com (Stanley P. Miller) writes:
>I was thinking that with the backdoor of the escrowed keys why would they
>bother with another, insufficiently parinoid? Probably!
Do not need a backdoor or a specific key if *all* of the issued keys are
known & key cannot be changed. World population is under 10^10.
A. Padgett Peterson, P.E.
Cybernetic Psychophysicist
Totally Obsessed with TransOceanics
My other car is a Pontiac too
We also walk dogs
PGP 2.7 Public Key Available
W T Shaw
In article <padgett.14...@goat.orl.mmc.com>,
pad...@goat.orl.mmc.com (Padgett 0sirius) wrote:
>
> Do not need a backdoor or a specific key if *all* of the issued keys are
> known & key cannot be changed. World population is under 10^10.
This is old thinking, key space is like virtual reality, it has no
relationship to the prior real world. Even so, there will continue to be
a flux in the population, births and dying. It is impossible for anyone
to keep a clean list of viables. You could see multiple keys, pirated
keys, stolden keys, alias keys, in fact anything that would be possible to
get around the *system*. And, then, there would be mistakes, false
accusations, missing records, bootleg certifiers, insider abuse, and out
and out fraud likely.
I would like to see the first trial where the government had to prove how
the encryption worked and disprove how it could be faked. Escrow working
with a secret algorithm is all just a contemplated trip up fool's hill.
Boudewijn W. Ch. Visser
"Dr. Nicko van Someren" <ni...@ant.co.uk> writes:
>In article <4un80g$q...@cyber.tn.tudelft.nl>, Boudewijn W. Ch. Visser
><URL:mailto:vis...@ph.tn.tudelft.nl> wrote:
>> DES is only "pretty weak" to those with BIG money. When DES came out,
>> a brute-force attack was estimated at $100-$200 million. That's not
>> "pretty weak",but not strong enough for really classified data.
>> DES was never meant to last as long as it has,and indeed now the cost
>> of a brute force attack has fallen to about $1 million,which puts
>> it in range for a much larger group of nosy people.
>People keep quoting a single price for the 'cost' of cracking DES. The
I plead guilty :-) . Yes,I know that there is a time/money tradeoff,
but the $1 mil figure is so very convenient.
>measure of strength should really be in some cost times time unit such as
>dollar-hours. In 1993 Wiener said that it cost 3.5 million dollar hours to
>build a cracker; that is to say a machine costing $1 million would take 3.5
>hours to crack a known plaintext message while am machine costing $100,000
>would take 35 hours, a machine costing $10,000 whould take about 14 days and
>a machine costing $100 million would take a couple of minutes. Their are
>some the cost relationship is not quite this simple due to the design costs
>but it is pretty close.
I think that on the low end the cost is a bit low; I guess that for a
small series of machines the design and debug cost are significant compared
to $10,000.
>I think that this suggests that DES is pretty week to people who have less
>than BIG money.
Depending on the lifetime of the data and the attacker,you are probably
right. I guess we can say that if data is worth protecting with single DES,
it is usually also worth doing it right by using 3DES.
Matt Blaze
Ian Farquhar <ia...@sydney.sgi.com> wrote:
>Peter Gutmann wrote:
>> They knew about differential cryptanalysis ~15 years before anyone
>> else did, under the name "T attack" (I'm not sure where this
>> terminology comes from, but Walter Tuchman and Bryant Tuckerman were
>> two of the people involved in designing DES, maybe one of them came
>> up with the idea).
>
>as well.
>
>Of course, it could also be using the glyph of the letter "T" as
>a rather clever graphical allusion to the actual attack.
I asked Coppersmith about this last year at Crypto. As I recall,
"T" stands for "tickle", the idea being you "tickle" the input
and observe the output.
-matt
Ian Farquhar
non...@nowhere.com wrote:
> : The latter is implemented with "antifuse" technology (I think)
VLSI Technology's Vialink process, to be precise. This was revealed
quite early in the discussion, and the technique itself is
widely published.
Andrew Haley wrote:
> The Skipjack algorithm is stored in antifuses; the chip itself is just
> a general purpose encryption processor, and so can be made in an
> unclassified fab.
I think you're mistaking the MYK-78 (formerly Clipper) for the
Capstone chip here. The Capstone was reported to contain an ARM
CPU, although it didn't implement the Skipjack algorithm itself,
and was there for general cryptographic processing.
How Skipjack was implemented in the MYK-78 has not been published
to my knowledge, but we do know that it has a 64 clock cycle
latency (across 32 rounds) and that it generates a block every
two clock cycles (when the "pipeline" is full). There is little
way that a general purpose CPU, or even a number of CPU's inside
the Clipper, could do this.
I'd bet money that it's a custom implementation of the algorithm.
I'm less certain about what the firmware is that is loaded into
ViaLink ROMs, but I expect that they are Sboxes. Without the
SBox content, you do not have a useable algorithm.
This actually brings up an interesting issue. Schneier has
suggested that Skipjack might be a 48:16 unbalanced Feistal
network.
PURE SPECULATION from this point onwards:
I tend to disagree, as there is one aspect of Skipjack which
has received surprisingly little comment: it seems very likely
that it has an 80-bit blocksize mode. This mode is used in
LEAF generation, when the current 80-bit session key is
encrypted by the unit key to generate an 80-bit encrypted block
which is then included in the LEAF. There are a couple of oblique
references in some of the early notes about Skipjack having special
modes, although this was usually in conjunction with the checksum
generation.
Just as an example: one of a number of possible configurations when
running in 64 bit mode is this:
| | | | |
+-----------|-----------|-----------|-----------+
| | | | |
| +---+ | | | |
*<--| F |<--+ +---+ | | |
| +---+ *<--| F |<--+ ----- | |
| | +---+ *<--| F |<--+ +---+ |
| | | ----- *<--| F |<--+
| | | | +---+
\ / / /
\ / / /
\ / / /
\ / / /
\ / / /
\ / / /
/ / /
/ \ / /
/ \ / /
/ ------/-----------/----\
/ / / \
/ / / \
| | | |
My guess is that Skipjack is a 4 way Feistal network of some
kind, with each "stream" being 16 bits wide. In 80-bit mode, there
is a fifth stream which is used. I've thought up of a few other
structures too (eg. balanced FN with 32 or 40 bit wide data paths and
bizarre "F" functions), but this is the one which best seems to fit
the bill for a block cipher with 64 and 80 bit selectable blocksize.
To select the 80 bit blocksize, you need a fifth stream with its
own "F" function, and a mux. That's easy to implement.
Something interesting about this structure, though: it would
be visible on the unprogrammed die and even moreso on the masks,
which are also unclassified. Assuming that the Sboxes
are the only part of the algorithm which are established in
"reverse engineering resistant" circuitry, then having the masks
or an uncapped die (with passivation removed) would likely reveal
the above. I wonder if the NSA would be willing to reveal a
structure which was different from DES, given the impetus
DES gave to the study of the properties balanced Feistal Networks?
Another interesting rumor was that Skipjack's Sboxes needed
half the storage of DES's. By this I am presuming that they
mean per "F" function, not in total, or per round. If this
is true - and please remember that this is only a rumor -
then possible configurations would be: 4 of 5:4, or 16 6:1, or
8 of 6:2. There is a rumor attributed to Denning which has
suggested that Skipjack has 16 SBoxes, and although I initially
rejected the idea of 6:1 SBoxes, there is no obvious reason
why they are invalid. This also presumes that the "F" function
is simple, and that there isn't more complex substitution or
expansion permutation happening before or after the SBoxes.
As I said, this is all pure speculation. But it's interesting
speculation. :)
> Also, there are oscillators on the surfce of the
> chip to make observation with electron microscopes more difficult.
I've heard this rumor too, but I've never found any concrete
evidence to suggest that this is the case. It is true, however,
that you would have to do something about electron microscope
analysis, otherwise you'd be able to determine the state
of the ViaFuses pretty quickly.
Ian.
Matt Blaze
[this may be a duplicate post; sorry if it is -matt]
Ian Farquhar
Peter Gutmann wrote:
> They knew about differential cryptanalysis ~15 years before anyone
> else did, under the name "T attack" (I'm not sure where this
> terminology comes from, but Walter Tuchman and Bryant Tuckerman were
> two of the people involved in designing DES, maybe one of them came
> up with the idea).
The terminology made me wonder if there were A through S attacks
as well.
Of course, it could also be using the glyph of the letter "T" as
a rather clever graphical allusion to the actual attack.
I have often wondered what the NSA calls the it. I am led
to believe that the terminologies used by the civilian and military
cryptographic communities are quite different (eg. "key" vs.
"cryptovariable"), and given that Coppersmith was told that
his "T attack" (amongst others) were reinventions of already known
design techniques, I am led to wonder what their term for it was.
Ian.