Cryptography-Digest Digest #804, Volume #9 Wed, 30 Jun 99 02:13:03 EDT
Contents:
Re: trapdoor one way functions (Nicol So)
Re: trapdoor one way functions (Nicol So)
Re: trapdoor one way functions (David A Molnar)
How serious is related key attack? (Robert Scott)
Re: VIC cipher now described on web site (Uri Blumenthal)
Re: Why mirrors invert left-to-right (was: Kryptos article) (wtshaw)
Re: MP3 Piracy Prevention is Impossible (wtshaw)
Re: Bytes of "truly random" data for PRNG seed. ([EMAIL PROTECTED])
Re: two questions (wtshaw)
Re: Can Anyone Help Me Crack A Simple Code? (mercury)
Re: MP3 Piracy Prevention is Impossible ("St�phane Lamy")
Re: Secure link over Inet if ISP is compromized. ("Else")
Re: A slide attack on TEA? (David Wagner)
Re: Can Anyone Help Me Crack A Simple Code? ("Douglas A. Gwyn")
Re: Kryptos article (David Wagner)
Re: A Quanitative Scale for Empirical Length-Strength ("Douglas A. Gwyn")
Re: Kryptos article ("Douglas A. Gwyn")
Re: How serious is related key attack? (David Wagner)
Re: Quasigroup engryption (David Wagner)
----------------------------------------------------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Tue, 29 Jun 1999 20:28:57 -0400
David A Molnar wrote:
>
> Anton Stiglic <[EMAIL PROTECTED]> wrote:
>
> > Note: It is still not know if any one-way or trapdoor one-way function
> > exist..
>
> you should really finish this with "...because even though we have
> functions which look one-way or trapdoor one-way, we have no guarantees
> that an efficient means of inverting every one-way function will not
> be found."
No. We don't know if one-way functions exist because... we simply
don't. Knowing whether one-way functions exist, either in the
affirmative or in the negative, would settle the P =? NP question, and
it would be such a big news that even people who are only casually
interested in the computer science would notice.
I don't think Anton should have ended his sentence as you've proposed.
The clause you proposed started with "because", but it doesn't really
explain what Anton said (which needed no explanation). The second part
of your clause is obviously false.
Nicol
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Tue, 29 Jun 1999 20:50:07 -0400
Medical Electronics Lab wrote:
>
> Nicol So wrote:
> > So, what's the trapdoor information?
>
> It's the private key. The idea behind a "one way function" is that
> using the private key it's easy to compute things, and without it
> life becomes extremely difficult. By choosing "hard" mathematical
> problems, you can estimate the amount of work it takes to do
> the "difficult" task of finding the private key from the public one.
>
> There are several methods in use today. In the IEEE p1363 (draft)
> standard, they list 3: Integer Factorization (RSA), Discrete Log,
> and Elliptic Curve. For IF, the trapdoor are the factors p and
> q which compose the modulus n, for DL the trapdoor is the exponent x
> in g^x mod n, and in EC the trapdoor is the multiplier k in k*P
> (where the * is multiplication over the curve).
I think you missed my point. I'm not asking for the definition of a
trapdoor one-way function (which I understand perfectly well). By
convention, a trapdoor one-way function is, loosely speaking, a function
which is easy to compute in the "forward" direction, but hard in the
"reverse" direction *without the trapdoor information*. By this
convention, discrete log is not even a candidate for a one-way
function--modular exponentiation is!
For modular exponentiation (as a parameterized class of functions) to be
trapdoor one-way, each instance of it (which can be characterized by g
and n), needs to have a piece of trapdoor information that would allow
you to compute the corresponding discrete log function easily for all
valid inputs.
See the message posted by Anton Stiglic.
Nicol
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: 30 Jun 1999 01:24:48 GMT
Nicol So <[EMAIL PROTECTED]> wrote:
> David A Molnar wrote:
>>
>> Anton Stiglic <[EMAIL PROTECTED]> wrote:
>>
>> > Note: It is still not know if any one-way or trapdoor one-way function
>> > exist..
>>
>> you should really finish this with "...because even though we have
>> functions which look one-way or trapdoor one-way, we have no guarantees
>> that an efficient means of inverting every one-way function will not
>> be found."
> No. We don't know if one-way functions exist because... we simply
> don't. Knowing whether one-way functions exist, either in the
> affirmative or in the negative, would settle the P =? NP question, and
> it would be such a big news that even people who are only casually
> interested in the computer science would notice.
Yes.
> I don't think Anton should have ended his sentence as you've proposed.
> The clause you proposed started with "because", but it doesn't really
> explain what Anton said (which needed no explanation). The second part
> of your clause is obviously false.
I'm sorry. I was referring to the apparent contradiction between
giving an example of a "one-way function" and then noting that
we do not know if any "one-way function" exists. Then I made
the same error by not noting that
"we have no guarantees that an efficient means of inverting
functions conjectured to be one-way will not be found."
^^^^^^^^^^^^^^^^^^^^^^^^^
and using "one-way" instead. To include the other side
of P=NP?, I shoud have also noted "Nor do we have any
means of showing that such a function cannot be inverted."
Is this the reason you considered the clause "obviously false"?
Apologies,
-David Molnar
------------------------------
From: [EMAIL PROTECTED] (Robert Scott)
Subject: How serious is related key attack?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 30 Jun 1999 01:46:24 GMT
>From an application point of view, how serious is a
related key attack? Specifically, which applications
would suffer if the cipher used were vulnerable to a
related key attack? I can see how things like a chosen
plaintext or chosen ciphertext attack might actually
happen where the attacker gets temporary custody of
an encryption machine. But how would and attacker go
about capitalizing on a cipher whose only weakness was
to related key?
Bob Scott
Ann Arbor, Michigan (email: rscott (at) wwnet (dot) net )
(My automatic return address is intentionally invalid.)
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: VIC cipher now described on web site
Date: Tue, 29 Jun 1999 21:40:42 -0400
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
> >That cipher must have been a Soviet red herring. There is no
> >way to implement a hand cipher of that complexity.
Bull****. And John is right:
> Although I disagree - a spy otherwise unsuspected, living as an
> ordinary individual, can, one quiet evening in a month, encode or
> decode a single message in such a cipher - it certainly _is_ correct
> that this hand cipher is far too complex for use, say, as a _field_
> cipher for soldiers.
If memory serves me (it was a lo-o-ong time ago), it took me about
15 minutes to encrypt a message (about 40 groups), and one (large)
sheet of squared paper. It does require some concentration (ie. it
is indeed not suited well for trench cryptography :-).
--
Regards,
Uri
-=-=-==-=-=-
<Disclaimer>
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Why mirrors invert left-to-right (was: Kryptos article)
Date: Tue, 29 Jun 1999 20:16:57 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
>
> >Consider this thought experiment: you stand in front of a mirror and
> >take a portrait of yourself with a Polaroid camera. The picture
> >basically captures what you see in the mirror. Then a friend of yours
> >moves into the position where the mirror was, and takes another picture
> >of you with another Polaroid camera.
>
Just have your friend take your picture in front of the inscription with a
throw-away camera. Then, take the film to Walmart; from my experience,
you have a fair chance that the picture will be printed backwards by some
zealous technician correcting an *obvious* problem, or by one who is not
paying attention enough to print the usual correct side in the first
place.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: MP3 Piracy Prevention is Impossible
Date: Tue, 29 Jun 1999 20:27:34 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> Else <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] wrote in message <7lapgp$ok4$[EMAIL PROTECTED]>...
> >>It's completely impossible to make sure that somebody can't share
> >>the plaintext of a document with somebody else. Why try?
>
>
> > It does not have to be "completely impossible". "Too expensive" would do
> > just fine.
>
> It's not "impossible" nor even "expensive" nor even hard. However, it does
> require a little bit of knowledge of how to get things done besides the
> ability to turn on the computer and point and click one's way around the
> WWW.
The easiest way, perhaps not ideal, is simply to take video and/or audio
out, and feed it to another computer's inputs. You might even choose to do
some modification of the audio to match your ear inbetween computers in
some standard band equalizer box.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Bytes of "truly random" data for PRNG seed.
Date: Wed, 30 Jun 1999 02:08:49 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote:
> [EMAIL PROTECTED] wrote:
>
> My free time has just gone negative, so I will say just what I can say
> quickly.
Yeah, I know how it is. How much I'd get done if it
weren't for those customers.
> >[...]
> >Whether or not we take special action to choose x[0] on
> >a long cycle, the proof of security of BBS (or any proof
> >of computational security) applies to the distribution of
> >keys, and not to a particular choice. For any particular
> >composite, there exists a fast algorithm to factor it.
> >
> >We must choose our factors and x[0] from some distribution,
> >and my argument shows that we can choose x[0] from the
> >uniform distribution. It makes no sense to object that the
> >proof doesn't show the security of a particular choice of
> >x[0] while ignoring the same issue in choosing the modulus.
>
> On the contrary, I think it makes quite a lot of sense to
> differentiate two cases:
>
> 1) We take the time to assure that x[0] is not on a short cycle;
> 2) We wish and hope that x[0] is not on a short cycle.
So do we wish and hope that you have not picked a modulus
that is also in someone's Verisign certificate, or do
we check them all? Neither of course. We understand the
math well enough to know that our key generation method
has a negligible chance of choosing such a modulus.
I've shown that given the existing assumptions of the BBS
proof of security, choosing x[0] at random has a
negligible chance of yielding a short cycle.
> There should be no argument that a short cycle is a security
> violation. So if we do not do (1), we openly admit the possibility of
> such violation. It is hard to talk about that and proof in the same
> breath.
A modulus that someone else is already using is just as
surely a security violation. So if you don't check every
public key you can, you admit the possibility of such
violation.
> >> Even though this is unlikely, if it is not actually impossible,
there
> >> can -- in my opinion -- be no "proof." "Proof," to me, means that
we
> >> are logically compelled to a belief because absolutely *no*
> >> alternative exists. To me, "proof" does not mean that we are
*almost*
> >> compelled to belief because the alternative is unlikely.
> >
> >You confuse the rigor of the proof with the character of
> >the proven assertion. Given the assumption stated in the
> >proof of security of BBS, one who understands the proof
> >is compelled to believe the conclusion. The conclusion
> >does not state that there is no case in which an
> >adversary could predict the generator's output without an
> >intractable amount of computation, only that the chance
> >of it is vanishingly small.
>
> And *you* confuse abstract mathematical assumptions and resulting
> "proofs" with the "proof" needed in cryptography. The proof we need
> pertains to security. I claim that if there is an inherent weakness,
> there can be no such proof. To claim that BB&S is proven secure, even
> if we *assume* that factoring is hard, we must *guarantee* that we are
> not on a short cycle. Because the BB&S structure inherently includes
> short cycles.
I don't think you followed. Even if we eliminate
candidates that fall into short cycles, the proof of BBS
security holds for the distribution of choices. There
is no guarantee that an attacker cannot easily break the
specific instance chosen.
If you don't think the conclusion of the BBS proof means
that BBS is secure, well that's up to you. But you can't
have it both ways: that the proof is sound even though
there is a minute chance of choosing a modulus such that
an attacker can break the system, but unsound if there's
a similar chance of choosing an x[0] that allows a break.
> We should note that the last half of the BB&S paper is concerned with
> constructing a particular structure having cycles of known length and
> then providing a way to verify that x[0] is on a long cycle in that
> structure. Do we really imagine that BB&S did all that just for fun?
You can imagine what you want. To support my position I
posted a proof.
--Bryan
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: two questions
Date: Tue, 29 Jun 1999 20:39:28 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>
> > 3. There has been a lot of research done into stream ciphers, however
> > I think we're in a lull right now since people are analyzing the
> > properties of FCSR's (Feedback Carry Shift Registers). The big
> > problem with stream ciphers is generating a fast, "random" number
> > generator.
>
> No, that's actually a rather stupid way to build a stream cipher.
>
> This question seems to come up every few months, always with the
> same (mostly wrong) answers.
It is not wrong to study ideas, but wrong to assume that all can be forced
into a lull of any sort, or be overly committed to any herding process.
Feedback mechanisms do not interest me because I personally consider them
on the dull side; my choice is to do other things. This is not to say
that I might not be interested in the results of others, just that I will
get other results in other areas in the meantime. Several years ago an
NSA fellow tried to convince me to intensely work on such things. I told
him what I just told you.
--
It's always possible that a politician is acting out of principles.
--Michael Kinsley of Slate.com
------------------------------
From: mercury <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Tue, 29 Jun 1999 23:40:34 -0400
Reply-To: [EMAIL PROTECTED]
William Tanksley wrote:
> It is. The algorithm which most efficiently solves this problem does so
> by leaving the computer off, thus producing no output. Every one of the
> mentioned inputs will produce the same output (nothing whatsoever).
>
> -William "Billy" Tanksley
> Utinam logica falsa tuam philosophiam totam suffodiant!
> :-: May faulty logic undermine your entire philosophy!
Okay ... Borderline insults and replies which are, by design, unhelpfull.
I'll put up with it because I am a "newbie". (My only two previous posts
were announcements for a steganography program I wrote - I did not
engage in discussion)
I understand your request for "more information", but I am afraid I don't have
any. This is a real world crypto problem, and I can not reduce it to a simple
math equation where you "solve for x". If I could, I would have solved it.
Mediphorically, I have a box with a red and a green light. If I feed numbers
into
it, I will usually get a red light. Certain numbers give me a green light. I
have
found six numbers that give me a green light, and I know there are others. How
can
I predict which other numbers will give me a green light?
This is a legitimate question and it does have an answer. These numbers do
have
something in common. There is not an "infinate number of possibilities". I'm
sure
I'm not the first to try to solve such a problem, and I'm sure there are ways
to go about solving it. Polynomial and multiple linear regression may offer
some hope.
If anyone has any helpfull advice, I would very much appreciate it.
Thanks.
-mecrury
My Six Number Sets:
582 285 8183
753 980 4828
653 429 9888
833 285 8883
528 853 8849
628 382 2858
------------------------------
From: "St�phane Lamy" <[EMAIL PROTECTED]>
Subject: Re: MP3 Piracy Prevention is Impossible
Date: Wed, 30 Jun 1999 00:57:28 -0400
> (for graphics, I have installed a postscript driver set to print to file
> and use GhostView/GhostScript to convert to BMP).
How can I convert to BMP within ghostscript???
------------------------------
From: "Else" <[EMAIL PROTECTED]>
Subject: Re: Secure link over Inet if ISP is compromized.
Date: Wed, 30 Jun 1999 08:47:47 +0400
Jim Felling wrote in message <[EMAIL PROTECTED]>...
>That is incorrect. Any internet encryption sceme is as secure as the
>parameters allow it to be.
Show please how SSL is secure against man-in-the-middle attack.
>If, for example, a trusted certification authority/ trusted public key
>collection exists, internet communication is as secure as that
certification
>authority/trusted key repository are. (Trusted authority)
How do you access this authority? Whould not it be thorough the ISP?
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A slide attack on TEA?
Date: 29 Jun 1999 21:55:14 -0700
In article <7kq6c1$qd1$[EMAIL PROTECTED]>,
Jooyeon Cho <[EMAIL PROTECTED]> wrote:
> I suspect a slide attack can be applied for TEA.
> The TEA algorithm consists of 32-round identical F-functions.
> And 128-bit master key is simply used in each round.
Aren't you forgetting about "c", which is used to introduce
diversity into the round functions?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Wed, 30 Jun 1999 05:05:34 GMT
mercury wrote:
> I understand your request for "more information", but I am afraid I
> don't have any.
Sure you do; according to your further remarks, you have run some
experiments. You could, for example, list the inputs and outputs
of the experiments.
> This is a real world crypto problem, ... Mediphorically, I have a
> box with a red and a green light. If I feed numbers into it, I will
> usually get a red light. Certain numbers give me a green light. I
> have found six numbers that give me a green light, and I know there
> are others. How can I predict which other numbers will give me a
> green light?
You can't, even knowing the data used, without making assumptions.
> My Six Number Sets:
> 582 285 8183
> 753 980 4828
> 653 429 9888
> 833 285 8883
> 528 853 8849
> 628 382 2858
It may be helpful to know the range of numbers tried, all of which
gave red lights (except for these).
Even so, while there may not be an "infinite" number of possibilities,
the number of black box structures that would give a green light for
those 6 numbers and a red light for every other 10-digit number is
certainly very large. For example, consider the program:
if ( input == 5822858183 )
return green;
if ( input == 7539804828 )
return green;
...
return red;
(C code that could be implemented in silicon). We have no way of
knowing if there are other as-yet-unknown numbers in the "green" list.
But if the system structure is tightly constrained to be of a certain
limited form, then it might be possible to discover its parameters
from a sufficiently large sampling of the data.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Kryptos article
Date: 29 Jun 1999 22:01:52 -0700
In article <[EMAIL PROTECTED]>, Jim Gillogly <[EMAIL PROTECTED]> wrote:
> Each of the systems so far would be solvable by most ACA members
> with sufficient time, if armed with the knowledge that it was in
> fact solvable. A positive mental attitude is a real key to this
> kind of thing.
No kidding!
I can agree, from personal experience. The first time I looked at
CMEA (a cellphone cipher), I just assumed it was probably going to be
too tough a nut to crack. When I heard through the grapevine that
someone else had broken it, but wasn't allowed to publish, I was
motivated to look again -- and I found an attack in just 48 hours.
It's amazing how much of a difference it makes. I almost wish
someone reputable would lie to the world and claim such-and-such
a cipher can be broken, just to see what the results are. :-)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A Quanitative Scale for Empirical Length-Strength
Date: Wed, 30 Jun 1999 05:13:07 GMT
wtshaw wrote:
> L-S is not the only factor in Algorithm Strength, but it is worth
> mentioning as one of the important ones. To not include it
> appropriately is to look foolish.
I dunno, it seems nearly "foolish" to me to promote the simple
taking of logarithm of an empirically-judged maximum safe message
length to any elevated status as a measurement of anything.
Why not just cite the maximum safe message length?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Wed, 30 Jun 1999 05:16:29 GMT
David Wagner wrote:
> It's amazing how much of a difference it makes. I almost wish
> someone reputable would lie to the world and claim such-and-such
> a cipher can be broken, just to see what the results are. :-)
They wouldn't have to lie -- history tells us that most ciphers are
breakable under favorable circumstances, when the right approach is
found. Sometimes it takes a lot of work to find a suitable approach!
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: How serious is related key attack?
Date: 29 Jun 1999 22:10:03 -0700
In article <[EMAIL PROTECTED]>,
Robert Scott <[EMAIL PROTECTED]> wrote:
> From an application point of view, how serious is a
> related key attack?
It depends on the key-exchange protocol you use.
If you use a bad one, related-key weaknesses in the cipher
can be exploited using only chosen-ciphertext queries.
See my CRYPTO'96 paper, with co-authors Bruce Schneier and
John Kelsey, for an example of how this can occur.
http://www.cs.berkeley.edu/~daw/papers/keysched-crypto96.ps
On the other hand, if your key exchange protocol
guaranteees key integrity, related-key attacks are probably
impossible.
Note also that related-key attacks may be relevant if the
block cipher is used to build a hash function, using e.g.
the Davies-Meyer construction. See the CRYPTO'96 paper.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Quasigroup engryption
Date: 29 Jun 1999 22:49:21 -0700
In article <7l8sko$uau$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Please read this paper, have anyone idea is it this secure? Where I
> can find more papers about using quasigroups for encrytpion?
It seems that your suggestion is "just" a small generalization of standard
modes of operation, such as CBC and CFB mode.
Namely, let A be an alphabet, i.e. a plaintext space, let K be a key-space,
and let E : K \times A \to A be a block cipher (i.e., E_k : A \to A is a
bijection for all k in K).
Then if we define x * y = E_k(x+y), we get a quasigroup (A,*).
Furthermore, the associated quasigroup cipher (A^+,f_*) is exactly CBC
mode encryption using the block cipher E.
Also, x * y = E_k(x) + y gives the so-called CFB mode.
One important requirement for the security of these modes is that A must be
large enough, because some information about the plaintext will start to
leak once you encrypt more than about \sqrt{|A|} blocks ("birthday paradox").
You also suggest to use f_{*'} o f_* as an encryption mode. Note that
this is not stronger than f_*, thanks to meet-in-the-middle attacks.
(This is standard crypto theory; see any textbook.)
Finally, your technique for composition of quasigroup ciphers seems
suboptimal. Your technique, f_{*'} o f_*, is akin to what's known in the
crypto world as "outer chaining". Eli Biham has done some work which
suggests that inner chaining is much more secure than outer chaining.
(Inner CBC chaining is given by x * y = E_k(E_{k'}(E_{k''}(x))) + y, where
k,k',k'' are three independent keys.)
I hope these comments help. Your observation that x * y need only be a
quasigroup is interesting; I wonder whether you can come up with some
other alternatives to the standard CBC and CFB mode constructions.
------------------------------
** 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
******************************
