Steganography Assignment

My 6 images:

(1)

(2)

(3)

(4)

(5)

(6)

3 of them have a hidden python script that I used to hide the 'message'(in this case the code itself). 

I'll post the code on November 1st at 9:30 A. M.

Programas - Estabilidad

El post siguiente involucrá un pequeño reporte sobre estabilidad y programas que analizarán la estabilidad de un sistema dado, utilizando el criterio de estabilidad de Routh. También utilizaré un método gráfico que está más detallado en el post de laboratorio.

Función de transferencia usada:

0.0026 s + 0.12

________________

s^2 + 0.0026 s + 0.1

Como dice una de las fuentes:

"Un sistema realimentado es estable si todos los polos de lazo cerrado se ubican en el semiplano izquierdo del plano s. Esto es lo mismo a decir que todas las raíces de la ecuación característica tienen parte real negativa." [1]

Pensando en lo anterior, podemos hacer uso de la función roots de octave para obtener las raíces o puntos críticos de la ecuación característica (denominador). En base a estas raíces podríamos extraer la parte real y comparar si están todas del lado izquierdo, es decir si son negativas. Un pequeño script en octave que hace esto es el siguiente:

El programa toma como parámetro un vector con los coeficientes del denominador e imprime las raíces y un mensaje de si es estable o no.

Criterio de estabilidad de Routh:

El criterio de estabilidad de Routh nos permite saber si existen raíces con parte real positiva (inestable) sin necesidad de resolver la ecuación, es decir sin obtener las raíces. Para entender el procedimiento, pueden leer el primer link de las referencias(en español) o el segundo(en inglés) que explican el algoritmo detalladamente.
Nota: El segundo link contiene algunos ejemplos con operaciones erróneas, pero el algoritmo es correcto.

El programa que hace esto lo hice en python porque me es más fácil manipular vectores y matrices ahí. Toma como parámetro un vector con los coeficientes de la ecuación característica, e imprime la matriz creada y un mensaje de si es o no estable.

Lugar geométrico de las raíces:

El siguiente código se encarga de graficar el impulso, el diagrama de nyquist y marcar las raíces en donde corresponde:

Root Locus

La estabilidad del sistema depende de la localización de los polos y ceros en el sistema. Un sistema continuo es estable si todos los polos están en la parte izquierda del plano. En cambio, un sistema discreto es estable si todos los polos están dentro del circulo centrados en el orígen del plano. 

Utilizando rlocus, podemos verificar esto:

Observando cerca del orígen (0) se encuentra un punto rojo(en verdad son dos, los polos) , además de estar encerrados dentro del círculo, por lo cual pasa esta prueba de estabilidad.

Nyquist Diagram

Graficamente podemos observar las raíces y el diagrama de nyquist como sigue:

Nota: El * marca uno de los puntos críticos (en realidad son 2, pero como se puede ver en los números de los puntos críticos estos son bastante cercanos). 

Referencias: 

• [1] Sistemas de Control
• [2] The Routh Criterion
• [3] Nyquist Plots

Tarea 9: Sistema de Transiciones

Sistema: Tostador de Pan

Componentes:

• Tostador: El tostador en sí es el que regula cuando se baja el resorte, cuando se sube y que hacer mientras estas transiciones ocurren.
• Resorte: El resorte, por lo menos en los tostadores pasados, es el que se encargaba de bajar el pan y encender el tostador para calentarlo, y subirlo cuando este estuviera listo.
• Persona(facor externo): Si bien una persona no es parte del sistema de un tostador, es el elemento que da entrada al sistema para que se puedan realizar las transiciones.Esta entrada es insertar el pan en el tostador y presionar el botón para que se inicie a calentar el pan.

Los diagramas de los componentes se pueden ver a continuación:

Persona

• Estados:
• Inicio: La persona se encuentra sin realizar nada con el tostador.
• Espera: La persona espera a que el pan se tueste.
• Acciones Involucradas:
• Insertar Pan: La persona inserta el pan al tostador.
• Devolver Pan: El tostador devuelve el pan.

Tostador

• Estados:
• Standby: El tostador permanece esperando a que se inserte el pan.
• Pan Dentro. El pan es insertado y se espera a que el resorte baje para calentar el pan.
• Calentando Pan: El resorte baja y se inicia calentar el pan, al terminar se sube el resorte.
• Fin: El pan es devuelto tostado a la persona, y se regresa al estado de inicio.
• Acciones Involucradas:
• Insertar Pan: La persona inserta el pan al tostador.
• Devolver Pan: El tostador devuelve el pan.
• Bajar resorte: El tostador baja el resorte para calentar el pan.
• Subir resorte: El tostador sube el resorte para devolver el pan.

Resorte

• Estados:
• Arriba: El resorte se encuentra estirado, o en la parte de arriba esperando una entrda(insertar pan).
• Abajo: El resorte se encuentra comprimido, o en la parte de abajo , calentando el pan.
• Acciones Involucradas:
• Subir resorte: Subir el resorte para devolver el pan.
• Bajar resorte: Bajar el resorte para calentar el pan.

Diagrama de transiciones:

El diagrama de transiciones se puede observar a continuación. En el se puede observar que al realizar transiciones desde el primer componente (Persona) los demás pueden ser modificados. Por ejemplo, al insertar el pan en el primer componente, se cambia al estado esperar. En el segundo componente se cambia al estado Pan Dentro, pero el tercero permanece inmutado. 

Para simplificar el diagrama, se toma lo siguiente:

Estados:

0, 1 = Estados del componente Persona (Inicio, Espera)

A, B, C, D = Estados del componente Tostador(Standby, Pan Dentro, Calentando Pan, Fin)

X, Y = Estados del componente resorte (Arriba, Abajo)

Acciones:

1, 2, 3, 4: insertar_pan, devolver_pan, bajar_resorte, subir_resorte

Referencias:

• Principles of Model Checking

Tarea 5: Diagrama de Nyquist y Estabilidad de un sistema

Mi problema para esta semana es el siguiente:

El problema pide dibujar un diagrama de Nyquist de la función ahí mostrada, y examinar su estabilidad. Lo segundo es lo mismo en lo que estaremos trabajando para la tercera tarea de la materia con nuestra función de transferencia, por lo cual practicar para examinar la estabilidad de otra función me parece buena idea.

Ahora, para dibujar el diagrama de Nyquist podemos simplemente usar Octave-MATLAB y la función nyquist, descrita a continuación:

Función nyquist

[re, im, w] = nyquist (sys)
[re, im, w] = nyquist (sys, w)

Descripción: Diagrama de Nyquist de respuesta de frecuencia. Si no se dan argumentos de salida, la respuesta se muestra en la pantalla.

Entradas:

• sys: Sistema LTI. Debe ser de una sola entrada y de una sola salida (SISO).
• w: Vector opcional de valores de frecuencia. Si no es especificado, es calculado con los ceros y polos del sistema.

Salidas:

• re: Vector con las partes reales. El largo es el mismo del vector de frecuencias w.
• im: Vector de las partes imaginarias. Igual tamaño que w.
• w: Vector de valores de frecuencia usado.

Proporcionando el sistema a la función, ignorando el vector de frecuencias w que no se especifica en el problema:

Entonces le pasamos a la función nyquist el sistema creado anteriormente y ajustamos un poco el plano para poder mostrar desde -2 a 2 en ambos ejes.

Lo siguiente es examinar su estabilidad.Esto podriamos hacerlo de múltiples maneras, pero debido a que estamos usando un diagrama de Nyquist la forma más sencilla es obtener los puntos críticos o raíces del denominador de la función del problema, y observar en que plano caen. En un par de fuentes se menciona esto:

"La estabilidad de un sistema se puede determinar por la ubicacón de los polos(raíces de la ecuación característica) en el plano s. Si alguno de los polos de la ecuación característica se encuentran en el semiplano derecho el sistema es inestable" [2]

"We remind you that a stable system will have all of the poles in the left half of the s-plane, so all of the p's will be negative in G(s)." [3]

Nota: La ecuación característica es el denominador de la función de transferencia.

El plano quedaría algo así entonces:

Podemos usar octave para obtener los puntos críticos de la ecuación característica, que sería s^3 + 0.2 s^2 + s + 1. Para esto utilizamos roots que toma como parametro el vector con los coeficientes de la ecuación característica:

Estos puntos quedan, los primeros dos del lado derecho del plano, y el último del lado izquierdo, dichos valores quedan localizados donde se muestra:

Con esto podemos concluir que: la ecuación es inestable.

Nota: Con solo ver la gráfica de Nyquist mostrada anteriormente podemos ver que NINGÚN punto cae sobre el eje izquierdo, por lo que simplemente podemos concluir que es inestable, pero no esta nada mal explicar como comprobar para los demás casos.

Referencias:

[1] Nyquist Function
[2] Sistemas de Control
[3] Nyquist Plots

6th Assignment: Dragon Stream CIpher

For this week, I chose the Dragon stream cipher for the assignment. I will explain how it works, its advantages and the common attacks-vulnerabilities.

How does it work?

The Dragon Stream cipher explained in the PDF(link at the references) is used to generate a keystream using a key and an initialization vector as input. These two are provided at the end of the PDF, including both sboxes that can be used to test some examples. I used a 256-bit key and initialization vector.

F Function

The first thing defined in the PDF is the F function used both in the key setup and generation. As the PDF defines it: 

"The F function is a reversible mapping of 192 bits (six 32-bit words) to 192 bits. It takes six 32-bit words as input and produces six 32-bit words as output."

These six 32-bit input words are normally defined as a, b, c, d, e, f. And the output words are a', b', c', d', e', f'. Also the function has other components called G1, G2, G3, H1, H2, H3. These are used to provide high non-linearity. 

The main operations used in the F function are the xor(+) and the addition modulo 2^32[+]. In python we can do both with decimal integers, but normally we would need the binary representation for each number. For example:

 a = 29
 b = 21    
                   XOR                                                  ADDITION MODULO 2^32 

               a  (+) b  =  ?                                                           a [+] b = ?
               29  (+) 21 = ?                                                  (a + b) % 2^32 = ?
       << Conversion to Binaries >>                                (21 + 29) % 2^32 = ?
             11101 (+) 10101 = 01000                                 (50) % 2^32 = 32
       << Back to Decimal >>
               29 (+) 21 = 8
               a  (+) b = 8
             
This F function is described as follows:

The inputs as mentioned earlier are six 32-bit words and the outputs are also six 32-bit words, but mixed. 

Now the G and H functions are constructed using the 8x32 bit  S1 and S2 sboxes. These sboxes are provided at the end of the PDF as explained early. Also the 32-bit input used in the G and H functions is separated in four bytes: x0, x1, x2 and x3. Then the results for each G and H function are obtained as follows:

That was the F function, which is used in both the initialization and generation, explained bellow.

Initialization

The initialization is used to generate an internal state W, used later in the generation. This internal state is initially filled by concatenating the key(K) and the initialization vector(IV). Then this is divided into eight 128-bit words (W0-W7). Then a 64-bit Memory component is defined.  The next thing is repeating for 16 rounds a series of operations involving W, so we can initialize the internal state, which is going to be used in the keystream generation.

The initialization algorithm as stated in the PDF is:

The input is the key and the initialization vector, and the output is  the eight 32-bit words that define the initialized internal state. Simply explained, the initialization algorithm involves:

1. Concatenate K + (K xor IV) + ¬(K + IV) + IV which will be a 1024-bit word, and separate it into eight 128-bit words W0 - W7.
2. Initialize the memory variable M = 0x0000447261676F6E (64-bit).
   
   Repeat 16 times
3.  Calculate (W0 xor W6 xor W7) and divide it into four 32-bit words a, b, c, d.
4. Divide M into two 32-bit words e, f.
5. Calculate a', b', c', d', e', f' using the F function defined previously.
6. Join a', b', c', d' and calculate xor with W4, this will be the new W0.
7. Calculate the new Wi = Wi - 1, looping from i = 7 to 1.
8. Join e' and f', this will be the new M.

Keystream Generation:

The keystream generation involves generating a keystream using the previously initialized internal state, and the last value of M as input. The internal state is now divided into thirty-two 32-bit words (B0-B31). During each round of the keystream generation, B0, B9, B16, B19, B30, B31 are used as the F function inputs a, b, c, d, e, f. 

Each round of the keystream generation the output is a 64-bit length keystream k, and an updated state B and M, which can be used again to generate more and more keystreams.

The process is described as follows:

The key generation algorithm simply explained:

1. Split M into two 32-bit words ML (left part) and MR(right part).
2. Obtain the six 32-bit words, making:
   a = B0, b = B9, c = B16, d = B19, e = B30 xor ML, f = B31 xor MR
3. Calculate a', b', c', d', e', f' using the F function defined previously.
4. Make the new B0 and B1 equal to b' and c' respectively.
5. Calculate the new B's with Bi = Bi-2  looping from i = 32 to i = 2.
6. Update M = M + 1.
7. Get the 64-bit keystream joining a' and e'.
8. Repeat using the last B's and M values.

Example

For an example of this cipher I created python script that used the test data provided in the PDF(256-bit key and IV). The script reads from the sbox1.dat and sbox2.dat files the S1 and S2 sboxes used in the f function, and generates one round of a keystream with the said test data. I use a lot of string operations to convert stuff into binary strings and manipulate them easier (even though it is also possible to do it with decimals). The Python code:

Output(Generating 100 rounds):

Note: There was no information available that I could found about how the keystream is used to encrypt a plaintext, so I didn't create an example for that.

Attacks-Vulnerabilities:

Time-Memory Trade-off Attack

Time-Memory tradeoff attacks  rely on pre-computation to reduce the effort required for a key recovery attack on a keystream. The attack comprises two steps.

• The first, the preprocessing step, sees the attacker calculating a table of keys or internal states and corresponding keystream prefixes. The table is ordered upon the prefix. 
• The second step involves observing keystreams and attempting to match each against a prefix in the table. If the match is successful, then with some likelihood the internal state is known by reading the opposing entry in the table

Guess and determine

To calculate keystream words from two rounds of Dragon, the attacker is required to guess more than 256 bits of the internal state. This is worse than exhaustive key search, and makes guess and determine attacks on Dragon unfeasible.

Distinguishing Attacks

If the output sequence of a stream cipher can be statistically distinguished from a random sequence, then the cipher is not strong enough for cryptographic applications. Dragon is designed with a large state and complex initialization and update function. It has no linear masking, and therefore immune to this type of distinguishing attacks

References:

• Dragon: A Fast Word Based Stream Cipher

Tarea 8: Sistemas Concurrentes

Red de Petri

Una red de Petri es un grafo con pesos bipartito usado como representación en la computación concurrente, particularmente los aspectos que involucran programación multi hilos. 

En las redes de petri existen dos sets de nodos, los llamados Places que normalmente se representan como círculos u ovalos, y las Transitions, dibujadas como rectángulos delgados. Debido a que es bipartito, hay aristas desde los Places a Transitions, y vice-versa, pero nunca a uno de igual tipo.

Sistema a modelar: SMART TV

Un sistema algo común para cualquiera. Podemos decir que es concurrente por el simple hecho de que reproduce sonido y audio a la vez, y las televisiones más nuevas hasta tienen internet inalámbrico por lo cual son tres actividades simultaneas(ignorando procesos internos).

El sistema entonces se modelara basandonos en el hecho de que se esté viendo una película por internet en una Smart TV.

(Imágen tomada de: http://bloglge.com.br/wp-content/uploads/2011/10/netflix-e1322839636471.jpg )

Los places en este caso pueden ser: 

P = {Inicio, Internet, Video, Audio, Película}

Entonces el proceso puede ser descrito como sigue:

• Primero se inicializa todo, ignorando el proceso de encendido y selección de película que son simples transiciones.
• Para que se pueda reproducir la película primero se descarga parte por parte, y se hace un streaming.
• Mientras se hace lo anterior se procesa video y audio de dicho streaming para que la televisión pueda reproducirlo.
• Hecho lo anterior se reproduce la película.

Ésto se puede representar mediante el siguiente diagrama:

Donde:

• P0: Inicializar
• P1: Video
• P2: Audio
• P3: Internet
• P5: Datos Descargados
• P4: Película

Python-Snakes

Utilizando el módulo Python-Snakes para crear la red de petri, nos puede quedar de la siguiente manera:

Código:

Referencias:

• Principles of Model Checking
• Modeling Concurrency with Graphs: Petri Nets (by MarkCC)

5th Assignment: Mesh Block Cipher

For this assignment I chose the Mesh Block Cipher to do some research. Because there are several variants are available (MESH-64, MESH-96, MESH-128, I'm going to focus on the MESH-64 variant.

The MESH block cipher

MESH is a block cipher designed in 2002 by Jorge Nakahara, Jr., Vincent Rijmen, Bart Preneel, and Joos Vandewalle. MESH is based directly on IDEA and uses the same basic operations.

The MESH block ciphers designs are based on the same group operations as the IDEA cipher, but with a number of novel features:

• Flexible block sizes in steps of 32 bits (the block size of IDEA is fixed at 64 bits)
• Larger MA-boxes
• Distinct key-mixing layers for odd and even rounds
• New key schedule algorithms that achieve fast avalanche and avoid the weak keys of IDEA.

The software performance of MESH ciphers are estimated to be better or comparable to that of triple-DES.

Main parameters

Mesh-64 Block Cipher


MESH-64 is a 64-bit block cipher with a 128-bit key and 8.5 rounds. The last 0.5 round is the output transformation. The key schedule for MESH-64 is:

• First, 16-bit constants ci are defined as: c0 = 1, and ci = 3 · ci−1 , i ≥ 1 with multiplication in GF(2)[x]/p(x), under the primitive polynomial p(x) = x^16 + x^5 + x^3 + x^2 + 1. The constant ‘3’ is represented by the polynomial x + 1 in GF(2).
• The 128-bit user key is partitioned into eight 16-bit words Ki , 0 ≤ i ≤ 7,  and assigned to Zj+1 = Kj ⊕ cj , 0 ≤ j ≤ 6, and Z1 = K7 ⊕ c7 .
• Finally, each subsequent 16-bit subkey is defined as follows:

for 8 ≤ i ≤ 59; ‘<<< 7' is left rotation by 7 bits; h(i) = i div 7 + 1, and l(i) = i mod 7 + 1.

Operations used:

• Bit-wise exclusive or ⊕
• Addition in Z216 
• Multiplications in GF(216 + 1)

Attacks

A number of attacks, such as truncated and impossible differentials, linear and Demirci’s attack, shows that more resources are required on the MESH ciphers than for IDEA, and indicates that both ciphers seem to have a large margin of security.

Main known attacks:

• Truncated  Differential Attack
• Linear Attack
• Impossible Differential Attack
• Demirci's Attack
• Biryukov-Demirci Attack

Performance

References:

• The MESH Block Ciphers - Jorge Nakahara Jr , Vincent Rijmen , Bart Preneel, Joos Vandewalle
• The Biryukov-Demirci Attack on IDEA and MESH Ciphers

Tarea 4: Curva de Respuesta

Para obtener la salida del sistema se usa la función lsim, describida a continuación.

Function File: y= lsim (sys, u, t)

Parámetros

• sys: Sistema invariante en el tiempo (LTI).
• u: Vector de señal de entrada. Debe ser del mismo largo de filas que el vector de tiempos y el mismo largo que entradas de columnas.
• t: Vector de tiempos espaciado uniformemente.

Salida

y: Vector de respuesta de salida. Tiene tantas filas como el largo de t y tantas columnas como salidas.

Proceso:

Creamos un vector con los digitos del numerador, y un vector con los digitos del denominador y creamos un sistema con ellos.
 

Después creamos un vector de tiempos uniformes(0.1 de espacio) y obtenemos el vector entrada de aceleración unitaria en base a éste:


Ahora podemos utilizar la función lsim para obtener la salida del sistema, dando como parametros el sistema, el vector de tiempos y vector de entrada.


Después graficamos los resultados:


Resultado:

Tarea 7: Aplicación de la Lógica Predicativa

La aplicación de la lógica predicativa que utilizaré de ejemplo será la Prueba de Teoremas.

"Un teorema es una afirmación que puede ser demostrada dentro de un sistema formal."

Para probar teoremas podemos expresar el teorema en lógica de primer orden, es decir pasando los términos a predicados.

Buscando información por Internet encontré un applet MUY interesante que sirve para probar teoremas, expresándolos en un lenguaje especial muy similar a la programación.

Ejemplo 1:

Si queremos probar el teorema: "Emmanuel es mortal", solo sabiendo que los humanos son mortales, y que Emmanuel es un humano, podemos hacer lo siguiente:

Axiomas

1. Los humanos son mortales.
2. Emmanuel es un humano.

Teorema

• Emmanuel es mortal.

Lógica Predicativa

Expresión	Símbología
X es humano	Humano(X)
X es mortal	Mortal(X)

  1. x( Humano(x) → Mortal(x))
  (Para todo x, Sí x es humano entonces x es mortal)

  2. Humano(Emmanuel)

  (Emmanuel es humano)

Ahora con lo anterior, reemplazando x por Emmanuel en la primera, podemos concluir:

  Humano(Emmanuel) → Mortal(Emmanuel)
  (Si Emmanuel es Humano, Emmanuel es Mortal)

Como ya habíamos definido anteriormente que Emmanuel es humano, entonces la expresión se hace verdadera y se comprueba que Emmanuel es Mortal.

Utilizando la applet produce el siguiente resultado:

Ejemplo 2:

Si deseáramos probar que los monos son seres vivos, solo sabiendo son mamíferos, y que los mamíferos son seres vivos, podríamos hacer algo así:

Axiomas:

1. Los monos son mamíferos.
2. Los mamíferos son Seres Vivos.

Teorema

Los monos son Mamíferos

Lógica de Predicados

Expresión	Símbología
X es mamífero	Mamifero(X)
X es ser vivo	SerVivo(X)

  1. Mamifero(Monos)
  (Los monos son mamiferos)

  2. x( Mamifero(x) → SerVivo(x))
  (Para todo x, Sí x es un mamífero x es un ser vivo )

Con lo anterior, podemos concluir:

 Mamífero(Monos)  → SerVivo(Monos)
 (Sí los monos son mamíferos, los monos son seres vivos)

Y como ya habíamos concluido que los monos son mamíferos, se comprueba que los monos son seres vivos.

Aquí una captura de como lo resuelve el applet:

Referencias:

http://www.foundalis.com/mat/atp/Prover.html
http://en.wikipedia.org/wiki/First-order_logic

Reporte 2: Diagrama de Bloques

Debido a que previamente había definido las funciones de entrada y salida como ecuaciones lineales, tuve que cambiarlas por ecuaciones diferenciales en función del tiempo.

Para esto entonces, tomamos en cuenta que la entrada es una temperatura en el sistema(que se convertirá en un voltaje análogo, pero en sí la entrada es la temperatura) y la salida es una velocidad en el ventilador, que será manipulada por un microcontrolador dependiendo de la temperatura de entrada.

Función de entrada:

• T0(t) es la temperatura actual del cuerpo(sensor).
• Tenv es una constante de la temperatura ambiente (20).
• k es una constante de proporcionalidad.

Obteniendo la transformada de Laplace:

Pero como esta temperatura se transforma en voltaje mediante el sensor, podemos usar la fórmula del sensor

Cambiando T a términos de T(s), entonces podemos obtener que el voltaje será:

Después será amplificado por un amplificador, pero esto es solo multiplicar el voltaje.

Función de salida:

Para la salida, tenemos un sistema mecánico que es la velocidad del ventilador. Esta podemos calcularla como Revoluciones por Minuto(RPM), utilizando la velocidad angular:

Función de Transferencia:

Diagrama de Bloques:

Para representar el sistema en un diagrama de bloques se tomarán en cuenta las siguientes propiedades:

Propiedades de los diagramas de bloques:

(Imágen obtenida de: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiSQQdoeAiBvfUAfzR6IeuEbw-Xav8-vEKnRXCZhd6zhh0rFUEA2ouCqbitrtes9CdKtt5p0HetOnWYCRCxJKos8kCiwGz6UQRQS7GZNwqh0UoahLhRplxRTIzSGA_FKtXBqY8gekvj8E9x/s640/PROP.jpg)

Paso 1:

Paso 2:

Paso 3:

Paso 4:

Referencias:

• Control Systems/Block Diagrams