Cryptography-Digest Digest #250, Volume #10 Thu, 16 Sep 99 21:13:03 EDT
Contents:
Re: Okay "experts," how do you do it? (Sundial Services)
Re: Okay "experts," how do you do it? (Eric Lee Green)
Re: RC4-40 Cracking (Paul Koning)
Re: Ritter's paper (Jerry Leichter)
Re: Okay "experts," how do you do it? (David Wagner)
Re: Comments on ECC (Helger Lipmaa)
Re: Okay "experts," how do you do it? (John Savard)
Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out (Ian)
Re: Example of a one way function? (John Savard)
Re: Looking for Completely-Free Strong Algorithms ("Joseph Ashwood")
Crypto 3.5 (JPeschel)
Re: The good things about "bad" cryptography ("Tony Stewart")
Re: Comments on ECC (DJohn37050)
Re: Okay "experts," how do you do it? (Scott Nelson)
Re: What is XOR? (John Savard)
What is XOR? ("entropy")
Re: Second "_NSAKey" (David Hoyt)
----------------------------------------------------------------------------
Date: Thu, 16 Sep 1999 13:40:38 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Okay "experts," how do you do it?
Roger Fleming wrote:
>
> [EMAIL PROTECTED] wrote:
> >Okay, "putup or shaddup ..." :-) :-)
> >
> >I see lots of articles, written by experts, who say that only experts
> >can evaluate the quality of a cipher ...
>
> I think you are mixing up two common statements here. It _is_ commonly said
> that only expert cryptanalysts are much good at designing new ciphers. It is
> also sometimes said that the only way we really have of evaluating security is
> to allow experts to examine the cipher for a long time.
> This isn't at all the same thing as saying that only an expert can evaluate
> the quality of a cipher; anyone can discover an attack and thereby illustrate
> a strength (or weakness) of the cipher; it's just that 'experts' are the
> people who've shown that they are pretty good at finding attacks. (And of
> course, there are other aspects to quality apart from security, that any
> programmer can quickly evaluate).
>
> >if they have the time, which
> >they usually don't unless there's a research paper in it. Yada, yada,
> >yada.
> >Okay, experts, "put up or shaddup" :-) :-) ... how do you do it?
> >How DO you determine that a cipher is or isn't a good one? How DO you
>
> You try to attack it. If a lot of people who know what they are doing look at
> it for several years and find no flaws, it is _believed_ to be pretty good;
> there are very few proofs available, just trial by fire.
> Sometimes an algorithm might be rejected as weak even though a complete attack
> hasn't been found, but because the algorithm has certain features (eg
> linearity, poor diffusion, highly regular key schedule, etc) that are known to
> be characteristic of weak algorithms. An algorithm might also be rejected as
> 'possibly secure but worthless' if it is very slow or very memory hungry,
> without any apparent compensatory advantages.
>
> >conclude that it is or isn't snake oil? What IS it that you've learned
> >that makes you qualified to pass judgement on a crypto-algorithm that no
> >one else can do the same??
>
> Passing judgement as secure is a matter of consensus over time, NO one person
> can do it.
> Passing judgement as insecure just requires an attack; ANYone can do it, you
> don't need any qualifications. It's just that the people good at doing attacks
> come to be considered experts.
> If you want to learn more about finding attacks, you'll find a self-study
> course at
> http://www.counterpane.com/self-study.html
C'mon, friend, let's be loosy-goosy here for a little while. Let's turn
the light upon exactly what those experts know that we don't. Or, to
put it another way, let's figure out what exactly it is that makes Bruce
Scheirer's opinion better than anyone else's besides the fact that he's
written a book. ;-) ;-) :-) <-!!!
Beneath my cavalier approach to this is a serious, hard question: what,
exactly, IS it that makes an expert an expert? And therefore, what IS
it that makes a cipher insecure when it appears, to a designer or to a
common layman, to be perfectly adequate? Why exactly IS it that one
carbon-based computer known as Bruce Scheirer, or John Savard, or
(whomever) has some element of knowledge that no one else has?
If we knew, then we could build provably better ciphers. We could
evaluate them whether or not the "experts" had the time or the research
or the research-papers to do it. We could "give them nothing to
evaluate."
It seems to me that we ought to be able to subject a cipher to an
objective test. We should not be in the situation of having to evaluate
-any- expert's judgement because that is no more (and no less) than a
human judgement and therefore it is flawed. We could be victims of
false-confidence just as easily as having our hopes of security secured,
now aren't we??
The -only- way we can know these things for sure is when they are
measurable and objective. And this world of mystery and "experts" is
anything but that, now isn't it?
:-/
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: Thu, 16 Sep 1999 13:41:15 -0700
Sundial Services wrote:
>
> Okay, "putup or shaddup ..." :-) :-)
>
> I see lots of articles, written by experts, who say that only experts
> can evaluate the quality of a cipher ... if they have the time, which
> they usually don't unless there's a research paper in it. Yada, yada,
> yada.
>
> Okay, experts, "put up or shaddup" :-) :-) ... how do you do it?
>
> How DO you determine that a cipher is or isn't a good one? How DO you
> conclude that it is or isn't snake oil? What IS it that you've learned
> that makes you qualified to pass judgement on a crypto-algorithm that no
> one else can do the same??
Well, I'm not an expert (and don't pretend to be one), but what I've
seen most of the "real" experts say is that an algorithm is strong only
if it resists attack from a variety of other "real" experts (well, if it
doesn't resist attack by talented amateurs or even not-so-talented
amateurs such as myself then obviously it is crud, but resisting attack
by me only means that total novices cannot crack it, not that the NSA
can't read it as easily as plain text).
The basic problem is that talented amateurs invent new algorithms on a
daily basis, and nobody could ever analyse them all. Thus algorithms
tend to get analysed only when a) there is some kind of contest such as
the AES contest that will result in major future sales, or b) the
algorithm has been adopted or proposed to be a standard, or c) the
algorithm has been adopted for a popular application or set of
applications, and thus attracts large-scale attention. (Possibly
unwanted attention, if the application turns out to be easily broken
:-( ). MSCHAP-80, for example, was broken when part (c) happened, to
Microsoft's chagrin.
Whoops, I forgot part (d), which is when you pay the "real" experts real
money to cryptanalyse your product prior to its release. Depending upon
the importance of the crypto component of your product, that may be
money well spent (or maybe not). I know that Microsoft probably wishes
today that they'd hired Bruce to cryptanalyse MSCHAP-80 prior to its
release...
--
Eric Lee Green http://members.tripod.com/e_l_green
mail: [EMAIL PROTECTED]
^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: RC4-40 Cracking
Date: Thu, 16 Sep 1999 16:46:32 -0400
yoni wrote:
>
> Can you help me clarify something ?
>
> When you refer to Cracking the RC4 you mean a "brute force" attack ?
> simply try all possible combinations of the key ?
Yes.
> Do you use a known plaintext attack ?
That's most straightforward. A probable plaintext attack
also works. (For example, Deep Crack supports either for DES.)
> RC4-40 is RC4 initialized with 40 Bits key (5 bytes)?
Yes.
paul
------------------------------
From: Jerry Leichter <[EMAIL PROTECTED]>
Subject: Re: Ritter's paper
Date: Thu, 16 Sep 1999 16:50:04 -0400
"I've made the assumption that the "utility function" we want
to minimize is the expected amount of compromised traffic. This is
probably an unrealistic assumption, but let's make it for the moment."
Actually, I believe this is the crux of much of your disagreement with
Mr. Ritter. You're looking at expectations - average values. For
expections, I believe your arguments are correct.
However, we must also consider what is effectively "the probability of
ruin". If AES is broken, every message sent using it is broken, and a
major - potentially immense - investment must be made to completely
replace an infrastructure based on it. On the other hand, even if a
significant fraction of Mr. Ritter's individual ciphers are broken, many
messages remain secure - and in a reasonable design for the infra-
structure, it's possible to eliminate the bad ciphers from future use
without rebuilding the entire infrastructure.
Another way of looking at this is that the cost function is highly
non-linear: As long a reasonably large fraction of Mr. Ritter's ciphers
are secure, the costs (in broken messages, in the effort needed to weed
out ciphers that have proven to be weak) are small. The cost grows very
rapidly beyond a certain point, where most combinations are breakable.
The problem with an AES, of course, is that there's only one "combina-
tion", so you get right to the extremely high cost range.
Ignoring the probability of ruin is at the heart of many bad probabilis-
tic arguments - e.g., many naive arguments about martingales, and all
sorts of bad investment strategies in the real world.
On the other hand, I think there are practical difficulties with Mr.
Ritter's approach. Even the cryptanalytic attacks known in the public
literature are sufficiently powerful to slice right through most simple
designs. The ciphers that can survive *even the attacks we know about*
are pretty rare on the ground. Where will we find a large collection of
reasonably secure ciphers to use for Mr. Ritter's scheme?
Mr. Ritter likes to design parameterized families of ciphers - a
powerful approach, and probably the only way to get a large number of
reasonable cipher designs in hand quickly. But that opens the door to
attacks against whole families.
If the collection of ciphers to be used in this scheme is fixed up
front, it will be subject to attack - and likely many ciphers will be
picked off. So there will likely have to be a mechanism to add new
ciphers to the mix. However, that opens a powerful line of attack to a
knowledgeable opponent: He can contribute (through apparently unrelated
3rd parties, of course) a large number of apparently very good ciphers
that he knows how to break. Since no one will be in a position to do
really deep analyses of many different ciphers, it's unlikely that the
"spiked" ciphers will be found: It took many years to become convinced
that DES doesn't have a trap door, and even today there are people who
retain their suspicions. (Actually, an attacker of this sort wouldn't
even have to wait for updates: He would likely be right there at the
initiation of the system, offering up a whole load of neat-looking
ciphers. It would require a big leap beyond the publically-known state
of the art in cryptography to slip a trap door into a system like AES,
which will be very closely examined by many people *and is expected to
be really strong* - so any weakness that *is* found will immediately
raise a red flag. On the other hand, it would be relatively easy to
slip many subtly spiked systems into Mr. Ritter's pool, since no one
would look at them very closely - and, besides, even if one, or many, of
the "spikes" were found, how could you distinguish that from those
ciphers just being weak because the person who proposed them wasn't
quite as good at crypto as he thought?)
-- Jerry
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Okay "experts," how do you do it?
Date: 16 Sep 1999 13:59:46 -0700
In article <[EMAIL PROTECTED]>,
Sundial Services <[EMAIL PROTECTED]> wrote:
> Or, to
> put it another way, let's figure out what exactly it is that makes Bruce
> Scheirer's opinion better than anyone else's besides the fact that he's
> written a book.
The whole point of the scientific process is that you _don't_ have
to trust Schneier's opinion any more than anyone else's. If someone
has a practical attack, it doesn't matter who he is, or whether he
is an expert; we can immediately conclude that the cipher is insecure.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: Thu, 16 Sep 1999 21:47:53 +0000
Alex wrote:
> I meant is there a mathematical proof that the time-complexity of any
> algorithm for solving an ECDLP is aymptotically at least exponential in
> the size of the finite field over which the EC is defined. The post I
> was responding to asserted that solving an ECDLP is much harder than a
> hard factoring problem of the same size, and I was wondering whether
> this assertion was absolute, or relates only to current algorithms for
> solving ECDLP's.
It cannot be more than exponential (consider exhaustive search). There's a
result by Shoup ("Lower bounds for discrete logarithms and related
problems", Eurocrypt '97, http://www.shoup.net) , which gives
sqrt-exponential lower bounds if you are restricted only to so called
generic algorithms (or, if the underlying group is sc generic group). Most
people take EC groups to be "generic". No proofs are known for this (at
least not to me).
Helger
http://home.cyber.ee/helger
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Okay "experts," how do you do it?
Date: Thu, 16 Sep 1999 22:11:27 GMT
Sundial Services <[EMAIL PROTECTED]> wrote, in part:
>Why exactly IS it that one
>carbon-based computer known as Bruce Scheirer, or John Savard, or
>(whomever) has some element of knowledge that no one else has?
I'm one of the amateurs, not one of the experts.
As David Wagner has pointed out, if a cipher is broken, that is an
objective fact.
But if a cipher is not broken, whether or not that means anything is
highly subjective: it depends on how smart we think the people are who
looked at it. So the question you've identified hasn't gone away.
People like Eli Biham, David Wagner, or Don Coppersmith, can be seen
to be "experts" on the basis of the quality of their discoveries and
publications. There's no simple trick to becoming expert in this
field, any more than there is to becoming a scientist, a surgeon, or a
trial lawyer.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Ian)
Crossposted-To: rec.arts.sf.written,alt.cyberpunk
Subject: Re: Neal Stephenson's Cryptonomicon: Crypto Cop-Out
Date: Thu, 16 Sep 1999 20:48:47 GMT
Reply-To: [EMAIL PROTECTED]
Andrea Chen <[EMAIL PROTECTED]> wrote:
>>
>> Except that it changes nothing from the present day.
>>
>> Present-day, the US could easily offer a reward on Saddam Hussein's head.
>> Some large sum of US dollars, payable in cash at a secret location or
>> whatever. With the cooperation of both sides of the exchange, one of which
>> is a government for crying out loud, tracing it isn't a realistic option.
>> The problem is that anyone who attempts to kill Saddam is likely to fail.
>
> The problem is that it's against the law to assasinate foreign
>leaders.
This isn't much of an obstacle. I recall that the US has offered
substantial rewards on peoples' heads at least a few times. Didn't they
try a large number of times to get Castro offed, to no avail? And put a
large reward on Osama Bin Laden's head, also to no avail?
>The bigger problem is people like you who think the government
>should ignore this law cause after all we're killing bad people. Yet
>this ugly, underground shit has a habit of coming back to haunt us.
What on Earth are you talking about? I didn't say that the US government
_should_ put a reward on Saddam's head! I said that if it tried, it
wouldn't likely do any good!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Example of a one way function?
Date: Thu, 16 Sep 1999 22:26:09 GMT
"I. Michael Mandelberg" <[EMAIL PROTECTED]> wrote, in part:
>Can someone point me to a one-way-function that is typically used for
>encryption?
>It ought to use a key.
A simple example of a keyed one-way function - but not a trapdoor
one-way function usable for public key encryption - would be this:
f(x) = (x encrypted with DES) XOR x
which is a keyed one-way function. It could be used in a hash
function, or for generating things like session keys. But there is no
known way to find x from f(x), even knowing the key.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Looking for Completely-Free Strong Algorithms
Date: Thu, 16 Sep 1999 15:25:50 -0700
It actually has nothing to do with replay attacks (which has already taken
care of), it's an efficiency issue the product occassionally issues
identical commands, the second of which the server simply throws away (it is
invalid data). It is not something that needs to be discussed here.
Joseph
ps Don't ask me why I chose "Go get me a head of lettuce" I think it was
because I was hungry
> That's why you use a challenge string and a sequence number as part of
> your protocol. Prevents replay attacks quite nicely.
>
> Or am I confused about what you were talking about?
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Crypto 3.5
Date: 16 Sep 1999 22:31:03 GMT
Crypto 3.5
(http://www.execpc.com/~sbd/Crypto.html)
How secure do you reckon it is?
:-)
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "Tony Stewart" <[EMAIL PROTECTED]>
Subject: Re: The good things about "bad" cryptography
Date: Fri, 17 Sep 1999 00:02:00 GMT
What if the key is hardware based and also uses rolling code technology for
communication and hashing of course?
Is this method not free from hacking even if you know the design details but
not the values of the keys???
> intelligence agency finding an attack and keeping it secret in order to
> give its home country's businesses an advantage over yours.
>
> --
> Eric Lee Green http://members.tripod.com/e_l_green
> mail: [EMAIL PROTECTED]
> ^^^^^^^ Burdening Microsoft with SPAM!
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Comments on ECC
Date: 16 Sep 1999 23:49:36 GMT
ECC systems can also be made future resilient to special purpose attacks
discovered in the future by adding new filters to domain parameter validation
and revoking any existing newly weak domain parameters. This can even be done
by a CA as a service as the domain parameters are public. It is not at all
clear that this can be done with RSA systems as it might involve updating the
portion of the system that has/uses the private key, as some of the group info
must be kept secret.
So it is very possible that ECC is MORE secure than RSA in some ways.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (Scott Nelson)
Subject: Re: Okay "experts," how do you do it?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 17 Sep 1999 00:32:03 GMT
On Thu, 16 Sep 1999 13:40:38 -0700, Sundial Services
[edited]
>
>Beneath my cavalier approach to this is a serious, hard question: what,
>exactly, IS it that makes an expert an expert? And therefore, what IS
>it that makes a cipher insecure when it appears, to a designer or to a
>common layman, to be perfectly adequate? Why exactly IS it that one
>carbon-based computer known as Bruce Scheirer, or John Savard, or
>(whomever) has some element of knowledge that no one else has?
>
>If we knew, then we could build provably better ciphers. We could
>evaluate them whether or not the "experts" had the time or the research
>or the research-papers to do it. We could "give them nothing to
>evaluate."
>
>It seems to me that we ought to be able to subject a cipher to an
>objective test. We should not be in the situation of having to evaluate
>-any- expert's judgement because that is no more (and no less) than a
>human judgement and therefore it is flawed. We could be victims of
>false-confidence just as easily as having our hopes of security secured,
>now aren't we??
>
>The -only- way we can know these things for sure is when they are
>measurable and objective. And this world of mystery and "experts" is
>anything but that, now isn't it?
>
A "good" cipher can withstand all known attacks, published
or unpublished. We can't know about unpublished attacks,
but it's startling how many new ciphers can be broken because
of a weakness to a very old, well published attack. It's like
the people who made them didn't read even read the sci.crypt FAQ,
much less study a book like applied cryptography. This isn't
the only criterion for "goodness" but a cipher will gain a
lot more acceptance a lot faster if you can list 5 or 6
attacks and it's resistance to them, then if all you can
say is "I can't break it, and I tried really hard."
I suppose an objective test of sorts is possible, you
could subject a new cipher to a predetermined set of
attacks and determine it's resistance to them. Of course,
it wouldn't cover every attack, but it would be a good
starting point. There would probably be people who thought
surviving the attacks meant a good cipher, rather than thinking
of it as a minimum standard, but it would probably still be
better than what we have now.
An "expert" is anyone who understands and can apply a large
percentage of the published attacks. Thus, Bruce is an "expert"
because he has taken the time to learn about the large number
of attacks published in the literature. You too could become
an expert by spending the time, effort, and money needed to
obtain, understand, and apply the published attacks. Since
new attacks are constantly being published, to stay an expert
requires constant effort. It's not like there's a secret
society of cryptography experts that "blesses" new members
and shuns people it doesn't like. And even an expert won't
know all the published attacks - there are simply too many.
Scott Nelson <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: What is XOR?
Date: Thu, 16 Sep 1999 23:49:45 GMT
"entropy" <[EMAIL PROTECTED]> wrote, in part:
>Sorry for the newbie-esque question, but what is XOR?
Binary addition without carries:
XOR 0 1
=============
0 0 1
1 1 0
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "entropy" <[EMAIL PROTECTED]>
Subject: What is XOR?
Date: Thu, 16 Sep 1999 19:43:22 -0400
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Sorry for the newbie-esque question, but what is XOR?
- --
a.
:::entropy:::
ktheory.com
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.5.1 for non-commercial use <http://www.pgp.com>
iQA/AwUBN+GAj+lLHfp8d083EQKmPwCgwM/Yq0LaTXX3OOqznzBYyk9FFdYAoLFQ
3XKHM8HrZd1fP1FbrSRFksea
=W59V
=====END PGP SIGNATURE=====
------------------------------
From: David Hoyt <[EMAIL PROTECTED]>
Subject: Re: Second "_NSAKey"
Date: Thu, 16 Sep 1999 20:04:55 -0500
Why didn't they just let the NSA audit their source code & build
process? That would be a whole lot more convincing than a
black box test apparatus.
david | [EMAIL PROTECTED]
"Douglas A. Gwyn" wrote:
> "Trevor Jackson, III" wrote:
> > We may not be able to determine what the actual purpose of their
> > "backup key" may have been, ...
>
> To the contrary, Microsoft *has* explained the purpose, and it
> was quite plausible (although perhaps ill-advised). The "role
> that NSA played" was, according to Microsoft, that NSA would be
> reviewing the product for export, and Microsoft didn't want to
> be forced to hand over their private key to NSA, so they
> anticipated this by providing for a second, NSA-private, key
> that could not be used to authenticate Microsoft modules but
> could be used by NSA to verify how the framework operated,
> using NSA's own (test) modules.
>
> I know I've mentioned this in previous posts; haven't they
> reached the newsgroup?
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
