Blowfish на страже ivi
Между разработчиками и продуктовиками нередко возникают противоречия. Первые ближе к железу и отвечают за него, вторые — за пользовательский интерфейс. Backend-разработчикам не хочется лишний раз грузить систему, хранить заведомо ложные непроверенные данные, тратить процессорное время и дисковое пространство. В их мировоззрении априори все запросы, все пользователи это злоумышленники, которые только и хотят, что забить всю память и вывести систему из строя. Если не ради вандализма, то ради конкурентов похожих сервисов.
Например, нет никаких проблем взять и зарегистрировать пользователя в базе данных по связке «email и пароль». Если мы не отсылаем никаких рассылок, не работаем с денежными системами и идентификация пользователя по его email необходима исключительно для его же удобства, то у нас всё равно останется вопрос аппаратных ресурсов наших систем. Запустив бесконечный цикл с запросами на регистрацию, мы можем забить все диски, и система откажет. Поэтому приходится заставлять совершать пользователям столь неудобные шаги в виде подтверждения своего email. То же самое происходит и с привязкой к телефонным номерам. То же самое и с привязкой учётных записей социальных сетей, которым делегировали задачи по идентификации пользователей.
Всегда найдутся те, кто в состоянии поднять свой собственный почтовый сервер. Создание виртуальных почтовых ящиков, переходы по ссылкам подтверждения в них тривиально автоматизируются, что опять же может нанести урон ресурсам серверов. Однако на деле это происходит столь редко, что на общем статистическом фоне всех запросов будет чётко отслеживаемо и последствия предотвратимы. А редкость: из-за высокого порога входа для регистрации в системе. Именно порог входа в большинстве своём отсеивает потуги злоумышленников.
Порог входа простых смертныхИдеальный мир продуктовых менеджеров не содержит никаких сложных технических систем в виде почтовых систем, ссылок перехода и прочего. Идеальный конечный результат для них — это когда пользователь, а точнее его программный клиент (программа в браузере в том числе), сама идентифицирует и аутентифицирует себя как уникальную сущность. Пользователь подключается к сервису, и тот его сразу же узнаёт без лишних телодвижений в виде SMS-ок и ссылок. Кроме лишних действий это требует от пользователя и привязку к сторонним сервисам, на которые ему тоже придётся тратить время.Идеальное решение в лоб — это когда программа просто сгенерирует случайное большое число (достаточно случайное, чтобы оно не совпало с кем-либо ещё) и будет его использовать в качестве идентификатора. Каждый пользователь сам себе сервис и средство аутентификации. Предполагаем, что у него надёжное безопасное долговременное хранилище этого идентификатора и всё общение с нами происходит по зашифрованному доверяемому каналу (TLS).
Остаётся одно «но»: порог входа подобных программных решений почти нулевой для регистрации. Программный клиент может быть как добропорядочным человеком, так и позабывшем о законах Азимова роботом.
Как решение можно ввести нечто, что отличило бы робота от человека: CAPTCHA. Довольно просто реализуется и эффективно работает. Как минимум даёт достаточный порог входа, чтобы отсеять многих вандалов (но не конкурентов, покупающих китайские фермы распознавателей). Однако подобное решение сильно не нравится как пользователям, ломающим глаза и нервы, так и, соответственно, продуктовикам.
Докажи, что работал Одно из решений, используемых у нас, это старая добрая система proof-of-work (PoW), известная со времён возникновения email-спама, идентифицировать который (робот ли он или нет) не хватало данных. Раз в нашем контексте мы хотим обезопасить трату своих ресурсов, так как посылка данных клиентом — гораздо более дешёвая операция, то PoW — это средство восстановления справедливости за счёт того, что пользователь должен будет отработать своё право на обработку запроса.Proof-of-work это технология, при которой для совершения какого-либо действия необходимо затратить минимальную установленную работу. Работа эта ресурсоёмкая, но проверка успешности её выполнения — дешёвая. Если кто-то захочет тратить наши ресурсы, то при стократной разнице между проверкой и решением работы злоумышленнику надо будет затратить в стократ больше ресурсов, чем надо. Как правило, это будет экономически невыгодно.
Пользователю не придётся вводить какие-либо CAPTCHA или зависеть от сторонних сервисов. Ему всего-лишь придётся чуть-чуть погреть свой процессор, прозрачно для интерфейса.
Схема работы клиент-сервера проста:
┌──────┐ ┌──────┐ │Клиент│ │Сервер│ └──┬───┘ └──┬───┘ │ JSON-RPC ЗАПРОС │ │ ────────────────────────────> │ │ │ ЗАДАЧА │ │ <──────────────────────────── │ │ │────┐ │ │ │ Решить(ЗАДАЧА) │ │<───┘ │ │ │ │ ЗАПРОС, ЗАДАЧА, РЕШЕНИЕ │ │ ────────────────────────────> │ │ │ │────┐ │ │ │ Проверить (ЗАДАЧА, РЕШЕНИЕ) │ │<───┘ │ │ │ Результат выполнения ЗАПРОСа│ │ <──────────────────────────── Привязанные к условиям задачи данные не хранятся в базе данных и поэтому их необходимо аутентифицировать, например, использовав криптографические подписи. И чтобы избежать возможности повторения запроса, то хотя бы, например, привязывать ко времени и давать чёткие сроки выполнения задачи.Если запрос клиента это JSON-структура REQ, то клиент в ответе от сервера получает:
{«req»: REQ, «bestbefore»: 1234, «task»: TASK, «sign»: «SIGN»} Клиент же в ответ присылает: {«req»: REQ, «bestbefore»: 1234, «task»: TASK, «sign»: «SIGN», «answer»: RESULT} где bestbefore — это время, до которого данный запрос можно выполнить, TASK — это начальные условия задачи, а SIGN — это криптографическая подпись всего этого сериализованного словаря. RESULT — это решение задачи.Если клиент попытается изменить свой оригинальный запрос, то подпись будет невалидна. Если он это попытается сделать повторно, спустя какое-то время (например, после публикации комментария), то сервер, сверив со своими часами, инвалидирует запрос. Если клиент попробует подставить уже ранее решённую задачу, то подпись тоже будет невалидной.
Вместо привязки по времени можно выдавать одноразовые токены, генерируемые случайным образом. Для простоты с ходу можно хранить в Redis и делать ограниченное время жизни. При запросе мы читаем 16 байт (128 бит) из /dev/urandom и кладём эту строчку в Redis на десять секунд. Этот токен должен появиться в ответе клиента. Если он ещё есть в Redis, то удаляем и обрабатываем запрос. При повторном использовании сервер уже не знает такого токена. Их короткое время жизни гарантирует нам что забить и вывести из строя Redis не получится, разве что только обладая большими каналами связи и мощностями.
Ещё лучше было бы добавлять какой-то уникальный идентификатор в запрос, оставляя bestbefore. При успешной проверке задачи мы сохраним в Redis этот идентификатор с оставшимся временем жизни. Таким образом при выдаче задач мы ничего не сохраняем у себя. Пользователю придётся решить задачу, чтобы попытаться повторить действие, но только в пределах оставшегося времени у него есть возможность их совершить, пока действительно bestbefore. Для сервера это выливается в дешёвую проверку PoW и проверку существования ключа в Redis.
TASK_SIGN_KEY = «ff7555ded9526ecf03b1617a61514d30».decode («hex») TASK_LIFETIME = 60
def task_generate (req): result = { «req»: req, «bestbefore»: datetime.utcnow () + timedelta (seconds=TASK_LIFETIME), «task»: task_new (), «id»: urandom (16).encode («hex»), } result[«sign»] = sign (TASK_SIGN_KEY, serialize (result)) return result
def task_validate (req): if req[«bestbefore»] < datetime.utcnow(): return False signature = req.pop("sign") answer = req.pop("answer") if not constant_time_compare(signature, sign(TASK_SIGN_KEY, req)): return False if redis.exists(req["id"]): return False redis.setex(req["id"], TASK_LIFETIME) if not task_verify(req["task"], answer): return False return True Не стоит забывать о том, что любые строки, используемые в криптографии и требующие сравнения, не должны сравниваться просто из коробки родными средствами языка. Сравнение "==" будет оптимальным по производительности и, грубо говоря, при первом не совпавшем байте операция завершится: в итоге время проверки не константное и из-за этого можно в случае TLS совершать мощнейшие атаки, которые способны дешифровать полностью всё сообщение. Частой практикой (хоть и не оптимальной по производительности) является сравнение через HMAC-и: hmac(compare_key, string1) == hmac(compare_key, string2) При этом время сравнения не константное, но рандомизированное, что предотвратит атаки нацеленные на утечку информации о времени сравнения строк.Задачи Что из себя могут представлять эти задачи? При первом подходе к снаряду мы решили использовать часть уже с 1970-х годов известных пазлов Меркле. Официально это можно считать первой асимметричной системой обмена ключами, глядя на которую был изобретён алгоритм Диффи-Хельмана. Каждый пазл представляет собой зашифрованную строчку и часть ключа дешифрования. Если это шифрование алгоритмом DES, то полный перебор ключей займёт в среднем 2^55 операций. Мы можем дать 5 байт (40 бит) этого ключа, и тогда необходимо будет сделать 2^15 операций, то есть более 32 тысяч операций дешифрования. Результатом решения будет являться оставшаяся часть ключа: недостающие два байта. Проверка решения на сервере заключается в одной операции дешифрования. Предварительно можно условиться, что шифруется строчка «YOUBROKE».Прикинуть, какие должны быть параметры подобных задач, не очень сложно. Берём самое низкопроизводительное из поддерживаемых устройств, которое может быть найдено массово у пользователей. Предполагаем, что там старое программное обеспечение с не очень оптимальными реализациями алгоритмов (например, это JavaScript в браузере). Ставим максимальную планку времени ожидания для пользователя и смотрим, сколько итераций может быть выполнено. Понимаем, сколько бит ключа не раскрывать.
Какой алгоритм шифрования предпочесть? Выбор огромен. Хочется, чтобы юридически быть чистым при его использовании, не платить, чтобы он был и быстр и криптографически безопасен (хотя нам не секреты передавать). Наиболее важно, чтобы при этом его реализации были на всех платформах. Среди платформ, поддерживаемых ivi, это Web-браузеры, iOS, Android, SmartTV и другие. Везде свои разработчики, которым, ясное дело, не хотелось бы писать много кода. JavaScript не имеет никаких встроенных криптографических средств. Если бы везде была библиотечная реализация AES, то выбор бы был очевиден — путь наименьшего сопротивления (раз с государством не связываться, то ГОСТ не диктуется).
Выбор пал на Blowfish — известный ещё с 1993-го года блочный шифр, разработанный известнейшим криптографом Брюсом Шнайером. Он полностью удовлетворяет поставленным условиям, имеет полностью свободные и открытые реализации. Да, безусловно есть технически более совершенные алгоритмы, но их код либо сложнее, либо алгоритм не так хорошо известен, либо не так много реализаций на всевозможных языках имеется. Такие шифры как Arcfour и Salsa20 более просты, но они потоковые и это ограничивает сферу применения, о которой будет ниже. Вообще отлично подходит и шифр XTEA, но человеческая субъективность везде присутствует и вес Шнайера был решающим.
Кроме того, во всех задачах, приведённых ниже, этот шифр используется только в режиме шифрования, не требуя кода для дешифрования. Так как это сеть Фейстеля, то дешифрование это просто инвертирование хода операций, но оно тоже занимает свою долю неиспользуемого кода.
Дни рождения Задача с поиском ключа дешифрования имеет серьёзный недостаток: слишком большую разницу в производительности между пользовательскими устройствами. JavaScript-код в браузере на ARM-процессоре на несколько порядков медленнее того, что будет запущено на современном ПК с реализацией на C. Количественная разница становится качественной: либо пользователь мобильных устройств слишком долго ждёт решения PoW, либо трудоёмкость на ПК становится несущественной и посылка трафика будет куда накладнее.Доступный ресурс, имеющийся на всех платформах, кроме процессора — оперативная память. Задачи процессоров могут быть реализованы аппаратно в виде ASIC- и FPGA-решений с большей производительностью на денежную единицу. А вот разница в производительности памяти на разных доступных пользователям платформах гораздо менее существенна.
Известный алгоритм для хранения паролей scrypt использует оперативную память для ускорения вычислений. Если всё будет производится на процессоре, то вычисления пройдут очень долго. Разница так велика, что ASIC/FPGA или мощные Intel Xeon процессоры не будут играть абсолютно никакой роли, если нет памяти.
Решение, взятое на вооружение в ivi — это использование памяти как кэша в задаче поиска коллизий между результатами работы PRP-функции (pseudo random permutation — псевдослучайная перестановка).
В теории вероятностей есть парадокс дней рождения: если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50%. Если мы возьмём хэш-функцию с выходом в 128-бит, то вероятность того, что у двух разных входов совпадёт хэш-значение, будет одна на 2^64.
В качестве некого хэш-значения мы используем часть зашифрованного кусочка данных. Например, мы берём только три байта от зашифрованных данных (имеем 24-битное подобие хэш-функции). Сервер присылает ключ, который должен быть использован для шифрования. В клиент заранее зашиты правила перебора/поиска коллизий: например, это будут два пространства строчек длиной равной размеру шифроблока, используемого алгоритма. Одно пространство строк это «XXXXXXX1», «XXXXXXX2», «YYYYYYY3» и так далее. Второе это «YYYYYYY1», «YYYYYYY2», «YYYYYYY3» и так далее. Каждый элемент этого пространства шифруется и от результата берутся последние 3 байта. Всё пространство первой последовательности сохраняется в оперативной памяти. Во время расчёта второй последовательности мы ищем совпадающие элементы с первой последовательностью и запоминаем эти коллизии. Например, при каком-то заданном ключе элемент с порядковым номером 123 будет иметь совпадающее значение нашего хэша с элементом второй последовательности с порядковым номером 5678: то есть последние три байта зашифрованной строчки «XXXXX123» совпадут с последними тремя байтами зашифрованной строчки «YYYY5678». Сохранённые хэши первой последовательности это и есть наш кэш. Требуемый размер кэша (чтобы, например, как минимум, 60% коллизий попадало) зависит от размера хэш-значений.
Сама задача представляет собой:
{«key»: «KEY», «size»: 1048576, «count»: 4096} где KEY — это случайный ключ шифрования, size — это размер последовательности, которую необходимо закэшировать, а count — это минимальное количество коллизий, которые нужно найти. Решением задачи является список пар последовательных номеров последовательностей, где коллизия была найдена (в нашем случае одна из пар это 123 и 5678). def solve (key, size, count): bf = Blowfish (key) cache = {} for i in xrange (size): val = str (i) val = «X» * (8 — len (val)) val = bf.encrypt (val) cache[val[-3:]] = i collisions = [] for i in xrange (size): val = str (i) val = «Y» * (8 — len (val)) val = bf.encrypt (val) found = cache.get (val[-3:]) if found: collisions.append ((found, i)) if len (collisions) == count * 2: return collisions Для нашей задачи от сервера из примера клиенту необходимо выполнить 1048576 + 4096 операций шифрования (минимум) или 1048576 + 1048576 (максимум) и три мегабайта оперативной памяти минимум (на практике чуть больше, чтобы хранить список хэшей первой последовательности в виде дерева для быстрого поиска наличия элемента в ней). Для проверки нужно выполнить 4096 + 4096 операций шифрования и иметь чуть больше 4-х килобайт оперативной памяти (накладные расходы на работу Blowfish).Очень желательно, чтобы необходимое количество элементов было таким, чтобы в преобладающем большинстве случаев заставить клиента пройтись по всей второй последовательности (прикинуть, сколько вообще коллизий при данном размере кэша возможно и взять число около этого). А также очень важно прикидывать размеры кэша: он может быть достаточно мал, чтобы полностью уместиться в кэше процессора второго или даже первого уровней, что даст существенное ускорение вычислений.
Давье-Майер Как уже говорилось выше, платформы, где есть только JavaScript, не имеют готовых криптографических средств, таких как даже хэш-функции. Нередки ситуации, когда использование хэшей требуется постоянно из-за удобства.Известные распространённые функции типа MD5, SHA1, SHA2 для подобных платформ придётся реализовывать (или использовать чью-то реализацию) самостоятельно. Из-за политических причин выбор по лицензионным ограничениям может быть резко урезан. Больше кода — больше вероятность ошибок.
Раз мы уже имеем работающий блочный шифр, то его можно легко применить и для задач хэширования данных. Большая часть хэш-функций строится на основе односторонних функций компрессии. Функция имеет два входа и один выход, все одинакового размера. По выходу функции невозможно восстановить и предположить, что было на входах. Обычный блочный шифр почти обладает этим свойством и поэтому его можно использовать как функцию компрессии. Такая структура называется функцией Давье-Майера.
┌───────────────────┐ │ ∨ ┌───┐ ┌───┐ ┌─────┐ ──> │ H │ ──> │ E │ ──> │ XOR │──> └───┘ └───┘ └─────┘ ∧ │ │
m Сообщение разбивается на части m (длина каждой равна длине шифроблока), каждая часть шифруется. В качестве ключа шифрования используется шифротекст H предыдущего блока. На самой первой итерации используются заранее заданные константы. def hasher (data): data += »\x80» if len (data) < 8: pad_length = 8 - len(data) else: pad_length = 8 - len(data) % 8 data += "\x00" * pad_length prev = "1aec98c401022e7c".decode("hex") for i in xrange(0, len(data), 8): bf = Blowfish.new(data[i:i + 8]) prev = strxor(bf.encrypt(prev), prev) return prev Так как размер сообщения должен быть кратен размеру шифроблока, то последняя часть сообщения требует дополнения (padding). Вариантов много:если среди данных не могут попадаться нулевые байты, то добить сообщение ими во время хэширования добавить «1», а дальше нужное количество нулей (так делают в MD5 и SHA1 и в примере выше) добавить нужное количество нулей, а в самом последнем байте количество добавленных байт (ANSI X.923) добавить случайные данные, а в самом последнем байте количество этих добавленных байт (ISO 10126) добавить в конец байты, значение которых равно длине дополнения (PKCS 7) Выход подобной хэш-функции равен размеру шифроблока. Для Blowfish это не очень много: 64 бит. Можно использовать эту функцию дважды, но применяя разные начальные векторы инициализации (те самые константы), и в результате получить два 64 бит хэша (в сумме 128 бит желаемые). Комбинирование хэшей применяется на практике в TLS. Да, это будет работать в два раза дольше, но требует минимума кода.
Подобное решение удобнее вставки полноценных хэш-функций из-за простоты кода, минимума используемых абстракций и алгоритмов нижестоящих. Есть улучшенные, более сложные, реализации хэш-функций на основе блочных шифров, более стойкие к атакам, но для большинства задач достаточно и такого уровня безопасности.
Почему на практике чаще применяют какие-нибудь SHA2 вместо того, чтобы сделать нечто простое поверх распространённого AES? Из-за скорости. В этой схеме на каждой итерации меняется ключ блочного шифра. Инициализация ключа это очень дорогая операция: в Blowfish инициализация ключа более чем в тысячу раз медленнее одной операции шифрования. Медленность Blowfish в том числе из-за того, что внутренние S-блок элементы шифра не заданы заранее в стандартах, как например в DES, а зависят от ключа.
Давье-Майер и его дальнейшие производные неприменимы к поточным шифрам. Реализовать что-то похожее поверх Arcfour или Salsa20 не получится. Хотя Salsa20 и используется как база для BLAKE хэш-функции, но код не столь тривиален и в нём не будет простого банального вызова Salsa20 итерации.
Аутентификация сообщений Мы в состоянии делать честные по ресурсам запросы, в состоянии применять хэш-функции, строя на них компактные по трафику протоколы синхронизации данных на основе деревьев Меркле, или просто для генерирования коротких псевдослучайных строк идентификаторов.Для аутентификации сервера на клиентах мы используем PKI предоставляемый TLS. Для аутентификации транспортных сообщений и их шифрования используется всё тот же TLS. Но мы не можем использовать аутентификацию клиентов на сервере (чтобы убедить его, что это не curl, а официальная реализация), так как эти возможности, давно имеющиеся в TLS на некоторых платформах, технически просто недоступны.
Реализовывать полноценную асимметричную криптографию дело неблагодарное, опять же, в первую очередь из-за ограничений JavaScript, в котором, например, для быстрого простого по коду Ed25519 нужна энтропия, для padding сообщения перед подписью в RSA тоже нужна энтропия —, а взять её попросту неоткуда. Разве что использовать как источник наши серверы по аутентифицированному каналу, но это опять же выливается в сложность и размеры кода.
Можно повторять как мантру: если есть возможность не использовать асимметричную криптографию — стоит всегда идти этим путём без оглядки. Количество снова перерастает в качество: официальных клиентов в ivi немного, а значит мы можем заранее сохранить в базе данных их аутентификационные ключи. Так как каждая сессия между пользователем и сервером по природе своей не рассчитана на хранение состояний, то, вместо каждый раз интерактивной аутентификации клиентской стороны (например, по CHAP протоколу) перед запросом, выгоднее аутентифицировать каждое сообщение по отдельности.
MAC (message authentication code) уже стал синонимом для аутентификации сообщений. Самый распространённый алгоритм MAC это HMAC из используемых в Интернете (хотя сейчас набирают популярность алгоритмы на основе универсального хэширования, такие как Poly1305). Подходит для использования с хэшами использующими структуру Меркле-Дамгарда (внутри которой всё те же односторонние функции компрессии). Но это не разумно, когда на руках уже имеется блочный шифр.
Сам по себе HMAC очень похож просто на хэширование, но к которому добавили ключ. Однако к MAC предъявляют другие требования, чем к просто к хэш-функциям. Например, MD5 настолько небезопасен к использованию, что как хэш-функцию его категорически нельзя применять, тогда как HMAC-MD5 вполне себе пригоден. На основе блочного шифра можно легко сделать MAC, используя CBC-MAC алгоритм, сутью которого является просто шифрование сообщения в CBC-режиме выделенным только для аутентификации ключом и самый последний зашифрованный блок будет являться значением MAC.
Одно «но» остаётся в такой CBC-MAC реализации: он безопасен только если сообщения кратны размеру шифроблока. В противном случае, из-за природы CBC-режима, зная две пары сообщений с MAC-тэгом, мы можем сделать третье, у которого будет валидный тэг. Из вариантов решения: добавлять в самое начало длину аутентифицируемых данных или шифровать последний блок. В первом случае мы заранее должны знать эту длину. Во втором необходимо иметь дополнительный ключ и делать ещё одну операцию шифрования.
Так как все наши сообщения это JSON, то в памяти мы имеем сериализованное представление данных уже известной длины. Поэтому проще всего пойти первым вариантом. Опять же имеем простой код и полноценный довольно быстрый MAC.
def mac (k, data): data = struct.pack (»! I», len (data)) + data if len (data) < 8: pad_length = 8 - len(data) else: pad_length = 8 - len(data) % 8 data += "\x00" * pad_length k = Blowfish.new(k) prev = "\x00" * 8 for i in xrange(0, len(data), 8): prev = bf.encrypt(strxor(data[i:i + 8], prev)) return prev Этот же MAC можно использовать для подписи сервером сообщений с задачами PoW и проверки им же самим, чтобы не хранить никаких промежуточных состояний, которым надо доверять и не иметь зависимостей от библиотек, кроме Blowfish.Выводы Не усложняйте без надобности код, загромождая, замедляя, уменьшая тем самым надёжность. Оценивайте сложность реализации тех или иных алгоритмов. Приведённые в статье решения на основе Blowfish достаточно просты, чтобы их можно было надёжно реализовать без ошибок любым разработчиком. Если же речь пойдёт о реализации RSA с нуля, то не стоит это делать самостоятельно. Не изобретайте собственные алгоритмы и протоколы. Каждый способен изобрести алгоритм или протокол, который он не сможет сломать. Но другие смогут. Это также известно как закон Шнайера, хотя подобные утверждения были задолго до него. Избегайте асимметричной криптографии везде, где только можно. Это чрезвычайно сложная для реализации и правильного применения область криптографии. Попытайтесь перенести часть нагрузки на пользователей с помощью криптографии. Если вам нужен псевдослучайный сессионный временный токен пользователя для его аутентификации и получения идентификации, то просто запишите всю эту необходимую информацию в виде строчки, подпишите симметричным алгоритмом, отправьте в виде cookie. Процессоры простаивают, а могли бы выполнять десятки миллионов операций шифрования/дешифрования или хэширования на одном ядре в секунду, сокращающих расходы на оперативную и долговременную память. Всего доброго, не переключайтесь!
