¿Que es un HASH?
Un hash es el resultado del proceso de aplicar una entrada una función hash, la cuál procesa la entrada para dar un resultado que tiene las siguiente características:
- Tiene un tamaño fijo, independientemente del tamaño de los datos que hemos proporcionado en la entrada.
- Es determinista, lo que significa que si cambiamos la entrada, el resultado será un hash distinto. La misma entrada da el mismo resultado, pero entradas diferentes, dan resultados diferentes.
- Unidireccional, de ninguna manera podemos reconstruir los datos de entrada, si poseemos únicamente el hash de salida.
Una de las cualidades más interesantes de las funciones hash, es la capacidad para garantizar que existe una probabilidad muy baja de que se produzcan colisiones, es decir, que dos entradas distintas generen el mismo resultado. Evitar colisiones en las funciones hash es muy importante, ya que la mayoría de los casos en los que se emplean este tipo de funciones, tienen relación con la verificación de la integridad de datos que se comparten. Por tanto, una función hash que no garantice una baja probabilidad de colisiones, no resultaría de mucha utilidad, ya que la integridad de los datos, no se podría garantizar empleando hashes.
La importancia de las colisiones en las funciones hash.
Como hemos comentado, en el apartado anterior, una función hash debe garantizar una probabilidad muy baja, de que se produzcan colisiones. Si la función hash tiene una implementación pobre en la forma en la que se generan los hash, de tal manera que la probabilidad de generar una colisión fuese alta. Un usuario malicioso podría desarrollar una forma para provocar un colisión que condicionara la integridad del dato.
Veamos cuál es el problema de las colisiones de las funciones hash mediante el siguiente ejemplo. Alice y Bob quieren compartir un dato de forma segura, para ellos acuerdan que Alice genera el dato y utilizará una función hash para obtener una hash, que ayude a Bob a verificar que el dato que recibe es el que Alice ha generado.
El esquema anterior, muestra el flujo de las acciones que Alice y Bob, deben ejecutar para compartir el dato.
- Alice aplica al Dato una función para obtener el hash.
- Obtiene el Hash asociado al Dato.
- Guarda el Dato en un repositorio.
- Envía el Hash a Bob
- Bob recupera el Dato del repositorio
- Aplica la función hash y la compara con el Hash que le ha enviado Alice.
Este sería un ejemplo sencillo del esquema para compartir datos de manera segura, utilizando dos canales diferentes, el repositorio del dato y la comunicación entre Alice y Bob para compartir el Hash asociado a dicho dato.
El problema en este esquema, es que si la función hash que se ha empleado, permite generar de forma sencilla, colisiones, es decir, podemos tener varias entradas en la función que provoquen la misma salida. Un atacante podría ejecutar la siguiente acción, para engañar a Bob.
El siguiente esquema, muestra un ejemplo en el que un atacante, puede sustituir el dato, aprovechando que la función hash no es fuerte y se pueden generar colisiones. Para engañar a Bob sobre la integridad de los datos.
- Alice aplica al Dato una función para obtener el hash.
- Obtiene el Hash asociado al Dato.
- Guarda el Dato en un repositorio.
- Envía el Hash a Bob
- El atacante obtiene el Hash del dato.
- Genera una nueva versión del dato, cuyo hash coincida con el hash del dato original. Ha provocado una colisión en los hashes.
- Bob recupera el dato y calcula el hash
- Compara el Hash que ha calculado, con el hash que Alice le ha enviado, comprobando que son el mismo y por tanto puede confiar en el dato del repositorio, ya que tiene la certeza que es el dato que ha dejado Alice.
¿Qué son los Chameleon Hash?
Es un tipo de función hash, que permite implementar un trapdoor o trampilla al propietario, para generar colisiones de manera controlada, provocando que distintos mensajes de entrada obtengan como salida, el mismo hash.
Los Chameleon Hash se pueden construir de muchas maneras distintas, aquí vamos a ver cómo podemos construir una función hash utilizando curva elíptica.
El esquema es muy sencillo, ya que se basa en construir un hash que esté asociado, no solo al contenido del mensaje que se quiere calcular, sino a otras variables, que estén controladas por el usuario que genera el chameleon hash y que solo él puede generar colisiones. Como estamos utilizando Curva Elíptica, contamos que el usuario ha generado una clave privada y la clave pública asociada. Si no tiene conocimiento sobre qué es una Curva elíptica, sería interesante echar un vistazo al post Criptografía de Curva Elíptica en el que se repasan los principios básicos.
- s la clave privada generada por el usuario.
- Disponemos de un punto en la curva que denominaremos G y nos sirve como generador.
- P es la clave pública que se obtiene con:
P = s G
- El usuario tiene un mensaje m, al cual aplica una función hash tradicional, por ejemplo HASH256.
- h es el hash producido por:
h = HASH256(mensaje)
El planteamiento para construir la función Chameleon Hash es el siguiente:
- Vamos a elegir un número aleatorio que llamaremos r con el que obtendremos un punto de la curva.
R = rG
- Necesitamos una expresión que nos permita calcular un número para relacionar, el número aleatorio r, con la clave privada s del usuario. Para esta relación utilizaremos la siguiente ecuación:
c⋅G = r⋅G + h⋅P (mod n)
- Queremos obtener un punto de la curva c⋅G que sea igual a la suma del punto R más la multiplicación del hash del mensaje por el punto P (que es la clave pública del usuario).
c⋅G = r⋅G + h⋅s⋅G (mod n)
c = r + h⋅s (mod n)
- Calculamos c y este será junto al punto R, el Chameleon Hash del mensaje. Si un usuario quiere comprobar el Chameleon hash necesita la terna:
(Mensaje, R, c,ClavePública)
Con los 4 elementos y sustituyendo en la siguiente ecuación, un usuario puede comprobar el hash del mensaje, si al sumar R y el punto h⋅P, obtiene como resultado el punto c⋅G.
c⋅G = R + h⋅P (mod n)
Lo que representa el Chameleon Hash es, para un mensaje, hemos generado un punto R aleatorio que lo hemos asociado al punto P y al mensaje. De esta forma el propietario del Chameleon Hash tiene una forma de generar colisiones sobre el mismo hash. Veamos cómo sería el proceso de generar estas colisiones.
- Calculamos el hash de un nuevo mensaje, diferente al mensaje anterior.
h = HASH256(mensaje2)
- Ahora debemos buscar un valor que nos ayude a cumplir con la siguiente ecuación:
c⋅G = r’⋅G + h⋅s⋅G (mod n)
Despejamos r’⋅G, porque el resto de valores los tenemos.
r’⋅G = c⋅G – h⋅s⋅G (mod n)
Esta ecuación no da como resultado, el punto de la curva para el nuevo mensaje, teniendo en cuenta que c no cambia. Como resultado obtendremos la siguiente terna.
(Mensaje2, R’, c,ClavePública)
Si un usuario aplica el mensaje 2 a la función Chameleon Hash con R’ y la clave pública del propietario del chameleon hash, obtendrá como resultado c, con lo que puede validar, que el mensaje genera una colisión sobre c.
Generar un hash camaleón
Un hash camaleón está formado por una pareja de elemento (R,c):
- Donde “R” es un punto de la curva elíptica que se forma:
R = r ⋅ G
- r es un número aleatorio.
- G es el punto base de la curva.
- Donde “c” se obtiene mediante la siguiente fórmula:
c = r + k⋅h (mod n)
- r es el número aleatorio que hemos elegido para calcular R.
- k es corresponde a la clave privada
- h es el hash del mensaje.
Por tanto para generar un hash camaleón debemos ejecutar los siguientes pasos:
- Calculamos el hash del mensaje.
h = hash(mensaje)
- Elegir un valor aleatorio r.
- Calculamos el valor del punto de la curva R.
R = r ⋅ G
- Resolvemos la fórmula para calcular el valor de c.
c = r + k⋅h (mod n)
- Ya tenemos el hash camaleón del mensaje m, es la pareja (R,c), en el que R es el punto de la curva que representa al valor aleatorio de r y c es el valor que asocia la clave privada con el valor aleatorio r y el hash del mensaje.
Validar un hash camaleón
Ya hemos generado el hash camaleón (R,c) del mensaje m. Ahora vamos ver cuál sería el proceso para que un usuario pudiera verificar que el hash corresponde al mensaje m.
El usuario tendría que resolver la ecuación:
c = r + k⋅h (mod n)
Pero no puede utilizar k que es la clave privada, en su lugar el usuario solo conocer clave pública P. Hay que transformar la ecuación para que un usuario que solo conozca P, pueda validar el mensaje. Además la ecuación anterior trabaja con r, cuyo valor también es desconocido para el usuario.
El primer paso multiplicar todos los términos de la ecuación por G, ya que de esta forma conseguimos transforma k en P, recuerda que P = k⋅G y R = r⋅G
cG = rG + kG⋅h (mod n)
cG = R + P⋅h (mod n)
En aritmética de curva eliptica, la resta se implementa como el inverso aditivo de Ph:
−P⋅h =(hPx,−hPy)
R = cG + (−P⋅h) (mod n)
Si el resultado es correcto, entonces el usuario puede comprobar que la pareja (R,c) sirven para validar el mensaje m.
Generar una colisión.
Por la propiedad que tiene el hash camaleón, el usuario que controle la clave privada, puede generar colisiones, es decir, puede generar parejas (R,c) para diferentes mensajes y conseguir que el valor de c permanezca inmutable.
Mensaje1: “Hola” -> HashCamaleón() -> (R,c)
Mensaje2: “Adiós” -> HashCamaleón -> (R’,c)
Para generar un colisión con el mensaje2 se ejecutan los siguientes pasos:
- Calculamos el hash del mensaje.
h = hash(mensaje)
- Aplicando la ecuación para calcular c, sabiendo que estamos buscando un nuevo punto R de la curva que cumpla con la ecuación.
cG = r’G + kG⋅h (mod n)
r’G = cG – kG⋅h (mod n)
En aritmética de curva eliptica, la resta se implementa como el inverso aditivo de Ph:
−P⋅h =(hPx,−hPy)
R’ = cG + (−P⋅h) (mod n)
El punto R’ es el que cumple con la ecuación, y está asociado al hash h y al punto cG. Si aplicamos el proceso de validación al menaje (“Adiós”,R’,c) podemos comprobar de forma sencilla con la ecuación:
cG = R’ + Ph (mod n)
Nota: Este es un ejemplo para mostrar cómo se puede implementar este tipo de hashes utilizando curva elíptica. El propósito es mostrar de manera más o menos didáctica, una implementación de los Chameleon hashes con curva elíptica y no se debería implementar este modelo, ya que si conoce algo sobre curva elíptica, podrá encontrar una forma sencilla, en este ejemplo, para generar colisiones de manera no autorizada.
Un método más seguro
La forma en la que se ha planteado la generación del Chameleon hash en los pasos anteriores, no es segura, ya que permite generar colisiones de manera sencilla. Vamos a cambiar el planteamiento, para para que sea más seguro.
Para el nuevo planteamiento, vamos a trabajar con un punto de la curva, al que denominaremos R. Este punto lo mantendremos en secreto y servirá para poder validar el Chameleon hash. Para construir nuestro Chameleon hash vamos a utilizar la siguiente ecuación:
s = (z + c⋅d) / k
Donde :
- z es el hash del mensaje.
- c es un número aleatorio.
- d es la clave privada.
- k es un número aleatorio.
También vamos a utilizar un parámetro r que lo obtendremos realizando las siguiente operaciones:
R = k⋅G
R = (x,y)
r = x mod n
Una vez generado el Chameleon hash, podemos utilizar s como identificador del hash y c como valor para verificar que el mensaje genera una colisión sobre el Chameleon hash. Para que un usuario pueda validar el mensaje debemos facilitarle la siguiente terna:
(Mensaje,s, r, c,ClavePública)
El proceso de validación para un usuario que conoce (Mensaje, s, r,c, ClavePública) consiste en resolver la siguiente ecuación, que nos devuelve el punto R’ de la curva.
R’ = (z/s)G + (c/s)P
R’ = (x,y)
r’ = x mod p
Comprobamos que el valor que hemos obtenido r’ coincide con el valor que tenemos de r. En caso afirmativo podemos asegurar que el mensaje, han sido generados por el propietario del Chamaleon Hash.
Para generar colisiones, solamente tenemos que utilizar la siguiente ecuación, despejando c, para calcular el nuevo valor en función del mensaje utilizar para generar la colisión:
s = (z + c⋅d) / k
c’ = (sk – z’)/ d
Una vez despejada c, ya tenemos una nueva colisión, del mensaje z’ sobre el hash s.
(Mensaje_nuevo,s, r, c’,ClavePública)
Como se puede comprobar, este método para generar el Chameleon hash, es más seguro que el primero que hemos visto, ya que garantiza que un usuario sin acceso a la clave privada y al punto R, nunca podrá generar una colisión válida sobre el Chameleon hash que hemos generado y del que tenemos el control. El proceso que hemos descrito es una variante de la firma ECDSA, lo que permite tanto verificar el Chameleon hash como garantizar que solo el propietario de la clave privada utilizada ha podido generar la colisión.
Utilidades de los Chameleon Hash
Este tipo de hash tienen varias utilidades interesantes, en los que podemos aplicar su capacidad para generar colisiones. Por ejemplo, en soluciones que necesiten la generación de colisiones, para poder cambiar datos de forma controlada, sin la necesidad de modificar los controles de integridad del sistema. Otra utilidad interesante en la que se pueden emplear este tipo de hashes, es la distribución de tokens de acceso, para que un tercero los valide, con la garantía que han sido generados por una entidad de confianza.
Un caso de uso, es aquel en el que los datos generados por un conjunto de usuarios, puede ser alterados por este conjunto, aunque para el resto de usuarios, la integridad de los datos se mantiene igual. Este modelo garantiza, que solo el conjunto de usuarios autorizados, tiene la capacidad de modificar el dato, porque no modifican el hash. Mientras que si un usuario no autorizado cambia el dato, el hash cambia con lo que se evidencia que se ha realizado una manipulación no autorizada.
La tecnologías Blockchain, en las que la fortaleza y seguridad de los protocolos, se basan en poder asegurar de manera irrefutable, que se pudieran modificar datos de manera controlada, sin la necesidad de reconstruir toda la cadena, abre las puertas a poder usar esta tecnología en soluciones que implementen ciertos requisitos de GDPR, por ejemplo, el derecho al olvido. Para una red blockchain, una modificación de los datos asociados a una transacción, significa que el hash de dicha transacción cambia y por tanto, esto implica que cambie el hash del bloque en el que está dicha transacción. Al cambiar el hash del bloque se rompe la cadena, ya que el bloque posterior, tiene una referencia al bloque anterior empleando el hash del bloque.
José Juan Mora Pérez
CTO & Founder
