Por sqrmatrix

Me he leído la patente del nuevo sistema de origen español que fue noticia hace unos días, y he visto algunos fallos, que expongo a continuación:

• Se afirma que "no es nada fácil descubrir y almacenar números primos suficientemente grandes". Quizá me equivoque, pero a mí me parece que esta afirmación es totalmente falsa. Por no decir que habla de que no disponemos de una fórmula matemática que genere números primos, pero no menciona que disponemos de métodos fiables que nos permiten obtener todos los números primos que queramos de la longitud que queramos de forma casi inmediata, o si queremos una mayor seguridad de que sea primo, tarda unos minutos.
• Se afirma que en la parte de las claves tenemos una cardinalidad Aleph-0 o mayor, pero que yo sepa, teóricamente ningún criptosistema puede tener una cardinalidad mayor a Aleph-0, y en la realidad, el espacio de claves siempre será finito.
• Se afirma que el número de ordenaciones de la matriz base es (mxn)!, cuando en realidad es m!xn!. Es decir, que en el ejemplo que pone de (27x27)!=729!~68x10^1770, en realidad es 27!x27!~1.19x10^56

Además se quiere convencer al lector, de manera indirecta, de que los demás sistemas son inseguros, lo cual a mí me parece que es mucho suponer.

En mi opinión, el algoritmo general es un algoritmo demasiado complejo, con demasiadas variables y demasiados pactos entre los interlocutores, lo que hará difícil la compatibilidad entre diferentes usuarios. También, el alto grado de expansión del tamaño de la información lo veo inaceptable. No le auguro ningún futuro, pero sí muchas críticas, como las que ya está teniendo aquí.

En lo que voy a exponer a continuación, espero no haberme equivocado. Si no, que alguien me corrija...

Como primera vulnerabilidad del algoritmo que se describe, veo lo siguiente. Antes, decir que esto se basa en lo indicado en el documento de la patente, pero el ejemplo que ponen no parece cumplir la fórmula. No sé si la fórmula indicada está mal, o el ejemplo indicado está mal. De ser cierta la fórmula, se tiene la vulnerabilidad que aquí explico.

Si tenemos un índice de protocolo j comprendido entre 1 y 3, sabemos que el número generado será R+Ax(10^(j-1)-1). Sabemos que R puede tomar los valores entre 1 y 9, y lo mismo con A. Así, pues, si j=3, tenemos que R+Ax(10^(3-1)-1)=R+Ax99. Esto supone un número limitado de valores, a saber, {100-108}U{199-207}U{298-306}U{397-405}U{496-504}U{595-603}U{694-702}U{793-801}U{892-900}. Es decir, si nos encontramos en el criptograma una secuencia de 3 números que no está en ninguno de esos conjuntos, tenemos la seguridad de que esa secuencia no pertenece a un índice de protocolo j con valor 3, o sea, que esos tres dígitos no codifican un dígito del mensaje. Podría codificarse con el primero de ellos, o los dos primeros, o los 4, 5, etc, pero no con esos tres. En caso de encontrarnos uno de esos valores, no tenemos ninguna seguridad de que codifiquen un dígito.

Por otro lado, en caso de que determinemos que uno de estos grupos de 3 dígitos efectivamente sí codifica un dígito del mensaje, podemos obtener directamente el valor de R, que vendrá dado por la suma del dígito más significativo con el menos significativo. En este caso, el valor aleatorio de A no aporta ninguna seguridad.

Por último, para este caso, suponiendo que haya al menos un índice de protocolo j igual a 3, y suponiendo que los índices de protocolo se repiten cíclicamente y no son demasiados (relativamente hablando), podemos obtener con probabilidad alta todas las cifras de 3 posiciones que codifican un dígito del mensaje. Para ello, buscamos todos los grupos de 3 dígitos que entren en uno de los conjuntos indicados (hay que buscarlos todos, es decir, si tenemos ...10895..., aquí tenemos el valor 108 y el valor 895) Una vez hallados todos estos grupos, realizamos el siguiente algoritmo: empezamos por el primer grupo, y buscamos el siguiente. Hallamos su distancia "d", y ahora, comprobamos todos los grupos que distan "d" partiendo del primero. Si todos ellos son grupos que caen dentro de los conjuntos antes especificados, es muy probable que todos ellos sean los valores generados por índices j de valor 3. De no ser así, repetimos el proceso, pero esta vez con el primer grupo y el tercero, ya que el segundo falló. Si haciendo todo esto no encontramos ningún caso en el que se cumpla que todos los valores pueden ser generados por un índice de protocolo j de valor 3, entonces reanudamos todo el proceso, pero esta vez partiendo del segundo grupo de 3, ya que el primero falló. Es decir, cogemos el segundo grupo de 3 dígitos y el tercero. Hallamos su distancia, y vemos si todos los grupos de 3 a distancia "d" partiendo del segundo grupo pertenecen a los conjuntos antes indicados. Y así sucesivamente. Si de ninguna forma encontramos ninguno de estos conjuntos, entonces bien no hay ningún índice de protocolo j igual a 3, bien estos índices no son cíclicos.

Si hemos encontrado uno de estos índices, que se repite a una distancia "d", no debemos descartar que haya otros, por lo que debemos seguir buscando, eso sí, saltándonos los que ya hemos encontrado. Si los encontramos, lo más probable es que su distancia sea "d", pero puede ocurrir que hayamos encontrado una configuración especial, como la siguiente: {2,3,6,3,1,3}. Siendo cíclica, tendríamos la secuencia 2,3,6,3,1,3,2,3,6,3,1,3,.... Traducido a dígitos, nos queda AABBBCCCCCCDDDEFFFAABBBCCCCCCDDDEFFF.... En ésta, aplicando el algoritmo, obtendríamos, por un lado, una distancia "d" de 9, que se corresponde a los índices 3 consecutivos dentro de la secuencia, pero por otro lado, descubriríamos una distancia secundaria de "d" de 18, no coincidente con la anterior. Para que esto ocurra, necesariamente la distancia menor ha de ser divisor de la distancia máxima hallada. Podría ocurrir que la secuencia de distancia menor esté dentro de la secuencia de distancia mayor en cuyo caso no podríamos determinar la secuencia mayor, pero bastaría ir probando secuencias de distancia múltiplo la que tenemos. En todo caso, si nos encontramos con varias secuencias no coincidentes, la longitud de la secuencia real será la de distancia mayor, o un múltiplo de ésta.

Halladas todas estas distancias, podemos saber la longitud total de la secuencia, en dígitos, antes de repetirse, y conocemos en qué posiciones están los índices de protocolo j de valor 3. Conocidos estos valores, podemos dividir el mensaje en bloques que sabemos que han sido codificados con los mismos índices de protocolo j, y también conocemos los índices de protocolo j de valor 3 que, como hemos visto, nos permiten saber el valor de R.

Visto esto, podemos seguir avanzando en el análisis, ahora que hemos reducido la complejidad del sistema. Ahora podemos averiguar la longitud del resto de bloques. Sabemos que si tenemos un bloque de 4 o más dígitos, sus dos últimos dígitos están fijados por el resto por la fórmula indicada en el algoritmo. Así, pues, nos situamos en el primer bloque, y cogemos el primer grupo de 4 dígitos. Para determinar la longitud de un grupo, suponemos que es de 4 dígitos. Comprobamos si los dos últimos dígitos cumplen las fórmulas. Si es así, hacemos lo mismo para el mismo grupo, pero en el siguiente bloque, y repetimos la operación para todos los bloques. Si en algún bloque no se cumple, sabemos que la longitud no es de 4, así que suponemos que es de 5 y repetimos. Si para una determinada longitud "l" se determinan los dos últimos dígitos para los mismos grupos de todos los bloques, es muy probable que la longitud del bloque sea ésa y hayamos determinado el valor de un índice de protocolo j. Si hemos alcanzado la máxima longitud permitida y no se ha cumplido en todos los bloques la determinación de los dos últimos dígitos, entonces es que estamos ante un bloque de 1 ó 2 dígitos. Como podemos estar ante un bloque de 1 dígito, lo que hacemos es repetir este proceso, pero empezando por el siguiente dígito, si tenemos a continuación 4 o más dígitos libres. En caso de haber pasado al siguiente dígito y haber encontrado un bloque de 4 o más dígitos, está claro que el dígito que hemos saltado es un bloque de longitud 1. Si hubiéramos saltado 2 ó más dígitos, de momento no podemos saber qué bloques son de 1 dígito y qué bloques son de 2 dígitos. Este procedimiento nos permitirá determinar algunos, o todos, los índices de protocolo j. Habiendo determinado estos bloques, podemos determinar el valor de R utilizando la fórmula dada.

En caso de no encontrar bloques de 3 dígitos, o en caso de que lo indicado anteriormente sea erróneo, podemos seguir aplicando este último ataque. Es simple. Obtenemos todos los posibles bloques de 4 ó más dígitos siguiendo el procedimiento indicado antes. En este caso, partimos de los primeros 4 dígitos y comprobamos si los dos últimos son generados por los anteriores. De ser así, lo anotamos, pero seguimos probando con más dígitos. Anotamos todos los posibles bloques, hasta llegar al máximo. De no haber ninguno, está claro que estamos ante un bloque de menos de 4 dígitos. Pasamos al siguiente dígito, y repetimos. Al final, obtendremos todos los posibles bloques. Unos serán válidos, otros no. Ahora, aplicamos el algoritmo de antes, pero con los datos que tenemos. Partimos del primer bloque, buscamos el siguiente de la misma longitud (que no se solape con éste, por supuesto), determinamos su distancia "d", y vemos si, partiendo del primer bloque, todos los bloques del mismo tamaño a distancia "d" son válidos. De ser así, es muy probable que todos sean bloques válidos. Si no es así, el bloque que estamos tratando no es válido. Pasamos al siguiente y repetimos. Este procedimiento deberá dar como resultado una secuencia de bloques que no se solape y que se repita (hablando en longitudes), que juntos formarán el bloque de índices de protocolo j, o un subloque de longitud un divisor de la longitud del bloque principal. En este punto, tendremos varios índices de protocolo j, o todos (los bloques de tamaño inferior a 3 podrían estar indeterminados en algunos casos). Como antes, podemos determinar el valor de R con la fórmula dada.

Creo que esto es un punto de partida para hacer el criptoanálisis, pero no creo que la cosa quede sólo en esto. Seguramente haya más fallos.

Por supuesto, esto que he expuesto no permite descifrar el mensaje, pero es un punto de partida para el ataque, y muestra que este sistema es más vulnerable de lo que afirma su autor. En particular, el cifrado por índices de protocolo es bastante vulnerable.

Bueno, espero no haberme equivocado en nada ni haberos aburrido.