En informática , una colisión o choque es una situación que se produce cuando dos datos distintos tienen el mismo valor hash , suma de comprobación , huella digital o resumen criptográfico . [1]
Debido a las posibles aplicaciones de las funciones hash en la gestión de datos y la seguridad informática (en particular, las funciones hash criptográficas ), la prevención de colisiones se ha convertido en un tema fundamental en la informática.
Las colisiones son inevitables cuando los miembros de un conjunto muy grande (como todos los posibles nombres de personas o todos los posibles archivos de computadora ) se asignan a una cadena de bits relativamente corta. Este es simplemente un ejemplo del principio de casillero . [1]
El impacto de las colisiones depende de la aplicación. Cuando se utilizan funciones hash y huellas dactilares para identificar datos similares, como secuencias de ADN homólogas o archivos de audio similares , las funciones se diseñan para maximizar la probabilidad de colisión entre datos distintos pero similares, utilizando técnicas como el hash sensible a la localidad . [2] Las sumas de comprobación , por otro lado, están diseñadas para minimizar la probabilidad de colisiones entre entradas similares, sin tener en cuenta las colisiones entre entradas muy diferentes. [3]
La seguridad informática
Las funciones hash pueden asignar diferentes datos al mismo hash (en virtud del principio de casillero ), los usuarios malintencionados pueden aprovechar esto para imitar datos. [4]
Por ejemplo; considere una función hash que codifica datos devolviendo los primeros tres caracteres de la cadena que se le da (es decir, "Password12345" va a "Pas"). Un hacker, que no conoce la contraseña del usuario, podría ingresar "Pass", lo que generaría el mismo valor hash de "Pas". Aunque el pirata informático no conoce la contraseña correcta, tiene una contraseña que les da el mismo hash, lo que les daría acceso. Este tipo de ataque se denomina ataque de preimagen .
En la práctica, las aplicaciones relacionadas con la seguridad utilizan algoritmos hash criptográficos, que están diseñados para ser lo suficientemente largos para que las coincidencias aleatorias sean poco probables, lo suficientemente rápidos como para que se puedan usar en cualquier lugar y lo suficientemente seguros como para que sea extremadamente difícil encontrar colisiones. [3]
Ver también
- Ataque de cumpleaños
- Ataque de colisión (contra funciones hash criptográficas)
- Resistencia a colisiones
- Resolución de colisiones (tablas hash)
- Función hash criptográfica
- Colisión de nombres , uso accidental de nombres de variables idénticos
- Hash de contraseña (función de derivación de clave)
- Función hash perfecta , una función hash que está libre de colisiones por diseño
- Ataque de preimagen
- Función hash demostrablemente segura
- Oráculo aleatorio
Referencias
- ↑ a b Jered Floyd (18 de julio de 2008). "¿Qué significan realmente las colisiones de hash?" . permabit.wordpress.com: Permabits y Petabytes . Consultado el 24 de marzo de 2011 .
Para la explicación extensa sobre hashes criptográficos y colisiones hash, escribí una columna un poco atrás para SNW Online, "Lo que necesita saber sobre hashes criptográficos y almacenamiento empresarial". La versión corta es que los sistemas de deduplicación que utilizan hashes criptográficos utilizan esos hashes para generar "huellas digitales" más cortas para identificar de forma única cada pieza de datos y determinar si esos datos ya existen en el sistema. El problema es que, según una regla matemática llamada "principio de casillero", no se puede asignar de forma única ningún archivo o fragmento de archivo posible a una huella digital más corta. Estadísticamente, hay varios archivos posibles que tienen el mismo hash.
- ^ Rajaraman, A .; Ullman, J. (2010). "Minería de conjuntos de datos masivos, cap. 3" .
- ^ a b Al-Kuwari, Saif; Davenport, James H .; Bradford, Russell J. (2011). "Funciones hash criptográficas: tendencias de diseño recientes y nociones de seguridad" . Cite journal requiere
|journal=
( ayuda ) - ^ Schneier, Bruce . "Criptoanálisis de MD5 y SHA: hora de un nuevo estándar" . Computerworld . Archivado desde el original el 16 de marzo de 2016 . Consultado el 20 de abril de 2016 .
Mucho más que algoritmos de cifrado, las funciones hash unidireccionales son los caballos de batalla de la criptografía moderna.