Poniższy wpis wyjaśnia pojęcie kanału podprogowego, który jest szczególną formą steganografii oraz obrazuje mechanizm wymiany informacji pomiędzy dwiema wtajemniczonymi stronami.

Kanał podprogowy to połączenie pozwalające na nawiązanie dodatkowej, ukrytej komunikacji między nadawcą i autoryzowanym odbiorcą niepozornie wyglądającej wiadomości.

W odróżnieniu od klasycznej steganografii kanały podprogowe nie tylko ukrywają istnienie tajnego przekazu w wiadomości, ale również go szyfrują. Wymiana tajnej korespondencji jest uzależniona od wspólnego klucza deszyfrującego między nadawcą a odbiorcą. Bezpieczeństwo metody jest więc uzależnione od poufności tego klucza, a nie od tajności algorytmu.

Same algorytmy i protokoły kryptograficzne również mogą zawierać kanały podprogowe, zwłaszcza jeśli wykorzystują losowe liczby. Kanały podprogowe stanowią podgrupę kanałów ukrytych [1]. Ukryty kanał umożliwia przesłanie informacji poprzez zastąpienie domyślnej wartości używanej do komunikacji innym parametrem.

Problem steganograficzny, jak i koncepcję kanału podprogowego najlepiej wyjaśnia abstrakcyjny model wymiany informacji pomiędzy dwoma więźniami stworzony przez Gustavusa Simmonsa [2].

Model kanału podprogowego

Wspólnicy Alice i Bob zostali schwytani i osadzeni w więzieniu w osobnych celach. Zamierzają opracować plan ucieczki. Nie mają jednak możliwości bezpośredniego kontaktu, mogą przekazywać sobie wiadomości jedynie przez strażnika – Wendy. Wartownik pozwala na komunikację pod warunkiem, że informacje zawarte w wiadomościach
są dla niego jawne. Strażnik ma możliwość nie tylko czytania korespondencji, ale również fabrykowania listów lub zmiany treści wiadomości przekazanych przez więźniów.
W takich warunkach aresztowani muszą znaleźć sposób na zaplanowanie ucieczki poprzez kanał podprogowy. Ponadto, ponieważ więźniowie przewidują oszustwo przez strażnika, chcą wymieniać tylko takie wiadomości, które będą mogli uwierzytelnić. Uwierzytelnienie zależy od wprowadzenia do wiadomości przez nadawcę nadmiarowej ustalonej wcześniej informacji. Aby zapobiec kopiowaniu tej dodatkowej treści i doklejeniu do sfabrykowanej wiadomości przez przeciwnika, strażnik musi zgodzić się na szyfrowanie wiadomości. W ten sposób wiadomość wraz z informacją uwierzytelniającą będą stanowiły blok tekstu zaszyfrowany jednym lub dwoma kluczami. Kanał uwierzytelnienia odgrywa kluczową rolę dla możliwości tajnej komunikacji, ponieważ będzie w nim stworzony kanał podprogowy. Innymi słowy, więźniowie podważają autentyczność komunikacji w zamian za możliwość przesłania tajnej wiadomości.

Sposób uwierzytelnienia wiadomości

Rozważmy najpierw samo uwierzytelnienie wiadomości bez kanału podprogowego.
Jeśli algorytm szyfrowania jest odpowiednio bezpieczny, to prawdopodobieństwo $P(A)$, że strażnik wybierze odpowiedni szyfr i podszyje się pod nadawcę wiadomości, jest związane z długością informacji uwierzytelniającej. Jeśli tajna informacja zapisana jest na $m$ bitach i $r$ bitów jest przeznaczonych na uwierzytelnienie, wówczas w zaszyfrowanej wiadomości zostaje przekazana łączna liczba bitów $(m + r)$ i $P(A) = 2^{-r}$.

Do szyfrowania wiadomości można użyć kryptografii symetrycznej lub asymetrycznej. W algorytmie symetrycznym do szyfrowania i deszyfrowania wiadomości używany jest ten sam klucz. Natomiast kryptografia asymetryczna (zwana również kryptografią klucza publicznego) wykorzystuje różne klucze, z czego jeden może być udostępniony publicznie bez naruszania bezpieczeństwa przesyłanej informacji. W opisywanym modelu używana jest druga opcja z kluczem publicznym i prywatnym. Wendy musi mieć dostęp do klucza, aby móc odszyfrować wiadomość i sprawdzić jej treść. Jeśli nadawca używa kryptoalgorytmu z jednym kluczem to udostępnia nadzorcy klucz szyfrujący/deszyfrujący po wymianie danych. W takim systemie kryptograficznym strażnik ryzykuje, że komunikacja między więźniami nastąpi przed poznaniem przez niego zawartości. Im dłuższa wiadomość, tym bardziej rośnie ryzyko skomunikowania się więźniów. Jeśli strażnik chciałby uniknąć tego ryzyka i mieć klucz wcześniej, wtedy nadawca wiadomości może zaprotestować, ponieważ pośrednik zyskałby możliwość podrobienia wiadomości.

Do rozwiązania tego problemu bardziej nadaje się kryptosystem z dwoma kluczami, ponieważ strażnik otrzyma klucz deszyfrujący przed każdą wymianą komunikatów, a zatem najpierw będzie mógł sprawdzić treść wiadomości przed przekazaniem jej dalej. Dopóki Wendy nie będzie znała klucza szyfrującego wiadomości Alice i Boba, nie ma możliwości polepszenia swoich szans w zgadywaniu szyfru uwierzytelniającego, a tym samym na oszukanie więźniów.

Wprowadzenie kanału podprogowego

Więźniowie przed aresztowaniem mogli ustalić między sobą, że zrezygnują częściowo z uwierzytelnienia w zamian za możliwość porozumiewania się w tajemnicy. W tym celu $s$ bitów z $r$ bitów informacji uwierzytelniającej, przeznaczają na przesłanie sekretnych informacji. Więźniowie mają teraz $(r – s)$ bity dostępne do uwierzytelnienia. Oznacza to wzrost prawdopodobienstwa, że strażnik jest w stanie oszukać więźniow do $P(A) = 2^{-(r – s)}$.

Rozważmy najkrótszy możliwy blok informacji, składający się z 3 bitów.
$h = m + (r – s)$, 1 bit jest przeznaczony na iadomość i 2 bity na informację uwierzytelniającą, z czego 1 bit został wydzielony na kanał podprogowy.

Sposób kodowania jest związany z wynikiem rzutu monetą. Jeśli w rzucie monetą wypadnie orzeł, to strażnik zgodzi się tylko na przesłanie parzystej wiadomości, gdzie parzystość oznacza parzystą sumę cyfr w binarnej reprezentacji wiadomości. Reszka natomiast symbolizuje wiadomość nieparzystą. Oznacza to, że więźniowie i strażnik godzą się na określoną z góry listę kluczy, przedstawioną w tabeli Tab. 1.

kostka binarna

Rys.1 Zbiór możliwych wiadomości przedstawiony na kostce bitowej w zależności od wyniku rzutu monetą. Tails oznacza zbiór dla reszki, natomiast heads dla orła.

Tab.1 Lista możliwych kluczy dla 1-bitowego kanału i 2-bitowego uwierzytelnienia
Orzeł Reszka
1 000 100
2 000 010
3 000 001
4 000 111
5 011 100
6 011 010
7 011 001
8 011 111
9 101 100
10 101 010
11 101 001
12 101 111
13 110 100
14 110 010
15 110 001
16 110 111

Strażnik nie wie jednak, który z 16 kluczy wybrali Alice i Bob przed zatrzymaniem.

Wendy może oszukać więźniów na dwa sposoby:

  • Przed rzutem monetą, czyli poprzez całkowite sfałszowanie treści wiadomości — wybiera losową wiadomość i podszywa się pod nadawcę. Jeśli wszystkie 16 kluczy są jednakowo prawdopodobne to szanse, na to, że wiadomość, którą wybrał strażnik będzie miała poprawny klucz wynoszą ${{4}\over{16}}={{1}\over{4}}$.
  • Po rzucie monetą — modyfikuje dostarczoną wiadomość, czyli zastępuje treść wiadomości przeciwnymi parzystościami. W takim wypadku jego wiadomość jest zawarta dokładnie w 4 kluczach, więc prawdopodobieństwo powodzenia wynosi również ${{1}\over{4}}$.

wiadomość podprogowa

Tab. 2 Lista możliwych kluczy dla 1-bitowego kanału, 1-bitowego kanału podprogowego i 1-bitowego uwierzytelnienia.
0 1 1 0
1 000 011 111 100
2 000 011 010 001
3 000 110 010 100
4 000 110 111 001
5 101 110 111 100
6 101 110 010 001
7 101 011 010 100
8 101 011 111 001

Rozważmy teraz jednobitowy kanał podprogowy, w którym więźniowie wybierają tajny klucz, nie z listy szesnastu, w którą wartownik wierzy, ale raczej spośród ośmiu kluczy pokazanych w tabeli Tab. 2. Każdy klucz na tej liście zawiera etykiety czterech narożników z listy Tab. 1 i każda wiadomość znajduje się dokładnie w czterech kluczach. Na przykład wiadomość 000 znajduje się w kluczach 1, 2, 3 i 4. Ważną rzeczą, na którą należy zwrócić uwagę na temat wpisów w tabeli Tab. 2, jest to, że środkowy bit w dowolnej kolumnie jest taki sam jak nagłówek podprogowej wiadomości kolumny oraz kolumny z parzystymi i nieparzystymi wiadomościami. Przekazanie podprogowego bitu wymaga od nadawcy wyboru tajnego klucza, który ma pożądany środkowy bit, wskazujący na parzystą lub nieparzystą wiadomość (w zależności od wyniku rzutu monetą).

Biorąc pod uwagę, że Bob zaakceptuje teraz każdą z czterech różnych wiadomości jako prawdziwą, dwie nieparzyste i dwie parzyste, prawdopodobieństwo udanego podszywania się przez strażnika ${{4}\over{8}} = {{1}\over{2}}$. Podobnie, jeśli strażnik czeka na wiadomość wysłaną przez Alice to wtedy prawdopodobieństwo pomyślnego zastąpienia wiadomości o przeciwnej parze w celu błędnego poinformowania Boba o wyniku rzutu monetą będzie również ${{1}\over{2}}$, ponieważ obserwowany komunikat pojawia się w czterech kluczach, z których dwa zawierają każdy z komunikatów o przeciwnej parzystości. Gdyby Wendy po każdej próbie oszustwa dostała informację zwrotną o powodzeniu podstępu, mógłaby zauważyć, że coś się nie zgadza.

W prawdziwym zastosowaniu prawdopodobieństwo sukcesu przy próbie oszustwa podczas uwierzytelnienia jest bardzo małe. Ponadto przedstawiony model nie zapewnia możliwości zmiany klucza przez więźniów w kolejnych komunikatach, aby pozbawić strażnika możliwości użycia wiadomości z poprzedniej wymiany.


Bibliografia

  1. G.J. Simmons, The Subliminal Channel and Digital Signatures. In: Beth T., Cot N., Ingemarsson I. (eds) Advances in Cryptology. Springer, Berlin, Heidelberg, 1985
  2. G.J. Simmons, The Prisoners’ Problem and the Subliminal Channel w Chaum D. (eds) Advances in Cryptology. Springer, Boston, MA, 1th edition, 1984