Diseño de un Servicio de Estampa de Tiempo Seguro con el Mínimo Requerimiento de Confianza

Massias, X. Serret Avila, J.-J. Quisquater 

Grupo Crypto UCL

Place du Levant, 3 , B-1348 Louvain-la-Neuve, Bélgica

 massias, serret, jjqdie.ul.a.be 

Este documento presenta nuestro diseño de un servicio de estampa de tiempo para el proyecto Belga TIMESEC. Primero, introducimos el método de estampa de tiempo usado y justificamos nuestra elección del mismo. Luego, presentamos el diseño de nuestra implementación así como algunos de los asuntos importantes que encontramos y las soluciones que les dimos.

INTRODUCCIÓN

La fecha de creación de documentos digitales y los tiempos expresados en estos se vuelven cada vez más importantes, dado que los documentos digitales están siendo introducidos al dominio legal. 

Definimos la “estampa de tiempo digital” como un certificado digital hecho para asegurar la existencia de un documento digital genérico en cierto tiempo. 

Para poder producir estampas de tiempo totalmente confiables, diseños muy específicos han sido presentados. Hacemos un repaso de los métodos más relevantes y presentamos el que nosotros usamos para la implementación del proyecto Belga TIMESEC (vea [PRQ+ 98], justificando nuestra elección del mismo. A continuación, presentamos el diseño de un sistema de estampa de tiempo usado para este proyecto. Separamos los diferentes procesos que son: Documentar la estampa de tiempo, verificación de la estampa de tiempo, auditoría, inicio y apagado del sistema. 

PRESENTACIÓN DE LAS TÉCNICAS DE ESTAMPA DE TIEMPO

Existen dos familias de técnicas de estampa de tiempo: aquellas que trabajan con un tercero de confianza y aquellas basadas en el concepto de la confianza distribuida. Las técnicas basadas en un tercero de confianza dependen de la imparcialidad de la entidad que está a cargo de emitir las estampas de tiempo. Las técnicas que se basan en la confianza distribuida consisten en hacer que los documentos lleven una fecha y firma por parte de un gran grupo de personas, pudiendo así convencer a los verificadores de que no se podría haber corrompido todos los documentos. Las técnicas de tercero de confianza también pueden ser clasificadas en dos tipos distintos: Aquellos donde el tercero es totalmente confiable y aquellas en las que es parcialmente confiable. Un estudio detallado de técnicas de estampa de tiempo puede ser encontrado en [MQ97]. Creemos que las técnicas basadas en confianza distribuida no son realmente viables en un ambiente profesional, es por ello que nos concentramos en el enfoque del tercero confiable. Sin embargo, nos impusimos a nosotros mismos el requerimiento de bajar el nivel de confianza necesario para el tercero al máximo. 

La solución fácil, que consiste en concatenar el documento con la fecha actual y firmar el resultado, ha sido descartado puesto que tiene dos grandes desventajas:

1. Se debe confiar por completo en el tercero, llamado Autoridad de Estampa de Tiempo Segura (STA por sus siglas en inglés), el cual puede emitir estampas de tiempo indetectables respaldadas por la banca. 
2. El tiempo de vida limitado de las firmas criptográficas, el cual puede ser más corto que el tiempo de vida del documento. 

El método de estampa de tiempo que hemos escogido usa una estructura de árbol binaria y ha sido descrito en [HS91] y [HS97]. Este método funciona por rondas, por cada ronda, un árbol binario es construido con las solicitudes llenadas durante ella. Las rondas tienen una duración determinada, que es el resultado de un trueque entre la precisión de las estampas de tiempo y el número de solicitudes presentadas. En la figura 1 vemos una representación gráfica de una ronda construida utilizando este método. 

Figura 1: La estructura del árbol binario. 

Cada una de las solicitudes de estampa de tiempo consiste en un trozo de valor de un documento dado. Las hojas del árbol son cada uno de esos trozos de valor. Las hojas de valores son entonces concatenadas con el valor obtenido por la ronda precedente (RHi1) y luego troceados de nuevo para obtener la real Ronda de Valores (RHi).

La estampa de tiempo del documento contiene todos los valores necesarios para reconstruir la correspondiente rama del árbol. Por ejemplo, la estampa de tiempo para y4 contiene f(y3; L); (H12; L); (H58; R); (RHi1; L)g. El proceso de verificación consiste en reconstruir las ramas del árbol y la cadena enlazante de Rondas de Valores hasta que una Ronda de Valores confiable (desde el punto de vista del verificador) sea re-computada. Este método de verificación es explicado en detalle en [HS91] y [MQ97]. 

Periódicamente, una de las Rondas de Valores es publicada en un medio inmodificable y ampliamente visto (Ej: periódico…). Estas Rondas de Valores, a los cuales llamaremos Grandes Rondas de Valores, son la base de la confianza para todas las estampas de tiempo emitidas. Todos los verificadores deben de confiar en esta Gran Ronda de Valores así como el tiempo asociado a los mismos. Este es un requerimiento razonable puesto que estos valores son ampliamente observados. El tiempo absoluto confiado por todos los verificadores potenciales es el tiempo indicado en el medio inmodificable. Suponemos que este tiempo es el mismo que el indicado por el STA para la Gran Ronda. Forzar a los clientes a chequear las estampas de tiempo tan pronto como las obtengan es otro requerimiento. De esta manera, el proceso es contínuamente auditado y la STA no tendrá ningún margen para maniobrar sin confianza. 

Un método muy útil para extender la vida útil de las estampas de tiempo es descrito en [BHS92]. Básicamente consiste en re-estampar en el tiempo el trozo de documento así como la estampa de tiempo original antes de que la función de troceado se rompa. 

Construimos dos árboles en paralelo para cada redondeo usando dos funciones de troceado diferentes (SHA-1 y RIPEMD-160). De esta manera, el sistema se mantiene seguro en el caso de un daño inesperado de una de las funciones de troceo utilizadas. 

DESCRIPCIÓN Y ANÁLISIS DE LA IMPLEMENTACIÓN DE ESTAMPADO DE TIEMPO TIMESEC

Ahora, presentaremos el diseño básico del sistema que hemos desarrollado, el cual está basado en la técnica presentada anteriormente.

Inicialmente, el usuario designa un documento para ser estampado en el tiempo. Dos trozos de este son creados utilizando los algoritmos SHA-1 y RIPEMD-160. La solicitud que contiene los dos trozos es entonces enviada por el cliente a la STA. Tras recepción de la solicitud, la STA crea la estampa de tiempo correspondiente usando el siguiente proceso: 

Descripción Principal del Proceso de Estampa de Tiempo

El diseño del sistema sigue un enfoque multi-hebra altamente disociado. Cada paso es asignado a un componente específico, el cual tiene su propia hebra distinta. En la Figura 2, presentamos un esbozo esquemático del proceso. El enfoque multi-hebra se justifica por el requerimiento de obtener una implementación altamente responsiva y de carga independiente. Al aislar las cargas del proceso en pasos independientes, intentamos desenlazar la carga entre ellas. Cada paso también tiene una fila ejecutable. Estas filas están a cargo de aliviar las diferencias de velocidad entre los diferentes pasos del proceso. 

Figura 2: Interacciones entre los componentes

El Receptor de Red

El Receptor de Red está a cargo de continuamente escuchar las solicitudes de estampa de tiempo de los clientes. El Temporizador de Solicitud recibe las solicitudes construidas del Receptor de Red. Entonces, las temporiza y reenvía al Coordinador de la Fila de Rondas. Cada ronda tiene su propio Coordinador de Fila de Rondas, el cual está a cargo de compilar y procesar en un árbol todas las solicitudes correspondientes a la ronda. Cuando el árbol de rondas ha sido computado, es enviado al Generador de Estampa de Tiempo, el cual genera las estampas de tiempo correspondientes. Una vez que una estampa de tiempo es generada, el Generador de Estampa de Tiempo lo reenvía a la Respuesta de la Red, que a su vez la reenvía al cliente. 

El Temporizador de Solicitud

Sólo existe una instancia del Temporizador de Solicitud en el sistema. El Temporizador de Solicitud está a cargo de ordenar las solicitudes recibidas desde los diferentes Receptores de Red y temporalizarlas acorde. Todas las demoras presentadas por el sistema antes de ese punto (es decir, aquellas presentadas por el Receptor de la Red) son indistinguibles de las demoras de red, y por lo tanto no se toman en cuenta. Una vez que una solicitud ha sido temporalizada, el Temporizador de Solicitudes intenta agregarla a la actual fila de ronda. Dado que las rondas se cierran de manera asincrónica por el correspondiente Coordinador de Fila de Rondas, esta operación no siempre es exitosa, en ese caso, el Temporizador de Solicitudes re-temporiza la solicitud y vuelve a intentar anexarla a la fila hasta que encuentra una ronda abierta. En ese proceso, la secuencia de solicitud se preserva para así entregar un comportamiento consistente. 

Creación del Coordinador de Fila de Rondas: 

Las instancias de Coordinación de Fila de Rondas son creadas por el Temporizador de Solicitudes al procesar una solicitud correspondiente a una ronda no-existente. La creación de las rondas que no tienen solicitudes es demorada hasta que se recibe una solicitud. Una vez creadas, esas rondas vacías son inmediatamente procesadas, sin presentar demoras significativas en el proceso. 

Determinación de números redondos: Los números redondos forman una secuencia integer ininterrumpida. Las rondas siempre están en sincronización con la duración de los intervalos. En otras palabras, si la duración de la ronda es de un minuto, todas las rondas empezarán en un límite de un minuto absoluto, independientemente de cuándo haya sido iniciado el sistema. Las Grandes Rondas son determinadas por el Temporizador de Solicitud usando un enfoque similar al seguido para determinar los límites de ronda. No restringimos la duración de la ronda a un valor x durante el espacio de vida del STA. Para alcanzar esto, la información respecto a la duración de las rondas y Grandes Rondas es introducida al sistema en la fase de inicio. Si deseamos modificarlo, debemos, primero, apagar el sistema, cambiar los valores y luego restaurar el sistema, el cual es el único procedimiento seguro que habíamos previsto. 

El Coordinador de Fila de Rondas

Lo primero que el Coordinador de Fila de Rondas hace es determinar el intervalo entre el tiempo real y el tiempo determinado para la ronda. Las solicitudes serán aceptadas sólo si la ronda es aún válida (la ronda se encuentra abierta). Cuando sea solicitado por el Temporizador de Solicitudes, el Coordinador de Fila de Rondas agrega la solicitud a la fila y la registra. Esta solicitud registrada será posteriormente usada para propósitos de auditoría de procesos.

Cuando el tiempo de ronda haya finalizado, obtiene los Valores de Ronda de la ronda precedente y computa los árboles binarios de ronda (uno por cada algoritmo hash) para obtener los correspondientes Valores de Ronda. Entonces entrega los árboles computados al Generador de Estampa de Tiempo y finalmente agrega al registro los Valores de Ronda y los Valores de Ronda Root. Estos valores registrados serán posteriormente usados para verificación de la estampa de tiempo y propósitos de audición de procesos. Si la ronda actual es una Gran Ronda, estos valores son reenviados a un medio xed también. 

Como habrá notado en la sección Introducción de las técnicas de estampa de tiempo, el árbol binario se define para un número de hojas (solicitudes) que es una potencia de 2. En general, esta no es la base. Podríamos crear solicitudes falsas para finalizar el árbol, pero esto agregaría muchas solicitudes (si tenemos 2n+1 solicitudes, entonces necesitaremos agregar 2n-1 solicitudes falsas). Una solución más inteligente sería agregar un valor aleatorio sólo cuando lo necesitemos. Entonces, agregaremos a la mayoría de los valores n (uno por cada nivel del árbol). Llamamos a estos nodos, Nodos Especiales, los cuales también quedarán registrados. En vez de valores aleatorios escogeremos usar el 0 o algún otro valor xed, esto sería tan seguro como nuestra elección si las funciones de hash fuesen perfectas. Dado que las funciones de hash son solo presumiblemente perfectas, pensamos en hacer nuestro diseño uno más seguro con muy pocas computaciones adicionales. 

En nuestra implementación, el STA deja en fila las solicitudes y computa el árbol al final de la ronda. A primera vista, parecería una solución más natural construir el árbol tan pronto como las solicitudes lleguen. Al final de la ronda, la computación del árbol sería entonces finalizada obteniendo el último Valor de Ronda y computando el actual Valor de Ronda. De hecho, esta solución es más difícil de implementar y no tiene ningún efecto en la seguridad alcanzada, dado que nadie puede chequear que el STA no ejecute ningún reordenamiento de las solicitudes antes de publicar el “Valor de Ronda”. 

El Generador de Estampa de Tiempo

El Generador de Estampa de Tiempo procesa los árboles de redondeo por pares (uno para cada algoritmo de hash) para así generar las estampas de tiempo por cada una de las solicitudes obtenidas en los árboles. Para poder maximizar la capacidad de respuesta del sistema, una vez ha sido generada una estampa de tiempo, esta es inmediatamente redirigida a la Respuesta de Red. Finalmente, cuando todas las estampas de tiempo contenidas en un árbol de ronda han sido procesadas, el árbol es destruido. 

La Respuesta de Red

La Respuesta de Red está a cargo de reenviar las estampas de tiempo procesadas a los clientes. Ha sido especificado de tal manera que pueda ejecutar varios hilos, de manera que el resto del proceso de estampa de tiempo pueda estar aislado de posibles problemáticas por retrasos en la red. 

El proceso de verificación de estampa de tiempo

Primero, el verificador designa un documento y su correspondiente estampa de tiempo para verificación. Entonces, el sistema del verificador (su computador personal o un computador remoto independiente del STA) genera los dos trozos (hashes) del documento y chequea si estos coinciden con los contenidos en la estampa de tiempo. Posteriormente, el Valor de Ronda es reconstruido usando los datos provistos en la estampa de tiempo. Si el Valor de Ronda computado es consistente con el contenido en la estampa de tiempo, entonces el próximo paso en el proceso de verificación será comparar este Valor de Ronda al Valor de Ronda obtenido del repositorio del STA. Finalmente, el verificador provee a sus sistema las dos Grandes Rondas de Valores que encuentra en el medio inalterable; el sistema del verificador obtiene todas las necesarias Rondas de Valores y Rondas Root de Valores del STA y chequea la coherencia de las dos cadenas enlazantes (una por cada función de hash). 

El proceso de auditoría

El auditor designa dos Grandes Rondas, las cuales saca de un medio xed. El comportamiento del sistema será chequeado entre estas dos Grandes Rondas de Valores. Para cada ronda, el sistema del auditor obtiene todos los valores de hash (hojas del árbol y Nodos Especiales) y el Valor de Ronda del STA. Entonces, construye los dos árboles y chequea que el Valor de Ronda sea consistente. Estos dos pasos se repiten hasta que todas las rondas consideradas son chequeadas o hasta que un error sea encontrado. De esta manera, todo comportamiento teóricamente verificable podrá ser verificado a posteriori. 

El proceso de iniciación del sistema

Aquí el asunto más delicado es ser capaz de iniciar el sistema correctamente cuando haya ocurrido un apagado inesperado. Si este es el caso, el registro mostrará una ronda no terminada; entonces el sistema marcará todas las entradas después de la última ronda completada como inválidas y publicará esa ronda como una Gran Ronda. Si el registro es consistente, accederá a la última Gran Ronda de Valores en el registro y la publicará como una Gran Ronda. Este proceso asegura un comportamiento totalmente verificable; seremos capaces de detectar las solicitudes no completamente procesadas. 

El proceso de apagado del sistema

El administrador señala al sistema que se apague. No más solicitudes de estampa de tiempo serán aceptadas. El sistema espera hasta que la ronda actual haya terminado y este Valor de Ronda es publicado como una Gran Ronda. 

REFERENCIAS

[BHS92] D. Bayer, S. Haber, y W.-S. Stornetta. Mejorando la eficiencia y confiabilidad de la estampa de tiempo digital. En Springer Verlag, editor, Sequences’91: Métodos en Comunicación, Seguridad y Ciencias Informáticas, páginas 329-334, 1992. 

[HS91] S. Haber y W.-S. Stornetta. Cómo estampar en el tiempo un documento digital. Journal de Criptología, 3(2):99-112, 1991. 

[HS97] S. Haber y W.S. Stornetta. Nombres seguros para cadenas de bits. En Procedimientos de la 4ta Conferencia ACM en Seguridad de Computadores y Comunicación, páginas 28-35. ACM Press, Abril 1997. 

[MQ97] H. Massias y J.j Quisquater. Tiempo y Criptografía. Reporte técnico, Proyecto TIMESEC (Proyecto Federal de Gobierno, Bélgica), 1997. Disponible en http://www.die.ul.a.be/rypto/TIMESEC.html. 

[PRQ+ 98] B. Preneel, B. Van Rompay, J.-J. Quiquater, H. Massias, y X. Serret Avila. Diseño de un sistema de estampa de tiempo. Reporte técnico, Proyecto TIMESEC (Proyecto Federal de Gobierno, Bélgica), 1998. Disponible en http://www.die.ul.a.be/rypto/TIMESEC.html.

Fuente: https://nakamotoinstitute.org/static/docs/secure-timestamping-service.pdf