2010-04-26 16 views
25

Estoy interesado en optimizar el hash de algunos archivos grandes (optimizar el tiempo del reloj de pared). La E/S ya se ha optimizado lo suficiente y el dispositivo de E/S (SSD local) solo recibe un 25% de la capacidad, mientras que uno de los núcleos de la CPU está completamente agotado.¿Qué algoritmos hash son paralelizables? Optimización del hashing de archivos de gran tamaño que se utilizan en CPU multinúcleo

Tengo más núcleos disponibles, y en el futuro es probable que tenga aún más núcleos. Hasta ahora solo he podido acceder a más núcleos si necesito varios hashes del mismo archivo, digamos un MD5 Y un SHA256 al mismo tiempo. Puedo usar el mismo flujo de E/S para alimentar dos o más algoritmos de hash, y obtengo los algoritmos más rápidos de forma gratuita (en cuanto al tiempo del reloj de pared). Según entiendo la mayoría de los algoritmos hash, cada bit nuevo cambia el resultado completo, y es inherentemente difícil/imposible de hacer en paralelo.

¿Algún algoritmo hash convencional es paralelizable?
¿Hay hash no convencionales que sean paralelizables (y que tengan al menos una implementación de muestra disponible)?

Como las futuras CPU tenderán hacia más núcleos y una nivelación en la velocidad del reloj, ¿hay alguna manera de mejorar el rendimiento del hash de archivos? (además del overclocking refrigerado por nitrógeno líquido?) o es intrínsecamente no paralelizable?

+0

Además, oigo que la mayoría de los algoritmos hash actuales _es ser paralelizados, pero no estoy seguro de lo que tiene. Obviamente, una forma de hacerlo sería decidir por ti mismo hash cada, por ejemplo, 4k fragmento de archivo, y luego combinar los hash de alguna manera. XOR, tal vez? Siempre es peligroso criptográficamente inventar tu propio algoritmo, por lo que no confiaría en esto si defiendes la manipulación de datos maliciosos en lugar de la corrupción accidental de datos. – sblom

+0

Leí la especificación Skein que ha vinculado. Lo que sugieres aquí es exactamente cómo se logra la paralelización (aparentemente se llama "hashing de árbol"). Skein tiene una forma estándar de especificar el tamaño de hoja, despliegue y altura máxima del árbol para que cualquiera que use los mismos parámetros obtenga el mismo hash resultado. (eso es importante) Me gustaría defenderme contra la manipulación maliciosa y la corrupción accidental. Ojalá los estándares estuvieran listos. – DanO

+0

http://tools.ietf.org/html/rfc1321 Parece MD5 no es fácilmente paralelizable, los cálculos para cada bloque dependen del estado calculada con todos los bloques anteriores. Si esta propiedad no fuera válida, entonces MD5 no sería segura (el cambio de la posición de los bloques no afectaría al hash, no es bueno). De todos modos, no digo que la paralelización de MD5 no sea posible, simplemente imposible a primera vista. – kgadek

Respuesta

12

Actualmente hay mucha investigación en curso en esta área. El Instituto Nacional de Estándares y Tecnología de EE. UU. Está llevando a cabo una competencia para diseñar la función hash de última generación de nivel gubernamental. La mayoría de las propuestas para eso son paralelizables.

Un ejemplo: http://www.schneier.com/skein1.2.pdf

descripción del estado actual del concurso de Wikipedia: http://en.wikipedia.org/wiki/SHA-3

+0

Gracias por los enlaces, la madeja se ve interesante, existen implementaciones en al menos media docena de idiomas. Es paralelizable solo de la misma manera que otras funciones hash lineales ... mediante el uso de un algoritmo de desglose de árbol estandarizado. básicamente hash secciones de la fuente, hash los hashes juntos (en secciones de nuevo si es necesario), etc. pero los parámetros de árbol se vuelven parte de los parámetros hash, y la verificación requiere el uso de los mismos parámetros exactos. Supongo que esto me funcionaría ...pero sería bueno si hubiera un "estándar" – DanO

7

¿Qué tipo de SSD tiene? La implementación de mi C de MD5 se ejecuta a 400 MB/s en un solo núcleo Intel Core2 (2,4 GHz, no el último Intel). ¿Realmente tienes SSD que admite un ancho de banda de 1.6 GB/s? Quiero lo mismo !

El hash de árbol se puede aplicar a cualquier función hash. Hay algunas sutilezas y la especificación Skein trata de lidiar con ellas, integrando algunos metadatos en la función en sí (esto no cambia mucho las cosas para el rendimiento), pero el "modo árbol" de Skein no es "el" Skein como se envía a SHA-3. Incluso si Skein se selecciona como SHA-3, la salida de un hash en modo árbol no sería lo mismo que la salida de "plain Skein".

Afortunadamente, se definirá un estándar en algún momento para describir el hash de árbol genérico. En este momento no hay ninguno. Sin embargo, algunos protocolos se han definido con soporte para un hashing de árbol personalizado con la función hash Tiger, bajo el nombre "TTH" (Tiger Tree Hash) o "THEX" (Tree Hash Exchange Format). La especificación para TTH parece ser un poco difícil de alcanzar; Encuentro algunas referencias a borradores que se han movido o desaparecido para siempre.

Aún así, tengo un poco de dudas sobre el concepto. Es bastante ordenado, pero proporciona un aumento en el rendimiento solo si puede leer datos más rápido que lo que un solo núcleo puede procesar, y, dada la función correcta y la implementación correcta, un núcleo único puede almacenar una gran cantidad de datos por segundo. Un hash de árbol distribuido en varios núcleos requiere que los datos se envíen a los núcleos adecuados, y 1.6 GB/s no es el ancho de banda más pequeño que haya existido.

SHA-256 y SHA-512 no son muy rápidos. Entre los candidatos SHA-3, suponiendo un procesador x86 en modo de 64 bits, algunos de ellos alcanzan alta velocidad (más de 300 MB/s en mi Intel Core 2 Q6600 a 2,4 GHz, con un único núcleo, eso es lo que puedo sacar de SHA-1, también), por ejemplo BMW, SHABAL o Skein.hablar criptográficamente, estos diseños son un poco demasiado nuevo, pero MD5 y SHA-1 ya están criptográficamente "roto" (con bastante eficacia en el caso de MD5, en lugar teóricamente para SHA-1) por lo que cualquier de los de ida y 2 SHA-3 candidatos debería estar bien.

Cuando pongo mi tapa de "vidente", preveo que los procesadores seguirán siendo más rápidos que la RAM, hasta el punto de que el costo de hash quedará eclipsado por el ancho de banda de la memoria: la CPU tendrá ciclos de reloj de repuesto mientras espera para los datos de la RAM principal. En algún punto, todo el modelo de subprocesamiento (una gran RAM para muchos núcleos) tendrá que ser modificado.

+4

Esto está parcialmente fuera del tema; de hecho, odio cuando OP solicita sugerencias de optimización y * siempre * hay alguien que 1) sugiero no molestar, pero comprar mejor hardware 2) probar probar que la optimización no tiene valor en ese caso OP probado/intentado demostrar que lo necesita, por lo que considero que tu opinión no es útil ["¿Realmente tienes SSD que admite un ancho de banda de 1,6 GB/s? ¡Quiero lo mismo!"]. Así que no puedo dar +1. – kgadek

4

Usted no dijo lo que necesita su hash para. Si no va a intercambiarlo con el mundo exterior, solo para uso interno, simplemente divida cada archivo en trozos, calcule y almacene todas las sumas de comprobación. Luego puede usar muchos núcleos simplemente lanzando un trozo a cada uno.

Dos soluciones que viene a la mente es dividiendo los archivos en trozos de tamaño fijo (más simple, pero usarán menos núcleos de archivos más pequeños donde se supone que no necesita toda esa potencia) o en un número fijo de trozos (usará todos los núcleos para cada archivo). Realmente depende de lo que quiere lograr y de la distribución del tamaño de su archivo.

Si, por otro lado, necesita hash para el mundo exterior, como puede leer de las otras respuestas, no es posible con hash "estándar" (por ejemplo, si desea enviar hashes SHA1 para que otros lo comprueben) con diferentes herramientas) por lo que debe buscar en otro lugar. Como calcular el hash al almacenar el archivo, para su posterior recuperación, o calcular hashes en segundo plano con los núcleos 'libres' y almacenarlos para su posterior recuperación.

La mejor solución depende de cuáles sean sus limitaciones y dónde puede invertir el espacio, el tiempo o la potencia de la CPU.

Cuestiones relacionadas