Cryptography-Digest Digest #411, Volume #9 Sat, 17 Apr 99 18:13:03 EDT
Contents:
Re: Question on confidence derived from cryptanalysis. (Terry Ritter)
Re: Extreme lossy text compression (Vernon Schryver)
Dynamic Data Dependant Key Schedule ([EMAIL PROTECTED])
Re: New drop in cipher in the spirit of TEA ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Sat, 17 Apr 1999 19:50:05 GMT
On Sat, 17 Apr 1999 15:00:25 -0400, in <[EMAIL PROTECTED]>,
in sci.crypt Geoff Thorpe <[EMAIL PROTECTED]> wrote:
>Hi there,
>
>I have been following this thread with interest, albeit silently for a
>while, and for the most part I have enjoyed the intellectual
>horn-locking, especially Terry's unconventional but often insightful
>contributions. However, good ideas can quickly get buried in slop, or
>just unmasked as reactionary drivel as they seem (IMHO) to in Mr
>Ritter's post below ...
>
>Terry Ritter wrote:
>> Sure they are. As far as I know, Schneier's point has always been
>> that cryptanalysis is the way we know a cipher's strength. I'm sure
>> he would agree that this is not proof, but I do not agree that it says
>> anything at all. The implication that cryptanalysis would like to
>> promote is indeed that of tested strength.
>
>You're contributions in this thread seem to have an emerging theme ...
>that continued testing of a cipher by cryptanalysists (presumably using
>the "current most widely recognised techniques") does not guarantee some
>absolute/quantitative strength of the cipher against any attack (which
>I'm sure we would ALL, including Mr Schneier, agree with). However you
>also seem to suggest that it gives us no indication of tested strength
>at all. And here I disagree with you.
So here we are in disagreement.
>You want to sound a cautionary note that we all risk being naive and
>over-confident in our "cryptanalytic testing" of ciphers - excellent
>point and it is well taken.
No, the point is NOT well-taken. It is ignored and brushed off as
trivial and known. Then everyone sticks their head in the sand again
until I bring it up again. This has happened for years.
>However, please do not go so far as to be
>similarly naive yourself, and to play things out to an theoretical abyss
>and expect us to follow you there.
The abyss is there. By not following, you are in it.
>History does in fact support the claim that bashing away at problems
>with the best techniques you can come up with at the time, for a period
>of time, DOES give some degree of confidence in "strength" that failing
>to do so does. Here strength is a practical measure, not a theoretical
>one.
But the only thing being "measured" here is the open, academic
analysis. The *real* experts do not play this way. We thus have no
way to understand their capabilities. The strength value measured on
academics cannot apply to the real problem.
>Now no rational person is going to tell you that RSA simply will never
>be attacked at a much better complexity than the best current factoring
>techniques. Similarly, no rational person should assure you that
>attacking DES or triple DES will never improve much beyond brute-force
>key-searches. However, I will humbly suggest to you we ARE a lot safer
>against those possibilities than similar risks with newer and less
>studied techniques - and that history and common sense DO give us the
>right to those basic assumptions contrary to the gloomy and highly
>unhelpful view you hold.
On the contrary: I have shown several different approaches which are
helpful for security even in an environment where we cannot assure
ourselves of the strength of any particular cipher. What is really
gloomy and unhelpful is this insistence that the only thing we can do
is wait for the "experts" to certify a cipher so we can use it.
We hit on a cipher as hard as we can and then assume it to be strong
and insist that we use that one cipher because it is "better tested"
than anything new. The "better tested" part is probably true, but
unless we know the capabilities of our Opponents, it hardly matters.
We don't know how they hit, or how hard.
>A quick glance at any of the big mathematical problems in history,
>particularly the ones that are simply stated (ie the difficulty is not
>composed even partially out of obscurity - it looks more like a brick
>wall than a maze) almost always are either not solved even today, or
>were solved using techniques much more sophisticated than those
>available to those who posed the original question and first tried to
>solve it. Indeed the classical problems have typically given rise to
>entire branches of mathematics that grew out of a pursuit of that
>problem.
>
>Fermat's Theorem is the obvious example but there are others too.
>Someone more up to date with things could clarify, but I think they were
>trying to refine Andrew Wiles' proof a little to slice a couple of
>hundred pages off it ... it simply was not solved using a ruler and
>compass and the odd quadratic here and there. And yes, as I'm sure
>you're thinking, it IS possible it can be solved with a ruler and
>compass and the occasional discriminant. But most people will be happy
>to accept that that is a lot LESS likely to happen than if I just pose a
>new simply stated differential equation and state it can't be solved in
>simple terms only to have someone prove me wrong.
>
>Techniques, understanding, and formalised mathematical frameworks evolve
>- occasionally someone does throw something new and useful in and things
>accelerate for a while, but sudden breaks solving historical problems
>with simple techniques are VERY much the exception not the rule.
I doubt that the historical record applies to ciphers in the same way
it does other problems. Nature is not deliberately trying to confuse
and hide. Cryptography has a completely different situation.
>Let me ask the following - do you disagree with the following statement;
>"History has demonstrated time and time again, that the longer a problem
>resists the attack of academics, hobbyists, and mechanics - the
>probability the problem can be broken using simple techniques that were
>available at the time the problem was posed (or even comprehensible to
>the people of that time) decreases."
Yes, I disagree. Each cipher either can or can not be solved easily.
A Boolean result is not a probability. We only get a probability when
we have a wide variety of ciphers. And then of course we still do not
know what that probability is.
>Occasionally someone invents a wheel, but divine beams of light are a
>lot less common than simple grunt-work and craftsmanship. This is also
>true of "our opponents" as you have a tendency to call them.
>
>> >Not at least trying cryptanalysis on a cipher is stupid which
>> >I'm sure you agree with.
>>
>> I do. But there is no one cryptanalysis. Indeed, there is no end to
>> it. But we do have to make an end before we can field anything. This
>> in itself tells us that cryptanalysis as certification is necessarily
>> incomplete.
>
>It is all probabilities and risk management. Mr Schneier will hopefully
>agree with me on that and I hope you do too (I hope anyone contributing
>to the crypto-frameworks I will have to use day-to-day agree with that
>also).
This is particularly disturbing: You do not know the probabilities,
and you do not know the risk, yet you would have us manage the
situation using exactly these quantities. That is mad.
I agree with a lot of handwave statements. I also take on the limits
of the handwaves which are false. I am not against cryptanalysis; I
think it should be used. I am against endowing it with mystical
powers, and I am against the implication that this is how we know the
strength of a cipher. Cryptanalysis gives us something, but not that.
In particular, cryptanalysis does not really provide the confidence
that others see in a "certified" result.
>Would you have us believe that all things that are not absolute are
>necessarily equal? God, this sounds like a debate on socialism all of a
>sudden - my humblest apologies [;-)
In ciphers, YES, I would have you so believe.
Ciphers are distinctly different from other areas of experience. The
problem is that our Opponents operate in secrecy. That means we
actually do not know when our ciphers fail. But unless we know about
failure, we cannot assess risk. Yet you and most others attempt to
interpret risk as we do in areas where we know the risk.
For example, we have some general feeling about the risk of driving
our cars because we see failure announced on the news. Everybody
knows the risk of flying because we see the disaster reported. Crypto
failure is not reported, so we assume that risk is low. That is a
faulty assumption. We do not know the risk. But in any security
analysis we necessarily must assume the risk is real.
>> Our main problem is that cryptanalysis does NOT say that there is no
>> simpler attack. It does NOT say that a well-examined cipher is secure
>> from your kid sister. Oh, many people will offer their opinion, but
>> you won't see many such a claims in scientific papers, because there
>> we expect actual facts, as opposed to wishes, hopes, and dreams.
>
>But those claims say as much as; "we've hopefully done the best we can
>with the best techniques we have and the best people we can find, and
>this one seemed to resist our best attacks the best so we can only give
>you the best assurances we can that the best chance you have is to use
>this one".
Yes, those are the formal claims. And then we see everyone putting
their eggs in the basket of a single cipher (or small fixed group of
ciphers) once again. The formal claims are not really what is being
transmitted: What people see is a "certified" cipher which everyone
should use instead of "uncertified" ciphers. In fact it is openly
argued that "uncertified" ciphers have more risk, without being able
to quantify that risk. While I would hope every cipher would get as
much analysis as it could get, the "certification" of one cipher does
not give us what we need. All it would take is a failure of that one
cipher for us to lose everything we try to protect.
>If you cannot interpret cryptanalytic conclusions in that fashion then
>you seem to miss their point.
On the contrary, if you cannot interpret the way those conclusions are
mis-taken -- even in this group, even by you -- it is you who misses
the point.
>I agree with Mr Schneier ... it is a race
>- our opponents (again using your phrase) get to see the best
>cryptanalytic techniques we have, and sometimes we get a peek (or a
>leak) at theirs ... we just do the best we can with what we've got - and
>history has shown that if we keep that up for a while, the chances of an
>about-turn due to some radical improvement in the theory decreases
>steadily.
I disagree with Schneier. I will agree that it is contest between
cryptographer and HIDDEN cryptanalyst. But it is no race because we
do not know what the hidden guys can do. This is about like calling
AES a "contest," when the rules are hidden so the winner can be chosen
in a smoke-filled back room. This is not to mention the fact that
patented ciphers were kept out, yet another decision influenced by
Schneier which just happens to benefit him. Just a coincidence.
>> Cryptanalysis does NOT give us an indication of how much effort our
>> Opponent will have to spend to break the cipher. Yet that is exactly
>> what the cryptanalytic process would like us to believe: That is why
>
>I disagree - your point of view has some merit but is no more valid than
>the polar opposite statement.
Hardly: The polar opposite does not provide a motive to alter the
usual recumbent attitude and actually change the way we do business.
Relying on any one cipher is a risk, and the extent of that risk is
not known. Because the risk is unknown, it hardly makes sense to say
that the experts have done all they can so we should trust the result.
Users should insist on having and using a wide and growing variety of
ciphers. The fact is that these ciphers cannot be as well "certified"
as any one cipher. But since "certification" cannot be complete, the
possibility of failure even in such a cipher should not be ignored.
But if one were to use that cipher in multiple ciphering along with
two others (selected, say, by a random message key), we get the best
of both worlds, at the cost of somewhat reduced throughput.
>If people devote their lives to keeping up
>to date with the literature and do their best to innovate and develop in
>full public-view, and their best attempts to break things fail for a
>period of time (and I'm talking about the crypto community as a whole
>here) then we CAN infer that that process represents a steadily
>increasing probability that it's not going to fall over tomorrow in some
>dramatic fashion. I do not mean that evolving cryptanalysis work
>provides increasing confidence in brand-new ciphers and what-not, rather
>that as one cipher builds up a catalogue of evolving cryptanalysis work
>against it that we DO have a decreasing probability that THAT cipher
>will fall over in show-stopper fashion.
We know no such thing. We have no idea how many attacks there may be
in theory, so cannot judge how many of those we know. All we know is
that we know more than we used to, which is no probability at all.
>> we have the process of: 1) design a cipher, and 2) certify the
>> cipher by cryptanalysis. As I see it, the real opportunity for
>> cryptanalysis is as part of a dynamic and interactive cipher design
>> process, as opposed to final certification.
>
>And it currently isn't? What exactly does the open publication of
>research, countless conferences, news-groups, mail-lists, web-sites,
>open-source projects, etc amount to other than a dynamic and interactive
>process?
The usual refusal to re-analyze a corrected work.
>Also, thousands of hobbyists and professionals all doing their
>damndest to break each others ciphers gives me personally some
>confidence in the value of "standing the test of time".
There is no such standing without knowing real results. We have no
idea how many tests are made, with what background and effort, and
have no idea what the results were. This "test of time" is an
illusion.
>> Thanks. I suggest you learn it by heart if you intend to depend upon
>> cryptography.
>
>I suggest that you get a little more realistic. What do you have more
>confidence in, "NT.DLL" or an established release version of the linux
>kernel? Or IIS versus Apache? (again, speaking about versions which
>aren't acknowledged by the authors as being "beta"). And no, that
>question is not rhetorical, I'm actually interested to hear your
>response.
I have no opinion. Confidence in programs is far different from
confidence in ciphers. We can "test" programs, at least to see
whether they do what we want, whether they crash, and so on. Ciphers
are fundamentally different. We can test a cipher program to see
whether it crashes, but we cannot know if it is providing the
protection we want. We do not know if the cipher has already been
penetrated and is being read by our Opponents just as easily as by the
recipient. We do not know. And without knowing, we are unable to
assess risk, or build either confidence or trust.
>As for your continued suggestion that confidence in (relative)
>conclusions reached by noted cryptanalysts is overrated and work by
>lesser mortals unfairly disregarded. In reality I think you are wrong.
>(a) If a lesser mortal finds an improvement in cracking DES keys, they
>need only publish it to sci.crypt with the header "I think I can hack
>DES keys a bit faster ..." and they will get all the attention to their
>claims they desire, and if they have the facts to back it up they
>needn't worry about anonymity.
Excuse me, but why would someone with such a breakthrough publish it
for free? Academics are paid to do their work, and paid to publish
(in fact, most professional journals expect the author's organization
to pay page fees). In a sense, academics are paid by society to give
their work away -- but exactly where is the payment for the individual
who comes up with similar advances? Why would they post it for free?
Anyone who thinks I am a greedy SOB, please feel free to look at my
pages and see the information there for free. I am not paid to do
that, nor am I compensated for "web excess bandwidth" charges for your
downloads. But, somewhere, there must be a profit to be able to
continue the work. People who do not get paid for publishing
cryptanalysis have scant motive to do it. Unfortunately, I expect
that our Opponents do indeed get paid for such work.
>(b) If someone with a track-record
>proposes a new cipher (or in my metaphor, an alteration to kernel.c in
>Linux) and someone unknown does the same, it is natural, right, and fair
>for me to regard the latter with more scepticism and the former with a
>little more of an open mind.
You are forced into a basically unscientific approach because you have
no way to measure the true strength of the designs. The very fact you
are behaving this way tells us much about whether such designs can be
trusted for what they are, or whether you would accept them being
promoted as something they really are not. You would.
>Perhaps this Darwinist philosophy is not to your liking but I'm afraid
>it fits the model. If I have a studied knowledge of shooting, am good at
>it myself, stay abreast of the most modern trends, and am widely
>respected as an expert in the field - then I am probably as good a
>person as any to suggest methods for staying out of the firing line.
But in shooting -- as in most other activities -- one knows the
result. Ciphers are fundamentally different in that one does not know
whether they are working or not.
>> This is my bit for public education.
>
>And it has been useful to provide for thoughtful debate - but I think
>you overreach to absolute conclusions to counter opposing conclusions
>that I don't think anybody is actually making.
It is obvious that people are making the conclusion that cryptanalysis
is certification, for there has been no effort to construct protocols
which deal with the fact that we can have no confidence in the
resulting cipher.
>> I have no modern products. I do offer cryptographic consulting time,
>> and then I call it as I see it. I also own patented cryptographic
>> technology which could be useful in a wide range of ciphers.
>
>Great - perhaps if you would benefit us all (if that is your aim) by
>describing
>(a) how you made design decisions for your cryptographic technology
>(particularly with relationship to your awareness of classical and
>modern loopholes and weaknesses you were trying to avoid).
Basically I started out in stream ciphers, and read everything I could
about them. As I recall, getting cryptographic information was far
more difficult at the time. I followed the basic path from Vernam,
and found more information about the sequence of development in the
patent literature than elsewhere. We can see an ever-increasing
complexity in the "running key generator" producing what I now call
the "confusion sequence." As far as I could tell there had been no
attempt to improve the combiner itself, and there was some feeling
that a reversible nonlinear combiner was a contradiction in terms.
But I did in fact find a new concept: Dynamic Substitution, which I
patented and now own.
A stream cipher also needs an efficient confusion source, so I
embarked on a survey of RNG technology. You can read about that in my
Cryptologia article on my pages. From among the various schemes I
selected the Additive RNG as being fast, and capable of expansion.
For the first version, I found a primitive mod-2 polynomial of degree
11,213 and so constructed an RNG holding about 44K of state. I also
innovated a new nonlinear filter to protect the RNG. The resulting
CLOAK cipher used two levels of Dynamic Substitution, with 16 dynamic
tables in the second level, which further protects the RNG.
With respect to my work in block ciphers, I have some descriptions of
the tests I have used, and the results found, on my pages. In
particular, I think the use of nonlinear complexity measurements to
show the expected distribution for a larger block constructed out of
smaller blocks and mixing, is fairly persuasive. Not proof, of
course, but we already talked about that.
>(b) what kind of analysis has been (or could be) done on the/those
>technology(ies).
My new technologies have been ignored by academia, even when formally
published in Cryptologia. Schneier has said that this is normal for
patented technology. Of course, academics are compensated for the
work they do; I am not.
The fact that my work is not addressed probably has negative
consequences for me. But it also means that academia has no
background for dealing with these structures beyond what I have
personally published. That may be insufficient, but it is all there
is.
>(c) how you would convince anybody that your ideas merit some degree of
>trust/faith/use/investment.
Jeez, I'm a technical guy (much to my loss I'm sure). I deliberately
do not try to convince people. I do try to make information available
for people to use. But as you imply most people are not able to use
that information, and don't want to, but do want me to give them
confidence in whatever cipher they are using. Alas, I know there is
no such confidence, so I have no confidence to give them. They
generally find this disturbing.
>Do you expect us to assume that even though the winning AES candidate
>will have been subjected to very deep analysis by vary many parties of
>very different angles of vested interest/disinterest, because it COULD
>be broken tomorrow it is has no more measurable "strength" than a
>boutique new idea which has not been widely distributed and tested? The
>fact two things are neither black or white does not imply they are the
>same shade of grey.
No, it implies that they have the same unknown risk: That of complete
exposure. To not use one because we are afraid of that risk and then
use the other which may have the same outcome is foolish.
>> I see no problem with someone promoting what they think is an advance
>> in the field, even if they will benefit. But when reasoning errors
>> are promoted which just happen to benefit one's business -- in fact, a
>> whole sub-industry -- some skepticism seems appropriate. Just once I
>> would like to see delusions promoted which produce *less* business.
>
>You call them "delusions", I call them "reasoned and qualified critiques
>open to public dissemination and review" - let's call the whole thing
>off. (as the song goes).
Which means?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Extreme lossy text compression
Date: 17 Apr 1999 15:20:49 -0600
In article <7fans2$hot$[EMAIL PROTECTED]>,
Geoffrey Teabo <[EMAIL PROTECTED]> wrote:
> ...
>Suppose I'm monitoring stories coming in off a newswire service (like
>Reuters), I'm just trying to make sure that I don't capture the identical
>news story TWICE in my database.
>
>A so-called attacker, or criminal, in this case would be trying to compose a
>news article to intentionally collide with an old news article, and supposedly
>to what purpose? The only effect would be that my system would IGNORE the new
>phony story anyway!!!!! How ironic!
>
>So clearly my ONLY concern is that a new VALID and REAL news story would
>appear with the same hash result as the hash result of ANOTHER DIFFERENT and
>OLDER news story. That would be really BAD because I'd be ignoring a VALID
>story.
In that case, why not do the standard, ancient, obvious thing? Pick a
fast, reasonable hash function, and keep an online database of all messages
keyed by their hash values. Then as each message arrives, compute its
hash value, and look up the hash value in your database. If there is a
record with that hash value, then compare the new message with the record.
If appropriate, let the comparison be "fuzzy' (and if so, remember to make
the hash function use the fuzzy value of the message). If the new message
matches the existing record, you have a duplicate, so do whatever is
appropriate. Use whatever database is reasonable give the number of
messages you need to deal with. Given modern disks, you can easily keep
everything that a newswire carries on line for long enough.
That worked great for a spam filter on a large corporate firewall. The
system received about 200,000 email messages/day, of which between 10,000
and 14,000 were copies of 50 to 200 different streams of spam, some with
the usual spammer customizing such as "Dear sucker" or random junk
prepended or appended. Every email message passing through the system
was hashed and checked against an automatically maintained "database" of
previously seen spam. The hash function I chose was a simple, 32-bit
byte-sum of the alphabetic characters in the message, excluding whitespace,
numbers, punctuation, etc. In practice, the hash function had a collision
rate of much better than 10e-6 messages. The "database" was a single UNIX
field directory, with the "key" consisting of the hash value used as a
file name containing the message. Hash collisions were handled by
appending a "-%d" string to the name.
>In light of my specific issues, another post to this thread suggested that a
>128 bit CRC would be okay, and that a hash is more trouble than it's worth.
>
>What do you think?
I think it's sad that people are unwilling to think about hashes. There
is as much snake oil for hash functions as for encryption. An early
response in this thread was typical of the common, silly notion that
'secure' hash functions are somehow less subject to hash collisions than
hash functions. That secure hash functions are intended to be hard to
invert does not let them magically map domains of 2^10000 or more messages
1-to-1 onto ranges of 2^128 hash values.
>I have a hunch that a CRC isn't as good because it's not as random, and I
>might have to worry that similar plaintexts like "BBBBBBBB" and "BBBBBBDA"
>might have the same CRC.
On the contrary, CRC-32 and other error detecting and correcting hash
functions are expressly designed to detect such small changes. There are
good reasons why your disk drive as well as your network links do not use
SHA or MD5 to detect bit rot. If you care more about detecting small
changes than making it hard for bad guys to compute naughty messages that
have the same hash value as a good message, then your only rational choice
is one of the many error detecting hash functions.
--
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Dynamic Data Dependant Key Schedule
Date: Sat, 17 Apr 1999 18:20:34 GMT
I have an idea (yeah!), which could benefit many simple ciphers, (RC5/RC6 are
my fav...), and still keep it simple.
Let's look at RC5 first
for r = 1 to rounds
A = ((A xor B) <<< B) + S[2 * r]
B = ((B xor A) <<< A) + S[2 * r + 1]
Ok, we all know this works well. But, apply my idea, and you get something
like
for r = 1 to rounds
A = ((A xor B) <<< B) + (S[2 * r] <<< (B >> 5))
B = ((B xor A) <<< A) + (S[2 * r + 1] <<< (A >> 5))
Which would change the key value (rotate it using the next 5 bits in the data
dependant register). Such that two blocks with the same key will not get
encrypted the same way (using the same subkeys)
This is basically dynamic key scheduling. Pretty cool no? What does anyone
think about it?
I think you could apply this to RC5, RC6, probably Blowfish (rotate the result
of the F function), and others.
I think using this would make sure that the same subkeys (scheduled keys) are
not used, but are derived from the same private key. Even with chosen
plaintext you don't know the value of the data dependant registers in
intermitent rounds, so you wouldn't be able to derive anything from that.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New drop in cipher in the spirit of TEA
Date: Sat, 17 Apr 1999 21:24:31 GMT
> You might want to look at it a little more closely.
>
> If I understand the algorithm, I think even a million rounds of
> it can be broken with a handful of chosen texts.
> (But I'm not sure; you should check the details.)
Maybe, but I would have to check myself. Thanks for the feedback.
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** 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
******************************
