Telegram: MTProto 2.0 перешел "втихую" с SHA-1 на SHA-256 и внесен еще ряд изменений - с чего вдруг?
[ Read this in English - Automatic translation to English: Google or Microsoft ]
Версия от 24 октября 2017 и ранее:
Q: How are MTProto messages authenticated?
A: All Telegram apps ensure that msg_key is equal to SHA-1 of the decrypted message. It is important that the plaintext always contains message length, server salt, session_id and other data not known to the attacker.
It is crucial that AES decryption keys depend both on msg_key, and on auth_key, known only to the parties involved in the exchange.
Q: Are you doing Encrypt-then-MAC, MAC-then-Encrypt or MAC-and-Encrypt?
A: We do none of the above, strictly speaking. For message authentication, we compute SHA-1(AES(…,encrypted_message)) upon message receipt and compare this value with the msg_key received with the encrypted message.
See also: Why not Encrypt-then-MAC? and But SHA-1 is broken!
Q: Why do you use SHA-1? SHA-1 is broken!
A: Even though it is possible for a well-funded attacker to find collisions in SHA-1, crafting a collision does not break the MTProto encryption scheme due to the way SHA-1 is used in the protocol (see here and here). We do not use SHA-1 in any areas where collisions are important, such as digital signatures or file identification.
We use SHA-1 as a component in the KDF and for a security check after transmission. Even if an attacker could create messages with a chosen SHA-1 (a far greater achievement than merely finding a collision), it would avail to nothing. This is because we use the SHA-1 of the plaintext *, while MTProto passes the ciphertext encrypted with a key unknown to the attacker. In order to threaten this setup, you need not a collision in SHA-1(ciphertext), you need a collision in SHA-1(AES_Decrypt(key_unknown_to_attacker, ciphertext)).
At the same time, SHA-1 is computed considerably faster than SHA-256 and other suitable and well-studied algorithms. This edge in speed is very important on older mobile devices, and especially so, since Telegram can send full-quality photos, as well as large videos and other files of up to 1,5 GB each. We stick with SHA-1 for the time being, reserving the option to switch to a different hash function in a future revision of the protocol, as the computational power of both potential adversaries and user devices grows over time.
Note on ‘plaintext’:
It is important that the plaintext always contains message length, server salt, session_id and other data not known to the attacker. It is crucial that AES decryption keys depend both on msg_key, and on auth_key, known only to the parties involved in the exchange.
И Николай Дуров и команда везде на форумах и обсуждениях примерно то же и вокруг того же говорили про использование SHA-1, мол, неважно, не принципиально, мы для скорости.
Вот пример поста на эту тему, там немало места уделено SHA-1, 19 декабря 2013 (4 года назад):
http://www.cryptofails.com/post/70546720222/telegrams-cryptanalysis-contest
Вот ответ команды Telegram на этот пост, 20 декабря 2013 (4 года назад):
https://telegramteam.tumblr.com/post/70588130319/telegrams-cryptanalysis-contest
Были еще подобные обсуждения.
Наступает декабрь 2017 и что мы видим?
https://core.telegram.org/api/end-to-end#a-note-on-mtproto-2-0
A note on MTProto 2.0
This article describes the end-to-end encryption layer in the MTProto protocol version 2.0.
The principal differences from version 1.0 (described here for reference) are as follows:
* SHA-256 is used instead of SHA-1;
* Padding bytes are involved in the computation of msg_key;
* msg_key depends not only on the message to be encrypted, but on a portion of the secret chat key as well;
* 12..1024 padding bytes are used instead of 0..15 padding bytes in v.1.0.
Ничего странного не замечаете? Куда же делись все аргументы Николая Дурова и ко в защиту использования SHA-1? Очень странным образом, практически абсолютно тихо, SHA-1 заменен на SHA-256. Плюс внесен еще ряд изменений в способ "подписи", а так же (что представляет немаловажный интерес) паддинга.
Теперь заглядываем в новую версию FAQ, там тоже изменения:
Q: Do you still use SHA-1?
A: The current version of the protocol is using SHA-256. MTProto 1.0 used to rely on SHA-1 (see this FAQ for details).
In MTProto 2.0, SHA-1 is used only where the choice of hash function is irrelevant for security, e.g.:
* When generating new keys
* For computing 64-bit auth_key_id from auth_key
* For computing the 64-bit key_fingerprint in secret chat used for sanity checks (these are not the key visualizations - they use a different algorithm, see Hash Collisions for Diffie-Hellman keys)
И вот теперь ключевой вопрос: с чего все это?
Откуда изменение столь жесткой и принципиальной позиции (а она очень четко была выражена не только на telegram.org, но и на различных сторонних ресурсах в обсуждениях, в 2013+ годах, когда шли споры о "новом крипто-протоколе" с людьми, интересующимися крипто)? Их, наконец-то, поимели? Кто-то смог убедить, доказать теоретически или практически? Что изменилось? Что повлияло?
Это не та история, где "ну, мы просто решили слегка изменить". Особенно при наличии жестко-категорической позиции ранее.
Меня очень настораживает, что они делают это как бы "незаметно". Т.е. псевдо-публично. Просто сделали и потерли все остальное. Это очень странно. Это очень нехорошо в области криптографии и в "открытых" проектах и протоколах. Когда отсутствует дискуссия, обоснования,
причины. Как будто что-то пытаются утаить и оставить "незамеченным".
Считаю, что подобные изменения "втихую", без объяснения причин и доводов, не должны вводиться. Иначе это может породить крипто-теории (и здесь это не в смысле криптографии). Причем, обоснованно.
Кстати, обратите внимание, что в новом FAQ явно делается отсылка к небезопасности SHA-1 в фразе: "In MTProto 2.0, SHA-1 is used only where the choice of hash function is irrelevant for security". До этого утверждалось, что во всех использованных местах MTProto 1.0 это было так.
Добавлено 11.12.2017 19:10: Для наглядности (картинки кликабельны):
Было:
Стало:
Добавлено 09.12.2017 04:30: Кажется, я нашел причину этих "случайных" и "незаметных" изменений. Вероятно, она кроется в публикации вот этого замечательного документа "Security Analysis of End-to-End Encryption in Telegram" (.pdf) с примерами возможных атак (документ 2017 года с отсылками к некоторым вещам 2015 года). Собственно, выводы все те же, что и раньше: "Although Telegram is particularly regarded as one of the most secure IM services in public, their own protocol called MTProto has not been fully reviewed by cryptanalytic experts. There are many questionable choices in the cryptographic protocol design, for example, SHA-1 whose collisions already found in 2005 [14], customised KDF, non-standard padding algorithm, and IGE mode which does not provide authenticity". Но, возможно, к этому могут иметь отношение и какие-либо иные работы по анализу MTProto, или даже иные практические события, связанные с его использованием.
Добавлено 15.12.2017 01:00: Возможно, еще эта ссылка имеет значение: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
P.S. Пользуясь случаем напомню про эту страничку сравнения (она не в ключе, что что-то хорошо или плохо, просто к месту). Поступило много предложений + я сам еще много чего хотел дописать, все записано, но пока еще не выложены изменения (их много, надо грамотно обобщить, проверить и написать).
Версия от 24 октября 2017 и ранее:
Q: How are MTProto messages authenticated?
A: All Telegram apps ensure that msg_key is equal to SHA-1 of the decrypted message. It is important that the plaintext always contains message length, server salt, session_id and other data not known to the attacker.
It is crucial that AES decryption keys depend both on msg_key, and on auth_key, known only to the parties involved in the exchange.
Q: Are you doing Encrypt-then-MAC, MAC-then-Encrypt or MAC-and-Encrypt?
A: We do none of the above, strictly speaking. For message authentication, we compute SHA-1(AES(…,encrypted_message)) upon message receipt and compare this value with the msg_key received with the encrypted message.
See also: Why not Encrypt-then-MAC? and But SHA-1 is broken!
Q: Why do you use SHA-1? SHA-1 is broken!
A: Even though it is possible for a well-funded attacker to find collisions in SHA-1, crafting a collision does not break the MTProto encryption scheme due to the way SHA-1 is used in the protocol (see here and here). We do not use SHA-1 in any areas where collisions are important, such as digital signatures or file identification.
We use SHA-1 as a component in the KDF and for a security check after transmission. Even if an attacker could create messages with a chosen SHA-1 (a far greater achievement than merely finding a collision), it would avail to nothing. This is because we use the SHA-1 of the plaintext *, while MTProto passes the ciphertext encrypted with a key unknown to the attacker. In order to threaten this setup, you need not a collision in SHA-1(ciphertext), you need a collision in SHA-1(AES_Decrypt(key_unknown_to_attacker, ciphertext)).
At the same time, SHA-1 is computed considerably faster than SHA-256 and other suitable and well-studied algorithms. This edge in speed is very important on older mobile devices, and especially so, since Telegram can send full-quality photos, as well as large videos and other files of up to 1,5 GB each. We stick with SHA-1 for the time being, reserving the option to switch to a different hash function in a future revision of the protocol, as the computational power of both potential adversaries and user devices grows over time.
Note on ‘plaintext’:
It is important that the plaintext always contains message length, server salt, session_id and other data not known to the attacker. It is crucial that AES decryption keys depend both on msg_key, and on auth_key, known only to the parties involved in the exchange.
И Николай Дуров и команда везде на форумах и обсуждениях примерно то же и вокруг того же говорили про использование SHA-1, мол, неважно, не принципиально, мы для скорости.
Вот пример поста на эту тему, там немало места уделено SHA-1, 19 декабря 2013 (4 года назад):
http://www.cryptofails.com/post/70546720222/telegrams-cryptanalysis-contest
Вот ответ команды Telegram на этот пост, 20 декабря 2013 (4 года назад):
https://telegramteam.tumblr.com/post/70588130319/telegrams-cryptanalysis-contest
Были еще подобные обсуждения.
Наступает декабрь 2017 и что мы видим?
https://core.telegram.org/api/end-to-end#a-note-on-mtproto-2-0
A note on MTProto 2.0
This article describes the end-to-end encryption layer in the MTProto protocol version 2.0.
The principal differences from version 1.0 (described here for reference) are as follows:
* SHA-256 is used instead of SHA-1;
* Padding bytes are involved in the computation of msg_key;
* msg_key depends not only on the message to be encrypted, but on a portion of the secret chat key as well;
* 12..1024 padding bytes are used instead of 0..15 padding bytes in v.1.0.
Ничего странного не замечаете? Куда же делись все аргументы Николая Дурова и ко в защиту использования SHA-1? Очень странным образом, практически абсолютно тихо, SHA-1 заменен на SHA-256. Плюс внесен еще ряд изменений в способ "подписи", а так же (что представляет немаловажный интерес) паддинга.
Теперь заглядываем в новую версию FAQ, там тоже изменения:
Q: Do you still use SHA-1?
A: The current version of the protocol is using SHA-256. MTProto 1.0 used to rely on SHA-1 (see this FAQ for details).
In MTProto 2.0, SHA-1 is used only where the choice of hash function is irrelevant for security, e.g.:
* When generating new keys
* For computing 64-bit auth_key_id from auth_key
* For computing the 64-bit key_fingerprint in secret chat used for sanity checks (these are not the key visualizations - they use a different algorithm, see Hash Collisions for Diffie-Hellman keys)
И вот теперь ключевой вопрос: с чего все это?
Откуда изменение столь жесткой и принципиальной позиции (а она очень четко была выражена не только на telegram.org, но и на различных сторонних ресурсах в обсуждениях, в 2013+ годах, когда шли споры о "новом крипто-протоколе" с людьми, интересующимися крипто)? Их, наконец-то, поимели? Кто-то смог убедить, доказать теоретически или практически? Что изменилось? Что повлияло?
Это не та история, где "ну, мы просто решили слегка изменить". Особенно при наличии жестко-категорической позиции ранее.
Меня очень настораживает, что они делают это как бы "незаметно". Т.е. псевдо-публично. Просто сделали и потерли все остальное. Это очень странно. Это очень нехорошо в области криптографии и в "открытых" проектах и протоколах. Когда отсутствует дискуссия, обоснования,
причины. Как будто что-то пытаются утаить и оставить "незамеченным".
Считаю, что подобные изменения "втихую", без объяснения причин и доводов, не должны вводиться. Иначе это может породить крипто-теории (и здесь это не в смысле криптографии). Причем, обоснованно.
Кстати, обратите внимание, что в новом FAQ явно делается отсылка к небезопасности SHA-1 в фразе: "In MTProto 2.0, SHA-1 is used only where the choice of hash function is irrelevant for security". До этого утверждалось, что во всех использованных местах MTProto 1.0 это было так.
Добавлено 11.12.2017 19:10: Для наглядности (картинки кликабельны):
Было:
Стало:
Добавлено 09.12.2017 04:30: Кажется, я нашел причину этих "случайных" и "незаметных" изменений. Вероятно, она кроется в публикации вот этого замечательного документа "Security Analysis of End-to-End Encryption in Telegram" (.pdf) с примерами возможных атак (документ 2017 года с отсылками к некоторым вещам 2015 года). Собственно, выводы все те же, что и раньше: "Although Telegram is particularly regarded as one of the most secure IM services in public, their own protocol called MTProto has not been fully reviewed by cryptanalytic experts. There are many questionable choices in the cryptographic protocol design, for example, SHA-1 whose collisions already found in 2005 [14], customised KDF, non-standard padding algorithm, and IGE mode which does not provide authenticity". Но, возможно, к этому могут иметь отношение и какие-либо иные работы по анализу MTProto, или даже иные практические события, связанные с его использованием.
Добавлено 15.12.2017 01:00: Возможно, еще эта ссылка имеет значение: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html
P.S. Пользуясь случаем напомню про эту страничку сравнения (она не в ключе, что что-то хорошо или плохо, просто к месту). Поступило много предложений + я сам еще много чего хотел дописать, все записано, но пока еще не выложены изменения (их много, надо грамотно обобщить, проверить и написать).