Comments 90
Сколько в среднем блоков в файле?
Почти во столько раз будет больше вероятность.
Но вероятность что разные файлы будут с одинаковым хэшем — на порядки меньше
В случае с BT мы имеем (упрощенно)
80 байт представляющих любую последовательность из 16k байт. Одна из них определенно представлена нулями, но сколько еще последовательностей с ней совпадают по хешу?
В случае с конкретным файлом и конкретной длинной хешируемых данных, то чем больше файл и меньше рамер единицы хешируемых, то вероятность совпадения уменьшается. Но и тогда она никогда не будет равна нулю, даже если размер хешируемых будет равен исходным, кроме изначально уникальных ситуаций.
Расскажите — интересно же! А в нашей вселенной эта задача настолько сложна, что её до сих пор не умеют решать…
P.S. Только перед тем, как вы начнёте давать нерелевантные ссылки рекомендую на досуге почитать пару статей в Wikipedia, понять, чем атака нахождения прообраза отличается от коллизионной атака — тогда, может быть, поймёте почему в данном конкретном случае SHA1 достаточно (а можно было бы MD4 использовать, да).
- Функция хэширования идеальна
- Хэшируемые данные случайны
Поэтому если вам дан хэш от блока нулей, то ваш шанс найти набор данных дающий такой же хэш является 1/2^количество битэто утверждение верно лишь для идеальной функции хэширования в идеальном (случайном) пространстве множеств данных. Оба условия не соблюдены. Независимо от того, что я путаю выше
для любогоприведу пример пространства входных данных, в котором вероятность коллизии будет равна 1:
Возьмём последнюю строку из раздела TTH
по количеству цифр (48) определяем, что выход функции 768-битный (N=768)
Возьмём множество всех возможных значений исходных данных объёмомом M=70368744177664*8 бит (в таблице объём в байтах) с неким фиксированным значением хэша, например, 7FFB233B3B2806328171FB8B5C209F48DC095B72. В нём будет 2^(70368744177664*8-768) элементов с одним и тем же значением функции хэширования.
достаточно большогодостаточно большое, или надо ещё больше?
И это для идеальной функции хэширования, неидеальная увеличивает такое пространство минимум в 2 раза
В самом первом сообщении я указал на то, что нельзя полагаться только на хэши и я продолжаю на этом настаивать.
Продолжаю указывать, что вы рассчитываете вероятность для идеальных условий, находясь в реальных и игнорируете мои указания на это (вновь и вновь приводя одни и те же аргументы, которые годятся только для идеального мира)
Вычислимо оно или невычислимо, коллизии будут, и это только вопрос времени (нет, существенно меньшего, чем возраст Вселенной, Нашей или Параллельной)
В этом сообщении всё, на что я претендовал в комментариях к данной статье, и не надо мне приписывать того, что я не говорил и чего не подразумевал.
Проекты по последовательной компрометации функций хэширования (они постепенно движутся от более старых к более новым), хоть и затратили неимоверные вычислительные ресурсы (которые, впрочем, как капля в море по сравнению с ресурсами, затраченными на майнинг), продемонстрировали, что коллизии существуют не только в головах таких как я
Проекты по последовательной компрометации функций хэширования (они постепенно движутся от более старых к более новым), хоть и затратили неимоверные вычислительные ресурсы (которые, впрочем, как капля в море по сравнению с ресурсами, затраченными на майнинг), продемонстрировали, что коллизии существуют не только в головах таких как я.А ещё они продемонстрировали, что подход «вы не рефлексируйте, вы распространяйте» — победил окончательно. Коллизии к рассматриваемой задаче неприменимы, а атаки, которые применимы и от которых вы предлагаете защищаться сломают заодно все интернет-банки, биткойны, CDN, и массу других вещей.
Уверяю вас: в мире, где всё это рухнет вам будет меньше всего интересно искать пустые блоки в файлах.
Учитывая, что изначальное сообщение было в контесте безопасности странно слышать о том что атаки на хэши нет и исключительно нахождение прообраза есть единстенно верный пруф небезопасности.
И вряд ли словарная атака применима в данном конкретном случае.
Учитывая, что изначальное сообщение было в контесте безопасности странно слышать о том что атаки на хэши нет и исключительно нахождение прообраза есть единстенно верный пруф небезопасности.Нет. Учитывая, что речь шла о безопасности странно видеть тут популярный подход «а давайте надёргаем дерьма со StackOverflow и подмешаем нам в код — авось заработает».
Этот подход и при обычном-то программировании работает плохо, а к безопасности он неприменим совсем — потому что злоумышленник не будет вас уведомлять о том, что он нашёл дыру, а будет просто её использовать.
Когда вы говорите о безопасности вы всегда должны прежде всего описать — что вы собираетесь гарантировать, а чего нет.
Вы этого не сделали — и потому
А вероятность того, что вы её там посадите — гораздо больше, чем вероятность того, что кто-то найдёт практическую атаку на SHA1. Как я уже сказал: требуемой атаки даже на MD4 (который изначально рассматривался как «быстрый, возможно криптографически нестойкий, хеш») не существует.
Покажите такую — будет о чём говорить.
P.S. Логика тут простая: даже если вы можете предполагать, что в вашей бронированной двери из титана и кевлара может быть трещина идея поставить «для надёжности» ещё одну дверь из картона рядом — плоха.
- Я говорил об ошибке в архитектуре, а не в реализации (ошибки в реализации относительно легко обнаружить в ходе тестирования, особенно при существовании других реализаций)
- Я ничего не говорил о хакерах и других любителях и профессионалах искать коллизии кроме отсутствия их в гипотетической Параллельной Вселенной
P.S. Ещё можно здесь почитать
Причина очень проста: с некоторой вероятностью ваш компьютер будет считать ненулевой блок нулевым и наоборот — независимо от того, что и как вы там делаете. И эта вероятность заведомо больше, чем вероятность хеш-коллизий для криптохешей. Ну а наворачивая проверки — вы лишь делаете хуже. Ибо больше мест для сбоя и больше вероятность сбоя.
Кстати, насколько я понимаю файл на скриншоте может быть не только sparse, но и reparse файлом, которые создаются windows dedupe.
Reparse это как я понимаю про замену идентиных фалов на один с несколькими жескими ссылками на него. Это уже другая тема.
Установить sparse флаг можно при помощи fsutil.
только, кажется, после первой записи файла во все эти байты, если у этогой файла даже появятся нулевые блоки – сжатия е произодет. Нужно будет с этого файла снять флаг sparse и поставить его обратно, чтобы произошол повторный анализ файл и его сжатие. Кажется так.
Но с таким гемороем, наверно, проще установить какую-нибудь прогу-драйвер, которая создает раздел или типа того, и при записи в который вся инфа будет сжиматься как-будто проходит через архиватор.
Флаг необходимо установить на файл пока он нулевого размера. Далее его размер на диске будет зависеть от того сколько данных в него записано.
только, кажется, после первой записи файла во все эти байты, если у этогой файла даже появятся нулевые блоки – сжатия е произодет.
В участки где обнаружены нуль блоки просто не производится запись. Прграмма должна их просто пропустить. Производится только чтение для проверки соответствия хеша.
Нужно будет с этого файла снять флаг sparse и поставить его обратно, чтобы произошол повторный анализ файл и его сжатие.
При снятии флага пустые(не записанные) участки заполнятся нулями. При повторной установке эти нули так и остануться. Но есть утилиты которые прореживают участки которые заполнены нулями.
Также можно проредить заданные участки файла при помоши fsutil.
Флаг необходимо установить на файл пока он нулевого размера
Ну да. Не совсем понятно выразился. Фраза «после первой записи файла во все эти байты» означала создание разреженного файла.
В участки где обнаружены нуль блоки просто не производится запись. Прграмма должна их просто пропустить. Производится только чтение для проверки соответствия хеша
Разве? Т.е. создали разреженный файл ➜ записали полностью ➜ и еще раз поверх записали. Разве во время повторной записи будет сжатие?
При снятии флага пустые(не записанные) участки заполнятся нулями. При повторной установке эти нули так и остануться. Но есть утилиты которые прореживают участки которые заполнены нулями.
Также можно проредить заданные участки файла при помоши fsutil.
Точно. Забыл просто как это делается. У меня для этого случая просто батник валяется. Я в его содержимое давно не заглядывал ;)
Теперь когда я вижу нуль блоки в файле то сбрасываю его загрузку. Я предпочитаю думать что там действительно нули и файл битый чем то что мне повезло и я созерцаю коллизию. Не может так часто и крупно (бывает больше половины файла) везти.
Но можно не сбрасывать и Shareaza скачает только ту часть где есть данные. Тогда найдя полный файл по имени и размеру его можно слить с уже загруженными частями и продолжить загрузку полного файла.
Так что это больше не экономия а борьба с битыми файлами.
Просто атас.
Потому что "нуль-блок" пишется через дефис.
Извините, но не могу в личку, если ошибка в тексте сразу же в самом-самом старте.
![](https://habrastorage.org/webt/wn/hk/3q/wnhk3qkw1tuv_srphxp66tvskvy.jpeg)
Тогда давайте окончательно дооформляем первое предложение:
- Про нуль-блоки разобрались, хотя при введении термина хорошо бы его оформить в кавычки "для указания границ".
- Пропущен пробел перед открывающей скобкой.
- Пропущена запятая перед "заполненные".
С запятыми вообще вопрос: почему вы их так не любите? :)
Теперь по пунктам:
1) Если вы посмотрите на приведённый мною скриншот, то увидите там ситуацию с грамотностью, по факту полностью соответствующую крылатой фразе из фильма «О чём говорят мужчины»: «Это не кризис, это — ...».
2) Если вы попробуете найти много запятых в приведённом тексте…
3) Всё это — не есть гут, а есть очень, блин, неграмотно. И сначала все забивают на грамотность, а потом начинают жаловаться, что качество всего и везде как-то падает, да.
4) В упомянутой вами статье особо оговаривается, что функция не работает для мобильной версии. И так уж сложилось, что от 95% до 99% моей активности на сайте происходит через мобильный телефон в состоянии «на ходу». Не подскажете, где у меня можно найти необходимую комбинацию клавиш? ;)
5) Не особо важно, но всё-таки. Если вы внимательно посмотрите на первый комментарий к вашей ссылке… :)
Однако мне трудно определить масштаб этого явления. Иначе говоря, какой может быть относительная доля нуль-блоков в абстрактном носителе на 500Гб?
Отдельно отмечу, что не считаю предмет вашей статьи чем-то бесполезным, но серьёзность проблемы представлена довольно мутно.
Наличие нуль-блоков может быть признаком битого файла. Но если для формата их наличие нормально то мы сэкономим немного места и времени не скачивая и не храня их.
Допустим на этот 500ГБ носитель загружается один файл такого же размера. Какой нибудь фильм в UltraMegaHD 4D качестве. И у него всего один нуль-блок. Сколько он будет занимать?
В сети Edonkey2000 это фиксировано 9 728 000 байт.
В сети BitTorrent файл делится на от 1000 до 1500 блоков. Один нуль-блок в данном случае займёт 512МБ.
536870912000 байт / 1500 блоков = 357913941 байт/блок (341МБ)
Округляем до степени двух в большую сторону: 536870912 байт/блок (512МБ)
В сетях где используется Tree Tiger Hash максимально файл делится на 512 частей. Один нуль-блок в данном случае займёт 1ГБ.
536870912000 байт / 512 блоков = 1048576000 байт/блок (1000МБ)
Округляем до степени двух в большую сторону: 1073741824 байт/блок (1ГБ)
Например для передачи по сети 1 гигабайта нулей сколько нужно байт?
Максимально необходимо всего 5 байт, а в хороших упаковщиках размер данных будет на-амного меньше.
На диске нули нужны в программах например для выравнивания данных, для более быстрой обработки и тд. и тп.
У Вас хороший настрой подвергать сомнению, то что есть.
Но нужно копнуть чуть больше.
Как говорили предки? Аз-Буки-Веди.
Пойми Азы-причину Букв-знаков и будешь Ведать-знать.
Копнули бы чуть глубже, сами разобрались бы в причинах и методах решения «нулевых данных».
Я же и призываю использовать механизмы которые предоставляет операционная и файловая система. Прореженные(sparse) файлы это один из них. Он эффективен именно для участков заполненными нулями. Операционная система при чтении программой прореженных участков файла генерирует нули не обращаясь к диску.
При сжатии операционной системе приходится обращаться к диску для чтения инструкций по распаковке каждого блока.
То что выше пакет программ не использует сжатие, для передачи, не фатально.
Конечно, самым оптимальным образом нужно подобрать кодек под данные, но если данные «заполнены нулями» и программы эти данные не сжимают их сжимает операционная система, а потом пытается их сжать передающая «железяка», так что решение уже есть и используются довольно давно.
PS:
Если захотите со мной пообщаться напишите в личку, причину «лички» думаю поймете.
В своём клиенте я допустим могу включить сжатие передаваемых данных. Но его должна поддерживать и другая сторона. Для этого надо писать предложение к каждому протоколу и добиться внедрения хотябы в одном популярном в этой сети клиенте.
Списки хешей с другой стороны передают практически все p2p клиенты уже сейчас. И на онове их мой клиент может понять где в файле нуль-блоки и вообще не запрашивать их. По моему не передавать ничего гораздо эффективней чем передавать что то сжатое.
> а потом пытается их сжать передающая «железяка»
То что на железном уровне при передаче есть какое то сжатие не знал. Надо будет по эксперементировать.
Во-вторых, уже не касательно вашего подхода (хоть он и вызывает опасения из-за возможных коллизий, но вероятность их и правда мала), а касательно самих p2p-протоколов: надёжнее и проще было бы пустые блоки помечать таковыми в таблице хешей сразу, флажком в явном виде, но этого как я понимаю там нигде нет, но если уж речь про доработку клиентов то наверно можно сделать опциональную фичу такую в них, а со временем её и другие начнут поддерживать. И ещё — неужели там сжатия нет? если есть, то качать бы не пришлось особо.
Во-первых пустые блоки бывают и во вполне нормальных (не повреждённых) файлах, так что считать признаком повреждения их можно только с дополнительными какими-то условиями.
Согласен. В двух дистрибутивах Ubuntu (1, 2) наблюдаю по одному нуль-блоку. Не будут же они публиковать битый образ диска. В этом случае мы просто экономим по 1МБ дискового пространства и не ждём пока нам раздадут этот нуль-блок.
С другой стороны у сжатых файлов(видео, аудио, архивы) нуль-блоки признак битого файла. Но решает отменить загрузку или нет пользователь. Программа отображает наличие нуль-блоков и качает остальные блоки до отмены загрузки файла.
надёжнее и проще было бы пустые блоки помечать таковыми в таблице хешей сразу
Да флаг + хеш был бы возможно надёжнее. Но это потребует обновления множества клиентов чтоб те отдавали дополнительный флаг.
И ещё — неужели там сжатия нет? если есть, то качать бы не пришлось особо.
Сжатия нет насколько я знаю. Может потому что в основном идёт обмен уже сжатыми данными (архивы, видео, музыка и т.д.) об этом и не задумывались.
В коде каких еще p2p приложений вы разбирались? retroshare, i2p, freenet, gnunet, tox...? Это чрезвычайно интересная тема!
Если известно что размер блока — степень двойки, то показатель степени можно найти по формуле __popcnt(m_nBlockSize - 1)
и всё же неспокойно.
sha1 это блок 160 бит, sha 256 — соответственно 256
для блока в 512 мб (2^32 бит) это означает, что каждому значению хеша (включая нулевой) соответствует, ни много ни мало, а примерно 2^24 возможных исходных блоков.
Конечно же, блоков с "ненулевым" хешем гораздо больше — их чуть меньше 2^32 8-)
Но если мы говорим про некий "запакованный" объект — то там степень разнообразия данных выше, и кмк коллизии с нулевым хешем гораздо более реальны.
Вот идея сливать сначала не весь такой объект, а только его часть — кмк может "прокатить": согласно условиям разработки хеша похожие блоки должны иметь существенно различный хеш.
Вот это вот откуда, блин:
Но если мы говорим про некий «запакованный» объект — то там степень разнообразия данных выше, и кмк коллизии с нулевым хешем гораздо более реальны.Разница между этими величинами — одна из важных характеристик крипохеша, а SHA1, при всей его устарелости, всё-таки криптохеш…
Я вот понимаю криптографичность кеша как то, что а) нет перекоса в вероятности получить данный хеш (т.е. каждому хешу соответствует примерно одно и то же количество исходных текстов заданной длины), и б) малое изменение исходного текста сильно меняет хеш.
А про боязнь малых вероятностей — это не совсем так 8-)
Я не боюсь малой (1/2^256) вероятности получить хеш, который соответствует блоку из нулей. Я боюсь огромной (1-1/2^24) вероятности того, что блок из которого я получил «нулевой» хеш — на самом деле сильно от «нулевого блока» отличается. Особенно если у нас сильно меняется распределение вероятностей засчет некого изменения исходных данных («сжатие»).
PS. Я как-то в детстве читал что-то типа «занимательной математики». Там был рассказ про доцента и профессора, которые поспорили на велосипед, что за 10 минут в выходной день в маленьком городке мимо окна не пройдёт 100 человек. Доцент утверждал, что вероятность этого абсолютно, ничтожно мала — и тут мимо прошел отряд военных.
Может, кто знает, что это была за книга?
Нуэ. А что посоветуете?Судя по вашим высказываниям нужно с самого начала начинать. С какой-нибудь занимательной статистики в комиксах.
Я боюсь огромной (1-1/2^24) вероятности того, что блок из которого я получил «нулевой» хеш — на самом деле сильно от «нулевого блока» отличается.Может быть тогда вы сможете понять — в каком месте вы сделали ошибку и из какого… гхм… места вытащили свою «огромную» вероятность.
Потому что пока я даже представить не могу что вы считали и как что у вас такая вероятность получилась.
P.S. Чисто для справки: каждому значению хеша (влючая нулевой) соотвествует не «примерно 2^24 возможных исходных блоков», а порядка 2232-160 исходных блоков. Это число — столь велико, что если его тут взять и записать — у вас браузер повиснет. Но это не меняет того факта, что ваша ультраогромная вероятность таки равна 2-160. И будет равна ровно этому независимо от размера блока (за исключением блоков с длиной сильно близкой к длине хеша: если у вас есть, скажем, всего 161 бит, то не факт, что там вероятности будут равны).
P.P.S. То, что вы историю из Перельмана вспомнили — это прекрасно, но тут хорошо бы всё-таки не только про смешные рассказы помнить…
Да и с подсчётом я облажался. N бит представляют 2^N различных блоков, и тогда 512 мб это 2^32 бит, и соответственно 2^(2^32) различных блоков, и на одно значение хеша приходится, как вы и сказали, 2^(2^32-160) различных блоков.
Но только вот какая штука:
Если нам дали значение хеша, и мы генерируем некий блок данных, то мы получим именно тот хеш, который нам дали с вероятностью 2^-160. Ок.
Но если значение хеша, которое нам дали, внезапно совпало с хешем блока, который мы вот только что сгенерили (т.е. наша вероятность коллизии 2^-160 уже сработала) — то вероятность того, что «на той стороне» посчитали хеш именно из этого блока — 2^-(2^32-160), если у нас нет каких-либо предположений о распределении данных «на той стороне».
Собственно, это должно быть свойством криптохеша — см. п.3 для свойств идеального криптохеша:
3. Невозможность сгенерировать сообщение из его хеш-значения, за исключением попыток создания всех возможных сообщений
Ну и в рамках данного обсуждения мы «сгенерили» блок из всех нулей, что на вышеизложенные размышления влиять не должно.
Буду рад, если мне укажут на ошибку в моих предположениях.
Спасибо.
PS. И за Перельмана отдельное спасибо. 8-)
Не хватает в Transmission на NAS выключение переиндексации (вычисления хешей) для ранее скаченных файлов, например, добавляется новая серия в раздачу, приходится ждать пока для всех серий не подсчитаются хеши и только потом начинается скачивание.
Интересная статья. Что заинтересовало, почему Lua 5.1 в 2019 году? 5.3 вполне себе живёт и процветает.
Если проект старый и большой, то там всё ясно: обновление с 5.1 на более свежую версию с большой долей вероятности боль. Но в чистом проекте почему не 5.3?
```
// tth_hashes
// Hash: 13143C45D95485EACD9C47D72630EF0139436CB77DF2632B Size: 1024.0
// Hash: 855DCE7FE3E963F50295A673120E6259165CED9F086DB031 Size: 2048.0
// Hash: 38FB763B44ECA3B13F40182C75694360AC8DA0865DDB29D6 Size: 4096.0
// Hash: 721BEF53CBBDA47BE44BD26C43EC048F136D371E918200CF Size: 8192.0
// Hash: AFDDF505C1E1D5AF8FAE007BBE4E64578F34D912345E23D8 Size: 16384.0
// Hash: 53CC478ED14FF7FB671F94ECE0FD7C8C5DCB2FE611ACAC6B Size: 32768.0
```
Quick-and-dirty решается приведением к инту (если не ошибаюсь, math.tointeger(x)
), хотя как он вышел дробным — не могу понять сходу.
Вот проблемная строка:
print("// Hash: "..hash_hex, " Size: "..(1024*2^i));
Решил проблему при помощи math.floor:
print("// Hash: "..hash_hex, " Size: "..math.floor(1024*2^i));
Эта функция присутствует и до версии 5.3.
Да хоть 1.0 (не в курсе, есть ли такая) — если она свою задачу выполняет и при этом не содержит дыр, то всё в порядке.
Но с нулями у нормальных людей проблем нет.
Вы уже не первый человек со схожими мыслями. У меня есть расширенная версия скрипта которая вычисляет хеши различных шаблонов. Также я хотел реализовать дедубликацию блоков. Но это уже менее приоритетные вещи.
А детектор нуль-блоков эффективно помогает мне не качать "битые" блоки файла и решить стоит ли этот файл вообще качать при их наличии.
Хватит качать и хранить нули