Boletín ENIGMA - nº 74

1 de Marzo de 2010

 


Boletín del Taller de Criptografía de Arturo Quirantes Sierra


Dirección original: http://www.cripto.es/enigma/boletin_enigma_74.htm


EDITORIAL

TEMAS DE ACTUALIDAD - El ataque "Fish'n Chips"

TEMAS DE ACTUALIDAD - El ataque "Fish'n Chips": actualización a la española

TEMAS DE ACTUALIDAD - Redes eléctricas inteligentes

CRIPTO 101 - LFSR y pseudoaleatoriedad
 


 

 EDITORIAL

 

Hoy no me encuentro inspirado en esta sección, así que me perdonaréis si en esta ocasión no os cuento batallitas de las mías. Será que se me han secado las neuronas después de escribir este Boletín, en el que espero aprenderéis bastante sobre las redes de tarjetas de crédito y el problema del azar. O a lo mejor es que hoy es el Día de Andalucía, y como buen andaluz estoy siguiendo el tópico de la siesta y el no pegar palo al agua. De hecho, es hora de la siesta, así que con vuestro permiso me echaré un sueñecito. Hasta el mes que viene.

 


 

  TEMAS DE ACTUALIDAD - El ataque "Fish'n Chips"

 

Si usted, querido lector, pierde su tarjeta de crédito, o si se la roban, sabrá que lo primero que debe hacer es informar a su banco y/o al emisor de la tarjeta lo antes posible. Los amigos de lo ajeno son expertos en usar prontamente estas tarjetas, por ejemplo mediante compras online. No es habitual que se dediquen a saquear nuestra cuenta, ya que necesitarían el PIN para operar en el cajero automático.

Al menos, en teoría. La práctica es muy distinta. Se sabe que bandas de ladrones organizados se dedican a "trucar" cajeros automáticos. Insertan lectores especiales en la ranura de la tarjeta, de forma que copian no sólo la banda magnética de ésta, sino también el número PIN que ha introducido el usuario legítimo. Los bancos responden con contramedidas como refuerzos en sus cajeros, cámaras de vigilancia, campañas de concienciación, y últimamente se están dedicando a introducir tarjetas con chip. Dicho chip, al no poder ser falsificado, garantiza que los datos de una tarjeta no podrán copiarse.

De nuevo, esa es la teoría. Recientemente, un artículo de cuatro investigadores de la Universidad de Cambridge (Steven J. Murdoch, Saar Drimer, Ross Anderson y Mike Bond) ha mostrado la vulnerabilidad de este sistema. Dicho artículo nos permite, entre otras cosas, examinar el modo en que funciona la protección del sistema de pago con tarjetas bancarias, y hasta qué punto podemos fiarnos de lo que nos dicen.

En esta ocasión, el problema no se ubica en un algoritmo de cifrado, sino que es un problema de protocolo, es decir, de la interconexión entre múltiples algoritmos y rutinas matemáticas. Pero esto no sería el Taller de Criptografía si no aprovechásemos la oportunidad para diseccionar el sistema y entender su funcionamiento.

La bicha que nos ocupa hoy se llama EMV (Eurocard Mastercard Visa), y constituye hoy día el estándar más ampliamente utilizado para pagos con tarjeta. En el Reino Unido, se conoce como protocolo "Chip and PIN" (que yo rebautizo como "Fish and chips"). Se usa sobre todo en Europa, y comienza a abrirse camino en Canadá y los Estados Unidos. EMV funciona autenticando tanto la tarjeta como al cliente, mediante una combinación de códigos de autenticación criptográficos, firmas digitales y un número de identificación, el famoso PIN.

El ataque "Fish and Chips" es el típico "man-in-the-middle", o ataque de intermediario. Básicamente, el intermediario se introduce entre el terminal de la tarjeta (sea el cajero o la típica "bacaladera" de la tienda) y el banco emisor, haciendo creer a ambos que todo va bien cuando no lo va. Se supone que el protocolo EMV está diseñado para evitar, entre otros, este tipo de ataque, pero resulta que hay una fisura en dicho protocolo.

El sistema EMV se introdujo para reducir la oleada de fraudes con tarjeta de crédito, pero no parece haber dado más resultado que cambiar el tipo de fraude. Las pérdidas por robo de tarjeta han disminuido, pero al mismo tiempo han aumentado las falsificaciones. Uno de los mayores problemas aquí consiste en que con EMV, los bancos han "externalizado" los problemas relativos a transacciones en litigio. Según esto, el banco emisor decide que, si una transacción fraudulenta lleva un firma manuscrita, el responsable, y por tanto el que pierde la pasta, es el vendedor de la tienda; y si ha sido autorizada por un PIN, el que pierde es el cliente. Es decir, si usted recibe un cargo de mil euros por una comida que solamente le costó cincuenta, los 950 euros que faltan los perderá usted si usó el PIN, y el restaurante si lo que hizo fue firmar el recibo.

En cualquier caso, la banca siempre gana. Mi contrato de tarjeta con mi banco (llamémosle X), afirma que yo seré responsable "sin limitación alguna por el uso de la tarjeta antes o después de dicha notificación si actuase con dolo o negligencia, entendiéndose como conducta negligente el incumplimiento de las obligaciones de custodiar la tarjeta, mantener en secreto las claves de seguridad de la tarjeta y notificar al Banco su robo, hurto, extravío o falsificación." Si alguien utiliza mi tarjeta, el banco presupone que yo le he dado el PIN al ladrón, ya que ¿cómo podría usar mi tarjeta si no? En consecuencia, yo he actuado con negligencia, y por tanto soy responsable del uso de mi tarjeta. Fin del alegato.

De hecho, muchas de las quejas hechas al Defensor Financierio del Reino Unido (Financia Ombudsman Service) se zanjan con excusas del tipo "la tarjeta del cliente tiene un chip y se usó un PIN, así que el cliente tiene la culpa." Eso no sería irrazonable si el sistema fuese seguro. Pero no lo es. Ha llegado la hora de destripar el EMV, y ver de qué pasta está hecho. En realidad, EMV es una especie de "toolkit", una caja de herramientas donde cada banco escoge los protocolos que quiere usar, relativos por ejemplo al método de firma digital. Genéricamente, el protocolo EMV consta de tres fases:

- Fase de autenticación de la tarjeta: garantiza al terminal (lector de tarjetas o cajero automático) cuál es el banco que emitió la tarjeta, y que los datos de ésta no han sido alterados.

- Fase de verificación del dueño de la tarjeta: garantiza al terminal que el PIN introducido por el usuario es el mismo que se almacena en la tarjeta.

- Fase de transacción: garantiza al terminal que el banco autoriza la transacción.

Examinemos las tres fases más en detalle. Para ello, supongamos que estoy comiendo en el Risueño Jabalí. Tras el café y el chupito, entrego mi tarjeta Vista Titanium al camarero, emitida por el Banco Brando. El camarero introduce la tarjeta en el tarjetero ("el terminal"), y comienza la fiesta.

Primero, la autenticación de la tarjeta. Cuando ésta se inserta, el terminal solicita una lista de las aplicaciones que dicha tarjeta permite realizar (sea pago con débito, crédito, retirada de dinero de un cajero, etc), y escoge una. A continuación, el terminal solicita a la tarjeta los datos pertinentes, como número de cuenta o fecha de aducidad. Los datos incluyen diversos parámetros de control, incluida una firma digital RSA hecha sobre un subconjunto de los datos Intercambiados, y un cojunto de certificados digitales que liguen esa clave RSA con una clave "root" conocida por el terminal.

En segundo lugar, la verificación del dueño de la tarjeta. Dicha verificación comienza con un mecanismo de negociación entre la tarjeta y el terminal, con objeto de determinar qué método de verificación va a usarse. El terminal recibe un archivo llamado CVM (Cardholder Verification Method), en el que se detalla qué entiende la tarjeta por una autenticación válida. El proceso puede ser bastante complejo, ya que para decidir qué autenticación usar entran en juego muchos elementos. Por ejemplo, no es lo mismo usar la tarjeta en el cajero, en un supermercado, o en el concesionario Ferrari.

En la práctica, los terminales no suelen complicarse la existencia, y se limitan a echar mano de un conjunto de procedimientos sencillos. Por ejemplo, una tarjeta puede decidir que hay que usar el PIN, otra puede conformarse con una verificación de firma, o incluso no verificar nada en absoluto. O puede usar una variedad de tales sistemas: si la red no funciona y no se puede usar PIN, pasar al "modo pedir firma." También puede limitar el número de intentos de autenticación, como hacen los cajeros automáticos: tres intentos, y a la calle.

En mi caso, digamos que la tarjeta "piensa" que el precio del jabalí con salsa de menta que me he comido no justifica el uso del PIN, de modo que con un garabato en un trozo de papel hay suficiente. En los casos en que sí necesite usar el PIN (por ejemplo, para pagar el canon de la SGAE por aquella vez que me pillaron silbando "Año 2000" en la ducha), la tarjeta lo comparó con el que guardaba en su interior. En el caso de los cajeros automáticos, el proceso cambia levemente: el PIN se cifra y se envía al emisor de la tarjeta, quien comprueba que es el correcto y envía la respuesta al cajero.

Finalmente, el tercer paso. Ya estamos todos seguros de quiénes somos, así que pasamos a la autenticación de la transacción. No vamos a detenernos demasiado aquí. Básicamente, el terminal coge los datos fundamentales de la transacción (cantidad a pagar, fecha), le añade un número escogido aleatoriamente (y conocido como "nonce"), y hace una bolita con todo ello. Se lo envía todo a la tarjeta, la cual crea un Código de Autenticación de Mensaje (MAC). Dicho MAC suele generarse mediante el algoritmo de clave simétrica TripleDES, usando una clave que comparten la tarjeta y el banco.

Cuando el banco recibe la información, pasa a procesar los datos para decidir si se ha de aceptar la transacción. En esto entran comprobaciones tales como: ¿tiene fondos la cuenta?, ¿ha sido registrada esta tarjeta como robada? ¿es aceptable la transacción, o debe despertar sospechas el hecho de que hoy se usa en Londres y ayer se usó en Nigeria? Cuando el banco está satisfecho, envía el equivalente a un "de acuerdo con la transacción, puede proceder", la tarjeta procede y lleva a cabo !por fin! el pago. El cliente recibe su tarjeta, se queda con una copia del recibo, firma el otro para el camarero, y hasta la próxima. Todo esto sucede ante mis narices, sin que yo tenga que preocuparme más de recordar que en el futuro nunca debo pedir jabalí con salsa de menta.

Y ahora que hemos descrito el modo en que funciona el protocolo EMV, veamos en qué consiste en "ataque Fish´n Chips". El fallo se encuentra en la fase 2, la de verificación del dueño de la tarjeta. Digamos que la transacción requiere el uso del PIN. El usuario teclea su número, y la tarjeta la compara con la que guarda en su interior (o, en el caso de cajeros, se envía cifrada y se compara con la que guarda la base de datos del banco). Si ambos coinciden, la tarjeta devuelve el código "0x9000", que es un forma de decir "de acuerdo, coinciden"; en caso contrario, responde "0x63Cv", donde "v" es el número de intentos que el sistema permite antes de cerrarse en banda.

El problema es que ese código no está autenticado, lo que permite alterarlo. Para ello, introduzcamos entre la tarjeta y el terminal a un intermediario al que llamaremos Doctor Maligno (DM). Este maligno hace dos cosas. Por un lado, instruye a la tarjeta para que no verifique el PIN que se acaba de teclear en el terminal. Por otro, indica al terminal que el PIN es válido, sea cual sea éste, ya que no tiene más que decirle "0x9000" para tener la luz verde.

El cogollo del asunto consiste en que, si el proceso de verificación no ha sido completado correctamente, la información que recibe el banco incluye un código que indica cuál fue el problema: el PIN no coincidía, o se intentó validar mediante PIN más de tres veces, o bien no se introdujo PIN alguno. Pero, y aquí está el detalle, si la verificación fue llevada a cabo con éxito, el banco NO tiene forma de saber cuál fue el método de verificación. Lo único que le consta es que desde el terminal dijeron "OK, adelante".

¿Y cómo se inserta al "intermediario" en el sistema?. Los investigadores de la Universidad de Cambridge usaron el siguiente sistema. Primero, la tarjeta falsa, que se introducirá en el terminal lector; segundo, un tablero FPGA, que hace de interfaz con un PC; tercero, ese mismo PC; cuarto, un lector de tarjetas; quinto, una tarjeta "buena". Lo que hace el PC es hacer de telefonista entre la tarjeta buena y la chunga. Sólo actúa en la etapa de verificación anteriormente descrita, enviando el código 0x9000 cuando llega el momento. En un ataque maligno real, el hardware necesario puede miniaturizarse mucho más, hasta llegar al tamaño de los aparatos que usan los criminales para leer y copiar datos de las bandas magnéticas.

Es decir: la tarjeta no verifica nada, el terminal cree que sí se ha introducido el PIN correcto, y el banco paga obediente. En caso de disputa, el cliente tiene las de perder, ya que su recibo indica claramente "Verificado por PIN", en cuyo caso el banco aplica la máxima de "en caso de duda, la culpa es del cliente"

No se trata de un ataque teórico. Según los autores del estudio, "contactan con nosotros, de forma regular, clientes bancarios que sufrieron transacciones fraudulentas poco después de que les robaran la tarjeta, que declaran que no escribieron en ninguna parte su PIN, pero que a pesar de eso el banco les acusa de negligencia y rehúsa cubrir las pérdidas. El ataque que describimos aquí puede explicar algunos de esos casos"

Los autores indican diversas causas para explicar esta vulnerabilidad. En primer lugar, la cortedad de miras. Tanto el vendedor como el banco necesitan tener una visión global de los resultados relativos a la verificación del usuario, lo que incluye saber qué método de autenticación se utilizó. No informar al banco de dicho método es lo que permitió el ataque de intermediario aquí descrito. En segundo lugar, el protocolo EMV fue diseñado en un proceso externo, sin revisión externa. Y uno de los mandamientos de la seguridad, como ya sabemos, es "no confiarás en seguridad mediante oscuridad".

En tercer lugar, tenemos el aspecto puramente económico. Los bancos no tienen ningún incentivo para mejorar el protocolo EMV, ya que han conseguido que la responsabilidad en caso de fraude recaiga sobre otros, sea el usuario, sea el vendedor.

Y, por supuesto, también entra el juego la complejidad del sistema. Los protocolos principales de EMV ocupan ya 706 páginas, con otras 2126 páginas de documentación para hacer pruebas, y eso sin contar las especificaciones particulares para las tarjetas (Visa ha publicado 810 páginas al respecto, y se sospecha que hay muchas más páginas que se mantienen en secreto). De hecho, hay muchos detalles que no se especifican en absoluto. Lo raro es que un protocolo tan extenso y complejo no tenga más vulnerabilidades ocultas. En opinión de los autores, EMV está fundamentalmente enfocado como sistema de compatibilidad y como "caja de herramientas" para protocolos. Pero seguir todas las especificaciones sólo nos garantiza que el sistema funciona; nada dice sobre si funcionará de forma segura.

Los autores no son optimistas sobre posibles soluciones. Aunque ellos mismos sugieren algunas modificaciones técnicas, creen que cualquier solución pasa por un esfuerzo conjunto entre vendedores y bancos (y estos últimos no están muy incentivados para hacerlo), y que puesto que seguramente hay más sorpresas escondidas en el protocolo EMV, quizá sería mejor cambiarlo por otros que funcionan de forma más fiable, como el TLS.

Lo increíble de todo este asunto es que la vulnerabilidad "Fish´n Chips" se conoce desde al menos 1999. Las consecuencias jurídicas pueden ser enormes. Ahora que un artículo técnico ha demostrado la vulnerabilidad del protocolo EMV al margen de lo que el usuario haga por garantizar la seguridad (guardando el PIN de forma segura, por ejemplo), los bancos ya no podrán culpar automáticamente al cliente de cualquier mal uso de las tarjetas.

Asi que, querido lector, si usted tiene una de esas tarjetas con chip y PIN, le sugiero se lea atentamente el contrato, y si incluye alguna cláusula del tipo "esta tarjeta es ultrasegura, por lo tanto cualquier fraude será culpa suya", no estaría de más una charla con su abogado.

Y no se olvide enviarme una copia de la cláusula, me gustaría echarle un vistazo. Ignoro cuántos bancos han dado el paso chip+PIN, pero sé que en Octubre de 2009 BBVA anunció que cambiaría todas las tarjetas de sus clientes por tarjetas EMV en un par de años. Según la publicidad de su página web, "[La] tarjeta incorpora un chip con tecnología EMV que te aportará mayor seguridad en todas tus operaciones y que dificultará su uso en caso de robo o extravío." Por lo menos, parecen reconocer que la seguridad es mayor, pero en ningún caso completa. Algo es algo.

 


 

 TEMAS DE ACTUALIDAD - El ataque "Fish'n Chips": actualización a la española

 

Cuando el anterior artículo "El ataque Fish`n Chips" estaba ya redactado, se ha hecho pública una sentencia del Tribunal Supremo español, según la cual resultan abusivas ciertas cláusulas bancarias. Hasta ahora, se imponía al consumidor la carga de probar que el PIN ha sido revelado a un tercero bajo fuerza o coacción. Esa exoneración automática de responsabilidad por parte del banco ha sido declarada abusiva y por tanto nula. Este párrafo nos interesa especialmente:

"... Cierto que con la utilización del chip electrónico en lugar de la tarjeta con banda magnética, y el necesario marcaje o tecleo del número secreto por el titular, cabrá reducir (en las operaciones con presencia física; otro tema lo constituyen las realizadas a distancia, como sucede con internet) las utilizaciones indebidas, pero respecto del caso que se examina no cabe desconocer la posibilidad de captaciones subrepticias, con independencia de otras manipulaciones varias a causa de las deficiencias del sistema de tarjetas..."

A partir de ahora, los bancos no pueden escurrir el bulto automáticamente, puesto que se reconoce la existencia de técnicas para obtener subrepticiamente el PIN, como las "captaciones subrepticias" (lease keyloggers y fauna similar), o esas "otras manipulaciones varias a causa de las deficiencias del sistema de tarjetas," que reconocen implícitamente la debilidad de un sistema falible; especialmente cuando, según el Supremo, "es notorio que, en ciertas circunstancias, las entidades bancarias pueden advertir utilizaciones indebidas empleando la diligencia que les es exigible en armonía con su experiencia y medios técnicos."

(Tribunal Supremo, Sala de lo Civil, Sentencia Nº 702/2009, disponible en www.elmundo.es/documentos/2010/02/18/sentencia.pdf)

 


 

 TEMAS DE ACTUALIDAD - Redes eléctricas inteligentes

 

Siguiendo nuestra línea editorial sobre artefactos que jamás imaginaríamos que llevan cripto ni falta que les hace, hoy vamos a dar el salto a una aplicación con un gran potencial en el futuro: los contadores de la luz.

Servidor es de los que les desearía que las compañías eléctricas utilizasen los contadores de la luz para contar la luz. Parece una tontería, pero imaginen ustedes la cantidad de contadores eléctricos que hay en un país. Como son del tipo "pase usted y lea", las eléctricas tienen que controlarlos en persona, lo que significa que cada dos meses envían revisores a leerlos y facturar a partir de ahí. Eso implica un gran gasto en personal, por no hablar de los problemas derivados del acceso a los contadores (no hay nadie en el chalé, la comunidad los guarda bajo llave y nadie sabe quién tiene copia, el pueblo está muy lejos, etc). El resultado es que, entre fallos de lectura, ausencias del revisor, estimaciones de consumo y demás faenas, tenemos que encomendarnos al oráculo de Delfos para saber qué hemos consumido y cuándo.

La solución lógica es leer los contadores online. Basta con sustituirlos por nuevos sistemas que indiquen automáticamente a la compañía cuánto hemos consumido. El problema evidente es el de logística, ya que sustituir millones de contadores no es una cosa que se hace de la noche a la mañana.

Las ventajas serían múltiples. El cliente tendría la seguridad de que le están cobrando lo que realmente ha gastado, y no sólo lo que alguien estime según quién sabe qué parámetros. También le permitiría optimizar el consumo. Imagínense, por ejemplo, una tarifa que variase en función de la potencia consumida. Un contador inteligente podría incluso "avisar" a la red doméstica de cuándo es más rentable usar los aparatos electrodomésticos. De esa forma, los electrodomésticos de mayor potencia (como lavadoras, lavavajillas o estufas eléctricas) podrían ponerse en marcha en el momento que fuese más barata la electricidad.

En cuanto a la empresa, le ayudará a reducir el fraude, le permitirá ahorrarse millones en personal (lo siento por los revisores de contadores, pero habrán de reconvertirse o ir al paro), e incluso les permitirá ajustar mejor la oferta a la demanda. Las medidas del consumo de todos los hogares les permitirían conocer mejor la potencia consumida en tiempo real, y ajustar el precio de la electricidad según suba o baje la demanda. En caso de sobrecarga, podrían incluso ordenar a los contadores que apagasen los aparatos de gran potencia de consumo, lo que siempre resulta más agradable a la gente que un apagón generalizado.

Por supuesto, siempre habrá inconvenientes. La información demasiado detallada puede alentar a las compañías eléctricas a subir las tarifas de forma injusta. Digamos que los contadores de todo el país indican una gran subida a las nueve de la noche porque hay final de la Champions. ¿Qué mejor momento para subir el precio del kilovatio-hora? Eso ya se podría hacer hoy, pero los contadores inteligentes permitirían hacerlo de forma más ágil y eficaz.

Otros problemas son más insidiosos. Conocer nuestros hábitos de consumo eléctrico dice muchas cosas sobre nosotros mismos. Los períodos sin apenas consumo indican que no estamos en casa, lo que sería información útil a los amigos de lo ajeno o a un gobierno que decidiese gravar económicamente los pisos vacíos. Analizando los picos de consumo, un investigador hábil podría llegar a deducir cuánto tiempo pasamos en casa, a qué hora nos sentamos a cenar, cuántas horas dormimos, si comemos sano o usamos demasiado el microondas, si tenemos niños, cuántas veces salimos a comer fuera. No me gustaría que nadie conociese tantos datos sobre mí, y mucho menos mi empresa de electricidad. ¿Y qué pasa si el gobierno, en plena paranoia ecológica, decide que no puedo poner el aire acondicionado más de dos horas al día en verano? ¿Podrán desconectarme la corriente si me paso de la cuota asignada? No suele pensarse demasiado en esos problemas, pero son graves y han de estudiarse a fondo.

Sin embargo, creo que los contadores digitalizados son la ola del futuro. Representan muchas ventajas para las compañías eléctricas, también para los consumidores, y por supuesto para una sociedad preocupada por la ecología, que tendrá en estos aparatos una herramienta para gestionar el flujo de electricidad de manera más eficiente. En los Estados Unidos, el paquete de estímulo a la economía impulsado por el presidente Obama incluye miles de millones de dólares en incentivos a las empresas eléctricas para el despliegue y uso de contadores inteligentes.

Y ahora la parte técnica negativa. Siempre que hay aparatos electrónicos que se comunican, debemos considerar la posibilidad de que un tercero no autorizado se dedique a poner la oreja, o aún peor, a intervenir en la conversación. Malo es que el ladrón del barrio se entere de que llevo tres días fuera de casa (ocasión perfecta para reventarme la puerta y robarme el Picasso). Peor sería que mi ex-novia, que es tan inteligente como rencorosa, pudiera trastear mis lecturas eléctricas. Si pudiera reprogramar el contador, podría cambiarme a la tarifa más cara, o por el contrario podría bajarme tanto la potencia consumida que yo no podría ni encender una bombilla, una "denegación de servicio" muy original.

Ya hay pruebas de concepto. El pasado verano, en la Black Hat de Las Vegas, Mike Davies, presentó una charla sobre posibles técnicas de ataque: desbordamiento de búfer, rootkits, software malicioso, etc. La mayoría de los "contadores inteligentes" no usan ningún tipo de cifrado, pero hay algunos que sí lo hacen. Vamos a fijarnos en uno de ellos, y como de costumbre, aprovecharemos la oportunidad para aprender.

Una de las empresas que fabrican chips capaces de ser usados como medidores electrónicos a distancia es Texas Instruments (TI). Algunos de sus microcontroladores, como el CC2430, cumplen un conjunto de protocolos llamado ZigBee, diseñado para aplicaciones que requieren comunicaciones seguras con baja tasa de envío de datos y maximización de la vida útil de sus baterías (wikipedia dixit). Entre otras cosas, los chips de TI implementan una librería que produce números aleatorios para general claves. El problema es que dichos números aleatorios no son tan aleatorios. Veámoslo en el artículo que sigue.

 


 

CRIPTO 101 - LFSR y pseudoaleatoriedad

 

El problema de la generación de números aleatorios es tan antiguo como el de la creación de algoritmos de cifrado sólidos. Los humanos no tenemos problemas en crearlos, ya que por definición somos impredecibles. Lanzar una moneda al aire entraña tantas variables (desde la velocidad inicial de rotación a la densidad del aire), que nunca sabemos si saldrá cara o cruz. Por el contrario, un ordenador funciona mediante pasos lógicos perfectamente definidos, y obtener números aleatorios es una tarea extremadamente difícil. Todo lo más que se puede hacer es intentar obtener números pseudoaleatorios, es decir, números que se obtienen siguiendo un patrón definido pero que a primera vista parecen sacados al azar.

La situación puede compararse a bajarar cartas. Podemos diseñar un algoritmo de barajado, por ejemplo, este que se me acaba de ocurrir:

1) Dividir la baraja en tres montones de 11, 16 y 13 cartas (usaré aquí la baraja española de cuarenta naipes)

2) Coger el montón que estaba en medio y ponerlo encima

3) Coger el montón que estaba abajo y ponerlo encima

4) Repetir los pasos 1 y 2 mil quince veces.

¿Por qué 11, 16, 13 o 1015? Sencillamente, porque son los primeros números que se me pasaron por la cabeza. No tienen nada de especial, y valdrían cualesquiera otros. El resultado será un montón de cartas aparentemente bien mezcladas, sin que parezca haber relación alguna entre una carta y la siguiente. El problema es que, si alguien ejecuta el mismo algoritmo en otro ordenador, obtendrá al final una baraja exactamente igual de barajada que la mía.

El problema de generar números aleatorios, como digo, no es sencillo. Y los criptógrafos necesiten un buen generador aleatorio utilizan para generar claves criptográficas que no puedan ser adivinadas. Uno de ellos es un bicho llamado LFSR.

LFSR significa algo así como "registradores lineales de retroalimentación lineal" (Linear Feedback Shift Registers). Es un caso particular de los FSR, es decir, los registradores generales (no lineares). La idea es, en principio, sencilla. Supongamos un FSR de n bits. Eso significa que partimos de un "registro" o paquete de n bits. En la primera "vuelta de manivela", descartamos el último bit y creamos uno nuevo. Ese nuevo bit es una función de los demás bits del registro. El proceso se repite todas las veces que queramos, y los números aleatorios vendrán más o menos dados por esos nuevos bits. aleatorios. El "más o menos" dependerá de la función que utilicemos para crear los nuevos bits.

Voy a inventarme un FSR de cuatro bits, para ilustrar la idea. Partamos del valor inicial 1111. Voy a definir mi función de la siguiente forma: si el número de cuatro bits, pasado a base decimal, representa un número primo, el nuevo bits será uno; de lo contrario, será cero.

En la primera iteración, partimos de 1111, que es el número 15 en notación decimal. Quince es primo, así que eliminaré el último bit (el 1 de la derecha), y añadiré un 0 a la izquierda. Paso así del 1111 al 0111. Ahora 0111 es el número 7, que es primo. Por tanto, fuera el 1 de la derecha, dentro un nuevo 1, y pasamos de 0111 a 1011. Como 1011 es el número 11, que es primo, toca poner un nuevo uno. Así, nuestro FSR pasa por los siguiente estados, o dicho en el lenguaje del ramo, registros:

        Registro     Valor     Nuevo    Registro
        anterior     decimal    bit      nuevo
         1111          15        0        0111
         0111           7        1        1011
         1011          11        1        1101
         1101          13        1        1110
         1110          14        0        0111
         0111           7        1        1011
         1011          11        1        1101

De esa forma, los nuevos bits van dando la serie de bits pseudoaleatorios 0,1,1,1,0,1,1, ... un momento, quietos todos. ¿No notan algo raro? Si se fijan ustedes, el tercer registro (1011) es igual que el séptimo. Eso hace que la serie se repita a intervalos regulares. De hecho, si siguen ustedes dando vueltas a la manivela, verán que este FSR irá repitiendo la secuencia 1011 indefinidamente. !Pues menuda birria de generador pseudoaleatorio!

En mi descargo, debo decir que no soy criptoanalista profesional, y de hecho, el criterio para crear este FSR ha sido el primero que se me ha pasado por la cabeza. No importa, porque así puedo remarcar un hecho importante que ya he dicho anteriormente: crear una secuencia pseudoaleatoria es muy difícil. Pruebe vd. a inventar la suya propia, y lo comprobará.

En general, incluso una FSR perfectamente bien definida se repetirá cada 2^n veces. Es inevitable, ya que cada estado consta de n bits. Tarde o temprano, volveremos a crear un registro de n bits que ya haya salido antes, y a partir se repetirán los registros anteriores uno tras otro. Como mucho, podemos intentar escoger una función que no me repita antes. En el ejemplo anterior, lo ideal sería que la secuencia de cuatro bits se repitiese cada 16 (2^4) vueltas de manivela. Yo lo he conseguido en sólo cuatro, debo haber roto un récord.

Particularizando en el caso que nos ocupa, un LFSR es un FSR cuya función se basa en la suma XOR de algunos bits del registro. La operación XOR (Exclusive-Or) adopta el valor 0 si ambos bits son iguales, y 1 si son distintos. Un LFSR que "xorease" (y discúlpenme por el palabro) los bits 1 y 4 del registro, partiendo del registro inicial 1111, nos daría la siguiente secuencia de registros:

    1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1101, 1110, 1111, ...

La secuencia pseudoaleatoria formada por el último bit (el izquierdo) de cada registro nos da: 101011001000111 que tiene quince bits. No está mal, teniendo en cuenta que solo contamos con registros de cuatro bits para jugar. El valor inicial del registro, en nuestro caso 1111, no determina la longitud de dicha secuencia pseudoaleatoria. Es decir, sea cual sea el estado inicial, ese LFSR siempre tendrá la misma serie de 15 bits que se repetirán una y otra vez. Ahora bien, si lo único que queremos es una secuencia de 15 bits aleatorios, ya nos vale.

De hecho, para cada valor del estado inicial, la secuencia comenzará de forma distinta. En el caso anterior, obteníamos 101011001000111. Si el registro inicial hubiera sido, digamos, 1001, la secuencia habría sido 100011110101100. Evidentemente, son la misma repetición. Pero supongamos que queremos sólo cinco números para crear una clave, y digamos que esos números serán los cinco primeros bits de la secuencia. Con un valor inicial 1111, nuestra "clave" sería 10101, pero con el valor inicial 1001, la clave será 10001. Es decir, lo que obtenemos depende tanto de la forma que tiene el LFSR como del valor que tenga el registro inicial. Interesa, por tanto, que dicho registro inicial sea también lo más aleatorio posible.

En el ejemplo que hemos mostrado, el LFSR se considera ideal, ya que los registros de 4 bits engloban todos los posibles, desde el 0001 hasta el 1111. El 0000 lo descartamos, ya que cualquier XOR con 0 y 0 nos dará siempre cero, de modo si uno de los registros es el cuádruple cero, todos los bits que salgan de la máquina serán cero. Y es evidente que la secuencia 000000000... es poco aleatoria.

De ese modo, en el caso ideal, un LFSR con n bits nos dará una secuencia pseudoaleatoria formada por hasta (2^n)-1 bits. Si eso sucede, se dice que es un LFSR de período máximo, y la secuencia de bits que arroja se denomina "secuencia m". El ejemplo de LFSR que acabamos de ver es un ejemplo máximo de cuatro bits. La secuencia m, de 2^4 - 1 = 15 bits, es 101011001000111.

¿Ventajas del LFSR? Básicamente, nos da una secuencia de números que no son aleatorios que pueden dar el pego, a partir de un conjunto de bits pequeño. ¿Inconvenientes? Bastantes. Los LFSR son susceptibles a ataques criptoanalíticos, que son especialmente eficientes debido al carácter lineal del generador. El llamado algoritmo de Berlekamp-Massey puede generar un LFSR a partir de un conjunto de bits de la secuencia generada. Por ese motivo, un LFSR no se considera un generador de bits aleatorios criptográficamente seguro.

Y con esto, volvemos a Texas Instruments y sus microchips. A finales de 2009, Travis Goodspeed analizó el modo en que dichos chips incorporan cripto. Su generador de números pseudoaleatorios utiliza un LFSR de 16 bits, lo que en principio nos dará una secuencia de hasta 65.535 bits, suficiente para crear muchas claves.

El primer problema consiste en que, como dijimos anteriormente, la forma de la secuencia depende del registro inicial. De ahí la zmportancia de que dicho registro sea lo más impredecible posible. Como el CC2530 es un chip para comunicaciones inalámbricas, lo que hace es usar las señales de radio que recibe (que se supone son aleatorias) para generar el registro inicial. Sin embargo, el estudio de Goodspeed demuestra que los datos que recibe distan mucho de ser aleatorios. Aunque el chip toma el bit menos significativo de esas señales (algo así como fijarse, no en el valor de la señal, sino en si esa señal es un número par o impar), Goodspeed afirma que puede forzarse una señal exterior que nos de un valor predecible para el registro inicial, lo que en parte se debe a la forma tan sencilla como el chip procesa el valor de esas señales. O dicho de otro modo, el valor inicial del registro deja de ser aleatorio.

Personalmente, lo veo un problema menor y fácilmente subsanable. El segundo problema, no obstante, permanece: el LFSR no es un generador pseoduoaleatorio fiable. Como hemos dicho antes, el algoritmo de Berlekamp-Massey nos permite generar todos los valores de una secuencia, generada por un LFSR, a partir de un conjunto de bits de dicha secuencia. Pero es que, incluso si no supiésemos de la existencia de dicho algoritmo, seguimos teniendo una secuencia que se repite tarde o temprano.

Digamos que ponemos la oreja, escuchamos parte de la secuencia, y lo que oímos es 1011 Eso no nos dice nada acerca de qué vendrá después, ya que en promedio uno de cada 16 conjuntos de cuatro bits será 1011. Es decir, en promedio, 1011 tenderá a aparecer unas cuatro mil veces a lo largo de la secuencia (estamos considerando un LSFR de 16 bits). Sin embargo, algo del tipo 10110010111 sólo aparecerá unas treinta veces, y una secuencia concreta de más de 16 bits será difícil que aparezca más de una vez. Esto significa que, si en el pasado he captado la secuencia 0010111101011010110101010111, la próxima vez que yo capte la secuencia 00101111010110101101010101, ya sé que tengo todas las papeletas para que los siguientes bits sean 11.

Eso nos da una posibilidad de alterar la medida del contador, puesto que conocer la secuencia pseudoaleatoria nos permite cifrar o alterar la información que se transmite a la central eléctrica, en el caso, claro, de que el chip se utilice en un contador eléctrico.

En descarga de Texas Instruments, hemos de decir que han reaccionado bien y rápido. El fallo, que se encuentra no tanto en el chip como en una implementación de software, está siendo corregido. Ojalá todos los fabricantes reaccionasen así de bien. Pero el problema de generar números aleatorios criptográficamente seguros seguirá siendo un hueso duro de roer, no sólo en este caso sino en general.

Como dicen que dijo von Neumann, "cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en estado de pecado." ¿Dónde aparecerá el próximo pecador?

 



El boletín ENIGMA es una publicación gratuita del Taller de Criptografía, y se rige por las normas de la licencia de Creative Commons Reconocimiento-NoComercial-CompartirIgual. Se permite su libre copia, distribución y comunicación para fines no lucrativos, citando nombre y referencia.

Para más información, véase la licencia Creative Commons en sus formas reducida y completa:
http://www.cripto.es/licencia/deed.es.htm
http://creativecommons.org/licenses/by-nc-sa/2.5/es/legalcode.es

PARA DARSE DE ALTA: envíe un mensaje a la dirección alta arroba cripto.es añadiendo las palabras alta_enigma en el asunto (subject).

PARA DARSE DE BAJA, envíe un mensaje a la dirección baja arroba cripto.es añadiendo las palabras baja_enigma en el asunto (subject)

Para comentarios a este boletín (dudas, preguntas, consultas, críticas, noticias, colaboraciones, etc.), estoy a su disposición en la dirección noticias arroba cripto.es

Página del Boletín Enigma (incluyendo números atrasados): http://www.cripto.es/enigma.htm

(c) Arturo Quirantes 2007

 


Vuelta a la Página principal del Boletín ENIGMA