Рейтинг:2

$2^{64}$ версий одного сообщения

флаг cn

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

Теперь мы покажем, как Оскар мог превратить свою способность находить столкновения (модифицируя два сообщения) в атаку. Например, он начинает с двух сообщений: $x_1 = \text{ Перевести \$10 на счет Оскара } \ x_2 = \text{ Перевести \$10 000 на счет Оскара} $

Теперь он изменяет $x_1$ и $x_2$ в «невидимых» местах, например, он заменяет пробелы табуляцией, добавляет пробелы и т. д. Смысл сообщений тот же (например, для банка), но меняется хэш.

Оскар пытается до тех пор, пока условие $ч(х_1)=ч(х_2)$. Обратите внимание, что если злоумышленник имеет, например, $64$ места, которые он может изменить или нет, это дает $2^{64}$ версии одного и того же сообщения с $2^{64}$ разные значения хэша.

Может кто-нибудь объяснить, что они имеют в виду под $2^{64}$ версии одного и того же сообщения? Это совершенно пролетело над моей головой. Я знаю, что хэш-функция (например, SHA-256) выдает 64 вывода, так что, например:

SHA256 (перевести 10 долларов на счет Оскара) = 250e62ddffbdf20a0ea40d69287327e8aff58b6ad49c03dab3f714b596804dc1

Я понимаю, что Оскар хочет изменить Переведите 10 000 долларов на счет Оскара так что вывод при подключении к функции SHA-256 дает тот же результат, что и выше. Но что они означают, что злоумышленник может «изменить или нет» 64 местоположения, и как это «изменить или нет» дает $2^{64}$ версии одного и того же сообщения?

kelalaka avatar
флаг in
`Пустые пространства, для чего мы живем`, кроме веселья, разве не ясно? добавьте 64 пробела или табуляции, чтобы изменить 64 возможные позиции. Тогда у вас есть объем данных, аналогичный атаке дня рождения, которая имеет вероятность успеха 1/2.
Slim Shady avatar
флаг cn
@kelalaka извините, я новичок в космосе, поэтому мне это непонятно.
kelalaka avatar
флаг in
Нажмите «пробел» на клавиатуре, что вы видите?
Slim Shady avatar
флаг cn
@kelalaka изменение вывода хеш-функции. Это ясно для меня. Я знаю, что теоретически мы можем расположить $x_2$ так, чтобы его хэш-вывод был таким же, как $x_1$. Это все, что я знаю
kelalaka avatar
флаг in
Кстати, как называется книга?
Рейтинг:3
флаг in

В цитируемом тексте вроде бы говорится о нахождении коллизии 128-битной хэш-функции с атакой Birthday. В атаке на день рождения человек создает вокруг $\sqrt{2^{128}} = 2^{64}$ сообщения так, чтобы они ожидали найти сталкивающуюся пару с вероятностью 1/2.

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

$x_1$= Переведите 10 долларов на счет Оскара
$x_2$= Переведите 10 000 долларов на счет Оскара

Чтобы создать $2^{64}$ сообщения, можно использовать невидимые символы, такие как пространство и вкладка. Если вы добавите 64 символа к $x_1$ или же $x_2$ это либо вкладка, либо пробел, тогда вы можете получить 64 местоположения. Это делает $2^{64}$ сообщения, имеющие одинаковое значение с высокими, вероятно, разными хэшами.

Эта невидимая модификация применяется как $x_1$ и $x_2$.

Создать $2^{64}$ разные строки для $x_1$ и $x_2$ и объединить их в набор. В этом наборе мы ожидаем столкновения. Имейте в виду, что таким образом у нас может возникнуть коллизия внутри варианта $x_1$ (или же $x_2$).

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

Другие примеры использования хеш-коллизии в реалистичных атаках см. в этом вопросе;


Атака столкновения против второй атаки предварительного изображения

в атака столкновением мы ищем два сообщения $m_1$ и $m_2$ с $m_1 \neq m_2$ такой $ч(м_1) = ч(м_2)$. При атаке столкновением злоумышленник может свободно выбирать значение хеш-функции, он ищет только два сообщения с одинаковым значением хеш-функции. Эта свобода снижает стоимость атаки. Общая стоимость столкновения $\mathcal{O}(\sqrt{2^{n/2}})$-время для $n$-битная выходная хэш-функция.

В некоторых других сценариях злоумышленнику необходимо вторая атака предварительного изображения; дано сообщение $м$ и это хэш-значение $х=ч(м)$, найти другое сообщение $м'\neq м$ такой, что $ч(м)=ч(м')$. Это сценарий, в котором злоумышленник создает подделку цифровой подписи (хэш и знак). Учитывая подпись, они пытаются найти другое сообщение $м'$ так что подпись совпадает с данной.

Две общие затраты на вторичную атаку прообраза составляют $\mathcal{O}(\sqrt{2^n})$-время для $n$-битная хеш-функция.

Формальные определения можно найти в

jjj avatar
флаг cn
jjj
Я не думаю, что они говорят о нападении на день рождения. Одно сообщение кажется фиксированным, в противном случае можно было бы изменить оба в 64 позициях, сделав каждое из 2^64 разных версий. Также атака имеет смысл только тогда, когда x1 каким-то образом авторизован (например, хэш был подписан).
kelalaka avatar
флаг in
@jjj говорится в текстах (изменение двух сообщений), и я привел простой аргумент, чтобы объединить все варианты $x_1$ и $x_2$ в набор и искать коллизию как привязку к дню рождения. Если один зафиксирован, то это вторичная атака прообраза. Разве я не сказал решетку и знак?
jjj avatar
флаг cn
jjj
О, пропустил это. Я все еще думаю, что стоит упомянуть, что для этого примера обычно будет заданный хэш и, следовательно, одно фиксированное сообщение.
kelalaka avatar
флаг in
@jjj теперь лучше?
Рейтинг:2
флаг in

Кому: ["The",""] First International Bank ["Панама",""] Тема: ["Деньги",""] ["Перевод","Перевод"] ["Заказ",""] с моего счета ["Число","#"]1234[".",""]

Я ["услышал", "хотел бы"] Поручить ["вам",""] ["перевести","перевести","переместить"] ["сумму","сумму"] [" один миллион","1,000,000"] ["USD","$"] на ["The following",""] счет ["num","#"] 3456.

и т. д. Это выше имеет "$2^{14}*3$" комбинации только для начала соответствующего сообщения. Без игры с пробелами.

kelalaka avatar
флаг in
Отлично, языковое решение.
dave_thompson_085 avatar
флаг cn
Слово, обычно используемое там в английском языке, не «услышать», а «настоящим» (также не «здесь»). Но это (оба!) были бы вероятными ошибками, которые вы могли бы использовать для создания эквивалентных текстов.
Рейтинг:0
флаг kz

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

Если я возьму «отправить 10 000» и добавлю 64 символа, каждый из которых представляет собой либо пробел, либо символ табуляции, то я получу ровно 2 ^ 64 разных сообщения. И с 64-битным хэшем есть большая вероятность, что одно из этих сообщений имеет тот же хэш-код, что и сообщение «отправить 10».

Причина добавления пробела или табуляции, а не просто любого символа, заключается в том, что читатель не увидит эти символы. Если бы я получил «Отправить 10 000 xlfe13^», я бы заподозрил неладное.

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

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