How broad is the SPEKE patent.
-- 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]
RSA-640 factored
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]
RSA-640 factored
From: http://mathworld.wolfram.com/news/2005-11-08/rsa-640 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]
Re: How broad is the SPEKE patent.
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]
Re: RSA-640 factored
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 http://mathworld.wolfram.com/NumberFieldSieve.html. 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]
[Clips] Sony BMG's DRM provider does not rule out future use of stealth
--- 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] http://www.tgdaily.com/2005/11/04/f4i_says_sony_bmg_xcp_is_not_rootkit/print.html 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' systems and cleans up the mess
Re: RSA-640 factored
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]
Re: RSA-640 factored
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: How broad is the SPEKE patent.
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: gonzo cryptography; how would you improve existing cryptosystems?
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: http://www.apache-ssl.org/openpgp-pfs.txt 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): http://www.cypherpunks.ca/otr/ Jon - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
