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
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
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