Атака Telegram за 2^64 операций, и почему суперзлодею она не нужна

2015-03-12 в 14:03, admin, рубрики: sms, telegram, диффи-хеллмана, информационная безопасность, коллизии, криптография, мессенджеры, приватность, уязвимость, метки: telegram

Прошлой весной мы с Juliano Rizzo (@julianor) придумали криптографическую атаку на «секретный» чат MTProto из Telegram, которая может быть осуществлена приблизительно за 2^64 операций. Атака осуществляется с позиции человека посередине на серверах Telegram.

Сообщения, отправляемые пользователям вне секретного чата, сохраняются на серверах 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 я спрашиваю, как они организовывают аутентификацию секретного чата; и как правило ответы приносят лишь разочарование. Обычно пользователи просто посылают скриншот отпечатка прямо через секретный чат, который они и пытаются установить. Для атакующего человека посередине автоматическая подмена картинки с отпечатком — это совершенно тривиальная задача.

Атака 2⁶⁴

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

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

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

В классическом сценарии атаки на ДХ человек посередине просто выбирает отдельный общий секрет для каждого из пользователей.

В то же время, если атакующий использует социальную инженерию, чтобы второй пользователь начал секретный чат по собственной инициативе, то у него намного больше свободы действий. То есть сейчас атакующий выбирает два публичных ключа (A и B). Человек посередине может создать два общих секрета M1A и M1B с разными экспонентами m1 и m2, тогда как раньше у него была лишь свобода выбора общего секрета с первым пользователем.

Вот это и является атакой. Атакующий перебирает значения m1 и m2, которые дадут одинаковый 128-битный отпечаток для M1A и M2A. Возможность поиска значений и m1, и m2 для разных общих секретов позволяет осуществить атаку «дней рождения» для поиска коллизии. Вместо поиска в пространстве 2¹²⁸, атакующий перебирает 2⁶⁴ значения ‘m1’ и 2⁶⁴ значения ‘m2’, вероятность успеха около 50%.

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

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

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

Оценка стоимости атаки за 2⁶⁰ операций — 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 анонимно; сейчас это невозможно.

Соревнование Telegram

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

Читатели, поищите ещё баги и уязвимости в MTProto, как минимум несколько ещё должно быть.

Благодарности

Огромное спасибо @odiumeh за сотрудничество, советы и поддержку, а также другим людям, которым я прожужжал все уши об этой атаке. Отдельное спасибо Dhiru Kholia и Marsh Ray за их отзывы.

Полезные ссылки

Пример частичной коллизии

p = 0xc71caeb9c6b1c9048e6c522f70f13f73980d40238e3e21c14934d037563d930f48198a0aa7c14058229493d22530f4dbfa336f6e0ac925139543aed44cce7c3720fd51f69458705ac68cd4fe6b6b13abdc9746512969328454f18faf8c595f642477fe96bb2a941d5bcd1d4ac8cc49880708fa9b378e3c4f3a9060bee67cf9a4a4a695811051907e162753b56b0f6b410dba74d8a84b2a14b3144e0ef1284754fd17ed950d5965b4b9dd46582db1178d169c6bc465b0d6ff9ca3928fef5b9ae4e418fc15e83ebea0f87fa9ff5eed70050ded2849f47bf959d956850ce929851f0d8115f635b105ee2e4e15d04b2454bf6f4fadf034b10403119cd8e3b92fcc5b

A = 31255283409627973717223000370765106922189476428506306750544086446550550889396

B = 112771494640069988074840580093805523312740220076402790935086113796930956685865

m1 = 1524456385

m2 = 2871128407

M1A = A2 * m1 mod p

M2B = B2 * m2 mod p

M1A = 0x894c450b654f0fba7eb0baf97f08cc0aa448a17a2773d5dfcd6827d119d5d910b9f8fa75e25cc23ad30aa819cdcae8e4b4a9f3551afbe37061f3a768b62507c1eb2d017a67d3433f69acec8a5cd2a73008c2f520c71a7cea269325dc8e5bf77778d6349d8db0ac64d7b362218d04bd0a0a0d2a8f8187c4df8f8aa2b177268a505fc8892bda722449a60fff1647601a505e0480af05b14ee5a613414ad3a4ea06d37c03d856e20c5156199bd382048f45e5c150321b8c354fb541946b501aeaf6af039acda9ecb871095f726cc20a920c4b3361cb5f40142fb6319e07667a0e587e49be5f0c7f13960fbc138c9b2c81ae0fff4364d041bfbbf66842d82aca7604

M2B = 0x6722b48e670f4d3c2a24019a9d18211ebbefa407fb94fa3e91bff416cf344d1a2e3bd62c43c92bb4b633586b8e11853faa609c2f474e92033bc0fc97e047e7ed4c2af54a75f7e4bbf08cf9854a478e485b358232aa886b701c5e5dc488335b757cfaf0eda87d5299b5385ca69bdbe758a0b99aa45d371bed4a576cfff4147d384e78ca245cd778d983168a3ebc55950c0203db61c67d903fe77b4879bc35e9529ff51dcbf24add97771a0538ed45d3ee7a269674ded42dc0c85546601485388b045f5196a18355d5a8579df69a06df1519f5bada66270691574b425b22cefa0f6d522394c60f6c5c568f3a16458c64d6dde8cea917cdacbc7fdf552dd7872ef7

SHA1(M1A) = 0xe20bf6722b0a44b7e0fca07bd6c55a74b378ad74

SHA1(M2B) = 0x5813a3521aa452a4a2fffc3ed6c55a74b378ad74

64-bits in common, d6c55a74b378ad74

Update

Нотация O() беспокоила людей и была неуместна, также я добавил ссылку на ответ Telegram про стоимость атаки.

Примечание переводчика

Спасибо HoverHell за вычитку перевода.

Обо всех найденных ошибках и неточностях перевода, пожалуйста, пишите в личку.

Автор: Davidov

Источник

Информация

Обсуждаемое

Рекомендуем