Лабораторная работа 4
Коды аутентификации сообщений - МАС
Цель: Ознакомиться с основными понятиями, относящиеся к обеспечению целостности и аутентичности сообщений.
Теоретические сведения
Обеспечение целостности сообщения - это невозможность изменения сообщения так, чтобы получатель этого не обнаружил. Под аутентификацией понимается подтверждение того, что информация получена от законного источника, и получателем является тот, кто нужно. Один из способов обеспечения целостности - это вычисление МАС (Message Authentication Code). В данном случае под МАС понимается некоторый аутентификатор, являющийся определенным способом вычисленным блоком данных, с помощью которого можно проверить целостность сообщения.
В некоторой степени симметричное шифрование всего сообщения может выполнять функцию аутентификации этого сообщения. Но в таком случае сообщение должно содержать достаточную избыточность, которая позволяла бы проверить, что сообщение не было изменено. Избыточность может быть в виде определенным образом отформатированного сообщения, текста на конкретном языке и т.п. Если сообщение допускает произвольную последовательность битов (например, зашифрован ключ сессии), то симметричное шифрование всего сообщения не может обеспечивать его целостность, так как при дешифровании в любом случае получится последовательность битов, правильность которой проверить нельзя. Поэтому гораздо чаще используется критографически созданный небольшой блок данных фиксированного размера, так называемый аутентификатор или имитовставка, с помощью которого проверяется целостность сообщения.
Этот блок данных может создаваться с помощью секретного ключа, который разделяют отправитель и получатель. МАС вычисляется в тот момент, когда известно, что сообщение корректно. После этого МАС присоединяется к сообщению и передается вместе с ним получателю. Получатель вычисляет МАС, используя тот же самый секретный ключ, и сравнивает вычисленное значение с полученным. Если эти значения совпадают, то с большой долей вероятности можно считать, что при пересылке изменения сообщения не произошло.
Требования к МАС
Код аутентичности сообщения МАС, называемый также криптографической контрольной суммой, генерируется функцией МАС вида:
MAC = CK(M)
Рассмотрим свойства, которыми должна обладать функция МАС. Если длина ключа, используемого при вычислении МАС, равна k, то при условии сильной функции МАС противнику потребуется выполнить 2k попыток для перебора всех ключей. Если длина значения, создаваемого МАС, равна n, то всего существует 2n различных значений МАС.
Предположим, что конфиденциальности сообщения нет, т.е. оппонент имеет доступ к открытому сообщению и соответствующему ему значению МАС. Определим усилия, необходимые оппоненту для нахождения ключа МАС. Предположим, что k > n, т.е. длина ключа больше длины МАС. Тогда, зная М1 и МАС1 = СK (M1), оппонент может вычислить МАС1 = СKi (M1) для всех возможных ключей Ki. При этом, по крайней мере, для одного из ключей будет получено совпадение MACi = MAC1. Оппонент вычислит 2k значений МАС, тогда как при длине МАС n битов существует всего 2n значений МАС. Мы предположили, что k > n, т.е. 2k > 2n. Таким образом, правильное значение МАС будет получено для нескольких значений ключей. В среднем совпадение будет иметь место для 2k / 2n = 2(k-n) ключей. Поэтому для вычисления единственного ключа оппоненту требуется знать несколько пар сообщение и соответствующий ему МАС.
Таким образом, простой перебор всех ключей требует не меньше, а больше усилий, чем поиск ключа симметричного шифрования той же длины.
Функция вычисления МАС должна обладать следующими свойствами:
- Должно быть вычислительно трудно, зная М и СK (M), найти сообщение М′, такое, что СK(M) = СK(M′).
- Значения СK(M) должны быть равномерно распределенными в том смысле, что для любых сообщений М и M′ вероятность того, что СK(M) = СK(M′), должна быть равна 2-n, где n - длина значения МАС.
- Если М′ получается в результате некоторой известной трансформации М,
т.е. М′ = f(M), то вероятность того что СK(M) = СK(M′), должна быть равна
Pr[СK(M) = СK(M′)] = 2-n, где n - длина значения МАС.
Первое требование не дает противнику возможности создать новое сообщение, соответствующее заданному значению МАС, если он не знает ключ.
Второе требование имеет своей целью воспрепятствовать анализу с перебором всех вариантов при наличии избранного открытого текста. Иначе говоря, если противник не знает K, но имеет доступ к функции вычисления МАС и может предоставить ей сообщения для получения соответствующих значений МАС, то он может проверять различные сообщения до тех пор, пока не обнаружит сообщения, соответствующего данному значению МАС. Если функция вычисления МАС имеет однородное распределение, то метод перебора должен потребовать для этого в среднем 2(n-1) попыток.
Последнее из требований гарантирует, что алгоритм аутентификации не будет слабее для одних частей или битов сообщения, чем для других. Если бы это было не так, то противник, получивший М и СK(M), может попытаться изменить М в сторону известного «слабого места», где можно быстрее обнаружить сообщение, соответствующее имеющемуся значению МАС.
Есть еще одно желательное свойство алгоритма вычисления МАС, которое требуется для защищенности этого алгоритма:
· Вычислительная стойкость. При наличии одной или большего числа пар «текст- МАС» - (xi, CK(xi)), практически невозможно вычислить любую новую пару (x, CK(x)) для любого x ¹ xi.
Другими словами, противник хотел бы получить правильный МАС для некоторого сообщения х. Он может использовать 2 линии атаки: атаку пространства ключей и атаку значения МАС.
Если противник сможет определить ключ, он сможет генерировать правильные значения МАС для любого х. Пусть длина ключа равна k битам и противнику известна одна пара «текст- МАС». Тогда он может вычислить n-битовые значения МАС известного текста для всех возможных ключей. При этом по крайней мере один ключ породит соответствующее значение МАС. Эта фаза атаки потребует усилий пропорциональных 2k. Однако, функция МАС отображает много значений в одно, поэтому может обнаружится много ключей, порождающих правильное значение, и потребуются дополнительные пары «текст- МАС» для тестирования. Уровень дополнительных усилий быстро снижается с каждой дополнительной парой «текст- МАС» и общей верхней оценкой для требуемых усилий может служить 2k.
Противник может также попытаться выяснить значение МАС, не пытаясь найти ключ. Целью в таком случае является либо поиск правильного значения МАС для данного сообщения, либо поиск сообщения, соответствующего данному значению МАС. В любом случае требуемые усилия сравнимы по величине с усилиями, необходимыми для атаки односторонней функции хэширования или функции, обладающей свойством слабой стойкости к коллизиям, а именно с усилиями порядка 2n. В случае МАС данная атака не может быть проведена в автономном режиме без дополнительного ввода данных и противнику потребуются избранные пары «текст- МАС» или знание ключа.
Уровень усилий, необходимых для перебора всех вариантов при атаке на алгоритм вычисления МАС, оценивается величиной min(2k, 2n). Кажется разумным условие, чтобы длины ключа и значения МАС удовлетворяли соотношению min(k, n) ³ N, где N ³ 128 битов.
MAA (Message Authenticator Algorithm)
Этот алгоритм является стандартом ISO. Он выдает 32-битовое хэш-значение и был спроектирован для мэйнфреймов с быстрыми инструкциями умножения.
v=v<<<1e=v xor wx=((((e+y) mod 2^32)۷A۸C)*(x xor Mi))mod 2^32-1y=((((e+x) mod 2^32)۷B۸D)*(y xor Mi))mod 2^32-1
Эти действия повторяются для каждого блока сообщений, Mi, и результирующее хэш-значение получается с помощью XOR x и y. Переменные v и e зависят от ключа. A, B, C и D являются константами. Возможно, этот алгоритм широко используется, но он достаточно не безопасен. Он был разработан давно и не слишком сложен.