NeverWalkAloner Feb 4 2011 at 01:13

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

5 min

89K

Information Security*

+244

123

Comments 123

gabber2k Feb 4 2011 at 01:38

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

JustLuckyGuy Feb 4 2011 at 01:40

bed -> bad

gabber2k Feb 4 2011 at 01:41

ха ха — точно

bogolt Feb 4 2011 at 02:14

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

burdakovd Feb 4 2011 at 02:59

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

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

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

odiszapc Feb 4 2011 at 04:01

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

AlDev Feb 4 2011 at 06:14

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

odiszapc Feb 4 2011 at 06:27

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

AlDev Feb 4 2011 at 07:09

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

odiszapc Feb 4 2011 at 07:54

заплачь еще

UFO just landed and posted this here

cyberstyle Feb 4 2011 at 11:32

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

UFO just landed and posted this here

odiszapc Feb 4 2011 at 11:43

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

UrbanRider Feb 4 2011 at 14:27

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

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

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

Mezomish Feb 4 2011 at 19:12

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

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

sasha_gud Feb 4 2011 at 10:28

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

fleshy Feb 4 2011 at 11:13

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

phillennium Feb 4 2011 at 07:40

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

odiszapc Feb 4 2011 at 08:06

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

kekekeks Feb 4 2011 at 09:01

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

EugeneDest Feb 4 2011 at 21:46

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

binariti Feb 4 2011 at 09:45

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

Mezomish Feb 4 2011 at 19:13

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

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

NeverWalkAloner Feb 4 2011 at 05:25

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

kanazirsky Feb 4 2011 at 06:56

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

AlexanderYastrebov Feb 4 2011 at 14:21

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

RedOctober Feb 4 2011 at 01:41

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

gabber2k Feb 4 2011 at 01:43

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

Lockdog Feb 4 2011 at 01:50

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

gabber2k Feb 4 2011 at 01:56

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

dzzh Feb 4 2011 at 02:12

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 Feb 4 2011 at 02:59

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

znvPredatoR Feb 4 2011 at 03:24

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

dime Feb 4 2011 at 10:44

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

kanazirsky Feb 4 2011 at 07:02

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

toxicdream Feb 4 2011 at 11:37

Мицгол? :)

Dark_MX Feb 6 2011 at 07:08

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

RedOctober Feb 4 2011 at 08:29

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

bolk Feb 4 2011 at 01:49

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

gabber2k Feb 4 2011 at 01:56

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 Feb 4 2011 at 02:02

Оксфордский словарь: 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 Feb 4 2011 at 02:05

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

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 Feb 4 2011 at 02:09

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

gabber2k Feb 4 2011 at 02:15

спасибо

Shirixae Feb 4 2011 at 02:30

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

UFO just landed and posted this here

wzrd Feb 4 2011 at 01:39

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

eforce Feb 4 2011 at 01:39

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

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

DeadFine Feb 4 2011 at 01:41

Охренеть.

UFO just landed and posted this here

Anexroid Feb 4 2011 at 01:51

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

StopKran Feb 4 2011 at 01:59

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

ooprizrakoo Feb 4 2011 at 02:03

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

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

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

alex_www Feb 4 2011 at 02:07

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

alklim Feb 4 2011 at 08:28

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

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

bolk Feb 4 2011 at 02:11

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

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

UFO just landed and posted this here

bolk Feb 4 2011 at 10:08

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

ooprizrakoo Feb 4 2011 at 12:46

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

bolk Feb 4 2011 at 14:01

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

Sap_ru Feb 4 2011 at 13:03

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

UFO just landed and posted this here

salium Feb 4 2011 at 12:04

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

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

bolk Feb 4 2011 at 12:42

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

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

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

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

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

salium Feb 4 2011 at 13:29

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

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

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

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

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

bolk Feb 4 2011 at 14:02

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

salium Feb 6 2011 at 12:58

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

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

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

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

burdakovd Feb 4 2011 at 15:35

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

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

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

bolk Feb 4 2011 at 16:25

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

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

burdakovd Feb 4 2011 at 16:32

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

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

bolk Feb 5 2011 at 00:35

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

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

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

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

burdakovd Feb 5 2011 at 01:09

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

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

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

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

drakmail Feb 4 2011 at 23:51

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

bolk Feb 5 2011 at 00:32

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

drakmail Feb 5 2011 at 03:03

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

UFO just landed and posted this here

Dark_MX Feb 6 2011 at 07:21

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

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

MaximKat Feb 5 2011 at 01:13

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

bolk Feb 5 2011 at 10:47

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

MaximKat Feb 5 2011 at 10:49

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

bolk Feb 5 2011 at 11:38

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

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

vitstr Feb 4 2011 at 02:14

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

mikenerevarin Feb 4 2011 at 03:25

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

segoon Feb 4 2011 at 11:51

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

UFO just landed and posted this here

printf Feb 4 2011 at 04:30

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

UFO just landed and posted this here

bogolt Feb 4 2011 at 02:14

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

mktums Feb 4 2011 at 10:46

Есть Whirpool еще, по которому я так и не увидел ни одной годной статьи на Хабре. Если кто сможет дать линки — буду благодарен.

UFO just landed and posted this here

burdakovd Feb 4 2011 at 03:06

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

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

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

MaximKat Feb 4 2011 at 03:21

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

tassadar_ha Feb 4 2011 at 02:05

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

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

drakmail Feb 4 2011 at 23:53

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

tassadar_ha Feb 4 2011 at 23:57

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

drakmail Feb 5 2011 at 12:55

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

tassadar_ha Feb 5 2011 at 13:05

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

TheShock Feb 4 2011 at 02:15

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

Shirixae Feb 4 2011 at 02:31

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

TheShock Feb 4 2011 at 02:33

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

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

Shirixae Feb 4 2011 at 02:52

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

UFO just landed and posted this here

lashtal Feb 4 2011 at 03:06

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

q0p Feb 4 2011 at 05:02

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

burdakovd Feb 4 2011 at 07:08

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

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

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

skobkin Feb 4 2011 at 15:08

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

dime Feb 4 2011 at 16:24

Эта забавная идея давно и успешно, и, главное, с пользой для дела, используется в униксах. Где может быть один бинарник (или скрипт) и кучка разных симлинков на него. В зависимости от имени единственный бинарник выполняет разные операции (из схожей серии).
А, во, простейший пример:
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 Feb 4 2011 at 03:40

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

gjf Feb 4 2011 at 03:53

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

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

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

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

ValdikSS Feb 4 2011 at 07:23

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

gjf Feb 4 2011 at 12:32

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

mikhanoid Feb 4 2011 at 07:56

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

segoon Feb 4 2011 at 11:54

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

burdakovd Feb 4 2011 at 15:40

было

LightServer Feb 4 2011 at 09:45

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

InTRUEdeR Feb 4 2011 at 14:11

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

NeverWalkAloner Feb 4 2011 at 14:47

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

UFO just landed and posted this here

Ctacok Feb 4 2011 at 14:53

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

NeverWalkAloner Feb 4 2011 at 14:56

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