Cryptography-Digest Digest #412, Volume #9 Sat, 17 Apr 99 22:13:08 EDT
Contents:
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Patrick Juola)
Re: AES Competition (A [Temporary] Dog)
Re: Extreme lossy text compression (D. J. Bernstein)
Re: Adequacy of FIPS-140 (wtshaw)
Re: Extreme lossy text compression (Terry Ritter)
RC6 new key standard from AES conference? ("Nick Strauss")
Re: Adequacy of FIPS-140 ("Douglas A. Gwyn")
Re: Adequacy of FIPS-140 ("Douglas A. Gwyn")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Extreme lossy text compression (D. J. Bernstein)
Re: Question on confidence derived from cryptanalysis. ("Douglas A. Gwyn")
Re: AES Competition ("Nick Strauss")
Re: AES Competition ("Douglas A. Gwyn")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: 17 Apr 1999 16:32:27 -0400
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>On 16 Apr 1999 17:21:22 -0400, in <7f89ki$gng$[EMAIL PROTECTED]>,
>in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>
>>[...]
>>So you're suggesting that a cypher that has withstood years of
>>intensive analysis by professionals is *NO* better than a cypher
>>that has not been analyzed at all?
>
>It is not provably better. And not provably better admits the
>possibility of contradiction.
But not-provable is not the same as unknown.
I don't know that Pittsburgh won't be hit by a devastating hurricane
in the next month.
But I've got a bright crisp $20 in my pocket that says that it won't.
In a philosophical sense, "knowledge" is a "justified true belief";
I don't have *proof* that Pittsburgh won't be hit by a hurricane,
but I can produce lots and lots of justification.
> So we do not know. Which means that
>interpreting years of intensive analysis as strength is nothing more
>than DELUSION. Cryptanalysis of any length whatsoever provides no
>rational scientific indication of strength.
Interesting. So your "rational scientific indication" is that we've
got no way of figuring out which side of my Pittsburgh weather bet
is the smart one?
>>I don't believe this;
>
>It is not necessary for you to believe it: It is what it is.
>
>
>>in fact, I think it's total bullshit.
>
>Then you need to think about it more deeply.
I just did. It's still total bullshit.
Knowledge doesn't require proof. Belief doesn't require knowledge.
Confidence doesn't even require belief.
-kitten
------------------------------
From: [EMAIL PROTECTED] (A [Temporary] Dog)
Subject: Re: AES Competition
Date: Sat, 17 Apr 1999 21:22:49 GMT
On Sat, 17 Apr 1999 22:13:05 +0100, "Michael Scott" <[EMAIL PROTECTED]>
wrote:
>
>I must say Rijndael is looking good, given that its completely patent free,
>scales nicely to various architectures, and can also be used as a one-way
>hash. Its only problem seems to be its awful name.
>
How do you pronounce that anyway? I've been (mentally) calling it
"Rinj N Dall" (three syllables, like Toys R Us).
- A (Temporary) Dog |"Intelligent, reasonable
The Domain is *erols dot com* |people understand that -
The Name is tempdog |unfortunately, we're dealing
|with elected officials"
Put together as name@domain | - name withheld
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Extreme lossy text compression
Date: 17 Apr 1999 22:20:41 GMT
> you might as well use a 128 bit CRC.
hash127 is much faster than a 128-bit CRC. Try it for yourself:
http://pobox.com/~djb/hash127.html
In spirit these functions are really all the same:
* reduce (Z/2)[x] modulo some prime x^128-... (CRC/``division'');
* reduce Z modulo some prime 2^128-... (basically Karp-Rabin);
* reduce F_(2^32)[x] modulo some prime x^4-... (Shoup);
* reduce (Z/(2^31-1))[x] modulo some prime x^4-...;
* reduce F_(2^128)[x] modulo some prime x-... (``evaluation'');
* reduce (Z/(2^127-1))[x] modulo some prime x-... (hash127);
* etc.
All of them have about the same natural hardware speed. However, in
software, arithmetic in large characteristic benefits from CPU support
for fast multiplication---often buried inside the floating-point unit,
but still accessible---whereas arithmetic in characteristic 2 doesn't.
I hope that CPUs will someday provide fast polynomial arithmetic mod 2;
but there's no reason that it'll ever be faster than integer arithmetic.
I haven't found any cryptographic applications where finite fields of
small characteristic turned out to be a good idea.
---Dan
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Adequacy of FIPS-140
Date: Fri, 16 Apr 1999 23:29:17 -0600
In article <7f7cqt$fdq$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Patrick Juola) wrote:
>
> And, of course, by Kerchoff's maxim, I know the trivial change you're
> going to apply *unless you make it part of the key*, so I can simply
> undo the change when I search on AltaVista (or write my own SpiderBot).
>
> At this point, you're adding a hell of a lot of bits to the key when
> you start to add *algorithms* into it. Why not just use a longer key
> and be done with it?
>
Long is relative, but shallow is always a problem. We can go back to the
Ritter idea of having numbers of algorithms to choose from as part of the
key.
As I said before, roughly, your choice of encryptive algorithm and the key
it requires is more important than having a very long key. Consider
something both broad and moderately, but portable, long.
--
Too much of a good thing can be much worse than none.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Extreme lossy text compression
Date: Sat, 17 Apr 1999 23:39:51 GMT
On 17 Apr 1999 22:20:41 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (D. J. Bernstein) wrote:
>> you might as well use a 128 bit CRC.
>
>hash127 is much faster than a 128-bit CRC. Try it for yourself:
>
> http://pobox.com/~djb/hash127.html
>
>In spirit these functions are really all the same:
>
> * reduce (Z/2)[x] modulo some prime x^128-... (CRC/``division'');
> * reduce Z modulo some prime 2^128-... (basically Karp-Rabin);
> * reduce F_(2^32)[x] modulo some prime x^4-... (Shoup);
> * reduce (Z/(2^31-1))[x] modulo some prime x^4-...;
> * reduce F_(2^128)[x] modulo some prime x-... (``evaluation'');
> * reduce (Z/(2^127-1))[x] modulo some prime x-... (hash127);
> * etc.
>
>All of them have about the same natural hardware speed. However, in
>software, arithmetic in large characteristic benefits from CPU support
>for fast multiplication---often buried inside the floating-point unit,
>but still accessible---whereas arithmetic in characteristic 2 doesn't.
>
>I hope that CPUs will someday provide fast polynomial arithmetic mod 2;
>but there's no reason that it'll ever be faster than integer arithmetic.
>I haven't found any cryptographic applications where finite fields of
>small characteristic turned out to be a good idea.
Surely we don't implement CRC's like this. Addition mod 2 is
exclusive-OR which is well supported in CPU's. "Division" mod an
irreducible mod 2 poly is just a test and conditional exclusive-OR,
which is, again, well supported.
For production use, CRC's are table-driven. Typically, we generate a
256-entry table, then process data byte-by-byte. Each step typically
requires a byte exclusive-OR, an 8-bit "shift" of the CRC (which might
involve simply changing a pointer to the head), and an exclusive-OR
from table into the CRC register.
That said, 128 bit (16-byte) values are not usually supported in CPU
registers or instruction sets. So I would instead probably use 4
CRC's using different deg-32 primitives (or perhaps 5 deg-31's) to
produce a similar effect. See, for example:
http://www.io.com/~ritter/KEYSHUF.HTM
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Nick Strauss" <[EMAIL PROTECTED]>
Subject: RC6 new key standard from AES conference?
Date: Sat, 17 Apr 1999 16:21:55 -0700
I've heard mention a couple times of a revised key schedule version of RC6
that Rivest discussed at the rump session of the last AES conference...
Anyone have, or have al link to, any documentation for this?
It sounded, from some of what I've caught, that it sacrificed performance on
8-bit systems for better speed elsewhere? Is it compatible with the basic
spec, or is it then a fundamentally new cipher rather than just an
implementation issue?
Thanks,
--N
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Adequacy of FIPS-140
Date: Sun, 18 Apr 1999 00:11:07 GMT
Kurt Wismer wrote:
> why can't you take the minimum cost of all the attacks...
The cheapest possible cryptanalytic attack against a complex
system is the "lucky guess", and yes, it has occasionally worked.
However, it doesn't work against a "typical" instance of the
system. So expectations have to enter into the metric.
The real problem with your suggestion is that few people know
all relevant attacks that your system might be exposed to.
(Except the enemy, who isn't going to help you analyze your
system.)
Shannon made a start at a *general* method of analysis,
not dependent on considering any specific forms of
cryptanalysis, with his "unicity distance" metric.
But surely we could do better than that, now that information
statistics is out of its infancy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Adequacy of FIPS-140
Date: Sun, 18 Apr 1999 00:11:53 GMT
"R. Knauer" wrote:
> Gee, I was hoping you could show us how you successfully attacked the
> OTP cryptosystem.
Gee, you never asked, you just asserted that I was mistaken.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Sat, 17 Apr 1999 23:40:04 GMT
On 17 Apr 1999 16:32:27 -0400, in <7far4r$htf$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>>
>>On 16 Apr 1999 17:21:22 -0400, in <7f89ki$gng$[EMAIL PROTECTED]>,
>>in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>>
>>>[...]
>>>So you're suggesting that a cypher that has withstood years of
>>>intensive analysis by professionals is *NO* better than a cypher
>>>that has not been analyzed at all?
>>
>>It is not provably better. And not provably better admits the
>>possibility of contradiction.
>
>But not-provable is not the same as unknown.
>
>I don't know that Pittsburgh won't be hit by a devastating hurricane
>in the next month.
>
>But I've got a bright crisp $20 in my pocket that says that it won't.
Which means to me that you have some understanding of the risk of
hurricanes in Pittsburgh. You get this understanding from reported
reality.
Unfortunately, neither you nor anyone else can have a similar
understanding of the risk of cipher failure -- there is no reporting
of cipher failure. There is instead every effort made to keep that
information secret, and in fact to generate false reporting to buoy
your unfounded delusion of strength.
>In a philosophical sense, "knowledge" is a "justified true belief";
>I don't have *proof* that Pittsburgh won't be hit by a hurricane,
>but I can produce lots and lots of justification.
Too bad we cannot do the same for a cipher.
>> So we do not know. Which means that
>>interpreting years of intensive analysis as strength is nothing more
>>than DELUSION. Cryptanalysis of any length whatsoever provides no
>>rational scientific indication of strength.
>
>Interesting. So your "rational scientific indication" is that we've
>got no way of figuring out which side of my Pittsburgh weather bet
>is the smart one?
Nonsense. Knowing the past weather in Pittsbugh is possible: Knowing
the past strength of a cipher is not.
>>>I don't believe this;
>>
>>It is not necessary for you to believe it: It is what it is.
>>
>>
>>>in fact, I think it's total bullshit.
>>
>>Then you need to think about it more deeply.
>
>I just did. It's still total bullshit.
Then you need to think about it even more deeply.
>Knowledge doesn't require proof. Belief doesn't require knowledge.
>Confidence doesn't even require belief.
Fine. I will grant that you can be confident completely independent
of reality. Oddly, I assumed that we were talking Science here.
RATIONAL confidence requires a quantification of risk, even if only as
a handwave generality. But that is not available in ciphers. Until
we have a complete theory of strength, or a complete theory of
cryptanalysis, we have no basis by which to judge the risk we take by
using any particular cipher.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Extreme lossy text compression
Date: 17 Apr 1999 23:26:16 GMT
Geoffrey Teabo <[EMAIL PROTECTED]> wrote:
> I have a hunch that a CRC isn't as good because it's not as random,
Actually, a 128-bit CRC _with a random polynomial_ guarantees an
extremely low collision probability for any fixed set of inputs.
(Just like hash127, except that hash127 is faster and provides a
slightly better bound on the collision probability.)
> 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?
What if the criminal spots a legitimate article before you do, and
quickly feeds you a fake article with the same hash, preventing the
legitimate article from entering your database?
``We're in sci.crypt. We're supposed to be paranoid.''
An attacker can easily do this if he knows your CRC polynomial; and he
can easily figure out the polynomial given a few CRC results. That's why
secrecy is an issue.
---Dan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Sun, 18 Apr 1999 00:35:46 GMT
Terry Ritter wrote:
> 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.
There is a difference between "less than total confidence" and
"no confidence". In many cases, one can reliably estimate the
enemy's capabilities and be confident that he is not in as
good a position to succeed in attacks against your system as
your own tiger team is; so if your guys can't crack the system,
it is more likely than not that the enemy can't crack it either.
Depending on the potential cost of being wrong, that might be
good enough. If not, then your idea of additional protection
makes sense. However, you need to prove that your protocols
do add significant security; otherwise the new "protocolled"
system is subject to the same argument you made about the
original system, namely one doesn't know whether or not the
enemy can crack it.
> ... 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.
I assume you're talking about the open literature, because it's
not the case inside the fence. That's one of the frustrating
things about this business; there is a lot of (slow) reinvention
of the wheel, due to extreme secrecy about what is known.
> 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.
Largely, academia studies what they already know how to study,
because the expectation of producing something "publishable"
is greater that way. This is really sad, but understandable.
Just so you know, I appreciate your work and especially your
making useful information available via the Web. Maybe self-
publication will help mankind make progress in fields that
are currently stagnating due to academic inbreeding.
------------------------------
From: "Nick Strauss" <[EMAIL PROTECTED]>
Subject: Re: AES Competition
Date: Sat, 17 Apr 1999 16:17:27 -0700
>So its even money Rijndael & RC6
>2/1 TwoFish
>3/1 Mars & Serpent
>10/1 E2
>
>100/1 bar those
Another interesting consideration -- remember this is a selection done by a
government committee (which I probably just spelled wrong) -- is the
politics that might influence the choice. The histories, reputations, etc.
of the designers.
These are just thoughts...what others might think in some cases, and not
necessarily what I feel:
Will the candidates of academic origin (Rijndael, Serpent, others) be unable
to "market" themselves well enough?
Will the reputations of folks like Coppersmith and Schnier preceed them and
their candidates (for better or worse?) Ie, Coppersmith's history with DES,
Schnier & Rivest's relatively high profile outside the community.
How will copyright/IP issues, particularly for the commercially developed
products, influcence selection?
Will the non-US candidates be able to overcome any bias that may exist, the
NIH syndrome, language barriers?
I guess I'm just trying to think of the non-cryptographic factors...anyone
think of any others?
--N
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: AES Competition
Date: Sun, 18 Apr 1999 00:40:07 GMT
Nick Strauss wrote:
> Another interesting consideration -- remember this is a selection
> done by a government committee (which I probably just spelled
> wrong) -- is the politics that might influence the choice. The
> histories, reputations, etc. of the designers.
Of course, that couldn't happen in a non-government committee. Right.
Actually, its a much more open process than the picture one has of
"a government committee". Evaluation criteria exist and were
published.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: 18 Apr 99 01:55:36 GMT
Terry Ritter ([EMAIL PROTECTED]) wrote:
: On 16 Apr 1999 17:21:22 -0400, in <7f89ki$gng$[EMAIL PROTECTED]>,
: in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
: >[...]
: >So you're suggesting that a cypher that has withstood years of
: >intensive analysis by professionals is *NO* better than a cypher
: >that has not been analyzed at all?
: It is not provably better. And not provably better admits the
: possibility of contradiction. So we do not know. Which means that
: interpreting years of intensive analysis as strength is nothing more
: than DELUSION. Cryptanalysis of any length whatsoever provides no
: rational scientific indication of strength.
Yes and no.
Your point is valid, however, what do we do if there is no way to obtain a
lower bound on the strength of a cipher? I fear this is quite possible:
proving a cipher is strong against attacks we can't even imagine seems to
me to be equivalent to solving the halting problem.
Then it does make sense to look at the upper bound, because it's one of
the few indications we have. But it also makes sense - and here, I think,
we come closer to agreement - not to put too much faith in that upper
bound, and to add constructs of different types, and constructs that seem
like any mathematical tools to analyze them which would be useful for
cryptanalysts are *far* in advance of the state of current knowledge.
John Savard
------------------------------
** 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
******************************
