Akrykuł wyjaśnia budowę pliku GIF i przykład steganografii metodą modyfikacji kolorów indeksowanych.

Obraz w formacie GIF jest plikiem indeksowanym. Oznacza to, że piksele nie zawierają bezpośrednio informacji o kolorach RGB, tylko numer indeksu do tablicy,
w której ten kolor się znajduje. Wiadomość zostaje ukryta według wcześniejszego schematu algorytmem LSB, jednak zmianie nie ulegają wartości składowe danego koloru, ale numery indeksów. Zmiana tylko jednego najmłodszego bitu powoduje przesunięcie wartości numeru indeksu co najwyżej o 1. Z tego powodu
obok siebie w tablicy kolorów powinny występować barwy o podobnych własnościach, aby ich podmiana nie była zauważalna. Dodatkowo informacje o pikselach są kompresowane metodą słownikową LZW (Lempel-Ziv-Welch), co pozwala na uzyskanie mniejszego rozmiaru pliku w formacie GIF, jednak nieco komplikuje sposób wydobycia informacji o numerach indeksów w pikselach. Powyższe czynniki wpływają na konieczność wstępnego przetworzenia pliku przed zastosowaniem algorytmu LSB.

Obraz GIF przekształcony w tablice bajtów składa się z kilku bloków informacji. Na potrzeby ukrycia informacji konieczne jest wydobycie indeksowanej tablicy kolorów oraz samych danych dotyczących indeksu w danym pikselu. Stałe elementy w budowie formatu pozwalają łatwo wyodrębnić potrzebne informacje z obrazu w formie tablicy bajtów.

Plik rozpoczyna się blokiem nagłówkowym. Pierwsze 6 bajtów zawsze określa format pliku, na przykład GIF89a. W programie sprawdzenie formatu pliku odbywa się poprzez odczytanie typu pliku mimetype,np:

String mimetype = new MimetypesFileTypeMap().getContentType(inputFile)

Istotny jest 11 bajt z kolei (indeks 10), który zawiera 4 pola spakowanych danych. Najbardziej znaczący bit to informacja czy w pliku występuje globalna tabela kolorów. Ustawienie tej flagi na 1 potwierdza, że obraz zawiera indeksowaną tablicę kolorów globalnych. Przydatną informację zawierają również 3 ostatnie bity w tym bloku, określające rozmiar tablicy kolorów. Jeśli wartość tego pola jest równa N, to liczba wpisów w globalnej tablicy kolorów będzie wynosić $2^{(N + 1)}$. Tablica kolorów w formacie GIF może mieć więc maksymalnie 256 kolorów, a jej rozmiar to $3*2^{(N + 1)}$, ponieważ każdy kolor zapisany jest za pomocą trzech składowych RGB.

Tablica kolorów w obrazie GIF nie jest domyślnie w żaden sposób sortowana. Kolory można by uporządkować tak, aby obok siebie znajdowały się podobne odcienie z palety, jednak oko ludzkie jest bardziej czułe na różnicę w jasności pikseli niż na zmianę koloru, więc w projekcie tablica została posortowana według wzoru na relatywną luminancję w przestrzeni kolorów RGB:
luminance = (r ∗ 0.2126f + g ∗ 0.7152f + b ∗ 0.0722f )1

Po lewej grafika stworzona na podstawie tablicy kolorów wczytanej z pliku, po prawej kolejność barw w posortowanej tablicy

Po lewej grafika stworzona na podstawie tablicy kolorów wczytanej
z pliku, po prawej kolejność barw w posortowanej tablicy

Dzięki sortowaniu globalnej tablicy kolorów podmiana barw na sąsiednie przy użyciu LSB w tablicy indeksów nie jest tak zauważalna.

Po posortowaniu tablicy kolorów kolej na podmianę indeksów w pikselach obrazu. Po wczytaniu tablicy kolorów przesunięcie numeru indeksu danych wynosi $12 + 3*2^{(N + 1)}$. Kolejny może być opcjonalny blok sterowania rozszerzeniami graficznymi. Łatwo rozpoznać czy wystęþuje, ponieważ zawsze rozpoczyna się taką samą parą bajtów w notacji heksadecymalnej 21 oraz F9, czyli $33_{(10)}$ i $-7_{(10)}$. Jeśli blok jest obecny, dodajemy do przesunięcia kolejne 8 bajtów i przechodzimy do bloku danych obrazu, który standardowo zaczyna się od bajtu $2C_{(16)}$, czyli $44_{(10)}$. Odczytanie danych dotyczących szerokości i wysokości obrazu pomoże upewnić się, że do tej pory dane pliku były odczytane prawidłowo. Jeśli obraz składa się z ruchomej sekwencji, mogą wystąpić lokalne tablice kolorów, zbudowane podobnie jak główna tablica kolorów.

Następny blok zawiera w końcu szukaną informację, czyli tablicę z indeksami kolorów pikseli. Dla dużych obrazów kolejne wartości pikseli zajęłyby dużo miejsca, więc dane są skompresowane algorytmem LZW. W skrócie LZW tworzy pomocniczy słownik, w którym występującym w obrazie wartościom przypisuje się dodatkowe kody. W przypadku gdy użyta jest maksymalna ilość barw, czyli 256 – kody poszczególnych kolorów od 0 do 255 zostają przypisane w słowniku tak jak w tablicy kolorów. Jako kolejny element z kodem 256 umieszczony jest znacznik „clear code”, który informuje o rozpoczęciu kolejnej sekwencji danych.
Następny kod 257 zarezerwowany jest jako informacja o końcu pliku. Dane o pik- selach podzielone są na bloki o wielkości z zakresu 0-255. Rozmiar każdego bloku jest określony w pierwszym wczytanym bajcie danej sekwencji. Dalsze dodawanie kodów do słownika opiera się na łączeniu sekwencji poprzednich bajtów i nowowczytanego. Jeśli ciąg danych powstały w ten sposób nie ma przydzielonego swojego kodu, zostaje dodany do słownika z kolejną wartością zapisaną jako kod. Po przeprowadzeniu dekompresji metodą LZW otrzymujemy tablicę bajtów z indeksami kolorów dla poszczególnych pikseli. Wartości pikseli należy podmienić na aktualne indeksy z posortowanej tablicy kolorów. Po tej operacji ukrycie wiadomości odbywa się na takiej samej zasadzie jak w plikach JPG lub PNG, z tą różnicą, że zmianie ulegają nie poszczególne kolory składowych RGB, tylko indeksy kolorów. Po tej operacji następuje utworzenie nowego pliku GIF, na podstawie pliku wejściowego, poprzez podmianę danych na posortowaną tablicą indeksów oraz skompresowanych algorytmem LZW danych nowych indeksów pikseli. Wizualnie obraz wynikowy nie różni się od oryginału.

Różnica między kolorami poszczególnych pikseli w powyższym przykładzie jest dostrzegalna dopiero w dużym powiększeniu. Różnice te byłyby znacznie bardziej zauważalne, gdyby osadzenie wiadomości nastąpiło w kolejnych występujących po sobie pikselach. Ukrywana informacja została jednak rozłożona na cały obraz.

Obraz wejściowy (po lewej) i obraz z osadzoną wiadomością (opra- cowanie własne)

Obraz wejściowy (po lewej) i obraz z osadzoną wiadomością (opra-
cowanie własne)

Zaburzenia wprowadzone w kolorach pikseli, widoczne przy po- większeniu 800%. W odcieniach niebieskiego na obrazie po prawej stronie dostrzec można żółte piksele

Zaburzenia wprowadzone w kolorach pikseli, widoczne przy po-
większeniu 800%. W odcieniach niebieskiego na obrazie po prawej stronie dostrzec
można żółte piksele


1 Na podstawie https://www.w3.org/TR/WCAG20/relative-luminance.xml