Problema de pollo/huevo: hash de archivo (incluido hash) dentro de un archivo! ¿Posible?

Question

La cosa es que tengo un archivo que tiene espacio para los metadatos. Quiero almacenar un hash para verificar la integridad en él. El problema es que, una vez que guardo el hash, el archivo y el hash cambian.

Entiendo perfectamente que esto es por definición imposible con métodos hash criptográficos de una vía como md5/sha.

También soy consciente de la posibilidad de que los contenedores almacenen datos de verificación separados del contenido como zip & co do.

También conozco la posibilidad de calcular el hash por separado y enviarlo junto con el archivo o adjuntarlo al final o en algún lugar donde el cliente, al calcular el hash, lo ignora.

Esto no es lo que quiero.

Quiero saber si hay un algoritmo donde es posible obtener el hash resultante de los datos donde se incluye el resultado del mismo hash.

No necesita ser criptográfico ni cumplir muchos criterios. También se puede basar en algunas heurísticas que después de un tiempo realista brindan el resultado deseado.

Realmente no estoy tan metido en las matemáticas, pero ¿no podría haber algo de avanzado exponencial modulo polinom cíclico atrás-referencia devision cosas que hace esto posible?

Y si no, ¿cuál es (si existe) la prueba en contra?

La razón por la que necesito tis es porque quiero (en última instancia) almacenar un hash junto con archivos MP4. Es complicado, pero otras soluciones no son fáciles de implementar ya que el archivo pasa por una tubería de producción mal diseñada ...

Answer 1

Es posible hacer esto con un CRC, en cierto modo. Lo que he hecho en el pasado es separar 4 bytes en un archivo como marcador de posición para un CRC32, llenándolos de ceros. Luego calculo el CRC del archivo.

Es posible completar los bytes del marcador de posición para hacer que el CRC del archivo sea igual a una constante fija arbitraria, calculando números en el campo Galois del polinomio CRC. .

(Más detalles posibles, pero no justo en este momento que básicamente necesita para calcular (CRC_desired - CRC_initial) * 2 * ^{-8 byte_offset} en el campo de Galois, donde byte_offset es el número de bytes entre los bytes de marcador de posición y al final del archivo)

---

Nota:. @ según los comentarios de Keith esta solución no es impedir contra la manipulación intencional. Lo usamos en un proyecto como un medio para vincular los metadatos dentro de un sistema incrustado con el ejecutable utilizado para programarlo: el sistema integrado no tiene conocimiento directo de los archivos utilizados para programarlo y, por lo tanto, no puede calcular un CRC o hash en sí mismo: para detectar desajustes inadvertidos entre un sistema integrado y el archivo utilizado para programarlo. (En sistemas posteriores, acabo de utilizar UUID.)

Answer 2

No, no es posible. O bien es un archivo separado para hashs ala md5sum, o el hash incrustado es solo para la parte de "datos" del archivo.

Answer 3

Depende de su definición de "hash". Como dices, obviamente con cualquier hash pseudoaleatorio esto sería imposible (en un tiempo razonable).

Igualmente obvio, hay por supuesto "hash" triviales donde puedes hacer esto. Datos con un número impar de bits configurados en 1 hash a 00 y un número par de 1s hash a 11, por ejemplo. El hash no modifica la impar/uniformidad de los 1 bits, por lo que los archivos hash son los mismos cuando se incluye su hash.

Answer 4

la forma the nix package manager hace esto es cuando se calcula el hash que pretende el contenido del hash en el archivo son algunos valor fijo como 20 x 's y no el hash del archivo, entonces escribir el hash sobre los 20 x 's y cuando compruebe el hash usted lee eso e ignore de nuevo que simulando que el hash fue solo el valor fijo de 20 x cuando hash

Lo hacen porque las rutas en las que se instala un paquete dependen del hash de todo el paquete, así como el hash es de longitud fija, lo configuran como un valor fijo y luego lo reemplazan con el hash real y cuando verifican ignoran el valor que colocaron y fingen que es ese valor fijo

pero si no se utiliza un procedimiento de este tipo es imposible

Answer 5

Recuerdo un viejo programa de DOS que fue capaz de incrustar en un archivo de texto el valor CRC de ese archivo. Sin embargo, esto es posible solo con funciones hash simples.
Aunque en teoría podría crear dicho archivo para cualquier tipo de función hash (dado el tiempo suficiente o el algoritmo correcto), el atacante podría usar exactamente el mismo enfoque. Aún más, tendría una opción: utilizar exactamente su enfoque para obtener dicho archivo, o simplemente para deshacerse del cheque.

Significa que ahora tiene dos problemas en lugar de uno, y ambos deben implementarse con la misma complejidad. Depende de usted decidir si vale la pena.

EDITAR: podría considerar la mezcla de algunos resultados intermedios (como la salida decodificada SIN PROCESAR, o algo específico de su códec). De esta forma, el decodificador lo tendría de todos modos, pero para otro programa sería más difícil de calcular.

Answer 6

Por supuesto, esto es posible, en una multitud de formas. Sin embargo, no puede evitar la manipulación intencional.

Por ejemplo, supongamos

hash(X) = sum of all 32-bit (non-overlapping) blocks of X modulo 65521. 

Deje

Z = X followed by the 32-bit unsigned integer (hash(X) * 65521) 

Entonces

hash(Z) == hash(X) == last 32-bits of Z 

La idea aquí es que cualquier número entero de 32 bits congruente con 0 módulo 65521 tendrán no hay efecto en el hash de X. Entonces, desde 65521 < 2^16, hash tiene ar ange menos que 2^16, y hay al menos 2^16 valores menores que 2^32 congruentes con 0 módulo 65521. Y entonces podemos codificar el hash en un entero de 32 bits que no afectará el hash. En realidad podría usar cualquier número menor que 2^16, 65521 simplemente es el número primo más grande.