in

¿Es la suma de hashes un hash adecuado para conjuntos?

Dejar $H: X \rightarrow \{0, 1\}^b$ denota un criptográficamente seguro, $b$-función hash de bits en un conjunto $X$. Dejar $H^*: \mathbb{P}(X) \rightarrow \{0, 1\}^b$ ser una función en el conjunto potencia de $X$ definido por
\begin{ecuación} H^*(\{x_1, \ldots, x_n\}) = \sum_i H(x_i) \end{ecuación}
donde la suma pretende envolver la suma sobre $b$-bit enteros.

me pregunto si $H^*$ es criptográficamente seguro en $\mathbb{P}(X)$.

Veo fácilmente que otros mecanismos de agregación (como XOR-ing todos los hashes juntos) son fácilmente propensos a colisiones. También veo cómo, si el mismo elemento de $X$ podría aparecer varias veces en la colección que se está procesando, se podría generar una colisión mediante una simple división de enteros. Pero, si todos los elementos de $X$ siendo hash son distintos, no puedo ver fácilmente un ataque a esta construcción.

2 respuestas
2

Cualquier combinación lineal es problemática, ya sea que la operación básica sea xor o sumatoria. Triture un montón de elementos y mírelos como una matriz, ¿cuál es su rango? obviamente, para un hash de bits ab no puede ser más que b, definitivamente encontrará una combinación lineal de los hash que producen otro elemento.

$H^\estrella$ es definitivamente inseguro. Si $n$ es grande, digamos que es comparable a $2^b,$ luego puede configurar un sistema lineal y resolverlo mediante eliminación gaussiana, por ejemplo.

Si $n$ es pequeño en comparación con $2^b,$ todavía hay atajos que reducen sustancialmente la complejidad. Aquí hay un ataque que encuentra una colisión en tal función. Hiven alguna salida de hash deseada $H_0,$
supongamos que tenemos un conjunto aleatorio de $v=2^{b/n}$ hachís, de la forma
$$H^\star(\{x_{1,i},\ldots,x_{n,i}\}),\quad i=1,\ldots,v\quad(1).$$
Ya que aquí están $v^n=2^b$ posible $n-$sumas de la forma (1) estas sumas que hemos reunido llegarán a su $H_0$ con probabilidad constante ya que el espacio de destino hash tiene tamaño $2^{b}.$

Si $n=2$ esto sería esencialmente el problema de cumpleaños con complejidad $O(2^{b/2}).$ Por reducción al caso cuando $n=2^v$ es una potencia de 2, Wagner dio una $$O(2^{b/(1+\lceil \log n\rceil)})$$ solución recursiva.

Este problema básico se denomina $n-$problema XORSUM y es relevante para el aprendizaje de la paridad con el ruido y el mecanismo de la cadena de bloques Equihash.

¿Te ayudó la respuesta?

Subscribirse
Notificar por
guest

0 Comentarios
Inline Feedbacks
Ver todas las Respuestas

¿Los pensamientos preceden al disparo de neuronas o al tornillo de banco?

El ventilador del horno del calentador doméstico no enciende