ocultando la informaci on: una introducci on a la esteganograf a · seguridad de las comunicaciones...

Ocultando la informacion:Una introduccion a la Esteganografıa

Carlos Munuera

marzo 2015

Seguridad de las comunicaciones

Alicia desea enviar un mensaje privado a Bob

→ nos vemos en Fondo de Bikini →

Un tercero, Eva, intenta acceder a la comunicacion entre ellos

Seguridad de las comunicaciones

La Seguridad de las Comunicaciones se ocupa de prevenir quealguna entidad no autorizada intercepte una comunicaciono pueda acceder o modificar la informacion que contiene.

Incluye la emision segura, la transmision segura, la seguridaddel flujo del trafico y la seguridad fısica de los equipos.

I Rapido crecimiento

I Tremendo interes industrial y social

I Fundamental para el comercio electronico.

Criptografıa

La receta ’tradicional’ para mantener la privacidad de lascomunicaciones consiste en utilizar la criptografıa.

Por ejemplo, usando AES con 128 bits,

→ GdN8Pqa8pdzxMqlOLoID99nPfAGAfM1lTxilf →

Un invonveniente obvio de este metodo es que

se oculta el significado del mensajepero no el mensaje mismo

(puede conocerse la existencia de mensajes secretos, su emisor yreceptor, su frecuencia, etc.)

La criptografıa protege los mensajes, pero no a losparticipantes en la comunicacion

¿Que es la esteganografıa?

La esteganografıa es la ciencia de transmitir mensajessecretos de manera que solo emisor y receptor conozcan laexistencia de la comunicacion.

esteganografıa = steganos+ graphein

= escritura encubierta

Su nombre describe el funcionamiento de la esteganografıa:el mensaje que se desea proteger se esconde en un objetoaparentemente inocuo (su cubierta).

Esteganografıa en la historia

I El ejemplo tıpico de esteganografıa es la tinta invisible.

I Los antiguos griegos escribian mensajes secretos en lacabeza rasurada de un esclavo.

I Otro ejemplo tıpico es el acrostico:

El silencio escuda y suele encubrir

Las faltas de ingenio e las torpes lenguas;

Blason que es contrario publica sus menguas

Al que mucho habla sin mucho sentir.

Como la hormiga que deja de ir

Holgando por tierra con la provision,

Iactose con alas de su perdicion:

LLevaronla en alto, no sabe donde ir.

El aire gozando, ajeno y extrano,

Rapina es ya hecha de aves que vuelan.

Esteganografıa en la historia

I El ejemplo tıpico de esteganografıa es la tinta invisible.

I Los antiguos griegos escribian mensajes secretos en lacabeza rasurada de un esclavo.

I Otro ejemplo tıpico es el acrostico.

La esteganografıa comenzo a ser publicamente conocida en2001, cuando FBI informo que era usada por Ben Laden, paradistribuir informacion secreta entre sus adeptos.

.

Esteganografıa Digital

La cubierta ’tıpica’ de la esteganografıa moderna es un ficherode computadora: imagen, sonido, vıdeo, ... Estos ficheros sonideales por su gran tamano y su redundancia.

Al contrario de los que sucedıa con la esteganografıatradicional, una coleccion de ’trucos astutos’, la esteganografıadigital es una ciencia, relacionada con las matematicas,estadıstica, informatica (procesado de senal, compresion,..), lapsicologıa, etc.

La esteganografıa es actualmente una disciplina de rapidocrecimiento: el 90 % de las publicaciones en este campo se hanescrito en los ultimos anos.

Sobre la cubierta y dos ejemplos

I La cubierta puede ser un documento pre-existente y lainformacion secreta se oculta en el, modificandolo(ligeramente) (modificacion de la cubierta).

I o la cubierta puede crearse ex-profeso a partir del mensajea ocultar (sıntesis de la cubierta).

Mostramos un ejemplo de estos dos tipos. Vamos a esconder elmensaje

no me gustan los lunes

Funciones de simulacion

La imitacion (’mimicking’) se basa en utilizar modelos paratransformar un fichero, buscando parecerse a una estructurapredeterminada.

Un buen ejemplo es el programa

SpamMimic (http://www.spammimic.com/)

que transforma un texto para que parezca un correo electronicode tipo ’spam’. Aplicando este programa a nuestro mensajesecreto, obtenemos el resultado siguiente:

SpamMimic

Dear Friend ; Your email address has been submitted to us

indicating your interest in our newsletter . We will

comply with all removal requests . This mail is being sent

in compliance with Senate bill 1625 ; Title 8 , Section

307 . Do NOT confuse us with Internet scam artists ! Why

work for somebody else when you can become rich in 83

months ! Have you ever noticed most everyone has a

cellphone and nearly every commercial on television has a

.com on in it . Well, now is your chance to capitalize on

this . WE will help YOU sell more increase customer

response by 140 . The best thing about our system is that

it is absolutely risk free for you . But don’t believe us

! Mr Ames who resides in Georgia tried us and says I’ve

been poor and I’ve been rich - rich is better¡

We assure you that we operate within all applicable laws .

If not for you then for your LOVED ONES - act now ! Sign

up a friend and you get halfoff ! God Bless . Dear Sir or

Madam , You made the right decision when you signed up for

our mailing list . This is a one time mailing there is no

need to request removal if you won’t want any more . This

mail is being sent in compliance with Senate bill 1621 ,

Title 4 ; Section 303 ! This is a ligitimate business

proposal ! Why work for somebody else when you can become

rich in 77 MONTHS ! Have you ever noticed nearly every

commercial on television has a .com on in it plus how many

people you know are on the Internet . Well, now is your

chance to capitalize on this . WE will help YOU turn your

business into an E-BUSINESS and deliver goods right to the

customer’s doorstep ! You can begin at absolutely no cost

to you . But don’t believe us ! Ms Anderson of Kansas

tried us and says I was skeptical but it worked for me¡ We

assure you that we operate within all applicable laws ! If

not for you then for your LOVED ONES - act now . Sign up a

friend and you get half off ! Warmest regards . Dear Sir

or Madam ;

Your email address has been submitted to us indicating

your interest in our letter . We will comply with all

removal requests ! This mail is being sent in compliance

with Senate bill 1627 ; Title 1 ; Section 305 ! This is

not a get rich scheme ! Why work for somebody else when

you can become rich within 79 days ! Have you ever noticed

people love convenience how long the line-ups are at bank

machines ! Well, now is your chance to capitalize on this

. WE will help YOU deliver goods right to the customer’s

doorstep use credit cards on your website . You can begin

at absolutely no cost to you ! But don’t believe us . Prof

Ames who resides in Utah tried us and says "Now I’m rich

many more things are possible¡ We are a BBB member in good

standing ! We urge you to contact us today for your own

future financial well-being . Sign up a friend and you’ll

get a discount of 10Cheers . Dear Salaryman , Your email

address has been submitted to us indicating your interest

in our briefing WE will help YOU turn your business into

an E-BUSINESS plus use credit cards on your website . You

can begin at absolutely no cost to you .

But don’t believe us ! Mr Ames who resides in Nebraska

tried us and says "Now I’m rich, Rich, RICH". We operate

in all states ! For the sake of your family order now !

Sign up a friend and you get half off .Thank-you for your

serious consideration of our offer !

notar que

la cubierta es mucho mayor que el texto a ocultar !!

esta es una de las caraterısticas (inconvenientes) de laesteganografıa

El segundo ejemplo:Escondiendo informacion

Recordemos que otra forma de esconder informacion esmodificar ligeramente un fichero existente. Por ejemplo

I imagenes (bmp, jpg, ...)

I audio

I vıdeo

I htlm

I

I no se utilizan ficheros ejecutables

El segundo ejemplo:Escondiendo informacion en imagenes

Por ejemplo, una imagen (aparentemente inocua)

Escondiendo informacion en imagenes

Una imagen digital se almacena en la computadora como unasecuencia de bits, correspondientes a sus pixeles

Para esconder un mensaje, el emisor ajusta el color de algunospixeles, de manera que se correspondan con una letra. Dada lalimitada capacidad del ojo humano, los cambios sonvisualmente imperceptibles.

Ademas, como la imagen original es borrada tras el proceso, nohay posibilidad de comparacion.

Esteganografıa y marcas de agua

Estrechamente relacionadas con la esteganografıa estan lasmarcas de agua. En ambos casos la finalidad es la proteccion dela informacion pero con importantes diferencias:

La presencia de marcas de agua no es secreta. Su contenidose relaciona con la cubierta, que es el valor que se trata deproteger (copyrights, etc.) El principal requerimiento es suimperceptibilidad.

En el caso de la esteganografıa la cubierta no tiene valorintrınseco. Su principal requerimiento es la indetectabilidad.

Esteganografıa LSB

Por simplificar tomemos el cso de una imagen bmp.La idea mas simple consiste en cambiar el bit menossignificativo de algunos pixeles de la imagen.

Esta tecnica se conoce como esteganografıa LSB.

[puede encontrarse facilmente en internet

( S-Tools: One of the BEST Steganography tools available...) ]

Sistemas esteganograficos

I Primero se seleccionan los elementos de la cubierta(pixeles, coeficientes, etc.) que almacenaran la informacion

I Se aplica en los elementos seleccionados un algoritmo deinsercion lo mas efectivo posible.

imagen de cubierta, mensaje secreto↓ regla de seleccion

vector de cubierta↓ algoritmo de insercion

vector modificado↓ canal de transmision

imagen modificada↓ algoritmo de recuperacion

mensaje secreto recuperado

Reglas de seleccion

La regla de seleccion permite determinar la localizacion eintensidad de los cambios a realizar durante la insercion deinformacion.

I Depende del tipo de cubierta (imagen [de que tipo?], vıdeo,audio, ...)

I a considerar factores informaticos, estadısticos,psicovisuales, etc.

I proporciona un vector binario (ejemplo LSB)

I la regla de seleccion debe ser tambien conocida por elreceptor !!

Reglas de seleccion

En general, se usan las zonas mas ruidosas de la imagen.

Algoritmo de insercion

La regla de seleccion proporciona un vector cubierta binarioc = (c1, . . . , cn)

El mensaje a esconder puede ser visto como un vector binariom = (m1, . . . ,mk)

El algoritmo de insercion debe ’embeber’ m en c con la menorcantidad de cambios posible (para reducir la distorsioncausada en la imagen de cubierta).

Asimismo deber ser posible invertir el proceso anterior, demanera que el recptor pueda recuperar m a partir de la imagenmodificada.

Esquemas esteganograficos

Recordamos que deseamos ’insertar’ un vector binariom = (m1, . . . ,mk) ∈ Fk

2 en c = (c1, . . . , cn) ∈ Fn2 .

El par de algoritmos que permiten insertar y recuperar lainformacion recibe el nombre de esquema esteganografico.

Un esquema esteganografico S de tipo [n, k] (sobre elalfabeto F2) es un par de funciones

ins : Fn2 × Fk

2 → Fn2 y rec : Fn

2 → Fk2

tales que rec(ins(c,m)) = m para todo c ∈ Fn2 y m ∈ Fk

2.

Esquema esteganografico LSB

A partir de la imagen de cubierta, se obtiene el vector cubiertac = (c1, . . . , cn) ∈ Fn

2 formado por los bits menos significativosde todos los pixeles de la imagen.

La funcion de insercion es

ins((c1, . . . , cn), (m1, . . . ,mk)) = (m1, . . . ,mk, ck+1, . . . , cn)

I ¿Puede hacerse mejor?

I ¿Cuanto mejor?

I ¿Como?

Parametros fundamentales

Los parametros que miden la calidad de un esquemaesteganografico (ins,rec), de tipo [n, k] que inserta un vectorbinario m = (m1, . . . ,mk) ∈ Fk

2 en c = (c1, . . . , cn) ∈ Fn2 , son

I la carga util α = k/n

I la distorsion relativa ρ = max{d(c, ins(c,m))}/n

siendo d la distancia de Hamming

d((x1, . . . , xn), (y1, . . . , yn)) = #{i : xi 6= yi}

Codigos correctores de errores

Un codigo corrector de errores de longitud n sobre F2 esun conjunto C ⊆ Fn

2 . Sus elementos son palabras. Su distanciamınima es

d = d(C) = mın{d(x,y) : x,y ∈ C,x 6= y}

siendo d la distancia de Hamming en Fn2 .

Cuando se transmite un palabra c ∈ C por un canal con ruido,ocurren errores que corrompen c. Sea x = c + e el vectorrecibido. Como x /∈ C, el receptor puede deducir que hanocurrido errores.

Correccion de errores

Se descodifica el vector recibido x = c + e por la palabra delcodigo mas cercana a x.Si la cantidad de errores no es muy grande, esta estrategiapermite recuperar el mensaje enviado c:

Teorema. Si x = c + e ∈ Fn2 con c ∈ C, y 2wt(e) < d(C)

entonces la palabra mas cercana a x es c.

Una funcion de descodificacion de C es una funcion

decC : Fn2 → C

tal que para cada x ∈ Fn2 , decC(x) es una de las palabras de C

mas cercanas a x.

El codigo de Haming [7, 4]El codigo de Haming [7, 4], H, permite codificar

secuencias de 4 bits (x1, x2, x3, x4)mediante secuencias de 7 bits, (x1, x2, x3, x4, x5, x6, x7),

anadiendo 3 bits de control del modo siguiente:

Consideramos tres cırculos



anadiendo 3 bits de control del modo siguiente:Consideramos tres cırculos



anadiendo 3 bits de control del modo siguiente:Numeramos la regiones que determinan



anadiendo 3 bits de control del modo siguiente:Colocaremos cada bit de (x1, x2, x3, x4, x5, x6, x7) en la regionque indica su ındice. Los sımbolos de control (x5, x6, x7) sedeterminan de manera que cada cırculo tenga suma par.

Por ejemplo, (1, 0, 1, 1) se codifica

Por ejemplo, (1011) se codifica (1011001)

El sistema permite corregir un error. Recibido (1001001)

El codigo de Haming [7, 4]

Se llama codigo de Hamming a

H = {(x1, x2, x3, x4, x5, x6, x7) : (x1, x2, x3, x4) ∈ F42}

I El sistema permite corregir un error.

I Un vector cualquiera (x1, x2, x3, x4, x5, x6, x7) ∈ F42 puede

llevarse a H con un solo cambio.

Esquemas esteganograficos y codigos correctores

Recordamos que un esquema esteganografico [n, k] permiteinsertar m = (m1, . . . ,mk) ∈ Fk

2 en c = (c1, . . . , cn) ∈ Fn2 .

ins : Fn2 × Fk

2 → Fn2 y rec : Fn

2 → Fk2

I Consideramos una funcion suprayectiva rec : Fn2 → Fk

2;

I ins(c,m) ∈ Cm = rec−1(m) que es un codigo corrector;

I ins(c,m) los mas cercano posible a c

⇒ ins(c,m) = decCm(c)

Estegosistema de Haming [7, 4]

El codigo de Hamming puede describirse como el conjunto devectores {(x1, x2, x3, x4, x5, x6, x7) ∈ F7

2} tales que (en F2)

x1 + x2 + x3 + x6 = 0

x1 + x2 + x4 + x5 = 0

x1 + x3 + x4 + x7 = 0

o como el nucleo de la aplicacion lineal rec : F72 → F3

2 de matriz 1 1 1 0 0 1 01 1 0 1 1 0 01 0 1 1 0 0 1

Estegosistema de Hamming

I rec es suprayectiva:Para cada z ∈ F3

2 existe ez tal que rec(ez) = z.

I rec−1(0) = H.

I rec−1(z) = ez +H.

El estegosistema de Hamming tiene funcion de insercion

ins(c,m) = decem+H(c)

permite insertar 3 bits de informacion en 7 bits decubierta con un cambio.

Este estegosistema se conoce comercialmente como F5.

Un ejemplo

Vamos a insertar el mensaje m = (111) en el vector cubiertac = (1010101). Recordemos que la matriz de rec es

H =

1 1 1 0 0 1 01 1 0 1 1 0 01 0 1 1 0 0 1

luego rec(1000000) = rec(e1) = (111). Por tanto

ins(c,m) ∈ e1 +H||

dec[e1+H](c)

||e1 + dec[H](e1 + c) = e1 + dec[H](0010101)

||e1 + (0110101) = (1110101)

Un ejemplo

Vamos a insertar el mensaje m = (111) en el vector cubiertac = (1010101). Recordemos que la matriz de rec es

H =

1 1 1 0 0 1 01 1 0 1 1 0 01 0 1 1 0 0 1

luego ins((1010101), (111)) = (1110101) (con un cambio)

Recibido este mensaje, el receptor calcula

H (1110101)t = (111)t

que era el mensaje oculto.

Conclusion

I campo de rapido crecimiento y expansion (investigacion yaplicaciones)

I enormes posibilidades (investigacion, industriales, militares)

I complementario con la criptografıa

ocultando la informaci on: una introducci on a la esteganograf a · seguridad de las comunicaciones...

Documents