Cryptography-Digest Digest #679, Volume #10 Sat, 4 Dec 99 01:13:00 EST
Contents:
Re: NP-hard Problems (Scott Fluhrer)
Re: Any negative comments about Peekboo >> How to verify that promised algorithms
are included (Dmitriy Morozov)
Re: Why Aren't Virtual Dice Adequate? ("Trevor Jackson, III")
Re: cookies ("Trevor Jackson, III")
Re: NSA should do a cryptoanalysis of AES ("Trevor Jackson, III")
Re: Any negative comments about Peekboo free win95/98 message encryptor ("Trevor
Jackson, III")
Re: Any negative comments about Peekboo >> How to verify that promised algorithms
are included (Steve K)
Re: NP-hard Problems (David A Molnar)
----------------------------------------------------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: Sat, 04 Dec 1999 03:40:48 GMT
In article <827kp9$7to$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>
>The original question was
>
> "Are there NP-hard problems which are not NP-complete?"
>
>From my understanding, this is equivalent to :
>
> "Are there problems which would let us solve all other
> problems in NP if we could do them easily, but are not
> themselves in NP ?"
>
>
>I think so. Now let me try something I'm not so sure of and try to
>give an example.
Better example: the halting problem.
This is obviously NP-hard, because for any problem in NP, you can
obviously construct a problem that will halt iff the string is in
the language.
This is obviously not in NP, because all problems in NP are
computable, and the halting problem is not.
>Just as an aside -- factoring is not known to be NP-complete. Neither
>is discrete log. This means an efficient means of solving the factoring
>problem may not imply that any other problems (besides RSA and other
>useful cryptosystems) are easy. Ditto for discrete log.
>
>At the same time, it's the cryptosystems which are based on these
>peculiar "we don't know" problems which persist. While the systems
>based on NP-complete problems like knapsacks and lattice basis
>reduction haven't done nearly as well. Weird...
Well, AFAICT, the attacks on knapsacks and lattice basis reduction
systems were not done by attacking the general problem, but instead
finding the trapdoor that the private key used. So, they managed
to avoid confronting the "hard" problem directly.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Dmitriy Morozov)
Crossposted-To: alt.security.pgp
Subject: Re: Any negative comments about Peekboo >> How to verify that promised
algorithms are included
Date: Sat, 04 Dec 1999 03:49:41 GMT
[EMAIL PROTECTED] (Johnny Bravo) wrote:
>On Thu, 02 Dec 1999 21:46:15 -0500, [EMAIL PROTECTED] wrote:
>
>>How to verify that promised algorithms are included when no link
>>between source & executable can be establish ?
>
> Compile your own executable. This is true for all crypto software,
>even PGP.
Well, there is a little problem. I downloaded the source code offered on the
web site. First of all, the name was kind of strange (pb_backup.zip) but that's
Ok. The main question is why does readme file included in the archive say
Peekboo V1.3. The only explanation (logical explanation) would be that the
source is for version 1.3. But then that means that what you see is NOT what
you get. More of that according to the site the encrypted files produced by the
version 1.70 and earlier are not compatible with later versions; so even if you
are successful in compiling the code (which I wasn't - though I didn't try very
hard) what you get won't be the executable you can download, more of that even
the encrypted files won't be compatible with the ones produced by
the executable.
And that's where my problem with Peekboo arises. There does not seem to be a
concept behind it. No structure... The files that were produced by versions <=
1.70 are not compatible with the ones produced by those > 1.70. The question
arises how well are things "thought through", is it possible that in the future
another incompatibility will be introduced (to add something else). If Tom has
message format and any idea of what might be added and how compatibility will
be preserved in future versions (and I'm pretty sure he does, at least I would
expect it to be so), then in my opinion it would be logical to publish it (on
the web site), and if he doesn't then there is no point in hoping for a big
future for this program.
And that's where the main thing that I cannot understand comes. Ok, I see an
idea behind it: make your own cryptographic application, make it small so it
would be easy to use and transport - and that's fine and actually kinda
interesting, but the question is why can't one make it, for example, OpenPGP
compatible. Not the whole thing, some of the things required for peekboo are
not defined there (though there are plenty of numbers-identifiers reserved for
your own "algorithms"), but at least some of the things could be compatible.
Most of the things/structures needed for peekboo are defined in OpenPGP, most
of those things are checked, and thought through by many people. The advantages
seem to be obvious to me, I don't really see disadvantages. Any comments
(especially, from Tom himself)?
Regards.
--
Dmitriy Morozov
[EMAIL PROTECTED]
------------------------------
Date: Sat, 04 Dec 1999 00:10:22 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Why Aren't Virtual Dice Adequate?
r.e.s. wrote:
> "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote ...
> : r.e.s. wrote:
> : > "Trevor Jackson, III" <[EMAIL PROTECTED]> wrote ...
> : > : A simple mechanism is to use a shared secret. Assume that in addition
> : > : to the (large) message key repository each pair of correspondents is
> : > : given a unique "signature" value. For purposes of illustration this
> : > : could be small; 64-256 bits. To send an authenic message one appeads
> : > : the "signature" to the message, encoding it with the keypad. On
> : > : receipt of a message the decoder unmasks the "signature" region and
> : > : compares the result with the secret value. Since the premise of the
> : > : "signature" is that only the sender and receiver known the valid
> : > : signature value, and because the signature ciphertext is not reused,
> : > : the message must have come from one of the two inposession of the
> : > : secret "signature" value. This approach does not prevent replay
> attacks.
> : >
> : > In addition to its other functions, doesn't a message key (as defined
> : > above) accomplish the same thing as the type of "signature" you
> describe?
> : > (It is, after all, a kind of "shared secret", being sent along with the
> : > enciphered message.)
> : >
> : > The message key is created by the sender to be random and unique to each
> : > transmission, is accessible only to possessors of the primary key, is
> : > necessary if the decipherment is not to produce garbage, and strengthens
> : > any stream cipher -- including an OTP -- by helping to ensure that keys
> : > are really used only once.
> :
> : What's an "authetic" message key?
>
> A thing is "authentic" if it is what it's claimed to be.
> In our context, this means it hasn't been surreptitiously
> altered in-transit.
>
> In the scenarios under discussion, a message key is inserted
> into the ciphertext in a way that makes it accessible only
> to those who know the relevant part of the primary key --
> "ciphertext within ciphertext" so to speak.
>
> : The purpose of authenticating a message cannot be addressed by the sender
> : synthesizing a value that the receiver cannot calculate.
>
> The receiver *does* calculate it, because some bits of the
> primary key -- unknown to the opponent -- serve to do just
> that, viz, to extract it from the transmitted ciphertext.
>
> : Thus a message key
> : generated by the sender and not already known to the receiver would not
> : authenticate a message because the receiver has no way to distinguish
> message
> : keys selected by the sender from message keys selected by an opponent.
>
> In the scenarios under discussion, an opponent cannot
> introduce a message key of his own making because he doesn't
> have the key for inserting it into the ciphertext.
What does hiding a block cipher under an OTP buy you that the OTP alone does
not? In what sense is your message kay a key to the message if it is not a key
to a hidden cipher?
------------------------------
Date: Sat, 04 Dec 1999 00:23:15 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: cookies
SCOTT19U.ZIP_GUY wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Steve K) wrote:
> >On Fri, 3 Dec 1999 13:08:37 -0500, E-mail <[EMAIL PROTECTED]> wrote:
> >
> >>
> >>
> >>Many web sites are pretty insistent about taking cookies. Why?
> >>
> >>I am suspicious about it because I see it as violation of privacy
> >>and possibly a means of breaking into data not mentioned in the
> >>reasons they give.
> >
> >The one decent use for cookies (that I know of):
> >
> >When registered users log in to a company's site, a cookie is set that
> >identifies that user as being currently logged on. Then, when moving
> >from page to page inside the site-- or even from server to server in
> >some cases-- a cgi program can read the cookie and grant access.
> >The alternatives to this all seem pretty messy and failure prone.
> >
> >On the other hand, here's from a ZDNET atricle quoted in HNN:
> >
> >> Novell chief Eric Schmidt has admitted that he has been
> >> the victim of credit card theft. Speaking at San Francisco's
> >> Digital Economy conference he blamed the theft of his
> >> personal information on browser cookies. He labeled cookies
> >> as "the biggest disaster for computers in the past [few] years."
> >
> >Since you seem to be concerned about privacy issues, you might want to
> >take a look at Internet Junkbuster:
> >
> >Junkbuster is a local proxy that selectively blocks domains specified
> >by the user. You can also specify domains whose cookies you want the
> >proxy to admit, in one of the Junkbuster config files. It even has a
> >function for spoofing cookies, though I have not had much luck with
> >that feature so far.
> >
> >If you specify the domains of the major tracking sites-- the ones hit
> >counters and banners come from-- you instantly get faster browsing and
> >a reduced profile. It also kills the referrer field that is sent out
> >with URL requests, and lies to websites about your browser and OS.
> >
> >http://www.junkbusters.com/ht/en/ijbfaq.html
> >
> >Steve K
> >
> >---Continuing freedom of speech brought to you by---
> > http://www.eff.org/ http://www.epic.org/
> > http://www.cdt.org/
>
> I give free cookies at my site to those with active X or javasrcipt turned
> on.
Well, why don't you make the world a better place? Just write a cookie monster.
------------------------------
Date: Sat, 04 Dec 1999 00:35:26 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NSA should do a cryptoanalysis of AES
karl malbrain wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > karl malbrain wrote:
> > > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > > > The infamous "toilet seat" was a limited production of fiberglass
> > > > moldings for a military transport plane, and would have cost about
> > > > as much as it did no matter what.
> > > Pure nonsense. We're talking about how the military specified a
> > > non-COTS toilet seat in the first place.
> >
> > It wasn't a "toilet seat", dammit, it was a *necessarily* custom
> > molding to fit a specific tight space in a packed aircraft. How
> > many other aircraft components are COTS consumer items? Proxmire
> > was grandstanding for political purposes, and shame on you for
> > falling for it.
>
> Your logic reminds me how BART decided to abandon rail-road signaling
> standards, and specify their VERY own VOLTAGE level between the rails.
> Nothing but problems ever since. And where did you ever get the idea that
> I'm not POLITICAL? Karl M
There's no argument here. pROXMIRE was creating issues out of thin air. He
once complained about a $600 coffe pot, conjuring up the image of a 19.95
Lechmere (RIP) special as the alternative. Like you are going to put a
table-top coffee pot on a military transport jet, expect it to feed 600 men,
at altitude (where water boils at lower temperature), and do so safely. Go
price a commerical coffee pot as you would for a restaurant. Then price a
coffee pot used on an airliner.
There are also convoluted rules that require the distribution of
administrative costs over every item listed on an invoice. So an invoice for
a jet engine costing ~1e5 and 1 lb of spare titanium 10/32 nuts costing ~1e1
both share the ~1e3 cost of admin, producing extremely valuable 10/32 nuts.
Nuts to that.
------------------------------
Date: Sat, 04 Dec 1999 00:45:49 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: Any negative comments about Peekboo free win95/98 message encryptor
David A Molnar wrote:
> In sci.crypt Keith A Monahan <[EMAIL PROTECTED]> wrote:
> > David,
>
> > Thanks for the response.
>
> No problem. Just wanted to point out that there are various axes of
> "trust". and some of them are orthogonal. :-)
>
> > problems. I always read companies' privacy/security policies online and
> > they always talk about SSL encryption and blah blah. But you KNOW alot
> > of these companies store your credit card info in plaintext on some
> > networked NT server, or even worse, plaintext on a unix box.
>
> Yeah. This is why SET still seems interesting to me; the idea of doing
> credit card transactions (if you _must_ do credit cards) without
> storing the card # anywhere is a Good Idea. Too bad that a previous
> thread here suggests that it's unworkable in practice...
>
> Re: a "security audit seal" -- who would you trust to do something
> like that? and how are they going to get paid? It doesn't seem to make
> sense for the vendors to pay the auditors directly...that's a nasty
> conflict of interest. :-(
It appears to work for Underwriter Labs. The brand name is worth something to
consumers. So the vendors pay for it to enhance their sales. UL preserves
their integrity because it is their only product. One compromise in a safety
standard that came to light would destroy their brand name's value.
BTW, auditors are generally paid by the organizations they audit. Same
product: integrity; same dynamic: no compromise on standards.
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Crossposted-To: alt.security.pgp
Subject: Re: Any negative comments about Peekboo >> How to verify that promised
algorithms are included
Date: Sat, 04 Dec 1999 05:57:28 GMT
On Sat, 04 Dec 1999 03:49:41 GMT, [EMAIL PROTECTED] (Dmitriy Morozov)
wrote:
>[EMAIL PROTECTED] (Johnny Bravo) wrote:
>
>>On Thu, 02 Dec 1999 21:46:15 -0500, [EMAIL PROTECTED] wrote:
>>
>>>How to verify that promised algorithms are included when no link
>>>between source & executable can be establish ?
>>
>> Compile your own executable. This is true for all crypto software,
>>even PGP.
>
>Well, there is a little problem. I downloaded the source code offered on the
>web site. First of all, the name was kind of strange (pb_backup.zip) but that's
>Ok. The main question is why does readme file included in the archive say
>Peekboo V1.3. The only explanation (logical explanation) would be that the
>source is for version 1.3. But then that means that what you see is NOT what
>you get. More of that according to the site the encrypted files produced by the
>version 1.70 and earlier are not compatible with later versions; so even if you
>are successful in compiling the code (which I wasn't - though I didn't try very
>hard) what you get won't be the executable you can download, more of that even
>the encrypted files won't be compatible with the ones produced by
>the executable.
>
>And that's where my problem with Peekboo arises. There does not seem to be a
>concept behind it. No structure... The files that were produced by versions <=
>1.70 are not compatible with the ones produced by those > 1.70. The question
>arises how well are things "thought through", is it possible that in the future
>another incompatibility will be introduced (to add something else). If Tom has
>message format and any idea of what might be added and how compatibility will
>be preserved in future versions (and I'm pretty sure he does, at least I would
>expect it to be so), then in my opinion it would be logical to publish it (on
>the web site), and if he doesn't then there is no point in hoping for a big
>future for this program.
>
>And that's where the main thing that I cannot understand comes. Ok, I see an
>idea behind it: make your own cryptographic application, make it small so it
>would be easy to use and transport - and that's fine and actually kinda
>interesting, but the question is why can't one make it, for example, OpenPGP
>compatible. Not the whole thing, some of the things required for peekboo are
>not defined there (though there are plenty of numbers-identifiers reserved for
>your own "algorithms"), but at least some of the things could be compatible.
>Most of the things/structures needed for peekboo are defined in OpenPGP, most
>of those things are checked, and thought through by many people. The advantages
>seem to be obvious to me, I don't really see disadvantages. Any comments
>(especially, from Tom himself)?
>
>Regards.
>
>--
>Dmitriy Morozov
>[EMAIL PROTECTED]
I think many of these questions are answered by the observation that
Peekboo is under active development; Tom has solicited help in both
software development and cryptanalysis, on the Peekboo e-list.
For loads o' info on Peekboo's development to date, log in at
http://www.egroups.com/register?url=/vote%3flistname%3dpeekboo%26m%3d1
While it is certainly intended to work securely as is, Peekboo is
still under development. Tom has indicated a willingness to add
developers to the Peekboo project, to make the source code easier to
port across OS platforms, and to aid and abet cryptanalysis efforts.
Of course this is just what I have read, and I can't speak for Tom.
Steve K
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: NP-hard Problems
Date: 4 Dec 1999 05:39:16 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> Better example: the halting problem.
Agreed. Thanks for pointing it out!
> Well, AFAICT, the attacks on knapsacks and lattice basis reduction
> systems were not done by attacking the general problem, but instead
> finding the trapdoor that the private key used. So, they managed
> to avoid confronting the "hard" problem directly.
Good point. It's not clear whether you can get
a public-key cryptosystem based only on the assumption "P != NP."
So the question of whether you *need* some extra trapdoor or extra
structure on your favorite "hard" NP problem seems open. Put another
way, the question seems to be "will there always be a way to avoid
confronting the 'hard' problem in a PKC based on some NP-complete
problem?"
In knapsacks and the Goldwasser-Goldreich-Halevi system, you're
right in that the attacks took advantage of structure added to
the problem by the algorithm. For example, the GGH scheme rests
on the assumption that adding a random vector to a certain
vector representing the plaintext hides the plaintext by creating
a lattice problem. The crucial observation for breaking GGH seems
to have been that this padding actually leaked information, making
the problemm very easy.
By contrast, I thought that the nice thing about Ajtai-Dwork was that
it was provably based on the short independent vector problem.
That is, breaking it would yield a general means of solving the
SIVP. In this case the problem seems to have been more that
the underlying problem turned out to be too easy...not so much that
there was a problem with the "trapdoor", as in knapsacks.
I haven't looked at the NTRU attacks. another to do. :-\
Anyway, it now seems that we need new hard problems which are also
hard to approximate, and also allow cryptosystems to be based on
them without introducing any extra structure. Anyone got 'em? :)
-David
------------------------------
** 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
******************************
