Funció de compressió unidireccional

En criptografia, una funció de compressió unidireccional és una funció que transforma dues entrades de longitud fixa en una sortida de longitud fixa. La transformació és "unidireccional", el que significa que és difícil, donada una sortida determinada, calcular entrades que es comprimeixen a aquesta sortida. Les funcions de compressió unidireccionals no estan relacionades amb els algorismes de compressió de dades convencionals, que en canvi es poden invertir exactament (compressió sense pèrdues) o aproximadament (compressió amb pèrdues) a les dades originals.

Una funció de compressió unidireccional.

Les funcions de compressió unidireccionals s'utilitzen, per exemple, en la construcció Merkle–Damgård dins de les funcions hash criptogràfiques.

Les funcions de compressió unidireccionals sovint es construeixen a partir de xifratge de blocs. Alguns mètodes per convertir qualsevol xifratge de bloc normal en una funció de compressió unidireccional són Davies–Meyer, Matyas–Meyer–Oseas, Miyaguchi–Preneel (funcions de compressió d'un sol bloc) i MDC-2/Meyer–Schilling, MDC-4., Hirose (funcions de compressió de doble longitud de bloc). Aquests mètodes es descriuen amb detall més avall. (MDC-2 també és el nom d'una funció hash patentada per IBM).

Una funció de compressió barreja dues entrades de longitud fixa i produeix una única sortida de longitud fixa de la mateixa mida que una de les entrades. Això també es pot veure com que la funció de compressió transforma una entrada gran de longitud fixa en una sortida més curta i de longitud fixa.

Una funció unidireccional és una funció que és fàcil de calcular però difícil d'invertir. Una funció de compressió unidireccional (també anomenada funció hash) hauria de tenir les propietats següents:

• Fàcil de calcular: si teniu algunes entrades, és fàcil calcular la sortida.
• Resistència a la preimatge: si un atacant només coneix la sortida, hauria de ser inviable calcular una entrada. En altres paraules, donada una sortida $h$, hauria de ser inviable calcular una entrada $m$ de tal manera que $\operatorname {hash} (m)=h$ .
• Resistència de la segona preimatge: donada una entrada $m_{1}$ la sortida del qual és $h$, hauria de ser inviable trobar una altra entrada $m_{2}$ que té la mateixa sortida $h$, és a dir $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$ .
• Resistència a la col·lisió: hauria de ser difícil trobar dues entrades diferents que es comprimeixin a la mateixa sortida, és a dir, un atacant no hauria de poder trobar un parell de missatges. $m_{1}\neq m_{2}$ de tal manera que $\operatorname {hash} (m_{1})=\operatorname {hash} (m_{2})$. A causa de la paradoxa de l'aniversari (vegeu també atac d'aniversari) hi ha un 50% de possibilitats que es pugui trobar una col·lisió en un temps d'aproximadament $2^{n/2}$ on $n$ és el nombre de bits a la sortida de la funció hash. Per tant, un atac a la funció hash no hauria de ser capaç de trobar una col·lisió amb menys d'aproximadament $2^{n/2}$ treball.