Grand opening EiPSI: Bruce Schneier y Whitfield Diffie en Eindhoven
Los próximos días 21 y 22 de abril se inaugura el nuevo grupo de investigación de la TUe sobre seguridad de la información y criptografía, llamado EiPSI. Para celebrarlo, se ha organizado un evento con charlas bastante interesantes sobre criptografía en la universidad, en las que estarán como reza el título Bruce Schneier (autor del famoso Applied Cryptography y de uno de los algoritmos propuestos para el estandar AES, Twofish ) y Whitfield Diffie, uno de los autores del famoso intercambio de claves Diffie-Hellman entre muchos otros.
Yo estaré allí el lunes y si me dejan en la empresa el martes también. Había que registrarse antes de este miércoles, pero como no me lee nadie que esté por aquí pues creo que tampoco pasa mucho por avisar tan tarde.
Se puede ver el programa aquí. Ya daré mis impresiones cuando llegue el momento ;-).
Protecciones contra Side Channel Analysis
Volvemos a la carga con el tema de SCA. Después de ver qué es eso del Side channel analysis y analizar los análisis de consumo de potencia en los dos posts anteriores, esta vez vamos a comentar un poco las medidas más usuales para hacer frente a este tipo de análisis, y más concretamente contra power analysis.
El análisis simple, en el que tomamos una o unas pocas tramas y mediante algún tipo de inspección (normalmente visual y poco más) de ésta intentamos obtener la clave es fácil de resolver mediante la eliminación de dependencias con la clave en el algoritmo. Por ejemplo, como vimos en el caso del ataque a RSA, haciendo que se calculen todos las posibilidades y haciendo la elección después.
En el caso de análisis de potencia diferencial, lo que debemos hacer es intentar reducir CUALQUIER relación del consumo de potencia con los datos o la clave, debido a que tras adquirir muchas trazas se realiza una medida de la relación de éstas con las trazas para decidir qué clave es la buena (usualmente esta medida es un cálculo de la correlación entre las trazas medidas y los consumos hipotéticos). Así pues, para tratar de reducir dicha correlación tenemos dos estrategias principales:
- Hiding : Como su nombre indica, se trata de ocultar de alguna forma estas relaciones.
- Masking : en este tipo de protecciones lo que se hace es enmascarar el cálculo de las operaciones conflictivas utilizando valores aleatorios, para luego obtener a partir de este cálculo con distribución uniforme el valor real.
Dentro de los métodos de ocultación podemos encontrar diversas técnicas. Una de ellas es introducir retardos aleatorios en ciertos puntos del algoritmo, con lo que se consigue que las trazas de consumo de potencia no estén perfectamente alineadas y se reduce la correlación con los valores hipotéticos de consumo.
Otra técnica comentada con frecuencia consiste en añadir ruido en amplitud al consumo de potencia. Puesto que estamos buscando cierta señal útil dentro de la medida (aquella parte relacionada con los datos y/o la clave), siempre podemos añadir más potencia de forma aleatoria, por ejemplo activando subsistemas inactivos en el chip, como conversores AD/DA, interrupciones, etcétera.
También se suele usar el hecho de que muchos de los procesos llevados a cabo en un algoritmo de cifrado se pueden realizar de forma paralela, con lo cual en software podríamos reordenarlos sin problemas o incluso si tenemos multithreading realizarlos en paralelo (y si tuviesemos varios cores o un sistema multiprocesador... pero hablamos de smart cards y dispositivos embebidos). Por ejemplo, hablando de DES podríamos hacer las búsquedas en las S-box de forma aleatoria empezando con un número aleatorio e incrementar el número cada vez, empezando por la primera cuando lleguemos a la última.
Para acabar con las medidas de ocultación (que conozco) , podríamos realizar varias implementaciones alternativas de ciertas partes del algoritmo e ir alternando entre ellas en cada cifrado eligiendo cuál usar de forma aleatoria.
En cuanto a medidas de masking, hay que ver cada algoritmo por su parte. Los algoritmos como DES o AES que realizan búsquedas en tablas (las famosas sbox se suelen implementar como tablas en software), se suelen tomar valores aleatorios y realizar una nueva tabla equivalente que tenga en cuenta dicho valor aleatorio, y luego hacer el acceso a memoria tomando el valor aleatorio. Por ejemplo, tomamos m aleatorio, y hacemos una tabla S' tal que S'[i+m]=S'[i]+m. Ahora, cuando tenemos que hacer el acceso, lo hacemos a la posición i+m de la tabla y posteriormente hacemos la resta del valor m al resultado tras la búsqueda en la tabla.
Para algoritmos como RSA, se suele hacer con un exponente aleatorio que tras el descifrado o la firma del documento se invierte, volviendo al valor inicial. Creo que ya lo comenté en el primer post sobre SCA.
Evidentemente, cuantas más medidas añadamos más difícil será romper la implementación con este tipo de técnicas, pero hay que buscar un compromiso entre la mejora en seguridad y el empeoramiento de las prestaciones. El objetivo será pues desarrollar un sistema con una seguridad y prestaciones aceptables combinando varias de estas medidas.
Ataques a smart cards: Side channel analysis (II)
En este post volvemos al tema de las smart cards, continuando con los ataques de tipo side channel analysis. En el post anterior vimos qué es eso del side channel y qué tipos había, así como analizamos un ataque a RSA basado en el tiempo de ejecución de una potencia realizada con el método de cuadrados repetidos ( repeat squaring ).
En este post vamos a hablar un poco del análisis de potencia ( power analysis ), en qué se basa y cómo funciona. No voy a poner ningún ejemplo concreto aquí, aunque al final enlazo a una página con ejemplos para matlab/octave.
Bases del análisis de potencia
Los ataques mediante análisis de la potencia consumida se basan en que, en un microcontrolador o microprocesado, la potencia consumida por el dispositivo depende de:
- La instrucción ejecutada
- Los datos tratados en dicha instrucción
Así pues, si la potencia consumida depende de los operandos de la instrucción, es lógico pensar que analizando dicha potencia consumida en un proceso conocido pero con unos datos desconocidos ( clave? ) podríamos llegar a obtener estos datos desconocidos.
Medida de la potencia consumida en smart cards
Como ya conocemos, la alimentación y el reloj de una smart card es proporcionada por el lector mediante sus pines externos. Por tanto, es sencillo introducir elementos en esa red de alimentación para poder calcular el consumo de potencia del dispositivo durante su operación.
El circuito más sencillo que se nos puede ocurrir es introducir una pequeña resistencia en serie con la línea de Vcc o de GND del dispositivo, por ejemplo de 1 ó 50 Ohmios. De esta forma, la corriente que fluye por la resistencia es la misma que la que fluye por el dispositivo, y realizando una medida de la tensión caída en dicha resistencia tenemos un valor proporcional al consumo de potencia del dispositivo.
Otra opciones más avanzadas incluyen el uso de circuitos estabilizados con la intención de que el circuito de medida afecte en la menor manera posible al dispositivo que se está analizando.
Análisis de potencia simple (SPA)
El análisis de potencia simple, o SPA de sus siglas en inglés, se basa en la inspección de una o unas pocas trazas de la potencia consumida por el dispositivo bajo estudio. De esta forma resulta sencillo obtener información sobre qué operación está realizando el dispositivo mediante la observación de patrones conocidos en las trazas.
Por ejemplo, la observación comentada en el post anterior sobre RSA se podría realizar con una de estas trazas directamente, mientras que con DES o AES probablemente no seríamos capaces de deducir ninguna clave. Lo que sí seríamos capaces es de determinar que se está realizando un cifrado DES debido a la aparición de 16 patrones similares que denotan las 16 rondas de cifrado/descifrado de DES.
Análisis de potencia diferencial (DPA)
Esta modalidad del análisis de potencia requiere la adquisición de muchas trazas de la potencia consumida por el dispositivo. Básicamente el procedimiento es el siguiente:
- Adquirir trazas de potencia del dispositivo
- Escoger un resultado intermedio del cifrado para atacarlo
- Calcular todos los posibles valores del resultado intermedio
- Obtener una estimación del consumo de potencia en base a dichos valores
- Calcular mediante alguna función de medida la clave más probable
Como ejemplo, en el punto 2 podríamos escoger los valores de salida de la primera S-box de AES ( o el componente SubBytes que es lo mismo) en la primera ronda de ejecución, y para cada valor del primer byte de la clave, k, combinado con el primer byte de datos,d, obtener el valor S[ k XOR d].
A partir de aquí se aplica el modelo de consumo elegido, que puede ser tan simple como LSB del valor o un poco más elaborado como el peso hamming del mismo, HW(S[ k XOR d]).
Finalmente se realiza la comparación mediante algún operador estadístico como puede ser la correlación de las trazas con el consumo estimado, o la diferencia de las medias como se explicaba en el paper original de Paul Kocher y otros. Todas estas funciones de medida tienen la propiedad de que a mayor resultado, más probable es la clave. Por tanto, buscando el máximo de la comparación encontraremos el valor del resultado intermedio, y de ahí el de la clave.
También tienen la propiedad de que a mayor número de trazas, más fácil encontrar el valor correcto de la clave; así pues, el número de trazas necesario para romper una implementación puede ser usado como indicativo de la seguridad de las protecciones implementadas en la misma, de las cuales hablaré un poco más adelante.
No voy a decir más sobre esto, pero existen libros completos sobre el tema de análisis de potencia, así que voy a dejar simplemente la referencia a un libro y a su web. El libro se llama Power Analysis Attacks, de la editorial Springer, y en su web se pueden obtener trazas en un workspace para matlab y/o octave, además de un ejemplo guiado de ataque.
Nuevo cuatrimestre, nuevas clases… y proyecto
El lunes pasado comenzó el segundo cuatrimestre y ya tengo nuevos frentes en los que lidiar en clase. Este cuatrimestre voy a hacer dos asignaturas y el PFC, con lo cual a finales de julio probablemente habrá concluido mi carrera a la espera de presentar el PFC en Valencia por septiembre.
Las asignaturas que tengo este nuevo cuatrimestre pintan interesantes, aunque parece que tengan una carga matemática importante y que me van a mandar unos cuantos trabajitos semanales para ir haciendo:
- Cryptography 2: se divide en dos partes, protocolos y sistemas. En la primera parte Berry Schoenmakers nos dará nociones sobre protocolos criptográficos incluyendo pruebas de su seguridad y concluirá con un examen parcial. En la segunda parte, Benne de Weger (el mismo de las colisiones en MD5 ) hablará de criptosistemas: PKI, Single sign-on, SSL, Kerberos, etc. y concluiremos la asignatura con dos papers.
- Verification of Security Protocols: en esta asignatura aprenderemos a verificar la seguridad de protocolos de comunicación que empleen criptografía, ya sea con métodos manuales o utilizando herramientas como proVerif. Tiene trabajos (70%) y examen final (30%).
En los enlaces se pueden encontrar las notas de clase y/o transparencias, si no ahora conforme vaya avanzando el curso.
Finalmente, ya he empezado el proyecto en la empresa Riscure en temas relacionados con smart cards y side channel analysis aunque de momento no he avanzado demasiado. Ahora tengo dos semanitas de vacaciones para irme de viaje final de carrera con la gente de Valencia, y luego vuelta al trabajo de nuevo.
FireGPG: GnuPG en tu Firefox
Hace un par de días estuve buscando cómo podía integrar GPG con Firefox y/o Gmail para poder cifrar/firmar correos desde el navegador sin tener que irme a copiar el texto a un archivo, cifrar/firmar el texto y luego copiarlo a Gmail cada vez.
Al poco de empezar encontré una extensión de Firefox llamanda FireGPG que necesita de GPG instalado y te permite utilizar las funciones de GPG desde Firefox. Se integra perfectamente en Gmail añadiendo botones de Firmar, Cifrar, Firmar y Enviar, Cifrar y Enviar, ... y verificando las firmas recibidas de manera automática.
Además añade una opción al botón derecho que te permite cifrar,firmar y verificar firmas de selecciones y contenidos de los formularios, importar y exportar firmas, y abrir una ventana de un editor propio para realizar allí las acciones que desees.
Es bastante cómodo y resuelve a la perfección el problema de usar GPG desde un Webmail 🙂
Ataques a smart cards: side channel analysis (I)
Volvemos a darle un poquito al tema de las smart cards ;-). Antes de continuar, sería recomendable que quien no conozca prácticamente nada sobre smart cards lea los posts anteriores al respecto:
- Introducción
- Normas y comunicación
- Clasificación de ataques
Pese a que hay mucha información al respecto en Internet y en libros, no sé si la hay en español así que espero que siga resultando útil/interesante a la gente :-).
En este post vamos a ahondar un poco más en uno de los ataques más famosos sobre smart cards. Se trata del llamado Side Channel Analysis o SCA ( en español supongo que se traduciría como análisis de canales adyacentes o algo similar) que consiste en analizar datos procedentes de la smart card por canales alternativos.
Como ya vimos, una smart card se comunica con el exterior únicamente mediante una interfaz serie a través de uno de sus contactos. En cambio, como cualquier dispositivo electrónico, estas tarjetas 'sufren' algunos fenómenos físicos que permiten obtener información. Veamos los principales canales utilizados:
- Información temporal: realizando mediciones de lo que tardan distintas operaciones.
- Consumo: midiendo el consumo de potencia del dispositivo también es posible determinar qué está haciendo.
- Radiaciones electromagnéticas: como todos sabemos, cualquier movimiento de electrones genera un campo electromagnético, y nuestras tarjetitas no iban a ser menos.
En este primer post sobre side channel analysis vamos a ver un ejemplo de información temporal que nos puede ayudar a romper un algoritmo considerado seguro como RSA debido a una 'mala' implementación. Para ello primero (en la página extendida para no alargar mucho la portada) explicaré brevemente cómo funciona RSA, la implementación base que usaremos y luego el problema que tiene y cómo podríamos solucionarlo.
De MD5, colisiones, presidentes de EE.UU. y PS3
Ayer Lunes comentaron en Barrapunto ( y previamente en meneame ) acerca de una predicción sobre el resultado de las próximas elecciones de los Estados Unidos realizada por unos investigadores de la universidad donde estoy ( TU Eindhoven ), concretamente Benne de Weger ( profesor de Cryptography 2, a parte de haber dado este año la parte de RSA de Cryptography 1 ) junto con Marc Stevens y Arjen Lenstra.
Lo que han hecho ha sido crear varios documentos PDF con las posibles predicciones, pero que todos tengan el mismo hash MD5 (es decir, encontrar colisiones en MD5). Aquí voy a explicar sin entrar en mucho detalle y lo mejor que pueda qué es lo que han hecho para quien esté interesado y no tenga ganas/tiempo de leer el documento.
Antes de empezar, conviene conocer un par de términos (enlace a Wikipedia en inglés): hash collision y hash function (ver también el enlace a función hash criptográfica) . Desde allí se puede ir también a la versión española 🙂
Asumiendo que ya conocemos qué es un hash y qué es una colisión, cabe mencionar que generalmente las funciones de hash funcionan en base a varias iteraciones sobre una función de compresión, utilizando en cada iteración un bloque de datos del mensaje y un valor de hash intermedio ( IHV, Intermediate Hash Value ). El valor obtenido con el último bloque del mensaje (al que probablemente se haya añadido relleno para que sea múltiplo del tamaño de bloque ) es el hash buscado.
Pese a que en 2004 ya se publicó cómo obtener colisiones con MD5 ( prof. Xiaoyun Wang ), en este caso se trataba de mensajes aleatorios, lo cual hace que aunque dos mensajes tengan el mismo hash, probablemente solo uno de ellos tenga cierto significado. En el caso del nuevo ataque, que describen como chosen-prefix collisions, el documento puede tener una parte inicial arbitraria, siempre que a partir de cierto momento todos los documentos sean iguales.
Lo que describen en su paper Benne de Wenger y sus co-autores es un mensaje con los 3 siguientes campos:
- Un prefijo cualquiera
- Un relleno aleatorio, para que el tamaño de los 3 campos sea múltiplo del bloque
- Una cadena elegida de forma que la diferencia entre IHVs en este campo tenga ciertas propiedades
Con esto, la diferencia entre IHVs conseguida no es nula, pero es posible obtener una colisión mediante lo que ellos llaman near-collision blocks, consturidos para reducir estas diferencias.
A partir de aquí, tenemos dos documentos con un hash idéntico, aunque con cierta basura, y podemos añadir lo que queramos detrás siempre que sea igual para ambos archivos.
Lo que han hecho en este caso, es poner esa basura en una imagen oculta dentro del PDF, y aunque no he examinado los documentos, supongo que la parte final idéntica en todos cierra la imagen y añade todos los campos que necesite el formato PDF (que desconozco) para tener un documento válido.
La mejora de este método frente a lo descrito en el CITS, es que en el nuevo método no es posible encontrar rastros de que existe el documento fraudulento, mientras que en el anterior el documento postscript contenía dos bloques de contenido y se podía ver el otro documento.
¿Y qué tiene que ver la PS3 con todo esto? Pues simplemente que han usado una PS3 con sus múltiples cores para realizar los cálculos, además de un PC quad core. En su paper inicial comentan que les tomó unos 6 meses de trabajo con miles de PCs para encontrar las colisiones, pero con la técnica nueva unos 2 días son suficientes, usando una PS3 y un PC quad core.
Shamir’s secret sharing: Secretos digitales compartidos
Con este post voy a salirme un poco de lo que viene siendo la temática habitual para meterme en otra un poquito más freak si cabe: la criptografía. No vamos a hablar de ningún algoritmo de cifrado ni de ningún criptosistema, sino de una técnica para compartir secretos digitales.
¿Qué es eso de compartir secretos? Imaginemos que somos parte del comité ejecutivo de una compañía que ha creado un producto revolucionario y desea que sus detalles se guarden en secreto, pero nuestro comité ejecutivo desea poder acceder a dicho secreto. Sin embargo, no queremos que un único miembro de dicho comité pueda acceder al secreto, sino que haya un determinado número de miembros presentes para dicho acceso. De esta forma, si un miembro por la razón que sea intenta acceder al secreto solo, el acceso será denegado.
Cómo podemos conseguir eso? Todos sabemos que para crear una recta sólo necesitamos dos puntos, una parábola 3, etcétera. Por tanto, una forma sencilla conocida como el esquema de Shamir (en inglés) se basa en el hecho de que con k+1 puntos de un polinomio somos capaces de reconstruir el polinomio entero. Para ello, se usa la interpolación polinómica de Lagrange , y en base a un determinado número de puntos se obtiene el polinomio.
Así pues, lo que habría que hacer para un esquema de secretos compartidos con n usuarios totales y un mínimo de k para obtener el secreto es lo siguiente:
- Codificar el secreto como un entero, S.
- Elegir un polinomio de grado k-1, f(x)=S+a·x + b·x^2 + ...
- Obtener n puntos de dicho polinomio y repartirlos a los n usuarios.
Así pues, cada usuario tiene su punto, y el polinomio se mantiene en secreto. Cuando se juntan k o más usuarios, simplemente aplican la fórmula de interpolación de Lagrange sobre esos puntos, y obtienen el término independiente del polinomio: nuestro secreto.
Este esquema se puede usar por ejemplo para el acceso a un sistema, siendo el secreto el password de acceso y teniendo cada usuario su propia clave. De esta forma, se proporcionan tres claves al sistema y éste reconstruye el polinomio mediante la fórmula de interpolación de Lagrange. Si el término independiente coincide con el esperado el acceso es permitido, y si no es denegado.
Un ejemplo simple e interesante de lo que pueden dar de sí las matemáticas, aplicando cosas sencillas que la mayoría conocemos de forma inteligente 🙂