{"id":161,"date":"2007-04-29T22:05:19","date_gmt":"2007-04-30T01:05:19","guid":{"rendered":"http:\/\/talsoft.com.ar\/weblog\/?p=161"},"modified":"2007-04-29T22:05:19","modified_gmt":"2007-04-30T01:05:19","slug":"algoritmos-hash-atacando-md5-y-sha-1","status":"publish","type":"post","link":"https:\/\/www.talsoft.com.ar\/site\/es\/algoritmos-hash-atacando-md5-y-sha-1\/","title":{"rendered":"Algoritmos HASH: Atacando MD5 y SHA-1"},"content":{"rendered":"<p><em>Este art\u00c3\u00adculo es una colaboraci\u00c3\u00b3n enviada por <a href=\"http:\/\/lordhash.blogspot.com\/\"><strong><font color=\"#de7008\">LordHASH<\/font><\/strong><\/a><\/em><\/p>\n<p>Algunos de los algoritmos de HASH m\u00c3\u00a1s utilizados, que son sobre los que trabajaremos, son los siguientes:<\/p>\n<ul>\n<li>MD5 (Message-Digest Algorithm 5 o Algoritmo de Firma de Mensajes 5): Desarrollado por Ron Rivest, ha sido hasta los \u00c3\u00baltimos a\u00c3\u00b1os el algoritmo hash m\u00c3\u00a1s usado. Procesa mensajes de una longitud arbitraria en bloques de 512 bits generando un compendio de 128 bits. Debido a la capacidad de procesamiento actual esos 128 bits son insuficientes, adem\u00c3\u00a1s de que una serie de ataques criptoanal\u00c3\u00adticos han puesto de manifiesto algunas vulnerabilidades del algoritmo. Puede ser \u00c3\u00batil para comprobar la integridad de un fichero tras una descarga, por ejemplo, pero ya no es aceptable desde el punto de vista del criptoan\u00c3\u00a1lisis.<\/li>\n<li>SHA-1 (Secure Hash Algorithm 1 o Algorimo de Hash Seguro 1): El SHA-1 toma como entrada un mensaje de longitud m\u00c3\u00a1xima 2<sup>64<\/sup> bits (m\u00c3\u00a1s de dos mil millones de Gigabytes) y produce como salida un resumen de 160 bits. Este n\u00c3\u00bamero es mayor que el que se utilizaba en el algoritmo SHA original, 128 bits. Ya existen nuevas versiones de SHA que trabajan con res\u00c3\u00bamenes de 224,256,384 e incluso 512 bits.<\/li>\n<\/ul>\n<p>En realidad, lo seguros o inseguros que estos algoritmos sean no depende de los conocimientos inform\u00c3\u00a1ticos o telem\u00c3\u00a1ticos que uno tenga, sino de sus conocimientos matem\u00c3\u00a1ticos. Nuestra intenci\u00c3\u00b3n es demostrar por d\u00c3\u00b3nde cojean los algoritmos de HASH, la dificultad computacional que presentan, y qu\u00c3\u00a9 soluciones se dan a los posibles ataques que puedan sufrir por parte de individuos malintencionados.<\/p>\n<p>Desde el a\u00c3\u00b1o 2004 aproximadamente, cuando saltaron las primeras noticias escandalosas sobre la ruptura de MD5, la seguridad que ofrecen los algoritmos de HASH a nuestros esquemas de cifrado ha sido una cuesti\u00c3\u00b3n que se ha puesto en entredicho. \u00c2\u00bfQu\u00c3\u00a9 seguridad ofrecen estos algoritmos? \u00c2\u00bfResulta computacionalmente complejo romper uno de estos algoritmos? \u00c2\u00bfQu\u00c3\u00a9 soluci\u00c3\u00b3n se debe adoptar? Intentaremos resolver estas cuestiones.<\/p>\n<p>Intentemos dar una descripci\u00c3\u00b3n algo m\u00c3\u00a1s matem\u00c3\u00a1tica de lo que es una funci\u00c3\u00b3n HASH. Supongamos que tenemos un mensaje <em>a<\/em>, al que aplicamos una funci\u00c3\u00b3n resumen a la que llamaremos <em>h<\/em>. Decimos entonces que el resultado de esta operaci\u00c3\u00b3n, al que llamaremos <em>b<\/em> es el HASH de <em>a<\/em>. Es decir:<\/p>\n<p align=\"center\"><strong><em>h(a)=b<\/em><\/strong><\/p>\n<p>Esta funci\u00c3\u00b3n debe ser sencilla de realizar para un computador, pero debe ser computacionalmente imposible realizar la operaci\u00c3\u00b3n inversa, al menos para usuarios normales.<\/p>\n<p>Adem\u00c3\u00a1s, esta funci\u00c3\u00b3n tiene otra caracter\u00c3\u00adstica: el tama\u00c3\u00b1o de la entrada no es de longitud fija, puede ser de longitud variable. Esto tiene la siguiente consecuencia, que no demostraremos matem\u00c3\u00a1ticamente, pero que asumiremos por estar razonado en otros art\u00c3\u00adculos publicados en Internet (al final se indican): es posible que dos mensajes de entrada <em>a<\/em> produzcan el mismo mensaje de salida <em>b<\/em>. Es decir, es posible encontrar un mensaje <em>c<\/em>, tal que:<\/p>\n<p align=\"center\"><strong><em>h(c)=b<\/em><\/strong><\/p>\n<p>Sin embargo, encontrar ese mensaje debe ser, al igual que la particularidad antes mencionada, muy complejo desde el punto de vista computacional. Para los algoritmos de HASH esto es lo que se conoce como <strong>colisi\u00c3\u00b3n<\/strong>: que dos mensajes de entrada produzcan el mismo mensaje de salida.<\/p>\n<p>As\u00c3\u00ad, a priori, podemos establecer dos posibles vulnerabilidades de las funciones HASH:<\/p>\n<ul>\n<li>Que sea posible realizar la operaci\u00c3\u00b3n:\n<p align=\"center\"><strong><em>h<sup>-1<\/sup>(b)=a<\/em><\/strong><\/p>\n<p>Habitualmente, a la operaci\u00c3\u00b3n de invertir la funci\u00c3\u00b3n HASH comprobando todas las posibilidades para los bits de salida se le llama <strong>ataque de fuerza bruta<\/strong>. Esto es lo que debe ser computacionalmente impracticable. Supondr\u00c3\u00ada aplicar la funci\u00c3\u00b3n HASH 2<sup>n<\/sup> veces hasta encontrar la coincidencia (n es el n\u00c3\u00bamero de bits de salida de la funci\u00c3\u00b3n).<\/li>\n<li>Que se hallen colisiones:\n<p align=\"center\"><strong><em>h(a)=b y h(c)=b, a distinto de c<\/em><\/strong><\/p>\n<p>Lo que antes hemos denominado <strong>colisi\u00c3\u00b3n<\/strong>.<\/li>\n<\/ul>\n<p>Estas dos posibles debilidades dan lugar a cuatro tipos de ataques:<\/p>\n<ul>\n<li><strong>Ataque Tipo 1<\/strong>: El atacante es capaz de encontrar dos mensajes al azar que colisionan pero es incapaz de hacerlo de forma sistem\u00c3\u00a1tica. Si es capaz de dar s\u00c3\u00b3lo con dos mensajes que provocan colisi\u00c3\u00b3n, esta no es raz\u00c3\u00b3n suficiente para tildar el algoritmo de ineficiente. \u00c3\u008dndice de peligrosidad: *<\/li>\n<li><strong>Ataque Tipo 2<\/strong>: El atacante es capaz de generar dos mensajes distintos de forma que sus HASH colisionen, pero sin saber a priori qu\u00c3\u00a9 hash resultar\u00c3\u00a1. Es decir, el atacante no podr\u00c3\u00ada generar \u00e2\u20ac\u0153queriendo\u00e2\u20ac\u009d el HASH que necesite para fines maliciosos. \u00c3\u008dndice de peligrosidad: **<\/li>\n<li><strong>Ataque Tipo 3<\/strong>: El atacante es capaz de construir un mensaje sin sentido de forma que su HASH colisione con el de un mensaje con sentido. Si \u00c3\u00a9ste es el caso, el agente malicioso puede atacar algoritmos de encriptaci\u00c3\u00b3n asim\u00c3\u00a9tricos con firma digital, haciendo que se firmen mensajes sin sentido, y que el destinatario los acepte como fidedignos. \u00c3\u008dndice de peligrosidad: ***<\/li>\n<li><strong>Ataque Tipo 4<\/strong>: El atacante es capaz de crear un segundo mensaje falso que tiene sentido y cuyo hash colisiona con el del mensaje verdadero. En este caso, el atacante puede actuar con total impunidad, puede falsificar certificados, firmar mensajes\u00e2\u20ac\u00a6El resultado ser\u00c3\u00ada desastroso. \u00c3\u008dndice de peligrosidad: ****.<\/li>\n<\/ul>\n<p>El problema entonces es el siguiente: \u00c2\u00bfc\u00c3\u00b3mo de dif\u00c3\u00adcil es encontrar una soluci\u00c3\u00b3n? \u00c2\u00bfQu\u00c3\u00a9 ataques reales son practicables? \u00c2\u00bfQu\u00c3\u00a9 se gana incrementando el n\u00c3\u00bamero de bits de salida del algoritmo?<\/p>\n<p>En primer lugar, responderemos a la \u00c3\u00baltima pregunta. Si aumentamos el n\u00c3\u00bamero de bits de salida del algoritmo, el ataque de fuerza bruta ser\u00c3\u00a1 m\u00c3\u00a1s impracticable y tambi\u00c3\u00a9n lo ser\u00c3\u00a1 encontrar los mensajes que colisionen, pues te\u00c3\u00b3ricamente se cumple que para confiar en que podemos encontrar dos mensajes que colisionen no hay que realizar 2<sup>n<\/sup> operaciones, si no s\u00c3\u00b3lo 2<sup>n\/2<\/sup>.<\/p>\n<p>Realicemos algunos c\u00c3\u00a1lculos para realizar ataques de fuerza bruta:<\/p>\n<ul>\n<li>Para una clave de 12 d\u00c3\u00adgitos, escrita con un teclado con 97 caracteres (base 97), habr\u00c3\u00ada que realizar (esto no tiene nada que ver con los algoritmos de HASH):\n<p align=\"center\"><strong>97<sup>12<\/sup> = 693.842.360.995.438.000.295.041 comprobaciones.<\/strong><\/p>\n<\/li>\n<li>Para MD5, la salida es de 128 bits, ser\u00c3\u00ada necesario realizar:\n<p align=\"center\"><strong>2<sup>128<\/sup>=3\u00e2\u20ac\u00b2402823669 * 10<sup>38<\/sup> operaciones.<\/strong><\/p>\n<\/li>\n<\/ul>\n<p>Trabajemos ahora con los ataques basados en b\u00c3\u00basqueda de colisiones:<\/p>\n<ul>\n<li>Para MD5, la salida es de 128 bits, luego hay que operar sobre la mitad de bits, y ser\u00c3\u00ada necesario realizar:\n<p align=\"center\"><strong>2<sup>64<\/sup>=18.446.744.073.709.551.616 operaciones.<\/strong><\/p>\n<\/li>\n<li>Para el algoritmo SHA 1, cuya salida es de 160 bits:\n<p align=\"center\"><strong>2<sup>80<\/sup>=1.208.925.819.614.629.174.706.176 operaciones.<\/strong><\/p>\n<p><em>Curiosidad: 1.000.000 de ordenadores capaces de procesar en 1 \u00c2\u00b5s cada operaci\u00c3\u00b3n tardar\u00c3\u00adan m\u00c3\u00a1s de 38.000 a\u00c3\u00b1os en las 2<sup>80<\/sup> operaciones<\/em>.<\/li>\n<\/ul>\n<p>Y para los m\u00c3\u00a1s desconfiados e incluso paranoicos: \u00c2\u00bfqu\u00c3\u00a9 hay de las supercomputadoras y de la gente que s\u00c3\u00ad dispone de los medios necesarios? Cuando saltaron las primeras alarmas sobre estos algoritmos, hace unos dos a\u00c3\u00b1os, las cifras eran las siguientes:<\/p>\n<ul>\n<li>Para romper el SHA-0 completo se ha requerido un supercomputador de BULL de 256 procesadores durante unos 9 a\u00c3\u00b1os de proceso, pero al supercomputador que est\u00c3\u00a1 instalando IBM en la UPC (Barcelona) s\u00c3\u00b3lo le costar\u00c3\u00ada del orden de 1 a\u00c3\u00b1o.<\/li>\n<li>Otro grupo de investigadores, Wang, Feng, Lai, y Yu han reportado haberlo conseguido con una complejidad aproximadamente 2000 veces menor (240 en vez de 251). Esta reducci\u00c3\u00b3n equivaldr\u00c3\u00ada a una necesidad de c\u00c3\u00a1lculo de algo menos de 1 d\u00c3\u00ada, si la relaci\u00c3\u00b3n fuese lineal, pero los mismos investigadores han reportado necesitar s\u00c3\u00b3lo 1 d\u00c3\u00ada con un IBM P690 en cluster, para romper el MD5, que tiene una complejidad equivalente.<\/li>\n<\/ul>\n<p>Por tanto, lo habitual no es que nos ataque desde uno de estos grandes usuarios (tienen cosas m\u00c3\u00a1s interesantes que hacer, dir\u00c3\u00ada yo\u00e2\u20ac\u00a6) si no que nos ataque un cracker o similares (ACLARACI\u00c3\u201cN: No incluyamos a los se\u00c3\u00b1ores programadores en esto, los hackers. Gracias a <a href=\"htttp:\/\/maracay.velug.org.ve\/docs\/free_software.pdf\"><font color=\"#de7008\">Richard Stallman<\/font><\/a>).<\/p>\n<p>Lo habitual es que este tipo de usuarios realicen ataques basados en diccionarios, como la aplicaci\u00c3\u00b3n para \u00c3\u2018u\/Linux <a href=\"http:\/\/www.openwall.com\/john\/\"><font color=\"#de7008\">John the Ripper<\/font><\/a>. Este tipo de aplicaciones tiene una base de datos con claves comunes, que prueban sobre los sistemas a los que queremos acceder (por ejemplo Sistemas basados en UNIX donde se almacenan los res\u00c3\u00bamenes HASH de el nombre de usuario y su clave para autenticar). Ante esto s\u00c3\u00b3lo hay una soluci\u00c3\u00b3n: EVITAR LAS PASSWORDS ABSURDAS. No sirve (marta -tkm ni maria-secreto) ok??<\/p>\n<p>Concluyendo, dependiendo de su nivel de paranoia cr\u00c3\u00adptica y de la aplicaci\u00c3\u00b3n que est\u00c3\u00a9n utilizando\u00e2\u20ac\u00a6escojan su algoritmo de HASH, pero no acepten menos de SHA-1. Cuando un algoritmo empieza a presentar vulnerabilidades no tarda mucho en ser aniquilado, as\u00c3\u00ad que a algunos de estos les queda poco tiempo de vida.<\/p>\n<p>Fuentes:<\/p>\n<ul>\n<li><a href=\"http:\/\/www.infosec.sdu.edu.cn\/paper\/md5-attack.pdf\"><font color=\"#de7008\">http:\/\/www.infosec.sdu.edu.cn\/paper\/md5-attack.pdf<\/font><\/a><\/li>\n<li><a href=\"http:\/\/www.md5database.net\/\"><font color=\"#de7008\">http:\/\/www.md5database.net\/<\/font><\/a><\/li>\n<li><a href=\"http:\/\/www.eumed.net\/cursecon\/ecoinet\/seguridad\/resumenes.htm\"><font color=\"#de7008\">http:\/\/www.eumed.net\/cursecon\/ecoinet\/seguridad\/resumenes.htm<\/font><\/a><\/li>\n<\/ul>\n<p><a href=\"http:\/\/gaussianos.com\/algoritmos-hash-i-introduccion\/\" \/><a href=\"http:\/\/seguinfo.blogspot.com\/2007\/04\/algoritmos-hash-introduccin-i.html\"><font color=\"#e0ad12\">Ir a Algoritmos HASH (I): Introducci\u00c3\u00b3n<\/font><\/a><span style=\"font-weight: bold\"><br \/>\n<\/span><\/p>\n<p>Fuente: http:\/\/gaussianos.com\/algoritmos-hash-ii-atacando-md5-y-sha-1\/<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Este art\u00c3\u00adculo es una colaboraci\u00c3\u00b3n enviada por LordHASH Algunos de los algoritmos de HASH m\u00c3\u00a1s utilizados, que son sobre los que trabajaremos, son los siguientes: MD5 (Message-Digest Algorithm 5 o Algoritmo de Firma de Mensajes 5): Desarrollado por Ron Rivest, ha sido hasta los \u00c3\u00baltimos a\u00c3\u00b1os el algoritmo hash m\u00c3\u00a1s usado. Procesa mensajes de una [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[3,1],"tags":[],"class_list":["post-161","post","type-post","status-publish","format-standard","hentry","category-articulos","category-profesional"],"_links":{"self":[{"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/posts\/161","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/comments?post=161"}],"version-history":[{"count":0,"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/posts\/161\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/media?parent=161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/categories?post=161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.talsoft.com.ar\/site\/wp-json\/wp\/v2\/tags?post=161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}