AW: [smb@cs.columbia.edu: Skype security evaluation]
-----Urspr|ngliche Nachricht----- Von: owner-cryptography@metzdowd.com [mailto:owner-cryptography@metzdowd.com] Im Auftrag von cyphrpunk Gesendet: Freitag, 28. Oktober 2005 06:07 An: cypherpunks@jfet.org; cryptography@metzdowd.com Betreff: Re: [smb@cs.columbia.edu: Skype security evaluation]
Wasn't there a rumor last year that Skype didn't do any encryption padding, it just did a straight exponentiation of the plaintext?
Would that be safe, if as the report suggests, the data being encrypted is 128 random bits (and assuming the encryption exponent is considerably bigger than 3)? Seems like it's probably OK. A bit risky perhaps to ride bareback like that but I don't see anything inherently fatal.
There are results available on this issue: First, a paper by Boneh, Joux, and Nguyen "Why Textbook ElGamal and RSA Encryption are Insecure", showing that you can essentially half the number of bits in the message, i.e. in this case the symmetric key transmitted. Second, it turns out that the tricky part is the implementation of the decryption side, where the straight-forward way -- ignoring the padding with 0s "They are zeroes, aren't they?" -- gives you a system that might be attacked in a chosen plaintext scenario very efficiently, obtaining the symmetric key. See my paper "Side-Channel Attacks on Textbook RSA and ElGamal Encryption" at PKC2003 for details. Hope this answers your question. Ulrich
On 10/31/05, Kuehn, Ulrich <Ulrich.Kuehn@telekom.de> wrote:
There are results available on this issue: First, a paper by Boneh, Joux, and Nguyen "Why Textbook ElGamal and RSA Encryption are Insecure", showing that you can essentially half the number of bits in the message, i.e. in this case the symmetric key transmitted.
Thanks for this pointer. In the case of Skype it would be consistent with the security report if they are encrypting random 128 bit values under each other's RSA keys, unpadded, and exchanging them, then hashing the pair of 128 bit values together to generate their session keys. The paper above shows an easy birthday attack on such encryptions. Approximately 18% of 128 bit numbers can be expressed as a product of two 64-bit numbers. For such keys, if the ciphertext is C, consider all 2^64 values m1 and m2, and compare m1^e with C/m2^e. This can be done in about 2^64 time and memory, and if the plaintext is in that 18%, it will be found as m1*m2. Based on these comments and others that have been made in this thread, the Skype security analysis seems to have major flaws. We have a reluctance in our community to criticize the work of our older members, especially those like Berson who have warm personalities and friendly smiles. But in this case the report leaves so much unanswered, and focuses inappropriately on trivial details like performance and test vectors, that overall it can only be called an entirely unsatisfactory piece of work. CP
What is the threat model? Even ROT-13 would thwart casual listening on or data harvesting. If you to be secure then you use voice over IPSec, PGPhone or any of dozens of other solutions. The idea that a commercial carrier can or should provide NSA-proof security boggles the mind. Nice masturbatory material though.
The paper above shows an easy birthday attack on such encryptions. Approximately 18% of 128 bit numbers can be expressed as a product of two 64-bit numbers. For such keys, if the ciphertext is C, consider all 2^64 values m1 and m2, and compare m1^e with C/m2^e. This can be done in about 2^64 time and memory, and if the plaintext is in that 18%, it will be found as m1*m2.
end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: __________________________________ Yahoo! FareChase: Search multiple travel sites in one click. http://farechase.yahoo.com
On 11/4/05, Morlock Elloi <morlockelloi@yahoo.com> wrote:
What is the threat model? Even ROT-13 would thwart casual listening on or data harvesting. If you to be secure then you use voice over IPSec, PGPhone or any of dozens of other solutions.
The idea that a commercial carrier can or should provide NSA-proof security boggles the mind. Nice masturbatory material though.
It's not too much to ask that Skype provide real security. It's no harder to do that than to offer fake security. And more to the point, this so-called security review should have been able to pinpoint these security weaknesses rather than running test vectors against its algorithms. (Granted, the review did in fact identify several weaknesses, but it appears to have glossed over others.) CP
-- 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
In message <43713115.4942.4A3995E@localhost>, "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
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 <43713115.4942.4A3995E@localhost>, "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 majordomo@metzdowd.com
participants (6)
-
cyphrpunk -
James A. Donald -
Kuehn, Ulrich -
Morlock Elloi -
Steven M. Bellovin -
William Arbaugh