пятница, 17 августа 2012 г.

Программа gifshuffle. Перестановки цветов

gifshuffle это программа для скрытия сообщений в изображениях GIF при помощи перестановок цветовой палитрыОбработанные программой изображения на вид не отличаются от оригинала. gifshuffle работает со всеми изображениями GIF, в том числе поддерживает прозрачность и анимацию.
Рассмотрим колоду из 52 карт. Есть 52 факториал (52!) способов перемешивания колоды, это означает, что любой конкретный порядок карт можно представить как число в диапазоне [0, 52! - 1]. Другими словами, имея n элементов, вы можете хранить приблизительно log 2 ( n!) битов информации на основе порядка их расположения.
GIF изображения содержат цветовую палитру до 256 записей, в результате чего максимальный объем информации, которую можно сохранить описанным выше способом - 1683 бит. Само изображение описывается из сжатым массивом индексов цветовой палитры.
 Чтобы скрыть сообщение в изображении GIF при помощи программы для стеганографии gifshuffle нужно сделать следующие шаги:

  1. Задать сообщение, которое вы хотите скрыть, указав его в командной строке или в файле. При желании можно сжимать и/или шифровать скрываемые сообщения. После этого сообщение преобразуется в последовательность из нулей и единиц.
  2. Приписываем спереди 1 к этой последовательности, что дает нам вам двоичное число m (вероятно, достаточно большое).
  3. Далее изучаем  GIF - изображение, в котором мы хотим скрыть сообщение. Считаем число уникальных цветов в изображении, которое назовем n . Если m > n! -1, то сообщение является слишком большим, и процедура будет отменена.
  4. Цвета в цветовой палитре сначала сортируются в их "естественном" порядке (кроме случаев, когда используется шифрование). Каждому RGB цвету  присваивается числовое значение ( красный * 65536 +зеленый * 256 + синий ), и цвета сортируются в соответствии с этими значениями. Любые повторяющиеся цвета удаляются.
  5. Итерация i которая принимает значения 1 .. N. Каждый n-i цвету  выделяется целевая позиция ( m mod i ), затем m делится на i .
  6. Каждый цвет ( n -1) .. 0, в свою очередь вставляется в новую цветовую палитру на свою целевую позицию. Цвет, который ранее занимал эту позицию и все цвета выше этой позиции перемещаются на одну позицию вверх.
  7. Если размер цветовой палитры больше, чем количество уникальных цветов в ней, в цветовая палитру будет добавлен последний цвет от оригинальной палитры.
  8. Область данных GIF распаковывается, значения цвета приводятся в соответсвие с новой палитрой, и изображение снова запаковывается. Для анимированных GIF-файлов эти действия повторяются для каждого изображения.
Извлечение скрытых сообщений производится аналогично, но в обратном направлении. Порядок следования цветов в палитре используется для построения двоичного числа, который затем может быть расшифрованным и распакован перед выводом, если при сокрытии сообщение было зашифровано и упаковано.
gifshuffle делает примитивное сжатие, используя таблицы Хаффмана оптимизированные для текста на английском языке. Однако, если данные не текст, или, если данных много, использование встроенного в программу сжатия не рекомендуется, так как внешняя программа сжатия, такая например, как compress или GZIP сделает это гораздо лучше.
Шифрование обеспечивается  с помощью алгоритма шифрования ICE в CBF - режиме. Поскольку ICE может использовать ключ произвольного размера, поддерживается пароли до 1170 символов.
В версии программы gifshuffle 2.0 алгоритм шифрования применяется также для упорядочения цвета в палитре. Вместо того чтобы использовать их "естественный" порядок, используется порядок их зашифрованного хэша. Это имеет то преимущество, что созданные палитры будут выглядеть случайными, даже если скрывается небольшое сообщение . Чтобы отключить эту функцию (которая не совместима с gifshuffle 1.0) используют опцию -1.

Опции утилиты gifshuffle

-C     Сжатие данных в случае сокрытия информации или распаковка, если извлечение информации. 
-Q     Автоматический режим. Если не установлен, то программа сообщает статистические данные, такие как процент сжатия  и количество используемого места. 
-S     Отчет о количестве свободного места для сообщения в палитре GIF. Этот показатель рассчитывается по количеству уникальных цветов в изображении. 
-1       Сохранение совместимости с gifshuffle 1.0, располагает цвета, используя их "естественный" порядка, а не связанного с паролем порядка. Эта опция имеет значение только если пароль не указан. 
-Р пароль
Если установлено, данные будут зашифрованы с этим паролем при сокрытии или расшифрованы при извлечении. 
-Е сообщение-файл
Содержимое этого файла будет скрыто в изображении. 
М сообщение строка
Содержимое этой строки будет скрыто в GIF-изображении.

Примеры использования

Следующая команда скрывает сообщение "Встреть меня в 6" в файле infile.gif , со сжатием, и шифрует с использованием пароля "привет мир". В результате текст будет сохранен в outfile.gif .
gifshuffle -С -м "Встреть меня в 6" -р "привет мир" infile.gif outfile.gif
Чтобы извлечь сообщение, используется команда
gifshuffle -C -р "привет мир" outfile.gif
Обратите внимание, что в результате сообщение не будет заканчиваться символом новой строки.

Ориентировочная емкость  файла -контейнера можно определить при помощи опции -S
gifshuffle -S infile.gif

Анализ исходных кодов программы

Трудно сказать что либо новое при столь подробном описании алгоритма на сайте программы, но тем не менее посмотрим какие конкретно конструкции реализуют вышеописанный алгоритм. Ранее я подробно анализировал другую стеганографическую информацию, поэтому сейчас ликбеза будет меньше.
Откроем на просмотр в исходных кодах файл main.c и найдем там функцию main. Из анализа мы видим, что после обработки параметров вызываются функции для каждой операции. Имена этих функций и их назначение:
space_calculate - расчет максимального скрываемого сообщения в зависимости от изображения - контейнера;
message_string_encode - скрытие сообщения в изображении - контейнере;
message_extract - извлечение сообщения из изображения - контейнера.

Итак, вначале изучим, как вычисляется максимальный размер скрываемого сообщения. Функция  space_calculate находится в файле encode.c
Что мы из нее видим? Прежде всего то что при оценке она работает только с заголовком GIF-файла. Получив заголовок она передает его в функцию colourmap_max_storage. Функция небольшая, привожу ее текст полностью.


static void
colourmap_max_storage (
const GIFINFO *gi,
EPI *epi
) {
int i, ncols = 0;
CMAP_INFO dummy[256];

/* Подсчет количества уникальных цветов в изображении */
ncols = unique_colours (gi->gi_colours, 
                                gi->gi_num_colours, dummy);

/* Вычисление значения ncols! - 1 */
epi_set (epi, 1);
for (i=2; i<=ncols; i++)
   epi_multiply (epi, i);

epi_decrement (epi);
}


Посмотрим, что тут происходит. Первоначально вычисляется количество уникальных цветов в палитре - при помощи функции unique_colours. Вычисляется довольно простым способом - создается еще один массив, который заполняется следующим способом: в него переносится новый элемент из исследуемой палитры цветов только если он отсутствовал ранее. После этого вычисляется размер массива.Листинг функции приведен ниже. В код я добавил комментарии  из которых ясно, что происходит в процессе работы функции.

static int unique_colours (
const RGB *cols,
int ncols,
CMAP_INFO *ci_array
) {
int i, n = 0, top = 0;

/* Перебор всех элементов полученного массива */
for (i=0; i<ncols; i++) { 
   int j;
   BOOL unique = TRUE;
/* Получение указателя на текущий элемент массива */
   const RGB *r = &cols[i]; 

/* Поиск, нет ли элемента в новом отсортированном массиве, состоящем только из уникальных элементов*/
   for (j=0; j<i; j++)
if (rgb_cmp (r, &cols[j]) == 0) {
/* Если есть переходим к следующему элементу*/
   unique = FALSE;
   break;
}
/* Если есть то увеличиваем значение уникальных цветов на 1 и записываем значение в отсортированный массив*/
   if (unique)
ci_array[n++].rgb = cols[i];
   else
ci_array[ncols - ++top].rgb = cols[i];
}

return (n);
}

Далее на основе В результате работы функции заполняется структура EPI, которая передается по указателю. Значение максимального количества бит, которые можно скрыть при помощи перестановки палитры вычисляется следующим образом
Наиболее интересным в этом коде является структура EPI, далее я привожу ее структуру


#define EPI_MAX_BITS 2040

typedef struct {
int epi_high_bit;
char epi_bits[EPI_MAX_BITS];
} EPI;

Структура служит для хранения и обработки скрываемого или извлекаемого сообщения. Назначение ее полей понятно интуитивно - epi_high_bit используется для хранения разрядности числа, которое получается в результате преобразования сообщения в последовательность бит и epi_bits[EPI_MAX_BITS] в котором хранится сама битовая последовательность. 
Со структурой можно проделывать следующие вещи (они описаны в файле epi.h)

extern void epi_init (EPI *epi); //Инициализация структуры
extern void epi_set (EPI *epi, int n); //Установка значения
extern int epi_cmp (const EPI *epi1, const EPI *epi2); //Сравнение двух структур
extern void epi_add (EPI *epi1, const EPI *epi2);//Добавление структуры в конец
extern void epi_multiply (EPI *epi, int n); //Умножение на число
extern int epi_divide (EPI *epi, int n); //Вычисляет значение epi % n, то есть остаток от целочисленного деления на n
extern void epi_decrement (EPI *epi); //Вычет из структуры 1 (декремент)


В нашем примере, чтобы вычислить значение n! - 1 используются функции epi_set, epi_multiply и epi_multiply.
В функции epi_set подсчитывается число бит, которые входят в переданное параметром число, после чего это значение записывается в поле epi_high_bit. В массив epi_bits побитно записывается переданное число.
В функции epi_multiply вычисляется новое значение epi_high_bit и дописываются значения в массив epi_bits в соответствии со значением произведения хранящегося в структуре числа с переданным числом.
Таким образом при помощи описанной выше структуры и сопутствующих ей функций осуществляется вычисление операций, сложения, умножения, объединения, и т.д. для больших двоичных чисел.

Итак, мы выяснили, что алгоритм вычисления максимально доступного места для сокрытия сообщения соответствует описанию, выяснили как это организовано алгоритмически. Теперь же перейдем непосредственно к алгоритму скрытия информации (стегоалгоритму) для чего перейдем к функции message_string_encode, описание которой содержится в файле main.c. Блок, отвечающий за сокрытие информации приведен ниже:
while (*msg != '\0') {
   if (!character_encode (*msg, infile, outfile))
return (FALSE);
   msg++;
}
Как видно из кода, программа осуществляет сокрытие сообщение посимвольно с использованием функции character_encode. Исходный текст функции также содержится в файле main.c. Функция разбивает байт на отдельные биты и вызывает функцию compress_bit, которая занимается заполнением структуры глобальной структуры EPI encode_bits, добавляя туда биты сообщения. После того как структура заполнена, осуществляется вызов функции  encode_flush которая, основываясь на сформированной структуре EPI и осуществляет сокрытие сообщения.  Функция, получив на вход заполненную структуру EPI  осуществляет проверку допустимости ее заполнения, емкости контейнера формат файла и т.д. Если обнаруживается какое-либо несоответствие, программа завершается и выдает сообщение об ошибке. Если все нормально, то управление передается функции colourmap_encode, расположенной в файле encode.c. Первоначально функция сортирует массив цветов, находящихся в цветовой палитре в порядке возрастания. Далее определяется положение каждого цвета в новой модифицированной палитре при помощи следующего программного кода:
for (i=0; i<ncols; i++)
    ci_array[ncols - i - 1].pos = epi_divide (epi, i + 1);

Далее при помощи определенного ранее положения каждого цвета в палитре производится ее модификация.


Комментариев нет:

Отправить комментарий