(Desde 2008 que no escribo en este blog; en esta serie de posts sobre esteganografía quizás reinicie mis posts al blog, o quizás no… ya veremos)

Hace unos días presenté un trabajo en JAIIO/WSegI sobre este tema, que pueden ver aquí: http://www.41jaiio.org.ar/WSegI_Contribuciones. A continuación presento brevemente y de forma muy informal sobre qué se trata este artículo. Los detalles formales y la matemática están en el paper.

Esteganografía es la disciplina que estudia el envío de mensajes escondidos (dentro de mensajes u objetos), de forma que no se sospeche que estos están allí. Un ejemplo típico es: un individuo A le quiere enviar un mensaje a un individuo B, pero hay un individuo C que intercepta los mensajes. La idea es que es necesario poder enviar los mensajes escondidos de forma tal que C ni siquiera sospeche que estos están allí.

En el caso de esteganografía de textos, se envían textos de aspecto inocente que ocultan, dentro de ellos, otros mensajes (que pueden ser textos o bits arbitrarios). Una forma de esteganografía de textos trivial y que todos conocen es partir de un texto como “ahora lo veo”, y agregar mayúsculas al mismo en lugares que indiquen qué letras son las que contienen el segundo mensaje escondido: “aHOra Lo veO”. En este caso el submensaje es, por supuesto, “hola”. Claro que la esteganografía estudia métodos más difíciles de detectar que éste.

El segundo concepto interesante que se usa en este proyecto son las cadenas de Markov. En vez de explicarlas como un modelo de proceso estocástico y explicar sus propiedades matemáticas, voy a tratar de dar una intuición sencilla de lo que son estos objetos.

Supongamos que tengo un texto, que es una secuencia de palabras como “w1 w2 w3 w4 …”. Hay varias formas de analizar este texto, una bastante sencilla es por ejemplo contar cuantas veces aparece cada palabra. Por ejemplo “la” aparece 1000 veces, “casa” aparece 300, etc. Más interesante, son las combinaciones de dos palabras, lo que se conoce como bigramas. Podemos decir, “la casa” aparece 120 veces; “el perro”, 50, y así sucesivamente.

Estas propiedades que extraigo de los textos definen un modelo de lenguaje. A partir de las mismas puedo entender cómo funciona un lenguaje a través de lo que veo en textos (a partir de sus propiedades estadísticas), y también puedo hacer cosas interesantes como generar nuevos textos haciendo de cuenta que mi modelo representa perfectamente el lenguaje. Más sobre esto luego.

Si usamos un poco de probabilidad por un momento, podemos decir algo un poco más interesante aún, que sólo trabajar con las frecuencias de los bigramas. Usando una notación de probabilidad condicional como

P(Xn+1 = casa | X n = la) = 0.5

estamos obteniendo una caracterización más interesante. Lo que esto significa es: si la palabra número n en el texto es “la”, la probabilidad que la siguiente palabra sea “casa” es 0.5. Es decir, la mitad de las veces que aparece la palabra “la”, la siguiente palabra es “casa”. Estas probabilidades (que se pueden computar fácilmente desde las frecuencias) definen la cadena de Markov, pero la forma más familiar para los programadores de la cadena de Markov es en su forma gráfica, que es una máquina de estados como la siguiente:

Markov chain

donde las transiciones son las probabilidades condicionales, y los estados son las palabras (y generalmente hay un estado inicial para indicar el inicio). Por supuesto las cadenas de Markov no funcionan sólo con palabras, esto es sólo para los efectos de este caso particular de análisis sencillo de textos.

A partir de un texto cualquiera puedo extraer una cadena de Markov que modela el lenguaje que se usa en el mismo. Esto (y otros modelos de lenguaje) tiene algunas ventajas muy interesantes para nosotros:

1- dada una cadena de Markov y un texto cualquiera, puedo averiguar cuál es la probabilidad que el texto haya sido generado por esa cadena de Markov… puedo hacer, por ejemplo, un detector simple de lenguaje español o inglés

2- más interesante para nuestros propósitos: dada una cadena de Markov, puedo generar nuevos textos al azar. Estos textos generados se parecerán en cuanto al lenguaje usado, al texto a partir del cual se extrajo la cadena.

Ambas ventajas se obtienen a partir de una idea sencilla. Supongamos que yo quiero saber cuál es la probabilidad de que la frase “el perro azul” sea generado por una cadena de Markov con estados que son palabras. Todo lo que tengo que hacer es calcular las probabilidades de P(perro|el) y P(azul|perro) y multiplicarlas entre sí:

P(el perro azul) = P(Xn+1 = perro | Xn = el) * P(Xn+1 = azul | Xn = perro)

En la siguiente parte, explicaré cómo es que se usan las cadenas de Markov en esteganografía, y contaré un poco más sobre mi trabajo en este tema.