jueves, 13 de noviembre de 2014

El arte de la esteganografía

Muchos autores han definido a la esteganografía como el arte de ocultar información [1], con el cual se tiene como propósito intercambiar información por un medio sin que se revele la existencia de dicha información. Es diferente de la criptografía, ya que en dicha área lo que se busca es hacer ilegible un mensaje, aunque no le es posible ocultar información.

La esteganografía moderna se inspira en archivos binarios [2], cada archivo de una computadora es una secuencia de bytes que a su vez es una secuencia de bits. Pero antes de empezar a hablar de la esteganografía, me gustaría explicar que són los bytes y los bits.

viernes, 31 de octubre de 2014

Repositorio de claves RSA y firmas digitales


Antes que nada, recomendaría leer mi entrada anterior acerca de RSA para entender un poco de cómo funciona esto.

Un repositorio, de acuerdo a la Real Academia de la Lengua [1], es un "Lugar donde se guarda algo." Siguiendo esa descripción, un repositorio de claves o llaves criptográficas se puede definir como un lugar donde se guardan claves para ser consultadas en cualquier momento.

En esta entrada describiré una aplicación desarrollada en Python que actúa como un repositorio casero de claves RSA, con el que no sólo se puede consultar las claves registradas en un servidor, sino que también proporciona una interfaz para cifrar y descifrar archivos de texto.

Enlace a GitHub de la aplicación.

domingo, 12 de octubre de 2014

Autenticación por medio de RSA

RSA es un algoritmo [1] de generación de llaves públicas, creado por Ron Rivest, Adi Shamir y Leonard Adleman. Es famoso por ser muy fácil de entender e implementar, además de que las llaves generadas con este algoritmo pueden utilizarse para encriptar y firmar mensajes.

jueves, 18 de septiembre de 2014

Diffie-Hellman key agreement

Diffie-Hellman protocol.


Chinese remainder theorem

Exponenciación modular

Algoritmo de Euclides y algoritmo extendido de Euclides

Factorización de un número

Test de primalidad

viernes, 12 de septiembre de 2014

The importance of randomness in security

Randomness is an important topic for a great number of persons, from scientists to philosophers, because of many questions around it. Although it's not obvious to many people, randomness is present in many aspects of our lives, like in videogames, simulations and even in security [1]. The latter is to main focus in this essay, because randomness is very important in various techniques related to safe activity in computer based information systems, such as in Internet browsing or in the use of cash machines.

What makes a number to be a random number?

For many mathematician and scientists, random numbers must be unknowable and unpredictable. This numbers also should pass many statistical test of uniformity [2], such as the chi-squared test or the Kolmogorov-Smirnov test.

The security in a cryptographic system (hereafter the cryptosystem) is strongly related to techniques that require random sequences for many different purposes [3]. One of the most important elements in cryptography are the cryptographic keys which determine the transformation of the plaintext into ciphertext and vice versa. Considering many of this algorithms are publicly known, the security in a cryptosystem is dependent on how the keys are managed, generated, transmitted, stored and destroyed.

Pseudo-Random Number Generators

In this point one can assume that random numbers are very important for many different reasons, but another question arises, how to generate good random numbers? In practice Pseudo-Random Number Generators (hereafter PRNG) are used, which are algorithm that generate pseudo-random numbers [4]. A PRNG works when an initial value is given to the algorithm as a seed, which ideally must be truly random [3], for generate a new number.

The core components of a PRNG are [4]: an internal state which consists of all the parameters, variables and other stored values that the PRNG uses for its operations, and the entropy source which is the source of randomness (seed) to update said internal state.

Usually the entropy sources come from changes in the physical environment of the device [7], such changes in the temperature, changes in the voltage or frequency of the power supply, exposure to radiation, etc. Many modern operating system, like Linux [6], have a PRNG implementation, where their entropy source comes from to the aforementioned sources and other sources, such as keystroke, mouse clicks, disk I/O.

If it is very difficult to access to a hardware entropy source, it is recommend to obtain random input from a large of uncorrelated sources and to mix them with a strong mixing function [5]. This function should preserve the randomness present in any of the sources even if other quantities are easily guessable.

Security notions in a PRNG

In security there is a notion about adversaries [4]: there are those who have access to the output of the generator, those who can control (partially or totally) the source of the generator and those who can control (partially or totally) the internal state of the generator, or any combination of them. Various standards define several desirable security properties of a PRNG [4] involving this notion of the adversary:
  • Resilience: an adversary must not to be able to predict future PRNG outputs even if he can influence the entropy source.
  • Forward security: an adversary must not to be able to predict future PRNG outputs even if he can compromise the internal state of the PRNG.
  • Backward security: an adversary must not to be able to predict past PRNG outputs even if he can compromise the internal state of the PRNG.
  • Entropy preservation [6]: the generator must preserves the entropy of the internal state after the output and refresh operations, in other words, the entropy must not to decrease.
In the Barak and Halevi PRNG model they define a new security property called robustness [4] that implies the aforementioned properties. This property actually assesses the behavior of a PRNG after compromise of its internal state [8], implying that even an observer with knowledge and control of the components of the PRNG can not distinguish the output of the generator from an endless string of random bits.

So, randomness is very important, right?

I think that because the today massive exchange of information, it is good have a bit of paranoia regarding about our security. For this very reason the security in the communication channels is so important to many people, because their personal, private information can be compromised if it is accessible to malicious people.

Maybe it is funny when a friend play a joke to us, but I don't think that it would be funny if someone “plays” with confidential information which it must be secret to almost everyone. Specially if it is regarding money or something very personal, of course.

References

[1] Jon Callas, "Using and Creating Cryptographic-Quality Random Numbers", 1996. https://www.merrymeet.com/jon/usingrandom.html
[2] Banks, Carson, et al, "Discrete-event System Simulation". https://cs.wmich.edu/~alfuqaha/Spring09/cs6910/lectures/Chapter7.pdf
[3] Márton, Suciu, et al, "Generation and Testing of Random Numbers for Cryptographic Applications", 2012.. http://www.acad.ro/sectii2002/proceedings/doc2012-4/11-Suciu.pdf
[4] Dodis, Pointcheval, et al, "Security Analysis of Pseudo-Random Number Generators with Input: /dev/random is not Robust". https://eprint.iacr.org/2013/338.pdf
[5] Eastlake, Crocker, Schiller, "Randomness Recommendations for Security", 1994.. http://www.hjp.at/doc/rfc/rfc1750.html
[6] Ruhault, "Barak-Halevi pseudo-random number generator model extended with applications to /dev/random". http://webmath.univ-rennes1.fr/c2/Soumissions_C2/c2_Ruhault.pdf
[7] Barak, Shaltiel,Tromer, "True Random Number Generators Secure in a Changing Environment". http://www.math.ias.edu/~boaz/Papers/trng.pdf
[8] Barak, Halevi, "A model and architecture for pseudo-random generation with applications to /dev/random", 2005. https://eprint.iacr.org/2005/029.pdf

miércoles, 20 de agosto de 2014

Cifrado XOR y One-time pad


El método de cifrado XOR es un método que, como su nombre lo indica, utiliza el operador lógico XOR. El operador XOR devuelve 1 (o verdadero) siempre y cuando sólo uno de sus entradas es igual a 1, en caso contrario devuelve 0 (o falso).

La tabla de verdad del operador XOR para dos entradas quedaría así:


En el caso que se utilice este operador para dos cadenas binarias, se aplica el operador XOR para cada bit de las dos cadenas, resultando en una nueva cadena binaria, como se muestra en la siguiente imagen.


Este operador es muy útil en Criptografía, pues imaginemos que la cadena binaria A es el mensaje, la cadena binaria B es la llave y C = A XOR B es el mensaje criptado. Si se desea recuperar el mensaje original, sólo es necesario aplicar el operador XOR para la cadena C y la cadena B, por lo que resulta que A = C XOR B.

Si bien este método es muy sencillo de implementar también es cierto que es fácil de atacarlo, en especial si la llave siempre es la misma. Para evitar este problema el concepto de One-time pad (libreta de un sólo uso) viene muy bien al caso, ya que son como una especie colección de llaves aleatorias que dos usuarios comparten.

Imaginemos que tenemos dos usuarios, Alice y Bob y que se ha generado un one-time pad de 10 llaves y los dos tienen una copia de este one-time pad. Cada vez que un usuario envía un mensaje al otro, se encripta el mensaje utilizando una llave de su propio one-time pad, para proceder a eliminar dicha llave de su libreta. Luego, el receptor recibe el mensaje criptado y lo recupera utilizando la llave de su propia copia del one-time pad, procediendose a eliminarse dicha llave de la libreta del receptor. Nótese que la llave en ambos operaciones  siempre es la misma, aunque está almacenada en dos lugares distintos. En este ejemplo el proceso de comunicación se podría repetir hasta 10 veces, que es el número de llaves disponibles para los dos usuarios, y en teoría, si se utiliza llaves verdaderamente aleatorias es prácticamente imposible romper la seguridad de un sistema que implemente one-time pad.

Se implementó en Python una especie de sistema one-time pad, que consiste en dos programas principales: un generador de llaves pseudoaleatorias y un programa que encripte y desencripte mensajes. Antes de continuar, es necesario mencionar que nuestras llaves y nuestros mensajes pueden contener símbolos alfanuméricos, por lo que es necesario consentir un "protocolo" para trabajar únicamente con números, en mi caso decidí trabajar con números Unicode, es decir, el número entero que representa un caracter en Unicode. Entonces ya que queda claro que todos los caracteres de mis llaves y mensajes se pueden representar como números, procedo a mostrar un pequeño ejemplo de esto.






Para generar llaves pseudoaleatorias es necesario mandar como argumentos el número de llaves a generar así como el tamaño de las mismas.. Para empezar con "la comunicación" es necesario que existan los archivos de llaves para los dos usuarios y también un archivo de texto que contenga texto cualquiera, el cual va a ser nuestro mensaje original. En el programa de encriptación, por tanto, se manda como argumentos los nombres del archivo que va a servir como el mensaje y también los nombres de los archivos que contienen las llaves. Ya que esto es una simulación de como se podría implementar one-time pad, la desencriptación del mensaje lo realiza en automático, mostrando en pantalla el contenido del mensaje original.

Los resultados se muestran a continuación.




Referencias:

domingo, 10 de agosto de 2014

ROT13

ROT13 es un método de cifrado simple, en el que las letras de un mensaje son remplazadas por la letra que se encuentra trece posiciones después de la misma en el abecedario.

Ya que este método trabaja con el abecedario, para convertir una letra en su equivalente en ROT13 es necesario conocer su posición y sumar trece, así se encuentra la posición de la letra que se utilizará para encriptar la original. Así, la letra A (1) se convierte en N  (14), la letra B (2) se convierte en O (15), la letra M (13) se convierte en Z (26), etcétera.

El método se puede ver de dos maneras: si son las primeras trece letras, se suman sus posiciones, y si son las últimas trece, se restan. Pero también es posible auxiliarse del módulo, por ejemplo, la letra U está en la posición 21 del abecedario, su suma sería 34, que claramente no existe. Para "dar la vuelta" al abecedario es necesario conocer el residuo entre la suma y el número total de letras. Así pues, ya que 21 cabe una vez en 34, "sobra" 8, es decir, la letra cifrada sería H. De esa manera es posible realizar la operación de una manera práctica y directa. Dado a que estamos sumando la mitad del número de letras en el abecedario, eso quiere decir que se puede implementar una sóla función en ROT13 que trabaje para cifrar y decifrar el contenido de los mensajes.


Además de que es un método muy conocido, y por eso mismo poco fiable, existe una razón por la que es fácil romper la seguridad de un mensaje cifrado en ROT13, y es conocer la frecuencia en la que aparecen las letras del abecedario en el texto. Es decir, si sabemos que la letra E (5) aparece con más frecuencia en el idioma inglés, ¿no es fácil deducir que la letra R (18) se encontrará más veces en un texto cifrado con ROT13?

A pesar de que hay muchas fuentes que está de acuerdo en la distribución de las frecuencias de las letras del abecedario, decidí realizar un experimento con un texto de la Wikipedia para probar esta teoría. Los resultados se muestran a continuación.

Análisis de frecuencia

El programa anterior realiza un conteo de las letras del abecedario en Inglés -que previamente se define en una lista- que aparecen con mayor frecuencia en un texto. El texto se encuentra almacenado en un archivo de texto, al cual es accedido cuando el usuario manda el nombre del archivo como parámetro. Al final el programa guarda en otro archivo los resultados del análisis de frecuencia, en donde cada fila hace referencia a la letra y su correspondiente porcentaje de frecuencia.

El formato en el que se guarda la información no es simple casualidad, ya que si está almacenado de esta manera es más fácil realizar una gráfica de dicha información con el siguiente comando de Gnuplot.



En base a esta gráfica, las letras que más aparecen son la e, a, t, n y o. En cambio, las que menos aparecen son las q, j, x, z, v. Conociendo esa información, eso quiere decir que las letras r, n, g, l y b van a aparecer mucho más que las letras d, w, k, m y i en un texto cifrado con ROT13. El mismo programa fue utilizado en un texto distinto que fue cifrado en ROT13 para comprobar la hipótesis.


Más o menos se puede observar una semejanza, ¿verdad? Si se sospecha tan siquiera que una letra aparece con más frecuencia que otras, este ataque puede acabar rápido con un mensaje cifrado en ROT13.

Además de este pequeño análisis también implementé ROT13 con Python, pudiendo analizar cadenas pequeñas o inclusive textos enteros para luego cifrarlos.