Всё правильно. Главная проблема большинства алгоритмов шифрования в том, что их придумали мужчины.
Соответственно мужики сами их взломать не могут, а тётки, используя альтернативную логику, щёлкают их как орешки.
Вот пусть попробуют свой алгоритм придумать — мы их ух как!
Здравствуйте, Блудов Павел, Вы писали:
БП>Вот пусть попробуют свой алгоритм придумать — мы их ух как!
Да легко! Они же заразы логикой вообще не пользуются. Их алгоритмы будут невозможно взломать! Правда будет один побочный эффект. С их помощью можно будет легко зашифровать информацию, но при попытке расшифровать ее будут получаться совершенно разные результаты.
А что вы хотите? Вы пробовали женщине задвать один и тот же вопрос несколько раз в разное время?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Кратко говоря — утка, прошлогодняя Пока не найдут хоть одну коллизию, считать взломанным алгоритм даже как-то странно.
Суть простая, вместо 2^80 операций по перебору для нахождения коллизии хэша достаточно и 2^63. Статья об этом была опубликована на Crypto 2006, а заявлено о факте вообще было чуть ли не в феврале того года.
.>Т.е. если ты украл табличку хэшей sha1 паролей для входа в какую-нибудь систему, то сможешь "быстро" подобрать пароль, с .>которым тебя система авторизует.
А вот это не так.
"Взломали" в данном случае означает то, что научились находить 2 сообщения, которые имеют один и тот же хэш. Найти сообщение, соответствующее какому-то *конкретному* хэшу по-прежнему очень трудно.
Так что "взлом" не имеет фатальных последствий прямо сейчас, а скорее указывает на потенциальную слабость хэш-функции.
L>Насколько я понимаю, найти сообщение, соответствующее какому-то *конкретному* хэшу просто невозможно — хотя бы потому, что любому конкретному хешу соответствует бесконечное множество сообщений.
Я имел в виду, что найти хотя бы одно сообщение, соответствующее конкретному хэшу очень трудно как в случае SHA-1, так и в случае MD-5 (на счет MD-4 не уверен).
L>Влом хеш-алгоритмов состоит именно в подборе коллизий — когда появляется возможность модифицировать сообщение, оставив хеш неизменным.
Вообще существует несколько свойств, которыми должны обладать хэш-функции:
Preimage resistant (See one way function for a related but slightly different property): given h it should be hard to find any m such that h = hash(m).
Second preimage resistant: given an input m1, it should be hard to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2).
Collision-resistant: it should be hard to find two different messages m1 and m2 such that hash(m1) = hash(m2). Due to a possible birthday attack, this means the hash function output must be at least twice as large as what is required for preimage-resistance.
То, о чем написал ты — атака на второе свойство. Таких атак по-прежнему нет, т.е. SHA-1 остается second preimage resistant и preimage resistant. Китаянка доказала, что SHA-1 НЕ является collision-resistant, но для большинства приложений это и не важно. Правда говорят, что в Микрософте есть специальный человек, который сейчас "на всякий случай" во всех продуктах заменяет SHA-1 на SHA-256. А раньше, судя по слухам, этот человек заменял MD-5 на SHA-1 Есть подозрение, что и в будущем без работы он не останется
Здравствуйте, eao197, Вы писали:
.>>ту же подпись. И никакой софт не обнаружит подлог.
E>Сначала хорошо было бы иметь софт, который создаст этот второй документ с осмысленным содержимым и точно таким же хэшем. Если это вообще возможно.
Это очень даже возможно. Смотреть например практически-осуществимую атаку на X.509 сертификаты ([1], [2]). Есть варианты атак на изменение архивов (zip/gzip), которые снабжаются подписью с md5 (это самые первые варианты практических атак, использовали вообще 1 опубликованную коллизию MD5).
P.S. В первой ссылке кстати аннонсирована атака и на SHA-1.
Блудов Павел wrote:
> А>http://safe.cnews.ru/news/line/index.shtml?2007/01/23/232525 > > Всё правильно. Главная проблема большинства алгоритмов шифрования в том, > что их придумали мужчины. > Соответственно мужики сами их взломать не могут, а тётки, используя > альтернативную логику, щёлкают их как орешки. > Вот пусть попробуют свой алгоритм придумать — мы их ух как!
Наверное ей это уже не под силу, ведь для составления алгоритма надо правильную логику применять.
Проблема в том, что китайцев много — то что нужно ломать миллион лет, миллиард китайцев ломают за 1/1000 года, т.е. за
~8 часов.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, Left2, Вы писали:
L>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
MD4/MD5/SHA-0/SHA-1/SHA-2 — это всё одно семейство и отличаются они только сжимающей функцией и начальными векторами.
Все эти алгоритмы предусматривают такой вариант, что если документы имеют разную длину, то их хэши наверняка будут разными — благодаря тому, что в конец сообщения перед хэшированием дописывается паддинг с длиной сообщения (называется трюк MD-усиление).
Само хэширование выполняется так: h = Hash(IV, Mi), Mi — блок сообщения, IV — это начальный вектор, который либо задаётся вначале, либо это значение хэширования предыдущего блока сообщения.
Теперь чтобы сделать два разных сообщения с одинаковым хэшем достаточно изменить только один блок сообщения, найти начальное значение вектора и найти к нему коллизию (скорее всего это будет какой-то мусорный блок).
То есть имеем два сообщения вида:
M = [M1, M2, M3] и M' = [M1, M2', M3] и такие что Hash(M) = Hash(M') — теперь осталось скрыть факт изменения и сделать сообщения осмысленными, для этого можно пользоваться всякими трюками современных редакторов аля Word — пусть сообщение — это некий договор, в котором нам требуется изменить некоторую цифру (напоминаю, что блок M3 может быть произвольным). Пишем некоторое выражение (аля "поле" в Word), которое вычисляется при открытии и базируется на содержании блока M2 или M2', например использует факт, что в блоке M2' имеется некий взведённый бит (0->1 от M2->M2'). И в зависимости от этого условия пишет в документ разные цифры: 100 рублей или 1000000 рублей.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Шахтер, Вы писали:
E>>>Да, brute force еще никто не отменял E>>>Тем более, что DES, если я не ошибаюсь был взломан за 8-мь часов.
Ш>>DES может быть взломан полным перебором ключей на специальной распределённой DES машине стоимостью около 100000$.
Ш>>Для 3DES взлом грубой силой невозможен.
E>На счет 8-ми часов ошибся, но за один день точно управлялись: E>
E>Six months later, in response to RSA Security's DES Challenge III, in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day — 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended Triple DES (also referred to as 3DES or TDES).
E>Что касается 3DES, то взом грубой силой, теоритически возможен.
Ну разумеется. Как и любого шифра с конечным пространством ключей.
Вопрос как всегда в практической реализуемости. Пока не просматривается.
Т.е. если ты украл табличку хэшей sha1 паролей для входа в какую-нибудь систему, то сможешь "быстро" подобрать пароль, с
которым тебя система авторизует.
Или если у тебя какая-то система передаёт сообщение и в качестве проверки целостности использует sha1 хэш, то можно так
исказить это сообщение, что подмену не просекут — хэши будут совпадать.
Вообще говоря, это всё не так уж ужасно, но сам факт...
> А то красной селедкой пахнет.
Это что?
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
.>Т.е. если ты украл табличку хэшей sha1 паролей для входа в какую-нибудь систему, то сможешь "быстро" подобрать пароль, с .>которым тебя система авторизует. .>Или если у тебя какая-то система передаёт сообщение и в качестве проверки целостности использует sha1 хэш, то можно так .>исказить это сообщение, что подмену не просекут — хэши будут совпадать.
.>Вообще говоря, это всё не так уж ужасно, но сам факт...
Хм.. А что тогда ужасно?
Где почитать нормальные сообщения на эту тему?
Какова сложность алгоритма поиска коллизии?
Igor Trofimov wrote:
> Где почитать нормальные сообщения на эту тему? > Какова сложность алгоритма поиска коллизии?
По sha1 не знаю, надо погуглить, а вот по md5 неплохая статейка тут: http://www.codeproject.com/dotnet/HackingMd5.asp
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, Шахтер, Вы писали:
А>>А что осталось-то?.. Ш>Если ты имеешь ввиду, какие ещё hash функции есть, то например, SHA-256, SHA-384, SHA-512.
Они основаны на тех же принципах что и MD5 и SHA-1, а так как основной подход к нахождению коллизий в них уже найден, то вскрытие более сильных функций — считается делом времени.
Также в том году небезызвестный NIST провёл конкурс Hash WorkShop — предполагалось выработать новый вариант стандарта на хэш-функцию. Пока о результатах ничего не слышно.
Здравствуйте, Andir, Вы писали:
А>>>А что осталось-то?.. Ш>>Если ты имеешь ввиду, какие ещё hash функции есть, то например, SHA-256, SHA-384, SHA-512.
A>Они основаны на тех же принципах что и MD5 и SHA-1, а так как основной подход к нахождению коллизий в них уже найден, то вскрытие более сильных функций — считается делом времени.
Ну, подходы к вскрытию DES и RSA так же известны давно. Только элементарное увеличение длины ключа в несколько раз делает осуществление взлома на существующих аппаратных ресурсах практически бесполезным.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
eao197 wrote: > Ну, подходы к вскрытию DES и RSA так же известны давно. Только > элементарное увеличение длины ключа в несколько раз делает осуществление > взлома на существующих аппаратных ресурсах практически бесполезным.
Для DES увеличение ключа — бесполезно. Для 3DES у нас будет перебор в
2^80 вариантов, если я не ошибаюсь, а алогитмическая сложность у него
почти как у AES.
Здравствуйте, Cyberax, Вы писали:
>> Ну, подходы к вскрытию DES и RSA так же известны давно. Только >> элементарное увеличение длины ключа в несколько раз делает осуществление >> взлома на существующих аппаратных ресурсах практически бесполезным. C>Для DES увеличение ключа — бесполезно.
Я бы больше сказал -- невозможно
Т.к. он жестко завязан на 64-х битовые ключи, из которых для шифрования используются только 56-ть бит.
Но в том-то и дело, что имея в основе довольно слабоустойчивый алгоритм, устойчивость шифрования увеличили в три раза просто трижды применяя DES над шифруемым текстом.
C> Для 3DES у нас будет перебор в 2^80 вариантов, если я не ошибаюсь, а алогитмическая сложность у него C>почти как у AES.
Насколько помню, в 3DES используется две основные схемы -- с ключами в 128 бит (где только 112 бит используются при шифровании) и с ключами в 192 бита (где только 168 бит задействованы). Причем, теоритически для ключа в 128 бит есть возможность подбора ключей но для этого требуется получение и хранение 2^56 64-х битовых значений. Для ключей же в 192 бита только полный перебор.
Что касается алгоритмической сложности и устойчивости DES по отношению к AES, то не буду ничего утверждать, т.к. подзабыл все уже основательно. Какие-то атаки на него были, и проблема подбора хорошего ключа для него была. Но, если не ошибаюсь, было это не сильно критично.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
C>> Для 3DES у нас будет перебор в 2^80 вариантов, если я не ошибаюсь, а алогитмическая сложность у него C>>почти как у AES.
E>Насколько помню, в 3DES используется две основные схемы -- с ключами в 128 бит (где только 112 бит используются при шифровании) и с ключами в 192 бита (где только 168 бит задействованы). Причем, теоритически для ключа в 128 бит есть возможность подбора ключей но для этого требуется получение и хранение 2^56 64-х битовых значений. Для ключей же в 192 бита только полный перебор.
Подробности можно найти по ссылкам, например, здесь. В частности:
Quoting from the paper "Attacking Triple Encryption" cited above:
[A]bout 2^108 steps of computation are sufficient to break three-key triple DES. If one concentrates on the number of single DES operations and assumes the other operations to be much faster, 2^90 of these are enough.
Better attacks than this are available against two-key triple DES (which should only be used for backward compatibility, if at all).
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Ну, подходы к вскрытию DES и RSA так же известны давно. Только элементарное увеличение длины ключа в несколько раз делает осуществление взлома на существующих аппаратных ресурсах практически бесполезным.
Не знаю ни одного подхода к взлому DES и RSA. Ключ DES — увеличить невозможно. Отсюда я делаю вывод, что ты имел ввиду перебор ключей RSA и соответственно соревнования по распределённому вычислению ключей RSA.
Здесь ситуация иная, используется вполне конкретный алгоритм, который позволяет уменьшить перебор до неприличных значений — MD4 — вручную на бумажке, MD5 за несколько секунд (по результатам прошлого года).
Алгоритм имеет слабое место: для его использования требуется найти хотя бы один достаточно длинный путь в котором сохраняется коллизия (длина пути — кол-во операций при котором возможно сохранение коллизии внутри сжимающей функции). Нахождение выполняется вручную (грубо говоря — случайно), и для MD5 — известен ровно 1 путь, которого хватило чтобы найти коллизию, а далее и стало возможно находить произвольные коллизии.
Собственно применение этого алгоритма к SHA-256 дело времени нахождения такого пути. Вполне возможно, что его найдут легко и быстро а может и долго и муторно.
Возможно будет формализована сложность нахождения такого пути, а возможно задача будет автоматизирована.
Чисто эмпирически можно оценить, учитывая, что применение этого алгоритма к SHA-1 (более сложной функции, и дело не только в длине) заняло менее года, то применение к SHA-256 (отличается только длиной, алгоритм вычисления не отличается ничем), что "взлом" займёт примерно 1-2 года.
Здравствуйте, Andir, Вы писали:
E>>Ну, подходы к вскрытию DES и RSA так же известны давно. Только элементарное увеличение длины ключа в несколько раз делает осуществление взлома на существующих аппаратных ресурсах практически бесполезным.
A>Не знаю ни одного подхода к взлому DES и RSA. Ключ DES — увеличить невозможно. Отсюда я делаю вывод, что ты имел ввиду перебор ключей RSA и соответственно соревнования по распределённому вычислению ключей RSA.
Да, brute force еще никто не отменял
Тем более, что DES, если я не ошибаюсь был взломан за 8-мь часов.
И еще в одном случае я слышал, что для ключей DES так же возможны коллизии.
<...с поскипанным согласен...>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Andir, Вы писали:
A>Не знаю ни одного подхода к взлому DES и RSA.
Про DES — я конечно загнул, имел ввиду, что практического алгоритма взлома зашифрованного сообщения DES (кроме брутфорса) — мне неизвестно. Всякие дифференциальные и линейные криптоанализы, которые и развивались благодаря DES — мне конечно известны
eao197 wrote: > C>Для DES увеличение ключа — бесполезно. > Я бы больше сказал -- невозможно > Т.к. он жестко завязан на 64-х битовые ключи, из которых для шифрования > используются только 56-ть бит.
Можно, берешь три разных ключа и последовательно шифруешь ими.
Получается 3DES — стойкость будет больше, чем у обычного DES, но все
равно не очень высокая.
> Но в том-то и дело, что имея в основе довольно слабоустойчивый алгоритм, > устойчивость шифрования увеличили в три раза просто трижды применяя DES > над шифруемым текстом.
Не в "три раза", а примерно в 2^34 раз. Сложность нелинейно растет
(из-за парадокса дней рождений).
> Что касается алгоритмической сложности и устойчивости DES по отношению к > AES, то не буду ничего утверждать, т.к. подзабыл все уже основательно. > Какие-то атаки на него были, и проблема подбора хорошего ключа для него > была. Но, если не ошибаюсь, было это не сильно критично.
Пока 3DES считается достаточно стойким алгоритмом, но у него нет запаса
от будущих атак.
Здравствуйте, Cyberax, Вы писали:
>> C>Для DES увеличение ключа — бесполезно. >> Я бы больше сказал -- невозможно >> Т.к. он жестко завязан на 64-х битовые ключи, из которых для шифрования >> используются только 56-ть бит. C>Можно, берешь три разных ключа и последовательно шифруешь ими. C>Получается 3DES — стойкость будет больше, чем у обычного DES, но все C>равно не очень высокая.
Извини за догматизм, но я таки настаиваю, что в DES нельзя изменить длину ключа. В отличии от, скажем, AES, Blowfish, MARS или Twofish.
TripleDES (3DES) -- это уже другой алгоритм, хотя и построенный на основе DES. К тому же по стандарту 3DES реализуется как DES(k3,UNDES(k2,DES(k1,v))), а не последовательными шифрованиями.
Формальность здесь очень важна
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Cyberax, Вы писали:
C>eao197 wrote: >> Ну, подходы к вскрытию DES и RSA так же известны давно. Только >> элементарное увеличение длины ключа в несколько раз делает осуществление >> взлома на существующих аппаратных ресурсах практически бесполезным. C>Для DES увеличение ключа — бесполезно.
Что значит, увеличить ключ для DES? Я не понимаю смысла этой фразы.
DES как алгоритм использует ключ 56 бит. Ничего изменть тут нельзя.
C> Для 3DES у нас будет перебор в C>2^80 вариантов, если я не ошибаюсь, а алогитмическая сложность у него C>почти как у AES.
Здравствуйте, Cyberax, Вы писали:
C>eao197 wrote: >> C>Для DES увеличение ключа — бесполезно. >> Я бы больше сказал -- невозможно >> Т.к. он жестко завязан на 64-х битовые ключи, из которых для шифрования >> используются только 56-ть бит. C>Можно, берешь три разных ключа и последовательно шифруешь ими. C>Получается 3DES — стойкость будет больше, чем у обычного DES, но все C>равно не очень высокая.
"Не очень высокая" -- это невзламываемая при современном уровне развития вычислительной техники.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Cyberax, Вы писали:
>>> C>Для DES увеличение ключа — бесполезно. >>> Я бы больше сказал -- невозможно >>> Т.к. он жестко завязан на 64-х битовые ключи, из которых для шифрования >>> используются только 56-ть бит. C>>Можно, берешь три разных ключа и последовательно шифруешь ими. C>>Получается 3DES — стойкость будет больше, чем у обычного DES, но все C>>равно не очень высокая.
E>Извини за догматизм, но я таки настаиваю, что в DES нельзя изменить длину ключа. В отличии от, скажем, AES, Blowfish, MARS или Twofish. E>TripleDES (3DES) -- это уже другой алгоритм, хотя и построенный на основе DES. К тому же по стандарту 3DES реализуется как DES(k3,UNDES(k2,DES(k1,v))), а не последовательными шифрованиями.
Это и есть последовательное шифрование.
E>Формальность здесь очень важна
Здравствуйте, Andir, Вы писали:
A>Здравствуйте, Аноним, Вы писали:
А>>http://safe.cnews.ru/news/line/index.shtml?2007/01/23/232525
А>>А что осталось-то?..
A>Кратко говоря — утка, прошлогодняя Пока не найдут хоть одну коллизию, считать взломанным алгоритм даже как-то странно. A>Суть простая, вместо 2^80 операций по перебору для нахождения коллизии хэша достаточно и 2^63. Статья об этом была опубликована на Crypto 2006, а заявлено о факте вообще было чуть ли не в феврале того года.
Ну собственно, я на это и намекал. SHA-1 вполне себе юзабельный алгоритм несмотря на найденые методы ускорения процесса взлома грубой силой.
Здравствуйте, Шахтер, Вы писали:
E>>TripleDES (3DES) -- это уже другой алгоритм, хотя и построенный на основе DES. К тому же по стандарту 3DES реализуется как DES(k3,UNDES(k2,DES(k1,v))), а не последовательными шифрованиями.
Ш>Это и есть последовательное шифрование.
Опять же с точки зрения догматизма последовательное шифрование -- это DES(k3,DES(k2,DES(k1,v))), что даст совсем другой результат, нежели DES(k3,UNDES(k2,DES(k1,v))). Поскольку при DES и при UNDES в разном порядке применяются вектора IP и IP-1 к шифруемому/дешифруемому тексту.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Шахтер, Вы писали:
E>>Да, brute force еще никто не отменял E>>Тем более, что DES, если я не ошибаюсь был взломан за 8-мь часов.
Ш>DES может быть взломан полным перебором ключей на специальной распределённой DES машине стоимостью около 100000$.
Ш>Для 3DES взлом грубой силой невозможен.
Six months later, in response to RSA Security's DES Challenge III, in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day — 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended Triple DES (also referred to as 3DES or TDES).
Что касается 3DES, то взом грубой силой, теоритически возможен.
Практически же сейчас это точно возможно и, насколько я понимаю, еще не скоро станет возможно. Хотя быстродействие машин до сих пор растет стремительными темпами.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Шахтер, Вы писали:
E>>>TripleDES (3DES) -- это уже другой алгоритм, хотя и построенный на основе DES. К тому же по стандарту 3DES реализуется как DES(k3,UNDES(k2,DES(k1,v))), а не последовательными шифрованиями.
Ш>>Это и есть последовательное шифрование.
E>Опять же с точки зрения догматизма последовательное шифрование -- это DES(k3,DES(k2,DES(k1,v))), что даст совсем другой результат, нежели DES(k3,UNDES(k2,DES(k1,v))). Поскольку при DES и при UNDES в разном порядке применяются вектора IP и IP-1 к шифруемому/дешифруемому тексту.
С точки зрения догматизма последовательное шифрование это просто применение нескольких шифрующих преобразований к блоку информации. UNDES как алгоритм шифрования ничем не хуже DES.
3DES сделан так для облегчения реализации совместимости с DES. Если k2=k3, то получается чистый DES с k1. Т.е. множество преобразований 3DES включает в себя DES.
B>А вот это не так. B>"Взломали" в данном случае означает то, что научились находить 2 сообщения, которые имеют один и тот же хэш. Найти сообщение, соответствующее какому-то *конкретному* хэшу по-прежнему очень трудно.
Насколько я понимаю, найти сообщение, соответствующее какому-то *конкретному* хэшу просто невозможно — хотя бы потому, что любому конкретному хешу соответствует бесконечное множество сообщений. Влом хеш-алгоритмов состоит именно в подборе коллизий — когда появляется возможность модифицировать сообщение, оставив хеш неизменным.
Здравствуйте, Vi2, Вы писали:
Vi2>Не так все критично. На вопрос "Ну, что, уходим?" в магазине ответ, млин, один и тот же. А этот — "Ну что, ещё разок?"?
Причемт тут логика? Это рефлекторное.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Brabant wrote:
> Я имел в виду, что найти хотя бы одно сообщение, соответствующее > конкретному хэшу очень трудно как в случае SHA-1, так и в случае MD-5 > (на счет MD-4 не уверен).
Не надо искать сообщение, можно данное привести к такому виду, чтобы оно имело такой же хеш.
Допустим, у тебя есть word документ (например, невинная рекомендация с работы), ты просишь начальника подписать этот
документ. Подписывается не сам документ, а его хеш (ибо подписывать весь документ слишком накладно с т.з. ресурсов).
Ты можешь создать свой word-документ, который будет говорить о том, что тебе нужно выдать огромную премию. Так вот ты
можешь его создать таким образом, что его хеш будет точно таким же как у рекомендации, а значит к нему можно прикрепить
ту же подпись. И никакой софт не обнаружит подлог.
> Вообще существует несколько свойств, которыми должны обладать хэш-функции: > Preimage resistant (See one way function for a related but slightly > different property): given h it should be hard to find any m such that h > = hash(m).
> Second preimage resistant: given an input m1, it should be hard to find > another input, m2 (not equal to m1) such that hash(m1) = hash(m2).
Не уловил. А в чём отличие? Положим "h = hash(m1)" (а это естественно простая операция), тогда второе свойство сводится
к первому.
> То, о чем написал ты — атака на второе свойство. Таких атак по-прежнему > нет, т.е. SHA-1 остается second preimage resistant и preimage resistant. > Китаянка доказала, что SHA-1 НЕ является collision-resistant, но для
Честно говоря, я не очень понял что она доказала о SHA-1, c MD5 более подробно расписано и во многих источниках.
Вот тут например http://www.codeproject.com/dotnet/HackingMd5.asp
> большинства приложений это и не важно. Правда говорят, что в Микрософте
Трудно сказать. Может быть и важным, смотря для чего хеш используется. Например, если для цифровой подписи, то можно,
как я понимаю, делать вирусы/драйвера, которые будут подписаны майкрософтом.
> есть специальный человек, который сейчас "на всякий случай" во всех > продуктах заменяет SHA-1 на SHA-256. А раньше, судя по слухам, этот > человек заменял MD-5 на SHA-1 Есть подозрение, что и в будущем без > работы он не останется
А что поделаешь?..
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ., Вы писали:
.>Не надо искать сообщение, можно данное привести к такому виду, чтобы оно имело такой же хеш. .>Допустим, у тебя есть word документ (например, невинная рекомендация с работы), ты просишь начальника подписать этот .>документ. Подписывается не сам документ, а его хеш (ибо подписывать весь документ слишком накладно с т.з. ресурсов). .>Ты можешь создать свой word-документ, который будет говорить о том, что тебе нужно выдать огромную премию. Так вот ты .>можешь его создать таким образом, что его хеш будет точно таким же как у рекомендации, а значит к нему можно прикрепить .>ту же подпись. И никакой софт не обнаружит подлог.
Сначала хорошо было бы иметь софт, который создаст этот второй документ с осмысленным содержимым и точно таким же хэшем. Если это вообще возможно.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
.>>Не надо искать сообщение, можно данное привести к такому виду, чтобы оно имело такой же хеш. .>>Допустим, у тебя есть word документ (например, невинная рекомендация с работы), ты просишь начальника подписать этот .>>документ. Подписывается не сам документ, а его хеш (ибо подписывать весь документ слишком накладно с т.з. ресурсов). .>>Ты можешь создать свой word-документ, который будет говорить о том, что тебе нужно выдать огромную премию. Так вот ты .>>можешь его создать таким образом, что его хеш будет точно таким же как у рекомендации, а значит к нему можно прикрепить .>>ту же подпись. И никакой софт не обнаружит подлог.
E>Сначала хорошо было бы иметь софт, который создаст этот второй документ с осмысленным содержимым и точно таким же хэшем. Если это вообще возможно.
Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
Здравствуйте, Left2, Вы писали:
L>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
Так вот этот хвостик может быть таковым, что в документ его запихнуть не представится никакой возможности, в противном случае сама структура документа (его формат) будет нарушен. Особенно, если этот документ будет не бинарный, в котром хрен знает что может быть, а текстовый (XML, LaTeX) в котором любой мусор будет выглядеть мусором.
Это как попытаться расплатиться банкнотой, густо политой черными чернилами.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Left2, Вы писали:
L>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
Еще подумалось. Ведь поиск коллизии -- это поиск последовательности X, для которой h(X) будет равен h(Y) (где Y -- неизвестная нам исходная последовательность). В задаче с подделкой документа эта задача усложняется -- нужно найти последовательность X с обязательным префиксом px (сама подделка). И я не знаю, решается ли такая задача в общем случае.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
L>>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
E>Так вот этот хвостик может быть таковым, что в документ его запихнуть не представится никакой возможности, в противном случае сама структура документа (его формат) будет нарушен. Особенно, если этот документ будет не бинарный, в котром хрен знает что может быть, а текстовый (XML, LaTeX) в котором любой мусор будет выглядеть мусором.
E>Это как попытаться расплатиться банкнотой, густо политой черными чернилами.
Ну если насчёт XML или текста я согласен, то вот в бинарных форматах практически всегда можно найти "дырки" в которые можно впихнуть "хвосты". Ну и XML вообщем-то глазами мало кто читает.
Здравствуйте, eao197, Вы писали:
L>>Я вот тоже на эту тему думал. Не знаю насчёт SHA-1, но как минимум MD5 — это алгоритм работы над потоком байт. То бишь, есть текущее(начальное) состояние и поток байт(с случае MD5 ЕМНИП это 64-разрядные слова), которые изменяют это состояниие. Так вот, если тебе нужно модифицировать документ — ты меняешь его состояние, а потом задача сводится к тому что нужно дописать какие-то данные дабы хеш остался тем же. Т.о., получается что мы решаем задачу No1 — поиск коллизии хеш-функции (правда, начальное состояние будет другим). Поправьте меня если не прав.
E>Так вот этот хвостик может быть таковым, что в документ его запихнуть не представится никакой возможности, в противном случае сама структура документа (его формат) будет нарушен. Особенно, если этот документ будет не бинарный, в котром хрен знает что может быть, а текстовый (XML, LaTeX) в котором любой мусор будет выглядеть мусором.
Да, это тоже задача, но разрешимая. В xml всегда можно вставить пробелы, переводы строк, комментарий или processing-instruction, которые софтом обычно игнорируются. Конечно, если документы просматриваются человеком на наличие "неправильностей", то может и можно такое избежать, но много ли ты знаешь систем, где пользователи читают xml?
Короче говоря, никаких принципиальных препятствий нет. А хотелось бы, как, например, с возможностью факторизации чисел.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
A>Также в том году небезызвестный NIST провёл конкурс Hash WorkShop — предполагалось выработать новый вариант стандарта на хэш-функцию. Пока о результатах ничего не слышно.
А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)?
И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать").
Здравствуйте, netch80, Вы писали:
N>А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)?
О функциях с ключами речь не идёт, они относительно неудобны и медленны.
N>И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать").
SHA1 — ещё не найдено ни одной коллизии, вопрос взлома пока только теоретический. MD5 — последние результаты, нахождение произвольной коллизии = менее секунды.
Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком
Здравствуйте, Andir, Вы писали:
N>>А что амеры думают про алгоритмы на эллиптических функциях (таких как функция ГОСТ Р 34.11)? A>О функциях с ключами речь не идёт, они относительно неудобны и медленны.
Можно чуть подробнее?
N>>И ещё интересно бы узнать насколько сейчас могут подделывать _одновременно_ MD5 и SHA1 (это чтобы OpenPGP стандарт "взломать"). A>SHA1 — ещё не найдено ни одной коллизии, вопрос взлома пока только теоретический. MD5 — последние результаты, нахождение произвольной коллизии = менее секунды. A>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком :-)
Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя.
Здравствуйте, netch80, Вы писали:
N>Можно чуть подробнее?
Что именно? NIST рассматривает только однонаправленные функции без использования шифрования/ключевой информации, грубо говоря алгоритм должен использовать простые и лёгкие для анализа сжимающие функции. А ГОСТ, про который ты спросил — это хэширование с использованием шифрования из другого госта + генерирование ключей из самого сообщения.
A>>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком N>Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя.
То есть предполагается подобрать такую коллизию сообщения M: чтобы => MD5(M) + SHA-1(M) = MD5(M') + SHA-1(M'). О результатах в этом направлении мне ничего не известно, а теоретически взлом возможен за 2^80 коллизий SHA-1 .
Здравствуйте, Andir, Вы писали:
A>Здравствуйте, netch80, Вы писали:
N>>Можно чуть подробнее?
A>Что именно? NIST рассматривает только однонаправленные функции без использования шифрования/ключевой информации, грубо говоря алгоритм должен использовать простые и лёгкие для анализа сжимающие функции. А ГОСТ, про который ты спросил — это хэширование с использованием шифрования из другого госта + генерирование ключей из самого сообщения.
То есть функцию из ГОСТ Р 34.11 нельзя применить как хэш-функцию, не используя никаких дополнительных данных? Извини, не сталкивался с ней плотно, поэтому уточняю.
A>>>Одновременный "взлом" двух хэш-функций зависит от того как именно они используются. А с алгоритмами OpenPGP я не знаком N>>Там просто конкатенация значений двух контрольных сумм, далее шифруемая секретным ключом отправителя. A>То есть предполагается подобрать такую коллизию сообщения M: чтобы => MD5(M) + SHA-1(M) = MD5(M') + SHA-1(M'). О результатах в этом направлении мне ничего не известно, а теоретически взлом возможен за 2^80 коллизий SHA-1 .
То есть пока скорее всего неактуально. Это хорошо.
Пока не найдут хоть одну коллизию, считать взломанным алгоритм даже как-то странно.
