Насколько сложно «взломать» корректику (CoRreCtica)?

Дело в том, что полной коллизии MD5 и SHA-1 не надо, используется всего первые два (хотя можно увеличить, но имя файла удлинняет) символа каждой из них, но CRC32 - хранится и передаётся полностью. Т.е. потенциальному злоумышленнику нужно подогнать CRC32 полностью, при этом ОДНОВРЕМЕННО ЧАСТИЧНО MD5 и SHA-1.

Добавляем к файлу 8 байт : первые 4 перебираем хаотично. Следующие 4 вычисляем так чтобы CRC32 совпал (это алгоритмически и не полный перебор). Вычисляем от результата MD5 и SHA-1. В среднем через 2^15 попыток совпадут первые байты и MD5 и SHA-1.

Лучше возьмите 3 байта от 2^20 повторений MD5 и 3 байта от 2^20 повторений SHA-1. Итого подпись будет 6-байтной и достаточно стойкой.

3 символа сложнее проверять на глазок, чем 2... Просто рассчёт на то, что вычисление хэшей - задачка требующая времени сама по себе, да и криптографические хэши (я нуб, могу термины путать и т.д.) для того и делаются, чтобы быть относительно случайными. А если добавить 2 байта sha3-512, например..? :D

Современная скорость перебора хешей на одном процессоре порядка 2^27/сек. Давайте зададимся защитным характеристиками в 100 процессоров и 1 год. Тогда стойкость контрольной суммы должна быть не меньше 48 бит (12 шестнадцатиричных символов), каким бы современным хеш-алгоритмом Вы ее не создавали. Немного снизить эту цифру можно используя замедление вычислений хеш за счет повторных взятий хеш-функции от результата (подробнее - bcrypt, PBKDF2, scrypt)

Андрей: хэши бывают с разной степенью сложности, да и от размера файла зависит. Попробуйте хотя бы MD5 от 4.7 dvd подсчитать, или любого другого крупного файла. А если добавить ещё и sha1, и всякие сложные хэши? Скорость будет падать пропорционально сложности какого-либо хэша*размер файла (я могу путать формулировки, но если гоню, поправьте). А если использовать «сложные» хэши, хотя бы частично (тот же sha3-512), то перебирать будет затруднительно. Хотя, конечно, можно надеяться на «случайное» совпадение, но чем больше разных контрольныых сумм используется, тем меньше вероятность случайности.

От размера файла не зависит. Хеши - алгоритмы однопроходные, при атаке на усеченный хеш полным перебором подбирать будут последний блок, а внутреннее состояние хеша на момент окончания предпоследнего блока будет всегда одинаковым - зачем его снова пересчитывать. Так что без разницы хоть в 1 кб файл хоть в 4 Гб.

Андрей: ...спасибо за разъяснение, хотя я и не понял.
А если поставить вопрос легче - есть ли ещё какие-нибудь методы, позволяющие проверить корректность (оригинальность) файла в несколько кликов мыши, без лишних файлов с контрольными суммами (которые тоже, кстати, можно подделать, не знаем ведь, что там).

Нет. Еще раз:
1. Имя файла не задействуется в чексумме - только содержимое
2. Ничто не запрещает поменять имя файла и поставить ту чексумму, которую надо:)

Пользователю в любом случае необходимо скачать вашу софтину, самому у себя локально получить его чексумму, зайти к вам на сайт и проверить её - байтик к байтику.

Но ваша аудитория не будет же этого делать.

brutal_lobster: кажется я один коммент не отправил). Просто сама идея корректики - это лёгкость проверки со стороны пользователя и сложность со стороны злоумышленника. Т.е. если для ориентира используется хотя бы пара байт какой-либо хэш-суммы, злоумышленнику надо будет подбирать самостоятельно — а это ещё время на вычисление хэшсуммы. Я абсолютный нуб в ИБ, но вроде прикол криптографических хэшей - это устойчивость к подбору, и тут встаёт вопрос, насколько по двум байтам можно судить о 160-битном ключе. Использовать хотя бы 3 байта - это уже не так удобно для примерки на глаз. А что, если использовать ещё 2 байта, скажем от SHA3-512 :D? Это вынудит «злоумышленника» каждый раз вычислять все 4 хэша, а это как никак процессорное время.

Так не понятно, в чем простота вашего способа для пользователя?
Злоумышленнику так только наоборот проще обмануть подменой имени файла и версии программы, чем париться с поиском коллизий, даже для crc32. Нужно же трезво оценивать риски)

Охота простоты и секьюрности - покупайте сертификат и подписывайте код. Но даже это не остановит от запуска Portable MegaPuper Enterprise Edition.

По поводу крипты:
Ваш способ очень сильно снижает устойчивость хэшей к атакам на коллизии. Смысл коллизий в том, что два одинаковых текста дают один и тот же хэш. В вашем случае коллизия осуществиться при совпадении первых нескольких байт. Очевидно, что таких сильно текстов больше - соответственно вариантов перебора - сильно меньше )

→Так не понятно, в чем простота вашего способа для пользователя?
Хорошо, пусть пользователь будет не совсем обычный, иметь на машинке плагин HashTab, чтобы контрольные суммы посмотреть можно было всего лишь в свойстве файла. :) Тогда сверить имя файла с хэшами будет достаточно просто - первые 2 символа мд5 и ща1, ну и визуально црц32 проверить. В противном случае. Если же кто-то будет менять имя, то знающим проверочные данные (сводится к 2+2+8 символам, разделёнными точками - запомнить/записать от руки реально) людям чтобы отличить фейк достаточно просто взглянуть на имя файла. И по поводу ухудшения безопасностей каждого хэша - это всё понятно, что каждый хэш по отдельности проигрывает, но подразумевается, что в совокупности даже использование нескольких байт из разных хэшей в СОВОКУПНОСТИ даст ОТНОСИТЕЛЬНО хорошую защищённость.

Dreamject:
Используйте лучшие практики - публикуйте хэши и публичные ключи у себя на сайте.

Да не нужно это даже не обычному пользователю.
Если человеку важно соответствие и безопасность - он сможет прочитать инструкцию и проверить нормальный sha + md5.
А если там домохозяйка, которой все равно - то и ваш способ собственно вызовет недоумение полное. Какие хэши, какое визуальное сравнение crc, о чем вы..

Также как и не нужно это любому злоумышленнику. Ну не будут заморачиваться с подбором коллизий:) Смысла нет - не выгодно это. Проще добавить слово Portable Edition..

Еще раз по поводу крипты - не даст ваш вариант относительно хорошую защищенность. Абсолютно не важно, что вы используете разные хэши. Математически - вы просто создаете новую хэш-функцию в виде композиции готовых.
Да, ваша функция считается в два раза медленнее чем sha. Но, вероятность коллизии на порядки больше чем в sha.
Не нужно лезть в крипту и пытаться придумывать свои хитрые новые штуки. Это слишком чувствительная и сложная область :)

brutal_lobster: Да не нужно это даже не обычному пользователю.
В том и дело... Просто есть предположение, что проверка хэшей - это очень неблагородный , муторный, неудобный процесс. Я не очень умный, и подхожу со стороны «юзабилити». Теоретически, корректикой можно защитить что угодно - текстовый документ, картинку (чтоб не отфотошопили), что угодно, причём без лишних плясок и без десятков символов. Есть же алгоритм Луна, который вычисляется в уме, подделать можно, но хотя бы немного подумать надо. Тут даже не уме вычисляется, а на глазок примеряется.
Но я вот что-то не понимаю... Почему говорят, что перебор будет идти очень быстро? Я понимаю, что даже в примитивном случае (md5, sha-1, crc32 - это самые популярных хэши, но если добавить sha3-512...) , когда стойкость обеспечивается 6 байтами), метода подбора нужно КАЖДЫЙ раз пересчитывать хэш (говорят же, что даже если бит изменить, то хэш перестроится)... Но если реально нет необходимости пересчитывать хэш каждый раз при подборе этих 6 байт, то ясное дело, что способ годен разве для блондинок. Но чувство, что либо мне не всю правду говорят, либо не понимают (не в обиду сказано)

Dreamject:
Удобный процесс - подпись кода.
Все правильно - при изменении исходного текста даже на 1 бит - нужно пересчитывать хэш.
Процесс будет идти быстро из-за того, что вы уменьшаете необходимое (в среднем) кол-во попыток.

brutal_lobster:
→Процесс будет идти быстро из-за того,
Не совсем. Тут всё наоборот, так как CoRreCtica основана на crc32, использование ХОТЯ БЫ одного хэша (даже одного символа, но 2 понадёжнее) замедляет перебор ОТНОСИТЕЛЬНО crc32. То есть, идентификация, причём полная, crc32 (но в принципе можно что угодно использовать), всё остальное - это костыли К crc32, их смысл - в замедлении скорости перебора, плюс какая-никакая-безопасность. Я думаю, что математически можно доказать зависимость вероятности случайного совпадения при прибавленнии хотя бы частички ещё одного хэша.

Dreamject: Вы меня окончательно потеряли :)
Очевидно, что ваш вариант с 6 байтами немного безопаснее, чем crc32 с 4 байтами %) Но он все равно на порядки хуже, чем sha-1 с 20 байтами)

brutal_lobster: мой вариант для проверки «на глазок», чтобы даже не очень терпеливая и умная блондинка смогла проверить красивыми глазками 12 символов (а ещё с разделителями), сверяясь с именем файла, а не с какими-то чуждыми, большими и странными и несомненно лишними *.md5, *.sha.
С другой стороны, если «школохакер» знает как автоматически подогнать коллизию для md1, crc32, то ещё и хотя бы часть sha-1 его должна припугнуть :D.
Да и автоматизировать процесс очень просто
i5.imageban.ru/out/2014/11/23/c20f58267d3b7d8aa318...

brutal_lobster: типа такого ) www.youtube.com/watch?v=EcT4FOz0S48