Здравствуйте, 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.
Здравствуйте, 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 паролей для входа в какую-нибудь систему, то сможешь "быстро" подобрать пароль, с .>которым тебя система авторизует.
А вот это не так.
"Взломали" в данном случае означает то, что научились находить 2 сообщения, которые имеют один и тот же хэш. Найти сообщение, соответствующее какому-то *конкретному* хэшу по-прежнему очень трудно.
Так что "взлом" не имеет фатальных последствий прямо сейчас, а скорее указывает на потенциальную слабость хэш-функции.
B>А вот это не так. B>"Взломали" в данном случае означает то, что научились находить 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 Есть подозрение, что и в будущем без работы он не останется
Здравствуйте, 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 вообщем-то глазами мало кто читает.
