Регистрация Войти
Рейтинг:0
avatar Crypto

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

флаг in
infogulch

Возьмите последовательность байтовых буферов, хэшируйте каждый из них, интерпретируйте хэш-дайджесты как квадратные матрицы с 8-битными элементами int без знака и (матрица) умножьте их по порядку. Определите окончательную матрицу как «хэш» списка элементов.

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

(Я исследую это определение более подробно, включая примеры рабочего кода в блокноте python jupyter, который я опубликовал под названием Мерклист. Вы также можете играть с ним самостоятельно на Google Колаб, и добавьте аннотации hypothes.is к сообщению для общего отзыва. Я могу поднять детали оттуда к этому вопросу, если это необходимо.)

Вопрос

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

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

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

83
1 + 9
poncho avatar
флаг my
poncho
Кстати: я только что попробовал; когда я хешировал последовательность примерно из 3000 различных (не злонамеренно выбранных) прообразов вместе, результатом была нулевая матрица.
0
Ответить
флаг in
infogulch
Малыш, похоже, мое "не сделал домашнее задание" показывает. Как неловко Думаю, мне придется попробовать еще раз с $GF(256)$ и, возможно, проверить его более тщательно.
0
Ответить
poncho avatar
флаг my
poncho
Я подозреваю, что, хотя $GF(256)$ было бы значительно лучше, даже если вам нужно исключить необратимые матрицы, достаточно большой ряд все равно будет состоять из 0 - просто он может занять, возможно, миллион элементов, а не просто 3000.
0
Ответить
флаг in
infogulch
Вы думаете? Я чувствую, что если записи-кандидаты ограничены только обратимыми матрицами, это должно исправить это. Возьмем такой пример: $X A B C C^{-1} B^{-1} A^{-1}$; это всегда должно снова приводить к $X$, независимо от того, насколько длинна исходная последовательность $ABC$. Мол, если бы это было не так, то одна или несколько матриц не были бы обратимыми по определению. Нет? Я чувствую, что самой большой проблемой будет поиск обратимой матрицы для каждой возможной записи в разумные сроки.
0
Ответить
флаг in
infogulch
@poncho Я только что попробовал это с элементами матрицы $ GF (256) $, и после 10 миллионов записей все еще кажется нормальным. Вскоре я опубликую еще один вопрос, подобный этому, но вместо этого с формулировкой $ GF (256) $.
0
Ответить
poncho avatar
флаг my
poncho
Если вы используете $GF(256)$, то случайная матрица имеет приблизительно $1/256$ сингулярности; мое подозрение, что с длинной цепочкой количество сингулярных матриц, которые появляются случайным образом, будет постепенно уменьшать ранг, в конечном итоге приводя к рангу 0 (матрица со всеми 0). Однако у меня нет хорошей модели того, как скоро это произойдет...
0
Ответить
флаг in
infogulch
Да, ты прав. Чтобы убедиться, что никакие единичные матрицы не допускаются, я использую выборку отклонения в цикле при вычислении «хэш-матрицы» элемента, как вы предлагали ранее.
0
Ответить
poncho avatar
флаг my
poncho
Очевидно, что если вы ограничите себя обратимыми элементами, то они образуют группу, и поэтому вы никогда не столкнетесь с ограниченным состоянием (например, матрицей со всеми нулями). Могут быть тонкие приемы, которые можно использовать из теории групп, чтобы найти столкновение; впрочем, это совсем не очевидно...
0
Ответить
флаг in
infogulch
@poncho Я опубликовал черновик этого, используя $GF(256)$ в новом посте, если вам интересно: https://blog.infogulch.com/2021/07/15/Merklist-GF.html Вместо этого используется Julia. python, потому что я хотел попробовать Julia. Вы можете открыть его, чтобы редактировать онлайн. Я имею в виду добавить дополнение к моему исходному сообщению с изложением проблемы, которую вы обнаружили.
0
Ответить
Рейтинг:1
poncho avatar Crypto
флаг my
poncho

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

Да; самый очевидный способ — найти буфер, который хэширует в матрицу со всеми $n^2$ матричные элементы четные; повторите этот буфер 8 раз, и вы получите продукт, состоящий только из нулей.

Это занимает ожидаемое $2^{n^2}$ работать, чтобы найти такой буфер; за $n=8$, это правдоподобно.

Вероятно, его можно было бы улучшить; глядя на пары необратимых матриц, кажется правдоподобным, что при значительно меньших затратах труда, чем $2^{64}$, вы можете найти два, в произведении которых все элементы четны (и в этом случае применимо приведенное выше наблюдение).

0 + 3
флаг in
infogulch
Это имеет большой смысл.Чтобы уточнить, это вызвано моим выбором кольца (256), которое имеет коэффициенты 2? Как вы думаете, можно ли это улучшить, выбрав первичное кольцо (скажем, 257)?
0
Ответить
poncho avatar
флаг my
poncho
@infogulch: или $GF(2^8)$? Что ж, это помогло бы, но не так значительно; все еще есть хорошая вероятность (вероятность около 1/256 за попытку) найти необратимые матрицы; кажется правдоподобным, что вы можете склеить их вместе, чтобы найти продукты убывающего ранга, что приведет к матрице всех 0. На самом деле, мой первоначальный ответ должен был быть таким, пока я не понял, что ответ «все lsbits 0» было значительно легче обосновать. Тем не менее, если вы использовали такое поле, как $GF(256)$ или $GF(257)$, и намеренно пропустили (используя выборку отклонения) необратимые матрицы, это может сработать.
1
Ответить
флаг in
infogulch
Спасибо за указание на поля Галуа и обратимые матрицы. Я считал, что обратимые матрицы могут быть полезными, но они, вероятно, необходимы для того, чтобы это работало и не приводило к вырожденным случаям, таким как нулевая матрица.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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