Хеш-функции

Народ, а вот такой вопрос. Насколько я знаю хеш-функцию можно построить на основе любого блочного шифра (это так? почему?) - если нельзя, то тогда вопрос - как вообще создаются хеш-функции по типу md4,md5, sha-1, sha-2 и прочие...

Цитата DiZpeRs @ 15.05.11, 16:38

Народ, а вот такой вопрос. Насколько я знаю хеш-функцию можно построить на основе любого блочного шифра (это так? почему?) - если нельзя, то тогда вопрос - как вообще создаются хеш-функции по типу md4,md5, sha-1, sha-2 и прочие...

afaik, любая контрольная сумма - хэш, соответственно да, "хеш-функцию можно построить на основе любого блочного шифра". http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5

Спасибо! А вот, например, набросал я пример своей хеш-функции. Как мне теперь проверить насколько она хеш функция так сказать То есть проверить что сложно подобрать второй такой аргумент функции, чтобы получить такой же хеш-код, ну и криптостойкость хотелось бы оценить...

Цитата DiZpeRs @ 17.05.11, 10:53

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

Часть 1.
Основы можно посмотреть здесь random.org/analysis/
Дальше по ссылкам на тесты случайности
Часть 2.
Гуглить по линейному/дифференциальному криптоанализу, эргодичности, размножению ошибки, книжку "Криптография от папируса до компьютера" -- если из нее выкинуть 80% (поучительные истории), останется очень удобоваримый фундамент теории и ссылки на методы.

хеш функция - некоторая однонаправленная функция, одностороннее преобразование, описывается сугубо некоторыми разделами прикладной дискретной математики. Весь этот "mathematical background" очень хорошо предоставлен в книге Брюса Шнаера "Прикладная криптография", Альфреда Менезеса "Handbook of applied cryptography"
Я бы рекомендовал обратиться к некоторым нормативным документам NISTа. Как правильно здесь сказали, первое что должно проверяться - это статистика. Для проверки статистики в криптографии существует "негласный стандарт" в виде публикации "NIST Special Publication 800-22 A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications"
В нем есть математическое описание для криптографического материала - сюда мы относим всякие начальные заполнения, в т.ч. и хеш вектора.
По сути - нужно набрать какой-то огромный пул сообщений, посчитать статистику и убедиться в том что статистика "корявая". Шлепаем из пула сообщений пул хеш векторов - нам нада насобирать миллион бит. Ну и для этого пула считаем статистику.
Надо пройти все тесты!
Также элементарный и упрощенный перечень статтестов можно найти в упомянутой выше книге менезеса. Мы считаем хеш функцию хеш функцией, когда она "выравнивает" статистику - то есть при изменении одного бита входа все биты выхода сыпятся с вероятность 0.5 ровно безо всяких оговорок и поправок на ветер.
Кроме того, если ты используешь блочный шифер какой-то кастом алгоритм в качестве строительного блока, тебе надо проверить его на стойкость к методам линейного и/или дифференциального криптоанализа, либо брать нечто стандартное ))))
И да, для примера хеш функция ГОСТ 34.10 построена на базе блочного шифра ГОСТ 28147-89, разработанного еще до нападения половцев на советский союз. Любая функция хеширования содержит блоки линейных и нелинейных преобразований, их надо либо строить самому и просчитывать всю эту математическую дрочь, либо брать уже готовые!) На самом деле вся эта инженерия - задача не для слабонервных

Цитата DiZpeRs @ 17.05.11, 10:53

Спасибо! А вот, например, набросал я пример своей хеш-функции. Как мне теперь проверить насколько она хеш функция так сказать То есть проверить что сложно подобрать второй такой аргумент функции, чтобы получить такой же хеш-код, ну и криптостойкость хотелось бы оценить...

1. криптостойкость ни в коем случае не выше, чем диапазон результатов хэша. например, если хэш-функция представляет собой двоичное восьмибитное сложение с игнором переполнения (т.н. CRC8, применялась в восьмидесятые. результат — число от 0 до 255), значит, при переборе 256 вариантов входных данных неминуемо будет как минимум два одинаковых хэша. для CRC32 вариантов конечно много больше, но тем не менее, существует множество разных файлов с одинаковой CRC32.
2. обратимость любого хэша — теоретически нулевая, если он короче входных данных. изложите "войну и мир" в ста словах... сможет ли кто-то на основании только этого "изложения" написать "войну и мир", идентичную оригиналу???

3. Единственный абсолютно стойкий шифр — это "Шифр Вернама", но терморектальному криптоанализу он поддаётся не хуже других.

DarknessPaladin
1. для шифров и для хешей - разные определения криптостойкости. Для шифра это количество переборов для определения ключа, для хеша - вычислительная сложность нахождения так называемых коллизий. В большей степени это задача мат статистики и теории автоматов. CRC32 - это не хеш, а всего навсего контрольная сумма. Да и использования хеша не предполагает генерацию и распределение ключей)
2. подсчет прямого и обратного значений хеша - задачи совершенно разных классов сложности. Р и NP. В теории алгоритмов проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в лимон баксов ))
3. Разовый блокнот к хешам не имеет вообще никакого отношения. И после гарантированного уничтожения разового ключ никакой паяльник ни в какой жопе не сможет восстановить уничтоженную гамму. Единственный способ узнать ключ - это телепатия!

Сообщение отредактировано: nemez - 11.08.11, 20:44

Цитата nemez @ 11.08.11, 20:44

DarknessPaladin
1. для шифров и для хешей - разные определения криптостойкости. Для шифра это количество переборов для определения ключа, для хеша - вычислительная сложность нахождения так называемых коллизий. В большей степени это задача мат статистики и теории автоматов.

К алгоритмам шифрования теория автоматов и мат. статистика замечательно приложимы.

Цитата nemez @ 11.08.11, 20:44

DarknessPaladin
Да и использования хеша не предполагает генерацию и распределение ключей)

Правда? А ключевые хэш-функции?

Цитата nemez @ 11.08.11, 20:44

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

Зато можно узнать саму информацию

Цитата "AV_77"

К алгоритмам шифрования теория автоматов и мат. статистика замечательно приложимы.

Кончено же применимы, но основной матаппарат для анализа симметричной криптохренатени - булева алгебра. В частности, методы линеаризации булевых функций. Да и теория графов)) Потом остальное) Анализ хеша, как правило, не требует ковыряния в нелинейных узлах наподобие S-блоков, P-блоков и тому подобной чепухи.. Потому как хеш в своей основе строится на базе уже готовых нелинейных узлов или вообще блочных шифров!. Потому там как раз таки основной удар на разделы мат статистики и теории автоматов!

Цитата "AV_77"

Правда? А ключевые хэш-функции?

Да, это игра слов. В нормативных документах рф, напр., "ключевой хеш" - это режим работы блочного шифра. Дада, в ГОСТ 28147-89 существует понятия режима иммитовставки )) "Ключевым хешом" его называют за рубежом ))))))
Я же здесь разговариваю на русском языке и следую терминологии нормативной базы рф. Хоть и обитаю не в России.
Кстати в самом хеше ГОСТ 3411 - там существует понятие так называемого 256 битового IV - вектора вектора инициализации.. Что это? Ключ! ))) Если его засекретить - то получаем "Месседж дайждест код". Если следовать стандарту (а по нему он не секретится) - имеем MAC )) вот так.

Дополню по ключевым хешам. Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с ДОВЕРЯЮЩИМИ друг другу пользователями. Такая вот издержка. А основной прикол политик безопасности - строить модель на недоверии! "В наше время никому верить нельзя, даже самому себе" - говорил мужик стирая от говна собственные джинсы..
Поэтому на смену ключевым хешам и пришла электрическая цифровая подпись
Она, как и ключевые хеши, гарантирует целостность и аутентичность, но юзерам А и Б не обязательно доверять друг другу! И кстати, хеш является неотъемлимым куском ЭЦП!

такой вам небольшой криптографический ликбез

Сообщение отредактировано: nemez - 16.08.11, 23:11

Цитата nemez @ 11.08.11, 20:44

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

еоллизия обязательно произойдёт, если перебрать число вариантов, равное 2^(битовая длинна хэша).

Цитата nemez @ 11.08.11, 20:44

CRC32 - это не хеш, а всего навсего контрольная сумма.

CRC32 — это как раз хэш (хоть и криптографически примитивный), ибо соответствует определению, являясь функцией необратимого преобразования с постоянным результатом: из одного и того же массива данных всегда можно вычислить одну и ту же CRC32, но из CRC невозможно вычислить исходный массив. В криптографии хэши подобного типа не применяются только из-за своей простоты... например, после изменения массива данных для получения нужного CRC8 все вычисления легко можно вообще провести "в уме". (CRC8 применялся, например, на спектрумах и подобных компах). CRC32 лично я в уме не посчитаю (нет соответствующего опыта, CRC8 мне лет пять приходилось регулярно считать), но просто на бумажке — вполне возможно.

Цитата nemez @ 11.08.11, 20:44

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

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

Говоря о ТРК, я не имел ввиду восстановление ключа — саму инфу методами ТРК восстановить проще.

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

Цитата

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

Докладываю. Шифр Вернама - это другое название шифра "Разовый блокнот" (One time pad) Почитайте Клода Шеннона, "Теорию связи в секретных системах" ))))
педивикия утверждает что

Цитата

Шифр Вернама (другое название: англ. One-time pad — схема одноразовых блокнотов) — в криптографии система симметричного шифрования, изобретённая в 1917 году сотрудниками AT&T Мейджором Джозефом Моборном и Гильбертом Вернамом. Шифр Вернама является системой шифрования, для которой доказана абсолютная криптографическая стойкость.

в чем я с ней на 100% согласен

Цитата nemez @ 16.08.11, 21:25

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

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

Цитата nemez @ 16.08.11, 21:25

Да, это игра слов. В нормативных документах рф, напр., "ключевой хеш" - это режим работы блочного шифра. Дада, в ГОСТ 28147-89 существует понятия режима иммитовставки )) "Ключевым хешом" его называют за рубежом ))))))

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

Цитата nemez @ 16.08.11, 21:25

Дополню по ключевым хешам. Они дают возможность без дополнительных средств гарантировать как правильность источника данных, так и целостность данных в системах с ДОВЕРЯЮЩИМИ друг другу пользователями. Такая вот издержка. А основной прикол политик безопасности - строить модель на недоверии!

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

Ну и вашими же словами:

Цитата nemez @ 16.08.11, 21:25

такой вам небольшой криптографический ликбез

Сообщение отредактировано: AV_77 - 17.08.11, 15:39

Цитата

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

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

Цитата

Понятие такое есть, а будете вы говорить об имитовставке или ключевой хэш-функции сути не меняет

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

Цитата

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

зависит напрямую. Модель защиты строится исходя из угроз и рисков. Есть нормативная база, как это делать, и определенные градации. Предусмотрено, какие механизмы защиты когда применять)

Цитата

Не читайте Шнайера ))

ага)) виноват исправлюсь

Цитата nemez @ 17.08.11, 15:41

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

Все-таки не все, тотальный перебор, "встреча по середине", и можно еще поискать )))

Цитата nemez @ 17.08.11, 15:41

А какой матаппарат использован для моделирования - это уже ... Но одной теорией автоматов и статистикой явно не обойтись )))))))))

Цитата nemez @ 17.08.11, 15:41

зависит напрямую. Модель защиты строится исходя из угроз и рисков. Есть нормативная база, как это делать, и определенные градации. Предусмотрено, какие механизмы защиты когда применять)

Кто же с этим спорит ) И ЭЦП и имитовставки широко применяются, каждая в своем случае. Про это и говорим.

Цитата nemez @ 17.08.11, 15:41

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

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

"встреча посередине" - вероятностный метод! там формируется множество ключей которые с какой-то вероятностью есть истинный ключ ) )) ДКА - вероятностный, линеаризация - вероятностный, и т.д. ))) там все вероятностное за исключением тотального перебора=)

Цитата

А вероятность принять ложное сообщение за истинное от наличия коллизий разве не зависит?

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

Цитата nemez @ 17.08.11, 13:20

Докладываю. Шифр Вернама - это другое название шифра "Разовый блокнот" (One time pad) Почитайте Клода Шеннона, "Теорию связи в секретных системах" ))))
педивикия утверждает что

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

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

Цитата nemez @ 17.08.11, 13:20

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

Цитата DarknessPaladin @ 17.08.11, 12:27

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

повторюсь. хэш -- это любая НЕОБРАТИМАЯ функция. даже операция MOD(x) (или возведение в квадрат) является хэшем, ибо необратимо меняет данные (из её результата невозможно вычислить, был аргумент положительным или отрицательным).

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

посяню на пальцах:

берём функцию y=mod(x). известно, что её аргумент при известном y был либо y, либо -y. то есть, если я хочу получить от неё результат, например, 10, я могу использовать аргумент "10" или "-10", неважно.
с крк почти тоже самое -- если я хочу получить от неё заданный результат, мне не нужно перебирать все возможные варианты аргумента -- я могу вычислить "какой-нибудь" аргумент, который позволит мне получить от функции нужный мне результат.

а криптографические хэши дают результат математически непредсказуемый, то есть, я не смогу найти никакого аргумента, подходящего для нужного результата, иначе, как перебирая варианты.
хороший пример: пишем на карточках случайные числа, перемешиваем их, и нумеруем от нуля до 255. потом nemez залезает в чёрный ящик с полученной колодой, и я спрашиваю его -- "хэш от 125?"... он смотрит на карточку с номером 125 и говорит какое число на ней написано... и фиг я придумаю, какое ему число нужно сказать, чтоб получить нужный результат, не перепробовав кучу вариантов... хотя конечно это не математический метод хэширования получился, а просто "закрытый алгоритм", но для ясности можно и так.


ЗЫ. и вообще, CRC я привёл в качестве примера хэша совсем не ради спора о том, является ли любой хэш криптографическим, а просто для иллюстрации идеи, что чем длиннее результат хэша, тем сложнее подобрать аргумент и тем ниже вероятность коллизий.

DarknessPaladin
в таком случае вы противоречите сами себе..

Цитата DarknessPaladin

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

далее..

Цитата DarknessPaladin

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

Тоесть, следовательно, таки является разовым блокнотом. Ваше последнее утверждение правильно.

Далее.

Цитата

повторюсь. хэш -- это любая НЕОБРАТИМАЯ функция.

вы можете понимать это как вы хотите, но есть нормативная база, которая для всех определяют терминологию.
Напр., действующий стандарт на территории РФ дает следующее определение:

Цитата ГОСТ 34.10-94

Хеш-функция - Функция, отображающая строки бит в строки бит фиксированной длины и удовлетворяющая следующим свойствам:
1) по данному значению функции сложно вычислить исходные данные, отображенные в это значение
2) для заданных исходных данных трудно найти другие исходные данные, отображаемые с тем же результатом
3) трудно найти какую-либо пару исходных данных с одинаковым значением хеш-функции

на этом точка. Это стандарт. Никакой "полной необратимости". Никаких "математических непредсказуемостей"
Все что попадает под определение и удовлетворяет п.п. 1-3 - это хеш. Остальное - все что угодно - код, однонаправленная функция, контрольная сумма. Но не хеш.

Цитата

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

ну дак и ежу понятно что при увеличении битовой длины результата возрастает количество переборов

Цитата nemez @ 20.08.11, 23:04

в таком случае вы противоречите сами себе..

"всякая селёдка — рыба, но не каждая рыба — селёдка" (с)
Шифр Вернама — это один из множества шифров, использующих одноразовый блокнот.

таким образом, ваше утверждение

Цитата nemez @ 17.08.11, 13:20

Шифр Вернама - это другое название шифра "Разовый блокнот" (One time pad)

неверно так же, как "селёдка — это другое название рыбы".

Цитата nemez @ 20.08.11, 23:04

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

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


а то, что в госте написано, следует читать так:

Цитата nemez @ 20.08.11, 23:04

Хеш-функция в криптографии - Функция, отображающая строки бит в строки бит фиксированной длины и удовлетворяющая следующим свойствам:

а теперь я сошлюсь на педивикию:

http://ru.wikipedia.org/wiki/Хеширование

Цитата

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

http://ru.wikipedia.org/wiki/Криптографическая_хеш-функция

Цитата

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

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

Сообщение отредактировано: DarknessPaladin - 21.08.11, 13:42

DarknessPaladin
кагбе нужно читать нормативную базу, а не переводы импортных учебников и педивикию, отредактированные пчеловодами. Что такое криптографическая хеш функция - почитайте в стандарте ГОСТ 34.10-94. Определение взято тоже из него. Ни дать, не взять.
Перевод гуглом импортных учебников вностит сумятицу как в терминологию, определенную действующими стандартами, так и искажает ваше понимание. Обращайтесь к первоисточникам - а это есть действующие стандарты.

Сообщение отредактировано: nemez - 21.08.11, 20:07

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

AV_77 по терминологии спорить не нужно. Она уже определена, в каждой стране действующими нормативными документами. просто когда люди называют одно и то же разными словами - они разговаривают на разных языках и совершенно не понимают друг друга. Хеш это хеш, контрольная сумма это контрольная сумма. Котлеты отдельно, мухи отдельно.

Цитата nemez @ 20.08.11, 23:04

Напр., действующий стандарт на территории РФ дает следующее определение
...
на этом точка. Это стандарт.

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

Ладно, для CRC, Adler и прочих простых функций\кодов контроля целостности можно по традиции юзать название "контрольная сумма". А как быть с устоявшимся названием хэш-таблиц для поиска\сортировки строк, ведь в них еще более примитивные "хэш-функции" могут использоваться? Тоже низ-зя?!

Цитата

А как быть с устоявшимся названием хэш-таблиц

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

Цитата nemez @ 23.08.11, 10:14

Почитайте первый пост - мы говорим именно о криптографических хеш функциях, и ни о чем дургом!

Во-первых, сам почитай - первый пост это классика в стиле "один пишем, два в уме", типа догадайтесь о чем это я. Осюда и совершенно справедливая отписка #2, после которой ТС "соблаговолил" уточнить, что речь идет о криптографической хэш-функции.
Во-вторых, твои мухи\котлеты, шевроны и забегаловки тут неуместны, т.к. и криптография, и "информатика в целом" оперируют одним и тем же общим понятием хэш-функции, только требования к свойствам этой функции ес-но разные в зависимости от ее назначения \ области применения. Да, CRC32 по крипто-свойствам "ни в какие ворота не лезет", но тем не менее под "общеинформативное" определение хэш-функции подходит. Собс-но только об этом, и ни о чем другом, и сказал DarknessPaladin в #10. И че тут напрягаться и упираться рогом, выдумывая разные противопоставления типа "северное сияние с козлиными яйцами" и т.п. - не понятно. Успокойся, наконец, ты - прав

nemez, знаете, на что это всё похоже?

Оффтоп-пример

nemez работает, к примеру, в строительстве дирижаблей. Я к слову говорю что-то типа "у меня на автомобиле гайка заржавела", на что nemez показывает мне инструкцию от дирижабля, где написано "гайки изготавливаются из аллюминия (т.к. он лёгкий)" — на основании чего делается вывод, что гаек нигде, кроме дирижаблей, нет, а если и есть, то все гайки в мире — аллюминиевые и ржаветь не могут.

Цитата nemez @ 22.08.11, 20:31

Хеш это хеш, контрольная сумма это контрольная сумма. Котлеты отдельно, мухи отдельно.

неверно.
хэш это хэш, а криптографический хэш — это криптографический хэш. для начала это поймите.

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

DarknessPaladin
One Way Function. OWF это OWF, хеш это хеш, контрольные суммы это контрольные суммы. Это разные вещи совсем!)))
однонаправленная - такая функция для которой прямое вычисление "быстрое", обратное - "медленное". "Быстрое" или "Медленное" - это описывается теорией вычислений, по принадлежности к тем или иным классам вычислительной сложности. Какой класс у контрольных сумм? Полиномиальный )))) Являются ли они OWF? Нет! Являются ли ли они необратимыми? Да! )))
это разные вещи, как надувной шарик и презерватив приблизительно

Добавлено 26.08.11, 07:56
вообще прикольно слышать, чтобы введенное колмогоровым в математике понятие необратимых фунций называли хешами! жги еще!
пардон за флуд

Сообщение отредактировано: nemez - 26.08.11, 07:56

Цитата DarknessPaladin @ 26.08.11, 06:47

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

Мда, такие "ляпы" только подливают масла в огонь
Раз уж ты говоришь о хэшировании в общем смысле, то стоит вслед за wiki признать, что хэширование - это просто представление данных произвольного размера в виде некоторого кода\дайджеста фиксированной\ограниченной длины. Поэтому в общем случае необратимость это просто следствие ограничения разрядности данных (хотя для крипто-хэшей она является самостоятельным требованием).

Цитата nemez @ 26.08.11, 07:00

хеш это хеш, контрольные суммы это контрольные суммы. Это разные вещи совсем!)))

Опять ты за свое - я что не могу MD5 или SHA в качестве "контрольной суммы" использовать?! Интересно, о каких совершенно разных вещах ты бы говорил, если бы нашлась такая чудо функция\алгоритм расчета хэша, которая бы и считалась сверхбыстро, и удовлетворяла бы требованиям криптостойкости? Еще раз повторю - конечно CRC32 и MD5 это "разные вещи", но не "совершенно разные" как твои "красочные" примеры, т.к. человеческому разуму свойственно за деревьями видеть лес и находить общие принципы\понятия в разнородных, на первый взгляд, вещах - вся наука на этом держится

Цитата leo @ 26.08.11, 08:06

Опять ты за свое - я что не могу MD5 или SHA в качестве "контрольной суммы" использовать?! Интересно, о каких совершенно разных вещах ты бы говорил, если бы нашлась такая чудо функция\алгоритм расчета хэша, которая бы и считалась сверхбыстро, и удовлетворяла бы требованиям криптостойкости? Еще раз повторю - конечно CRC32 и MD5 это "разные вещи", но не "совершенно разные" как твои "красочные" примеры, т.к. человеческому разуму свойственно за деревьями видеть лес и находить общие принципы\понятия в разнородных, на первый взгляд, вещах - вся наука на этом держится

Есть один хороший принцып) Разумности и достатчоности, что вообще говря логично. Как таковое можно приудмать свое сжимающие отображение, которое будет рабоать быстро и иметь большое колличество прообразов. Да, может оно будет не так безопасно, но вполне достаточно, осбенно если считать все хитрым образом) А как таковое есть люди свято верющие что если, защифровать или применить повторно крипто алгоритм, буде ну очень безопасно)

И еще при применении даже безопасной и мощьной приптофункции глупя ошибка может убить все старания...

И CRC32 и MD5 по сути одно и тоже, но цели ращные. Как таковое, можно использовать MD5 или SHA)

leo
Syrl все правильно говорит. Это разные инструменты для решения разных целевых задач.

Цитата

Опять ты за свое - я что не могу MD5 или SHA в качестве "контрольной суммы" использовать?!

можете. Можете 20-килограмовую кувалду использовать в качестве молоточка для ремонта обуви. Или кластер на двесте процессоров использовать в качестве домашнего компьютера )))
А вы можете CRC32 использовать в качестве хеша для ECDSA? Если да - то я перед вами низко снимаю шляпу, кланяюсь как перед великим математиком и рекомендую результаты своей деятельности опубликовать на EuroCrypt!)) Ура новому направлению в дискретке!

Цитата

Интересно, о каких совершенно разных вещах ты бы говорил, если бы нашлась

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

Добавлено 09.09.11, 16:53
PS: Кинь ссылку на определение "контрольная сумма", желательно из какого-нить ГОСТ'а

Добавлено 09.09.11, 17:05
PPS: Бабушка с дедушкой - это уже прогресс по сравнению с северным сиянием и козлиными органами Надеюсь ты сам понимаешь, что для многих "приложений" без разницы с кем иметь дело - с бабушкой или с дедушкой

Цитата

PS: Кинь ссылку на определение "контрольная сумма", желательно из какого-нить ГОСТ'а

leo
если бы вы хоть раз в жизни держали в руках хоть один стандарт, таких бы вопросов не возникало бы
почитайте ГОСТ 34.11-94
там оперирует понятие как хеш функции, так и контрольных сумм. Контрольные суммы считаются при промежуточных вычислениях, сама функция - хеш.


почитайте глобальный документ - RFC 791 - Internet Protocol, описывающий протокол IP
там считается именно контрольная сумма на каждом заголовке сообщения.
Откройте любой документ NIST, абсолютно любой стандарт.
Почитайте нормативную базу - подобные посты вы просто пишете от ее незнания или извращенного понимания.

Уймись

Цитата nemez @ 11.09.11, 19:01

Почитайте нормативную базу - подобные посты вы просто пишете от ее незнания или извращенного понимания.

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

так и тут. вы тыкаете всем свои ГОСТы на криптографию, как ту инструкцию от дирижабля, не задумываясь, что "хэш" и "контрольная сумма" настолько же связаны с криптографией, насколько гайка — с дирижаблем. то есть, дирижабль (криптография) обязательно содержит в себе гайки, причём алюминиевые (криптохэши в криптографии), но это не значит, что других гаек не бывает в природе.

во, понял, как вам втолковать:

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

прям хокку, блин...

Цитата

вы тыкаете всем свои ГОСТы на криптографию, как ту инструкцию от дирижабля, не задумываясь, что "хэш" и "контрольная сумма" настолько же связаны с криптографией, насколько гайка — с дирижаблем

DarknessPaladin
какие госты по криптографии? Здесь о криптографии вскользь - я привел в качестве примера спецификацию протокола IP
RFC 791 - Internet Protocol
там на каждом IP пакете считается КОНТРОЛЬНАЯ СУММА - именно!
ip_checksum ))))) и никак иначе! ))))
криптография здесь никаким раком и никаким боком не проходит!

пример номер два. Национальный стандарт РФ.
Транспортирование аудио- и видеослужб с алгоритмом компрессии MPEG-4 (H.264/AVC) по цифровым системам передачи
http://www.niir.ru/rus/files/1_MPEG-4_IP_28_07_10.pdf
читайте дословно

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

Цитата nemez @ 14.09.11, 08:04

какие госты по криптографии? Здесь о криптографии вскользь - я привел в качестве примера спецификацию протокола IP
RFC 791 - Internet Protocol
там на каждом IP пакете считается КОНТРОЛЬНАЯ СУММА - именно!
ip_checksum ))))) и никак иначе! ))))
криптография здесь никаким раком и никаким боком не проходит!

Для любителя ссылаться на стандарты.
http://www.ietf.org/rfc/rfc2828
RFC 2828, Internet Security Glossary, p. 79:

Цитата

hash function
(I) An algorithm that computes a value based on a data object
(such as a message or file; usually variable-length; possibly very
large), thereby mapping the data object to a smaller data object
(the "hash result") which is usually a fixed-size value. (See:
checksum, keyed hash.)

(O) "A (mathematical) function which maps values from a large
(possibly very large) domain into a smaller range. A 'good' hash
function is such that the results of applying the function to a
(large) set of values in the domain will be evenly distributed
(and apparently at random) over the range." [X509]

( C ) The kind of hash function needed for security applications is
called a "cryptographic hash function", an algorithm for which it
is computationally infeasible (because no attack is significantly
more efficient than brute force) to find either (a) a data object
that maps to a pre-specified hash result (the "one-way" property)
or (b) two data objects that map to the same hash result (the
"collision-free" property). (See: MD2, MD4, MD5, SHA-1.)

( C ) A cryptographic hash is "good" in the sense stated in the "O"
definition for hash function. Any change to an input data object
will, with high probability, result in a different hash result, so
that the result of a cryptographic hash makes a good checksum for
a data object.

AV_77
ОООО )))
итак. по порядку.. возьмите приведенный вами документ, и прочитайте его для начала, сопоставьте данные!
Начнем с определения контрольной суммы:


например:

Цитата

checksum
( I ) A value that (a) is computed by a function that is dependent
on the contents of a data object and (b) is stored or transmitted
together with the object, for the purpose of detecting changes in
the data. (See: cyclic redundancy check, data integrity service,
error detection code, hash, keyed hash, protected checksum.)

( C ) To gain confidence that a data object has not been changed, an
entity that later uses the data can compute a checksum and compare
it with the checksum that was stored or transmitted with the
object.
..... блаблабла

и сравниваем с определением функции хеширования.. (приведено предыдущим постом)
разницу то хоть уловили между ними? Если нет, то я вам ее постараюсь объяснить на пальцах
если результат этого отображения хранится вместе с данными - то это контрольная сумма. Читайте дословно: "is stored or transmitted together with the object"!
Если результат отображения передается без данных, или данные передаются без вектора отображения, - это хеш.
Применяется ли в криптографических применениях передача хешей вместе с сообщениях? Если вы не в курсе криптографии, то поспешу вам ответить - нет. Те же банковские платежные транзакции - там передается цифровая подпись, хеш - это всего навсего промежуточное вычисление, этот вектор не передается на ту сторону, и не хранится. Поэтому эта вычислительная функция, в том применеии, в котором ее рекомендуют ваши же российские уполномоченные органы, и называется хешом.
Если вы возьмете, и при помощи ГОСТ Р 34.11 посчитаете хеш вектор от файла, и сохраните его вместе с файлом - этот хеш вектор будет называться контрольной суммой.
Почему CRC называют в приведенном вами документе алгоритмом для вычисления контрольных сумм (пруфлинк:

Цитата

cyclic redundancy check (CRC)
(I) Sometimes called "cyclic redundancy code". A type of checksum
algorithm that is not a cryptographic hash but is used to
implement data integrity service where accidental changes to data
are expected.

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

Короче, бывают контрольные суммы, бывают хеши. Также бывают иммитовставки - это за рубежом называемые ключевые хеши. Разбирайтесь, учитесь!

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

Цитата nemez @ 19.09.11, 15:55

разницу то хоть уловили между ними? Если нет, то я вам ее постараюсь объяснить на пальцах
если результат этого отображения хранится вместе с данными - то это контрольная сумма

Правильно. Теперь загляни, например, в описание майкрософтовских SxS манифестов (а также в сами манифесты в папочке Windows\WinSxS\Manifests) и "объясни на пальцах" откуда там взялись слова hashalg, hash и SHA1? То, что SHA1 в данном случае используется как "контрольная сумма", наверное, и ежу понятно. Но интересно как это вписывается в твою "теорию" - или SHA1 нельзя считать хэшем в твоем понимании, или все же любой "хороший" хэш можно использовать в качестве "контрольной суммы"?

Qraizer
совершенно верно!
смотри. Берешь, придумываешь пароль.
Считаешь от него CRC32. Получаешь ХЕШ ПАРОЛЯ,
Передаешь его хз куда - куда хочешь. ЭТО ХЕШ. На той стороне спрашиваем пароль, сравниваем хеши - если совпадет - орлайт христофор банифатич, пароль правильный. Это пример того, что называется хешом.
он передается "без сопутствующих данных", как ты и говоришь. "сопутствующие данные" остались в твоей памяти

Теперь идем далее. У тебя есть пакет данных. Тебе нужно для него обеспечить целостность передаваемых данных. Ты передаешь данные, и вместе с ними CRC32 - в этом случае CRC32 выступает в роли контрольной суммы!
Только лишь потому, что она передается вместе с данными!

В первом случае данные находятся в твоих мозгах. Они не передаются - передается только их "отпечаток". Именно он называется словом "хеш".
Во втором случае - данные идут по каналу связи. В этом случае их "свертка" называется контрольной суммой!
Это я привел пример. CRC32 на практике неприменима для хеширования - ее удел - вычисление контрольных сумм.

leo
теория не моя. Это так везде в сетевых технологиях принято, все вопросы к rfc

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

Сообщение отредактировано: nemez - 19.09.11, 18:13

Цитата nemez @ 19.09.11, 18:08

совершенно верно! ...

Спасибо, не надо. Флуд-флудом, но надо и меру знать. nemez, есть определение сущности и есть область её применения. Второе следует из первого, но никак не наоборот.

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

принято называть "контрольная сумма IP заголовка" или "хеш пароля". И никак не наоборот. Есть алгоритмы расчета конрольных сумм, есть функции хеширования. И есть строгие определения, что есть что, и есть между ними различие!
Это все подкреплено нормативной базой. Сделано для того, чтобы люди разговаривали на одном языке. Потому как есть все предпосылки превращать проекты в "вавилонскую башню" где каждый разговаривает на своем языке и никто ничего не понимает.
Специально для ВАС создан Инженерный Совет Интернет - (Internet Engineering Task Force, IETF). Одной из их задач есть разработка спецификаций, стандартов и соглашений по общим архитектурным принципам протоколов Интернет
в том числе и по вопросам терминологии. Хотите вы этого или нет, согласны или нет - это так и есть
Если кто-то считает что он умнее спецификаций rfc и стандартов РФ - флаг в руки, как говорится!)

Ничего, что это вообще говоря, математические термины, а отнюдь не IT-шные, и уж точно не настолько узкоспециализированные, чтобы ограничиваться интернетом и его RFCями?

Цитата

математические термины

лучше иногда жевать чем говорить. Математика описывает множества - в дискретке это поля кольца группы
поле http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B5_(%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B0)
кольцо http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D1%8C%D1%86%D0%BE_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
группа http://ru.wikipedia.org/wiki/%D0%93%D1%80%D1%83%D0%BF%D0%BF%D0%B0_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
а также отображения множеств
http://masteroid.ru/content/view/1028/42/
http://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
инъективные биективные и сюръективные

Далее. Математика описывает теорией автоматов некоторые фигни - конечные автоматы с их матрицами переходных вероятностей!

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

Понятно...

Добавлено 20.09.11, 10:04
Информатика - это по факту одно из практических приложений дискретной математики. Погугли лучше её, получишь много интересных ссылок. Даже на той же вики раздел по дискретной математике имеет прилично ссылок на различные её подразделы.

Qraizer
почти все вокруг - практическое приложение дискретки. Это высшего уровня теория. Применяемая для математического моделирования как вычислительных систем, так и систем криптографической защиты информации.
Информатика - это уровнем ниже теория, совмещенная с практикой. Как и криптография. Многие фундаментальные криптографические исследования публикуются в научных сборниках по информатике (LNCS - lecture notes for computer science) потому как содержат более высокоуровневую математику, применимую для представления, описания и доказательства "состоятельности" как обычных вычислительных алгоритмов, так и криптосистем. От одного до другого всего полшага!
Именно по этой причине эти разделы в совке были под грифом и обучали людей этим дисциплинам в сугубо специализированных учебных заведениях после тщательной проверки )))) После падения железного занавеса слово "дискретная математика" стали произносить вслух
Сама по себе штука достаточно интересная ))) тот же сертиком за рубежом
http://www.certicom.com/index.php/about
который начал проводить дискретно математические исследования так называемых эллиптических кривых, с потрохами купило АНБ США )))) и все публикации их специалистов прекратились Да и наши институты, занимающиеся прикладными исследованиями в области кибернетики и математики, были режимными объектами
Это штука в некотором смысле стратегическая )))