Comments 39
Подписи это конечно хорошо, но по моему самое время подумать о ядовитых pull-request в git. Похоже коллизии могут повреждать репозиторий.
не повреждать, а терять новый объект.
в целом, выходит безопасно — перезаписать с помощью коллизии что-то нельзя.
в целом, выходит безопасно — перезаписать с помощью коллизии что-то нельзя.
webkit'овскую автоматизацию это развалило: https://bugs.webkit.org/show_bug.cgi?id=168774#c23
UFO just landed and posted this here
> И опять же, как будто ничего кроме SHA не существует, хотя приличных хэш функций десятки.
Ну, вообще-то SHA — это аббревиатура Secure Hash Algorithm, то есть как раз «приличная хэш-фунция может быть признана SHA», а не наоборот, семейство SHA-функций входит во множество «приличных». Для этого её авторы должны попробовать доказать её криптографическую надежность, а ученые умы должны потыкать в неё своими инструментами, покачать убеленными сединами головами и либо одобрить, либо отклонить. Ну там всякие скорости, ресурсоемкости и прочие вещи всегда учитываются.
Ну, вообще-то SHA — это аббревиатура Secure Hash Algorithm, то есть как раз «приличная хэш-фунция может быть признана SHA», а не наоборот, семейство SHA-функций входит во множество «приличных». Для этого её авторы должны попробовать доказать её криптографическую надежность, а ученые умы должны потыкать в неё своими инструментами, покачать убеленными сединами головами и либо одобрить, либо отклонить. Ну там всякие скорости, ресурсоемкости и прочие вещи всегда учитываются.
> Вектор атаки здесь понятен: злоумышленник может подменить «хороший» файл своим экземпляров с закладкой, вредоносным макросом или загрузчиком трояна. И этот «плохой» файл будет иметь такой же хеш или цифровую подпись.
Нет. Тут генерируются два файла одновременно с одинаковым хэшем. Сгенерировать один файл по известному хэшу в разы сложнее!
Нет. Тут генерируются два файла одновременно с одинаковым хэшем. Сгенерировать один файл по известному хэшу в разы сложнее!
Относительно простой способ проверить не скомпрометирован ли файл — иметь как минимум два разных типа хэшей у одного объекта (к примеру, SHA-1 и SHA-256). Представляется чем-то невероятным генерацию коллизий одновременно по двум типам.
Генерация коллизий по двум типам хэшей ничем не отличается от генерации коллизий по одному хэшу (по сложности равному сумме двух предыдущих).
Думаю, это ближе к примеру с Гитом. Чтоб не было случайных коллизий.
Сумме? Может, всё-таки, произведению?
Ситуация еще хуже. Сам только сегодня узнал.
Оказывается что, теоретически, конкатенация 2-х хэшей не лучше чем самый слабый из 2-х.
В этом конкретном случае, ша1 + мд5 будет (скорее всего) лучше чем взломанный ша1 (2^50 colision resistence); и лучше чем взломанный мд5 (2^40).
Но, при этом, не устойчивее к генерации коллизий чем качественны, не взломанный, 160-битный хэш, каким считался ша1 (2^80)
Для большей информации, искать «Multicollisions in iterated hash functions. Application to cascaded constructions»
Оказывается что, теоретически, конкатенация 2-х хэшей не лучше чем самый слабый из 2-х.
В этом конкретном случае, ша1 + мд5 будет (скорее всего) лучше чем взломанный ша1 (2^50 colision resistence); и лучше чем взломанный мд5 (2^40).
Но, при этом, не устойчивее к генерации коллизий чем качественны, не взломанный, 160-битный хэш, каким считался ша1 (2^80)
Для большей информации, искать «Multicollisions in iterated hash functions. Application to cascaded constructions»
О как. Благодарю за информацию.
UFO just landed and posted this here
а зачем использовать конкатенацию, если можно проводить валидацию по 2 хэшам? например MD5 и SHA-1. в этом случае вероятности нахождения коллизий для каждого из использованных алгоритмов перемножаются.
вероятность нахождения коллизии для SHA-1 равна 2^-80 (=8.3e-25) а для MD5 — 2^-40(=9.1e-13). тогда произведение вероятностей будет равно 7.5e-37.
вероятность нахождения коллизии для SHA-1 равна 2^-80 (=8.3e-25) а для MD5 — 2^-40(=9.1e-13). тогда произведение вероятностей будет равно 7.5e-37.
Мы говорим об одинаковых вещах по разному.
— Рассчитать оба хэша; конкатенировать их; а потом сравнить.
— Рассчитать оба хэша; и сравнить отдельно.
Очень часто в криптографии интуитивные выводы не верны.
И это один из таких случаев.
вероятность нахождения коллизии для идеального 160 -битного хэша: 2^-80
вероятность нахождения коллизии для идеального 128 -битного хэша: 2^-64
Вы правы, были бы эти хэши идеальными, вероятность коллизии в конкатенации была бы 2^(-80-64) = 2 ^ (-144).
Но!!! если рассчитать хотя-бы один из таких хэшей по итеративному принципу, вероятность коллизии становиться «чуть менее» 2^-80.
В реальности: и MD5, и SHA1, и SHA2… итеративные хэши; а вот SHA3 нет.
Так вот,
в SHA1 нашли возможность повысить вероятность до 2^-50
в MD5 и того хуже… 2^-40
Вероятность найти коллизию в SHA1 + MD5 где-то между 2^-50 (SHA1) и 2^-80+epsilon (теоретический максимум); но никак не 2^(-50-40) = 2^(-90)
— Рассчитать оба хэша; конкатенировать их; а потом сравнить.
— Рассчитать оба хэша; и сравнить отдельно.
Очень часто в криптографии интуитивные выводы не верны.
И это один из таких случаев.
вероятность нахождения коллизии для идеального 160 -битного хэша: 2^-80
вероятность нахождения коллизии для идеального 128 -битного хэша: 2^-64
Вы правы, были бы эти хэши идеальными, вероятность коллизии в конкатенации была бы 2^(-80-64) = 2 ^ (-144).
Но!!! если рассчитать хотя-бы один из таких хэшей по итеративному принципу, вероятность коллизии становиться «чуть менее» 2^-80.
В реальности: и MD5, и SHA1, и SHA2… итеративные хэши; а вот SHA3 нет.
Так вот,
в SHA1 нашли возможность повысить вероятность до 2^-50
в MD5 и того хуже… 2^-40
Вероятность найти коллизию в SHA1 + MD5 где-то между 2^-50 (SHA1) и 2^-80+epsilon (теоретический максимум); но никак не 2^(-50-40) = 2^(-90)
Вероятность найти коллизию в SHA1 + MD5 где-то между 2^-50 (SHA1) и 2^-80+epsilon (теоретический максимум); но никак не 2^(-50-40) = 2^(-90)
И всё-таки это лучше, чем один только SHA1 (2^-50) или один только MD5 (2^-40), нет?
Очень часто в криптографии интуитивные выводы не верны.
Никакой интуиции, одна суровая логика.
да, вы правы. Это лучше чем каждый по отдельности.
На много ли? скорее всего нет. Почитайте документ который я упомянул: «Multicollisions in iterated hash functions. Application to cascaded constructions»
Если коротко. Самая простая атака будет примерно следующей:
Генерируются 2 документа с одинаковым sha1: 2^50… а вот md5 у них будет разный.
После этого, добавляем (одинаковый) мусор в конец этих 2-х документов (почитайте про «Length extension attack»). Скорее всего, этот мусор будет незаметным в бинарном документе. Получаем другие 2 документа с одинаковым sha1, но с разным md5.
Повторяем 2^64 (md5) раз с разным мусором. С большой вероятностью, найдем 2 документа с одинаковым md5 И sha1.
В конце концов, нашли хэш за 2^64 + 2^50 = 2^64.
И это «тупой перебор». В реальность же дело (скорее всего) хуже.
Как я уже говорил, этот трюк не пройдет с sha3, но у него свой проблемы.
Если хэш важен, используйте sha2 и будьте готовы заменить когда взломают. Не надо надеяться что 2 слабых хэша спасут из-за того что их 2.
Плюс к этому, есть вероятность что sha1+md5 будет медленнее чем один хороший хэш. Зачем тогда мучатся?
На много ли? скорее всего нет. Почитайте документ который я упомянул: «Multicollisions in iterated hash functions. Application to cascaded constructions»
Если коротко. Самая простая атака будет примерно следующей:
Генерируются 2 документа с одинаковым sha1: 2^50… а вот md5 у них будет разный.
После этого, добавляем (одинаковый) мусор в конец этих 2-х документов (почитайте про «Length extension attack»). Скорее всего, этот мусор будет незаметным в бинарном документе. Получаем другие 2 документа с одинаковым sha1, но с разным md5.
Повторяем 2^64 (md5) раз с разным мусором. С большой вероятностью, найдем 2 документа с одинаковым md5 И sha1.
В конце концов, нашли хэш за 2^64 + 2^50 = 2^64.
И это «тупой перебор». В реальность же дело (скорее всего) хуже.
Как я уже говорил, этот трюк не пройдет с sha3, но у него свой проблемы.
Если хэш важен, используйте sha2 и будьте готовы заменить когда взломают. Не надо надеяться что 2 слабых хэша спасут из-за того что их 2.
Плюс к этому, есть вероятность что sha1+md5 будет медленнее чем один хороший хэш. Зачем тогда мучатся?
Плюс к этому, есть вероятность что sha1+md5 будет медленнее чем один хороший хэш. Зачем тогда мучатся?
С этим не поспоришь, низкая эффективность — очевидный недостаток. Однако я тут вижу некоторый компромисс. В «хорошем» может обнаружиться фатальная уязвимость, в этом случае два хэша дают какой-то запас надёжности и времени за не очень высокую цену.
После этого, добавляем (одинаковый) мусор в конец этих 2-х документов (почитайте про «Length extension attack»). Скорее всего, этот мусор будет незаметным в бинарном документе. Получаем другие 2 документа с одинаковым sha1, но с разным md5.
Тут у вас ошибка, по-моему. Если мусор добавили одинаковый, а документы изначально разные, то sha1 будет разный.
Корркетно было бы добавлять только к одному документу, сохраняя sha1 и подбирая при этом MD5, чтобы совпал со вторым.
Но в общем я согласен, что суммарная устойчивость может при определённых условиях оказаться не сильно выше, чем каждый хэш в отдельности.
Вы опять заблуждаетесь. По конструкции sha1, хэш у них будет будет одинаковый:
$ sha1sum shattered-*.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-2.pdf
$ echo «musssor» >> shattered-1.pdf
$ echo «musssor» >> shattered-2.pdf
$ sha1sum shattered-*.pdf
589dec295aaa1fb915e767db80d5b7533b1b7e16 shattered-1.pdf
589dec295aaa1fb915e767db80d5b7533b1b7e16 shattered-2.pdf
$ sha1sum shattered-*.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a shattered-2.pdf
$ echo «musssor» >> shattered-1.pdf
$ echo «musssor» >> shattered-2.pdf
$ sha1sum shattered-*.pdf
589dec295aaa1fb915e767db80d5b7533b1b7e16 shattered-1.pdf
589dec295aaa1fb915e767db80d5b7533b1b7e16 shattered-2.pdf
Я думал, у sha1 состояние более, чем просто текущий хэш.
Согласен, заблуждаюсь. Но почему «опять»? ))
Согласен, заблуждаюсь. Но почему «опять»? ))
Оно выше число за счет _неожиданного_ взлома одного из алгоритмов.
Примерно как запаска у парашюта — заметно хуже основного, но если ты потерял основной купол, и не смог сесть со скоростью 5м/с, то лучше сесть с 10м/с, пусть даже зашибешь мягкое место, чем влететь со скоростью в пару сотен метров и гарантированно разбиться. Так и здесь — при потере более стойкого хеша у нас останется менее стойкий, а так то компрометированно было бы всё.
Примерно как запаска у парашюта — заметно хуже основного, но если ты потерял основной купол, и не смог сесть со скоростью 5м/с, то лучше сесть с 10м/с, пусть даже зашибешь мягкое место, чем влететь со скоростью в пару сотен метров и гарантированно разбиться. Так и здесь — при потере более стойкого хеша у нас останется менее стойкий, а так то компрометированно было бы всё.
Сложности тут будут перемножаться, то есть необходимое число вычислений увеличится соответственно в квинтильон раз…
Эта особенность атак связанных с перебором и приводит к тому, что увеличение длины ключа повышает защиту от брутфорса (и связанных вещей) на много порядков, при более-менее линейном (в принципе полиномиальном, в зависимости от алгоритма) увеличении затрат на шифрование/хеширование, единственной проблемой может быть только железная поддержка только ключей определенной длины.
Эта особенность атак связанных с перебором и приводит к тому, что увеличение длины ключа повышает защиту от брутфорса (и связанных вещей) на много порядков, при более-менее линейном (в принципе полиномиальном, в зависимости от алгоритма) увеличении затрат на шифрование/хеширование, единственной проблемой может быть только железная поддержка только ключей определенной длины.
Практическая схема атак, связанных с поиском коллизий второго рода может быть следующей:
1. Есть легитимный электронный документ подписанный электронной подписью (например, платежное поручение).
2. Злоумышленник, вносит изменения в оригинальный документ изменения (например, подменяет реквизиты получателя).
3. Используя алгоритмы поиска коллизий, злоумышленник ищет такое дополнение в к модифицированному файлу, которое позволит сделать его хэш идентичным оригиналу.
4. Злоумышленник подменяет оригинальный документ модифицированным с таким же хэшом.
Так же следует понимать, что создание электронной подписи, в общем случае, это шифрование хэша документа на закрытом ключе подписанта, поэтому в модифицированном документе, электронная подпись будет валидной и соответствовать ЭП оригинального документа.
1. Есть легитимный электронный документ подписанный электронной подписью (например, платежное поручение).
2. Злоумышленник, вносит изменения в оригинальный документ изменения (например, подменяет реквизиты получателя).
3. Используя алгоритмы поиска коллизий, злоумышленник ищет такое дополнение в к модифицированному файлу, которое позволит сделать его хэш идентичным оригиналу.
4. Злоумышленник подменяет оригинальный документ модифицированным с таким же хэшом.
Так же следует понимать, что создание электронной подписи, в общем случае, это шифрование хэша документа на закрытом ключе подписанта, поэтому в модифицированном документе, электронная подпись будет валидной и соответствовать ЭП оригинального документа.
- Есть легитимный электронный документ подписанный электронной подписью (например, платежное поручение).
- Злоумышленник, вносит изменения в оригинальный документ изменения (например, подменяет реквизиты получателя).
- Используя алгоритмы поиска коллизий, злоумышленник ищет такое дополнение в к модифицированному файлу, которое позволит сделать его хэш идентичным оригиналу.
- Злоумышленник подменяет оригинальный документ модифицированным с таким же хэшом.
Ваш вариант — про коллизии первого рода (она же second preimage attack), т. е. при наличии H(M_1) = X найти такой M_2, что H(M_2) = X.
Если говорить про коллизии второго рода — то вектор такой: злоумышленник генерирует пару документов, один из которых подписывает атакуемый, а потом подменяет этот документ вторым из пары.
Так же следует понимать, что создание электронной подписи, в общем случае, это шифрование хэша документа на закрытом ключе подписанта, поэтому в модифицированном документе, электронная подпись будет валидной и соответствовать ЭП оригинального документа.
Шифрование и подпись — два разных процесса. Подпись не является шифрованием. В частном случае использования RSA для подписи оно технически неотличимо. В случае каких-нибудь DSA/ECDSA или EdDSA операции шифрования вообще нет.
Можно ли, имея эти два файла, сломать Git-репозиторий? (пусть даже на искусственном примере)
В некотором смысле можно. Выше постил ссылку на webkit'овский багтрекер: https://bugs.webkit.org/show_bug.cgi?id=168774#c23.
А если использовать конкатенацию двух хэшей SHA1+MD5? :)
Ну шо, понеслось! https://github.com/nneonneo/sha1collider
Sign up to leave a comment.
Первый способ генерации коллизий для SHA-1