Steganography

Seguridad de la Información y Criptografía
Homework 8 - Images

Here are my images, three of them with the hidden code that I used.

Download original files in a zip

Try to find the images with the code hidden. Good luck!

Estabilidad

Automatización y Control de Sistemas Dinámicos
Programa 1

Para esta semana la tarea a realizar fue un programa que determinara si una función de transferencia, en este caso la de nuestro proyecto para la clase, se considera estable o inestable, de acuerdo a análisis mediante octave.

El proyecto para esta clase trata de modular el nivel de sonido en un altavoz, que depende del ruido en la habitación.

Uno de los métodos que use para analizar si mi función de transferencia tiene estabilidad o no fue el Criterio de Routh-Hurvitz, pero debido a que octave no cuenta con un paquete especifico para obtener la tabla de valores que resulta de este criterio, use un modulo de código libre en la siguiente página.

Modulo de criterio Routh-Hurvitz

Simplemente lo que hace este modulo es regresar los cuantos cambios de signo hubo en la primer columna de la tabla de Routh, y la tabla en sí. La cual es de gran ayuda para el análisis de estabilidad de esta tarea.

Mi código es el que muestro enseguida. Resumiendo lo que hace, al inicio se inicia la función de transferencia predeterminada, que es la que corresponde al proyecto en el que trabajo, según lo que se entrego en los reportes anteriores, también es posible mandar una función de transferencia cualquiera para analizar otras funciones.

Luego mediante el análisis de las raíces y el criterio de Routh, se determina si es inestable o no, y se manda una impresión. Al final se crean algunas gráficas que explico al final.


Cuando le mandamos como parámetro el valor de "None", toma la función de transferencia predeterminada, podemos ver la ejecución de este código en seguida.

octave:1> estabilidad('None')
****************************
* Funcion de transferencia *
****************************

Transfer function 'funtrans' from input 'u1' to output ...

      0.001358 s^2 + 5.5 s + 11
 y1:  -------------------------
       0.0001235 s^3 + s^2 + 1 

Continuous-time model.
****************************
*         Analisis         *
****************************
Raices en el denominador:
r =

  -8.1000e+03 + 0.0000e+00i
   6.1728e-05 + 1.0000e+00i
   6.1728e-05 - 1.0000e+00i

* Analizando las RAICES *
Hay partes reales positivas en las raices.
Por lo tanto el sistema es INESTABLE
* Criterio de Routh-Hurvitz *
tabla =

   0.00012   0.00000
   1.00000   1.00000
  -0.00012   0.00000
   1.00000   0.00000

Hay 2 cambios de signo.
Por lo tanto el sistema es INESTABLE

Lo que nos arroja en una de las gráficas es la función escalón de la función de transferencia dada.

También obtenemos el diagrama de Bode, que según la segunda gráfica indica que la función llega a un punto a donde tiende a infinito, lo cual nos dice que el sistema es inestable, ya que para poder ser estable, debería de haber estado acotado entre un rango especifico de valores, en cambio si graficaramos cada vez en un rango de frecuencia mayor, solo veríamos que la línea sigue subiendo.

Por último use lsim para ingresar "ruido" a la función de transferencia en un tiempo determinado. Puse valores obtenidos con la función de seno para ver que efecto causa.

Podemos ver nuevamente una función que sigue en el infinito conforme avanza en el tiempo, igual que la deducción anterior, se puede decir que el sistema es inestable.

Justificación de por qué es inestable el sistema
El sistema modula el volumen de los altavoces dependiendo de si existe ruido en la sala o no, pensemos en que inicialmente se reproduce música a cierto volumen, entonces si el sistema detecta ruido y en base a eso aumenta el volumen, seguramente su propia salida este entrando al sistema como ruido y provoque el aumento en volumen, por eso en las gráficas podemos ver un incremento en la amplitud.

Referencias:
Guardar gráficos de octave
Funciones del paquete control en Octave

Grafo de Programa

Verificación y Validación de Software
Entrada 9

Para esta semana se nos pidió que modeláramos un sistema simple y lo representáramos mediante un sistema de transiciones o un grafo de programa, y opcionalmente crear la representación en PROMELA.

El sistema que modele para esta semana es muy simple. Se trata de la máquina donde se paga el pasaje en el Transmetro.

Descripción:
En el transporte "Transmetro" cuando un pasajero aborda el camión debe de ingresar la cantidad de $4.50 en la máquina. Una vez ingresada tal cantidad, se imprime un boleto con un código de barras. Esto se hace para evitar hacer doble pago al llegar a la estación, ya que con el mismo boleto del camión es posible subir al Metro.

Tomando en cuenta la máquina que recibe el dinero e imprime lo boletos, modele el sistema, que como podemos ver es muy simple, ya que solo consiste en una máquina que espera el ingreso de monedas, este esta contando el total, y cuando se tiene ya 4.50 en la máquina, se imprime un boleto. También hay que tomar en cuenta que no regresa cambio.

Por ser algo simple de entender, me pareció más práctico dibujar el sistema directo a un grafo de programa.

De la forma en que yo lo modele, supongo que desde que la máquina es encendida inicializa una variable para contar y otra que dice de cuanto fue la moneda. Hay un bucle al que entra inmediatamente después de esto, donde se espera a ingresar una moneda y se suma a la cantidad actual, y no se sale de ahí hasta que el total sean 4.50. Después de salir se imprime el boleto y se resta 4.50 al total, para regresar de nuevo al estado donde se espera el ingreso de monedas.

Es posible que el trabajo de esta máquina no sea secuencial sino que sea algo de forma paralelizada, por un lado la parte que toma las monedas, y por otro la que imprime el boleto. Esto se puede ver cuando un grupo de personas sube al camión, y solo una persona se encarga de depositar el dinero de todos en la máquina. La máquina no necesita que el usuario deje de meter monedas para poder imprimir los boletos, sino que cada que sobrepasa la cantidad de $4.50 imprime un boleto y resta la misma cantidad del total.

Entonces podemos verlo como dos tareas independientes de la siguiente forma.

Contador de monedas
Impresión del boleto

Representación PROMELA

PROMELA (Process/Protocol Meta Language) es un lenguaje de modelado de verificación. El lenguaje permite la creación dinámica de procesos concurrentes de un modelo, por ejemplo, los sistemas distribuidos. En modelos PROMELA, la comunicación a través de canales de mensajes puede ser definido para ser sincrónico o asincrónico. Un modelo escrito en PROMELA se puede analizar con el comprobador de modelos SPIN, para verificar que el sistema modelado produce el comportamiento deseado. [1]

Instalar SPIN en Ubuntu

1. Descargar la versión más reciente y compatible con tu sistema del ejecutable Spin. En mi caso he descargado el archivo spin622_linux64 para Linux.

Spin Precompiled Executables

2. De forma opcional es posible descargar un complemento gráfico para ejecutar y depurar el código. Aquí descargue el archivo ispin.tcl, que solo requiere de tener instalado el paquete tk8.4.

Spin Sources

3. Si no tienes instalado el paquete tk8.4, o no estas seguro de si ya lo tienes ejecuta el siguiente comando, si no esta instalado te pedirá tu aprobación para iniciar la instalación, en caso contrario te dirá que no es necesario instalar ningún paquete extra.

~$ sudo apt-get install tk8.4

4. Ahora vamos a la carpeta donde guardamos los archivos descargados y copiamos el ejecutable a la carpeta /usr/bin/ con el nombre de spin.

~$ cd Downloads/promela/
~$ sudo cp spin622_linux64 /usr/bin/spin

5. Para abrir la interfaz gráfica, estando en la carpeta donde tenemos guardado nuestro archivo ejecutamos la siguiente instrucción.

~$ wish ispin.tcl

6. Si quieres correr tus programas desde terminal solo es necesario ejecutar la siguiente instrucción, donde hello.pml es el nombre del archivo donde tienes tu código.

~$ spin -n2 hello.pml

Regresando al grafo de programa que mostré anteriormente, y basado en él, escribí un código sencillo de como debería trabajar este pequeño sistema, para luego probar desde interfaz gráfica. Para probar tome en cuenta que se ingresan siempre monedas de un peso y que la tarifa de la máquina es de 5 pesos.


Usando Spin desde interfaz gráfica es posible generar un diagrama desde el código escrito y su ejecución.

Ahora lo mismo, pero modelado como dos tareas independientes, incluyendo las líneas de skip, para uso de exclusión mutua, donde se accede a la variable "x".


Si corremos directo en terminal, podemos observar lo siguiente, que no es más que la ejecución de los dos procesos. Esto es solo una sección, ya que al correr el programa los procesos están en ejecución de forma infinita.

One coin introduced
One coin introduced
One coin introduced
One coin introduced
One coin introduced
    Ticket printed
One coin introduced
One coin introduced
One coin introduced
One coin introduced
One coin introduced
    Ticket printed

Podemos verificar el programa desde interfaz gráfica, y nos dará información acerca de nuestro programa. Nos da información acerca de cuantos estados y transiciones se crearon, si existe error alguno en la ejecución, la cantidad de memoria y procesos creados, etcétera.

Referencias:
[1] - Promela - Definición
Spin on Linux
Promela Model
Model Checking

Stream Ciphers: Edon80

Seguridad de la Información y Criptografía
Homework 7 - Report 3

Edon80 is a stream cypher algorithm designed by Danilo Gligoroski, Smile Markovski, Ljupco Kocarev, and Marjan Gusev. [1]

Has some strengths: [2]

1. If the needs for security bits have to be increased to arbitrary value, the speed of the cipher would not be affected at all (except initialization phases).
2. If the size of IV change, it would not affect the speed of the cipher.
3. It is easily paralelizable.
4. For achieving high speeds, it is appropriate only for a hardware realization to utilize its more then 80 pipeline and parallel operations.

Edon80 is a hardware binary additive synchronous stream cipher. It belongs to a family of stream ciphers that in hardware can have a constant speed of one bit per clock cycle, but in software implementation on popular modern CPUs can be made as slow as needed.

Since its first description in 2005, it has been analyzed by several cryptographers, have been implemented in a more compact way and a MAC functionality have been added. [3]

How it works?

Edon80 is a binary stream cipher. The keystream in Edon80 is generated as a row of a certain in fnite matrix whose elements are defi ned iteratively using quasigroup operations.

The stream cipher Edon80 uses four fixed quasigroups of order 4. The four quasigroups are the next:

But, why use only that quasigroups or are the unique. In fact, we can generate a different quasigroup if we want, but a quasigroup has a special way to be created, and there are some that are not good for generate a random stream in our case.

In Edon80 we use a quasigroup with a dimension of 4x4, so every row and col need to have a 0, 1, 2 and 3, filled in a table like when we play sudoku. We only need four quasigroups, so the crucial part of this method, was select that quasigroups of a set of 576 options. There are 192 quasigroups and are called fractal quasigroups, since they produce highly regular strings.

Some of the rest 384 after every application of an e-transformation increase the period of the transformed string with smaller coefficient, and other by higher coefficient, and those was discarded. We give a list of 64 quasigroups that increase the period of the transformed string at least 2 times, after every application of an e-transformation by them. For select the four quasigroups of the set of the 64 remaining, each one of them was tested and was found the best four options.

Now we have the general model of the stream cipher Edon80. A key and a Input Vector are required for generate a output stream.

For its proper work Edon80 has the following additional inputs:

1. One register key of 80 bits to store the actual secret key.
2. One register IV of 80 bits to store padded initialization vector.
3. One internal 2-bit counter as a feeder of Edon80 Core in keystream mode.
4. One 7 bit SetupCounter that is used in IVSetup mode.
5. One 4 × 4 = 16 bytes ROM bank where 4 quasigroups of order 4 are stored.

In the first row of that table we placed a periodic string that has shape: 01230123[...]0123. The next 80 rows in the table describe 80 e-transformations of that string by using the obtained values of $a_i$ in input vector mode and by the quasigroups $∗i$. The recurrence equations for this transformations are:

The output of the stream cipher is every second value of the last e-transformation so the keystream can be described as:

Using the source code of the official web page of Edon80, I executed a simple example, but I reduced the length of the keystreams:

Generated Key = 04000000000000000000
Generated IV = 0000000000000000
Keystreams generated (3x20 bytes)
s[1]=4E3E5646183CDB17561B8536812775D95D713E69
s[2]=8C67697FD96A249D5E794242413EBEA6B552CC08
s[3]=C61DABCB6AA8E0E50FC5B6392B8549C2F7CBF07B

Encryption of 20 bytes
Plaintext = F4604512C52C03158686A84DF32139B143755F04
Ciphertext = 4E3E5646183CDB17561B8536812775D95D713E69

Decryption of 20 bytes
Ciphertext = 4E3E5646183CDB17561B8536812775D95D713E69
Plaintext = F4604512C52C03158686A84DF32139B143755F04

Attacks and vulnerabilities

Is difficult to attack this kind of stream cipher. Experts found that the complexity of the attack is around 2^69 simple operations for a keystream of similar length. So if we want to attack we have a possibility to found the keystream, but with a brutal force algorithm it will take a very long time.

Another attack and a vulnerability is founded like in others types of encryption and is about the base of explore some periodicy inside the generator.

Using the fact that some elements will repeat with large probability, we can build a kind of test to find out the correct value of the key bits used at the end of the concatenation. We can use it to find a part of the keystream, and is why this kind of stream cipher has a vulnerability.

References:
[1] - Edon80 - Wikipedia
[2] - The eSTREAM Project
[3] - Edon80 Properties
A Key Recovery Attack Of Edon80

Redes Petri: Sistema Concurrente

Verificación y Validación de Software
Entrada 8

La entrega para esta semana consistió en lo siguiente:

• Investigar sobre las redes Petri.
• Inventar un pequeño sistema concurrente.
• Modelar un sistema con una red Petri y correrlo en Python.

¿Qué es una red de Petri?

Las redes de Petri son una herramienta gráfica para modelar sistemas formales que pueden ser descritos en términos de pasos en una actividad: como los procedimientos legales, procesos industriales, recetas y algoritmos. Los diseñadores industriales pueden usarlos, ya que son lo suficientemente generales como para la mayoría de los problemas y proporcionan un modelo para la programación. [1]

Una red de Petri es una representación matemática o gráfica de un sistema a eventos discretos en el cual se puede describir la topología de un sistema distribuido, paralelo o concurrente. La red de Petri esencial fue definida en la década de los años 1960 por Carl Adam Petri. Son una generalización de la teoría de autómatas que permite expresar un sistema a eventos concurrentes. [2]

Una red de Petri está formada por lugares, transiciones, arcos dirigidos y marcas o fichas que ocupan posiciones dentro de los lugares. [3]

Las reglas son:

• Los arcos conectan un lugar a una transición así como una transición a un lugar.
• No puede haber arcos entre lugares ni entre transiciones.
• Los lugares contienen un número finito o infinito contable de marcas.
• Las transiciones se disparan, es decir consumen marcas de una posición de inicio y producen marcas en una posición de llegada.
• Una transición está habilitada si tiene marcas en todas sus posiciones de entrada.

Modelar un sistema

El sistema que decidí modelar fue el de las máquinas que hay en las gasolineras, en mi caso hice una versión simple, ya que el sistema completo requiere de más estados y transiciones que las que yo usé.

Lo que tome en cuenta para el sistema fue lo siguiente:

• La máquina se encuentra en reposo hasta que es accionada.
• El personal indica cual es la cantidad de gasolina a expedir.
• Se selecciona el tipo de gasolina, que puede ser la premium o magna.
• La máquina verifica si hay disponible el tipo deseado.
• Si no hay disponibilidad, muestra un mensaje de agotado.
• Si hay disponibilidad, empieza el llenado.
• Al final vuelve al estado de espera nuevamente.

El siguiente es un dibujo creado previo a modelar el sistema en python, y muestra una idea general de como fluye el sistema.

Modelar la Red Petri con Python

Para modelar el sistema en python, fue necesario hacer uso de la librería python-snakes, que es posible descargar desde el siguiente sitio.

Python Snakes

Snakes es una librería de python que nos proporciona todo lo necesario para definir y ejecutar muchos tipos de redes Petri. Su objetivo es tener al alcance una herramienta para crear prototipos rápidamente para nuevas ideas.

Unos de los puntos a resaltar de esta librería es la extensión de plugins, que permite ampliar funciones básicas y trabajar con clases especializadas en redes Petri. Por ejemplo, están los plugins usados para dibujar las redes de Petri en sus diferentes formas y exportarlos como imágenes.

El modelo de la imagen mostrada anteriormente fue escrito con las funciones que python-snakes proporciona, y el código fue el siguiente.


Este código al final crea las diferentes representaciones posibles de la red Petri, aquí deje solo dos de las cinco generadas, que son las que en este caso muestran de una forma más organizada la red.

La siguiente parece más ordenada y es más parecida al modelo del sistema que cree con la herramienta de dibujo.

Recursos consultados:
[1] - Petri Nets
[2] y [3] - Definición de Redes Petri
Python Snakes - Google Code
Python Snakes - API
Franck Pommereau's Blog

Bloque Ciphers: OFB - Output Feedback

Seguridad de la Información y Criptografía
Homework 6 - Report 2

The Output Feedback (OFB) mode is a confidentiality mode that requires a unique initialization vector for every message that is ever encrypted under the given key. [1]

The Federal Data Encryption Standard (DES) specifies a crypto-graphic algorithm to be used for the cryptographic protection of sensitive, but unclassified, computer data. This FIPS defines four modes of operation for the DES which may be used in a wide variety of applications. The modes specify how data will be encrypted and decrypted. The modes included in this standard are the Electronic Codebook (ECB) mode, the Cipher Block Chaining (CBC) mode, the Cipher Feedback (CFB) mode, and the Output Feedback (OFB) mode. [2]

This standard is based on the DES and provides the next level of detail necessary for providing compatibility among DES equipment. This standard anticipates the development of a set of application standards which reference it such as communication security standards, data storage standards, password protection standards and key management standards. Cryptographic system designers or security application designers must select one or more of the possible modes of operation for implementing and using the DES in a cryptographic system or security application. [3]

The Output Feedback mode was created by Computer Systems Laboratory and the standard was registered by the National Institute of Standards and Technology.

Difference between the others

The Output feedback has some similarities to the ciphertext feedback mode in that it permits encryption of differing block sizes, but has the key difference that the output of the encryption block function is the feedback, instead of the ciphertext. The XOR value of each plaintext block is created independently of both the plaintext and ciphertext. It is this mode that is used when there can be no tolerance for error propagation, as there are no chaining dependencies. Like the ciphertext feedback mode, it uses an initialization vector. Changing the IV in the same plaintext block results in different ciphertext.

How it works?

The kind of mathematics that this method use is XOR operation, and is the reason why we use the same operation to encrypt and decrypt.

$C_j = P_j \oplus O_j$
$P_j = C_j \oplus O_j$
$O_j = E_k(I_j)$
$I_j = O_{j-1}$
$I_0 = IV$

How to encrypt:

http://upload.wikimedia.org/wikipedia/commons/a/a9/Ofb_encryption.png

How to decrypt:

http://upload.wikimedia.org/wikipedia/commons/8/82/Ofb_decryption.png

We can see in the images that each output feedback block cipher operation depends on all previous ones.

Example

This is a simple example of the output feedback implemented in a python script.

ramon@pavilion:~/Documents$ python outputfeedback.py 
Text: me gusta la clase de cripto
Key: abcdefgh
IV: 12345678
Block size: 8

Block #1
Input block: 12345678
Output block: rtvxz| "
Plaintext: me gusta
Ciphertext: a[vaqqtc
Decrypted: me gusta

Block # 2
Input block: rtvxz| "
Output block: UX[^adgj
Plaintext:  la clas
Ciphertext: UF>^FRJ_
Decrypted:  la clas

Block # 3
Input block: UX[^adgj
Output block: 8<@DHLPT
Plaintext: e de cri
Ciphertext: }<&+H1D?
Decrypted: e de cri

Block # 4
Input block: 8<@DHLPT
Output block: y %*/49>
Plaintext: pto
Ciphertext: +05:?&//
Decrypted: pto

Text: me gusta la clase de cripto

What I did in my program?

• First my program divide the text in blocks.
• Then, I use the Input Vector only for the first iteration to get the output block using the key.
• Using the output block, I encrypt the text block.
• I get the encrypted text block.
• In this case, I used the encrypted block text to decrypted at the same time, but it must be separately.
• Then I use the last output block, for the new input block, and repeat the last steps, until we don't have more text blocks.
• At the end, I print all the decrypted text block together.

Vulnerabilities

In terms of error correction, output feedback can tolerate ciphertext bit errors, but is incapable of self-synchronization after losing ciphertext bits, as it disturbs the synchronization of the aligning keystream. A problem with output feedback is that the plaintext can be easily altered, but using a digital signature scheme can overcome this problem.

References:
[1] - Block Cipher Modes of Operations
[2] [3] - Standard for DES - Modes of Operation
Definition - Output Feedback
OFB - Examples

Aplicación de la Lógica Predicativa

Verificación y Validación de Software
Entrada 7

La lógica predicativa tiene un amplio rango de aplicaciones, y yo he seleccionado para esta publicación el tema de procesamiento del lenguaje natural.

El procesamiento del lenguaje natural, es un campo que se ha venido desarrollando prácticamente desde los inicios de la informática. Lo que se busca en este campo es hacer preguntas al ordenador y recibir respuestas útiles, o dándole órdenes que la computadora actúe de forma razonable. Por ser una aplicación que hace un tiempo era tal vez muy difícil de imaginar en la realidad, ha aparecido en la ciencia ficción muchas veces.

Actualmente los sistemas encargados del procesamiento del lenguaje natural, han hecho uso de lenguajes de programación con amplia experiencia en este ámbito, como lo es el reconocido uso de Prolog, como un lenguaje lógico que puede llegar a una respuesta al darle una serie de predicados que son ciertos o falsos, en ciertas circunstancias.

¿Cómo es el procesamiento del lenguaje?

Lo que se necesita primeramente para lograr el procesamiento del lenguaje natural es romper el texto capturado como una estructura de oraciones, mediante estructuras lógicas, con el fin de un posterior análisis.

Suele ser difícil la parte del procesamiento, debido a que se tratará con una cantidad grande de información, y esta en base al contexto en que se este hablando, es posible entrar en una serie de ambigüedades que hagan difícil llegar a una solución o resultado.

También el procesamiento depende mucho del lenguaje en el que se aplique, por lo que se suelen utilizar una serie de diccionarios, de los cuáles podamos hacer uso para dar significado lógico a una oración procesada por el sistema.

Pueden ser utilizados para proporcionar retroalimentación auditiva en un sistema automatizado de comprobación de precios en un supermercado o para leer en voz alta una previsión del tiempo que cambia frecuentemente.

El proceso por el que pasa un texto requiere de un análisis que ha de descomponerse en estructuras que el sistema pueda procesar, y luego diferenciarlo en cierto tipo de unidades específicas de información.

La forma de entender como se estructura la entrada de información, es tal y como se hace en la lógica de predicados, de ahí que esta aplicación surge de este tema, ya que se realiza un árbol en el que se estructuran los predicados, hasta llegar a unidades lógicas pequeñas que sea posible evaluar como si fuesen funciones.

La siguiente imagen muestra el procesamiento que hace el sistema al que hace mención el PDF anexado al final de esta publicación como recursos consultados, donde los creadores de el sistema de procesamiento de lenguaje natural utilizan esta misma metodología para analizar la información.

Y ahora es necesario trasladar esas unidades elementales al sistema como si fuesen parámetros a evaluar, una forma de visualizar como se mandaría la entrada de datos al sistema computacional encargado de evaluar la información o texto, se vería de la siguiente manera.

La respuesta de salida, puede determinar si una oración o texto tiene coherencia en cuanto al contexto en el que se estaba hablando, o determinar una serie de acciones a realizar por un sistema.

Recursos consultados:
A Natural Language Interface Using First-Order Logic, Andrews, Itz and Meyer
Logic Predicate - Chapter 4