Information Hiding on Open Format Documents using Permutations
Contents
1. de objetos independientemente del orden en que est n escritos en el fichero as fue posible realizar un esquema para darle un significado al orden en que se encuentren los objetos La organizaci n del trabajo es la siguiente en la Secci n II se recapitulan las caracter sticas y aspectos t cnicos de los formatos est ndares En la Secci n III se explica el protocolo de ocultamiento de informaci n En la Secci n IV se muestran detalles de la implementaci n Finalmente se pueden encontrar las conclusiones en la Secci n V II FORMATOS EST NDARES PARA DOCUMENTOS Durante varios a os cuando se utilizaba una aplicaci n los ficheros se almacenaban en un formato que se pod a interpretar completa y adecuadamente s lo por la aplicaci n que los generaba Pages creaba los ficheros Pages Microsoft Word generaba los ficheros Word y as sucesivamente Eventualmente los programadores inclu an m dulos para dar soporte a los formatos de sus competidores en ocasiones pod a ser un xito al menos hasta la siguiente actualizaci n del formato por parte de los propietarios lo mismo para presentaciones hojas de c lculo y otros El intercambio de ficheros entre diferentes aplicaciones podr a ser todo un reto para los usuarios tal as que copiar el contenido y adecuar el formato era el procedimiento realizado Los formatos estandarizados como el ODF y PDF llegan a solucionar el problema de almacenar e intercambiar ficheros entre apl2. ficheros adjuntos sonidos y pel culas Un documento puede incluso definir su propia interfaz de usuario acciones del teclado y del rat n las cuales pueden ser vinculadas con acciones descritas en objetos Incluso en un documento PDF puede haber informaci n de alto nivel que es til para el intercambio de contenidos entre aplicaciones Es decir puede incluir la identificaci n y la informaci n de la estructura l gica que le permite realizar b squedas editar o extraer informaci n para su reutilizaci n en otros lugares Las contrase as y certificados son parte de esta informaci n de alto nivel que especifica el formato Un fichero PDF inicialmente se compone de cuatro elemen tos Un encabezado escrito en la primer l nea del PDF identi fica la versi n del formato utilizado para la especificaci n del documento a El cuerpo de un fichero PDF consiste en una secuencia de objetos los cuales representan el contenido del do cumento como la tipograf a las p ginas e im genes En versiones iguales o posteriores a la 1 5 el cuerpo puede contener flujos de objetos Cada flujo de objetos contiene una secuencia de objetos indirectos Una tabla de referencias cruzadas localizado xref 0 23 0000000000 0000064425 0000000019 0000001668 0000001689 0000001866 0000001906 0000024415 0000064568 0000024437 0000046596 0000046619 0000046819 0000047307 0000047648 0000063346 0000063369 0000063584 0000063985 000006
3. 4257 0000064300 0000064667 0000064764 65535 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 00000 oia o o a o ja a o Ma a o a a o o o o o a o a O Figura 2 Ejemplo de una tabla de referencias cruzadas del formato PDF com nmente en la pen ltima secci n de la estructura est ndar de un fichero la cual muestra informaci n que permite el acceso aleatorio de los objetos descritos en el cuerpo de esta forma no es necesario leer todo el documento para identificar un objeto en particular La tabla esta dise ada para tener una entrada por l nea especificando la posici n del objeto dentro del documento La tabla de referencias cruzadas es la nica parte de todo el documento que tiene un formato fijo y permite entradas de la tabla para tener acceso aleatorio Inicialmente la tabla tiene una sola secci n y conforme se forme el documento se agregan las dem s entradas a la tabla Cada secci n en la tabla como la que se presenta en la Figura 2 inicia con una l nea que contiene la palabra reservada xref despu s de esta l nea se pueden agregar una o m s subsecciones sin importar el orden en que se registren Cada subsecci n de referencias cruzadas contiene entradas para un rango contiguo de objetos Cada subsecci n inicia con una l nea que contiene dos n meros separados por un espacio el primero indica el n mero del objeto co
4. F contiene los objetos que lo crean junto a la informaci n estructurada que despliega todo se representa como una secuencia de bytes Las p ginas de un documento y otros elementos visuales pueden contener cualquier combinaci n de texto gr ficos e im genes La apariencia de una p gina se describe a trav s lt style style style name P1 style family paragraph style parent style name Standard gt lt style paragraph properties fo margin left 0in fo margin right 0in fo margin top 0in fo margin bottom 0 1626in style contextual spacing false style line height at least 0 1862in fo text indent 0in style auto text indent false fo padding 0in fo border none gt lt style text properties fo font variant normal fo text transform none fo color 000000 style font name arial fo font size 25 1000003814697pt fo letter spacing normal fo font style normal fo font weight normal gt lt style style gt Figura 1 Extracto de los estilos que por defecto genera LibreOffice al crear un fichero de texto de un flujo de contenido el cual contiene una secuencia de objetos gr ficos que ser n pintados en la p gina Adem s para describir el aspecto est tico de las p ginas un documento PDF puede contener elementos interactivos que son posibles s lo en una representaci n electr nica Se admiten anotaciones de muchos tipos de cosas tales como texto enlaces de hipertexto de marcado
5. Information Hiding on Open Format Documents using Permutations Michel Ruiz Tejeida and Guillermo Morales Luna Departamento de Computaci n CINVESTAV IPN Mexico D F Mexico Email mruizcomputacion cs cinvestav mx Resumen We introduce an information hiding protocol for textual documents arranged in open formats which are open and standards by the ISO We show a software tool created to test the protocol s robustness on several work group environments Index Terms cryptography permutations data hiding digital steganography copyright protection ODF PDF factorial number system I INTRODUCCI N Ocultar informaci n en medios gr ficos es una t cnica que se ha utilizado por muchos a os 1 dependiendo del objeto que lo oculta se han propuesto muchas formas para incrustar y extraer secretos La creciente actividad de crear y distribuir documentos de texto con herramientas ofim ticas en l nea sistemas colaborativos o por editores en dispositivos m viles entre otros tantos ejemplos sugiere utilizar los ficheros ODF OASIS Open Document Format for Office Applications y PDF Portable Document Format como medio anfitri n del secreto En la literatura podemos encontrar diferentes mecanismos empleados para ocultar informaci n en al menos uno de los formatos mencionados Brassil Low y Maxemchuk 2 describen y comparan varios mecanismos para el marcado de documentos y varios mecanismos para la decodificaci n de las marcas
6. ar las entradas temporalmente de la lista de elementos el primero debe quedar intacto para evitar problemas de compatibilidad con los programas visores los siguientes ser n utilizados para ocultar la informaci n A diferencia de los documentos ODF en los ficheros PDF se conoce la cantidad de informaci n que se puede ocultar hasta realizar el an lisis del fichero Por otro lado la cantidad de informaci n que se puede ocultar en un documento PDF puede ser considerablemente mayor dependiendo de la cantidad de objetos utilizados para su creaci n que est directamente relacionado con el tipo de contenido V CONCLUSIONES En este trabajo se presenta un esquema para ocultar in formaci n en los dos formatos m s com nmente utilizados para distribuir documentos de texto ODF y PDF Uno de los aspectos m s importantes del esquema es que el fichero marcado no tiene cambios significativos no se agregan obje tos tan solo se permutan elementos existentes el secreto se oculta directamente en el c digo del formato lo que provee un esquema de marcado invisible La dificultad para recuperar el secreto sin posesi n de la clave depende de la cantidad de elementos seleccionados y el tiempo que tome encontrar la permutaci n correcta El software descrito en este art culo estar disponible en http computacion cs cinvestav mx mruiz REFERENCIAS 1 LJ Cox M L Miller J A Bloom J Fridrich and T Kalkel Digital Watermarki
7. ci n m y una lista L con todos los elementos de S ordenada de forma ascendiente se identifica el valor factor dico de 7T es decir se buscan los cambios en posici n de los elementos de la Require m Sp n E N Ensure ndice i 1 for j 1 gt n do 2 mlj j 3 jj 1 4 end for 5 for j 1 gt n do 6 a milj 7T p lt EncontrarPosicion r a Regresar la po sici n del valor de a en m 8 Dl p 9 m T T p 10 end for 11 i 4 Decimal D 12 return 2 Figura 5 Obtener el ndice de una permutaci n 7 permutaci n m con respecto de L y se hace nuevamente un cambio de base del sistema de numeraci n factorial al decimal este proceso est descrito en la Figura 5 El mensaje a incrustar se lee desde la entrada est ndar y se codifica a una representaci n entera utilizando el c digo ASCII American Standard Code for Information Interchange como sabemos es necesario utilizar 8 bits para cada caracter y de forma similar en el proceso de extracci n se realiza la decodificaci n del entero a su valor en la tabla ASCII Este valor decimal correspondiente al mensaje se utiliza junto a la clave compartida para obtener el ndice de la permutaci n Finalmente utilizando las funciones b sicas del lenguaje Go es posible leer y analizar los ficheros ODF y PDF para poder identificar y acomodar en un arreglo los elementos permutables al final este arreglo se modificar en relaci n a la permutaci
8. despu s de que los documentos han sido sometidos a tipos comunes de distorsi n con el prop sito de poder identificar el documento original de alguna copia realizada ilegalmente Zhu Wu y Kankanhalli 3 proponen un m todo de autenti caci n de documentos el cual modifica el formato de descrip ci n del documento en donde un car cter predeterminado se permuta mediante una clave secreta del usuario En el proceso de verificaci n conociendo la clave se determina la permu taci n inicial y al encontrar el car cter se puede determinar si el documento ha sido marcado Algunas vulnerabilidades se han encontrado y corregido en este esquema proponiendo modificar las m tricas del documento para insertar una marca de agua brindando un esquema m s robusto 6 Tambi n Artz 4 explica una forma de hacer esteganograf a con permutaciones Un documento de texto contiene objetos que son interpretados por los programas para indicar la forma en que se debe mostrar Para un procesador de textos los ob jetos le indican la forma en que se visualizar n los caracteres como el tipo de letra el tama o de la letra los t tulos y dem s caracter sticas Si le damos importancia al orden en que se encuentran los objetos se puede representar como un valor oculto Los objetos en los formatos PDF y ODF no tienen un orden estricto salvo algunas excepciones 7 8 Esto significa que un procesador de textos interpreta de la misma forma un grupo
9. en el primero cada secci n del formato es guardado en un fichero independiente con el prop sito de facilitar su administraci n este enfoque es muy parecido a la manera en que se crean sitios web en donde se tienen ficheros para el estilo otros para el contenido incluso en el caso de las im genes estas se incorporan al empaquetado como ficheros separados que posteriormente se ligan con su ruta interna Cada fichero tambi n tiene ciertas reglas como el elemento ra z que debe tener y el tipo de contenido sin embargo es flexible en el orden de los atributos para cada elemento cuidando las convenciones establecidas en el lenguaje de esquema RELAX NG REgular LAnguage for XML Next Generation el utilizado para definir el formato 9 En la Figura 1 se muestra un extracto en donde se pueden distinguir algunos elementos que definen el estilo del contenido en documentos de texto cada elemento tiene atributos espec ficos los cuales pueden estar escritos en diferente orden sin afectar la visualizaci n en pantalla II B El Formato de Documento Port til El popular formato PDF es uno de fichero usado para re presentar documentos de manera independiente a la aplicaci n de software hardware y de los sistemas operativos 8 creado y mantenido por Adobe Un documento PDF consiste en una colecci n de objetos que juntos describen la apariencia de una o m s p ginas posiblemente acompa ado de otros elementos interactivos Un fichero PD
10. icaciones y sistemas Un fichero puede ser creado en Windows utilizando Microsoft Word y guardado con alguno de los formatos mencionados al compartirlo a otro equipo con Linux por ejemplo cualquier aplicaci n que soporte estos formatos va a desplegar de la misma forma su contenido II A El Formato de Documento Abierto para Aplicaciones Ofim ticas Establecido como formato est ndar por la ISO Interna tional Organization for Standardization IEC International Tabla I CONTENIDO DE UN EMPAQUETADO ODF Length Method Size Cmpr Name 39 Stored 39 0 mimetype 45 Defi N 37 18 layout cache 807121 Defi N 76945 1 Pictures 18 png 10403 Defi N 2178 79 content xml 11784 Defi N 2165 82 styles xml 9187 Defi N 1424 85 settings xml 1053 Stored 1053 0 meta xml 899 Defi N 261 71 manifest rdf Electrotechnical Commission basado en XML eXtensible Markup Language y dise ado para almacenar e intercambiar documentos entre aplicaciones ofim ticas incluyendo proce sadores de texto hojas de c lculo y presentaciones el formato ODF es neutral en cuanto a la aplicaci n plataforma y sistema operativo Se almacena como un JAR Java ARchive 5 es decir un empaquetado zip con un fichero adicional que lista su contenido De acuerdo a las especificaciones t cnicas 7 un fichero ODF debe cumplir ciertos requisitos dependiendo de su estructura puede estar constituido como un paquete Tabla I o como fichero nico
11. ilj j ej l end for for 1 gt n do a D tilj mla T S T1 Ti a 10 end for 11 return 7 e RE E E a Figura 4 Obtener i sima permutaci n c lculo de todas las permutaciones de n es suficiente con 1 dado un valor de ndice obtener la permutaci n 7 es decir la sima permutaci n y 2 dada una permutaci n m obtener su ndice en el rango 1 n Como se tiene conocimiento una forma de representar una n permutaci n es mediante su ndice N con 0 lt N lt n y algunos m todos convencionales para convertir el entero en una representaci n habitual de una permutaci n como una secuencia La conversi n se realiza a una secuencia de n meros d d 1 d2 d1 donde d es un entero no negativo menor que i al arreglo D dn d 1 da d1 lo llamaremos representaci n de n en base factorial o a caso forzando el idioma factor dico El primer paso es obtener la representaci n de N en el sistema de numeraci n factorial como se describe en la Figura 3 El segundo paso es interpretar la secuencia para generar la permutaci n como se muestra en la Figura 4 se inicia liza una lista en orden creciente de los elementos de Sn 11 2 Tn se remueve 2 para i d cada uno de los elementos de la representaci n en el sistema de numeraci n factorial y se agrega a un arreglo simple el nuevo arreglo de elementos es la permutaci n m de n En el proceso contrario dada una permuta
12. l cardinal del conjunto Sn Se llama permutaci n de un conjunto a una biyecci n de ste sobre s Yn N designaremos por Sn el conjunto de todas las permutaciones del intervalo 1 n de N Una forma de representar los elementos del conjunto Sn es mediante un ndice N con 0 lt N lt n y algunos m todos convencionales para convertir el entero en una representaci n habitual de una permutaci n como una secuencia de la forma T a1 a2 di n donde cada a es un entero positivo menor o igual a n Esta representaci n de una permutaci n como un arreglo de enteros es similar a la utilizada para almacenar los elementos del objeto anfitri n dise ado de sta forma para poder trabajar con los ndices de las permutaciones Una correspondencia entre n permutaciones y los primeros n n meros naturales asocia a cada permutacion m un ndice y se escribe T T se dice pues que 7 es la 2 sima permutaci n La funci n de incrustaci n Z utiliza el mensaje a incrustar m 0 1 codificado como un entero positivo y la clave esteganogr fica k para calcular x k m m d n Q despu s se computa la sima permutaci n m Sn haciendo uso de una funci n FN gt Sa 3 En un proceso de mapeo se ajusta el orden de los elementos de Fo para hacerla coincidir con el orden de los valores de r a este nuevo arreglo se le llama F Finalmente F reemplaza a Fy en el formato de c y como resultado tenemos el archivo
13. marcado w La funci n de extracci n E utiliza el objeto tentavitamente marcado w y la clave secreta k Del archivo marcado w se localizan los n elementos permutados y se crea el arreglo Fi fi f2 fn como en el proceso de incrustaci n y se construye la permutaci n Ty Sn a partir de la cual se computa su ndice es decir se calcula el valor de z mediante una funci n FE Sa gt N 4 con la clave k se calcula m x k m d n 5 y de esta forma se recupera el mensaje m IV IMPLEMENTACI N Una herramienta de software para ocultar informaci n en ficheros PDF y ODF siguiendo el protocolo descrito anterior mente se implement usando el lenguaje de programaci n Go en los siguientes p rrafos se describe los principales algoritmos utilizados Sedgewick en 10 resume varios algoritmos para generar permutaciones e identifica el algoritmo de cambio m nimo de Heap que generalmente es el m s r pido para calcular todas las permutaciones de una lista con n elementos 11 Sin embargo para nuestros prop sitos no es necesario realizar el Require N Ensure D representaci n de en base factorial bl 2 While gt 0 do 3 r i m d b 4 isi div b 5 D b Sr 6 amp 6 b b 1 7 end while 8 return D Figura 3 Cambio de base decimal a factorial Require ndice i en el intervalo 1 n n N Ensure Permutaci n m Sn 1 De factor dico i Figura 3 for j 1 gt n do pi
14. n almacenada en el documento en su lugar aprovecha las caracter sticas definidas en el est ndar para las aplicaciones que despliegan su conte nido En el fichero ODF es posible cambiar el orden de los atributos de una etiqueta y para los ficheros PDF el orden de las entradas en la tabla de referencias cruzadas como se explic en la secci n anterior Estos n elementos son utilizados para ocultar la informaci n si podemos representarlos en una forma F fr fz ado donde cada fj sea un entero vinculado al elemento seleccio nado Se define matem ticamente el esquema esteganogr fico Sea k una clave esteganogr fica extra da del conjunto K de todas las claves secretas M el conjunto de todos los mensajes incrustables C el conjunto de todos los objetos anfitriones y W el conjunto de los objetos marcados El esquema est con formado por dos asignaciones la de incrustaci n I y la de extracci n E I CxKx M gt WwW E WxK gt M tal que Vel keK meM E l c k m k m 1 El conjunto de objetos anfitriones C esta conformado por todos los ficheros ODF y PDF El de los mensajes incrustables est definido por M mm 0 1 0 lt 1 lt loga n donde n es el n mero de elementos del objeto anfitri n seleccionado c la funci n logaritmo denota la capacidad de inserci n de la funci n su unidad son bits El conjunto de las claves esteganogr ficas se denota como K 4AklkeN 0 lt k lt mnm b donde n es e
15. n el que inicia la tabla el n mero a su derecha representa la cantidad de entradas en la subsecci n Seguida de esta l nea las consecutivas son referencias cruzadas Cada entrada en la tabla tiene una longitud exacta de 20 bytes incluyendo los caracteres de fin de l nea Hay dos tipos de referencias cruzadas una para los objetos que est n en uso y la otra para los que han sido eliminados y por consiguiente no se utilizan Ambas entradas usan el mismo formato y se pueden distinguir por la palabra clave n para las que est n en uso y f para las entradas libres El tr iler de un PDF permite que la aplicaci n de lectura encuentre f cilmente la tabla de referencias cruzadas Regularmente una aplicaci n lee un documento PDF desde el final del fichero La ltima l nea del fichero contiene solo una marca de fin de fichero EOF End Of File Antes de la marca de fin de fichero se encuentra el diccionario tr iler Los tokens en un fichero PDF se acomodan en l neas una l nea se identifica al encontrar un car cter EOL End Of Line que puede ser un CR Carriage Return LF Line Feed o ambos Los ficheros que contengan informaci n binaria tienen l neas de longitud arbitraria sin embargo para mejorar la compatibilidad entre aplicaciones se recomienda no se exceda de 255 caracteres por l nea III PROTOCOLO DE OCULTAMIENTO A diferencia de otras herramientas y modelos presentados nuestro esquema no altera la informaci
16. n generada a partir de su ndice Los detalles conforme al formato seleccionado se explican en dos subsec ciones IV A En documentos ODF El documento ODF tiene la ventaja de que el autor puede es tablecer la cantidad de informaci n que desea ocultar los atri butos del formato est n establecidos en el manual t cnico 7 con esto solamente se tendr a que modificar el programa para indicar los elementos seleccionados y como se utilizar n para representar las permutaciones En un documento de texto por ejemplo el empaquetado contiene un fichero exclusivo para el contenido con nombre content xml dentro se encuentra el elemento ra z lt office document content gt el cual puede tener hasta 34 atributos que se pueden asignar y permutar lo que provee 128 bits de capacidad independiente mente del contenido mismo incluso puede ser un documento en blanco Si se utilizan m s elementos como los estilos predeterminados del formato o los atributos de las etiquetas correspondientes a los metadatos la cantidad de informaci n a ocultar puede crecer tanto como sea posible controlar los elementos seleccionados en el programa IV B En ficheros PDF De forma similar a un visor el programa identifica el tr iler para posteriormente localizar la tabla de referencias cruzadas que inicia con la palabra reservada xref la l nea inmediata indica la cantidad de elementos en la tabla con lo que se puede crear un arreglo exacto para almacen
17. ng and Steganography 2nd ed San Francisco CA USA Morgan Kaufmann Publishers Inc 2008 2 J T Brassil S Low and N F Maxemchuk Copyright protection for the electronic distribution of text documents Proceedings of the IEEE vol 87 7 pp 1181 1196 July 1999 3 B Zhu Jiankang Wu and M S Kankanhalli Render Sequence Encoding for Document Protection Multimedia IEEE Transactions on vol 9 1 pp 16 24 2007 4 D Artz Digital steganography hiding data within data Internet Computing IEEE vol 5 3 pp 75 80 May 2001 5 J David Eisenberg OASIS OpenDocument Essentials 2006 6 M Garc a Horta Autenticaci n de Documentos Digitales usando la T cnica de marca de agua tesis para obtener el grado de M en C Escuela Superior de Ingenier a Mec nica y El ctrica IPN M xico 2012 7 OASIS Technical Committee Open Document Format for Office Appli cations OpenDocument Version 1 2 version 29 September 2011 8 Adobe Systems Incorporated PDF Reference Sixth edition version 1 23 2006 9 O Uche Introducing OpenDocument IBM July 2008 10 R Sedgewick Permutation generation methods ACM Computing Surveys CSUR vol 9 2 pp 137 164 1977 11 S Skiena Implementing discrete mathematics combinatorics and graph theory with Mathematica Addison Wesley Longman Publishing Co Inc 1991
Download Pdf Manuals
Related Search