Атака Telegram за 2^64 операций

Прошлой весной мы с Juliano Rizzo придумали криптографическую атаку на «секретный» чат MTProto из Telegram, которая может быть осуществлена приблизительно за 2^64 операций. Атака осуществляется с позиции человека посередине на серверах Telegram. 20 Март 2015, 00:39
Сообщения, отправляемые пользователям вне секретного чата, сохраняются на серверах Telegram таким образом, что позволяют компании просматривать содержимое сообщений и передавать их третьим лицам. Так происходит всегда, если беседы могут перемещаться между устройствами (например между телефоном и компьютером). Эти чаты не являются приватными, то есть пользователи должны быть очень внимательны, чтобы случайно не отправить инкриминирующую информацию или картинки без включения секретного чата. Групповые чаты к тому же вообще не используют ent-to-end шифрование. Более того, когда кто-нибудь входит в такой чат, он сразу получает доступ к ранее отправленным несекретным сообщениям. Мы к этому вернемся чуть позже.
Секретный чат
Слоган Telegram гласит: «taking back our right to privacy», и имеется в виду секретный чат с end-to-end шифрованием. Эта часть была легко взломана во время первого соревнования по компрометации Telegram с XOR-ключами выдаваемыми сервером.
Фотография с сайта
По сути, end-to-end шифрование «Телеграмма» — это протокол Диффи-Хеллмана для выбора ключа, а затем шифрование по видоизмененной схеме AES. Аутентичность end-to-end шифрования основывается на усеченном SHA-1 хэше общего секретного ключа, который отображается графически в качестве отпечатка. Этот отпечаток каким-то образом нужно передать и сравнить визуально. Если вы криптограф, то мне очень жаль, что вам пришлось это прочитать; я понимаю, как это мучает и противоречит многочисленным наработкам и канонам. По крайней мере инженеры из Telegram хотя бы используют неплохие рекомендации и требования к значениям параметров Диффи-Хеллмана.
Отпечаток, который два пользователя должны сравнить, получается из хэша ключа Диффи-Хэллмана. То есть общий ключ имеет пространство значений 2^2048, хэш-функция SHA-1 производит 160-битный хэш. 160-битных хэш обрезается до 128 бит, которые и используются, чтобы получить отпечаток (см. рисунок).

Важно понимать, что это кошмар крипто-юзабилити. Когда я встречаю кого-нибудь из пользователей Telegram я спрашиваю, как они организовывают аутентификацию секретного чата; и как правило ответы приносят лишь разочарование. Обычно пользователи просто посылают скриншот отпечатка прямо через секретный чат, который они и пытаются установить. Для атакующего человека посередине автоматическая подмена картинки с отпечатком — это совершенно тривиальная задача.

Атака 264

Хорошо, допустим теперь вы все делаете правильно, и производите сравнение отпечатков при личной встрече. А также не допускаете ошибок при сравнении, потому что вы чрезвычайно внимательны.

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

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

В классическом сценарии атаки на ДХ человек посередине просто выбирает отдельный общий секрет для каждого из пользователей.
В то же время, если атакующий использует социальную инженерию, чтобы второй пользователь начал секретный чат по собственной инициативе, то у него намного больше свободы действий. То есть сейчас атакующий выбирает два публичных ключа (A и B). Человек посередине может создать два общих секрета M1A и M1B с разными экспонентами m1 и m2, тогда как раньше у него была лишь свобода выбора общего секрета с первым пользователем.
Вот это и является атакой. Атакующий перебирает значения m1 и m2, которые дадут одинаковый 128-битный отпечаток для M1A и M2A. Возможность поиска значений и m1, и m2 для разных общих секретов позволяет осуществить атаку «дней рождения» для поиска коллизии. Вместо поиска в пространстве 2128, атакующий перебирает 264 значения ‘m1’ и 264 значения ‘m2’, вероятность успеха около 50%.

С точки зрения сложности атака требует порядка 265 операций. В 2015 году такая сложность является неприемлемо низкой. Для справки, NIST объявил SHA-1 устаревшим ещё в конце 2012 и рекомендовал использовать SHA-256 в качестве замены. Атака «дней рождения» на SHA-256 потребует около 2128 операций. Так что несмотря на высокую стоимость, описанная выше атака вполне осуществима хорошо финансируемым злоумышленником.

С точки зрения реализации, на первый взгляд кажется, что атака все ещё требует чрезмерно высоких ресурсов.
Одним из заблуждений является то, что экспоненцирование такой большой величины в поисках коллизии является слишком тяжелым с вычислительной точки зрения, поскольку приходится экспоненцировать 2048-битные простые числа. На самом деле атакующему нужно выполнять только возведения в квадрат и деление по модулю на каждом шаге.
Другим заблуждением является сложность по памяти в 264. Это тоже неверно, поскольку существуют параллельные и не требующие большого количество памяти атаки «дней рождения», и существуют различные стратегии компромисса между используемой памятью и затраченным временем. Мы написали код, использующий ρ-aлгоритм Полларда для поиска коллизий, не требующий много памяти.
В целом, я бы оценил полную атаку в диапазоне десятков миллионов долларов с точки зрения инфраструктуры и электричества для получения полной коллизии за разумное время. Атакующий также может украсть или арендовать существующую инфраструктуру, например ботнет или суперкомпьютер. Другими словами все вписывается в бюджет суперзлодея.

Оценка стоимости атаки за 260 операций — www.schneier.com/blog/archives/2012/10/when_will_we_se.html
Производительность вычисления SHA при помощи GPU — gist.github.com/epixoip/c0b92196a33b902ec5f3 www.geforce.com/hardware/desktop-gpus/geforce-gtx-980/buy-online

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

Теперь, если суперзлодей действительно хочет перехватить секретные чаты, он может рассчитывать, что жертва просто отправит отпечаток через новое секретное соединение. К сожалению, многие пользователи так и поступают. И поскольку мы говорим о суперзлодее, то он может перехватить другие каналы коммуникации, которые пользователь попытается использовать для аутентификации, например SMS; дело ещё и в том, что визуальный отпечаток не может быть передан вербально, поскольку большинство клиентов не показывают отпечаток в читаемой форме. Два отпечатка просто-напросто подменяются суперзлодеем, и до следующей личной встречи пользователи так и не узнают, что их общение было перехвачено.
И ещё кое-что. Допустим, люди используют приватные мессенждеры на телефоне, чтобы избежать уязвимых средств коммуникации, предоставляемых операторами связи. Тем не менее, единственной системой аутентификации в Telegram является SMS-код.
Мы знаем что SMS слабо защищены, и мы знаем, что злоумышленники очень часто это используют. SMS могут быть подслушаны и взломаны, пользователи могут быть подключены к поддельным базовым станциям, а ещё операторы могут быть взломаны (вспомните belgacom) или принуждены к сотрудничеству. То есть если SMS является методом аутентификации, то очевидно, что аккаунт Telegram может быть похищен.

Атака SMS также не требует высоких технологий. Если суперзлодей атакует вруга (frenimy — враг, притворяющийся другом; примечание переводчика), он может просто одолжить телефон (или SIM-карту, если телефон запаролен) на несколько минут и украсть аккаунт. Более того, Telegram сохраняет и показывает старые сообщения. С украденного аккаунта суперзлодей может с помощью социальной инженерии вынудить контакта начать новый секретный чат, чтобы тот сообщил какой-нибудь секрет.

Как починить Telegram

Первого декабря Telegram анонсировал forward secrecy, эта фича добавляет ротацию ключей внутри установленного канала. Но это никак не помешает описанной атаке человека посередине.

Есть несколько вещей, которые надо починить в Telegram, и вот список наиболее критичных.

Во-первых, чаты (включая групповые) должны иметь end-to-end шифрование по умолчанию. Это избавит от человеческих ошибок и утечки информации. Кстати, в Threema и TextSecure end-to-end шифрование уже включено по умолчанию.

Во-вторых, end-to-end шифрование должно перейти от аутентификации при каждом чате к криптографии с публичными ключами для идентификации пользователей. Нет никакого смысла аутентифицировать секретные чаты сессионным ключом. Вместо этого у каждого пользователя должен быть один или несколько публичных ключей, с помощью которых происходит выбор ключа сессии. Пользователи подтверждают друг друга единожды, и все. И, кстати, в Threema и TextSecure все это было сделано несколько лет назад.
В-третьих, аутентификация пользователя — это очень, очень слабая защита для приватного мессенджера, и злоумышленник, который может позволить себе перехват SMS, может легко украсть аккаунт и использовать социальную инженерию или просматривать обычные чаты. Необходима другая схема аутентификации аккаунта, и как можно скорее, пусть даже пароли с двух-факторной аутентификацией. Кстати, этот вектор является наиболее вероятным для реальных атак без взлома серверов Telegram, и это может сделать даже обычный злодей, не обязательно быть суперзлодеем.

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

HoverHell отмечает, что в конце 2014 года в Telegram появились никнеймы. Это избавляет от необходимости знать номер телефона собеседника, но в то же время аутентификация по-прежнему осуществляется по номеру телефона, и на серверах эта информация хранится. Примечание переводчика.
Соревнование Telegram
На данный момент идет соревнование с призом в 300 тысяч долларов за взлом end-to-end шифрования. Можно ли использовать описанную атаку? Дело в том, что само соревнование организовано так, что не позволяет устроить атаку типа «человек посередине». Если бы условия конкурса это позволяли, то у атаки был бы шанс. Ну, правда, скорее всего, вычисления будут стоить больше, чем приз; можно, конечно, использовать крауд-сорсинг.

Читатели, поищите ещё баги и уязвимости в MTProto, как минимум несколько ещё должно быть.
Рекомендации для пользователей, которым нужна приватность
Как мессенджер общего назначения Telegram выглядит нормально. Но если вам нужна секретность и приватность, то я рекомендовал бы что-нибудь другое. Например, Threema или TextSecure.
Материал с сайта http://habrahabr.ru/post/252911/