In January, John Proos, a PhD student at the University of Waterloo, published a research paper entitled “Imperfect Decryption and an Attack on the NTRU Encryption Scheme.” Proos found that given an NTRU public key, there exist ciphertexts that can be validly created using the public key but can’t be decrypted using the private key. The valid ciphertexts, that an NTRU secret key will not correctly decipher determine, up to a cyclic shift, the secret key. In this paper, Proos explains attacks based on this property against the NTRU primitive and many of the suggested NTRU padding schemes. These attacks are quite practical, taking a few minutes on a single PC. Visit http://www.cacr.math.uwaterloo.ca/techreports/2003/corr2003-01.pdf for a copy of Proos’ paper.

Factoring for 1024-bit RSA Keys

In February, Adi Shamir and Eran Tromer published “Factoring Large Numbers with the TWIRL Device”, which raises some concerns about the security of 1024-bit RSA keys. The security of RSA depends on the difficulty of factoring large integers. In 1999, a large distributed computation involving hundreds of workstations working for many months managed to factor a 512-bit RSA key, but 1024-bit keys were believed to be safe for the next 15-20 years. This paper describes a new hardware implementation, 3-4 orders of magnitude more cost effective than the best previously published designs, and suggests that factoring for 1024-bit RSA keys can be completed in less than a year by a $10M device. Visit http://www.wisdom.weizmann.ac.il/~tromer/papers/twirl.pdf to find a copy of the paper.

Validation for Elliptic Curve Public Keys

In January, Adrian Antipa, Daniel Brown, Alfred Menezes, Rene Struik and Scott Vanstone published “Validation of Elliptic Curve Public Keys” in Conference Proceedings of Public Key Cryptography – PKC 2003. In this work, they show that an implementation of elliptic curve cryptography (ECC) must be extremely careful to validate elliptic curve public keys, otherwise private keys could be compromised very easily. A few standards, including IEEE 1363-2000 neither require public key validation nor provide adequate warning, while other standards, including ANSI X9.63 require public key validation. Visit http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/Jan03.html to see the presentation.