Kangaroo configuration for criptoanalysis of public key protocols

Abstract

[EN] The discrete logarithm problem is considered as the basis for proposing several public-key cryptographic protocols, regardless of whether they are proposed for encryption, signing or identification. Among the systems that use this problem is the Diffie-Hellman public key exchange protocol, commonly used in many applications, from instant messaging to private network access. One of the algorithms proposed to solve the discrete logarithm problem, and therefore useful to attack the cryptographic protocols that consider it, is known as the "kangaroo method". In this work, we analyze the behaviour of this algorithm, taking into account keys of different sizes, some alternatives in its implementation that modify its behaviour, as well as possible configurations of the algorithm, and the effect in its behaviour with respect to that of the original proposal, in order to check the effect in a cryptographic attack.

[ES] El problema del logaritmo discreto es uno de los problemas que hoy día se consideran como base para proponer protocolos criptográficos de clave pública (independientemente de si estos se proponen para el cifrado, firma o identificación). Entre los sistemas que utilizan este problema se encuentra el protocolo de intercambio público de claves de Diffie-Hellman, utilizado habitualmente en multitud de aplicaciones, desde la mensajería instantánea al acceso privado a redes. Uno de los algoritmos propuestos para resolver este problema, y por lo tanto utilizable para atacar los protocolos criptográficos que lo consideran, es conocido como el "método del canguro". En este trabajo se analiza el comportamiento de este algoritmo frente a claves de distinto tamaño, alternativas en su implementación que modifiquen su comportamiento, así como posibles configuraciones de este algoritmo analizando su comportamiento en un ataque criptográfico comparando el resultado respecto la propuesta original.

[CA] El problema del Logaritme Discret és un dels problemes que avui dia es consideren com a base per proposar protocols criptogràfics de clau pública (independentment de si aquests es proposen per al xifratge, signatura o identificació). Entre els sistemes que utilitzen aquest problema es troba el protocol d’intercanvi públic de claus de DiffieHellman, utilitzat habitualment en multitud d’aplicacions, des de la missatgeria instantània a l’accés privat a xarxes. Un dels algorismes proposats per resoldre aquest problema, i, per tant, utilitzable per atacar els protocols criptogràfics que ho consideren, és conegut com el “mètode del cangur”. En aquest treball s’analitza el comportament d’aquest algorisme davant de claus de diferent tamany, alternatives en la seva implementació que modifiquen el seu comportament, així com possibles configuracions d’aquest algorisme analitzant el seu comportament en un atac criptogràfic, comparant el resultat respecte a la proposta original.