Hashing Flashcards
Defina funcion de hashing.
En su más básica definición una función de hashing debe ser capaz de recibir como input un cierto dato cualquiera y devolver un número acotado a un cierto intervalo. Al conjunto de claves posibles (input) lo denominaremos ”espacio de claves” y al conjunto de números que la función de hashing puede devolver lo llamaremos ”espacio de direcciones”.
Explique mecanismos de resolucion de colisiones.
i) Búsqueda lineal (direccionamiento abierto o hashing cerrado)
La búsqueda lineal es una solución muy sencilla al problema de las colisiones. Cuando queremos almacenar un dato pero su posición está ocupada buscamos linealmente y de forma cı́clica hasta encontrar un lugar libre o bien hasta volver al lugar original en cuyo caso la tabla está llena. Cuando queremos recuperar un dato tenemos que tener en cuenta que si en la posición indicada por la función de hashing encontramos otro dato entonces el dato que buscamos podrı́a estar en otra posición por lo que tenemos que buscar linealmente hasta encontrar el dato o bien un lugar vacı́o. Notemos que si se permiten bajas no podemos detenernos al encontrar una posición dada de baja.
La búsqueda lineal es sencilla pero a medida que aumenta la cantidad de datos en la tabla degrada muy rápidamente y se parece mucho a una simple búsqueda lineal que es O(n) en lugar de O(1).
ii) Encadenamiento de Sinónimos (direccionamiento cerrado o hashing abierto)
En este método vamos a generar una lista enlazada en cada posición de nuestra tabla de hash para almacenar allı́ las claves que colisionen. Nuestra estructura es entonces un vector de listas. Cuando queremos almacenar un dato simplemente lo agregamos a la lista que está en la posición indicada por la función de hashing. Cuando queremos buscar un dato accedemos a la lista indicada por la función de hashing y buscamos en la lista.
Este método es muy sencillo y es un poco mas eficiente que la búsqueda lineal pero cuando existen muchas colisiones las listas pueden volverse bastante largas por lo que las búsquedas pueden tender a O(n) en lugar de O(1). No obstante es un método muy usado y que debemos tener en cuenta ya que tiene varias aplicaciones interesantes.
Que se quiere garantizar con Hopscotch hashing?
Queremos garantizar O(1) para las búsquedas y queremos que la zona en la cual tenemos que buscar el dato sea igual o muy cercana a la indicada por la función de hashing para favorecer el uso de datos en memoria cache.
Explique hopscotch hashing.
En Hopscotch partimos de un vector de ”m” elementos que es nuestra tabla de hash, vamos a usar además un número ”k” que indica que tan lejos podemos guardar un dato respecto de la posición indicada por la función de hashing. Si k=3 podemos guardar el dato en h(x), h(x)+1 o h(x)+2. Es decir que cada dato tiene k posiciones en las cuales puede almacenarse. Es importante mencionar que esto no quiere decir que si esas k posiciones están ocupadas el dato no pueda almacenarse.
La forma de resolver colisiones en Hopscotch es muy interesante y muy simple. En primer lugar consideremos las posiciones h(x), h(x)+1 hasta h(x)+k-1, si alguna de esas posiciones está libre entonces podemos guardar el dato allı́ sin ningún problema. Si todas las posiciones están ocupadas entonces buscamos linealmente hasta encontrar una posición libre y a partir de esta recorremos hacia atrás viendo si podemos ir moviendo datos hacia adelante de forma de liberar una posición válida para nuestro dato.
Que sucede en el caso que no se pueda liberar un espacio en las k posiciones en Hopscotch hashing?
En el caso que no se pueda liberar un espacio en las k posiciones donde puede almacenarse el dato, se debe cambiar el tamaño de la tabla y reubicar a los datos de la misma.
Enuncie las propiedades que debe cumplir una funcion de hashing.
- La función tiene que ser muy eficiente, es decir, generar el resultado en muy poco tiempo.
El motivo por el cual usamos una función de hashing es para poder recuperar un dato de forma muy eficiente en tiempo similar a O(1). Si la función de hashing fuera muy compleja e ineficiente podrı́a pasar que buscar linealmente en el vector tarde menos tiempo que usar la función de hashing y acceder a la posición indicada, lo cual invalidarı́a el uso de una función de hashing por completo. - La función tiene que producir la menor cantidad de colisiones posibles.
El segundo punto pide minimizar las colisiones, lo cual no solo implica evitar, en lo posible, que nuestras claves colisionen sino que debemos intentar que la distribución de las claves en el espacio de direcciones sea lo más pareja posible.
FNV hashing.
Data: s: string Result: h: integer 1 h = 14695981039346656037; 2 for c in s do 3 h = h * 1099511628211; 4 h = h XOR c; 5 return h;
Jenkins
Data: s: string Result: hash: integer 1 for hash=i=0;i> 6); 5 hash += (hash << 3); 6 hash xor= (hash >> 11); 7 hash += (hash << 15); 8 return hash;
Pearson.
Data: s: string Result: hash: integer 1 h = 0; 2 for c in s do 3 index = h xor c; 4 h = T[index]; 5 return h
A que cosa es Pearson una primera aproximacion y por que?
La función de Pearson nos permite también una primera aproximación rudimentaria a una función de hashing perfecta. Si tenemos pocas claves a hashear podemos simplemente probar diferentes tablas al azar hasta que alguna de las tablas nos genere una función de Pearson que sea perfecta. Este es un algoritmo aleatorizado de tipo Las Vegas ya que siempre produce un resultado exacto pero con una cierta probabilidad, aunque puede tardar mucho tiempo en generar el resultado.
Caracteristicas de funciones de hashing criptograficas.
- La función tiene que producir la menor cantidad de colisiones posibles
- Dado h(x) tiene que ser muy difı́cil hallar x
- Tiene que ser muy difı́cil hallar x e y de forma tal que h(x)=h(y)
- Un cambio mı́nimo en la clave tiene que producir un cambio significativo en el resultado (efecto avalancha)
Cual es la funcion de hash cript. mas usada hoy dia y en que se basa?
SHA-256 se basa en la combinación de dos primitivas criptográficas muy importantes: La construcción de Merkle-Damgard y la construcción de Davis-Meyer.
Explique construccion de Merkle-Damgard.
En esta construcción suponemos que existe una función ”f” que recibe un bloque de m bits y devuelve un bloque de n bits con n < m. A esta función se la llama función de compresión aunque no tiene nada que ver con compresión de datos. Simplemente devuelve menos bits que los que recibe.
El objetivo de la construcción de Merkle-Damgard es dado un string de una cantidad arbitraria de bits emitir un único resultado de tamaño igual al tamaño que emite la función f.
Supongamos que ”n” es la cantidad de bits que emite nuestra función de compresión f, dividimos nuestro mensaje entonces en bloques de ”n” bits agregando un padding al final en caso de ser necesario. El padding es crı́tico para el correcto funcionamiento de la función y no debe ser fijo.
Como la función de compresión recibe bloques de m bits agregamos un bloque ficticio llamado IV con el cual podemos comenzar el algoritmo. Notar que la construcción es muy simple y se basa en concatenar el resultado anterior de f al bloque próximo y luego volver a aplicar f.
Mediante la construcción de Merkle-Damgard podemos aplicar una función de compresión cualquiera a un mensaje de longitud arbitraria de forma segura, veamos ahora como construir una función de compresión segura.
Explique construccion de Davis-Meyer.
La construcción de Davis-Meyer permite generar una función de compresión segura a partir de un algoritmo de encripción seguro. El procedimiento es muy simple, recibimos dos bloques y usaremos uno como clave para encriptar el otro, finalizando con el xor entre el bloque 1 y el resultado de la encripción.
SHA-256 es entonces una construcción de Merkle-Damgard en donde la función de compresión es una construcción de Davis-Meyer usando SHACAL-2 como algoritmo de encripción. Cada bloque del mensaje tiene 512 bits y la función de compresión devuelve 256 bits.
Son intercambiables las funciones de hashing tradicionales y criptograficas? Por que?
Es importante destacar que es un error muy grave usar una función de hashing tradicional cuando se necesita una función de hashing criptográfica pero también es un error grave usar una función criptográfica cuando solo necesitamos una función de hashing tradicional. Esto es porque las funciones criptográficas son menos eficientes y estarı́amos perdiendo velocidad a cambio de propiedades adicionales que no necesitamos!
