Постойте. Речь не шла о length extension attack на H(key | message)
Там ведь и коллизий-то никаких не надо — растянул сообщение, обновил хэш и отправил на сервер (уже с _новой_ подписью)
А в схеме H(message | key) как раз за счёт коллизий можно подменить message, оставив подпись без изменений. О том и речь была:
Конкретно от угрозы length extension это избавит. Но у варианта H(message | key) есть свои проблемы. ...
(может быть, я некорректно назвал это «chosen prefix»-ом в предыдущем своём комментарии)
Вернёмся теперь к тому, с чего это ветка начиналась.
У вредителя есть сообщение message1 и его валидная подпись. На основании этого он генерирует новое сообщение message2, которому будет подходить та же самая подпись.
Ну оставит он неизменным тот же самый «chosen-prefix», а потом (за счёт 250) добавит к нему какой-то мусорный параметр, в который спрячет все лишние байты, а вместе с ним ещё один параметр типа «action=delete».
Вот и получается, что перехватив сообщение message1 = «action:add ...» его можно превратить в message2 = «action:add… action:delete ...», имеющее ту же самую подпись.
Что это, как не та самая проблема схемы H(message | key), о которой я писал выше?
Хорошо, с парами файлов всё понятно.
Но как по-вашему они сертификат меняли? Или вы думаете, что там они тоже сначала сгенерировали пару _случайных_ блоков?
Пишут, кстати, что для взлома использовали кластер из примерно 200 Sony PS3, который работал 3 дня. И это в 2008 году! Спустя два года после описанного в вашем посте:
в 2006 году чешский криптограф Властимил Клима предложил для поиска коллизий новый метод, позволяющий найти разную пару случайных 128 байтных блоков с одной md5 суммой на персональном компьютере меньше чем за минуту
Что-то я торможу, извините. Конечно, «брутфорс-клиент» не может обновить временную метку, потому что она подписана вместе со всем сообщением (тем самым HMAC).
Мы обычно к HMAC добавляем таймстемп. Во-первых защищает от отложенных атак (reply), во-вторых защищает от бесконечного брутфорса.
И часы синхронизируете по защищённому протоколу? Всё как положено?
Не совсем понятно, как это защищает от «бесконечного брутфорса»?
Насколько я понял, вы говорите о том, что клиент добавляет к запросу временную метку, а сервер пропускает только те запросы, у которых метка не сильно отличается от ожидаемой? (HMAC здесь тогда особо и ни при чём)
Что мешает «брутфорс-клиенту» обновлять эту метку в своих запросах с какой-то периодичностью? (лишь бы попадала в «окно сравнения»)
Навскидку:
1) если вы результат вычисления сравниваете обычным == — timing attack, получите и распишитесь
2) пример у вас в первом абзаце выглядит лучше*, чем тот вариант, что вы «используете уже 3 года»
если в вашем внутреннем вызове md5($mes. $this->o['secret_part2']. $this->id) заменить значение $mes на другое, имеющее такой же хэш, подпись по-прежнему будет валидной
* в общем-то, защищённый от extension-атак HMAC использует очень похожую схему: H(key1 | H(key2 | message))
Ограничения здесь не обязательно искусственные.
Например, в некоторых странах есть запрет на экспорт сильной криптографии. И вам могут просто не дать выпустить на международный рынок продукт, оборудованный «по последнему слову криптограферской моды».
Да и статья ведь немного не о том. В ней не говорится, что решения не существует. Основной её мотив в том, что даже в самых известных подходах и алгоритмах (как в общем-то, и в любом «паттерне», о которых вы пишете) могут быть лазейки, о которых вы не знаете.
Я уверен, что до определённого времени вариант MD5(key | message) был вполне себе «паттерном». Примеры Flickr, Vimeo и RTM нам на это как бы намекают.
Но интереснее всего, пожалуй, опубликованная в 2011 работа, в которой пишут о распознавании фраз в зашифрованном потоке.
Они использовали не следы от VAD, а информацию о фонетическом произношении слов. При этом ни образцов голоса, ни образцов произношения входящих во фразу слов алгоритму не требуется. А атака стала возможной из-за комбинации VBR сжатия и сохраняющего длину шифрования. www.cs.unc.edu/%7Efabian/papers/tissec2010.pdf
Вы по ссылке-то ходили?
В 2005 исследователи смогли создать пару PostScript документов, имеющих одинаковый MD5-хэш, а также пару X.509 сертификатов с совпадающим хэшем.
А в 2008 обычный SSL-сертификат был успешно превращён в рабочий CA-сертификат якобы от имени того же самого провайдера.
Но у варианта H(message | key) есть свои проблемы. В частности, поскольку message (а значит и его хэш) взломщику известен, он может найти такое сообщение message2, которое будет давать то же самое значение хэша: H(message) = H(message2). А значит и после приклеивания в конце ключа хэши будут совпадать. Т.е. подпись от message можно будет использовать для отправки message2.
Вариант H(key | message | key) — лучше. Но и у него были обнаружены уязвимости, даже когда ключ-префикс и ключ-суффикс различаются.
Упоминаемый в статье HMAC использует, на самом деле, схему H(key1 | H(key2 | message)), где key1 и key2 особым образом получаются из исходного ключа.
Всё, о чём вы пишете — это и есть упомянутые в статье «шумы».
С ними можно пробовать бороться. И два наиболее очевидных способа как раз указаны.
Подобраться физически как можно ближе к атакуемому серверу, запускать подбор, когда большинство пользователей спят, повторять запросы тысячи раз, чтобы отфильтровать все случайные девиации за счёт усреднения — всё это вполне может обеспечить атаке успех.
Вы, безусловно, правы. А автор (не думаю, что он об этом не знал), видимо, решил спрятать это за своим «Вкратце».
Деталь, в общем-то, существенная. И в некоторых случаях вполне может сделать атаку невозможной.
Там ведь и коллизий-то никаких не надо — растянул сообщение, обновил хэш и отправил на сервер (уже с _новой_ подписью)
А в схеме H(message | key) как раз за счёт коллизий можно подменить message, оставив подпись без изменений. О том и речь была:
(может быть, я некорректно назвал это «chosen prefix»-ом в предыдущем своём комментарии)
У вредителя есть сообщение message1 и его валидная подпись. На основании этого он генерирует новое сообщение message2, которому будет подходить та же самая подпись.
Ну оставит он неизменным тот же самый «chosen-prefix», а потом (за счёт 250) добавит к нему какой-то мусорный параметр, в который спрячет все лишние байты, а вместе с ним ещё один параметр типа «action=delete».
Вот и получается, что перехватив сообщение message1 = «action:add ...» его можно превратить в message2 = «action:add… action:delete ...», имеющее ту же самую подпись.
Что это, как не та самая проблема схемы
H(message | key), о которой я писал выше?Но как по-вашему они сертификат меняли? Или вы думаете, что там они тоже сначала сгенерировали пару _случайных_ блоков?
Пишут, кстати, что для взлома использовали кластер из примерно 200 Sony PS3, который работал 3 дня. И это в 2008 году! Спустя два года после описанного в вашем посте:
Думаете, им просто хотелось кластер погонять?
И часы синхронизируете по защищённому протоколу? Всё как положено?
Не совсем понятно, как это защищает от «бесконечного брутфорса»?
Насколько я понял, вы говорите о том, что клиент добавляет к запросу временную метку, а сервер пропускает только те запросы, у которых метка не сильно отличается от ожидаемой? (HMAC здесь тогда особо и ни при чём)
Что мешает «брутфорс-клиенту» обновлять эту метку в своих запросах с какой-то периодичностью? (лишь бы попадала в «окно сравнения»)
1) если вы результат вычисления сравниваете обычным == — timing attack, получите и распишитесь
2) пример у вас в первом абзаце выглядит лучше*, чем тот вариант, что вы «используете уже 3 года»
если в вашем внутреннем вызове
md5($mes. $this->o['secret_part2']. $this->id)заменить значение $mes на другое, имеющее такой же хэш, подпись по-прежнему будет валидной* в общем-то, защищённый от extension-атак HMAC использует очень похожую схему:
H(key1 | H(key2 | message))Например, в некоторых странах есть запрет на экспорт сильной криптографии. И вам могут просто не дать выпустить на международный рынок продукт, оборудованный «по последнему слову криптограферской моды».
Да и статья ведь немного не о том. В ней не говорится, что решения не существует. Основной её мотив в том, что даже в самых известных подходах и алгоритмах (как в общем-то, и в любом «паттерне», о которых вы пишете) могут быть лазейки, о которых вы не знаете.
Я уверен, что до определённого времени вариант
MD5(key | message)был вполне себе «паттерном». Примеры Flickr, Vimeo и RTM нам на это как бы намекают.Но там речь идёт всё же об идентификации говорящего (по характерному отпечатку пауз от VAD), а не о раскрытии текста.
Вот ещё одна аналогичная работа 2007 года с тестами на SIP и Skype — etd.ohiolink.edu/send-pdf.cgi/Lu%20Yuanchao.pdf?csu1260222271
Но интереснее всего, пожалуй, опубликованная в 2011 работа, в которой пишут о распознавании фраз в зашифрованном потоке.
Они использовали не следы от VAD, а информацию о фонетическом произношении слов. При этом ни образцов голоса, ни образцов произношения входящих во фразу слов алгоритму не требуется. А атака стала возможной из-за комбинации VBR сжатия и сохраняющего длину шифрования.
www.cs.unc.edu/%7Efabian/papers/tissec2010.pdf
Берём какой-нть Triple DES, неправильно выбираем константу режима шифрования (ECB вместо CBC) — и получаем шифровку, которую можно спокойно резать на части и собирать новое сообщение из нескольких исходных — www.codinghorror.com/blog/2009/05/why-isnt-my-encryption-encrypting.html
В 2005 исследователи смогли создать пару PostScript документов, имеющих одинаковый MD5-хэш, а также пару X.509 сертификатов с совпадающим хэшем.
А в 2008 обычный SSL-сертификат был успешно превращён в рабочий CA-сертификат якобы от имени того же самого провайдера.
Но в случае всё того же MD5 — вполне реально: en.wikipedia.org/wiki/Md5#Collision_vulnerabilities
Но у варианта
H(message | key)есть свои проблемы. В частности, поскольку message (а значит и его хэш) взломщику известен, он может найти такое сообщение message2, которое будет давать то же самое значение хэша:H(message) = H(message2). А значит и после приклеивания в конце ключа хэши будут совпадать. Т.е. подпись от message можно будет использовать для отправки message2.Вариант
H(key | message | key)— лучше. Но и у него были обнаружены уязвимости, даже когда ключ-префикс и ключ-суффикс различаются.Упоминаемый в статье HMAC использует, на самом деле, схему
H(key1 | H(key2 | message)), где key1 и key2 особым образом получаются из исходного ключа.www.youtube.com/watch?v=9i9jhPo9jTM
(вот же ж этот парсер!)
Ссылка, которую я привёл выше, к сожалению, не работает. Вот правильная — Remote timing attacks are practical
С ними можно пробовать бороться. И два наиболее очевидных способа как раз указаны.
Подобраться физически как можно ближе к атакуемому серверу, запускать подбор, когда большинство пользователей спят, повторять запросы тысячи раз, чтобы отфильтровать все случайные девиации за счёт усреднения — всё это вполне может обеспечить атаке успех.
Деталь, в общем-то, существенная. И в некоторых случаях вполне может сделать атаку невозможной.