Git
Информационная безопасность
Криптография
Комментарии 39
+2
Подписи это конечно хорошо, но по моему самое время подумать о ядовитых pull-request в git. Похоже коллизии могут повреждать репозиторий.
+2
не повреждать, а терять новый объект.
в целом, выходит безопасно — перезаписать с помощью коллизии что-то нельзя.
НЛО прилетело, и опубликовало эту надпись здесь
+2
> И опять же, как будто ничего кроме SHA не существует, хотя приличных хэш функций десятки.

Ну, вообще-то SHA — это аббревиатура Secure Hash Algorithm, то есть как раз «приличная хэш-фунция может быть признана SHA», а не наоборот, семейство SHA-функций входит во множество «приличных». Для этого её авторы должны попробовать доказать её криптографическую надежность, а ученые умы должны потыкать в неё своими инструментами, покачать убеленными сединами головами и либо одобрить, либо отклонить. Ну там всякие скорости, ресурсоемкости и прочие вещи всегда учитываются.
НЛО прилетело, и опубликовало эту надпись здесь
+9
> Вектор атаки здесь понятен: злоумышленник может подменить «хороший» файл своим экземпляров с закладкой, вредоносным макросом или загрузчиком трояна. И этот «плохой» файл будет иметь такой же хеш или цифровую подпись.

Нет. Тут генерируются два файла одновременно с одинаковым хэшем. Сгенерировать один файл по известному хэшу в разы сложнее!
+1
Относительно простой способ проверить не скомпрометирован ли файл — иметь как минимум два разных типа хэшей у одного объекта (к примеру, SHA-1 и SHA-256). Представляется чем-то невероятным генерацию коллизий одновременно по двум типам.
0
Генерация коллизий по двум типам хэшей ничем не отличается от генерации коллизий по одному хэшу (по сложности равному сумме двух предыдущих).
+1
Думаю, это ближе к примеру с Гитом. Чтоб не было случайных коллизий.
+1
Ситуация еще хуже. Сам только сегодня узнал.

Оказывается что, теоретически, конкатенация 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»
+1
конкатенация 2-х хэшей не лучше чем самый слабый из 2-х.

То есть например конкатенация CRC-32 и SHA-512 не лучше чем CRC-32?

+2
Здесь скорее всего имеется последовательное применение
SHA-512(CRC-32(text)) или CRC-32(SHA-512(text)), а не конкатенация.

Конкатенация с увеличением суммарной длины хэша улучшает надёжность.
0
Речь именно о конкатенации.
Но в моем посте есть ошибка. Должно быть: не лучше чем самый стойкий из 2-х
+2
Конкатенация не может быть хуже, чем один хеш. В принципе. Вы, скорее всего, путаете конкатенацию с композицией.
0
Да, извиняюсь… механическая ошибка. Правильно будет: не сильнее самого СТОЙКОГО из 2-х
0
а зачем использовать конкатенацию, если можно проводить валидацию по 2 хэшам? например MD5 и SHA-1. в этом случае вероятности нахождения коллизий для каждого из использованных алгоритмов перемножаются.
вероятность нахождения коллизии для SHA-1 равна 2^-80 (=8.3e-25) а для MD5 — 2^-40(=9.1e-13). тогда произведение вероятностей будет равно 7.5e-37.
0
Мы говорим об одинаковых вещах по разному.
— Рассчитать оба хэша; конкатенировать их; а потом сравнить.
— Рассчитать оба хэша; и сравнить отдельно.

Очень часто в криптографии интуитивные выводы не верны.
И это один из таких случаев.

вероятность нахождения коллизии для идеального 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)

0
Вероятность найти коллизию в SHA1 + MD5 где-то между 2^-50 (SHA1) и 2^-80+epsilon (теоретический максимум); но никак не 2^(-50-40) = 2^(-90)

И всё-таки это лучше, чем один только SHA1 (2^-50) или один только MD5 (2^-40), нет?
Очень часто в криптографии интуитивные выводы не верны.

Никакой интуиции, одна суровая логика.
0
да, вы правы. Это лучше чем каждый по отдельности.
На много ли? скорее всего нет. Почитайте документ который я упомянул: «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 будет медленнее чем один хороший хэш. Зачем тогда мучатся?
0
Плюс к этому, есть вероятность что sha1+md5 будет медленнее чем один хороший хэш. Зачем тогда мучатся?

С этим не поспоришь, низкая эффективность — очевидный недостаток. Однако я тут вижу некоторый компромисс. В «хорошем» может обнаружиться фатальная уязвимость, в этом случае два хэша дают какой-то запас надёжности и времени за не очень высокую цену.
0
После этого, добавляем (одинаковый) мусор в конец этих 2-х документов (почитайте про «Length extension attack»). Скорее всего, этот мусор будет незаметным в бинарном документе. Получаем другие 2 документа с одинаковым sha1, но с разным md5.

Тут у вас ошибка, по-моему. Если мусор добавили одинаковый, а документы изначально разные, то sha1 будет разный.
Корркетно было бы добавлять только к одному документу, сохраняя sha1 и подбирая при этом MD5, чтобы совпал со вторым.
Но в общем я согласен, что суммарная устойчивость может при определённых условиях оказаться не сильно выше, чем каждый хэш в отдельности.
0
Вы опять заблуждаетесь. По конструкции 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
0
Я думал, у sha1 состояние более, чем просто текущий хэш.
Согласен, заблуждаюсь. Но почему «опять»? ))
0
Эта главная (известная мне) причина почему 2 «итеративные» хэш функции не лучше самой стойкой из 2-х.
И почему на sha3 это правило не действует.
Кто его знает какие еще векторы атаки есть… о которых мне не известно но для криптографов очевидны.

Я погорячился сказав «опять» ))
0
Подумав немного… я понял что предложенный мной метод вообще-то не работает.

Почитайте предложенную мною статью: там правильный метод.

Вот и я положился на интуицию в криптографии… и она меня подвела.
0
Оно выше число за счет _неожиданного_ взлома одного из алгоритмов.
Примерно как запаска у парашюта — заметно хуже основного, но если ты потерял основной купол, и не смог сесть со скоростью 5м/с, то лучше сесть с 10м/с, пусть даже зашибешь мягкое место, чем влететь со скоростью в пару сотен метров и гарантированно разбиться. Так и здесь — при потере более стойкого хеша у нас останется менее стойкий, а так то компрометированно было бы всё.
0
Сложности тут будут перемножаться, то есть необходимое число вычислений увеличится соответственно в квинтильон раз…

Эта особенность атак связанных с перебором и приводит к тому, что увеличение длины ключа повышает защиту от брутфорса (и связанных вещей) на много порядков, при более-менее линейном (в принципе полиномиальном, в зависимости от алгоритма) увеличении затрат на шифрование/хеширование, единственной проблемой может быть только железная поддержка только ключей определенной длины.
0
Практическая схема атак, связанных с поиском коллизий второго рода может быть следующей:
1. Есть легитимный электронный документ подписанный электронной подписью (например, платежное поручение).
2. Злоумышленник, вносит изменения в оригинальный документ изменения (например, подменяет реквизиты получателя).
3. Используя алгоритмы поиска коллизий, злоумышленник ищет такое дополнение в к модифицированному файлу, которое позволит сделать его хэш идентичным оригиналу.
4. Злоумышленник подменяет оригинальный документ модифицированным с таким же хэшом.

Так же следует понимать, что создание электронной подписи, в общем случае, это шифрование хэша документа на закрытом ключе подписанта, поэтому в модифицированном документе, электронная подпись будет валидной и соответствовать ЭП оригинального документа.
-1
  1. Есть легитимный электронный документ подписанный электронной подписью (например, платежное поручение).
  2. Злоумышленник, вносит изменения в оригинальный документ изменения (например, подменяет реквизиты получателя).
  3. Используя алгоритмы поиска коллизий, злоумышленник ищет такое дополнение в к модифицированному файлу, которое позволит сделать его хэш идентичным оригиналу.
  4. Злоумышленник подменяет оригинальный документ модифицированным с таким же хэшом.

Ваш вариант — про коллизии первого рода (она же second preimage attack), т. е. при наличии H(M_1) = X найти такой M_2, что H(M_2) = X.


Если говорить про коллизии второго рода — то вектор такой: злоумышленник генерирует пару документов, один из которых подписывает атакуемый, а потом подменяет этот документ вторым из пары.


Так же следует понимать, что создание электронной подписи, в общем случае, это шифрование хэша документа на закрытом ключе подписанта, поэтому в модифицированном документе, электронная подпись будет валидной и соответствовать ЭП оригинального документа.

Шифрование и подпись — два разных процесса. Подпись не является шифрованием. В частном случае использования RSA для подписи оно технически неотличимо. В случае каких-нибудь DSA/ECDSA или EdDSA операции шифрования вообще нет.

0
Можно ли, имея эти два файла, сломать Git-репозиторий? (пусть даже на искусственном примере)
Только полноправные пользователи могут оставлять комментарии. , пожалуйста.