RSA-algoritme is lek

Wetenschappers hebben een fout ontdekt in de manier waarop publieke sleutels worden gegenereerd met het RSA-algoritme voor het versleutelen van online communicatie en transacties. Een klein deel van de publieke sleutels, 27.000 van de 7,1 miljoen, zijn niet ad random tot stand gekomen. Daardoor is het mogelijk dat iemand de geheime priemgetallen kan achterhalen die gebruikt worden om een publieke sleutel te creëren. De onderzoekers verzamelden beveiligingssleutels op het web en controleerden de betrouwbaarheid van de sleutels, ervan uitgaande dat er elke keer afwijkende random keuzen zijn gemaakt, bij het aanmaken van de sleutels. Dat blijkt niet het geval te zijn: twee op elke duizend RSA-sleutels biedt geen beveiliging.

Dat maakt het RSA-algoritme onbetrouwbaar, stellen de onderzoekers. ‘Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for multiple-secrets cryptosystems such as RSA is signi cantly riskier than for single-secret ones such as ElGamal or (EC)DSA which are based on Diffe-Hellman’. De titel van de paper is ‘Ron was wrong, Whit is right’, is een verwijzing naar Ron Rivest, die aan de wieg stond van het RSA-algoritme (samen met Adleman en Shamir) en Whitfield Diffie die samen met Martin Hellman in 1976 het Diffie-Hellman (DH)-algoritme maakte.

Het onderzoek werd geleid door Arjen Lenstra, een Nederlandse professor crytologische algoritmen, werkzaam aan de Ecole Polytechnique Federale de Lausanne (EPFL). Het onderzoek werd uitgevoerd door een team van EPFL, en kenbaar gemaakt in een paper, waarover het team in augustus een presentatie zal verzorgen tijdens CRYPTO 2012 aan de Universiteit van Californië in Santa Barabara.

Inmiddels zijn de publieke sleutels verwijderd van de algemeen toegankelijke database om te voorkomen dat iemand de onbetrouwbaarheid van de sleutels misbruikt. Om de integriteit van beveiligde systemen te verzekeren, zullen website beheerders de gebruikte sleutels moeten aanpassen.

In hun paper stellen de onderzoekers dat ‘Overall, over the data we collected, 1024-bit RSA provides 99.8% security at best. More seriously, we stumbled upon 12,720 different 1024-bit RSA moduli that offer no security. Their secret keys are accessible to anyone who takes the trouble to redo our work’. In samenvatting concludeerden ze: ‘We find the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security’.

Cryptografen zijn onder de indruk van het onderzoek. ‘It is interesting. And great research’, zo stelde Bruce Schneier. Hij stelde dat de paper ‘is mainly a demonstration of the truism that random number generation is hard to do’. Of dit paniek teweeg brengt, is volgens Schneier niet zo waarschijnlijk. ‘But it will, like an Italian cruise ship running aground off the coast of Italy, make people wary of cruising – or maybe countries that begin with the letter ‘I”.

De onderzoeksdata zijn ‘under custody’ geplaatst, zodat ze niet kunnen worden geexploiteerd. Iemand die het onderzoek met dezelfde data wil overdoen, dient contact op te nemen met de onderzoekers.

They also said due to the difficulty in contacting individuals whose public key certificates they say are at risk, they have decided to put their project data “under custody” so that if anyone wants to exploit the current situation, they would have to redo the work, both the data collection and the calculation.

 

Share This:

Leave a Reply

Your email address will not be published. Required fields are marked *