| Kriptópolis alojado en |
| Zilos-Veloxia Network |
| Tu mejor defensa: |
| Bufet Almeida |
Se buscan candidatos para SHA-3
Enviado por admin el 9. Noviembre 2007 - 23:13.
El NIST considera factible demostrar la existencia de colisiones en SHA-1 (en ello estamos), pero consideraría catastrófico que se hallaran también en SHA-2, por lo que estima llegado el momento de empezar a buscar, con tiempo, un nuevo algoritmo de hash, que recibirá el nombre de SHA-3.
El sistema elegido para desarrollarlo es la competición pública, como ya se hizo en su día para la búsqueda de candidatos para el estándar oficial de cifrado AES. Es más: el NIST quiere que el algoritmo no sólo sea público, sino también que esté disponible libremente, sin ningún pago de derechos de propiedad intelectual...
El NIST considera escasos los 160 bits del resumen de SHA-1, así que quiere que el candidato disponga de la posibilidad de producir resúmenes de 224, 256, 384 y 512 bit, en correspondencia con las variantes actualmente existentes de SHA-2, al que aspira a sustituir.
- Cryptographic Hash Algorithm Competition [NIST].
- Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA–3) Family [Todos los detalles de la convocatoria, en pdf].
Colisiones?
Con la cantidad de pruebas que se han hecho (y kriptópolis lleva el record indiscutido), si no han podido demostrar existencia de colisiones en sha1, yo diría que podemos estar bastante tranquilos a ese respecto, ¿no?
Tal vez sea un poco apresurado ir buscando un sha-3 cuando todavía parece resistir muy bien el sha-1, aunque bueno, nunca está de más...
Parece que hay algo más
Según la web del grupo de la Universidad de Viena que está llevando a cabo el análisis, una vez encuentren una colisión por su método entonces sería capaces de encontrar otra colisión con la gorra. Supongo que están ajustando parámetros "a ciegas" pero, una vez ajustados, su método sería muy simple.
Lo que no tengo claro es si esta búsqueda tiene una cota. Es decir, si su método predice también que, dado un esfuerzo (medido en unidades de computación, o como sea) por alcanzar una colisión, si ésta no se produce, entonces sería posible descartar este método.
Si es así ...
es porque ya tendrán algún método para romper SHA-1 y no se fían.
No entiendo bien
Si se quiere asignar a cualquier archivo una cadena de bits de longitud fija, siempre habrá colisiones. Es simplemente una cuestión de cardinalidad: todas las cadenas de, digamos, 512 bits, no alcanzan para los archivos de 513 bits, por lo que siempre habrá al menos dos con el mismo hash. A muchos les gusta denominar esto el "principio del palomar".
Entonces, ¿qué es lo que se pretende? ¿Que no sea sencillo generar archivos distintos que colisionen? ¿Cuál es en ese caso la definición de "sencillo"?
De paso: es la primera vez que dejo un mensaje aquí. No me dedico a la seguridad, pero es un tema que me resulta interesante y por eso los (os, si preferís) leo.
Matías
Colisiones y sencillez
Estoy seguro que habrá gente que lo sepa explicar mejor que yo. Básicamente un algoritmo de hash debe cumplir al menos estas condiciones:
1- Debe ser univoco: mismo fichero genera siempre mismo hash
2- No debe ser reversible: esto es no puede haber ninguna función hash inversa
3- Debe ser resistente en "sentido fuerte": Dado un fichero debe ser computacionalmente "no abordable" el encontrar otro fichero que tenga el mismo hash
4- Debe ser resistente en "sentido débil": No debe ser computacionalmente abordable encontrar dos ficheros cualesquiera que tengan el mismo hash
Los puntos 3 y 4 aunque parecidos no son lo mismo. Podemos equipararlos a la conocida "paradoja del cumpleaños"
* El punto 3 equivale a preguntar: ¿Cuál es la probabilidad de que en una sala en la que hay "n" personas, al menos una cumpla años un determinado día?
* El punto 4 equivale a: ¿Cuál es la probabilidad de que en una sala en la que hay "n" personas haya al menos dos que cumplan años el mismo día?
El algoritmo sha1 si bien parece resistente a la colisión fuerte, recientes investigaciones parecen sugerir que la colisión débil está a punto de ser rota. Es por ello que desde hace un año, se viene sugiriendo el ir dejando paulatinamente el sha1 cambiándolo por otros más fuertes
Y como siempre, "Computacionalmente abordable" o "Sencillo" significa que el problema se puede resolver en un tiempo tal en que el valor de la información obtenida justifica el esfuerzo invertido. Concepto relativo a más no poder :-)
Opinar