Cryptography-Digest Digest #76, Volume #14 Wed, 4 Apr 01 14:13:01 EDT
Contents:
Re: patent this and patent that (Vernon Schryver)
PGP Private key cracking service ("Peter")
Re: Security of IAPM, alone. (Shai Halevi)
Re: PGP Private key cracking service ("Tom St Denis")
Re: PGP Private key cracking service ("James Wyatt")
Re: PGP Private key cracking service (Jim Gillogly)
Re: PGP Private key cracking service ("Sam Simpson")
Re: PGP Private key cracking service ("Tom St Denis")
Re: PGP Private key cracking service (Roman Katzer)
Encrypted Swap in Linux 2.4 - Was supposed to work since 2.4.2ac8 or something...
Anyone have any luck with this? (~JennyDriver)
Re: How do I exchange the values of A and B (Mikito Harakiri)
Re: keys and random (David Wagner)
Re: Security of IAPM, alone. (David Wagner)
Re: Factoring.... (Stefan Katzenbeisser)
Re: Matrix PK idea? (Mike Rosing)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: patent this and patent that
Date: 4 Apr 2001 09:18:32 -0600
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> ...
>Patents are complex legal documents constructed by humans, granted by
>humans, and administered by humans. Of course there are going to be
>problems. Legal systems are inherently inconsistent. Do you really
>imagine that we should not be overjoyed by any legal ownership process
>which has problems in only 1 in a million cases? Wouldn't life be
>nice if everything was perfect?
Yes, that's what patent lawyers tell suckers buying their tickets
in the patent lottery.
>In reality, I expect there are lots more examples of patent problems.
>But, in general, the system creaks along, despite having what I think
>is our major government example of an "old-world-style bureaucracy."
Yes, but those who are intellectually honest ask what the system is
trying to accomplish as it creaks along. The history of of software
patents demonstrates that fostering innovation is not only not one
of its goals, but one of the things that it tries to stop and prevent.
>>Other great examples include the Motorola-Codex patent on TCP/IP
>>header compression whose only problem was that it was filed after
>>that stuff was already shipping,
>
>Unless things have changed recently, as far as I know it is perfectly
>reasonable to file for US patent up to a year after implementations
>are shipped.
In this case the "shipping" had nothing to do with Codex, but included
the discussion and publication in a standards committee. Those facts
might be why Motorola-Codex conveniently ignored TCP/IP header
compression while it was trying to stop the standardization of PPP
data compression by the IETF, and why that patent faded.
>>or the other Motorola-Codex patent
>>that essentially patents x.25 only 20+ years too late.
>
>Well, "essentially" is the problem. To know what a patent really is,
>one has to examine the actual claims in detail. It is very
>appropriate to take prior art, modify it, and then patent the modified
>scheme. Patenting individual ciphers is sort of like that.
Yes, that's what the patent lawyers tell suckers buying tickets in
the patent lottery. It's also what big companies' patent lawyers
tell courts when fielding blocking patents.
I have seen patents that I think were worthwhile. For example, I
disagree with many and think the infamous LZW patent was about a
genuinely novel idea. However, the existence of the IBM patent on
the same idea, the earlier date on the IBM patent, the history of
Unisys's efforts to profit from the Welch patent are eloquent
statements about other evils of the system.
>>I wonder how many patents are as bad as those or the various "blocking"
>>patents seen in the 19th Century history of firearms and the late 20th
>>Century history of ink jet printers.
>
>The whole point of the ideal patent document is to construct a
>limited-term monopoly. Unless a patent is a monopoly, it does not
>force someone to license it. When a patent can be "engineered
>around," some people are not paying for the research which lead to the
>patent.
The point of those blocking patents was to prevent innovation. They
had nothing to do with compensating inventors or fostering the development
of science and technology. The idea is that while you're setting up
your factory, your look for and patent all of the other ways you can
find to make your product as well as products that serve similar purposes.
You don't do any real research or inventing, but merely try think of
all of the obvious ways that a competitor could compete. The idea is
to create a monoploy, but it is antithetical to the nominal purpose of
patents, which is something about fostering innovation.
> ...
>Normally, assuming basic requirements are met, the PTO just grants the
>patent. If the patented thing is useless (i.e., not "a real
>invention"), the patent is just worthless, and does not affect
>anybody.
That statement is at best grossly uninformed. Only someone with no
experience in industry could make it honestly. Those of us in the
software industry spend significant time talking to patent lawyers.
True, much of that wasted time is about getting yet more stupid patents.
Most patents are filed, granted, and never licensed, but you still
must check for stupid patents if you're building anything whose workings
will be visible, such as non-proprietary protocols. The cost of
fighting a stupid patent is essentially never worthwhile, so you always
just work around it. If you're building something whose insides will
be not be visible, such as the inner workings of much software, you
can just ignore the patent extortionists, since they'll never know to
get court orders to read a company's trade secret source. It's only
open protocols, free software, and external specifications that are
affected by software patents, such as the .gif format.
Another fact contrary to the baloney of patent advocates is that patents
do not, as they claim, lead to or involve the publishing of new ideas.
Real innovators do not search existing patents for ideas on how to do
things. That's too expensive and painful. Instead everyone who creates
things first does the creating, then hires patent lawyers to look for
problems, and finally adjusts the creation to avoid the problems.
>From years of reading Mr. Ritter's complaints about how no one wants
to license his patents and about the unfairness of the AES rules, I
know that there is no chance that he might advert to any systematic
problems with patents. He invested too much time, money, and ego in
his patent lottery tickets to believe that he was playing the sucker.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: "Peter" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: PGP Private key cracking service
Date: Wed, 4 Apr 2001 15:54:16 +0000 (UTC)
I forgot my passphrase...
Are there any tools I could use to try to crack my private key passphrase?
Is there a (commercial) service that does this for me?
Peter
------------------------------
From: Shai Halevi <[EMAIL PROTECTED]>
Subject: Re: Security of IAPM, alone.
Date: Wed, 04 Apr 2001 12:04:24 -0400
David Wagner wrote:
> Benjamin Goldberg wrote:
> >The IAPM chaining mode can be described as follows:
> >w(x) = E(k0, iv0 + x) (for x = 0..log2(messagelength))
> >s(i) = XOR-sum of a subset of w, selected with binary_greycode(i)
> >ct[i] = s(i) XOR E(k1, s(i) XOR pt[i])
> >
> >I'm curious. How secure is this scheme if k1 is fixed, perhaps at 0?
>
> Great question!
>
> I'm not sure, but I _think_ it might be quite secure, if we assume
> E(k1, .) behaves like a random permutation when k1 is fixed.
If you assume that, then the analysis goes through without any change.
But is this a reasonable assumption to make, when E is a contemporary
block cipher?
> The analogy to the Even-Mansour construction (which does have
> a proof of security) is quite intriguing.
This "proof of security" is done in a model where the only access to E is
via "black box" calls. Again, this does not tell you all that much about
the security when E is implemented as a block cipher with known key.
After all, these ciphers were not really analyzed with this model in
mind, and some attacks may be a whole lot easier to mount when you know
the key.
Implicit in the Even-Mansour model is the assumption that the only event
that is of use to the attacker, is when you have a "collision". I.e.,
two different queries result in the application of E (or its inverse) on
the same value. For a block cipher with known key, this is probably not
the case: applying the cipher on several "related" blocks may also be
useful.
The bottom line here is that block ciphers that are otherwise perfectly
fine, may turn out to be insecure in the Even-Mansour construction (resp.
the IAPM-with-fixed-k1 construction).
-- Shai
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: Re: PGP Private key cracking service
Date: Wed, 04 Apr 2001 16:13:27 GMT
"Peter" <[EMAIL PROTECTED]> wrote in message
news:01c0bd1f$7f5756c0$2471310a@u51376...
> I forgot my passphrase...
>
> Are there any tools I could use to try to crack my private key passphrase?
>
> Is there a (commercial) service that does this for me?
This is a stupid question, go away troll boy.
If PGP was so easy to break, why would you use it?
Tom
------------------------------
From: "James Wyatt" <[EMAIL PROTECTED]>
Subject: Re: PGP Private key cracking service
Date: Wed, 04 Apr 2001 16:13:44 GMT
Are you for real?
"Peter" <[EMAIL PROTECTED]> wrote in message
news:01c0bd1f$7f5756c0$2471310a@u51376...
> I forgot my passphrase...
>
> Are there any tools I could use to try to crack my private key passphrase?
>
> Is there a (commercial) service that does this for me?
>
> Peter
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: Re: PGP Private key cracking service
Date: Wed, 04 Apr 2001 09:25:10 -0700
Peter wrote:
>
> I forgot my passphrase...
>
> Are there any tools I could use to try to crack my private key passphrase?
>
> Is there a (commercial) service that does this for me?
Tools have been written to do this -- you might try a web search.
If you were at all sensible with your passphrase selection you're
totally out of luck, and you'll need to create a new key and write
off any encrypted data you left lying around. On the other hand,
if you're the type that picks a dictionary word or a date, you have
a good chance of recovering it.
--
Jim Gillogly
Mersday, 13 Astron S.R. 2001, 16:23
12.19.8.1.19, 13 Cauac 2 Uayeb, Third Lord of Night
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: Re: PGP Private key cracking service
Date: Wed, 4 Apr 2001 17:25:00 +0100
Think it through Tom: PGP allows _blank_ passphrases - wouldn't you say that
makes it 'easy to break' in some instances?
--
Regards,
Sam
http://www.scramdisk.clara.net/
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:HKHy6.19051$[EMAIL PROTECTED]...
>
> "Peter" <[EMAIL PROTECTED]> wrote in message
> news:01c0bd1f$7f5756c0$2471310a@u51376...
> > I forgot my passphrase...
> >
> > Are there any tools I could use to try to crack my private key
passphrase?
> >
> > Is there a (commercial) service that does this for me?
>
> This is a stupid question, go away troll boy.
>
> If PGP was so easy to break, why would you use it?
>
> Tom
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: Re: PGP Private key cracking service
Date: Wed, 04 Apr 2001 16:28:23 GMT
"Sam Simpson" <[EMAIL PROTECTED]> wrote in message
news:TSHy6.1091$[EMAIL PROTECTED]...
> Think it through Tom: PGP allows _blank_ passphrases - wouldn't you say
that
> makes it 'easy to break' in some instances?
>
Anyone who uses a blank password deserves the security of double ROT-13.
Tom
------------------------------
From: Roman Katzer <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security,comp.security.misc,comp.security.pgp.discuss,comp.security.pgp.tech,de.comp.security
Subject: Re: PGP Private key cracking service
Date: Wed, 04 Apr 2001 18:39:10 +0200
On Wed, 4 Apr 2001 15:54:16 +0000 (UTC), Peter wrote:
>Is there a (commercial) service that does this for me?
Try www.nsa.gov, if what you have encrypted are national or foreign state
secrets *fg*
Roman
------------------------------
From: ~JennyDriver <[EMAIL PROTECTED]>
Subject: Encrypted Swap in Linux 2.4 - Was supposed to work since 2.4.2ac8 or
something... Anyone have any luck with this?
Date: Wed, 04 Apr 2001 12:33:55 -0400
Encrypted Swap in Linux 2.4 - Was supposed to work since 2.4.2ac8 or
something... Anyone have any luck with this? I tried on 2.4.2-ac13,
and would get segfaults in swapon when mounting the encrypted swap
volume.
------------------------------
From: Mikito Harakiri <[EMAIL PROTECTED]>
Subject: Re: How do I exchange the values of A and B
Date: Wed, 04 Apr 2001 16:48:48 GMT
In article <9aeolo$gjc$[EMAIL PROTECTED]>, Stefek Zaba says...
>
>In sci.crypt, Dave Moore [EMAIL PROTECTED]> (ROT13=) wrote:
>> Back when Dinosaurs roamed the Earth and 64K was fully populated memory this
>> was a classic.
>
>> Assuming "A" and "B" contain integers, reverse their contents without using a
>> 3rd storage location.
>
>> A' = A xor B
>> B' = B xor A' = B xor (A xor B) = A
>> A''= A' xor B' = (A xor B) xor A = B
>
>> Three instructions, and depending on the processor sometimes faster than using
>> a 3rd location. But OBTUSE ! Doing this without comments was a capital
>> offense.
>
>And often coded as a C preprocessor macro. And giving rise to unexpected
>consequences when A and B turn out to refer to the same storage location,
>which promptly gets zero'd. Which makes for a nice toy example for formal
>proof-of-correctness tools.
>
This discussion has been iterated infinite times already in the other
newsgroups. I'm not talking about processor instructions, though. For this forum
the question is: What class of encrypt functions beyond xor allows me to do the
same?
BTW, javascript has an interesting answer too:
var a;
var b;
a = [a,b] // can squeeze quite a lot of info!
b = a[1];
a = a[0];
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: keys and random
Date: 4 Apr 2001 17:14:16 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Mark Wooding wrote:
>There are some sly active attacks against Diffie-Hellman exchanges and
>similar which force values into different subgroups. You resist these
>attacks by (a) noticing when something is in the trivial subgroup (1,
>-1) and (b) making sure that it doesn't matter when this happens because
>all the other subgroups are at least as difficult as your main one
>anyway.
I agree with your first statement, but I'd like to see some
further evidence for the second one. What if I replace g^x
(in the subgroup) by - g^x? This won't be detected by your
measures, but I can easily imagine using it to attack a protocol.
(For instance, suppose the receiver computes (g^x)^y, where y
is a long-term secret. Then the resulting key exchange will
succeed iff y is even, potentially revealing one bit of
information on y per key exchange.)
It seems to me that it would be prudent to check that all
received values that are supposed to be in the subgroup are
indeed in the subgroup. This can be done by checking that
X = g^x is not 1, and that X^q = 1 mod p, if q is prime.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Security of IAPM, alone.
Date: 4 Apr 2001 17:17:13 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Shai Halevi wrote:
>David Wagner wrote:
>> I'm not sure, but I _think_ it might be quite secure, if we assume
>> E(k1, .) behaves like a random permutation when k1 is fixed.
>
>If you assume that, then the analysis goes through without any change.
>But is this a reasonable assumption to make, when E is a contemporary
>block cipher?
No, not especially. But: A proof of security in the Shannon
model is better than no proof at all. :-)
Yes, I agree that the limitations of the Shannon / Even-Mansour
style models are important and should not be overlooked (and I
should not have omitted them). Thank you for giving an excellent
summary of these issues!
------------------------------
Date: Wed, 04 Apr 2001 19:59:22 +0200
From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Subject: Re: Factoring....
Jeffrey Walton wrote:
> Thank you Tom. I realize I'm somewhat backwards. Assume factoring is
> is only as hard as finding the square root of a quadratic residues in
> modulo n (n = p*q - got it right this time :). The supposition does
> indeed seem to be backwards. This is by intent.
Sorry, but there seems to be some sort of confusion here; by definition
"as hard as" is a symmetric relation. It is normally defined using
so-called reductions. Very informally, we say that a problem A is reducible
to a problem B if solutions of A can be computed by a program that uses
an algorithm for solving B as a subroutine. In other words, knowledge of
an algorithm for solving B suffices to construct an algorithm for solving
A that has only a "small" overhead. Two problems A and B are "computationally
equivalent" if A is reducible to B and B is reducible to A. In this case,
we say that problem A is as hard as problem B.
Computing square roots modulo n=pq is really computationally equivalent to
factoring n, you can show both directions. Thus, if you can factor you can
compute square roots efficiently and if you find any algorithm that computes
square roots mod n, you can extend this algorithm to a factorization method.
> Does this mean factoring is NOT an np class problem?
No. Factoring (the corresponding decision problem) is known to be in NP;
this follows quite easily from the fact that deciding whether an arbitrary
integer is a prime is in NP (Pratt's Theorem).
> Further, does this mean factoring is now a p class problem.
No.
> I'm not inferring anything
> about p = np (or they not equal), or the possible union of np and np
> complete. I know there's an active debate about where factoring lies
> (p, np, or np complete).
It is definitively in NP; but it is an open question whether it is
in P or it is NP complete (there are some good arguments that both
answers are negative).
--Stefan.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Matrix PK idea?
Date: Wed, 04 Apr 2001 12:54:15 -0500
Tom St Denis wrote:
> Ahh but doesn't the summations mess around with index calculus methods of
> discrete logs?
Yeah, it probably does. but it makes it easier, not harder! That's because
you're creating more stucture, and more structure gives more room and leverage
for attacks.
That's why *really* conservative coders use GF(p) for ECC - it's already at
the simplest level you can get. With GF(2^n) there's more structure to work
with.
A more interesting line of attack might be to look at non-euclidian spaces
and see if any can be fit with GF. I'm not sure it's possible, but it would
be weird :-)
Patience, persistence, truth,
Dr. mike
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
