martes, 30 de octubre de 2012

[SC] 9. Steganography

For this week the challenge was implement a steganography script using python, so, here are my pictures.

This one contain a hidden message:

Hidden Plaintext:


In a village of La Mancha, the name of which I have no desire to call to mind, there lived not long since one of those gentlemen that keep a lance in the lance-rack, 
an old buckler, a lean hack, and a greyhound for coursing. An olla of rather more beef than mutton, a salad on most nights, scraps on Saturdays, lentils on Fridays, 
and a pigeon or so extra on Sundays, made away with three-quarters of his income. The rest of it went in a doublet of fine cloth and velvet breeches and shoes to match 
for holidays, while on week-days he made a brave figure in his best homespun. He had in his house a housekeeper past forty, a niece under twenty, and a lad for the field 
and market-place, who used to saddle the hack as well as handle the bill-hook. The age of this gentleman of ours was bordering on fifty; he was of a hardy habit, spare, 
gaunt-featured, a very early riser and a great sportsman. They will have it his surname was Quixada or Quesada (for here there is some difference of opinion among the 
authors who write on the subject), although from reasonable conjectures it seems plain that he was called Quexana. This, however, is of but little importance to our tale; 
it will be enough not to stray a hair's breadth from the truth in the telling of it.

You must know, then, that the above-named gentleman whenever he was at leisure (which was mostly all the year round) gave himself up to reading books of chivalry with 
such ardour and avidity that he almost entirely neglected the pursuit of his field-sports, and even the management of his property; and to such a pitch did his eagerness 
and infatuation go that he sold many an acre of tillageland to buy books of chivalry to read, and brought home as many of them as he could get. But of all there were none 
he liked so well as those of the famous Feliciano de Silva's composition, for their lucidity of style and complicated conceits were as pearls in his sight, particularly 
when in his reading he came upon courtships and cartels, where he often found passages like "the reason of the unreason with which my reason is afflicted so weakens my 
reason that with reason I murmur at your beauty;" or again, "the high heavens, that of your divinity divinely fortify you with the stars, render you deserving of the 
desert your greatness deserves." Over conceits of this sort the poor gentleman lost his wits, and used to lie awake striving to understand them and worm the meaning out 
of them; what Aristotle himself could not have made out or extracted had he come to life again for that special purpose. He was not at all easy about the wounds which 
Don Belianis gave and took, because it seemed to him that, great as were the surgeons who had cured him, he must have had his face and body covered all over with seams 
and scars. He commended, however, the author's way of ending his book with the promise of that interminable adventure, and many a time was he tempted to take up his pen 
and finish it properly as is there proposed, which no doubt he would have done, and made a successful piece of work of it too, had not greater and more absorbing thoughts 
prevented him.

Three of these ones (the three inside the blue frame) contains the python code used to hide the information:

So, let's hack begin...


To download the code:

To download the images:

To encode information:

python -E

To decode information

python  -D

Then, enter the requested data.

lunes, 29 de octubre de 2012

[VVS] 9. Modelado de Sistemas Concurrentes

La tarea consistió en elegir un sistema y modelarlo de 2 posibles maneras, ya sea mediante un sistema de transiciones o mediante un grafo de programa, elegí el sistema de transiciones.

El sistema que elegí fue una minimización de un restaurante de comida rápida.


  • Cajero: Es el encargado de tomar las ordenes y pasarlas a la cocina para posteriormente cobrar el monto total del pedido.
  • Cocina: Recibe las ordenes del cajero y se encarga de preparar el pedido, posteriormente sirve los platos para su posterior entrega.
  • Ayudante: Se encarga de recibir los pedidos preparados por la cocina y los entrega al cliente, cerrando así el ciclo.
Siguiendo la nomenclatura del libro, el sistema completo queda definido por los componentes:

Modelado y descripción formal de los componentes:


  • {0} Espera
  • {1} Orden recibida
  • {2} Orden cobrada
  • {Rec} Recibir la orden
  • {Cob} Cobrar la orden
  • {Pas} Pasar la orden a cocina
  • {0} Espera
  • {1} Orden recibida
  • {2} Orden preparada
  • {Pas} Pasar orden (recibirla del cajero)
  • {Pre} Preparar la orden
  • {Ser} Servir la orden
  • {0} Espera
  • {1} Orden entregada
  • {Ser} Servir la orden (Recibida de la cocina)
  • {Ent} Entregar la orden al cliente

Diagrama de Transiciones

El sistema que elegí es altamente concurrente, es común que en un restaurante veamos a todo el equipo trabajando al mismo tiempo, por ejemplo, el cajero puede estar recibiendo ordenes constantemente y enviarlas a la cocina, no espera a que la cocina termine las ordenes, así mismo el ayudante quien constantemente entrega ordenes mientras el cajero y la cocina trabajan.

Es por ello que encontré múltiples caminos a diversos estados, pero se puede notar un miniloop con los estados {000} → {100} → {200} → {010} → {020} → {001} que indican el camino de la transición si el sistema no fuera concurrente


  • [Libro] Principles of Model Checking - Christer Baier & Joost-Pieter Katoen

sábado, 27 de octubre de 2012

[Lab ACSD] 5. Análisis de la respuesta en frecuencia

Planteamiento del problema

8.24 Considere el sistema definido mediante:

Hay cuatro diagramas de Nyquist individuales implícitos en este sistema. Dibuje dos diagramas de Nyquist individuales para la entrada U1 en un gráfico y dos diagramas de Nyquist para la entrada U2 en otro gráfico.
Utilice MATLAB para obtener éstos dos gŕaficos.


La solución a este problema la planteare en OCTAVE,  lo dividiré en 2 partes:

  • Hallar las funciones de transferencia
  • Dibujar los diagramas de Nyquist

Primero, necesitamos cargar los datos del sistema en OCTAVE de la siguiente manera:
octave:1> A = [-1 -1;6.5 0]; octave:2> B = [1 1;1 0]; octave:3> C = [1 0;0 1]; octave:4> D = [0 0;0 0];


Como ya hemos notado, el sistema se encuentra representado en la forma canónica, entonces hay que convertirlo a forma algebraica para poder utilizar la función nyquist en OCTAVE, eso se logra con el comando:
octave:5> pkg load signal octave:6> [num, den] = ss2tf(A,B,C,D,1)
El comando anterior nos regresa 2 arreglos, uno con los 4 numeradores y otro con los 4 denominadores, correspondientes (por pares) a las 4 funciones de transferencia, y por consiguiente, a los 4 diagramas de Nyquist.


Ahora vamos a formar las 4 funciones de transferencia con los siguientes comandos, utlizando los correspondientes numeradores y denominadores por pares:
octave:7> sys1 = tf(num{1}, den{1}); octave:8> sys2 = tf(num{2}, den{2}); octave:9> sys3 = tf(num{3}, den{3}); octave:10> sys4 = tf(num{4}, den{4});

Con esto queda concluida la parte de obtener las funciones de transferencia.

Ahora vamos a dibujar los diagramas de Nyquist tal como lo especifica, para ello utilizamos los siguientes comandos:
octave:11> nyquist(sys1); octave:12> hold on; octave:13> nyquist(sys2);
Lo que da como resultado el primer diagrama para la entrada U1(sys1 es el diagrama ovalado pequeño y sys2 el diagrama externo)

Despues liberamos
octave:14> hold off;
Y dibujamos el segundo par
octave:15> nyquist(sys3); octave:16> hold on; octave:17> nyquist(sys4);
Lo que da como resultado el diagrama para la entrada U(sys3 es el diagrama ovalado pequeño y sys4 el diagrama externo)

Ejecución de los 2 pasos anteriores:

Asi concluye la actividad, espero les sirva como buena referencia. Saludos.


jueves, 25 de octubre de 2012

[SC] 8. Stream ciphers: Grain


Grain is a stream cipher pruposed and submitted to eSTREAM project by Martin Hell, Thomas Johansson and Willi Meier in 2004.It has been selected for the final eSTREAM portfolio for Profile 2 by the eSTREAM project.

Grain is designed for very restricted hardware environments, such as RFID tags.

The cipher is based on Linear Feedback Shift Register (LFSR) and non-linear feedback shift register (NFSR).


Actually exists a need of cryptographic systems that have a low hardware complexity. Per example, a RFID tag has a very limited amount of resources; it's a microchip capable of transmiting a sequence after a request from the reader.

There are serveral aplications for RFID tags, mostly, card-based authentication systems. The information transmitted between the card and the readers can be hacked easily because there isn't a system that protects the information during its transmission.

Devasting consequences could happen if the RFID tags were implemented, seriously, in electronic payments and hence.

Today, the implementation of AES and DES on an RFID tag is not feasible due to the expensive hardware cost (the large number of logical gates, gate equivalent).
And we can take so much more other examples, such as, bluetooth and NFC modules, microchips, sim cards, memory cards, etc.
Grain is a stream cipher designed to be very simple and small to implement in hardware.

Grain provides a higher security than other ciphers intended to be used in hardware applications, such as E0 used in Bluetooth and A5/1 used in GSM.
These ciphers, while also having a very small hardware implementation, have been proven to be very insecure.
Compared to E0 and A5/1, Grain provides higher security while maintaining a small hardware complexity.


Grain is based in three main blocks:
  • A 80-bit linear feedback shift register
  • A 80-bit nonlinear feedback shift register
  • A nonlinear filtering function. 

Grain is initialized with the 80-bit key K and the 64-bit initialization value IV . The cipher output is an L-bit keystream sequence (zt) t = 0,...,L−1.

The current LFSR content is denoted by St+80 = (st, st+1, . . . , st+79).

The feedback polynomial of the LFSR, f(x) is a primitive polynomial of degree 80. It is defined as:

f(x) = 1 ⊕ x18 ⊕ x29 ⊕ x42 ⊕ x57 ⊕ x67 ⊕ x80

The update function of LFSR is governed by the linear recurrence:

st+80 = st+62 ⊕ st+51 ⊕ st+38 ⊕ st+23 ⊕ st+13 ⊕ st

The current NFSR content is denoted by Bt+80 = (bt, bt+1, . . . , bt+79).
The feedback polynomial of the NFSR, g(x), is defined as:

g(x) = 1 ⊕ x17 ⊕ x20 ⊕ x28 ⊕ x35 ⊕ x43 ⊕ x47 ⊕ x52 ⊕ x59 ⊕ x65 ⊕ x71 ⊕ x80 ⊕ x17x20 ⊕ x43x47 ⊕ x65x71 ⊕ x20x28x35 ⊕ x47x52x59 ⊕ x17x35x52x71 ⊕ x20x28x43x47 ⊕ x17x20x59x65 ⊕ x17x20x28x35x43 ⊕ x47x52x59x65x71 ⊕ x28x35x43x47x52x59

 The NFSR feedback is disturbed by the output of the LFSR, so that the NFSR content is governed by the recurrence:

bt+80 = st ⊕ g(bt, bt+1, . . . , bt+79)


g(bt, bt+1, . . . , bt+79) = bt+63 ⊕ bt+60 ⊕ bt+52 ⊕ bt+45 ⊕ bt+37 ⊕ bt+33 ⊕ bt+28⊕ bt+21 ⊕ bt+15 ⊕ bt+9 ⊕ bt ⊕ bt+63bt+60 ⊕ bt+37bt+33 ⊕ bt+15bt+9 ⊕ bt+60bt+52bt+45 ⊕ bt+33bt+28bt+21 ⊕ bt+63bt+45bt+28bt+9 ⊕ bt+60bt+52bt+37bt+33 ⊕ bt+63bt+60bt+21bt+15 ⊕ bt+63bt+60bt+52bt+45bt+37 ⊕ bt+33bt+28bt+21bt+15bt+9 ⊕ bt+52bt+45bt+37bt+33bt+28bt+21

The contents of the two shift registers represent a state of the cipher. The cipher output bit is derived from these states; 5 variables (x0, x1, x2, x3, x4) are taken as input to a boolean function, h(x), the bits are st+3, st+25, st+46, st+64 and bt+63

This filter function is chosen to be balanced, correlation immune of the first order and has algebraic degree 3. The function is defined as:

h(x) = x1 ⊕ x4 ⊕ x0x3 ⊕ x2x3 ⊕ x3x4 ⊕ x0x1x2 ⊕ x0x2x3 ⊕ x0x2x4 ⊕ x1x2x4 ⊕ x2x3x4

Finally, we take take the output of the NFSR and the output of h(x), apply xor with both values to obtain a bit of the keystream.

The  keystream is combined with the plaintext using XOR operation to obtain ciphertext.

Key Initialization

Before generate a keystream, the cipher must be initialized with the key and an iniatialization vector (IV), the process as the follows:
  • Put the 80-bit length key in the NFSR
  • Put the 64-bit length IV in LFSR
  • Fill the remaining 16 bits of the LFSR with ones.
  • Clock the cipher at 160 cycles.
  • Run the cipher.
  • The output of the cipher must be xored with the input of both NFSR and LFSR.

Vulnerabilities and proposed solutions

From "Grain - A Stream Cipher for Constrained Environments"

    There are several vulnerabilities found in Grain cipher, such as:

    • "Correlations: Due to the statistical properties of maximum-length LFSR sequences, the bits in the LFSR are (almost) exactly balanced. This may not be the case for a NFSR when it is driven autonomously. However, as the feedback g(x) is xored with a LFSR-state, the bits in the NFSR are balanced. Moreover, recall that g is a balanced function. Therefore, the bits in the NFSR may be assumed to be uncorrelated to the LFSR bits. The function h is chosen to be correlation immune of first order. This does not preclude that there are correlations of the output of h(x) to sums of inputs. As one input comes from the NFSR and as h(x) is xored with a state bit of the NFSR, correlations of the output of the generator to sums of LFSR-bits will be so small that they will not be exploitable by (fast) correlation attacks."

    • "Algebraic Attack: A filter generator alone with output function h(x) of degree only three would be very vulnerable to algebraic attacks. On the other hand, algebraic attacks will not work for solving for the initial 160-bit state of the full generator, as the update function of the NFSR is nonlinear, and the later state bits of the NFSR as a function of the inital state bits will have varying but large algebraic degree. Using key initialization, it may be possible to express the output of the generator as a function of state bits of the LFSR alone. As the filter function h(x) has one input coming from the NFSR, and h(x) is xored with a NFSR-state bit, the algebraic degrees of the output bits when expressed as a function of LFSR-bits, are large in general, and varying in time. This will defeat algebraic attacks."

    • "Time/Memory/Data Tradeoff Attack: The cost of time/memory/data tradeoff attacks on stream ciphers is O(2n/2), where n is the number of inner states of the stream cipher. To obey the margins set by this attack, n = 160 has been chosen. It is known that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters. The sampling resistance of h(x) is reasonable:
      • This function does not become linear in the remaining variables by fixing less than 3 of its 5 variables. Similarly, the variables occuring in monomials of g(x) are sufficiently disjoint. Hence the resulting sampling resistance is large, and thus time/memory/data tradeoff attacks are expected to have complexity not lower than O(280)."


    martes, 23 de octubre de 2012

    [VVS] 8. Verificación formal de sistemas

    Una Red de Petri es un modelo gráfico, formal y abstracto para describir y analizar el flujo de información, sirven como una herramienta matemática para modelar concurrencia, no deterninismo, comunicación y sincronización.

    El análisis de las Redes de Petri ayuda a mostrar información importante sobre la estructura y el comportamiento dinámico de los sistemas modelados.

    Las redes de petri fueron inventadas por el alemán Karl Adam Petri en 1962. En su tesis doctoral "kommunikation mit automaten" (Comunicación con autómatas) establece los fundamentos para el desarrollo teórico de los conceptos básicos de las redes de petri.

    Las redes petri son consideradas una herramienta para el estudio de los sistemas, con una red de petri se puede modelar el comportamiento y la estructura de un sistema. Posteriormente se puede analizar el flujo del proceso que el sistema realiza para obtener un resultado, asi como obtener información sobre el comportamiento dinámico del sistema.

    Las redes de petri se componen de dos cosas:
    • Lugares: que permiten representar los estados del sistema mediante la utilización de marcas.
    • Transiciones: que representan el conjunto de acciones a realizar cuando se cumplen unas determinadas precondiciones en el sistema.

    Más ampliamente, una red de Petri es un conjunto formado por la tupla R = {P, T, Pre, Post}, la tupla contiene los componentes básicos que forman su estructura:
    • Un conjunto de plazas P
    • Un conjunto de transiciones T
    • La función de entrada I
    • La función de salida O

    Las funciones de entrada y salida relacionan las transiciones y las plazas.

    La función de entrada I es un mapeo a partir del conjunto de plazas de entrada hacia la transición tj, la función se puede escribir como I(tj).

    La función de salida O es un mapeo a partir de la transición tj hacia el conjunto de plazas de salida, la función de salida se puede escribir como O(tj).

    Hay una serie de condiciones que deben cumplirse en la construcción de las Redes de Petri:

    1. Un arco une siempre lugares con transiciones y nunca dos lugares o dos transiciones.
    2. Una transición puede ser destino de varios lugares y un lugar puede ser el destino devarias transiciones.
    3. Una transición puede ser origen de varios lugares y un lugar puede ser origen de varias transiciones.
    4. Los lugares pueden presentar marcas (una marca se representa mediante un punto en el interior del círculo).
    5. Cada lugar tiene asociada una acción o salida. Los lugares que contiene marcas se consideran lugares activos. Cuando un lugar está activo sus salidas están a uno.
    6. A las transiciones se les asocia eventos (funciones lógicas de las variables de entrada). Una transición se dice que está sensibilizada cuando todos su lugares origen están marcados.
    7. Cuando ocurre un evento asociado a una transición (la función lógica se hace uno), se dice que la transición está validada.

    Algunas de las aplicaciones de las Redes de Petri pueden ser diseñar, analizar y diagnosticar:
    • Sistemas concurrentes
    • Arquitetura de Computadores
    • Protocolos de Redes
    • Sistemas Operativos
    • Sistemas de Producción
    • Sistemas Digitales
    • Hardware/Software
    • Sistemas de Tiempo Real
    • Control de Tráfico

    Mas información, consultar referencias.


    La actividad de esta semana consistió en:
    • Investigar un poco sobre Redes Petri
    • Inventar un pequeño sistema concurrente
    • Modelar la Red Petri en Python, utilizando python-snakes

    El sistema concurrente que elegí se me ocurrio viendo una maquina de café en el trabajo, asi que comencé a diseñar una red de petri de acuerdo a cómo pienso que funciona esa máquina.

    Primero, ¿qué hace la máquina? Básicamente tiene 2 botones, agua o café, y dependiendo de cuál botón presiones dispensará agua caliente o una infusión de café.

    Para ello note el siguiente flujo de trabajo:
    • La máquina está en espera
    • Presionas el boton de agua caliente o café.
    • Si eliges café, la maquina toma un poco de café, lo muele y lo coloca en el filtro
    • La máquina comienza a hacer fluir el agua caliente por el filtro
    • La máquina dispensa la infusión de café.
    • La máquina limpia el filtro y espera nuevamente.
    • Si eliges agua caliente la máquina se brinca los pasos de tomar, moler y colocar el café, solamente hace fluir el agua caliente y vuelve a esperar.

    Ahora, hay 2 transiciones que suceden en silencio.
    • Verificar si hay café en el contenedor, si no, enciende un led rojo como aviso.
    • Verificar si hay agua en el contenedor, si no, enciende un led rojo (diferente) como aviso.

    Entonces, identifiqué los siguientes estados y transiciones:

    1. Esperando
    2. Agua seleccionada
    3. Café seleccionado
    4. Si hay café
    5. Si hay agua
    6. Bebida servida
    7. No hay café
    8. No hay agua
    1. Selecciona bebida
    2. Verificar café
    3. Verificar agua
    4. Servir bebida
    5. Limpiar filtro
    6. Aviso error

    El dibujo queda algo asi:

    Utilizando python-snakes:

    Diagrama animado:



    jueves, 18 de octubre de 2012

    [SC] 7. Block Ciphers: PRESENT


    PRESENT cipher was developed together by the Orange Labs in France, The Ruhr University Bochum in Germany and the Technical University of Denmark; and was first published on August 23 of 2007.

    PRESENT cipher is one of the most compact encryption methods ever designed and is 2.5 times smaller than AES (Advanced Encryption Standard).

    The specifications of PRESENT cipher was written in the paper "PRESENT: An Ultra-Lightweight Block Cipher", published in 2007 in the event CHES 2007 (Cryptographic Hardware and Embedded Systems Workshop) in Vienna, Austria , the authors are:
    • A. Bogdanov, G. Leander and C. Paar from Horst-Görtz-Institute for IT-Security at Ruhr-University Bochum in Germany
    • A. Poschmann, L.R. Knudsen and C. Vikkelsoe from Technical University Denmark at Lyngby, Denmark
    • M.J.B. Robshaw and Y. Seurin from France Telecom R&D at Issy les Moulineaux, France


    Actually the computation paradigm are shifting to Pervasive Computing, so, there are a lot of devices with a limited amount of CPU, memory, power, and energy consumption. The problem is that all known ciphers are designed for high performance devices.

    The goals of the PRESENT cipher are:
    • The cipher is to be implemented directly in the hardware, efficiently
    • Applications with moderate security levels (80 bit)
    • Small amounts of encrypted data
    • Often no rekeying possible (Encryption only core)
    • Metrics:
      • Security
      • Power consumption
      • Time
    That means that in very small devices such as RFID cards or microcontrollers is possible to implement a cipher for simple security tasks, that with other ciphers was not possible due to the system requirements.

    Some concepts


    The PRESENT cipher is a simple SP-network with 64-bits block size and 80 or 128 bits of key lenght (PRESENT128 for the 128 bit version). A key lenght of 80-bits provides a good security level for many RFID or other small applications.

    PRESENT uses a round-based algorithm, 32 rounds in total, where 31 rounds are regular rounds that consists in a key mixing step, a substitution layer and a permutation layer; the final round consists only in the key mixing step.

    The recommended functions are:
    • addRoundKey: Given round key Ki = [K63, K62, ..., K1, K0], and a current state bi = [b63, b62, ..., b1, b0]; the key mixing step addRoundKey consists in a XOR operation:
    bj = bj ⊕ Kj; for j ≤ 0 ≤ 63

    • sBoxLayer: The S-box used in PRESENT is a 4-bit to 4-bit S-box, the 64-bit block is divided in chunks of 4-bits, each 4-bit chunk is the input to a S-box. The S-Box Layer consist in 16 parallel S-boxs. The substitutions, written in hexadecimal (1111 = F) are given by the following table:

    • pLayer: Performs a bit permutation, where the bit i of the block is moved to bit position P(i).  The permutation used in PRESENT is given by the following table.

    • keyRegisterUpdate: The key register stores a 80-bit key, where, only the 64 leftmost bits are used in the key mixing step. After that, the key register is updated, the key register is rotated 61-bits to the left, the left-most four bits are passed through the present S-box, finally the round counter is XOR-ed with the bits 15-19 of the key register. 

    The whole SP-Network of PRESENT cipher is represented as follows:

    Finally, the pseudocode algorithm and flow diagram are represented as follows:

    Example (v0.1)

    For this report I was trying to write my own implementation of PRESENT in python, but, something went wrong, as you can see in the following picture.

    Basically, I have 2 errors:
    • The implementation only accept numeric strings.
    • The implementation only decode the last 2 characters of the string
    I think there are some errors in my conversion logic because I need to convert the strings from bin to hex to ascii and viceversa, so, maybe the encrypt-decrypt engine is half ok.

    I will update this entry when the code is ready, sorry for my failure.

    In the references (bottom) are some implementations of PRESENT in C and Python.


    An example of vulnerability in PRESENT cipher is the Statistical Saturation Attack. The attack is based on a weakness in the permutation layer of PRESENT. 
    This weakness can be found making a closer look to the permutation layer, in this example, the S-boxes 5,6,9 and 10 (counting from S-box 0 at the right), only 8 out of 16 input bits are directed to other S-boxes, and the other 8 input bits are fixed in all rounds!.

    Permutation Layer Poor Diffusion example 1, from "A Statistical Saturation Attack against the Block Cipher PRESENT"

    There are many other examples of poor diffusion in the permutation. So, if the 16 bits at the input of the S-boxes 5-6-9-10 are fixed, then 8 bits will be known at the very same input for the next round. We can iteratively repeat this process round by round and observe a non-uniform behavior at the output of the S-boxes 5-6-9-10.

    The attack 
    from: "A Statistical Saturation Attack against the Block Cipher PRESENT"

    "In order to exploit this weakness, we first evaluate theoretically the distribution of the 8 bits in the bold trail of the above picture at the output of the S-box layer, for a fixed value of the same 8 bits of plaintext. This requires to guess the 8 subkey bits involved in the trail. One also needs to assume that the bits not situated in the trail are uniformly distributed. This is a reasonable assumption as soon as the 56 remaining bits of plaintext (excluding the 8 bits in the trail) are randomly generated. Then, given the distribution of the 8-bit trail at the input of a round, it is possible to compute the 8-bit distribution at the output of the round. Iteratively, we can compute the distribution for an arbitrary number of rounds.
    For each key guess, the work needed to compute the theoretical distribution of the target trail after r rounds is equivalent to r · 216 partial encryptions.

    Once we have computed the theoretical distributions of the trail for each possible key guess, we can attack the cipher by simply comparing them with a practical distribution obtained by encrypting a large number of plaintexts with a secret key. The key guess minimizing the distance between theoretical and practical distributions is chosen as the correct key. We can construct a list of key candidates sorted according to the distance between theory and practice. The better the position of the right key in the list, the better the attack."

    Permutation Layer Poor Diffusion example 2, from "A Statistical Saturation Attack against the Block Cipher PRESENT"


    martes, 16 de octubre de 2012

    [Lab ACSD] 4. Análisis del lugar geométrico de las raíces

    Dibuje los lugares de las raíces para un sistema con:

    Determine los puntos exactos donde los lugares de las raíces cortan el eje jω.


    Primero debemos determinar los puntos donde los lugares de las raíces cortan el eje real, para ello hay que obtener la ecuación característica:

    En este caso no existen puntos que cortan el eje real, pues si resolvemos el denominador de la ecuacion obtenemos solo puntos imaginarios:

    Entonces, para encontrar los puntos donde los lugares de las raíces cortan el eje imaginario debemos resolver la ecuacíon caracteristica para s = jω.

    Los lugares de las raíces que cortan el eje imaginario son las raíces o ceros de la parte imaginaria de la ecuación final que obtuvimos, entonces, vamos a gráficar la parte imaginaria para obtener una aproximación de dichos puntos, para ello utilice gnuplot:

    Vemos que la gráfica corta el eje en los rangos (-2 : -1.5)(1.5 : 2), la gráfica es simétrica, entonces, reducimos el rango de visualizacion de un lado para obtener los puntos:

    Nuestra aproximación es  ω±1.88, entonces el eje imaginario se corta en los puntos 1.88 y -1.88

    Para obtener un valor mas preciso utilizaremos el Criterio de Routh (ver referencias).  Para encontrar los puntos despejamos k de la penúltima fila y la sustituyemos en la antepenúltima fila y la resolvemos.

    Asi comprobamos que los lugares de las raíces cortan el eje imáginario (s = jω) en los puntos ω±1.8708

    Gráficamos con Octave para comprobar, el eje X es el eje real, el eje Y es el eje imaginario. Podemos ver como la curva azúl corta el eje imaginario en los puntos ±1.8708, además hay 4 puntos adicionales conectados con 1 recta, estos corresponden a los puntos donde se corta el eje imaginario con el sistema a lazo abierto, estos puntos lo encontramos al resolver el denominador de la ecuacion de la imágen 3, es decir -2i, -1i, 1i y 2i


    martes, 9 de octubre de 2012

    [RNA] 2. Reporte de Avances

    En esta entrada explico los avances con los que he contribuido al proyecto de la clase de redes neuronales.

    Descripción del proyecto

    Recordando un poco, el proyecto consiste en desarrollar una libreria basada en redes neuronales que permita realizar predicciones de datos.

    Mas concretamente, detectar patrones de delincuencia basandonos en los historiales de eventos pasados para así poder predecir el posible aumento o disminución de actividad delictiva en ciertas zonas.

    El objetivo adicional es realizar un análisis más profundo que nos permita predecir en cuáles zonas es mas probable que aumente la actividad delictiva y en cuales sea probable que disminuya.


    Primeramente dedique algo de tiempo a desarrollar una neurona, el primer paso fue desarrollar una neurona que fuera capaz de separar datos linealmente. Con ésta neurona se pueden realizar clasificaciones simples de información.

    La neurona esta en el repositorio, la siguiente imagén muestra una gráfica con la clasificación de la información:

    El siguiente paso consistió en desarrollar un sistema de aprendizaje, en éste caso es un aprendizaje simple basado en la regla delta, para probar si el sistema de aprendizaje era exitoso realizé algunas pruebas con compuertas lógicas, la siguiente imágen muestra las compuertas lógicas AND y OR, la salida de la neurona es 1 o 0 dependiendo de las entradas, en éste caso el aprendizaje fue exitoso:

    Compuerta AND

    Compuerta OR

    Vale la pena mencionar que el siguiente paso consistió en realizar multicapas, el sistema multicapas funciona. Mediante un archivo de configuración es posible generar multiples capas, sin embargo, existe un problema entre la interconexión de las mismas; ésto lo pude constatar al intentar entrenar la neurona utilizando la compuerta XOR.
    En éste caso la configuración fue de 3 capas, con la siguiente configuración:

    • Capa 1, 2 neuronas, Aprendizaje 0.1
    • Capa 2, 2 neuronas, Aprendizaje 0.1
    • Capa 3, 1 neurona, Aprendizaje 0.1
    Los resultados no fueron los óptimos ya que para todos los casos obtuve siempre una salida 0:

    Compuerta XOR

    Para el siguiente paso se planea implementar backpropagation, sin embargo, planeamos implementarlo solo para efectos de práctica y conocimiento general, ésto lo explicaré un poco más adelante.


    La siguiente actividad realizada consistió en la recolección de información. Con base a la información logramos establecer la estructura básica de nuestra red neuronal.

    Para empezar, las entradas de nuestra red pueden ser de muy variados tipos, por ejemplo:
    • Escalas (nominal, intervalo, o relación)
    • Observaciones
      • Series de tiempo
    • Variables relacionadas
    La salida producida consistiría en algun aumento o disminución en los valores de escala, el siguiente o siguientes valores adicional en dada serie de tiempo o algúna conclusión obtenida de la conclusión delas varibles relacionadas.

    Nosotros elegimos como entradas las observaciónes en una serie de tiempo, por ejemplo:
    • Robos cada día.
    • Homicidios por mes
    Y la salida sería la observación u observaciones posteriores, por ejemplo, si nuestra entrada fueran las observaciones en cada mes de un año, entonces necesitaremos una red con una capa incial de tamaño 12, una neurona por cada mes.
    El tamaño de la capa de salida depende del número de observaciones que deseemos tener al final.

    Por ahora nuestra salida consistiría en datos binarios, es decir, un vector de 1 y -1 que indican si la serie de tiempo tiende a subir o a bajar, en pocas palabras, una tendencia. Posteriormente la salida sería un dato análogo entre 1 y -1 que indicaría la magnitud del cambio y finalmente traducir ese valor análogo según la escala de valores en la serie de tiempo.

    También se establecio un modelo de entrenamiento simple. Dado que estamos trabajando con series de datos existentes, podemos utilizar datos anteriores para entrenar, y calcular valores ya existentes, asi pues, los pasos serían:
    1. La entrada es una observación vieja, por ejemplo, datos del año 2010 para calcular los del año 2011
    2. Como conocemos los valores del 2011, comparar dichos valores con la salida de la red y calcular el error.
    3. Utilizar backpropagation para modificar los pesos y reducir el error en observaciones posteriores.
    4. Mover la serie de datos hacia adelante una vez para mostrar el siguiente patrón.

    Como tipo de aprendizaje elegimos el tipo no supervisado, ésta es la razón por la que ponemos en tela de duda el método de entrenamiento antes descrito, ya que, un aprendizaje no supervisado no tiene una salida esperada, sino que la salida se basa en identificar patrones (ideal), entonces realizar backpropagation resultaría complicado.


    Las conclusiones anteriores son el diseño básico de la red, asi pues, faltarían especificar algunas cosas un poco más detalladamente, por ejemplo:
    • Función de activación a utilizar
    • Número de capas ocultas
    • Elegir un mejor método de entrenamiento
    • Parámetros de entrenamiento
    • Combinar los anteriores y elegir el que mejores resultados proporcione.

    viernes, 5 de octubre de 2012

    [VVS] 7. Aplicaciones de la lógica predicativa

    Esta tarea consistio en investigar una aplicación práctica de la lógica de primer orden, el tema que elegí fue la aplicacion de la lógica de primer orden para la verificación de protocolos de seguridad


    Un protocolo es un conjunto de reglas que establecen cómo se debe realizar la transmisión de datos de cualquier tipo entre 2 entidades. Sin un protocolo común, los dos dispositivos pueden estar conectados pero no comunicarse.

    Un protocolo debe tener 3 caracteristicas:

    • Sintaxis (¿Cómo se comunica?) Orden en que se agrupan los datos para formar el mensaje.
    • Semántica (¿Qué se comunica?) Significado de cada parte del mensaje.
    • Temporización (¿Cuándo se comunica?) Cuándo se debe enviar el mensaje.

    En los protocolos de seguridad existen además 2 elementos importantes, cada uno con sis propieas caracteristicas:

    • Mensaje:
      • Confidencialidad
      • Integridad
      • Autenticación
      • No repudio
    • Entidades que se comunican:
      • Realizan autenticación

    Un protocolo de seguridad se compone habitualmente de dos partes:

    • Criptográfica: que es el cifrado de los datos
    • Lógica: que define la estructura y el orden de los mensajes.

    Protocolos de seguridad y lógica de primer orden

    La mayoría de las debilidades en un protocolo se encuentran en la parte lógica debido a que no es posible analizar todas las aplicaciónes que éste pueda tener, entonces las pruebas se limitan a suposiciones de cómo el protocolo será utilizado y bajo qué condiciones.
    La lógica de primer orden permite realizar un análisis previo a la liberación del protocolo.

    Para verificar un protocolo, hay que probar dos cosas:
    • Que el protocolo consigue sus objetivos (postcondiciones) cuando se ejecuta cada uno de los pasos especificados en el diseño (casos de uso del protocolo).
    • Que no hay posibilidad de un ataque (es decir, no se puede usar el protocolo de forma fraudulenta).

    Analicemos el caso del protocolo RSA, la parte criptográfica consiste en los siguientes pasos:

    • Se eligen dos primos muy grandes p y q.
    • Se calcula n = (p) (q), el cual será el módulo para cifrado y descifrado.
    • Se calcula φn = (p − 1) (q − 1).
    • Se elige un número aleatorio e y se calcula d, de forma que d = e-1 mod φn.
    • La pareja de numeros (e, n) forman la clave pública.
    • La pareja de números (d, n) forman la clave privada.

    Los mensajes se cifran con (e, n) y sólo se puede descifrar con (d, n) y viceversa.
    La seguridad del protocolo RSA depende del tamaño de n, ya que, dada la clave pública es posible obtener la clave privada factorizando n.

    La parte lógica del protócolo, por ejemplo, trata las siguientes cuestiones:

    • ¿Cómo saber si el usuario que dice ser Bob es realmente Bob?
    • ¿Es suficiente utilizar una contraseña?
    • ¿La contraseña debe ser cifrada con la clave pública del servidor? 
    • Analizar confidencialidad, integridad, autenticación, no repudio.

    La exactitud del protocolo (que éste sea correcto) se analiza definiendo axiomas y reglas de inferencia comunes de la logica de primer orden y adicionalmente se agregan axiomas que represetan las caracteristicas y propiedades de seguridad que debe tener el protocolo. Mediante esta sintaxis es posible demostrar algunas de las propiedades de seguridad del protocolo directamente.
    Estas pruebas logicas garantizan que las propiedades sean verdaderas y comprueba que el protocolo es robusto.

    Protocolo simétrico de Needham-Schroeder

    En éste protocolo cada mensaje se puede interpretar como una acción que modifica el estado de creencia de los individuos que intervienen en la comunicación

    Se necesitan enviar 3 mensajes para establecer una comunicación segura, cuando se han enviado los tres mensajes cada uno de los agentes sabe que el otro es quien dice ser.

    Las condiciones iniciales del protocolo son las siguientes:
    • S es un servidor confiado por ambas partes
    • KAS es una clave simétrica que conocen sólo A y S
    • KBS es una clave simétrica que conocen sólo B y S 
    • NA y NB son nonces (número, puede ser pseudoaleatorio, de un solo uso que se usa como un sencillo método adicional de autenticación).

    Las propiedades del protocolo, utilizando la lógica de primer orden, se escriben de la siguiente forma:

    • A → S : A,B,NA
    • S → A : {NA, KAB, B, {KAB, A}KBS}KAS
    • ==============================================
    • A → B : {KAB, A}KBS
    • B → A : {NB}KAB
    • A → B : {NB-1}KAB

    El protocolo se lee de la siguiente forma:

    • Alice se comunica con el servidor, se identifica a si misma y a Bob y envía un nonce. (Solicta comunicarse con Bob)
    • Servidor responde a Alice, genera la clave KAB y la envía a Alice junto con el nonce y la autenticación de Bob, además envía un paquete con la clave KAB y la autenticación de Alice, cifrado con la clave KBS (que solo Bob y el servidor conocen). La totalidad de la información esta cifrada con la clave que solo Alice y el servidor conocen.

    Los tres mensajes de autenticación consisten en lo siguiente:

    • Alice decifra la información, recupera el nonce (garantiza que la información corresponde a su sesión y que es reciente), la clave KAB y la autenticación de Bob. Como hay un paquete cifrado con KBS el paquete se envía a Bob para que también tenga su copia de la clave KAB. y de la autenticación de Alice.
    • Bob responde a Alice con un nonce cifrado con KAB (clave que solo conocen Alice y Bob), con ello demuestra que recibio la clave.
    • Alice responde a Bob con un nonce modificado (mediante una operación simple) cifrado con la clave , con ello demuestra que tiene la clave también.

    Asi queda comprobado que Alice y Bob son quien dicen ser.

    Protocolo de clave pública de Needham-Schroeder

    Las condiciones iniciales para éste protocolo son:

    • KPA y KSA claves pública y privada de Alice.
    • KPB y KSB claves pública y privada de Bob.
    • KPS y KSS claves pública y privada del servidor.

    Utilizando lógica de primer orden, el protocolo se representa de la siguiente forma:

    • A → S : A, B
    • S → A : {KPB, B}KSS
    • A → B : {NA, A}KPB
    • B → S : B, A
    • S → B : {KPA, A}KSS
    • B → A : {NA, NB}KPA
    • A → B : {NB}KPB

    El protocolo se lee:

    • Alice solicita al servidor la clave pública de Bob
    • El servidor responde con la cláve pública de Bob y con si identidad, la información esta cifrada con la clave secreta del servidor.
    • Alice conoce la clave pública del servidor, decripta la información y envía un nonce a Bob con su identidad, todo cifrado con la clave publica de Bob.
    • B solicita al servidor la cláve pública de Alice.
    • El servidor responde con la cláve pública de Alice y con si identidad, la información esta cifrada con la clave secreta del servidor.
    • Bob genera otro nonce y lo envía a Alice junto con el nonce que recibio de Alice, la información va encriptada con la clave pública de Alice.
    • Alice reponde a Bob con el nonce recibido NB, encriptado con la clave pública de Bob.

    Al finalizar el protocolo, Alice y Bob estan seguros de ser quien decían ser.

    Lógica de BAN

    Es un método formal que permite difinir y analizar las propiedades de los protocolos. Fue
    desarrollado con los aportes de Michael Burrows, Martin Abadi y Roger Needham.
    Es una extensión de la lógica de primer orden que se basa en creencias de los agentes que participan en el protocolo.


    Lógica de BAN intenta responder las siguientes preguntas:
    • ¿Cuál es el objetivo del protocolo a analizar?
    • ¿El protocolo necesita mas suposiciones que algún otro?
    • ¿El protocolo realiza una acción innecesaria que puede eliminarse sin debilitarlo?
    • ¿El protocolo encripta información que puede ser enviada en texto plano sin debilitarlo?


    La principal limitación es que siempre asume una criptografia perfecta:
    • Los agentes nunca publican la información secreta, pero no se encarga de verificar que se cumpla.
    • Los agentes reconocen los fallos, pero no verifica la ausencia de los mismos.
    • Los agentes reconocen o ignoran mensajes enviados por ellos mismos.
    • Los agentes son honestos.
    • Agentes comprometidos no estan considerados
    • Los atacantes no tienen claves válidas.

    • Identificadores para los agentes. (A, B, C, ...)
    • Identificadores para las llaves. (k)
    • Identificadores para funciones atomicas. (n)
    • Conjunto de formulas. (X , Y, Z, ...)

    Las formulas pueden ser expresadas por ejemplo: "A cree que k es una llave compartida entre A y B", y dan siempre como resultado verdad o falso.


    1. P cree X: P tiene razones para creer que el mensaje X es verdad.
    2. P ve X: P puede ver el mensaje X y puede reproducirlo.
    3. P dijo X: En algún momento P envió el mensaje X.
    4. Fresco(X): El mensaje X pertenece al presente (sesión actual) y no ha sido utilizado antes.
    5. P controla X: P tiene pertenencia sobre X. (Tiene, controla, o conoce)
    6. P y Q comparten la llave K, K es buena para establecer comunicación entre ambos.
    7. P tiene la clave pública K
    8. X es un secreto solo y solo entre P y Q
    9. X combinada con la función Y.
    10. {X}K : X encriptada con la llave K

    Algunos ejemplos donde se aplican las anteriores formulas son las siguientes formulas:

    P cree que la llave K esta compartida con Q. P vee que X esta encriptado con la llave pública K. Entonces P cree que Q dijo X.
    P cree que Q tiene la llave publica K. P vee que X esta encriptado con la llave privada K-1. Entonces P cree que Q dijo X.
    P cree que Y es un secreto entre él y Q. P vee que X se utiliza en la fórmula Y. Entonces P cree que Q dijo X
    P cree que X fue mencionado recientemente. Q alguna vez dijo X. Entonces P cree que Q cree en X.
    P cree que a Q le pertenece X. P cree que Q cree en X. Entonces P cree en X.

    Protocolo Needham-Schroeder y Lógica de BAN

    Como ejemplo, vamos a analizar el protocolo Needham-Schroeder (especificado más arriba) utilizando la lógica de BAN.

    Recordando las condiciones iniciales:

  • KA y KA-1 claves pública y privada de Alice.
  • KB y KB-1 claves pública y privada de Bob.
  • KS y KS-1 claves pública y privada del servidor.

  • Las propiedades del protocolo quedarían de la siguiente forma:

    A cree que tiene la llave pública KA B cree que tiene la llave pública KB
    A cree que S tiene la llave pública KS B cree que S tiene la llave pública KS
    S cree que A tiene la llave pública KA S cree que B tiene la llave pública KB
    S cree que tiene la llave pública KS
    A cree que S conoce la llave de B B cree que S conoce la llave de A
    A cree que su nonce NA es reciente (fresco) B cree que su nonce NB es reciente (fresco)
    A cree que su nonce NA es un secreto entre él y B B cree que su nonce NB es un secreto entre él y A
    A cree que el mensaje con la llave pública de B, KB es reciente B cree que el mensaje con la llave pública de A, KA es reciente

    En resumen, cada uno A y B tienen un par de llaves las cuales con conocidas por S. Los nonces son creados para esa sesión especifica y cada uno conoce su nonce. Ambos utilizan sus llaves públicas durante la sesión de comunicación.

    Ahora, la debilidad del protocolo se encuentra justamente en las 2 ultimas creencias, a pesar de que son llaves públicas, A y B no conocen las llaves del otro hasta que cada uno la envía al otro, esto provoca que dicho mensaje no sea fresco, sino que pudo haber sido envíado por un tercero quien lo encripto previamente. Para solucionar este problema de agregan 4 creencias más:

    A cree que B tiene la llave pública KB B cree que A tiene la llave pública KA
    A cree que B cree que el nonce NA es un secreto entre ellos B cree que A cree que el nonce NB es un secreto entre ellos

    Ahora, ambos confirman su llave pública mutuamente y además intercambian su nonce para asegurar que es fresco en ambos casos, ahora ambos creen que el otro dice la verdad por lo que pueden continuar el intercambio de información.