Механизмы контроля целостности данных

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

Введение

Приведем несколько определений понятия целостности информации:

В руководящих документах Гостехкомиссии РФ целостность информации определяется следующим образом:

Целостность информации – это способность средства вычислительной техники или автоматизированной системы обеспечивать неизменность информации в условиях случайного и (или) преднамеренного искажения (разрушения).

Также распространено определение целостности информации как отсутствие ненадлежащих изменений. Смысл понятия “ненадлежащее изменение” раскрывается Д. Кларком и Д. Вилсоном в их статье “A comparison of Commercial and Military Computer Security Policies”: ни одному пользователю АС, в том числе и авторизованному, не должны быть разрешены такие изменения данных, которые повлекут за собой их разрушение или потерю.

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

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

Метод контрольных сумм

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

Пусть:

a – массив данных, элементами которого являются числовые значения.

Length(a) – количество элементов массива a.

Sum – результат суммирования всех элементов a[i] массива данных a, где i = [1..Length(a)].

CheckSum – контрольная сумма массива a.

MaxVal – максимально возможное числовое значение CheckSum.

Тогда контрольной суммой массива a будет являться величина CheckSum полученная путем деления с остатком суммы всех элементов массива Sum на максимально возможное числовое значение контрольной суммы, увеличенное на единицу или:

 CheckSum = Sum mod (MaxVal+1)

Рассмотрим вышеописанный механизм расчета контрольной суммы на примере.

Пусть есть некая последовательность байт:

a = 0A 11 B3 58 A2 CE 78 6D 90 01

Будем считать, что под контрольную сумму CheckSum нам выделяется ячейка памяти размерностью 1 байт (максимальное значение MaxVal = FF или 255 в десятичной системе исчисления)

Рассчитаем сумму байт последовательности:

Sum(a[i]) = 0A+11+B3+58+A2+CE+78+6D+90+01=40C(или 1036 в десятичной системе исчисления), где i = [1..10].

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

CheckSum = Sum mod (MaxVal+1) = 40C mod (FF+1) = 1036 mod (255+1) = 12 (0C в шестнадцатеричной системе исчисления)

Таким образом, мы получили, что контрольной суммой массива байт a является числовое значение 12. Стоит заметить, что при изменении какого-либо элемента массива a изменится и его контрольная сумма.

Использование метода контрольных сумм началось еще на заре вычислительной техники, и он применяется до сих пор в некоторых протоколах передачи данных.

Рассмотрим плюсы и минусы метода:

Плюсы:

• Простота реализации
• Высокая производительность

Минусы:

• Равенство полученных значений контрольных сумм не дает гарантии неизменности информации
• При известной контрольной сумме крайне просто “подогнать” данные так, чтобы в результате получилось корректное значение

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

Метод “циклического контрольного кода”

Более совершенным способом контроля целостности данных является, так называемый, метод “циклического контрольного кода”(cyclic redundancy check — CRC). Алгоритм широко используется в аппаратных устройствах (дисковые контроллеры, сетевые адаптеры и др.) для верификации неизменности входной и выходной информации, а также во многих программных продуктах для выявления ошибок при передаче данных по каналам связи.

В основе метода CRC лежит понятие полинома или многочлена. Каждый бит некоторого блока данных соответствует одному из коэффициентов двоичного полинома. Например, полином шестнадцатеричного числа 7A (двоичная запись — 1111010) будет выглядеть следующим образом:

A(x) = 1*x⁶+1*x⁵+1*x⁴+1*x³+0*x²+1*x¹+0*x⁰ = x⁶+x⁵+x⁴+x³+x

Таким образом, любой блок данных представляет собой последовательность битов, которую можно представить в виде двоичного полинома A(x). Для вычисления контрольного кода необходим еще один полином G(x), называемый порождающим полиномом. Для каждой реализации алгоритма контроля CRC порождающий полином выбирается заранее произвольным образом. Например, для контроллеров гибких магнитных дисков порождающий полином G(x) = x¹⁶+x¹²+x⁵+1.

Пусть R(x) — некий полином. R(x) называется контрольным кодом полинома A(x) при порождающем полиноме G(x), если R(x) является остатком от деления полинома A(x)*x^r на G(x), где r – степень полинома G(x).

R(x) = (A(x)*x^r) mod G(x)

Так же, как и для контрольных сумм, контрольный код не занимает много места (обычно 16/32 бита), однако вероятность обнаружения ошибки существенно выше. Например, в отличие от контрольных сумм метод CRC сможет обнаружить перестановку двух байт либо добавление единицы к одному и вычитание единицы из другого.

Рассмотрим плюсы и минусы метода:

Плюсы:

• Простота реализации
• Высокая производительность
• Высокая вероятность обнаружения ошибки

Минусы:

• Равенство полученных значений контрольных сумм все равно не дает гарантии неизменности информации
• При известной контрольной сумме не составляет большого труда написать программу, которая будет “подгонять” данные так, чтобы в результате получилось корректное значение, хотя это намного сложнее, чем в предыдущем методе контрольных сумм

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

Однонаправленные функции хэширования

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

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

Пусть результатом применения функции f к A является набор данных B (хэш).

f(A) = B

Функция f является однонаправленной, если не существует такой функции g, что

g(B) = A

либо такую функцию g крайне сложно построить.

Коллизией называется ситуация, когда разным наборам входных блоков данных соответствует один хэш.

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

Пусть f(A)=B. Не существует такого A’ либо его крайне сложно найти, что f(A’)=B. Чем больше длина хэша, тем труднее найти соответствующий набор входных данных.

Среди алгоритмов хэширования наибольшей известностью пользуются:

• Алгоритм MD5 (длина хэша – 128 бит), автор Ron Rivest, создатель алгоритма шифрования с открытым ключом RSA
• Алгоритм SHA-1 (длина хэша – 160 бит), созданный усилиями специалистов Национального института по стандартизации и технологиям (NIST) и Агентства национальной безопасности (NSA)

Также стоит отметить российский стандарт на функцию хэширования ГОСТ Р34.11-94.

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

Список литературы:

1. П.Н.Девянин, О.О. Михальский, Д.И. Правиков и др. “Теоретические основы компьютерной безопасности”, Учебное пособие для вузов
2. Bruce Schneier, “Applied cryptography: Protocols, Algorithms and Source Code in C”, John Wiley&Sons, 1995
3. W. David Schwaderer “C Programmer’s Guide to Netbios”, Howard W. Sams&Company, 1988
4. Гостехкомиссия России, “Руководящий документ: Защита от несанкционированного доступа к информации. Термины и определения.” – М.: Военное издательство, 1992.
5. Clark D., Wilson D. A comparison of Commercial and Military Computer Security Policies / Proce. Of the 1987 IEEE Symposium on Security and Privacy. – Oakland. Cal., 1987.
6. Жельников В. “Криптография от папируса до компьютера” – М.: ABF, 1996.

Евгений Климов