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