что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

:-) Собственно, там самое интересное это то, что это уже не брутфорс. А для хэш-функции, с точки зрения математики, это уже broken. А практически пока ещё рано паниковать, конечно :-).

Lego_12239 (24.03.2009 2:44:15)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> это уже не брутфорс

вспомнился вежливый лось из анекдота

dilmah (24.03.2009 9:55:32)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> А для хэш-функции, с точки зрения математики, это уже broken

А, с точки зрения математики... тогда конечно. То, что о нахождении реальной коллизии за 4 года так и не сообщалось, с точки зрения математики несущественно, очевидно же.

Так что у меня вопрос: как вы относитесь к тому, что крыши домов не укрпеляют против попадания метеоритов?

tailgunner (24.03.2009 12:45:49)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Линус и ко впаривают некорректный код. Они используют неинъективную функцию там, где требуется инъективная.

dilmah (24.03.2009 12:50:13)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Они используют неинъективную функцию там, где требуется инъективная.

А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

tailgunner (24.03.2009 12:54:15)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

:-) Ну, так-то оно конечно так. Но когда-то и про MD5 думали, что, мол, долго ещё до реально-найденных коллизий. А вон оно как вышло. Мощности компьютеров растут очень быстро. Придёт время... :-)
А вот насчёт метеоритов я более-менее спокоен (насчёт sha-1, кстати, тоже :-) ). По крайней мере, сущестуют наблюдатели небесных тел, которые мне сообщат когда надо из дому бежать :-). Не думаю, что сколько-нибудь разрушительный метеорит проскользнёт незамеченным :-). А бабки потом с государства будем трясти, как потерпевшие от природных катаклизмов. Хм... интересно, а страховка от этого существует :-)?

Lego_12239 (24.03.2009 12:59:08)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Но когда-то и про MD5 думали, что, мол, долго ещё до реально-найденных коллизий.

IIRC, коллизий MD5 "in the wild" найдено не было - все были подобраны специально. И в любом случае, SHA1 малость посильнее будет :)

Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

> По крайней мере, сущестуют наблюдатели небесных тел, которые мне сообщат когда надо из дому бежать :-). Не думаю, что сколько-нибудь разрушительный метеорит проскользнёт незамеченным :-)

Ненене, они следят только за крупными метеоритами, от которых всемкапец. А мелкие, которые пробивают крыши (есть случаи, ага) - это ответственность строителей :D

tailgunner (24.03.2009 13:03:57)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

не волнует

dilmah (24.03.2009 13:06:55)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

>> А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

> не волнует

Необнаруживаемые баги в железе - не волнуют, а в софте - волнуют? "Где логика?" (c) анекдот

%)

tailgunner (24.03.2009 13:09:40)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Впрочем, здравое design decision (его слямзили у Monotone и OpenCM, кстати) не отменяет факта, что Git угребищен :)

tailgunner (24.03.2009 13:11:04)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

А что не в этом мире не угрёбищно :-)?

Lego_12239 (24.03.2009 13:32:15)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

я выбираю RCS, пока остановился на darcs. Видно, что разумный человек делает, не то что чухонский гопник Линус и его гойманда.

dilmah (25.03.2009 13:15:46)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

>> Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

> я выбираю RCS, пока остановился на darcs

Дело твое, но даже хаскеляторы ушли с него на Git. DARCS слишком революционная система, неизвестно, доведут ли ее до ума вообще. IIRC, в DARCS 2.0 используется такое же хранилище, как в Git, со всеми его проблемами :D

ИМХО, если не вестись на пиар, то из DVCS нужно выбирать либо Mercurial, либо Bzr. Но Bzr тормоз.

tailgunner (25.03.2009 14:03:18)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Дык все что связано с хэшами - подвержено ненулевой вероятности коллизии. Теория множеств мать ее итить.

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

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

eXOR (26.03.2009 7:26:56)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Ну случится это один раз - удалят этот файл из репозитория и заново зальют. И хэш не повторится.

O_o с чего бы ему не повториться?

tailgunner (26.03.2009 12:46:22)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> O_o с чего бы ему не повториться?

дык табы на пробелы заменят. Все зло от табов.

dilmah (26.03.2009 13:21:36)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Ну случится это один раз - удалят этот файл

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

Я был бы более спокоен, если бы они использовали CRC32, но зато протестировали код, обрабатывающий коллизии.

> Дык все что связано с хэшами - подвержено ненулевой вероятности коллизии. Теория множеств мать ее итить.

я не вижу необходимости здесь опираться только на один хэш (кроме мнимой красоты и упрощения кода).

dilmah (26.03.2009 13:26:33)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

>> O_o с чего бы ему не повториться?

> дык табы на пробелы заменят.

Дык это ж другой файл будет.

> Все зло от табов.

Клевета :D

tailgunner (26.03.2009 13:26:37)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> O_o с чего бы ему не повториться?

Ну например в комментарий допишут одну строчку где будет сказано /* a collision happened */ и тогда оно не повторится.

eXOR (26.03.2009 15:52:00)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> а повлечет коррупцию данных и таинственные глюки.

да почему?

eXOR (26.03.2009 15:53:04)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Дык это ж другой файл будет.

О чем и речь.

eXOR (26.03.2009 15:53:43)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> > > а повлечет коррупцию данных и таинственные глюки.

> да почему?

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

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

dilmah (26.03.2009 16:04:23)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> а где доказательства того, что кто-то продумывал код на случай коллизии?

А это невозможно. В систему заложено предположение "коллизий не будет".

> хэши используют вовсе не только для иденитификации файлов, а вообще всех объектов в системе -- патчсетов например.

Патчсеты - это не в Git, а в Darcs. Но тоже по хэшам, да.

tailgunner (26.03.2009 16:21:56)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

>а где доказательства того, что кто-то продумывал код на случай
>коллизии?

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

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

И что? Даже если у патчесета и у файла один и тот же хэш - это все равно разные сущности. Системе на это полюбому пофиг.


>Я ж говорю, луше бы CRC32 использовали, чтобы протестировать этот
>код.

Дык какая разница? Протестировать систему можно используя простую хэш функцию x -> 1. Будет со 100% выдавать коллизию.

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

eXOR (26.03.2009 18:10:14)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Посмотри как в базах данных живут с ключами в виде GUID-ов, для обеспечения уникальности ключа.

Это совсем другая вещь.

> Бывают коллизии, но их фиксят ручками

Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

tailgunner (26.03.2009 18:15:36)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Посмотри как в базах данных живут с ключами в виде GUID-ов, для обеспечения уникальности ключа.

UUID, генерируемый правильно, по RFC, с использованием MAC, time и счетчиков кардинально отличается от хэшей.

dilmah (26.03.2009 18:17:51)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

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

dilmah (26.03.2009 18:29:08)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> UUID, генерируемый правильно, по RFC, с использованием MAC, time и счетчиков кардинально отличается от хэшей.

И чем же? Вероятность коллизии есть и для него.

>> Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

> не верю, что это нерешаемая проблема

Решается она с такими накладными расходами, что придется отказаться от схемы.

tailgunner (26.03.2009 18:32:16)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Чем? Есть большее множество, которое отображается в меньшее множество. Будут коллизии. Хоть ты как заисголяйся над алгоритмом.

eXOR (26.03.2009 18:37:22)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Нужно просто поддерживать дополнительные ID, а не довольствоваться
> "внутренним" ID, который определяется как хэш содержимого.

А когда дополнительный ID совпадет с другим дополнительным ID, тогда придумаем третий ID? И так до тех пор пока множества не станут равны? :).

eXOR (26.03.2009 18:38:51)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> И чем же? Вероятность коллизии есть и для него.

обсуждалось же выше.. birthday paradox убивается.

Компаниям выдают неперескающиеся диапазоны маков, если конкретная компания реюзает маки, то это ее проблема, не нужно покупать их карты.

Время нужно майнтейнить, есть ntp.

Плюс там используются дополнительные счетчики.

Если UUID все-таки совпадают, то это распиздяйство, а не кирпич с неба на голову упал.

dilmah (26.03.2009 18:43:30)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> А когда дополнительный ID совпадет с другим дополнительным ID, тогда придумаем третий ID? И так до тех пор пока множества не станут равны? :)

нет конечно.

dilmah (26.03.2009 18:45:37)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Компаниям выдают неперескающиеся диапазоны маков, если конкретная компания реюзает маки, то это ее проблема, не нужно покупать их карты.

Никогда не знаешь наперед.

> Время нужно майнтейнить, есть ntp.

Ага, в глобальном масштабе.

> Если UUID все-таки совпадают, то это распиздяйство

А обнаруживать это как?

tailgunner (26.03.2009 18:46:21)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

А как?

eXOR (26.03.2009 18:55:48)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Компаниям выдают неперескающиеся диапазоны маков

Дык два разных mac-а выдадут одинаковый хэш. Точно так же как два разных файла могут выдать одинаковый хэш.

eXOR (26.03.2009 18:57:12)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> Дык два разных mac-а выдадут одинаковый хэш.

в uuid мак, время и счетчик не хэшируются, они включаются in plain.

dilmah (26.03.2009 19:11:26)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

То есть на одном маке можно легко создать два одинаковых хэша?

eXOR (26.03.2009 23:33:57)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

> То есть на одном маке можно легко создать два одинаковых хэша?

что-то я тебя совсем не понимаю..

dilmah (27.03.2009 14:02:12)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

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

eXOR (27.03.2009 15:42:24)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

я говорил, что DRCS можно реализовать, не опираясь на предположение о том, что коллизии в хэшах можно игнорировать.

Нам нужны ID для объектов, они же не обязаны быть только хэшем содержимого. Мы можем добавить к ним UUID. Мы можем добавить к ним имена. Наконец, нам в любом случае нужно от каждого пользователя DRCS иметь криптографическую подпись, а стало быть его identity. Все это мы можем включить в Id.

Разумеется, в этом случае в репозитории должно быть отдельное хранилище для Id.

Я не понимаю о чем спор.

dilmah (27.03.2009 16:24:48)

Re: что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

Это не решает задачу обеспечения уникальности идентификатора ресурса.

eXOR (27.03.2009 22:04:02)