Хэш функции на асимметрике

Идеальная не смысле случайного оракула, а в смысле отсутствия коллизий. Но такая функция n → n будет определена не всюду на N=n² значениях блока, а за вычетом множества объема N^-(1-1/a), гда a>1 и не очень велико, где она выдает ошибку. И это будет не банальная перестановка.


Почему не сработает такой вариант. Берем блочную хэш-фунцию без коллизий и определенную почти всюду f, обычную алгебраическую нелинейную и сильно зависящую от каждого бита каждого аргумета w, и сторим хэш-фунцию сжатия: h(x, y) = f(w(f(x), f(y))).
Какие претензии к таким фунциям? По ним просто нет доказательства их надежности или же постоянно обнаруживаются уязвимости, различители?

описка: N=2~n~, не N=n~2~

А такое не нужно. Если неотличима от RO, то нет коллизий и многих других побочных эффектов. Даже НИСТ неофициально предложил на конкурсе SHA-3 давать доказательства в ROM. Найден RO-различитель — функция нестойкая, неважно по коллизиям или по чему ещё.


С доказательствами сложнее. А второе — почти точно так. Например, в сети Файстеля любую небиективную раундовую функцию можно по определению преобразовать в блочный шифр (биективную ключезависимую перестановку). Но на практике стало выходить, что сети Файстеля с небиективными функциями легче подвержены криптоанализу, легче найти простые и невозможные дифференциалы и пр. различители. Стали предпочитать делать сети Файстеля с биективными раундовыми функциями. Затем посмотрели на это и решили, зачем вообще нужна сеть Файстеля? Раз раундовая функция биективна, значит обратима и решили отказаться от Файстеля и сделать прямую SP-сеть. Так появился Rijndael (после его концептуальных, но практически неудачных предшественников — 3-way и Square). Затем, практически те же авторы, что продвинули концепцию SP-сетей и AES, режили сделать такой же сдвиг парадигмы и для хэшей с помощью Keccak — использовать бесключевую биективную псевдослучайную перестановку, как самый надёжно конструируемый и понятный в моделировании объект и строить всё на основе него.

еще описка: N~-(1-1/a)~ это доля значений аргумента вне области определения, а само их количество порядка N~1/a~.

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

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


Если хеш-функция h построена на ассиметрике f (с открытым ключом шифрования и закрытым дешифрования) с надежным модулем, то она стойкая. В чем проблема для сжимающей h(x, y) = f(w(f(x), f(y)))? где w – несимметричный полином по модулю некоторого простого M, |N-M|<N~1/a~.


Это как, итерацией? Преобразовать в доказуемо биективную?


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

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

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


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

ZAS опять пытается рогами забор снести? Никогда не думал, что научиться писать степени для формул — это так сложно.

В идеальной конструкции должны быть коллизии.

Кстати, покажите (строгое доказательство не нужно, достаточно отсылки к очевидному факту), что даже если есть идеальная PRP, то даже в районе меньше 128…256 бит возможны случаи наличия тривиального различителя от RO в губчатой конструкции. Для идеальной PRP вероятность его выпадения приемлемо мала, а для реальной не должно быть метода нахождения быстрее перебора грубой силы. И если кто-то наткнётся на такой различитель, он может произвести сколько угодно коллизий. Просто по факту ограниченности размера внутреннего состояния.

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

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


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


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


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

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


Я не ZAS.


Это я ступил.

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

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

См. VSH и VSH^*, ECOH и ECOH2, FSB, SWIFT.

Общее рассмотрение проблемы: Provably secure cryptographic hash function, где упомянуты ещё MuHASH; Chaum, van Heijst, Pfitzmann hash function; Knapsack-based hash functions; The Zйmor-Tillich hash function; Hash functions from Sigma Protocols.

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

Ну и общее впечатление, даже часто по поверхностным выводам. Много народу пыталось что-то сделать на этом поле и пересмотрели гораздо более сложные конструкции, чем те наивные варианты, которые сперва приходят в голову. И в целом, как-то на этом поле практически ничего не выросло. Там указаны общие причины, вроде особенностей зазора в доказательствах по асимметрике; Коблиц и Менезис упоминали такое: стоит немного поменять коэффициент в доказательстве и сведение к сложной проблеме превращается в тыкву:

Менезис и я также исследовали некоторые менее значительные проблемы интерпретации результатов доказуемой безопасности. Даже если доказальство корректно, оно часто маскирует очень большую "ширину зазора". Это значит, что редукционистский аргумент, описывающий атаку на протокол, должен быть повторён миллионы раз для решения трудной вычислительной задачи. В этом случае практические гарантии, которых он достигает, очень непрочные. Менезис нашёл некоторые экстремальные примеры из таких "плохо подогнанных" проблем в нескольких очень известных работах по генераторам случайных чисел. Из одной работы следовало, что если вы аккуратно следуете аргументам авторов с рекоммендованными параметрами безопасности, то всё что они доказали, так это то, что атакующему потребуется 10^-40 наносекунд для взлома системы. Это меньше времени за которое свет успевает пройти 1 микрон.
Вот что стало происходить, когда стали делать рекоммендации по выбору параметров на основе ассимптотических теорем. Эта теорема гласит, что если N стремится к бесконечности, вы можете безопасно генерировать O(log log N) псевдослучайных бит, каждый раз когда вы выполняете извлечение корня квадратного по модулю составного числа N.

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

С хэшами на асимметрике такой же мрак, не следует слепо уповать на наличие доказательств сведения к «трудной проблеме». Шнайер и др. как раз больше доверяют симметрике, несмотря на её кажущуюся худшую математическую обоснованность.

Показателен пример с FSB, про которую доказано, что с т.з. трудных задач её взлом равносилен решению NP-полной задачи, зато всё отлично ломается простеньким линейным криптоанализом:

The provable security of FSB means that finding collisions is NP-complete. But the proof is a reduction to a problem with asymptotically hard worst-case complexity. This offers only limited security assurance as there still can be an algorithm that easily solves the problem for a subset of the problem space. For example, there exists a linearization method that can be used to produce collisions of in a matter of seconds on a desktop PC for early variants of FSB with claimed 2¹²⁸ security. It is shown that the hash function offers minimal pre-image or collision resistance when the message space is chosen in a specific way.

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

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

Да, вопрос обсуждался с «квантовиками» (Слово-то какое! Первый раз слышу) теми, кто профессионально занимался QKD (имеет научные статьи по этой теме), но окончательную точку поставил Реннер, я ему задал этот вопрос напрямую:

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

Реннер — бог №1 в мире в области теории по квантовому крипто (в широком смысле этого слова), и Уэли Маурер — отец его его руководитель по диссертации, поэтому с ε-точностью, где ε→0, можете считать это мнение истиной в последней инстанции.

Как раз Маурер, кажется, много занимался шумовой криптографией(?) и вообще всякой криптографией с ограничениями (типа bounded memory), так что, я думаю, они оба там в курсе всего.

Spinore, как поживают П.К.К.К.?

WTF?

Именно так.

Если это оно, то там и спрашивайте.

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

Это весьма нетривиальная конструкция при условии сохранения стойкости шифра. Если в таком шифре выбрать размер блока = размеру ключа, то он будет образовывать квазигруппу. Весьма нетрививально создать конструкцию в виде симметричного шифра, которая образовывала бы большую квазигруппу по открытому тексту и ключу. Можно было бы даже асимметричное шифрование на симметрике сделать. Такие попытки были, но успеха не потерпели.

Почему такое отличие от симметрики? В силу алгебраических свойств асимметрики несправедливы какие-то эмпирические предположения о статистической независимости композиций функций?

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

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


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

На случайного оракула тоже не следует уповать. Если мы возьмем две шифрующие n-битные блочные функции f₁ и f₂ с фиксированными ключами и построим на их основе хэш-функцию
h(x) = f₂( (q * f₁(x) + r) mod (2ⁿ – 2^n/2) ), где НОД(q, 2ⁿ – 2^n/2)=1, мы получим идеальную насколько возможно модель случайного оракула – ровно с 2^n/2 парными коллизиями, все честь по чести. Но взламывается она элементарно, если функции f₁ построена на симметрике, то есть легко обращаема.


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


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


По любому должен быть размер блока = размеру ключа, иначе не будет биективности, а в лучшем случае инъективность.


Полугруппу по композиции функций? Она всегда существует, по определению. При биективности по ключам, композиции функции шифрования f(f(m, k₁), k₂) порожают полноценную группу, с ключами неограниченной длины вида k₁ || k₂ ||...|| k_n образованных конкатенацей первичных n-битных ключей k_i с правилом сокращения k || k^-1=e, то есть образующих свободную алгебру. Но толку от какой композиции? При комбинировании ключей ее высота бы неограниченно возрастала. Вот если бы композиция функций приводила к умножению ключей f(f(m, k₁), k₂)=f(m, k₃ = ω(k₁, k₂)) это была бы практичная группа, где функция шифрования выполняется только один раз для любого ключа, но биективности по ключам для этого совершенно недостаточно.

Функцию шифрования с биективностью по ключам сделать нетрудно, например:
z = f_e(x,k) = f₂ ((f₁(x) + k) mod 2ⁿ). Тогда дешифрование будет
x = f_d(z, k^-1) = f₁^-1 ((f₂^-1(z) + k^-1) mod 2ⁿ), где k^-1 = -k mod 2ⁿ.
При f₂ = f₁^-1 композиция шифрований сводится к умножению ключей ω(k₁, k₂) = (k₁ + k₂) mod 2ⁿ.

Можно также брать z = f_e(x,k) = f₂ (f₁(x) XOR (XOR_i=1ⁿ k[i]*v_i)), где блоки v_i линейно независимы, k^-1=k. Для f₂ = f₁^-1 имеем ω(k₁, k₂) = k₁ XOR k₂.


Каким образом? Асимметричное шифрование здесь получится, только если f₁ и f₂ сами сделать на асимметрике.

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

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

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

Еще до возникшей здесь полемики, я схематически набросал программку многопроходного вычисления хэша от последовательности блоков длины n. Подмешивание к аргументу и результату имеется, оно даже несколько переусложнено. К аргументу я также помешивал хэш предыдущего раунда add, номер раунда k и номер блока beg, чтобы избежать вырожденных значений. Хэш вычисляется делением последовательности надвое, а не поточно, чтобы глубина обработки каждого блока была примерно одинакова – порядка log₂(n), для чего используется рекурсия.
Небольшие пояснения: '*' – метка экспорта, '-' – метка экспорта переменной только для чтения, h – многораундовая (32*D)-битная функция хэша от массива s из (32*D0)-битовых блоков, g – однораудовая функция хэша от интервала массива. Функция шифрования f и нелинейная биективная по каждому аргументу функция сжатия w не реализованы (выдают нулевой блок).
(* language Oberon *) MODULE hash; CONST D0* = 32; D* = 32; R* = 3; (* round *) (* (1 <= D0) & (D0 <= D) & (D <= MAX(INTEGER)) *) (* (1 <= R) & (R <= MAX(INTEGER)) *) TYPE TBlock0* = ARRAY D0 OF SET; TBlock* = ARRAY D OF SET; (* (MIN(SET) = 0) & (MAX(SET) = 31) *) (* SET ~ ARRAY 32 OF BOOLEAN *) (* TBlock0 ~ ARRAY 1024 OF BOOLEAN *) (* TBlock ~ ARRAY 1024 OF BOOLEAN *) VAR zero-: TBlock; PROCEDURE index (i: INTEGER; OUT res: TBlock); VAR j: INTEGER; BEGIN res[0] := BITS(i); j := 1; WHILE j < D DO res[j] := {}; INC(j) END END index; PROCEDURE copy0 (IN a: TBlock0; OUT res: TBlock); VAR j: INTEGER; BEGIN j := 0; WHILE j < D0 DO res[j] := a[j]; INC(j) END; WHILE j < D DO res[j] := {}; INC(j) END END copy0; PROCEDURE copy (IN a: TBlock; OUT res: TBlock); (* допустимо: @a = @res *) VAR j: INTEGER; BEGIN j := 0; WHILE j < D DO res[j] := a[j]; INC(j) END END copy; PROCEDURE xor (IN a, b: TBlock; OUT res: TBlock); (* допустимо: (@a = @b) OR (@a = @res) OR (@b = @res) *) VAR j: INTEGER; BEGIN j := 0; WHILE j < D DO res[j] := a[j] / b[j]; INC(j) END END xor; PROCEDURE w (IN a, b: TBlock; OUT res: TBlock); (*не реализована*) (* допустимо: (@a = @b) OR (@a = @res) OR (@b = @res) *) BEGIN END w; PROCEDURE f (IN a: TBlock; OUT res: TBlock); (*первичная hash*) (*не реализована*) (* допустимо: @a = @res *) BEGIN END f; PROCEDURE f2 (IN a, b: TBlock; OUT res: TBlock); (* допустимо: (@a = @b) OR (@a = @res) OR (@b = @res) *) VAR res0: TBlock; BEGIN w(a, b, res0 (*w(a,b)*)); f(res0, res (*f(w(a,b))*)) END f2; PROCEDURE g0 (IN a: TBlock; OUT res: TBlock); (* допустимо: @a = @res *) VAR res0: TBlock; BEGIN f(a, res0 (*f(a)*)); xor(a, res0, res (*a+f(a)*)) END g0; PROCEDURE g (IN s: ARRAY OF TBlock0; IN add: TBlock; beg, end, n, k: INTEGER; OUT res: TBlock); (* допустимо: (@s[beg] = @add) OR (@s[beg] = @res) OR (@add = @res) *) (* (beg < end) & (end <= n) & (n <= LEN(s)) *) VAR mell: INTEGER; res0, res1: TBlock; BEGIN index(k, res0 (*k*)); xor(res0, add, res0 (*add+k*)); g0(res0, res0 (*add+k+f(add+k)*)); index(beg, res1 (*beg*)); xor(res0, res1, res1 (*beg+add+k+f(add+k)*)); g0(res1, res1 (*beg+add+k+f(add+k)+f(beg+add+k+f(add+k))*)); index(n, res0 (*n*)); xor(res0, res1, res1 (*n+beg+add+k+f(add+k)+f(beg+add+k+f(add+k))*)); IF beg < end - 1 THEN mell := (beg + end MOD 2) DIV 2 + end DIV 2; g(s, add, beg, mell, n, k, res0); xor(res0, res1 (*n+beg+add+k+f(add+k)+f(beg+add+k+f(add+k))*), res0); g(s, add, mell, end, n, k, res1); f2(res0 (*n+beg+add+k+f(add+k)+f(beg+add+k+f(add+k))+g(beg..mell-1)*), res1 (*g(mell..end-1)*), res) ELSE copy0(s[beg], res0 (*s[beg]*)); xor(res0, add, res1 (*add+s[beg]*)); f2(res0 (*add+s[beg]*), res1 (*n+beg+add+k+f(add+k)+f(beg+add+k+f(add+k))*), res) END END g; PROCEDURE h* (IN s: ARRAY OF TBlock0; IN add0: TBlock; OUT res: TBlock); (* допустимо: (@s[i] = @add0) OR (@s[i] = @res) OR (@add0 = @res) *) (* по стандарту языка: 1 <= LEN(s) <= MAX(INTEGER) *) VAR k: INTEGER; add, res0: TBlock; BEGIN n := LEN(s); k := 0; copy(add0, add); WHILE k < R DO g(s, add, 0, n, n, k, res0); xor(res0, add, add); INC(k) END; copy(add, res) END h; BEGIN index(0, zero) END hash.