El algoritmo de cifrado que reta a los hackers “revelaed”

http://feedproxy.google.com/~r/ElLadoDelMal/~3/gAMl_H5uGF8/el-algoritmo-de-cifrado-que-reta-los.html

Muchos somos los que hemos pedido un análisis sobre la nueva patente criptográfica que ha salido por todas las noticias a nuestro experto particular en estos lares, Jorge Ramió, así que al final ha optado por escribir junto con el Dr. Alfonso Muñoz un documento en la red Criptored, que os paso a transcribir aquí por lo detallado del análisis.

Primeras impresiones sobre la solicitud de la patente “Procedimiento de
doble criptograma simétrico de seguridad de Shannon por codificación
de información para transmisión telemática y electrónica”

Jorge Ramió Aguirre – Alfonso Muñoz Muñoz

Miembros de la Red Temática Criptored

Madrid, 21 de enero de 2013

1. Introducción

Referencias periodísticas (entre otras):

– El País: Patente valenciana antipiratas- El Mundo: Un físico reta a los ‘hackers’- Documento de la solicitud de patente

El presente escrito pretende dar luz sobre diferentes cuestiones aparecidas en la prensa
nacional (España) el 3 y 17 de enero de 2013, relativas a una patente de un nuevo algoritmo
criptográfico “indescifrable”. Si este breve escrito sirve de guía para evaluar mejor en un futuro
este tipo de sistemas, o servir de referencia a periodistas que han dado una publicidad inusual
a este hecho, los firmantes del mismo se dan por satisfechos.

Este informe viene a petición de diferentes miembros de la red en cuanto a publicar una
opinión, personal que no colectiva de la red, a este respecto. En los últimos días, diferentes
blogs y comunidades de internautas relacionadas con la seguridad de la información se han
expresado y se están expresando también en este sentido, entre ellos:

– Blog de Arturo Quirantes- Kriptópolis

Nota: Ninguno de los miembros ni los editores de la Red Temática de Criptografía y Seguridad de la
Información Criptored, con base en la Universidad Politécnica de Madrid, suele realizar
comentarios sobre la opinión de terceros en cuanto a la ciencia de la criptología, centrándose
su trabajo fundamentalmente en la difusión, y en su caso evaluación y estudio de trabajos
publicados en conferencias, congresos y seminarios científicos, que siguen por tanto un
riguroso proceso de evaluación por terceras partes. No obstante, vemos importante hacer una
excepción en este caso -dada la notoriedad social que esta noticia ha alcanzado- para aclarar
diferentes cuestiones.

2. Comentarios sobre la solicitud de patente en cuestión

A continuación se adjunta una serie de comentarios basados en el estudio de la solicitud de
patente a la que puede acceder desde la dirección ya indicada.

En primer lugar, sin entrar a valorar aún las operaciones que en dicha solicitud indica realiza el
algoritmo propuesto, hay que decir que si todo se limita a operaciones matemáticas lineales –
como así parece ser- (ver el estudio del algoritmo en párrafos posteriores) el sistema tiene
muchas posibilidades de ser inseguro, puesto que una de las máximas en criptografía simétrica
moderna para que los algoritmos sean robustos es la no linealidad de algunas de sus
operaciones.

La redacción de la patente no ayuda mucho en dar credibilidad al algoritmo. Sin ser
exhaustivos, comentar son un par de cuestiones:

Aunque sea muy común en Latinoamérica usar las palabras ‘encriptar’ y ‘desencriptar’ por
influencia directa del inglés, lo cierto es que en lengua española esas palabras no existen y lo
correcto, más aún en un documento oficial, sería utilizar cifrar y descifrar.

Toda la redacción está plagada de afirmaciones sin fundamento, errores de concepto y
diversos errores básicos de lenguajes de programación.

Por ejemplo, en la página 25 (línea 25) se afirma:

“un ordenador actual difícilmente puede operar con exactitud con números enteros de más de
15 dígitos”.

Cualquier lenguaje de programación moderno permite implementar programas que manejen
números de tamaño arbitrario en ordenadores normales. Por ejemplo, en lenguaje Java con la
clase BigInteger.

En cualquier caso, y sólo a modo anecdótico, incluimos a continuación unas cuantas
aclaraciones que el lector puede observar en el documento de solicitud de patente en
cuestión:

1. Sección Descripción, página 1, línea 25:

Afirma:

“… y operaciones bancarias, criptografía de obras musicales y audiovisuales, y firmas”

Aclaración:

No existe la ‘criptografía de obras musicales y audiovisuales’; sí algoritmos
criptográficos que permiten proteger obras musicales y audiovisuales, así como
diversos métodos basados en la criptografía, marcas de agua, etc.

2. Sección Descripción, página 2, líneas 13 y 14:

Afirma:

“Actualmente hay diversos lenguajes de cifrado”

Aclaración:

No existen ‘lenguajes de cifrado’; lo que existe son algoritmos de cifra que se
implementan con uno u otro lenguaje de programación, en el caso de software
criptográfico como lo es el invento que se propone.

3. Sección Descripción, página 2, líneas 15 y 16:

Afirma:

“… o bien como sistema de cifrado asimétrico. Este último es muy seguro”

Aclaración:

Si el algoritmo que se presenta es de tipo simétrico, esta afirmación no es adecuada en
este entorno pues son igual de seguros (o inseguros) los sistemas de cifra simétricos
que asimétricos. Hablar solamente de los asimétricos como ‘muy seguros’ supone
excluir a los primeros, lo cual es un error.

4. Sección Descripción, página 2, líneas 16 y 17:

Afirma:

“… pero no por eso resulta imposible romperlo por el procedimiento llamado fuerza
bruta”

Aclaración:

Los sistemas de cifra asimétricos no se rompen por fuerza bruta, aunque podría
intentarse -si se desea- pero no tiene sentido con la capacidad de cómputo actual.
Existen, no obstante, algoritmos específicos para romper su fortaleza, que está basada
generalmente por un problema matemático tipo NP (exponencial) de costosa solución
computacional cuando los números son grandes, e.g. sobre mil bits, llámese éste
problema del logaritmo discreto, problema de la factorización entera, etc. Los sistemas
de cifra donde es más común usar fuerza bruta -aunque existan otros procedimientos
más elegantes- son los simétricos, nunca los asimétricos. 

En el mundo real los ataques por fuerza bruta son la última solución, porque son los
más costosos. De hecho, en criptografía hay un dicho cuando estamos en el mundo
real: “la criptografía no se ataca, se esquiva”. 

En el mundo real es más fácil obtener una clave almacenada indebidamente,
procesada incorrectamente, usar fallos de programación de los algoritmos
criptográficos, de los sistemas que lo implementan, etc., que atacar al propio
algoritmo de cifrado.

5. Sección Descripción, página 2, líneas 18 y 19:

Afirma:

“… acaban averiguando los números primos a partir de cuyo producto se ha construido
el criptograma”

Aclaración:

El autor supone que como sistema asimétrico sólo existe el algoritmo RSA, que
efectivamente utiliza dos primos grandes cuyo producto es el módulo o cuerpo de
cifra, pero existen otros algoritmos para el intercambio de clave y/o firma digital que
no usan dos o más primos sino solamente uno como es el caso de Diffie y Hellman,
Elgamal, DSA (en este caso dos primos pero en sentido diferente), además de curvas
elípticas, etc. Así mismo no es apropiado afirmar que “a partir de cuyo producto se ha
construido el criptograma”: el criptograma se construye mediante una operaciónmatemática (generalmente exponenciación) donde interviene ese producto, el módulo
o cuerpo de cifra, pero nada más.

6. Sección Descripción, página 2, líneas 19 y 20:

Afirma:

“Y no es nada fácil descubrir y almacenar números primos suficientemente grandes”

Aclaración:

En tanto no especifique el autor qué entiende por ‘números primos suficientemente
grandes’, lo cierto es que existen muchas librerías que permiten encontrar números
primos grandes con total facilidad y rapidez para las necesidades actuales. Además no
se entiende qué quiere decir con ‘almacenar números primos’.

7. Sección Descripción, página 2, líneas 21 y 22:

Afirma:

“… uno de los lenguajes más solventes continua siendo el llamado algoritmo DES”

Aclaración:

Insistiendo en que en este caso el DES jamás ha sido patentado como un lenguaje,
decir que continúa (el acento lo ponemos nosotros) siendo el más solvente significa
remontarnos al estado del arte de la criptografía simétrica antes del año 1997.
Después del DES, existen muchos algoritmos más robustos tanto en diseño como en
longitud de clave, e.g. IDEA, AES. Si se desea hacer una afirmación en ese sentido en
pleno siglo XXI, la elección obviamente es AES.

8. Sección Descripción, página 2, líneas 24 y 25:

Afirma:

“… DES consta de 256 claves, lo que significa que si se dispone de un ordenador capaz
de realizar un millón de operaciones por segundo, se tardarían más de 2.200 años en
probar todas las claves”

Aclaración:

Aunque los cálculos son correctos, es necesario recalcar que estos ataques a sistemas
simétricos permiten un divide y vencerás en red, por lo que hablar en un documento
científico como éste de un solo ordenador con capacidad de cálculo de un millón de
claves por segundo, resulta como poco inapropiado. Ya en el DES Challenge III cuando
se rompió la clave del DES en 1999 en menos de un día, la capacidad de cómputo en
red y con la máquina DES Cracker alcanzó los 250 mil millones de claves por segundo, y
estamos hablando de 13 años atrás.

9. Sección Descripción, página 5, líneas 10, 11 y 12:

Afirma:

“Además la conjunción de muchos ordenadores muy potentes puede romper claves
asimétricas, consideradas largas, en poco tiempo”

Aclaración:

Se están mezclando conceptos de ataques a criptografía simétrica con la criptografía
asimétrica. El trabajo de ‘la conjunción de muchos ordenadores muy potentes’ se
entiende como un trabajo en red, una acción en paralelo. Si el autor conoce soluciones
de ataques en red al problema de la factorización entera o del logaritmo discreto,
debería nombrarlos. Por lo tanto, no se sabe qué ha querido afirmar aquí el autor, y
menos aún dilucidar qué entiende por ‘poco tiempo’.10. Sección Descripción, página 5, líneas 31 y 32 y página 6, líneas 1 y 2:

Afirma:

“Pues bien, todos los cifradores por bloques trabajan con cadenas fijas de n bits a las
que se aplican alternativamente procesos de sustitución en las llamadas S-cajas (Sboxes) y de permutación en las P-cajas (P-boxes)”

Aclaración:

Esto no es cierto. No se puede generalizar las operaciones que se realizan en el
algoritmo DES a todos los demás algoritmos simétricos; es más, no tienen nada que
ver, e.g. IDEA no usa cajas y en AES no se llaman S-boxes.

11. Sección Descripción, página 7, línea 7:

Afirma:

“… mediante la operación or exclusivo byte a byte”

Aclaración:

Aunque está sacado de la referencia del libro de D. Manuel José Lucena, que cita, tal
vez merecería la pena no dejar la sensación de que sólo existe ese tipo de cifra en
flujo. Si bien es cierto que algunos algoritmos de flujo cifran byte a byte, otros
algoritmos lo hacen bit a bit. De hecho, el principio básico de la cifra de flujo (Solomon
Golomb) es la cifra bit a bit.

12. Sección Descripción, página 10, línea 1:

Afirma:

“… cuando conoce las claves que han sido utilizadas para codificarlo”

Aclaración:

Debería haber terminado la frase con la palabra ‘cifrarlo’ y no ‘codificarlo’. Codificar es
algo estático y siempre entrega el mismo valor (código ASCII, código Baudot, código
Morse, etc.), en cambio cifrar es algo dinámico; en función de una u otra clave
utilizada en la cifra, se obtiene uno u otro criptograma. Por esta misma razón no es adecuado usar en el título de esta solicitud de patente la
frase “por codificación de la información” cuando en realidad lo que se quiere decir es
“por cifrado de la información”.

En esa misma página 10 y en las línea 2 y 3, vuelve a insistir en que el único sistema de ataque
a ‘todos’ los sistemas de cifra es la fuerza bruta.

No merece la pena profundizar en sus apreciaciones sobre lo que denomina “criptogramas
seguros de Shannon”, algo inexistente, si bien existe el concepto de cifrado con secreto
perfecto introducido por Shannon, pero son cosas distintas.

No haremos valoraciones sobre afirmaciones tales como que el sistema es inexpugnable
‘incluso’ (página 2, línea 33) para los ordenadores del futuro y otras afirmaciones que aparecen
en el documento como usar la palabra ‘pirata’ (página 9, línea 33) como la persona que
intercepta una comunicación porque sería entrar en el plano personal.

En resumidas cuentas, que no tiene interés seguir con esto. Creemos que queda claro lo que
pretendemos decir; continuemos con la descripción del algoritmo para entender mejor las
conclusiones de esta nota y las recomendaciones.

3. Comentarios sobre el algoritmo presentado

Si hemos entendido bien el algoritmo, lo cual no es sencillo a partir de la redacción, éste podría
resumirse en lo siguiente:

1. Un residuo es un número del 1 al 9. Es posible combinarlo en grupos: 1 al 9, 11 al 99,
111 al 999, etc. 

2. Tenemos una matriz alfanumérica (básicamente representamos los caracteres ASCII en
matriz). 

3. Tenemos una matriz base de residuos numéricos (representamos todos los residuos
posibles en una matriz). Por ejemplo, si estamos trabajando con los residuos desde el
111 al 999 pues los ordenamos en una matriz. 

4. Se necesita una clave de equivalencia Es una clave formada por números naturales. Se
agrupan en parejas e indican qué fila “conmutar” por otra “fila”. 

5. Matriz base de residuos + clave equivalencia = matriz base de residuos ordenadas.
Conmutamos la matriz en función de lo que nos indica la clave, dando lugar a una
nueva matriz. 

6. Construimos una tabla de equivalencias.

a. Extraemos los valores de la matriz alfanumérica y los hacemos corresponder
con uno o más valores de la matriz base de residuos ordenadas.
b. Única condición que no se repitan los valores,

7. Construir plantilla (criptograma reducido)

a. Ponemos el mensaje a cifrar en ASCII.
b. Seleccionamos uno de los posibles valores de la tabla de equivalencia para
cada carácter ASCII a cifrar.

8. Necesitamos una clave de protocolo. Una secuencia de números naturales, cada
número indica el número de dígitos en los que se convertirá cada “carácter ASCII
cifrado (residuo)”. 

9. Define un algoritmo “simple” para asignar valores a los dígitos indicados. No queda
claro cómo es la generación de los números aleatorios indicados.
Y… eso es todo. 

Emisor y receptor necesitan compartir:

1. Clave de protocolo.

2. Clave de equivalencias.

3. La matriz base de residuos (cómo ordenar los residuos en la matriz).En el ejemplo que pone para cifrar “la reunión es mañana jueves” (23 dígitos) el resultado es
de 462 dígitos (20 veces más).

4. Opinión y conclusiones

1. Primer inconveniente del algoritmo.

El autor afirma que una de las bondades de este
algoritmo es precisamente la “expansión” de los dígitos a cifrar, múltiples opciones
entre las que elegir. Esto tiene un problema claro: el texto cifrado es mucho más
grande que el texto en claro. Únicamente por esto se puede afirmar que este
algoritmo no será de utilidad en la práctica. Un algoritmo de cifrado moderno no sólo
debe ser seguro, sino que debe ser eficiente en múltiples aspectos. Los algoritmos
modernos producen, típicamente, texto cifrados del mismo tamaño que el texto en
claro (dejaremos aparte cuestiones de relleno). Un ejemplo es el actual estándar
mundial AES, el cual tiene ciertas propiedades interesantes para su ejecución en
terminales de bajo recursos, almacenamiento, etc.

2. Emisor y receptor necesitan compartir 3 claves.

Es necesario compartir por algún
procedimiento 3 claves (o una que las componga) cuyo tamaño total es mayor que las
claves criptográficas actuales para proporcionar una supuesta seguridad no probada.
El proceso en el que interviene la clave es crítico en cualquier algoritmo simétrico
moderno. La patente no deja claro cómo se debería elegir la clave con unas mínimas
consideraciones de seguridad, es más, en el texto recomienda que incluso emisor y
receptor podrían repetir la clave una y otra vez en el proceso, recordando a algoritmos
clásicos rotos hace siglos. Cómo interviene la clave en el cifrado o cómo se selecciona
no es baladí. Muchos de los algoritmos simétricos utilizan generadores de subclaves
basados en una clave principal que van proporcionando bits de clave según una serie
de condiciones muy estudiadas. La seguridad de estos generadores es crítica para la
seguridad global del algoritmo.

3. La descripción del algoritmo es oscuro y “variable”.

Los algoritmos “serios” describen
una serie de pasos a realizar de manera impermutable. La descripción de este
algoritmo deja abierta la selección de multitud de cuestiones al emisor y receptor; esto
puede introducir problemas.

4. Cualquier algoritmo criptográfico que se precie debe resistir un ataque con texto en
claro conocido

Esto es algo básico y no lo vemos reflejado en el documento. Sin estas
pruebas elementales, ningún algoritmo puede darse por bueno.

5. El algoritmo tiene pinta de mezcla de procedimientos básicos de criptografía clásica.

En ocasiones, recuerda a cifradores por homófonos, en otros casos a cifradores
basados en matrices y transposiciones de sus elementos. En cualquier caso, no queda
claro que los procedimientos establezcan procesos no lineales en los que basar una
seguridad real. Hablando de sistemas de cifra lineales con espacios de claves muy grandes (que parece
ser el fuerte de este sistema), más grandes incluso que los actuales cifradores
modernos que son no lineales, hay que ser muy cautos; e.g. si en el algoritmo de
matrices de Hill se usa una simple matriz de 8×8 y un cuerpo de cifra de todos los
caracteres ASCII imprimibles, se obtiene un espacio de claves válidas exorbitante … pero el sistema se rompe con una simple matriz de Gauss-Jordan y tres o cuatro
palabras del texto en claro y su correspondiente texto cifrado.

6. Si se desea probar la seguridad del sistema es bien sencillo, hay dos opciones no
excluyentes. 

La primera es publicar sus resultados en cualquiera de los congresos o
conferencias científicas de renombre en criptografía, tanto en España como en otros
países, y someter sus resultados a investigaciones independientes. Una segunda, y
aconsejable, liberar una herramienta concreta que implemente su algoritmo y ser
sometido al escrutinio de la comunidad científica e internautas. Si se incentiva a la
comunidad de alguna manera para atacar su sistema, tanto mejor.

Ante todo lo anterior no sólo podemos afirmar que este algoritmo ni mucho menos va a
desplazar a los algoritmos actuales, sino que no le auguramos ningún futuro. Sería conveniente, especialmente para los profesionales del periodismo que difunden este tipo
de noticias en grandes medios, recordar que en España disponemos de excelentes
profesionales, tanto expertos en seguridad informática como criptólogos; a la mayoría de ellos
se les podría consultar antes de publicar noticias sensacionalista como las que nos ocupa.
Atentamente,

Dr. Jorge Ramió

Profesor Titular de la Universidad Politécnica de Madrid. Desde el año 1994 imparte diversas
asignaturas relacionadas con la seguridad y criptografía. Entre sus facetas destaca su interés
por la difusión de la seguridad informática en Iberoamérica. Autor del libro electrónico de
Seguridad Informática y Criptografía en 2006, de libre distribución en Internet y con más de
120.000 descargas, creador en 1999 de la Red Temática de Criptografía y Seguridad de la
Información Criptored, organización de los congresos iberoamericanos CIBSI y TIBETS, creador
y director de la cátedra UPM Applus+ de seguridad, creación y dirección de la Enciclopedia de
la Seguridad de la Información Intypedia y del primer MOOC en español sobre seguridad de la
información Crypt4you, participación como profesor invitado en cursos de posgrado en España
y países de Latinoamérica.

Dr. Alfonso Muñoz

Doctor de Telecomunicaciones por la Universidad Politécnica de Madrid e investigador
postdoctoral en Computer Security & Advanced Switching Network en la Universidad Carlos III
de Madrid. Especialista en protección de datos digitales y diseño de sistemas seguros
(criptografía, esteganografía, dpi, etc.). Ha publicado más de 20 artículos en revistas y
congresos científicos de alto impacto (revisión ciega por pares) en el campo de la seguridad
informática, y ha trabajado en proyectos con organismos europeos, ministerios y
multinacionales. Su trabajo de investigador lo combina con su faceta de divulgación. Algún
ejemplo destacable es la creación y dirección técnica de Intypedia, creación del primer MOOC
en español sobre seguridad de la información Crypt4you, artículos de divulgación en revistas o
blogs del sector o la participación en conferencias de seguridad informática y hacking

Un informático en el lado del mal – Google+ RSS Informática 64 Seguridad Apple

Enviado por gReader

Anuncios
Esta entrada fue publicada en Security. Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s