Комментарии 49
А достаточно будет для защиты от бекдоров спецслужб шифровать текст два раза алгоритмами от противоборствующих государств, которые вряд ли договорятся? ГОСТ+AES? Или двойное шифрование не повышает криптостойкость?
На самом деле, шифрование двумя разными алгоритмами — это классная идея. Про это не так много написано, единственная зацепка — «Software Application GoldBug Messenger», защищеный почтовый клиент.
Так вот, там алгоритм шифрования состоит из трёх стадий с использованием разных методов: -Ассиметричное RSA шифрование
-Симметричное AES-256
-шифрование пакетов на уровне HTTPS (то есть SSL/TLS Tunnel).
Такой подход, вероятно, может защитить от бэкдоров.
Для двойного шифрования одним и тем же алгоритмом ситуация следующая. (Тут уже скорее про обычную криптостойкость, без использования бэкдоров, хотя, это может и усложнить процесс взлома алгоритма даже и использованием бэкдора)
Если речь идет про двойное шифрование с использованием одного и того же ключа, то для некоторых шифров это может скорее ухудшить их криптостойкость.
Если же используются два разных ключа, то это более безопасно, но не намного. Можно провести аналогию с замками из реального мира. Поставив на дверь два физических замка одного типа, вы гарантируете, что вор, который может вскрыть один замок за пять минут, теперь должен потратить десять минут. Но гораздо надёжнее купить замок, который был бы вдвое дороже, и который вор не мог бы взломать вообще.
В криптографии это работает примерно так же: в общем случае вы не можете гарантировать, что шифрование дважды делает его более чем в два раза более трудным для взлома шифрования. Так что если АНБ обычно может расшифровать ваше сообщение за N минут, с двойным шифрованием, им нужно 2 * N минут. Вероятно, вам будет гораздо лучше, если вместо этого вы удвоите длину ключа, что может привести к тому, что им потребуется 100 лет, чтобы взломать шифрование.
В некоторых случаях имеет смысл повторить шифрование, но нужно учитывать некоторые подводные камни математического характера. Например, Triple-DES в основном повторяется трижды с тремя разными ключами (за исключением того, что вы encrypt-decrypt-encrypt, а не просто шифруете три раза). Но это также показывает, насколько неинтуитивно это работает, потому что в то время как Triple-DES утрояет количество шифрований, он имеет только двойную эффективную длину ключа алгоритма DES.
Вероятно, вам будет гораздо лучше, если вместо этого вы удвоите длину ключа, что может привести к тому, что им потребуется 100 лет, чтобы взломать шифрование.
Вот про это хотелось бы поподробнее. Тот же упомянутый VC/TC генерировал из пассфразы некоторую гигантскую последовательность, которая потом употреблялась в качестве ключа.
Вопросы:
1) Интересно а как влияет увеличение размера размера разрядности S блока (а точнее подстановочной таблицы), например с 8 бит как в примере Rijndael до скажем 16 бит (или больше — пока хватит памяти). Снизится ли вероятность выпадения такого неудачного набора, который все еще подвержен дифференциальному криптоанализу?
2) Что если дополнительно к пункту 1 заполнять таблицу доказуемо случайными числами как это делается при выборе коэффициентов в хэш функции SHA256 (квадратные или кубические корни из подряд идущих простых чисел).
Да, абсолютно верно, сами по себе SP-сети уязвимостей не имеют, это просто математическая модель, описывающая алгоритм. Бэкдор может скрываться в конкретной реализации S-блоков.
По поводу вопросов:
1) Сложно сказать, как повлияет увеличение размера S-блоков на изменении вероятности именно НАХОЖДЕНИЯ секретных S-блоков. Это очень запутанная математика конечных полей, в которой чёрт ногу сломит. Вероятнее всего, бэкдор будет найти сложнее, но насколько сложнее, линейно, квадратично, итд — лично мне пока что непонятно.
Вообще, на эту тему не так много работ, всё еще ведутся различные исследования. Алгоритм BEA-1, по заявлению авторов — один из первых в своем роде, планируется дальнейшая работа по созданию более совершенных бэкдоров. Поэтому, опять же сложно оценить, как повлияет увеличение размера S-блоков на сложность разработки уязвимости. Возможно, для S-блоков большего размера уязвимости будет создавать проще, так как больше «пространства для манёвра»
2) Про доказуемо случайные числа. Честно говоря, сходу ответить не могу. Ведь в данном случае требуется математически доказать невозможность существования бэкдора при заполнении таблицы таким образом. Скорее всего, возможность создания уязвимости при таком подходе к создании таблицы значительно уменьшится. Однако, опять же, не факт, что такая возможность исчезнет совсем.
Это означает, что такая техника анализа была известна АНБ ещё в 1970-х годах.
Почему не допускается, что блоки могли выбираться неслучайно, но из каких-то других соображений, не связанных с этой техникой? И как вообще поняли, что их выбирали неслучайно?
Также вы так и не раскрыли тему, как именно специальные S-блоки помогают в расшифровке. А также что значит
Но нельзя исключать возможность, что кому-то может повезти и он по счастливой случайности сможет вычислить идеальные секретные S-блоки для того же AES. Хочется добавить, что такое открытие может принести очень много денег
Что значит вычислить секретные S-блоки? Как я понял, S-блок является неизменной частью алгоритма AES, поменяете его — получите другой алгоритм. Как в этих условиях можно что-то "вычислить"? И главное, как на этом заработать, если остальные тоже могут это самое вычислить?
сложно повторить — даже если бэкдор был кем-то найден, то его невозможно будет использовать в другом коде или в другом устройстве.
Если в остальных свойствах еще более-менее очевидно, чем они хороши для бекдора, то вот это мне непонятно. Почему это хорошо для бекдора?
Отвечу поэтапно:
1) АНБ в 1970 косвенно приняло участие в разработке S-блоков для алгоритма шифрования DES. На тот момент, методика дифференциального криптоанализа не была известна в широких научных кругах.
В 1990 году независимые исследователи обнаружили, что S-блоки, разработанные в 1970 оказались на удивление устойчивыми к дифференциальному криптоанализу. Вероятность того, что такая устойчивость обоснована какой-либо случайностью — мала. Наиболее закономерный вариант, что S-блоки были каким-либо образом усовершенствованы.
2) Еще раз повторю про секретные S-блоки.
Во время честного шифрования и дешифрования в алгоритме используются самые обычные публичные S-блоки. Секретные же S-блоки есть только у того, что обладает уязвимостью, они позволяют расшифровать данные, не обладая ключом
Говоря о реализации, секретные S-блоки незначительно отличаются от обычных S-блоков, в небольшом количестве параметров. Однако такое незначительное отличие параметров подобрано специальным образом. Если кратко, то почти для всех входных данных выходные данные секретного S-блока и обычного одинаковы, однако для некоторого заранее известного набора входных данных выходные данные секретного S-блока и обычного отличаются. Именно это знание позволяет значительно упростить процесс перебора, необходимого для взлома алгоритма.
Чтобы не быть голословным, для алгоритма BEA-1 для S0, S1, S2 количество входных данных для которых выходные данные секретного S-блока и обычного одинаковы есть 944 (из 1024, так как блоки работают с сегментами данных по 10 бит) для S3 это число 925 (также из 1024)
Сам процесс взлома заключается в том, что при расшифровке зашифрованного сообщения вместо блоков обратных публичным S-блокам используются блоки обратные секретным S-блокам, и параллельно с этим происходит подбор раундовых ключей.
Если кратко, секретные S-блоки используются вместо публичных при расшифровке, и это ускоряет процесс перебора ключей. Ускоряет = уменьшает размер множества, по которому ведется перебор
3) Про «вычислить». Имелось ввиду, найти как раз таки те самые секретные S-блоки, которые и представляют из себя уязвимость, что может быть невероятно сложно и для чего определенно необходимо везение. По поводу заработать, уязвимость можно продать за очень большие деньги, тем же хакерам или спецслужбам, вопрос в том, насколько жато морально.
4) Для бэкдора это хорошо, потому что при обладании такими свойствами доказать его наличие в алгоритме шифрования невозможно
1) Но это все же не значит, что именно обладали этой техникой. Пример: вы, ничего не зная о простых числах, взяли первые 3-4 нечетных числа. Через некоторое время открывают простые числа и оказывается, что числа (1), 3, 5 и 7 — простые. Можно ли на основе этого утверждать, что вы сознательно выбирали простые числа, когда о них еще никто не знал?
2) Т.е., если я правильно понял, в процессе подбора ключей мы пропускаем шифротекст через S-блок, варьируя ключ, и ищем что-то знакомое на выходе. А секретный S-блок устроен так, что, грубо говоря, любое четное число на входе превращается в 3x+1 на выходе и зная это и все четные числа на входе, мы, видя на выходе 3x+1, можем понять, что подобрали кусочек ключа, так?
3) Ну вот. Т.е. все-таки найти, а то вы написали так, словно бери любые числа, что-там считай и вот тебе секретный S-блок, а процедура подобна генеративно-состязательной нейросети, которая генерирует лицо — должно быть два глаза, два уха и по одному рту и носу и дальше только улучшай, чтобы больше на лицо было похоже, а чье — неважно. А на самом деле нужно найти зеркальный портрет.
4) Если его уже нашли, то что тут еще доказывать? Нашли==доказали, а как иначе еще понимать слово "нашли"? Честное слово Васи, что у Коли тут бэкдор?
Прошу прощения, перепутал один момент связанный с ассиметричным шифрованием
"Их используют, например, для создания электронной подписи, где пользователь обладающий приватным ключом может зашифровать сообщение, и любой другой пользователь, обладающий открытым (публичным) ключом может это сообщения......"
Наоборот, публичным ключом сообщение шифруют, а приватным расшифровывают
Однако, стоит заметить, что для генерации электронной подписи необходим приватный ключ
за ремарку спасибо polearnik
Сам процесс взлома заключается в том, что при расшифровке зашифрованного сообщения...
Не понятно, как это работает. Ведь, при расшифровке нужен ключ. Или берётся какой-то пустой ключ?
А можно подробнее, какой принцип построения секретных S-блоков?
Во время взлома происходит поэтапный процесс перебора раундовых ключей, раунд за раундом. Использование секретных S-блоков в процессе дешифровки позволяет многократно уменьшить то множество ключей, среди которых производится перебор
А ведь это должно быть очень интересно.
Согласен, я старался придерживаться концепции "просто о сложном". Потому что дальнейшие погружение в устройство секретных и публичных S-блоков требует очень много математики. Этому посвящен весь раздел в книге французских исследователей.
С другой стороны, в новостях периодически всплывают новости о том, что то или иное агенство безопасности требует ту или иную компанию, разрабатывающую продукты для нас, предоставить им бэкдор к алгоритмам шифрования, которые защищают наши данные.
Эмм… вообще-то не бэкдор, а доступ — это совершенно разные вещи. У вас тут смешано все (и синее, и круглое, и соленое) в одну кучу.
Ну а вообще, в мире очень серьезно взялись за шифрование и, думаю, в ближайшие годы додавят. В Австралии уже два года действует закон о доступе к шифрованной переписке. В Америке в июле внесли в Сенат. В Англии с уже 4 года действует.
Согласен, доступ к алгоритму шифрования может быть разным: это может быть как просьба предоставить ключи шифрования, используемые пользователями, так и предоставление информации об уязвимости, которая позволяет расшифровывать данные без знания ключей шифрования (такое требование может быть необходимо, например, для систем типа point-to-point)
Как можно видеть, после первого оператора if стоят две строчки goto fail, и вторая строчка выполняется всегда, независимо от результата if. Таким образом процедура проверки сертификата проходит не полностью. Злоумышленник, знающий об этой уязвимости, может подделать сертификат и пройти проверку подлинности.
И каким образом проверка выдающая фэйл поможет злоумышленнику в этом?
Поясните, как это возможно математически? Ведь мы просто еще раз перемешали биты. Если бы такое ослабление было, что мешает искусственно ослаблять зашифрованное дополнительным шифрованием в целях взлома?
На мой взгляд доп.шифрование может улучшить защщенность, в крайнем случае ее не изменить. Но ухудшить не может. Ведь это не случай A xor X xor X
Как раз примерно такой случай. Я встречал в одной игре что-то похожее. Ключ активации преобразуется в 8 байт, потом сначала ксорится побайтово с секретным значением, потом преобразуется — первые биты образуют первый байт, вторые второй и т.д, потом ксорится еще раз. Вроде выглядит запутанно, но получается, что матрица битов переворачивается относительно диагонали, и биты на главной диагонали не шифируются вообще. Это уменьшило количество возможных вариантов в 256 раз, и это помогло мне среди возможных вариантов расшифровки проверочного файла найти осмысленный текст.
Насчет шифрования не уверен но для вычисления хешей это точно так. При вычислении хеша есть шанс коллизии, и при вычислении хешей несколько раз шанс коллизии растет.
т.е. условно md5(md5(plaintext)) может быть менее секьюрно чем md5(plaintext)
А так многочисленные хэширования используются, чтобы замедлить брутфорс украденных хэшей. Скажем, если у нас в базе лежит не пароль, а md5(пароль) — это одно. А вот если у нас в базе лежит результат md5(md5(md5(… и так 2000 раз… md5(пароль)...))) -это уже в 2000 раз замедлит перебор паролей, если базу украдут.
Их не будет исчезающе мало. Хеш функции специально не проектируются для такой цели
Может быть некоторые хеш-функции обладают таким свойством, также можно специально создать подобную хеш функцию, но вообще это не является требованием.
Их, конечно, будет не много. Но не исчезающе мало.
Возьмем с потолка 5%. То есть при хешировании всех 2^128 хешей, 5% из них совпадут.
Тогда при хешировании 2000 раз останется лишь (опять же с потолка) 2^128 * (0.95)^2000 и результат будет <1. То есть вообще возможна ситуация что при применении хеша 2000 раз результат будет всегда одинаковый.
Это, конечное же, в реальности не произойдет. Потому что на самом деле на каждой итерации совпадать будут все меньше и меньше хешей. Но ослабить таким образом используемую хеш функцию до уровня "слабее чем 1 хеширование" можно запросто, даже с учетом х2000 времени вычисления каждого хеша.
Возьмем с потолка 5%. То есть при хешировании всех 2^128 хешей, 5% из них совпадут.
Если 5% хэшей совпадают, то это очень некачественная функция. Даже в MD5 такого количества коллизий нет.
Это, конечное же, в реальности не произойдет. Потому что на самом деле на каждой итерации совпадать будут все меньше и меньше хешей. Но ослабить таким образом используемую хеш функцию до уровня «слабее чем 1 хеширование» можно запросто, даже с учетом х2000 времени вычисления каждого хеша.
Вы только что обозвали дураками разработчиков PBKDF2 — они там как раз тем и занимаются, что используют много раундов хэширования для генерации ключей шифрования.
Если 5% хэшей совпадают, то это очень некачественная функция. Даже в MD5 такого количества коллизий нет.
Есть ссылки на какие-то исследования по этому? Мне кажется там даже больше.
На минуточку, мое утверждение значит что "для любого хеша есть 5% шанс что один из оставшихся 340282366920938463463374607431768211455 хешей совпадет". Кажется что там даже больше из-за парадокса дней рождения.
Вы только что обозвали дураками разработчиков PBKDF2 — они там как раз тем и занимаются, что используют много раундов хэширования для генерации ключей шифрования.
Если прочитать внимательнее мое сообщение то можно оттуда увидеть причину проблемы многоразового хеширования. Причина в том что если на каком-то этапе будет коллизия, то эта коллизия сохранится до конца хеширования. И чем больше раундов, тем больше шансов что она произойдет, ослабляя итоговую функцию.
Это НЕ так для PBKDF2. Потому что они на каждом раунде примешивают пароль. То есть даже если на каком-то раунде будет коллизия, она перестанет быть коллизией на следующем.
Именно из-за таких нюансов и существует совет "не изобретать самому ничего в криптографии" (вроде md5(md5(md5(...))) а пользоваться проверенными решениями (вроде PBKDF2)
Есть ссылки на какие-то исследования по этому? Мне кажется там даже больше.
Исследования есть на поиск коллизий — но ЕМНИП, там размер хэшируемого сообщения как минимум в 2 раза больше размера хэша MD5.
Мой скептицизм строится на знании устройства MD5: там по факту перемешивание бит исходного сообщения, т.е. для сообщений размером, равным размеру хэша, коллизий вообще не должно быть. Но я вполне допускаю, что чего-то не учитываю и они таки есть — в любом случае, их количество далеко от 5%.
Если бы 5% хэшей совпадали, достаточно было бы высчитать пару миллионов хэшей и сравнить их между собой. В среднем процент совпадений был бы все тем же — 5%, верно? И чем больше выборка, тем точнее будет процент. Так вот, я пробовал гонять такой тест (и на бОльших выборках) — ни единой коллизии не обнаружено.
Это НЕ так для PBKDF2. Потому что они на каждом раунде примешивают пароль. То есть даже если на каком-то раунде будет коллизия, она перестанет быть коллизией на следующем.
Здрасьте. А куда она денется?
Если бы 5% хэшей совпадали, достаточно было бы высчитать пару миллионов хэшей и сравнить их между собой
Разумеется нет. Если есть 5% шанс найти коллизию из 340282366920938463463374607431768211455 то это не значит что есть 5% шанс найти коллизию из миллиона.
Однако, из-за парадокса дней рождений, если высчитать 2^(128/2) хешей то вероятность найти одну коллизию уже заметно отлична от 0.
2^64 это, впрочем, пока еще дофига, и это мало что даст.
Здрасьте. А куда она денется?
Что такое коллизия?
Это когда два разных пароля дают одинаковый хеш.
Если на этапе N получлась коллизия, то на этапе N+1 она пропадет, потому что пароли-то разные, а они примешиваются на каждом этапе. В отличии от md5(md5(...))
Однако, из-за парадокса дней рождений, если высчитать 2^(128/2) хешей то вероятность найти одну коллизию уже заметно отлична от 0.
2^64 это, впрочем, пока еще дофига.
Так 2^64 или 2000 итераций нужно, чтобы наткнуться на коллизию? Вы уж определитесь. :)
Что такое коллизия?
Это когда два разных пароля дают одинаковый хеш.
Один пароль у нас «хэш1+хвост», второй — «хэш2+хвост». В результате получаются одинаковые хэши3 — т.е. коллизия.
Почему вы думаете, что «хэш3+хвост» аннулирует предыдущую коллизию? Хвост-то у нас константный.
Так 2^64 или 2000 итераций нужно, чтобы наткнуться на коллизию? Вы уж определитесь. :)
Это совсем разные итерации. Прочитайте переписку еще раз.
- при вычислении 2^64 отдельных md5 есть заметный шанс наткнуться на одну коллизию
- Самодельная функции md5^2000 скорее всего более слабая чем прсто md5 даже учитывая в 2000 раз большее время вычисления. Все предпосылки для этого есть. Это не доказано, но в криптографии нужно доказывать то что что-то работает, а не то что не работает.
Почему вы думаете, что «хэш3+хвост» аннулирует предыдущую коллизию? Хвост-то у нас константный.
потому что hash(collision+pass1) != hash(collision+pass2) потому что pass1 != pass2
"хвост" это пароль. Пароли разные. Нет "хвоста", есть хвост1 и хвост2.
Её доказательство и выводы можно найти в статье
Security Amplification for the Composition of Block Ciphers:
Simpler Proofs and New Results
Интересно рассмотреть гипотетические примеры бэкдоров в современных алгоритмах:
DUAL_EC_DRBG
gotofail в TLS от Apple
Мне кажется у вас намешано из разных областей.
Математические бэкдоры должны быть полностью независимы от реализации.
А в примере есть и то и другое.
В TLS от Apple как раз ошибка / бэкдор в реализации.
А вот в DUAL_EC_DRBG бэкдор в самом алгоритме и как его не реализуй следуя стандарту всё равно получится генератор случайных чисел с бэкдором.
К сожалению, в реальном мире невозможно пользоваться (удобно пользоваться) длиной ключа=длине сообщения.
А алгоритм шифрования взять XOR, самый надежный метод, теоретически невзламываемый(если у вас ключ длиннее данных и не переиспользован).
Или, например, известна история когда во время Второй мировой войны морские пехотинцы США завербовали и обучили людей из племени индейцев навахо, свободно владеющих языком навахо. Это был привлекательный способ использования кодирования, мало людей не из племени знали этот язык, а также не было никаких опубликованных книг на языке навахо. В данном случае общей информацией было знание языка навахо.
Не совсем так. Японцы нашли носителей языка навахо и даже уговорили их сотрудничать. Вот только в расшифровке это им не очень помогло: на выходе получался бессвязный набор слов.
Кроме языка навахо «общей информацией» еще был способ кодирования информации: текст шифрограммы составлялся на английском, далее каждая буква шифрограммы кодировалась словом на навахо. Принцип был простой: слово в переводе на английский должно было начинаться на нужную букву (слова «би-ла-сана» (apple, «яблоко»), «уол-ла-чи» (ant, «муравей») и «це-нилл» (axe, «топор») обозначали букву «а» — из википедии).
Ну и чтобы шифрограммы не разрастались, некоторые часто употребимые слова шифровались отдельно, описательными конструкциями.
Японцы этого не знали и переводили с навахо сразу на японский — получая бессмысленное бесполезное сообщение.
они хотели чтобы на этой основе все прешли на блок чеин. но он непошёл в массы, как ему пророчили. если-бы пошёл, они бы имели доступ не только к новому печатному станку но и инвормации которая хранится с помощью технологиии блокченина.
таже история только в российской миниатюре была разыгранна и якобы мятежным телеграммом, теперь на него все подсели и даже на западе он становится популярным. А слушать их легко и приятно на лубянке. Лица уровня Паши ещё задолго до подхода к популярным проектам (по количеству денег или популярности политической или социальной значимости) находятся на коротком поводке. Наивно полагать что просто так бежать на туманные альбионы комуто дадут…
Математические бэкдоры в алгоритмах шифрования