Забавляемся с хешами

[gabber2k]

вместо programme обычно пишут program, если это на английском написано

[JustLuckyGuy]

bed -> bad

[gabber2k]

ха ха — точно

[bogolt]

да да — мне тоже эта кроватная функция понравилась =)

[burdakovd]

Да у автора и с русским не очень:

«Вы скажите но что нам даст обладание такой парой сообщений, мало того что они маленькие(всего 128 байт), так еще в добавок и случайные, т.е. метод не позволяет для заданного сообщение подобрать другое с идентичным хешем»

Да, я понял, он всего лишь торопился.

[odiszapc]

Как эти Розентали уже достали. Ну что вам не имется?

[AlDev]

Хабр — не администрация N-ской области
habrahabr.ru/info/help/rules/

[odiszapc]

Сынок родной, увидел ошибку — напиши в личку, не надо исполнять на главной, ценность таких коментов равна нулю.

[AlDev]

Я Вам не сынок.
Про ценность — Как и ценность комментов про Розенталей.
Про личку — я и не писал про ошибку. Я лишь указал на правила хабра в ответ на Ваш бесценный коммент

[odiszapc]

заплачь еще

[cyberstyle]

Вы, видимо, в свое время эти самые уроки не посещали… А жаль=\

[odiszapc]

Это правильно, значит тема актуальна. И потерянная карма того стоит. Я все написал верно: я люблю своя язык, но увидел ошибку — напиши в личку, это не блог русского языка

[UrbanRider]

я люблю своя язык

Моя твоя не понимай…

Орда детектед :)

[Mezomish]

>Я все написал верно: я люблю своя язык...

Нет, вы написали это неверно. Верно будет «я люблю своя языка».

[sasha_gud]

Родной, ты запятую забыл.

[fleshy]

таки нет, если «сынок родной» ~ «родной сынок» — одно обращение. «сынок, родной, ...» — два обращения

[phillennium]

Запомните, что «не имется» пишется как «неймется», и они начнут доставать вас меньше.

[odiszapc]

Нет ты посмотри, еще один Розенталь. У вас сообщество?

[kekekeks]

Ага. Международное. Даже лозунг есть: «Grammatik macht frei!»

[EugeneDest]

Лучше уж — Grammatisch. Praktisch. Gut! )

[binariti]

Да, у нас тут сообщество носителей русского языка.

[Mezomish]

>Запомните, что «не имется» пишется как «неймется»

Точкофилы протестуют! Это слово пишется как «неймётся»!

[NeverWalkAloner]

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

[kanazirsky]

мозг хотел в bed :)

[AlexanderYastrebov]

оффтопик::хозяйке_на_заметку {
    отбивайте в коде операторы(=, ==, >> и т.д.) пробелами с обоих сторон
    отбивайте запятую пробелом справа (s2.erase(0, 64);)
    для склейки строк обратный слеш не нужен
}

[RedOctober]

Да какая блин разница…

[gabber2k]

впрынцэпе ныкакой

[Lockdog]

Такъ что же вам не нравитъся? =)

[gabber2k]

мне кажется писать programme не правильно

[dzzh]

American English always uses program
British English uses programme unless referring to computers
Australian English recommends program for official usage, but programme is still in common use

www.dailywritingtips.com/get-with-the-programme/

[justabaka]

А в IT, в свою очередь, в подавляющем большинстве случаев используется именно American English.

[znvPredatoR]

Та ну какая разница, ну нравится человеку так писать, а вы тут тред развели на два экрана. Топик, как вы могли заметить, вообще не об этом.

[dime]

Смотря кто пишет. Читал тут доку по RFB протоколу и удивлялся слову colour при том, что одно из слов на обложке про авторов — AT&T Labs. Сейчас только что поискал местонахождение компании _текущего_ автора этой доки, таки да, теперь UK. И цвета он аккуратно поправил :).

[kanazirsky]

правильно писать «аппликация»

[toxicdream]

Мицгол? :)

[Dark_MX]

Это аналогично с «резолюция»? :)

[RedOctober]

Я имел ввиду, какая разница что выводит программа? Некоторым обязательно надо что-то написать в топик, не важно что…

[bolk]

lingvo.yandex.ru/programme/с%20английского/

[gabber2k]

en.wiktionary.org/wiki/programme
UK: programme is used in all cases except for computer code, in which case program is generally used. Older sources may use programme for computer code.

т.е. даже в британском английском это уже не применяется.

[bolk]

Оксфордский словарь: www.oxforddictionaries.com/view/entry/m_en_gb0665170;jsessionid=09EEB470BCE659BEE99758B7AAC1E7FC#m_en_gb0665170

4 (program)a series of coded software instructions to control the operation of a computer or other machine.

[gabber2k]

Я думаю то что ваша ссылка подтверждает мою точку зрения.

Spelling help
Remember that programme ends with — amme, unless it is used in computing senses, when program is correct. In American English, it is always spelled program.

[bolk]

Похоже на то, спасибо. Поставлю вам плюс в благодарность.

[gabber2k]

спасибо

[Shirixae]

Походу, немецкий.

[wzrd]

Отличная статья, читал с интересом.

[eforce]

«Ловкость рук и никакого мошенничества!»

Спасибо, с удовольствием прочитал статью.

[DeadFine]

Охренеть.

[Anexroid]

Эх, тоже самое бы, но на примере действительно Evil кода)))

[StopKran]

А ещё такие программы можно написать например проверяя название исполняемого файла самой себя же.
И да, спасибо за интересную статью.

[ooprizrakoo]

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

В соц.сетях, рапидшаре, или торрент-трекерах могут выкладываться файлы с измененным «подставным» хэшем… И при «зачистке» подставных файлов с плохим контентом будут потерты и «хорошие» файлы, идентичные по хэшу и размеру. Ну и так далее.

Интересно, какие теперь можно использовать способы для проверки идентичности файлов? Высчитывать хэш рандомного куска файла небольшого размера, и сверять его с таким же куском другого?..

[alex_www]

Вроде уже писали что «правообладатели» так поступают с торрентами.

[alklim]

Нет не поступают! В торрентах для идентификации используется SHA1 для которого такую атаку еще не реализовали.

Поверьте, если бы она была реализована, то каждый фильм который бы вы скачивали с торрентов, был бы битый и не проигрывался бы.

[bolk]

Хеши вообще нельзя использовать для проверки идентичности файлов. И никогда нельзя было.

Если хеши разные, то файлы разные, если одинаковые, то это ни о чём не говорит.

[bolk]

Это какой-то аргумент что ли? Мало ли где это используется. Нельзя так делать.

[ooprizrakoo]

У нас в компании при хранении файлов используется хэш+размер файла для их идентичности — чтоб 1 файл 50000 раз не копировать каждому пользователю, физически в единственном виде (не считая бэкапов) существует. Правда, у нас наверное хэш более умный :)

[bolk]

Это сильно ситуацию не влияет :)

[Sap_ru]

Зато как будет обидно, если коллизия всё же произойдёт? И заметят это совсем не сразу. И вообще, хрен поймёшь, что произошло.

[salium]

Говорит. Вот ровно о том и говорит, что файлы НЕ [точно не идентичны]. Мало того, все-таки говорит, что идентичны, но с точностью до почти наверное (в строгом смысле этого выражения). Наличие одновременно двух хэшей логически ничего не меняет, но существенно уменьшает вероятность строгой неидентичности.

Это, возможно, уязвимо (существование строго необратимых хэш-функций, несколько я понимаю, не доказано), но в значительном числе случаев «достаточно» для бытового использования. Вы же, обещая приехать в гости, не говорите «если только мне по дороге не упадет на голову кирпич, рояль, топор, сундук и далее еще бесконечное множество предметов». Но из этого вовсе не следует, что вам нельзя верить.

[bolk]

Вы какую-то странную вещь говорите. Какая ещё бытовое использование? Что это? Хешем хлеб резать?

Представьте, что операция сравнения в Си выдавала бы полную чушь один раз на десять миллионов? Это «бытовой точности» нам хватило бы, чтобы программировать в Си?

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

И вот, через полгода, ко мне приходит и говорит, что один файл не заливается, утверждается, что он есть, но его точно нет.

И что мне делать, с вашим «бытовым использованием»? Рассказывать заказчику о хешах? Да он меня мудаком назовёт и будет прав.

[salium]

>Вы какую-то странную вещь говорите. Какая ещё бытовое использование? Что это?

Скачиваем файл. Считаем md5 и sha. Сравниваем с опубликованными. Если совпадает, значит перескачитвать не нужно (почти наверное). Если не совпадает — нужно точно перескачать. Это и есть бытовое использование.

Ровно то же самое происходит в голове у вашего контрагента, когда вы обещаете ему приехать в гости.

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

Любопытно, и сколько же?

[bolk]

Ох. Такое ощущение, что вы либо совсем не в теме, либо троллите. Я не хочу продолжать диалог.

[salium]

Ну, хамить — дело несложное. А в чем мои рассуждения неверны, я так и не понял.

Смысл хеша ровно в том, чтобы относительно быстро, дешево и сердито дать ответ с точностью до почти наверное.

Ваш пример с хостингом — я также не понимаю, чем вам там хэши мешают. Ну даже совпали они (скажем, оба: и md5, и sha1, и при этом размер у файлов одинаковый) — и чего, жизнь кончилась? Взяли, посчитали для сегмента случайной длины со случайным смещением. Опять совпали? — и еще раз совпали? — «ну тогда я не знаю» © — дальше, если в этом есть коммерческий (или какой там) смысл, побайтное сравнение или что там вам больше нравится.

Вы знаете способ эффективнее? Расскажите, я буду благодарен.

[burdakovd]

Давайте посчитаем, сколько коллизий будет (независимо от размера файлов), удивитесь.

Общая мощность пространства значений пары хэшей md5+sha1: 288 бит, а значит есть 2^288 возможных значений (на самом деле меньше за счёт неидеальности хэш-функций, но пока пропустим этот момент)
Допустим у вас на хостинге 2^32 файлов (миллиард).
Вероятность того, что случайно произойдёт хоть одна коллизия примерно 2^288 / 2^64 = 2^224
Это 3.7*10^(-68)

Оценка весьма грубая, но всё же.

[bolk]

> Общая мощность пространства значений пары хэшей md5+sha1: 288 бит, а значит есть 2^288 возможных значений (на самом деле меньше за счёт неидеальности хэш-функций, но пока пропустим этот момент)
Во-первых, я не понял почему мы опускаем этот момент. Как относятся распределяются значения md5 + sha1 на одном и том же файле мы не знаем. Они могут давать значения куда у́же, чем 288 бит.

Во-вторых, я не понял почему мы игнорируем длину файла. Я специально привёл в пример видеохостинг, то есть файлы примерно от 800МБ до 4ГБ. Можно ещё ухудшить ситуацию, если взять видеохостинг каких-то определёных рипов, нампример, только HDRip.

[burdakovd]

> Как относятся распределяются значения md5 + sha1 на одном и том же файле мы не знаем. Они могут давать значения куда у́же, чем 288 бит.
Да, действительно пространство значений меньше чем 288 бит. Мне кажется, что не намного, но аргументировать не смогу — глубоко не копал.
Другой аргумент в их пользу: до сих пор не было найдено (сгенерировано) ни одной пары документов с одновременно совпадающими md5 и sha1. (При чём сгенерировать пару проще, чем получить коллизию случайно)

А длина файла? Разве она вообще как-то влияет на шанс коллизии? Мне кажется тут имеет значение только количество файлов, но не их размер.

[bolk]

> Да, действительно пространство значений меньше чем 288 бит. Мне кажется, что не намного, но аргументировать не смогу — глубоко не копал.

Меня, как математика сильно смущает, что в нашем споре куча переменных, влияющих на порядок вычислений. А ещё — куча зрителей, ничего в этом не понимающих.

> А длина файла? Разве она вообще как-то влияет на шанс коллизии? Мне кажется тут имеет значение только количество файлов, но не их размер.

Ну, например, какой может быть шанс коллизии на файле в один байт?

[burdakovd]

> Меня, как математика сильно смущает, что в нашем споре куча переменных, влияющих на порядок вычислений. А ещё — куча зрителей, ничего в этом не понимающих.

Переменных да, много. Но в том-то и штука, что несмотря на то, что хэш вещь непредсказуемая, и его значение нетривиальным образом зависит от хэшируемых данных — основные его свойства сохраняются. А основные свойства — это как раз то, что хотя коллизии и возможны, но их вероятность (даже в случае злонамеренного поиска) настолько мала, что в реальном мире (тем более если взять два хэш-алгоритма, чтобы предостеречься от взлома какого-то одного) можно считать что коллизий нет. Об этом salium вам выше и пытался сказать.
А зрители — ну неужели прекращать поиски истины из-за них?)

> Ну, например, какой может быть шанс коллизии на файле в один байт?
Напомню, коллизия — это равенство значений хеш-функции на двух различных файлах.
То есть «на файле» о коллизии речи быть не может.

> Можно ещё ухудшить ситуацию, если взять видеохостинг каких-то определёных рипов, нампример, только HDRip
Формат видео-то тут причём? Разве что заголовки будут немного совпадать, но хэши двух разных HDRip фильмов не будут иметь ничего общего, тем более что есть лавинный эффект.

[drakmail]

Просветите же нас, как влияет длина файла на хеш этого файла?

[bolk]

О, сарказм невежды!

[drakmail]

Так просветите, действительно интересно )

[Dark_MX]

Ну наверное имелся ввиду не хеш файла а «хешики» кусков или точнее будет даже «кусочков файла».

Конечно то что в файле есть коллизии не значит что полный хеш будет идентичен с другим файлом в котором так же есть коллизии. Ой как не значит :)

[MaximKat]

Это все конечно очень правильно, но хотелось бы услышать ваш метод для проверки идентичности видеофайлов.

[bolk]

О! Вы меня нанимаете? :)

[MaximKat]

О! Вы просто болтаете? :)

[bolk]

Нет, просто потерял интерес к теме.

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

[vitstr]

>Интересно, какие теперь можно использовать способы для проверки идентичности файлов?
SHA-1, например. в приведенных в статье примерах совпадает только MD5, a CRC32 и SHA-1 отличаются.

[mikenerevarin]

Я сталкивался с ситуацией, когда crc32 выдавал одинаковый хэш. Не с файлами, но всё же.

[segoon]

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

[printf]

Поэтому нужно сравнивать сразу несколько хешей, SHA-1 и MD5, например. Подобрать данные, дающие коллизию по нескольким разным алгоритмам, на несколько порядков сложнее.

[bogolt]

к счастью свет не сошелся клином на md5
Есть sha1, sha256,…

[burdakovd]

Не забывайте, что тут можно найти пару блоков, для которых будет коллизия.

То есть если уже есть «хороший» файл, то создать «плохой» файл с тем же хэшем гораздо сложнее.

Атака дней рождения же.

[MaximKat]

Для этого используют несколько разных хэш-функций одновременно.

[tassadar_ha]

А ведь хеш-функции активно применяются и в сетевых технлогиях для аутентификации сторон при всяческих PPP, например.

Задумался… Большое спасибо за статью!

[drakmail]

Openvpn по умолчанию использует TLS и SHA1.

[tassadar_ha]

Не, я имел в виду именно PPP. Там два вида аутентификации: PAP, который почти не используется, и CHAP. CHAP использует MD5.

[drakmail]

А как же 128-битный MSCHAPv2?

[tassadar_ha]

Он не всеми железками подджерживается.

[TheShock]

В вашей статье не хватает вывода, ответа на вопрос: «Так что теперь делать?»

[Shirixae]

Использовать MD6 или SHA1

[TheShock]

И виной тому служит следующая особенность работы любой хеш функции: Хеш функция по своей природе итеративна.

Они точно не обладают теми же недостатками, но с другими условиями ?; )

[Shirixae]

И для них нужно изобретать свой алгоритм поиска коллизий. А MD6 ещё и сильно сложнее пятой версии.

[lashtal]

А теперь то же самое, но проще: проверяем имя исполняемого файла и простым условием:
— если good.exe -> вывод good, если evil.exe -> вывод 'bad code'. Хэш ведь считается без учета имени файла :)

[q0p]

ну то есть вы всерьёз считаете, что человек, сумевший так хорошо замаскировать свой зловред под нечто безобидное — не догадается и название файла выставить идентичное?

[burdakovd]

Речь не о маскировке зловреда, а о том, что в данном примере программа могла проверять argv[0] и выводить разные сообщения от имени файла.

При этом md5, sha1, crc, да и вообще файлы побитово совпадали, а результат при запуске разный.

Это совсем по теме статьи, но забавная идея.

[skobkin]

Был бы хороший хабраприкол. Сколько было бы негодования в комментах, пока кто-нибудь не догадался бы переименовать.

[dime]

Эта забавная идея давно и успешно, и, главное, с пользой для дела, используется в униксах. Где может быть один бинарник (или скрипт) и кучка разных симлинков на него. В зависимости от имени единственный бинарник выполняет разные операции (из схожей серии).
А, во, простейший пример:
lrwxrwxrwx 1 root root 5 Дек 4 02:05 bunzip2 -> bzip2
lrwxrwxrwx 1 root root 5 Дек 4 02:05 bzcat -> bzip2
-rwxr-xr-x 1 root root 35224 Дек 4 02:05 bzip2

[remal]

Стоит добавить ссылку на эту статью: habrahabr.ru/blogs/infosecurity/50434/

[gjf]

А как это будет работать на реальный примерах с размером кода хотя бы на порядок больше?
Кстати, заподозрить неладное можно уже при открытии архива:


что в принципе неудивительно — код-то разный.

Ну и кроме того, как правильно сказали — есть другие хеши:
evil.exe:
CRC32: B5917900
MD5: ECEA96A6FEA9A1744ADCC9802AB7590D
SHA-1: BE3AEE5D2A99BC88233E331A653D14CA3EB722F8

good.exe:
CRC32: A71D16A9
MD5: ECEA96A6FEA9A1744ADCC9802AB7590D
SHA-1: BE1DF26F1245278611739F49F610DCFF677FBEC2

[ValdikSS]

Хе-хе, а есть еще такая же штука, но для crc32, только она много проще. Я когда программы правил, и у них сверка контрольных сумм шла, а мне было лень ее искать, я брал и правил crc32. Там нужно править было всего 4 байта.

[gjf]

А что там вспоминать-то ;)

[mikhanoid]

if(argv[0] == 'evil.exe') (be evil); ne?

[segoon]

s/argv[0] == 'evil.exe'/strcmp(argv[0], «evil.exe») == 0/, я, увидя заметку в RSS, сначала подумал об этом же :)

[burdakovd]

было

[LightServer]

Evil evil код запихан в кровать… )

[InTRUEdeR]

Немного не в тему: а нет рекомендаций каких-нибудь в виде «поменяй пару байтиков и получится 'красивая' контрольная сумма»? Просто интересно, такое еще не придумывали?

[NeverWalkAloner]

Навряд ли, то о чем вы говорите это скорее похоже на нахождение прообраза для заданного хеша. А такая задача на сегодняшний день пока решается только методом грубой силой.

[Ctacok]

Почему не «gud»? :)

[NeverWalkAloner]

Ха, не знаю, наверное, просто еще все не настолько плохо:)