[CRIPTOGRAFÍA] Código de Esteganografía

Este es el código tal y como se encuentra dentro de las 3 imagenes que seleccioné, incluye las variables de prueba y variables comentadas que no quité porque cuando me di cuenta ya estaban subidas. Utilizé el bit más bajo para sobreescribir el binario del texto, si el valór ya existe, es pasa por alto. Descargar
Realizé un ejemplo visible para ver los lugares donde se realizan los cambios, simplemente le dije al programa que en lugar de guardar el rgb de la imagen, guarde un color estatico:

La imagen original luce de esta manera:

La imagen modificada luce (internamente) de esta manera:

Los amarillos, rojos, azules y verdes representan los pixeles modificados.

La esquina inferior derecha guarda el ultimo bit escrito, el pixel de diferente color para x y y representa el pixel de fin de lectura, en este caso el amarillo es el ultimo pixel, esa esquina tiene sus coordenadas representadas en bits:




Y este es el código para desencriptar: Descargar
Y las imagenes modificadas fueron la 1, la 3 y la 4 ;)

El resto de imagenes las convertí a png solo para despistar

[CRIPTOGRAFÍA] Imágenes

Imagen 1

Imagen 2

Imagen 3

Imagen 4

Imagen 5

Imagen 6

[CRIPTOGRAFÍA] Stream Cipher - HC-128/HC-256

Cifrado de flujo

Esta semana investigamos sobre cifras de flujo. A diferencia de el cifrado por bloques que utiliza bloques de información de tamaño constante, el cifrado de flujo utiliza un generador de flujo de clave para operar con cada bit o cada caracter del texto plano.

Generalmente el generador es un algoritmo que recibe una entrada aleatoria (una clave) y a partir de esta genera una salida datos continua pseudoaleatoria.

Para generar esta salida, se aplica un algoritmo hash a la contraseña de longitud variable y se obtiene una contraseña de longitud fija.

Se puede utilizar una contraseña tan larga como la cantidad de datos que se cifran, lo cual es una de las fortalezas de los sistemas de cifrado.

HC-256

Escogí un algoritmo llamado HC-256. HC-256 es un cifrado de flujo diseñado para proporcionar cifrado masivo de software a gran velocidad mientras que permite una gran confianza en su seguridad. Su variante HC-128 fue presentado como un candidato eSTREAM y fue uno de los 4 finalistas en el perfil de software.

HC-128 y HC-256 son algoritmos adecuados para microprocesadores superescalares modernos y futuros. Sus pasos se pueden calcular en paralelo tanto de entrada como salida.

La velocidad de codificación de HC-128 llega a 3,05 ciclos / byte en un procesador Intel Pentium

M mientras que HC-256 llega a los 4.2 ciclos / byte en un procesador Intel Pentium 4.

Algoritmo

El proceso de cifrado para HC-256 consiste en lo siguiente:

• Inicialmente se necesita una clave (K) de 256 bits y un vector de inicialización (IV) de 256 bits.
• Internamente, consiste en dos tablas secretas (P y Q), cada una contiene 1024 palabras de 32 bits.
• EL flujo de clave (s) es generado del mismo algoritmo. La salida de 32 bits del paso i es denotada como si. Así que s = s0 || s1 || s2...

Hay 6 funciones en el algoritmo. Para g1(x) y h1(x) la tabla Q es usada como S-box y para g2(x) y h2(x) la tabla P es al S-box.

donde x = x3 || x2 || x1 || x0, x es una palabra de 32 bits, x0, x1, x2 y x3 son 4 bytes, x3 y x0 son los bytes mas y menos significativos respectivamente.

El código en python de estas formulas es como sigue:

Con respecto al proceso de inicialización, serán 4096 pasos antes de generar alguna salida, se expande K y IV dentro de un vector W, esto para actualizar las S-box P y Q.

El código en python para esta parte: En la ultima parte generaremos el flujo de clave s y se generará por cada paso una salida de 32 bits. También se actualiza cada tabla P o Q dependiendo de los datos que se operan. El código de esta parte es: Y de esta manera con la salida s generamos el flujo de clave que al final solo se aplicara XOR a el mensaje. La cantidad de pasos en el código es fija, pero lo recomendable es que sea indeterminada o bien de largo del mensaje.

El código completo es:

La captura de pantalla mostrando el resultado de s:

Seguridad

El cifrado es seguro y casi impenetrable, se han probado con ataques algebraicos sin resultados positivos para el atacante. La salida de el cifrado es proveniente de una función no lineal por lo que recuperar la contraseña es casi imposible.

Sin embargo al conocer parte del texto plano surge el problema, ya que en base a otros ataques de diccionario en combinacion con álgebra se puede recuperar parte de la clave y el vector de inicialización.

Lo que hace seguro el sistema es el uso de claves aleatorias de largo igual que el mensaje y de cifrados múltiples, pero eso es aplicando en todos los algoritmos en general. Lo que le da la seguridad extra es el uso de las tablas S-box P y Q que reciben cambios casi en cada paso, lo que la vuelve difícil de decifrar sin la clave.

Fuentes:

Wikipedia
Link 1
Link 2
PDF oficial
PDF de HC-128

[CRIPTOGRAFÍA] Block Cipher - FROG

Cifrado por bloques

Esta semana se encargó investigar sobre alguna unidad de cifrado por bloques, una unidad de cifrado de clave simétrica que opera en grupos de bits de longitud fija, llamados bloques, aplicándoles una transformación invariante.

Cuando realiza cifrado, una unidad de cifrado por bloques toma un bloque de texto plano como entrada y produce un bloque de igual tamaño de texto cifrado.

La transformación exacta es controlada utilizando una segunda entrada — la clave secreta. El descifrado es similar: se ingresan bloques de texto cifrado y se producen bloques de texto plano.






FROG

Para mi ejemplo, encontré un algoritmo llamado FROG. FROG es un algoritmo de cifrado por bloques realizado por Georgoudis, Leroux y Chaves. Puede trabajar con bloques de tamaño entre 8 y 128 bytes, con tamaños de clave comprendidos entre los 5 y los 125 bytes. El algoritmo consiste en 8 rondas y tiene un desarrollo de la clave muy complicado.

Se envió en 1998 a la competición AES como candidato para convertirse en el Advanced Encryption Standard. En 1999, David Wagner y otros encontraron un número de claves débiles para FROG, que afectaba aproximadamente a una cada mil millones. Otros problemas eran un inicio de la clave muy lento y una velocidad de cifrado relativamente lenta. FROG no llegó a ser elegido finalista.

Algoritmo

Frog opera de la siguiente manera:

Primero que nada se necesitan de ciertas cosas antes de empezar:

• Clave de 16 bytes.
• Una S-box invertible de 8 entradas, 8 salidas dependiente de la clave.
• Una secuencia de 0 a 15 ordenada en forma aleatoria.

Esto teniendo en cuenta que necesitamos los bloques aleatorios y nuestro texto plano.

Cada ronda consiste en 16 pasos; uno para cada byte del bloque, en cada paso se realiza lo siguiente:

1. Se aplica un XOR al byte seleccionado del texto con el de la clave.
2. Se reemplaza el resultado por el sustituto en la S-box.
3. Se hace XOR con el byte del bloque correspondiente y se toma el resultado.
4. Se toma un número de la secuencia que corresponde a la posición de un byte del bloque y se hace XOR con ese byte.
5. Se repiten los pasos.

Ejemplo

Haré un ejemplo sencillo con un "hola mundo". Trataré de cifrar el texto y de decifrarlo utilizando un bloque. Primero que nada se transforma la cadena en binario para hacer las operaciones. y se agregarán ceros para completar los 16 bytes, quedando de la siguiente manera:

"h" - 01101000 

"o" - 01101111 

"l" - 01101100 

"a" - 01100001 

" " - 00100000 

"m" - 01101101 

"u" - 01110101 

"n" - 01101110 

"d" - 01100100 

"o" - 01101111 

"0" - 00110000 

"0" - 00110000 

"0" - 00110000 

"0" - 00110000 

"0" - 00110000 

"0" - 00110000

Se genera una clave de 16 bytes aleatoria formateada en binario:

01100011 00110011 00110000 00101010 10101111 11011100 01100101 11111001

01100110 01010110 11111100 10000011 10001000 11111111 10000100 10101000

Se genera una secuencia de números del 0 al 15:

10   8   9   2  12   5   4  11   6   1  14  15  13   7   3   0

Se toma la posición 0 y se procede:

01101000

01100011

________

00001011

La S-box:

El valor del S-box de 0000 - 1011 es: 01011000 y se reemplaza por 00001011 y viceversa para generar los bloques de decifrado.

El bloque 1 es :

11110011 11110111 01101101 10000111 01011010 00100011 00101110 01011010

11101000 11111111 10111101 11110000 01011101 01001100 11010011 10010100

Se toma el primer valo:

11110011

01011000

________

10101011

Se toma el segundo valor según la secuencia:

11111111

10101011

________

01010100

Se guarda el valor como cifrado.

Los primeros números resultantes con este procedimiento son:

01010100

01000110

10000100

10110011

...

Para obtener el Texto plano se hace el mismo procedimiento pero desde atrás hacia adelante.

Ventajas y desventajas

Como se había mencionado antes, FROG era uno de los algoritmos que participó en la competencia para ser el próximo AES pero no fue seleccionado para las finales.

Tambien se mencionó que el algoritmo tiene debilidades frente a ciertas claves afectando una en mil millones. Sin embargo la debilidad que tiene es fácil de resolver aplicando en sus últimas 4 rondas el modo de descifrado.

FROG no es rápido al ejecutar, debido a que genera las claves de una manera lenta, sin embargo es rápido encriptando y desencriptando. Por lo que se si generan las claves anteriormente no debería ser un problema.

[CRIPTOGRAFÍA] RSA-Based Digital Signatures

Para esta semana hicimos un servicio web de autenticación de usuarios, la cual guarda las claves públicas.

Para esto se hicieron 3 códigos, 2 en python con la ayuda de la librería CGI (Interfaz de entrada común) de python y un ultimo código en HTML simple que le envía los datos al script que autentifica el usuario. Todo esto corriendo en el servidor local.

La página es así:

Y el código es un simple HTML:

<form method = "get" action="http://localhost/cgi-bin/main.py">

<table border=0>
<tr>
    <td><font face="arial">Challenge</font></td>
    <td>
    <input type=text name="x">
    </td>
</tr>

<tr>
    <td><font face="arial">Usuario</font></td>
    <td>
    <input type=text name="user">
    </td>
</tr>

<tr>
        <td><font face="arial">Respuesta</font></td>
        <td>
        <input type=text name="r">
        </td>
</tr>

<tr>
    <td></td>
    <td colspan=2>
    <input type="submit" value="Enviar">
    </td>
</tr>
<tr>
    <td></td>
    <td colspan=2>
    <font face="arial"><a href="http://localhost/respuesta.py" target="_blank">Descargar Script</a></font>
    </td>
    </tr>
</table>
</form>

Al colocar los datos redirecciona a el script que autentifica al usuario, el código es así:

#!/usr/bin/python

import cgi 

def f(x):
    return x*2

def fastmodexp(x, y, mod):
    p = 1
    aux = x
    while y > 0:
        if y % 2 == 1:
            p = (p * aux) % mod
        aux = (aux * aux) % mod
        y = y >> 1
    return p

def public_key(user):
  keys = open("usuarios", "r")
  for line in keys:
      usuario, e, n = line.split(" ")
      if usuario == user:
          return int(e), int(n)

print "Content-type: text/html"
print
print "<html><head><title>Respuesta</title></head><body>"
form = cgi.FieldStorage()
x = int(form.getvalue("x"))
user = form.getvalue("user")
r = int(form.getvalue("r"))
e, n = public_key(user)
y = fastmodexp(r, e, n)
z = f(x)
if y == z:
      print "Si es "+ user
else:
      print "No es "+ user
print "</body></html>"

El programa anterior lo que hace es recibir los datos del html, despues comprueba que el usuario que hace referencia tiene su clave correcto, esto lo hace con un "y" que es "fastmodexp" que en si es [(r ^ e) mod n] para calcular f(x) con los datos del usuario al que se hace referencia y se usa "z" para calcular directamente f(x).

Al final se hace una comparacion, si ambas "y" y "z" son iguales se trata de el usuario correcto.

El usuario que esta en duda descarga el siguiente script:

#!/usr/bin/python

def f(x):
  return x*2

def fastmodexp(x, y, mod):
    p = 1
    aux = x
    while y > 0:
        if y % 2 == 1:
            p = (p * aux) % mod
        aux = (aux * aux) % mod
        y = y >> 1
    return p


def main():
   x = int(raw_input("x:"))
   d = int(raw_input("d:"))
   n = int(raw_input("n:"))
   y = f(x)
   res = fastmodexp(y, d, n)
   print "Respuesta = %s"%res
main()

El script genera una respuesta para "x" utilizando fastmodexp que es [(y ^ d) mod n] la cual el usuario entrega en el chat para quien quiere autentificar que realmente es el.

Ahora se muestra un ejemplo para una "x" = 79, quiero saber que el usuario Victor cuya clave públca es (e = 2903, n = 5917) y su clave privada es (d= 1127, n= 5917).

"Victor" descarga el script y lo ejecuta, como el es el único que sabe su clave privada estara seguro de su respuesta.

Por chat envia 229 y el otro usuario comprueba en la página:

La respuesta es:

En caso de una respuesta por parte de "Victor" que no sea 229:

[CRIPTOGRAFÍA] Diffie–Hellman key exchange

En grupos de 3 personas, nos dimos a la tarea de realizar un ejercicio en el que utilizaríamos el protocolo Diffie–Hellman, así los roles de mi compañeros René y Emmanuel fueron de Alice y Bob, y el mio de Eve, ellos compartieron datos públicamente:

Como Eve, traté de obtener la llave "K" mediante fuerza bruta, osea, checar todas las combinaciones posibles.

Para esto utilicé las formulas siguientes:

X = g^x % p

Y = g^y % p

K = X^y % p = Y^x % p

Así tendría que sustituir "x" y "y" en la fórmula por cualquier número hasta obtener "X" y "Y".

Realicé a mano los problemas ya que era parte de la tarea hacerlos a mano, cosas como elevar un número grande a una potencia grande lo realicé con calculadora.

Obtuve x = 4 y y = 7, cabe mencionar que la "x" de René era x = 13, pero no afecta ya que 4 o 13 ambos resultan en la misma "K", de hecho esto es repetitivo, cada cierto numero de veces encontraremos una "x" o una "y" que resultan en la misma "K", esto se debe a que el generador "g" no es muy eficiente, al menos si cada 9 números hay una "x" o una "y" como en mi caso.

Al final obtuve una K = 5 y lo comprobé:

[CRIPTOGRAFÍA] Análisis OTP

En esta entrada se hará un análisis a los resultados arrojados por el OTP de la tarea 1, en este caso utilizaré el código de mi compañero Emmanuel ya que no lo tengo de la primera tarea.

El análisis consiste en realizar pruebas estadísticas a las llaves generadas. Existen varias pruebas, yo utilizaré el Test Monobit.

Generé 10 llaves utilizando los caracteres "abcdefghijklmnopqrstuvwxyz,.;: ", en el texto a encriptar se eliminaron caracteres no pertenecientes a los ASCII, y se utilizaron minúsculas.

Empecé buscando la frecuencia con la que aparecen ciertos caracteres en las distintas llaves, en las imágenes siguientes se muestran las frecuencias con la que aparecen los caracteres "abcdefghijklmnopqrstuvwxyz,.;: " en ese orden. Fueron tomadas 4 llaves para la prueba.

Hay una gran cantidad de caracteres que se repiten varias veces como desde la "e" a la "k", mientras que otros ni aparecen.

Código para obtener frecuencias:

def frecuencia(file):
    text = open(file,"r").read()
    abc = "abcdefghijklmnopqrstuvwxyz,.;: "
    cadena = ""
    x=0
    for element in abc:
        print element, 
        for character in text:
            if character == element:
                x+=1
        print x
        cadena+=str(element)+" "+str(x)+"\n"
        x = 0
    return cadena

for i in range(10):
    archivo = open("frecuencia_"+str(i)+".txt", "w")
    archivo.write(frecuencia("cifrado_"+str(i)+".txt"))

Para analizar más profundamente se realizó un test de frecuencias Monobit basado en trabajos anteriores. Los resultados fueron los siguientes:

Al parecer el generador de llaves no es completamente random.











Código para frecuencias Monobit

from math import sqrt, erfc, fabs

def monobit(texto):
    suma = 0
    for letra in texto:
        if letra == "0":
            suma += 1
        else:
            suma -= 1
    sobs = fabs(suma)/sqrt(len(texto))
    p = erfc(sobs/sqrt(2))
    if(p > 0.0001):
        print "RANDOM! :D " + str(p)
    else:
        print "NO RANDOM :C " + str(p)

for i in range(10):
    file = open("binario_"+str(i)+".txt", "r").read()
    monobit(file)

Despues de las pruebas decidi hacerlas de nuevo pero esta vez con un texto más pequeño, mi primer texto era:

en un lugar de la mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivia un hidalgo de los de lanza en astillero, adarga antigua, rocin flaco y galgo corredor. una olla de algo mas vaca que carnero, salpicon las mas noches, duelos y quebrantos los sabados, lantejas los viernes, algun palomino de anadidura los domingos, consumian las tres partes de su hacienda. el resto della concluian sayo de velarte, calzas de velludo para las fiestas, con sus pantuflos de lo mesmo, y los dias de entresemana se honraba con su vellori de lo mas fino. tenia en su casa una ama que pasaba de los cuarenta, y una sobrina que no llegaba a los veinte, y un mozo de campo y plaza, que asi ensillaba el rocin como tomaba la podadera. frisaba la edad de nuestro hidalgo con los cincuenta anos; era de complexion recia, seco de carnes, enjuto de rostro, gran madrugador y amigo de la caza. quieren decir que tenia el sobrenombre de quijada, o quesada, que en esto hay alguna diferencia en los autores que deste caso escriben; aunque, por conjeturas verosimiles, se deja entender que se llamaba quejana. pero esto importa poco a nuestro cuento; basta que en la narracion del no se salga un punto de la verdad. es, pues, de saber que este sobredicho hidalgo, los ratos que estaba ocioso, que eran los mas del ano, se daba a leer libros de caballerias, con tanta aficion y gusto, que olvido casi de todo punto el ejercicio de la caza, y aun la administracion de su hacienda. y llego a tanto su curiosidad y desatino en esto, que vendio muchas hanegas de tierra de sembradura para comprar libros de caballerias en que leer, y asi, llevo a su casa todos cuantos pudo haber dellos; y de todos, ningunos le parecian tan bien como los que compuso el famoso feliciano de silva, porque la claridad de su prosa y aquellas entricadas razones suyas le parecian de perlas, y mas cuando llegaba a leer aquellos requiebros y cartas de desafios, donde en muchas partes hallaba escrito: la razon de la sinrazon que a mi razon se hace, de tal manera mi razon enflaquece, que con razon me quejo de la vuestra fermosura. y tambien cuando leia: ...los altos cielos que de vuestra divinidad divinamente con las estrellas os fortifican, y os hacen merecedora del merecimiento que merece la vuestra grandeza.

Pero decidi cambiarlo por:

en un lugar de la mancha, de cuyo nombre no quiero acordarme, no ha mucho tiempo que vivia un hidalgo de los de lanza en astillero, adarga antigua, rocin flaco y galgo corredor.

Los resultados fueron los siguientes:

Aunque sus frecuencias siguen manteniendose grandes de la "d" a la "g", estas bajaron. El resultado de el test fue:

Parece que al haber llaves pequeñas reduce las coincidencias entre 0's y 1's, esto es porque seguramente las repeticiones son más largas que el mensaje corto. En cambio las del mensaje largo son suficientemente largas para hacer notar la repeticion de ciertos patrones generados.









Fuentes:

Pruebas de Aleatoridad
Valor P
Statistical Testing of Randomness
Pruebas estadisticas para números pseudoaleatorios