Простой вопрос о скорости работы SHA1 и MD5

По стандарту хэш должен быть полностью случайный.

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

Так вот, даже та случайность, которая полная, все же бывает очень разного сорта — есть независимые случайные события, а есть зависимые. Те и другие случайные, но качество случайности разное, при бросании монетки уже наступившие события не влияют на вероятность последующих, а при сдаче карт из колоды влияют — вероятность того, что следующая карта будет пиковой дамой, растет строго монотонно: 1/17, 1/16, 1/15, 1/14...

Это все из учебника, а углубленный анализ показывает более тонкие различия — сдача карт из колоды и выход шаров из тиражного барабана вроде бы совершенно тождественные процессы, то и другое цепочка зависимых случайных событий, настоящая случайная выборка без возврата, — ан нет, различие есть, чтобы его уловить, приходится ввести понятие отложенной случайности, так и пишем: наступившее событие, но неизвестное, мы считаем актуально ненаступившим! И соответственно вычисляем вероятность его наступления.
Вот оно — мы не знаем, орлом или решкой легла монета, потому что она закатилась под диван, так что для нас это наступившее событие находится в будущем. С колодой карт то же самое — настоящим случайным процессом является не сдача колоды (прометка), а тасование, а сдать карты можно только в том порядке, в каком они лежат в колоде (если не дергать!), так что прометка не случайный процесс, а только раскрытие (развертывание) случайного объекта (комбинаторного) — случайной перестановки 36 карт... Да, и этим сдача карт принципиально отличается от выхода шаров из тиражного барабана лотереи: там тоже любой номер может последовать за любым, но это случайность актуальная, информация о наступлении событий не отстает от событий ни на шаг...

Так вот, к чему вся эта теория? Это к тому, что случайность бывает разная, такая и этакая. Есть случайные объекты, а есть случайные процессы. Хорошая гамма, зависящая от пароля и от nonce, есть в точном смысле случайный объект — в точнейшем смысле, самом строгом, по учебнику: это случайная функция, то есть функция от случайного аргумента. Поэтому даже приставка псевдо- применительно к такой случайности выглядит лишней, это настоящая случайность. Но это не процесс, а объект — уже готовый, вроде стасованной колоды. Зато асинхронный шифр по своей природе не объект, а процесс — у него есть траектория, после замены во входном тексте хотя бы одной точки на запятую шифртекст меняет траекторию, все символы будут другими. Тоже случайность, но другая.
Да, да, и вот это же самое касается хэша, у которого левая и правая половина строки изменяются по разному закону! Обе половины полностью случайны, это строгое утверждение, но при малых искажениях текста левая и правая половины изменяются с неравной вероятностью. Одно другому не противоречит — не все случайные события равновероятны, не все распределения случайных величин равномерны...

Вот относительно гаммы есть это требование — равномерность, равновероятность, есть еще более тонкие условия Голомба. А относительно хэша... ну, не хочется спорить с людьми, которые в текущем положении вопроса осведомлены лучше меня, но все же должен заметить, что если общепринятое требование состоит в том, чтобы все символы хэша были равновероятны — не просто случайны, а именно равновероятны! — это требование несуразное, оно сформулировано с грубой ошибкой. Более точное и резонное условие — чтобы все символы хэша с равной (и очень высокой) вероятностью изменялись при малейших изменениях в тексте, это как раз в просторечии и называют лавинным эффектом, но и в такой формулировке есть теоретический изъян — это требование легко выполнить жульническим образом, схитрить. Очень просто: сделать так, что символы хэша зависят не только от символов текста, но и друг от друга. Истинная разрешающая способность хэша состоит в том, что на одну ошибку в тексте он отзывается ошибками в 21 байте из 32, а мы делаем перемешивание, складываем левую и правую часть — и пожалуйста, 32 ошибки на 32 байта. Только это жульничество и шарлатанство, формально условие соблюдено, но пользы никакой.

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

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

Это много или мало? Стоит ли овчинка выделки?

я долго ломал себе голову над тем, что это такое — случайность

Вопрос об истинной случайности? Этот вопрос по-настоящему не решён никак, о чём есть оговорки в работах по криптографии. К нему подходят чисто с утилитарной точки зрения. Обычно требуется создать равномерное случайное распределение и вводится понятие противника, который не сможет воспроизвести результат, не потратив определённого количества вычислительных затрат на восстановление внутреннего состояния.

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

Необходимое, но недостаточное, скажем так.

Нахождение любого различителя, быстрее чем полный перебор, между хэшем и случайной функцией — взлом хэша. Хэш должен быть неотличим от т.н. "модели случайного оракула" (Random Oracle Model). Все требования к хэшу по (псевдо)случайности (равномерность распределения, неразличимость подмножеств выхода, лавинный эффект, невозможность найти связь между входом и выходом, нахождение первых и вторых прообразов) должны укладываться в ROM.

Можете посмотреть, как вопрос неразличимости в ROM решён для функции KeccaK.

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

Что касается просто контрольной суммы без требования случайности (а только различимости на разных текстах), наверное, криптографы долго думали и пришли к выводу, что это не реализуемо без случайности — просто потому, что длина этой контрольной суммы сильно ограничена по сравнению с длиной текста, от которого она берётся. Имеет ли смысл такой узкоспециальный вопрос, как контрольная сумма (не хэш!) от текстов длиной порядка самой контрольной суммы? Не могу сказать. Наверное, такую задачу можно свести с каким-то случайным перестановкам. Напомнило/comment52716.

Но вот кто бы мне объяснил, на какие шиши живет автор ассемблера Arrowsoft?

Всегда есть выбор – не выводить изобретение из коммерческой тайны или выводить и запатентовать. В первом случае Вы получаете монополию до тех пор, пока чья нибудь умная голова не разгадает секрет, во втором Вы получаете монополию на время, теперь секрет Вы сами раскрыли всем и монополию защищает закон. Однако монополию надо ограничивать, чтобы стимулировать конкуренцию. Автор изобретения имеет много времени, чтобы создать новое изобретение и запатентовать его. Таким образом закон стимулирует прогресс и конкуренцию.

так что я долго ломал себе голову над тем, что это такое — случайность

чтобы рассматривать что такое случайность надо сперва определить о какой случайности идёт речь. Хеш md5(x) не случаен для одного и того же x. Правильнее сказать про хеш так:
Существует hash=md5(x), но не существует функции x=de_md5(hash) с приемлимой вычислительной сложностью.

Далее – под случайным событием иногда понимают не то, что им является. Например я подкидываю монету. Какова вероятность, что монета лежит орлом вверх? Сейчас она равна 100%, это свершившийся факт, просто никто пока не знает о нём. А вот вероятность, что Вы угадаете как лежит монета будет в идеале равна 50% в случае если нет никакой обратной связи между Вами и монетой. По сути в большинстве случаев под случайным событием имеется в виду такое событие, о котором не было известно, что оно произойдёт. В случае с квантовыми процессами из-за принципа неопределённости получается, что ещё и нельзя получить точную информацию, т.е. по сути из-за физических ограничений нельзя предугадать процесс и он становится в чистом виде случаен. Бритва Окамма удаляет вопрос о том будут ли две системы с полностью одинаковыми исходными данными развиваться одинаково, так как это никак нельзя проверить, т.е. нельзя создать или даже просто пронаблюдать две абсолютно одинаковые системы.

Наверное, такую задачу можно свести с каким-то случайным перестановкам. Напомнило/comment52716.

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

Самым уязвимым для критики местом оказалось, что у хэша есть неоднородность, левая и правая часть строки по-разному отзываются на ошибки в тексте, ну, и за этим вопиющим безобразием как-то незамеченным осталось сообщение, что это только один хэш из двух, а есть второй с другими свойствами, его выходная строка размещение без повторений. Так это просто кусочек более длинной строки, случайной перестановки всех 256 байт, можно вычислять ее полностью, а 24, 32 или 64 байта из 256 берутся просто ради экономии, это сокращает вычисления.

Но как раз у этого алгоритма теория жуткая! Конечно, случайных перестановок не 256, а 256! (примерно 10+e507), но это очень, очень проблемная штука — доказать, что хэширующая функция может порождать любую перестановку из всего множества возможных. Дикая задача! На самом деле она даже не сводится к вопросу, может ли подгруппа от данного набора образующих покрывать всю группу, как раз на этот счет есть известные результаты, почти классические, считается, что два произвольно выбранных элемента (случайных, случайных!) почти наверняка порождают группу целиком, — но это результат, как говорится, без ограничения общности, предполагается, что множители берутся в любом количестве и во всех степенях. А в реальной программе это невозможное условие, никто не может брать множители в ЛЮБОМ количестве, как раз количество ограничено, и тогда для всякого частного случая доказательство того, что среди произведений есть все 256! различных перестановок, становится невыразимо трудным. И от автора не приходится ждать помощи, хотя есть сведения, что он жив, просто по житейским причинам переменил интересы, сейчас работает крановщиком в городе Ашдоде. Или в Ашкелоне, точно никто не знает...

Да, так этот хэш, где случайные перестановки, он с виду красивее, элегантнее, и на порчу одного бита текста отзывается сразу вся строка — все 24 байта из 24 или 32 из 32, но радости в этом мало, потому что нет средства точно оценить вероятность коллизии, когда вся строка случайно совпадет с правильным значение. Очень поганая теория! Хотя в реализации есть какие-то бешеные хитрости, чтобы этот изъян в теории обойти. Ну, усложнения, которые не устраняют трудность, а переносят ее в другое место — нельзя доказать, что все произведения будут различны, так докажем хотя бы, что все множители будут различны: хэширование романа "Война и мир", который содержит три миллиона букв, состоит в том, что перемножаются три миллиона перестановок — и все разные, все различные! Но опять же не доказано, что различающиеся наборы множителей дают различные произведения, наоборот, легко доказывается, что произведения будут совпадать, коллизий сколько угодно, потому различных произведений всего-навсего 256!, а различных наборов множителей длиной в "Войну и мир" гораздо больше, — и не доказано даже более слабое утверждение, что вероятность коллизии будет немногим больше 1/256! Вот в чем загвоздка...

Поэтому красота этого алгоритма меня уже не радует, безумные хитрости реализации тоже не радуют (они еще и дорогостоящие, расходы на вычисления быстро растут), а вот тот алгоритм, где у хэша есть сильная и слабая половина, радует гораздо больше. Теория простая и понятная! Ну, раздражает людей слабая половина строки, откинем ее к черту, но даже и у этой слабой половины теория яснейшая, оценки вероятности элементарнейшие, все выражается аликвотными дробями, уровень математики древнеегипетский и вавилонский...

Для вероятностных процессов понятия априорности/апостериорности/(не)детерминированности давно приняты.

Кстати, с практической точки зрения, важен ещё объём памяти в процессе исполнения алгоритма, не только скорость. Безотносительно к объёмам памяти современных компьютеров, он всё равно должен быть минимальным для универсальности. RC4 — один из самых быстрых, но во многих случаях (микроконтроллеры, смарт-карты) неприемлимый по объёмам памяти.

Хэш должен быть неотличим от т.н. "модели случайного оракула" (Random Oracle Model). Все требования к хэшу по (псевдо)случайности (равномерность распределения, неразличимость подмножеств выхода, лавинный эффект, невозможность найти связь между входом и выходом, нахождение первых и вторых прообразов) должны укладываться в ROM.

Вспомнил старинный анекдот. "-- Это такси! — Такси. — А где шашечки? — Так вам нужны шашечки или нужно ехать?"
Вот и у нас то же самое. Что важнее — чтобы по хэшу было трудно найти прообраз (истинный или коллизионный) или чтобы хэш был по свойствам неотличим от этой самой Модели Случайного Оракула? Люблю теорию, но думаю, что первое важнее. А если кто-то скажет, что все, все без исключения условия в этой модели обязательны и рациональны, не поверю. Вам ехать или вам шашечки? Теория штука общая, а теперь объясните мне частный случай, в цифрах — в строке хэша ровно 16 байтов из 32 в ответ на порчу одного бита текста изменяются с вероятностью ровно 5/16 — вот и скажите, в каком году умерла бабушка швейцара во сколько раз это облегчает подыскание прообраза.
Сам сосчитать не могу, но предполагаю, что уменьшение расходов незначительное.

Можете посмотреть, как вопрос неразличимости в ROM решён для функции KeccaK.

Посмотрю, спасибо. Вот только пойму ли — это вопрос...

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

Поэтому без теории совсем никак. Например, это — атака. И это, т.е. это тоже. Если они будут быстрее брутфорса — то это сертификационный взлом и снятие алгоритмов с конкурса даже при отсутствии практических применимостей.

Если что, у нас есть FAQ по общим вопросам криптографии и статьи по доказуемой безопасности.

Всегда есть выбор – не выводить изобретение из коммерческой тайны или выводить и запатентовать. В первом случае Вы получаете монополию до тех пор, пока чья нибудь умная голова не разгадает секрет, во втором Вы получаете монополию на время, теперь секрет Вы сами раскрыли всем и монополию защищает закон. Однако монополию надо ограничивать, чтобы стимулировать конкуренцию. Автор изобретения имеет много времени, чтобы создать новое изобретение и запатентовать его. Таким образом закон стимулирует прогресс и конкуренцию.

Ах, не нравятся мне ихние буржуазные порядки! Прямо законы джунглей.

Угадал чужой секрет — схватил и бежать. И у них всегда так было, еще папаша Гека Финна говорил так: "Когда тебе подвернется курица, хватай ее, даже если она тебе не нужна, потому что кому-то другому она пригодится, а доброе дело никогда не пропадет." Оцените логику этого утверждения! И его мораль тоже...

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

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

Это ради прогресса? Нет, тут другая идея, вообще социалистическая — люди с трудом признали, что мои штаны принадлежат только мне, но все же не могут смириться с мыслью, что бумаги в моем столе тоже принадлежат только мне. Нет, искусство принадлежит народу! И новая техника является народным достоянием...

Ладно, это ихняя буржуйская мораль, загнивающий Запад, известное дело, еще в школе проходили, но кто же их все-таки кормит при таких порядках? Как они при таких жлобских законах с голоду не перемерли?
Уму непостижимо...

Всего три миллиона букв ... сколько это будет — всех подстрок не длинее 512 символов?

Весьма немного, около полутора миллиардов (длина текста помноженная на максимальную длину подстроки).

Агафон, ну сейчас точно оффтоперы набегут. Все социалистические, антибуржуазные и антикопирайтные идеи тоже придумали на Западе и именно там они и получили максимальное распространение (свободное ПО, добровольный отказ ряда изобретателей интернет-протоколов от их патентования и от миллиардов потенциальной выгоды и пр.). Мы не обсуждаем полит. вопросы в общей ветке.

не могут смириться с мыслью, что бумаги в моем столе тоже принадлежат только мне

Бумаги в столе – вам, а вот если вы их всем показали, по своей воле поделившись информацией (бумаги то остаются при вас) то уже не ваше дело как этои информацией распорядятся другие, потому как это уже и их информация. Ну это если по совести...

Бизнес на "интеллектуальной собственности" противоречит совести. :-)

Все социалистические, антибуржуазные и антикопирайтные идеи тоже придумали на Западе и именно там они и получили максимальное распространение

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

Бизнес на "интеллектуальной собственности" противоречит совести. :-)

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