Могущество кодов Рида-Соломона, или Информация, воскресшая из пепла

Крис Касперски

Энтропия слепа, но терпелива. Рано или поздно, обстреливая наши позиции по квадратам, она нанесет удар по штабу

 по центру связи. И тогда первая линия обороны уничтожена. И приходится отходить на запасные позиции.

Иными словами, доставать из магнитотеки пакет дисков с копией тома.

Е. В. Лишак

«Тридцать второй день года. (Записки парасистемного программиста)».

Все вы наверняка слышали о существовании помехозащитных кодов Рида-Соломона, широко использующихся в устройствах передачи и хранения данных для обнаружения и исправления как одиночных, так и групповых (!) ошибок. Область их применения необычайно широка – кодеры/декодеры Рида-Соломона можно найти и в ленточных запоминающих устройствах, и в контроллерах оперативной памяти, и в модемах, и в жестких дисках, и в CD-ROM/DVD-приводах и т. д. Благодаря им некоторые продвинутые архиваторы безболезненно переносят порчу нескольких секторов носителя, содержащего архив, а подчас и полное разрушение целого тома многотомного архива. Еще коды Рида-Соломона позволяют защитному механизму автоматически восстанавливать байтики, хакнутые взломщиком и/или искаженные в результате сбоя программного/аппаратного обеспечения. Короче говоря, если владение техникой помехозащитного кодирования не превращает вас в Бога, то, по крайней мере, поднимает на Олимп, где среди бесшумных вентиляторов и безглючных операционных систем снуют великие компьютерные гуру.

В то же время лишь немногие программисты могут похвастаться собственной реализацией алгоритмов Рида-Соломона. Да и зачем? Готовых библиотек море: от прагматичных коммерческих пакетов до бесплатных исходников, распространяемых по лицензии GNU. Как говорится, бери – не хочу[1]. Что ж, в использовании библиотек есть вполне определенный практический смысл, но никакой хакер не доверит управление программе до тех пор, пока не поймет, как именно она работает (а эта публикация именно для хакеров и предназначена, естественно, «хакеров» в хорошем значении этого слова).

С другой стороны, при анализе программного обеспечения, распространяемого без исходных кодов, вы не сможете идентифицировать алгоритм Рида-Соломона, если только заранее не разберетесь во всех его тонкостях. Допустим, вам встретилась защита, хитрым образом манипулирующая с EDC/ECC-полями ключевых секторов, считанных ею с лазерного диска, и каждый такой сектор содержит две умышленно внесенные ошибки (плюс еще ошибки, естественным путем возникающие при небрежном обращении с CD), причем одна из этих ошибок ложная и исправлять ее не нужно. При штатном копировании защищенного диска микропроцессорная начинка CD-ROM автоматически исправляет все ошибки, которые она только может исправить, в результате чего происходит искажение ключевых меток и, как следствие, защищенная программа перестанет работать. Можно, конечно, скопировать диск в «сыром» режиме, т.е. без исправления ошибок, но тогда копия будет содержать как непредумышленные, так и предумышленные ошибки, в результате чего даже при незначительном повреждении оригинала корректирующих возможностей кодов Рида-Соломона уже окажется недостаточно, и диск просто перестанет читаться (а как вы хотели? копирование дисков в сыром режиме ведет к накоплению ошибок и потому крайне непрактично с любой точки зрения).