[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:

CHAPTER I.
WHICH TREATS OF THE CHARACTER AND PURSUITS OF THE FAMOUS GENTLEMAN DON QUIXOTE OF LA MANCHA

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...

Code:

To download the code:

wget https://raw.github.com/gist/3991979/8d4098ded0ed08db6870121bdd8c13f343a211e3/stegano.py

To download the images:

https://docs.google.com/open?id=0B_0N8wEsinLfWUpWOXVmcldWVHc

  

To encode information:

python stegano.py -E

To decode information

python stegano.py  -D

Then, enter the requested data.

[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.

Componentes:

• 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:

Componente	Descripción	Modelado
Cajero	Estados {0} Espera {1} Orden recibida {2} Orden cobrada Acciones {Rec} Recibir la orden {Cob} Cobrar la orden {Pas} Pasar la orden a cocina
Cocina	Estados {0} Espera {1} Orden recibida {2} Orden preparada Acciones {Pas} Pasar orden (recibirla del cajero) {Pre} Preparar la orden {Ser} Servir la orden
Ayudante	Estados {0} Espera {1} Orden entregada Acciones {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

Referencias:

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

[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.

Solución

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];

Ejecución:

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.

Ejecución:

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});

Ejecución:

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 U₁(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.

Referencias:

• http://elisa.dyndns-web.com/~elisa/teaching/sys/control/frecuencia.pdf
• http://elisa.dyndns-web.com/~elisa/teaching/sys/control/estados.pdf

[SC] 8. Stream ciphers: Grain

Introduction

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).

Background

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.

Specification

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 (z_t) t = 0,...,L−1.

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

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

f(x) = 1 ⊕ x¹⁸ ⊕ x²⁹ ⊕ x⁴² ⊕ x⁵⁷ ⊕ x⁶⁷ ⊕ x⁸⁰

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

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

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

g(x) = 1 ⊕ x¹⁷ ⊕ x²⁰ ⊕ x²⁸ ⊕ x³⁵ ⊕ x⁴³ ⊕ x⁴⁷ ⊕ x⁵² ⊕ x⁵⁹ ⊕ x⁶⁵ ⊕ x⁷¹ ⊕ x⁸⁰ ⊕ x¹⁷x²⁰ ⊕ x⁴³x⁴⁷ ⊕ x⁶⁵x⁷¹ ⊕ x²⁰x²⁸x³⁵ ⊕ x⁴⁷x⁵²x⁵⁹ ⊕ x¹⁷x³⁵x⁵²x⁷¹ ⊕ x²⁰x²⁸x⁴³x⁴⁷ ⊕ x¹⁷x²⁰x⁵⁹x⁶⁵ ⊕ x¹⁷x²⁰x²⁸x³⁵x⁴³ ⊕ x⁴⁷x⁵²x⁵⁹x⁶⁵x⁷¹ ⊕ x²⁸x³⁵x⁴³x⁴⁷x⁵²x⁵⁹

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

b_t+80 = s_t ⊕ g(b_t, b_t+1, . . . , b_t+79)

where:

g(b_t, b_t+1, . . . , b_t+79) = b_t+63 ⊕ b_t+60 ⊕ b_t+52 ⊕ b_t+45 ⊕ b_t+37 ⊕ b_t+33 ⊕ b_t+28⊕ b_t+21 ⊕ b_t+15 ⊕ b_t+9 ⊕ b_t ⊕ b_t+63b_t+60 ⊕ b_t+37b_t+33 ⊕ b_t+15b_t+9 ⊕ b_t+60b_t+52b_t+45 ⊕ b_t+33b_t+28b_t+21 ⊕ b_t+63b_t+45b_t+28b_t+9 ⊕ b_t+60b_t+52b_t+37b_t+33 ⊕ b_t+63b_t+60b_t+21b_t+15 ⊕ b_t+63b_t+60b_t+52b_t+45b_t+37 ⊕ b_t+33b_t+28b_t+21b_t+15b_t+9 ⊕ b_t+52b_t+45b_t+37b_t+33b_t+28b_t+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 s_t+3, s_t+25, s_t+46, s_t+64 and b_t+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.

Grain, from http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf

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.

Grain, from http://www.ecrypt.eu.org/stream/p3ciphers/grain/Grain_p3.pdf

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(2^n/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(2⁸⁰)."

References

http://events.iaik.tugraz.at/RFIDandLightweightCrypto05/RFID-SlidesandProceedings/Johansson-Grain.pdf

http://edipermadi.wordpress.com/tag/nfsr/

http://edipermadi.files.wordpress.com/2008/06/grain-spec.pdf

http://www.ecrypt.eu.org/stream/e2-grain.html

http://www.iacr.org/cryptodb/archive/2006/FSE/3235/3235.pdf
http://en.wikipedia.org/wiki/Linear_feedback_shift_register
http://cacr.uwaterloo.ca/techreports/2011/cacr2011-08.pdf

[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.

http://astreo.ii.uam.es/~jlara/doctorado.2006/tema7.pdf

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).

Ejemplo de Red de Petri: http://www.uhu.es/diego.lopez/AI/auto_trans-tema3.PDF

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.

Actividad

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:

Estados	Transiciones
Esperando Agua seleccionada Café seleccionado Si hay café Si hay agua Bebida servida No hay café No hay agua	Selecciona bebida Verificar café Verificar agua Servir bebida Limpiar filtro Aviso error

El dibujo queda algo asi:

Utilizando python-snakes:

Diagrama animado:

Código:

Referencias
http://pommereau.blogspot.mx/search/label/SNAKES
http://pommereau.blogspot.mx/2010/01/first-steps-with-snakes.html
http://pommereau.blogspot.mx/2010/01/firing-rule-in-snakes.html
http://pommereau.blogspot.mx/2010/01/snakes.html
http://code.google.com/p/python-snakes/source/browse/doc/tutorial.txt?spec=svn.abcd.b7e58afd5c1b845899816065fff49d782e02a56b&repo=abcd&r=b7e58afd5c1b845899816065fff49d782e02a56b
http://www.uhu.es/diego.lopez/AI/auto_trans-tema3.PDF

[SC] 7. Block Ciphers: PRESENT

Introduction

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).

http://en.wikipedia.org/wiki/PRESENT_(cipher)

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

Background

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

• GE (Gate Equivalent): http://en.wikipedia.org/wiki/Gate_equivalent. Refers to a physical area, one GE is equivalent to the area which is required by the two-input NAND gate with the lowest driving strength of the corresponding technology. The area in GE is derived by dividing the area in µm² by the area of a two-input NAND gate.
• SP (Substitution-Permutation): http://en.wikipedia.org/wiki/Substitution-permutation_network
• S-Box (Substitution Box): http://en.wikipedia.org/wiki/S-box
• P-Layer or P-Box (Permutation Layer/Box): http://en.wikipedia.org/wiki/Permutation_box

Specification

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 K_i = [K₆₃, K₆₂, ..., K₁, K₀], and a current state b_i = [b₆₃, b₆₂, ..., b₁, b₀]; the key mixing step addRoundKey consists in a XOR operation:

b_j = b_j ⊕ K_j; 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:

PRESENT cipher S-box, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

• 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.

PRESENT cipher P-box, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

• 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:

PRESENT cipher SP-Network, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

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

PRESENT cipher pseudocode, from http://www.lightweightcrypto.org/present/present_cardis2008.pdf

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.

Vulnerability

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"

Referencias

http://www.lightweightcrypto.org/present/present_cardis2008.pdf
http://www.lightweightcrypto.org/present/present_ches2007.pdf
http://www.emsec.rub.de/media/crypto/veroeffentlichungen/2011/01/29/present_ches2007_slides.pdf
http://homes.esat.kuleuven.be/~abogdano/talks/present_rfidsec07.pdf
http://math.fau.edu/~eisenbarth/pdf/SLEsolvers.pdf

http://www.lightweightcrypto.org/implementations.php

[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ω.


Solución:

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





Referencias:

• http://gama.fime.uanl.mx/~agarcia/materias/ingco/apclas/07%20-%20Criterio%20de%20Estabilidad%20de%20Routh.pdf
• http://materias.fi.uba.ar/7609/material/Clase%2004/06%20Lugar%20de%20Raices.pdf
• http://es.wikipedia.org/wiki/Unidad_imaginaria
• http://www.esi2.us.es/~asun/TCA07/T2-5.pdf
• http://gama.fime.uanl.mx/~agarcia/materias/ingco/apclas/08%20-%20Analisis%20del%20Lugar%20Geometrico%20de%20la%20Raices.pdf

[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.

Contribuciones

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.

Investigación

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.

Fuente: http://www.neural-forecasting.com/Downloads/EVIC05_tutorial/EVIC'05%20Slides%20-%20Forecasting%20with%20Neural%20Networks%20Tutorial%20SFCrone.pdf

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.

Ejemplo arquitectura, fuente: http://www.neural-forecasting.com/Downloads/EVIC05_tutorial/EVIC'05%20Slides%20-%20Forecasting%20with%20Neural%20Networks%20Tutorial%20SFCrone.pdf

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.

Pendientes

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.

Repositorio: https://www.github.com/rafaellopezgtz/neurored

Referencias

• http://www.neural-forecasting.com/Downloads/EVIC05_tutorial/EVIC'05%20Slides%20-%20Forecasting%20with%20Neural%20Networks%20Tutorial%20SFCrone.pdf
• http://www.ic.unicamp.br/~wainer/cursos/mo416/forecast-nn.pdf
• http://www.obitko.com/tutorials/neural-network-prediction/prediction.html

[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

Definición

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
• K_AS es una clave simétrica que conocen sólo A y S
• K_BS 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, K_AB, B, {K_AB, A}_KBS}_KAS
• ==============================================
• A → B : {K_AB, A}_KBS
• B → A : {N_B}_KAB
• A → B : {N_B-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 K_AB 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 K_AB y la autenticación de Alice, cifrado con la clave K_BS (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 K_AB y la autenticación de Bob. Como hay un paquete cifrado con K_BS el paquete se envía a Bob para que también tenga su copia de la clave K_AB. y de la autenticación de Alice.
• Bob responde a Alice con un nonce cifrado con K_AB (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:

• K_PA y K_SA claves pública y privada de Alice.
• K_PB y K_SB claves pública y privada de Bob.
• K_PS y K_SS 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 : {K_PB, B}_KSS
• A → B : {NA, A}_KPB
• B → S : B, A
• S → B : {K_PA, 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.

Objetivo

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?

Limitaciones

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.

Sintaxis

• 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.

Formulas

Tomada de http://wwwhome.cs.utwente.nl/~sape/sse/ban.pdf

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.

Fuente: A Logic of Authentication

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:

K_A y K_A^-1 claves pública y privada de Alice.

K_B y K_B^-1 claves pública y privada de Bob.

K_S y K_S^-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.



Referencias

• Wikipedia: Protocolo de Needham-Schroeder
• University of Cambridge Computer Laboratory: A Logic of Authentication
• BAN Logic: A Logic of Authentication by Sape J. Mullender
• Verification of Security Protocols Chapter 6: BAN Logic by Christian Haack
• Métodos formales para la verificación de protocolos: http://grupo.us.es/ghum609/php/system/files/fernando1.pdf
• Protocolos de seguridad: http://ldc.usb.ve/~poc/Seguridad/protocolos.pdf