Как общаются шпионы или зачем нужны алгоритмы

Один из вопросов, который я довольно часто слышу от начинающих разработчиков, звучит примерно так:

«А зачем мне вообще нужны алгоритмы?»

Зачем разбираться с битовыми операциями? Зачем думать об алгоритмической сложности? Зачем на собеседованиях дают все эти странные задачи, если в реальной работе я буду писать API, перекладывать JSON из одного сервиса в другой и подключать очередную библиотеку?

Вопрос, надо сказать, вполне справедливый, особенно когда в очередной раз сидишь перед задачей, в которой предлагается что-нибудь сдвинуть на три бита вправо, наложить маску 0xFE, а потом почему-то ещё радоваться полученному результату.

Вместо абстрактных рассуждений о том, насколько алгоритмы развивают мышление, предлагаю посмотреть на совершенно обычную картинку.

просто фотография

На ней нет ничего необычного. Несколько объектов, цвета, фон — всё то, что мы видим в тысячах изображений каждый день. Если открыть её в браузере — браузер покажет картинку. Если отправить её в мессенджер — собеседник увидит картинку. Если положить её на сайт — пользователь увидит ту же картинку.

Но если взять ровно этот же файл и передать его специальной программе — например, декодеру на h-message.com — из изображения можно получить текстовое сообщение. И нет, текст не написан микроскопическим белым шрифтом в правом нижнем углу. Он действительно спрятан внутри самого изображения.

Но как?

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

Стеганография: когда никто не должен знать даже о существовании сообщения

Пора определить ключевые термины и развеять один стереотип. То, что сделано с картинкой, называется стеганографией. Это понятие очень часто путают с криптографией. Хотя подход и задачи у них разные.

У криптографии принцип: «Вот сообщение. Ты видишь, что оно существует, и не можешь прочитать его без ключа». А наш второй герой, стеганография, пытается решить совсем другие задачи: «Какое ещё сообщение? Здесь ничего нет, уверяю вас. Просто самая обычная картинка с котиком». То есть скрывается не только содержание, но и сам обмен сообщениями.

Эти два подхода отлично комбинируются. И тогда даже если кто-нибудь обнаружит скрытые данные, ему как минимум придётся потом разбираться с шифрованием. Но пока оставим криптографию в стороне и рассмотрим ещё один вопрос: куда именно можно положить данные?

Вообще, картинка для передачи скрытого сообщения не обязательна. Простейший канал — текст. Можно договориться о правиле, по которому, из обычного текста извлекается второй, скрытый текст.

Например, значение может иметь первое слово каждого абзаца. Для обычного читателя перед ним будет вполне связный текст, но если взять только первые слова и поставить их подряд, получится совсем другое сообщение.

Похожий приём можно проделать со строками: использовать первые буквы каждой строки или предложения. Именно так работают акростихи — текст выглядит обычным стихотворением или набором фраз, но первые буквы строк складываются в отдельное слово или предложение.

Пятница, вечер — пора отдыхать,

Решили мы «маленький фикс» заливать,

Опять всё сломалось — пришлось откатить,

До понедельника будет трудно дожить.

Схема может быть и намного сложнее. Позиции букв можно определять по заранее известному ключу, математической последовательности или псевдослучайному алгоритму. Тогда без знания правила будет очень сложно понять, какие именно символы являются частью сообщения.

По сути, во всех этих примерах происходит одно и то же: у отправителя и получателя есть дополнительная договорённость о том, как и на какую часть обычного объекта нужно смотреть.

Именно поэтому стеганография не привязана к какому-то конкретному формату данных. Скрывать информацию можно в расположении слов, выборе букв, пробелах, цветах, звуках, временных интервалах — практически в любом объекте, где есть возможность сделать несколько вариантов, не меняя его очевидного смысла.

Кстати, чтобы далеко не ходить за примером, попробуйте взять последнюю букву каждого восьмого слова из этого раздела в первых 6 абзацах.

Что вообще такое картинка

А теперь вернёмся к изображениям и разберёмся, какие варианты стеганографии здесь доступны.

Когда мы говорим «картинка», на самом деле за этим словом может скрываться несколько совершенно разных способов представления изображения.

Например JPEG, PNG, GIF, WebP, SVG, AVIF и так далее. И это не просто разные расширения одного и того же файла. Внутри они могут быть устроены принципиально по-разному. SVG, например, вообще может описывать изображение при помощи геометрических примитивов: нарисовать линию отсюда сюда, построить прямоугольник такого размера, залить его таким цветом. А PNG или JPEG обычно представляют растровое изображение.

Сильно упрощая, растровая картинка — это огромная таблица из маленьких цветных точек — пикселей.

Если изображение имеет разрешение 1920 × 1080, в нём:

1920 × 1080 = 2 073 600 пикселей

Чуть больше двух миллионов.

Почему PNG?

Для статьи я решил использовать формат изображения truecolor PNG. И это не случайно.

Например, есть картинка в JPEG и есть картинка в PNG. Обе прекрасно открываются браузером. Обе можно отправить другому человеку. Но внутренне эти форматы ведут себя очень по-разному. Главное различие для нас — сжатие.

Формат JPEG обычно использует сжатие с потерями — lossy compression. А PNG — сжатие без потерь — lossless compression.

JPEG создавался с очень разумной идеей: для качественного отображения картинки совершенно не обязательно хранить каждый исходный пиксель абсолютно точно. Можно немного изменить некоторые значения так, что человек не заметит разницы, зато файл станет значительно меньше.

Для фотографии это обычно не проблема. А вот для стеганографии — огромная проблема.

Потому что если мы собираемся сознательно менять отдельные биты изображения и использовать их для хранения данных, нам необходима уверенность в том, что после сохранения эти биты останутся там, где мы их оставили. И в этом смысле PNG гораздо надёжнее.

После декодирования PNG мы получим исходные значения пикселей без потерь. Поэтому для демонстрации классической пиксельной стеганографии PNG практически идеален.

Итак, приступим к рассмотрению вариантов стеганографии в PNG.

Вариант первый: просто положить данные рядом с картинкой

Начнём с самого простого варианта. Файл изображения — это определённая последовательность байтов. Программа, которая умеет читать PNG, разбирает его структуру, находит необходимые части и восстанавливает изображение.

Но совершенно не обязательно, что любой просмотрщик будет использовать каждый байт файла. В некоторых ситуациях можно добавить дополнительные данные после основной структуры изображения.

Получится примерно так:

[ Данные PNG ][ Секретное сообщение ]

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

image.png

Работает? В некоторых случаях — да. Стеганография? Формально что-то похожее. Но довольно примитивное.

Стоит посмотреть на файл hex-редактором или сравнить его структуру со спецификацией, как дополнительный payload быстро обнаружится.

Поэтому идём дальше.

Вариант второй: использовать структуру PNG

Файл PNG — не просто непрерывный поток пикселей. Он состоит из блоков, которые называются chunks. Очень упрощённо структура выглядит примерно так:

PNG signature
IHDR
IDAT
IDAT
...
IEND

Блок IHDR содержит техническую информацию об изображении.

Например:

• ширину;

• высоту;

• глубину цвета;

• тип цвета;

• способ сжатия.

Блок IDAT содержит непосредственно данные изображения. А IEND отмечает конец PNG.

Кроме обязательных chunks формат допускает дополнительные блоки. Например, текстовые метаданные. А значит, теоретически мы можем положить наше сообщение туда. Получится очень удобный контейнер. Картинка продолжит нормально открываться. Пользователь ничего необычного не увидит.

Но есть одна проблема.

Если специалист посмотрит на структуру PNG, наличие дополнительного chunk обнаружится очень быстро. Фактически мы просто положили сообщение в ящик и написали на ящике: “METADATA”.

image.png

Можно сделать хитрее.

Вариант третий: изменить саму картинку

В изображении для каждого пикселя нужно каким-то образом записывать его цвет. Один из распространённых вариантов — модель RGB. Цвет представляется тремя компонентами:

R — Red
G — Green
B — Blue

Каждая цветовая компонента обычно может принимать значение от 0 до 255.

Например:

R = 255
G = 0
B = 0

даст ярко-красный цвет,

R = 0
G = 0
B = 0

— чёрный.

Иногда добавляется ещё один канал:

A — Alpha

Он отвечает за прозрачность. Получается RGBA. Но сейчас для простоты достаточно RGB.

Возьмём какой-нибудь совершенно случайный пиксель:

R = 154
G = 201
B = 78

Для нас это просто три числа. Для компьютера каждое из этих чисел можно представить в двоичной системе.

Например:

154 = 10011010
201 = 11001001
 78 = 01001110

И вот здесь у нас внезапно появляется кое-что очень интересное.

Посмотрим на первое число:

10011010

Самый левый бит имеет очень большой вес. Если изменить его:

10011010 = 154
00011010 = 26

Цвет изменится очень заметно.

А если изменим самый правый бит:

10011010 = 154
10011011 = 155

То исходное значение будет отличаться всего на единицу.

Для компьютера, конечно, 154 ≠ 155. Это разные числа. Но для человеческого глаза цветовая компонента со значением 154 от компоненты со значением 155 не отличается почти никак. И вот здесь появляется лазейка.

Самый правый бит двоичного числа называется “младший значащий бит” (Least Significant Bit, или сокращённо LSB).

Если число выглядит так:

10011010
       ↑
      LSB

то именно этот бит оказывает минимальное влияние на числовое значение. Изменив его, мы можем увеличить или уменьшить значение цветового канала максимум на единицу.

А значит, можно сделать следующее:

использовать младшие биты цветовых каналов не только для представления цвета, но и для хранения собственных данных.

Звучит сложнее, чем работает на практике.

Представим, что мы хотим спрятать один бит в конкретной точке изображения.

Берём одну цветовую компоненту пикселя:

154 = 10011010

Сейчас её LSB равен 0. Нам нужен 1.

Меняем:

10011010
       ↓
10011011

Получаем:

155

Визуально цвет практически не изменился. Но теперь последний бит хранит нашу единицу. Если нам нужно спрятать 0, мы обеспечиваем, чтобы младший бит был равен нулю. И всё.

На этом базовая идея LSB-стеганографии заканчивается.

Как спрятать букву?

Но одного бита нам, конечно, мало. Возьмём символ, например A в латинской раскладке.

В кодировке ASCII:

A = 65

В двоичном виде:

01000001

То есть нам надо запрятать в картинку восемь бит. Теперь берём восемь цветовых каналов изображения из трёх первых пикселей.

Например:

10011011
01100110
11101001
10110011
00110101
11100010
01010111
11001000

И заменяем последний бит каждого значения битом нашего сообщения.

После изменения:

10011010
01100111
11101000
10110010
00110100
11100010
01010110
11001001

Поздравляю. Мы только что спрятали букву внутри цвета изображения.

А сколько текста можно туда положить?

Довольно много. Возьмём Full HD изображение. При разрешении 1920 × 1080 количество пикселей составит 2 073 600. Предположим, мы используем RGB и можем взять по одному младшему биту каждого цветового канала. Тогда на каждый пиксель приходится 3 бита.

Итого:

2 073 600 × 3 = 6 220 800 бит

Делим на восемь — 777 600 байт. Это примерно 759 KiB потенциальной ёмкости.

Конечно, в реальной реализации часть пространства понадобится для служебных данных:

• длины сообщения;

• версии формата;

• контрольной суммы;

• идентификатора;

• параметров алгоритма;

• error correction;

И использовать каждый доступный LSB тоже далеко не всегда хорошая идея. Но порядок величины интересный. В обычной Full HD картинке существуют миллионы мест, каждое из которых можно изменить настолько незначительно, что пользователь этого не заметит.

Как сообщение извлекается обратно?

Декодирование — практически тот же процесс в обратную сторону. Программа получает изображение и начинает читать выбранные цветовые каналы. Из каждого значения извлекается LSB.

Например:

# пиксель 1
154 = 10011010 → 0
103 = 01100111 → 1
232 = 11101000 → 0
# пиксель 2
178 = 10110010 → 0
 52 = 00110100 → 0
226 = 11100010 → 0
# пиксель 3
 86 = 01010110 → 0
201 = 11001001 → 1

Получаем поток:

010000010110...

Разбиваем его по восемь бит:

01000001
01100010
...

Преобразуем в байты. А байты уже можно интерпретировать как UTF-8 или другой формат.

01000001 → 65 → A

Но тут возникает логичный вопрос.

Откуда программа узнает, где сообщение заканчивается?

Есть несколько вариантов. Например, в начале скрытых данных можно записать длину.

[ LENGTH ][ PAYLOAD ]

Предположим, первые 32 бита обозначают количество байтов. Декодер сначала читает эти 32 бита.

Получает:

137

А затем знает, что нужно прочитать ещё ровно 137 байтов. Можно использовать специальный маркер конца. Можно хранить заголовок собственного формата.

Например:

HM01
length
checksum
payload

И вот тут наша игрушка постепенно начинает превращаться во вполне настоящее проектирование протокола. А дальше становится ещё интереснее.

Кто сказал, что нужно использовать пиксели подряд?

Самая очевидная реализация LSB выглядит примерно так:

пиксель 1
пиксель 2
пиксель 3
пиксель 4
пиксель 5
...

Мы идём по изображению слева направо, сверху вниз и записываем сообщение.

Работает.

Но это очень предсказуемо. Если кто-то подозревает, что мы используем LSB, ему достаточно начать читать младшие биты с самого начала изображения.

Порядок изменённых пикселей можно устанавливать алгоритмически. Например, у нас есть секретный ключ:

my-secret-key

Из него можно получить seed для псевдослучайного генератора. После этого генератор создаёт последовательность индексов пикселей:

1842
92831
441
71920
...

И данные записываются уже не подряд, а в определённые позиции изображения. Чтобы прочитать сообщение, второй стороне нужно:

1. знать алгоритм;

2. знать seed или ключ;

3. воспроизвести ту же последовательность;

4. прочитать LSB именно из этих пикселей.

Само сообщение при этом физически распределено по изображению. Это уже гораздо интереснее чем обычная последовательность младших битов слева направо.

А можно выбирать пиксели ещё хитрее. Например, использовать не все части изображения одинаково. Представьте фотографию, на которой половина изображения — идеально ровное голубое небо. А вторая половина — деревья, трава, листья и множество мелких деталей. Изменения в однородной области потенциально легче анализировать статистически. А среди текстур и шумных участков небольшие изменения будут менее заметны.

Значит, алгоритм может сначала оценить изображение, а затем выбирать области с высокой детализацией.

Например, учитывать:

• локальный контраст;

• градиенты;

• края объектов;

• дисперсию цвета;

• уровень шума;

• текстурность.

И записывать payload преимущественно туда. То есть вместо “возьми следующий пиксель” мы приходим к “найди подходящий пиксель согласно некоторой функции”. Вот вам уже вполне нормальная алгоритмическая задача.

Что будет, если картинку изменить?

А теперь плохая новость. Базовая LSB-стеганография довольно хрупкая. Представьте, что мы спрятали сообщение в младших битах PNG.

А потом кто-нибудь:

• уменьшил изображение;

• увеличил изображение;

• применил blur;

• изменил яркость;

• прогнал файл через оптимизатор;

• преобразовал PNG в JPEG;

• сделал скриншот;

• пересохранил картинку через графический редактор.

Пиксели изменятся. А вместе с ними могут исчезнуть наши младшие биты.

Если:

154 = 10011010

после обработки превратилось в:

152 = 10011000

для глаза разница всё ещё почти незаметна. Но наш спрятанный бит изменился. Поэтому здесь важно не перепутать две разные задачи: скрытность и устойчивость.

Псевдослучайное распределение данных по пикселям хорошо помогает сделать расположение payload менее очевидным. Но само по себе оно не делает обычный LSB устойчивым к серьёзному преобразованию изображения. Если чтобы payload пережил модификации картинки — алгоритм должен быть сложнее.

Первое очевидное решение — избыточность. Вместо того чтобы записать бит один раз мы можем записать его несколько раз. После изменения изображения часть значений может повредиться. Но оставшиеся фрагменты payload всё ещё будут хранить необходимую информацию. Это простейшая схема.

Более серьёзный подход — использовать коды коррекции ошибок. Например, Reed-Solomon, BCH или другие схемы, позволяющие восстановить исходные данные даже при повреждении части payload.

Можно также записывать разные фрагменты сообщения в разные области изображения. Или выбирать пиксели согласно ключу и одновременно распределять копии критичных данных по нескольким регионам. Но если нам нужна действительно высокая устойчивость к изменению размера картинки, JPEG-компрессии и другим преобразованиям, простой LSB не сработает. А это уже тема для другой статьи.

Можно ли использовать LSB для защиты собственного контента?

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

Визуально:

image_A ≈ image_B

Для человека они одинаковы. Но внутри каждой версии можно разместить уникальный идентификатор:

customer_18421
customer_51920
customer_77311

И если одна из копий впоследствии окажется где-нибудь в публичном доступе, теоретически можно попробовать определить, откуда она появилась. Это называется fingerprinting.

Другой вариант — маркировка собственного контента для последующего поиска или подтверждения происхождения. Например, компания публикует набор изображений и в каждое вставляет проверяемую подпись или идентификатор.

Позже можно проверить является ли этот файл оригиналом или производной от нашего материала.

Разумеется, здесь появляются сложные вопросы.

• Насколько маркировка устойчива?

• Можно ли удалить идентификатор?

• Как избежать ложных срабатываний?

• Что случится после обрезки изображения?

• Что случится если сделать скриншот?

• Как быть с изменением разрешения картинки?

• Что произойдёт после генеративного редактирования?

Поэтому реальная система защиты контента — значительно сложнее нашего учебного примера LSB. Но начать думать о такой системе можно именно с этой простой модели.

Можно ли обнаружить стеганографию?

Если мы научились что-то прятать, естественный следующий вопрос — можно ли это найти?

Этим занимается стегоанализ. Самый примитивный вариант это попытаться прочитать LSB и посмотреть, не складываются ли они во что-нибудь осмысленное.

Но если используется:

• ключ;

• псевдослучайный выбор пикселей;

• шифрование payload;

• error correction;

• нестандартная схема размещения,

такой подход быстро перестаёт работать. Тогда можно анализировать статистические свойства изображения. Например, чрезмерно активная модификация младших битов способна нарушать естественные закономерности распределения значений.

• У настоящей фотографии пиксели появляются не случайно.

• Соседние значения коррелируют.

• Камера имеет определённый шум.

• Сжатие оставляет определённые статистические следы.

Изменение большого количества LSB может немного изменить эти распределения. Человек ничего не увидит. Но статистический анализ может заметить аномалию.

Значит ли это, что любой PNG теперь подозрительный? Конечно нет. Иначе мы довольно быстро сойдём с ума. Но этот пример хорошо показывает одну важную вещь из информационной безопасности. Тип файла не определяет всё содержание информационного обмена.

Мы привыкли мыслить примерно так:

.jpg → картинка
.mp3 → музыка
.pdf → документ

Но с точки зрения информационной теории любой достаточно сложный контейнер потенциально можно использовать ещё и как носитель дополнительного сигнала.

• Изображения.

• Аудио.

• Видео.

• Текст.

Даже временные интервалы между сетевыми запросами. Если две стороны заранее договорились, какое свойство интерпретировать как данные, появляется канал связи.

Представьте, что две системы обмениваются обычными запросами.

Но договорились:

запрос через 1 секунду = 0
запрос через 2 секунды = 1

Или определённая последовательность заголовков. Или изменение регистра символов. Или выбор одного из нескольких эквивалентных слов.

И вот теперь — зачем разработчику алгоритмы

Помните вопросы из начала?

Зачем мне алгоритмы? Зачем все эти биты? Почему на интервью меня спрашивают про маски?

Ну вот прямо сейчас у нас появились:

• двоичное представление чисел;

• побитовые операции;

• маски;

• последовательности байтов;

• кодировки;

• обход массивов;

• преобразование данных;

• контроль целостности;

• оценка ёмкости;

• выбор элементов по определённому алгоритму.

Например, чтобы принудительно установить младший бит числа в 0, можно воспользоваться маской.

Концептуально:

value AND 11111110

Последний бит обнулится. А чтобы установить его в 1:

(value AND 11111110) OR 00000001

Вот вам совершенно настоящий практический пример тех самых битовых операций, которые обычно кажутся начинающему разработчику чем-то придуманным исключительно авторами LeetCode.

Вместо заключения

Тема LSB — это не что-то инновационное, лично я начал разбираться с этим инструментом примерно двадцать лет назад. Именно тогда мне больше всего понравилась именно мысль, что мы привыкли воспринимать данные очень буквально:

• Текст — это символы.

• Картинка — это пиксели.

• Звук — это waveform.

Но почти в любом достаточно сложном объекте существует пространство небольших вариаций.

Два текста могут означать одно и то же, но использовать немного разные слова. Два изображения могут выглядеть одинаково, но отличаться младшими битами тысяч пикселей. Два аудиофайла могут звучать одинаково, но иметь небольшие различия в сигнале. И эти различия тоже могут быть информацией. Именно поэтому тема стеганографии сейчас снова становится настолько интересной.

А напоследок у меня остаётся только один вопрос.

В следующий раз, когда сотрудник вашей компании отправит наружу совершенно безобидный PNG размером пару мегабайт, система безопасности увидит: “image/png”. Корпоративная DLP скажет: “это картинка”, а антивирус скажет: “ничего подозрительного”, а пользователь скажет: “да это просто мем”.

Возможно, так и есть. Но точно ли ваша служба информационной безопасности знает, что именно находится внутри этой картинки?