Una función de compresión unidireccional MP (Multi Permutaciones), surge de los trabajos de J. Black, M. Cochran y T. Shrimpton que demuestran, en 2.005, que el caso más simple de una función de compresión es 2n a n bits y que una permutación de n bits (π), no puede ser resistente a la colisión. Sobre esta vía continuaron profundizando, por caminos separados, P. Rogaway, J. Steinberger y M. Stam.
En 2.008 T. Shrimpton y M. Stam propusieron una función de compresión basada en XOR, utilizando tres funciones unidireccionales en lugar de permutaciones:
F (x1, x2) = f1 (x1) ⊕ f3 (f1 (x1) ⊕ f2 (x2))
Esta función es resistente a la colisión hasta 2n / 2 intentos de ruptura (asintóticamente), pero se pueden encontrar imágenes previas con alta probabilidad después de 2n / 2 consultas. Se ha demostrado mediante un análisis automatizado de Rogaway y Steinberger que los mismos resultados se mantienen si f1, f2, f3 son funciones de compresión similares a Davies-Meyer utilizando permutaciones π1, π2, π3, es decir, fi (x) = x⊕ πi (x), pero nunca se ha dado un análisis de seguridad formal. Es un problema abierto e importantepero al mismo tiempo es un problema elegante y a la vez simple (las funciones solo emplean operadores XOR) y mejoran la eficiencia. (Los operadores XOR son ligeramente más “baratos” que las multiplicaciones de campo finito).
En 2.012 Bart Mennick y Bart Preneel demostraron la posibilidad de crear una función de compresión de 2n a n bits resistente a la colisión y a la preimagen basándose únicamente en tres permutaciones distintas con operación XOR. Para el ajuste de permutación múltiple, donde se supone que las tres permutaciones π1, π2, π3 se seleccionan de manera independiente y uniforme al azar, los resultados son:
- Una función de compresión F está libre de colisiones (asintóticamente) si y solo si es equivalente a una de las cuatro funciones de compresión:
F1 (x1, x2) = x2 ⊕ π2 (x2) ⊕ π3 (x1 x2 ⊕ π1 (x1)),
F2 (x1, x2) = x1 ⊕ π1 (x1) ⊕ π2 (x2) ⊕ π3 (x1 ⊕ x2 ⊕ π1 (x1)),
F3 (x1, x2) = x1 ⊕ π1 (x1) ⊕ π3 (x1 x2 ⊕ π1 (x1) ⊕ π2 (x2)),
F4 (x1, x2) = x1 ⊕ x2 ⊕ π1 (x1) ⊕ π3 (x1 x2 ⊕ π1 (x1) ⊕ π2 (x2)).
- Para las funciones de compresión distintas de F1, F2, F3 y F4, las colisiones se pueden encontrar más rápido que el ataque del cumpleaños, es decir, en un máximo de 22n / 5 intentos de ruptura.
- Las funciones equivalentes a F2 son seguras hasta 22 n / 3 intentos.
- Las funciones F1, F3 ó F4 se comportan de forma óptima para lograr una seguridad de preimagen hasta 2 n / 2 intentos.
- Por lo tanto, una función de compresión logra una resistencia óptima de colisión y preimagen si y solo si es equivalente a F2.
