08-25-2005, 06:27 AM
Tras los recientes avances efectuados por la Doctora Xiaoyun Wang y su equipo de analistas criptógrafos, parece obvio que se avecinan nuevos tiempos para la criptografía.
Durante los últimos meses hemos asistido a lo que sólo era una cuestión de tiempo: algunos algoritmos como SHA-1 y MD5 han quedado en entredicho, al ejecutar distintos investigadores, principalmente los adscritos al equipo de Wang, ataques mediante los cuales se ha posibilitado la ruptura de ambos algoritmos...
Las funciones hash de una dirección cumplen siempre dos propiedades: la primera es la unidireccionalidad, mediante la cual se establece la imposibilidad de obtener la palabra clave a partir del hash obtenido, siendo únicamente posible calcular el hash a partir de la palabra clave. Esta imposibilidad debe entenderse como capacidad de revertir la función hash en un tiempo razonable. La segunda propiedad básica es que las funciones hash deben estar libres de colisiones. Es decir, dos mensajes distintos no pueden generar una misma suma hash. En el momento que alguna o ambas condiciones se incumple, la función hash se dice ha sido rota.
A la hora de documentar colisiones, es fundamental hablar de la posibilidad de encontrar una colisión en función de la robustez del algoritmo. Para un algoritmo como SHA-1, que emplea 160 bit, tenemos que la posibilidad de encontrar una colisión por fuerza bruta es de 1 entre 280. En el caso de MD5, que emplea 128 bit, la posibilidad aumenta a 264. El patrón de hallar esa posibilidad es siempre 1/2^[n/2], siendo n el número de bit. Sea como fuere, es frecuente hablar de hash o algoritmo roto cuando se demuestra matemáticamente que es posible encontrar colisiones con una velocidad inferior al número teórico anteriormente citado.
La doctora Wang y su equipo, por ejemplo, han documentado la ruptura de SHA-1 con una reducción probabilística a 2^63. Previamente, habían logrado reducir la cifra a 2^69. Tal ycomo hemos visto, la complejidad de ruptura por fuerza bruta es de 2^80. Dividiendo, es fácil comprobar que la doctora Wang y su equipo han hallado colisiones 131072 veces más rápido que mediante un ataque de fuerza bruta. Y según opinan muchos expertos, 2^63 no parece un límite no mejorable. Todo apunta a que según progrese la investigación, se mejorarán las cifras y por tanto, SHA-1 será paulatimanente más vulnerable.
Llegados a este punto, conviene preguntarse qué implica esto para la vida útil de los algoritmos MD5 y SHA-1. Muchos medios se apresuran a tachar los algoritmos como totalmente inválidos a tenor de los resultados, y proclaman su sustitución inmediata como estándar de facto. Pensando sobre el tema, llegamos a la conclusión de que quizás esto sea algo precipitado.
nota completa: http://www.kriptopolis.org/node/1042
Durante los últimos meses hemos asistido a lo que sólo era una cuestión de tiempo: algunos algoritmos como SHA-1 y MD5 han quedado en entredicho, al ejecutar distintos investigadores, principalmente los adscritos al equipo de Wang, ataques mediante los cuales se ha posibilitado la ruptura de ambos algoritmos...
Las funciones hash de una dirección cumplen siempre dos propiedades: la primera es la unidireccionalidad, mediante la cual se establece la imposibilidad de obtener la palabra clave a partir del hash obtenido, siendo únicamente posible calcular el hash a partir de la palabra clave. Esta imposibilidad debe entenderse como capacidad de revertir la función hash en un tiempo razonable. La segunda propiedad básica es que las funciones hash deben estar libres de colisiones. Es decir, dos mensajes distintos no pueden generar una misma suma hash. En el momento que alguna o ambas condiciones se incumple, la función hash se dice ha sido rota.
A la hora de documentar colisiones, es fundamental hablar de la posibilidad de encontrar una colisión en función de la robustez del algoritmo. Para un algoritmo como SHA-1, que emplea 160 bit, tenemos que la posibilidad de encontrar una colisión por fuerza bruta es de 1 entre 280. En el caso de MD5, que emplea 128 bit, la posibilidad aumenta a 264. El patrón de hallar esa posibilidad es siempre 1/2^[n/2], siendo n el número de bit. Sea como fuere, es frecuente hablar de hash o algoritmo roto cuando se demuestra matemáticamente que es posible encontrar colisiones con una velocidad inferior al número teórico anteriormente citado.
La doctora Wang y su equipo, por ejemplo, han documentado la ruptura de SHA-1 con una reducción probabilística a 2^63. Previamente, habían logrado reducir la cifra a 2^69. Tal ycomo hemos visto, la complejidad de ruptura por fuerza bruta es de 2^80. Dividiendo, es fácil comprobar que la doctora Wang y su equipo han hallado colisiones 131072 veces más rápido que mediante un ataque de fuerza bruta. Y según opinan muchos expertos, 2^63 no parece un límite no mejorable. Todo apunta a que según progrese la investigación, se mejorarán las cifras y por tanto, SHA-1 será paulatimanente más vulnerable.
Llegados a este punto, conviene preguntarse qué implica esto para la vida útil de los algoritmos MD5 y SHA-1. Muchos medios se apresuran a tachar los algoritmos como totalmente inválidos a tenor de los resultados, y proclaman su sustitución inmediata como estándar de facto. Pensando sobre el tema, llegamos a la conclusión de que quizás esto sea algo precipitado.
nota completa: http://www.kriptopolis.org/node/1042