Re: gonzo cryptography; how would you improve existing cryptosystems?

[Jon Callas]

On 4 Nov 2005, at 5:23 PM, Travis H. wrote:


For example, pgp doesn't hide the key IDs of the addressees.


But OpenPGP does. Here's an extract fro RFC 2440:

5.1. Public-Key Encrypted Session Key Packets (Tag 1)

[...]

   An implementation MAY accept or use a Key ID of zero as a "wild  
card"

   or "speculative" Key ID. In this case, the receiving implementation
   would try all available private keys, checking for a valid decrypted
   session key. This format helps reduce traffic analysis of messages.

Now, there has been much discussion about how useful this is, and  
there are other related issues like how you do the UI for such a  
thing. But the *protocol* handles it.


You might also want to look at the PFS extensions for OpenPGP:



and even OTR, which is very cool in its own right (and is designed to  
take care of the sort of edge conditions all of these other things  
have):




Jon


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: How broad is the SPEKE patent.

[William Arbaugh]

You may want to look at EAP-PAX. We tried to engineer around the  
patent land mines in the field when we designed it. This of course  
doesn't mean that someone won't claim it infringes on something.


We also have a proof (not yet published) of security in a random  
oracle model.


Best, Bill

p.s. EAP-PAX is work with my student T. Charles Clancy.

On Nov 9, 2005, at 10:54 AM, Steven M. Bellovin wrote:

In message <[EMAIL PROTECTED]>, "James A. Donald"  
writes:



   --
Does SPEKE claim to patent any uses of zero knowledge
proof of possession of the password for mutual
authentication, or just some particular method for
establishing communications?   Is there any way around
the SPEKE patent for mutual authentication and
establishing secure communications on a weak passphrase?




It certainly doesn't claim EKE, by myself and Michael Merritt,  
since he

and I invented the field.  Of course, EKE is also patented.

SRP is patented but royalty-free.  Some of have claimed that it
infringes the EKE patent; since I don't work for the EKE patent owner
(Lucent), I've never tried to verify that.

Radia Perlman and Charlie Kaufman invented PDM specifically as a
patent-free method.  However, the claim was made that it infringed the
SPEKE patent.  Since it wasn't patented, there was no one willing to
spend the money on legal fees to fight that claim, per a story I  
heard.


Have a look at http://web.archive.org/web/20041018153649/ 
integritysciences.com/history.html

for some history.

--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to  
[EMAIL PROTECTED]





-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: RSA-640 factored

[Simon Josefsson]

Victor Duchovni <[EMAIL PROTECTED]> writes:

> On Wed, Nov 09, 2005 at 05:27:12PM +0100, Simon Josefsson wrote:
>
>> I'm not sure translating complexity into running time is reasonable,
>> but pending other ideas, this is a first sketch.
>> 
>
> It is not reasonable, because the biggest constraint is memory, not
> CPU. Inverting the matrix requires increasingly prohitive quantities
> of RAM. Read the DJB hardware GNFS proposal.

Can we deduct a complexity expression from it, that could be used to
(at least somewhat reliably) predict the cost of cracking RSA-768 or
or RSA-1024, based on the timing information given in this report?
The announcement doesn't say how much memory these machines had,
though, but perhaps that information can be disclosed.

Thanks,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: RSA-640 factored

[Victor Duchovni]

On Wed, Nov 09, 2005 at 05:27:12PM +0100, Simon Josefsson wrote:

> I'm not sure translating complexity into running time is reasonable,
> but pending other ideas, this is a first sketch.
> 

It is not reasonable, because the biggest constraint is memory, not
CPU. Inverting the matrix requires increasingly prohitive quantities
of RAM. Read the DJB hardware GNFS proposal.

-- 

 /"\ ASCII RIBBON  NOTICE: If received in error,
 \ / CAMPAIGN Victor Duchovni  please destroy and notify
  X AGAINST   IT Security, sender. Sender does not waive
 / \ HTML MAILMorgan Stanley   confidentiality or privilege,
   and use is prohibited.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

[Clips] Sony BMG's DRM provider does not rule out future use of stealth

[R. A. Hettinga]

--- begin forwarded text


 Delivered-To: [EMAIL PROTECTED]
 Date: Wed, 9 Nov 2005 10:50:05 -0500
 To: Philodox Clips List <[EMAIL PROTECTED]>
 From: "R. A. Hettinga" <[EMAIL PROTECTED]>
 Subject: [Clips] Sony BMG's DRM provider does not rule out future use of
stealth
 Reply-To: [EMAIL PROTECTED]
 Sender: [EMAIL PROTECTED]

 


 Tom's Guide Daily

 Sony BMG's DRM provider does not rule out future use of stealth
 By Scott M. Fulton, III
 Published Friday 4th November 2005 22:27 GMT


 Oxfordshire (UK) - The CEO of the company which provides digital rights
 management tools and software to global music publisher Sony BMG, and which
 developed the XCP system that was the subject of controversy this week,
 told TG Daily in an exclusive interview that, despite what some security
 software engineers, news sources, and bloggers have suggested, XCP is not,
 and was never designed to be, a rootkit.

 "We believe there are some comments that have been misunderstood in the
 media," said Matthew Gilliat-Smith, chief executive officer of First 4
 Internet, the manufacturers of XCP. "Our view is that this is a 'storm in a
 teacup,' as we say over here in the UK ... I want to confirm that this is
 not malware. It's not spyware. There's nothing other than pure content
 protection, which is benign."



 As we reported yesterday
 (http://www.tgdaily.com/2005/11/03/sony_bmg_xcp_is_it_a_rootkit/), security
 software engineer Mark Russinovich discovered, through the use of a program
 he wrote called RootkitRevealer, that drivers deposited on his system from
 a Sony BMG audio CD he purchased were using stealth techniques to hide
 their appearance not only from the user, but also from portions of the
 Windows operating system. These drivers had been installed in such a way
 that they were run perpetually, loaded automatically - even in safe mode -
 and were referenced in the Windows System Registry using a method that
 could not be deleted without extensive reworking of the Registry, to enable
 the operating system to recognize the CD-ROM drive again. In his
 investigation, he identified these drivers as part of the XCP copy
 protection system.

 Russinovich's story, posted to his company's Web site
 (http://www.sysinternals.com/Blog/), was widely read and generated enormous
 response from bloggers, some of whom believed either that Russinovich was
 suggesting, or that his evidence had substantiated, that XCP constituted a
 rootkit. Under the more technical definition of that term, it would have to
 open up an unmonitored Internet connection with a remote host, probably
 with the intention of delivering a malicious payload in a very undetectable
 manner. No such allegations were made of such behavior by Russinovich, yet
 the characterization hung in the air.

 "There's areas of misinformation which I'd be very happy to set straight,"
 Gilliat-Smith told us. "The first is [the allegation that XCP is some form
 of] rootkit technology, in the form that would be used to spread malware.
 What it is, it's using cloaking techniques that are similar to a rootkit,
 for the purpose of making speed bumps on the content protection, to make it
 more difficult to circumvent the protection."

 Gilliat-Smith said his software does not open up any connection between the
 stealth driver and its host. "Ours does not do that," he said. "All we're
 doing is using a hook and a redirect, so when you look for a file, it is
 hidden. It is very widely used...since way back in 1994, by many shareware
 companies and anti-virus companies."

 A paper describing what appears to be the "hook and redirect" method to
 which Gilliat-Smith refers, published by the online hacker magazine
 Phrack.org, defines rootkit as "a program designed to control the behavior
 of a given machine. This is often used to hide the illegitimate presence of
 a backdoor and other such tools. It acts by denying the listing of certain
 elements when requested by the user, affecting thereby the confidence that
 the machine has not been compromised." By "backdoor," the paper can be
 presumed to mean a method by which a remote party can take control of the
 system undetected. Gilliat-Smith denies any such methods are, or have ever
 been, used by XCP.

 Furthermore, Gilliat-Smith stated, the version of XCP which utilized this
 "hook and redirect" method to hide the presence of the persistent driver,
 is no longer being used in new audio CDs. At the time these concerns arose,
 he said, "we had already created the new version of the software, which
 provides a range of additional features for the consumer. We have moved
 away from the cloaking technology that gives rise to these concerns."

 First 4 Internet (F4i) has made available to Sony BMG a removal tool, which
 users can download from Sony BMG's Web site
 (http://cp.sonybmg.com/xcp/english/updates.html), that removes the XCP
 driver from users' sy

Re: RSA-640 factored

[Simon Josefsson]

"Steven M. Bellovin" <[EMAIL PROTECTED]> writes:

> http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

There are timing details in:

http://www.crypto-world.com/announcements/rsa640.txt

They claim they need 5 months of 80 machines with 2.2GHz processors.

Using these numbers, I think it would be interesting to come up with
an estimate of how expensive it would be to crack larger RSA keys for
someone who used the same software.  I'll make an attempt to do this
below, but I reckon I will make errors...  please correct me.

The complexity for the GNFS is roughly

O(exp(1.9(log n)^.3 * (log log n)^.66)

where n is the number to factor, according to
.

I'm not sure translating complexity into running time is reasonable,
but pending other ideas, this is a first sketch.

Let's input the numbers for 2^640:

octave:26> n=2^640
n =  4.5624e+192
octave:27> a=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
a =  1.7890e+21

And let's input them for 2^768:

octave:28> n=2^768
n =  1.5525e+231
octave:29> b=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
b =  1.0776e+23

Let's compute the difference:

octave:30> b/a
ans = 60.232

In other words, cracking a RSA-768 key would take 60 times as long,
assuming the running time scale exactly as the complexity (which is
unlikely).

So it seems, if you have 80*60 = 4800 machines, you would be able to
crack a RSA-768 key in 5 months.

Continuing this to 1024 bit keys...  (or rather 1023 since Octave
believe 2^1024=Inf)

octave:40> n=2^1023
n =  8.9885e+307
octave:41> c=e^(1.923*(log(n))^(1/3)*(log(log(n)))^(2/3))
c =  1.2827e+26
octave:42> c/a
ans =  7.1697e+04
octave:43>

I.e., RSA-1024 is about 7 times as difficult as RSA-640 using
GNFS.  If you have 80*7 = 560 machines, you would be able to
crack a 1024 bit RSA keys in 5 months.  Or put differently, if you had
10.000 CPUs it would take 5*80*7/1/12 = 233 years to factor a
RSA-1024 key.

I know there are many hidden assumptions here, and I probably made
mistakes when computing this.  Please point out flaws so we can get
accurate numbers.

Cheers,
Simon

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: How broad is the SPEKE patent.

[Steven M. Bellovin]

In message <[EMAIL PROTECTED]>, "James A. Donald" writes:
>--
>Does SPEKE claim to patent any uses of zero knowledge
>proof of possession of the password for mutual
>authentication, or just some particular method for
>establishing communications?   Is there any way around
>the SPEKE patent for mutual authentication and
>establishing secure communications on a weak passphrase? 
>

It certainly doesn't claim EKE, by myself and Michael Merritt, since he 
and I invented the field.  Of course, EKE is also patented.  

SRP is patented but royalty-free.  Some of have claimed that it 
infringes the EKE patent; since I don't work for the EKE patent owner 
(Lucent), I've never tried to verify that.

Radia Perlman and Charlie Kaufman invented PDM specifically as a 
patent-free method.  However, the claim was made that it infringed the 
SPEKE patent.  Since it wasn't patented, there was no one willing to 
spend the money on legal fees to fight that claim, per a story I heard.

Have a look at 
http://web.archive.org/web/20041018153649/integritysciences.com/history.html
for some history.

--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

RSA-640 factored

[Heyman, Michael]

From: 



November 8, 2005--A team at the German Federal Agency 
for Information Technology Security (BSI) recently 
announced the factorization of the 193-digit number 

310 7418240490 0437213507 5003588856 7930037346 
0228427275 4572016194 8823206440 5180815045 5634682967 
1723286782 4379162728 3803341547 1073108501 9195485290 
0733772482 2783525742 3864540146 9173660247 7652346609 

known as RSA-640. The team responsible for this 
factorization is the same one that previously factored 
the 174-digit number known as RSA-576 (MathWorld 
headline news, December 5, 2003) and the 200-digit 
number known as RSA-200 (MathWorld headline news, 
May 10, 2005). 

-Michael Heyman

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

RSA-640 factored

[Steven M. Bellovin]

http://mathworld.wolfram.com/news/2005-11-08/rsa-640/

--Steven M. Bellovin, http://www.cs.columbia.edu/~smb



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: [EMAIL PROTECTED]: Skype security evaluation]

[Joseph Ashwood]

- Original Message - 
From: "Marcel Popescu" <[EMAIL PROTECTED]>

Subject: RE: [EMAIL PROTECTED]: Skype security evaluation]



From: [EMAIL PROTECTED] [mailto:owner-
[EMAIL PROTECTED] On Behalf Of Peter Gutmann



I can't understand why they didn't just use TLS for the handshake (maybe
YASSL) and IPsec sliding-window + ESP for the transport (there's a free
minimal implementation of this whose name escapes me for use by people 
who

want to avoid the IKE nightmare).



Do you have some articles about these protocols?


The authoritative reference for TLS is the TLS RFC 
(http://www.ietf.org/rfc/rfc2246.txt). The authoritative reference for IPsec 
is of course the IPsec RFC (http://www.ietf.org/rfc/rfc2401.txt). As to why 
they wouldn't use these as they stand, synchronized protocols often require 
finer control over the data block size than these offer, but modification is 
easy enough, and would certainly have caused fewer concerns than a roll your 
own.
   Joe 




-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: Fermat's primality test vs. Miller-Rabin

[Alexander Klimov]

On Tue, 8 Nov 2005, Jeremiah Rogers wrote:
> > It appears that Fermat's test can be fooled by Carmichael numbers,
> > whereas Miller-Rabin is immune, but I'm not sure why.
>
> Where does it say Miller-Rabin is immune to Carmichael numbers?
> [...]
> To me it looks like M-R just eliminates some needless computation that
> a naive application of the Fermat test would require.

I guess the small increase in efficiency would not be worth additional
program code.  Although the Carmichael numbers fool the Fermat test
(that is, $a^{n-1} = 1 (n)$) for *all* a, there are no such things for
the Miller-Rabin test:  for any odd composite n at least 3/4 of a's
fail the test, that is if you made m MR tests with random a's then you
are mistaken with probability at most (1/4)^m.

-- 
Regards,
ASK

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

How broad is the SPEKE patent.

[James A. Donald]

--
Does SPEKE claim to patent any uses of zero knowledge
proof of possession of the password for mutual
authentication, or just some particular method for
establishing communications?   Is there any way around
the SPEKE patent for mutual authentication and
establishing secure communications on a weak passphrase? 

--digsig
 James A. Donald
 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG
 c3YaEtPqVbOMIjHk3eId6UngzMgXPFWqhwk9daye
 4S2HlmFAZeCAhYaaxiPBSR5+8yf8Wwqy+gi8rWY6f


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]