[smb at cs.columbia.edu: Skype security evaluation]

[cyphrpunk]

On 10/31/05, Kuehn, Ulrich <Ulrich.Kuehn at 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

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com