Криптография, 05 лекция (от 29 октября)

Материал из eSyr's wiki.

[править] Аутентификация сообщений

Еще раз суть задания про DES.

У вас есть черный ящик, который шифрует передаваемую строку одним раундом DES. Он выполняет один раунд перестановки и подстановки. При этом ключ вам неизвестен, он определяется параметром id.

Задача -- выяснить ключ.

Размер блока 64 бита, размер ключа 56 бит. Описание алгоритма и s-box есть в Википедии.

Дедлайн второго задания 6 недель -- середина декабря.

Если вопросов нет, перейдём к следующей теме.

[править] Задача аутентификации

В прошлый раз было про потоковое шифрования. В позапрошлый было про блочное шифрование.

Механизмы симметричного шифрования решают задачу конфиденциальности. Кроме неё есть целостность, аутентификации и отказ от авторства.

Ясно, что само по себе шифрование гаммой не обеспечивает невозможности подделки. Изменили один бит -- пришло сообщение с измененным одним битом.

Сам шифр не включает механизмов обнаружения изменений в шифротексте.

Иначе говоря, у нас проблема аутентификации.

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

Представим, что у нас сообщение на естественном языке. Можем ли мы убедиться, что сообщение не было изменено?

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

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

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

preimage, second preimage, collision --- атаки на контрольные суммы.

1. возможность восстановить исходный текст по контрольной сумме
1. по исходному тексту и хэшу найти второй открытый текст с таким же суммой
1. найти два сообщения с одинаковыми суммами.

[править] MAC

Message authentification code -- MAC. По ключу и тексту сгенерировать аутентификационный код.

Как использовать? Отправитель передает текст и результат функции аутентификации. Получатель дает на вход текст и секретный ключ и проверяет совпадение аутентификационных кодов.

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

Блочное шифрование? Как?

[править] CBC MAC

Самый простой механизм CBC mac.

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

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

Какие недостатки?

Свойство лавинности неочевидно. Почему неочевидно? Вообще непонятно, что будет. Давайте посмотрим на свойства блочного шифра. Когда мы изменяем 1 бит в открытом тексте, унас изменяется половина бит выходного текста. Значит, нет оснований предполагать, то здесь не будет лавинного эффекта. Начиная со второго блока у нас есть вероятность изменить хоть все биты.

Какие ещё проблемы? Пример с паддингом, пример с коллизиями из-за парадокса о днях рождениях.

Кто вспомнить, как реализовывалась атака с паддингом? Из-за чего она была возможна? Мы подбирали последний блок. Чего мы можем делать, как атакующий, если у нас сообщения имеют переменную длину и получатель не знает заранее длину получаемых сообщений?

IV = 0
C1 = E(T1)
C2 = E(T2 ^ C1)
C3 = E(T3 ^ C2)

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

T4 = C3 ^ TX

С4 = E(C3^C3^TX) = E(TX)

Чего мы добьемся? Мы знаем какой у такого блока шифр и какая контрольная сумма будет у такого блока.

О чем нам говорит такая атака. Расширяя сообщение таким тривиальным образом мы можем генрировтаь другие сообщения, контрольные суммы которых будут признаны действительными. В чем проблема и как еенужно решить? Нужно, чтоб C3 не сокращалось. Надо понимать, что этот режим CBC используется повсеместно. Например, в 90% случаях в https будет оно. Или rc4. Две проблемы, одна хуже другой -- beast и rc4. Про beast поговорим, там есть нормальное криптографическое решение.

Но нельзя просто так взять и сменить режим шифрования. Тем более, что CBC не так уж плох.

Решение простое, надо записывать сообщение и его длину. Есть специальный вид паддинга, когда сообщение дополняется своей длиной. Очень удобно.

[править] Криптографические хэш-функции

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

1. ее легко вычислить для сообщения любой длины
1. по хэшу нельзя восстановить текст(preimage)
1. нельзя подменить текст не изменив хэш(second preimage)
1. нельзя подобрать два сообщщения так, чтобы у них был одинаковый хэш (collision)

Какие существуют современные алгоритмы хэширования?

[править] MD4/MD5

md4|md5. На текущий момент не считаются стойкими. Хотя md5 всё ещё широко распространен. Для него существуют атаки на коллизии и на второй прообраз. Когда семейство функций md начало показывать своб слабость nist начал работу по разработке новго семейства алгоритмов хэширования. Сеймество назвали sha. Их несколько, отличаются размером выходного блока. sha1(168 бит), sha256, sha384, sha512. Считается, что никаких особенных закладок в них нет. Их дизайн сильно напоминает md5.

[править] SHA

sha1 были походи по дизайну на md5 и они попали под подозрение. Несколько лет назад nist открыл конкурс на создание нового алгоритма хэширования. Конкурс законченЮ победитель есть, но бюрократически процедура стандартизации еще не завершена. Но в следующем году наверное будем уже говрить про sha3.

Базовая часть алгоритма хэширования -- это функция сжатия.

Криптографическая функция получает на вход два блока длинной 128 бит в один блок длиной 128 бит. Короче говоря, преобразует два блока в один.

Какое ее важное применение?

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

Что делать если текст не делится ровно на блоки? Паддинг. В конструкциях Merkle–Damgård для паддинга используется длина сообщения.

[править] Как применяются хэш-функции?

Заем они могут быть нужны в реальной жизни помимо генерации MAC.

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

Как может выглядеть атака на такой криптоконтейнер? Шифруем файлы на диске на основе пароля, что можно сделать? Пободрать по словарю, особенно используя данные о пользователе. Полагаемся на то, что пароль принадлежит небольшому подмножеству пространства ключей. В яндексе наблюдаем за 50 миллионов пользователей и можем анализировать статистические характеристики паролей. Есть много стсатей про стойкость паролей и статистические данные. распространены 12345, 123456, gfhjkm, password. Открытием был пароль спартак. Последний раз смотрели на сэмпл из 200000 паролей. Спартак занимал одну промилле. Кстати, теперь распространенную фразу нельзя задать как пароль. У твиттера есть аналогичный черный список слов, которые нельзя использовать как пароли.

В реальной жизни нельзя ожидать, что пользователь выберет случайный пароль.

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

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

Что нам это дает? Генерация ключа шифрования занимает заметное время. Можожно подобрать количество итераций pbkdf так, чтобы это занимало 1 секунду. Для пользователя это не проблема. А вот когда мы говорим про атаку по словарю, то подбор даже 600 паролей займет уже 10 минут. Удорожаем атаку по перебору паролей и защищаем пользователя даже если его пароль будет доступен по словарю.

Другое применеие -- хранение паролей. Как хранятся пароли в ос или крупных приложениях крупных компаний. JohnThe Reaper -- програма подбора паролей по хэшам. Шифровать пароли и их хранить нужно весьма специальным образом, чтобы не бояться разрушительных атак. Это произошло на почве парольной атаки на linkedin. Это такая странная соц сеть, которая называет себя социальной, хотя по всему прочему это обычная соц сеть. Отличия от фейсбука -- что вместо того чтобы написать где вы путешествовали и как зовут вашу девушку, там вы пишите свои профессиональные достижения.

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

Обычно подход другой. Берем пароль. Считаем хэш, сохраняем. Это используется в продуктах microsoft в system authentification manager. Хорошо -- если злоумышленник получил доступ к базе, то он не узнает напрямую пароли пользователей. Если хэш функция хорошая, то легко он пароль назад не вычислит. Проверка происходит просто -- вычисляется хэш от того, что ввел пользователь. поскольку считается, что хорошие хэшфункции неуязвимы к second preimage атаке, это значит, что маловероятно, что человек ввел другой пароль.

Какие проблемы? Были у linkedin, а теперь есть у microsoft. У одинаковых паролей одинаковый хэш. По базе видно, у кого одинаковый пароль. Учитывая известность статистического распределения паролей, это уязвимость -- можно выбрать один хэш для атаки и получить доступ к паролям большого количества пользователей.

Еще одно -- мы можем захэшировать один раз словарь заранее.

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

Как от этого защититься?

"Зашифровать базу и всё.". От sql инъекций это не спасет, они получают доступ как легитимное приложение.

"Сразу расшифровывать и сразу сравнивать." Что-то такое есть у оракл. Но, где-то должно быть сравнение хэша с тем, что ввел пользователь. И если этот уровень будет скомпрометирован, то шифрование не поможет.

Что еще можно делать? Соли. Будем добавлять случайное значение к паролю, который вводит пользователь. Хэшируем связку, соль хранить рядом.

Какого размера должна быть соль? "Большой". "Чтобы обеспечить уникальность". Как мы оцениваем вероятность отсутсвия двух одинаковых случайных величин в потоке?

Пусть у нас в базе 2^32 паролей. Какой разумный размер соли? Оставляем на дом. Этот вопрос задам в следующий раз.

Какие ещё есть проблемы с функциями хэширования в этом месте?

Мы пытаемся неэкономно расходовать процессорное время. У линкедин была такая проблема -- их хэши были не посолены. Был sha1 с нестандартным изменением 1 байта. Вся хакерская братия с гиканьем и улюлюканьем кинулась искать словари в этих паролях.

Первое куда выложил хакер эту базу -- это был яндекс диск. Было развлечение, потому что собрали все ипшники, тех, кто их скачал. А на сб яндекса наседал линкедин, попутно еще пытяась что-то выяснить о правоохранительных органах РФ. А яндекс отлично проверил скорост скачивания с яндекс диска из самых азных мест, особенно из США.

Посоленность позволяет эффективно заторомзить атакующего с точки зрения процессорного времени. Но надо понимать, что алгоритмы sha1 очень эффективно реализуются на gpu. Скорость повышается на несколько порядков. Для атакующего на сильно меняется трейдофф.

Допустим на доманей машине у пользователя считалось 1 секунду. А у атакующего 1000 узлов по 4 gpu в каждом. Он в 4 миллионов раз быстрее. Чтобы его застаивть считать пароль одну секунду, у пользователя его надо считать 4 миллиона секунд.

Атакующий почти всегда имеет доступ к большому объему cpu. Он может сделать предвычисление. Да и просто у него больше cpu.

Каким же образом от этого можно защититься?

Главная проблема gpu -- быстрые процессоры, но мало оперативной памяти. Если бы функция хэширования требовала большого объема оперативной памяти, ее нельзя было бы делать на gpu.

Как сделать такую функцию?

Мы умеем шифровать блок данных. Генерировать гамму любой длины. Вычислять хэш.

Сделать огромную гамму и от неё хэшировать-хэшировать-хэшировать? Близко, почти.

Берём гамму размером 10Гб. Хэшировать. Считать это ключом новой гаммы на 10Гб.

openssl speed sha

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