Обратимы ли функции S0, S1, E0, E1 из алгоритма SHA-256?

Question

[Денис]

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

Например, найти функцию F, которая будет удовлетворять условию X=F(S0(X))

Ответы желательно аргументировать.
Спасибо заранее.

Comments

[sim3x]

как заголовок связан с текстом вопроса?

[Денис]

я точно не знаю, но наверное логикой.

[sim3x]

Денис: не вижу между ними связи - дополни вопрос своими размышлениями, по поводу их связи

[Денис]

Хорошо. На примере S0
Есть функция Y=S0(X),
Так вот, хотелось бы знать, есть ли такая функция для S0, чтобы X=F(Y),
А вот про S0, это советую поглядеть в описание SHA256

[Денис]

sim3x: Даже по другому: Надо найти функцию F, которая будет удовлетворять условию X=F(S0(X))

[Денис]

sim3x: Без сарказма благодарю за семантику, но вопрос все таки остается в силе.

Answer 1

[Veliant]

Как пример S0
rol(x, 25) ^ rol(x, 14) ^ (x >> 3)

rol обратим, xor обратим, сдвиг вправо не обратим. т.е. << (сдвиг влево) даст число с нулевыми младшими битами. Так что само выражением не обратимо

Comments

[Денис]

Но там два rol и один shr. То-есть после двух rol значение не исчезает, а в shr тоже все биты известны. Может быть есть все таки надежда, что обратимость имеется?

[jcmvbkbc]

> xor обратим
Veliant каким образом обратим xor? Возьмём пример ещё проще: y= x ^ rol(x, 1). y[0] = x[0] ^ x[31]. y[31] = x[31] ^ x[30]. .... Как нам знание y поможет однозначно восстановить x?

[jcmvbkbc]

Т.е. в приведённом примере y = 0 можно получить из x = 0 и из x = 0xffffffff, и любое другое значение y с чётным числом единичных битов можно получить из двух различных x, а результат с нечётным числом единичных битов в y вообще невозможно получить.

[Veliant]

jcmvbkbc: Ваша правда. Xor не всегда обратим. Что касательно примера, то Y будет содержать 1 биты в тех позициях, где происходит смена с 1 на 0 либо с 0 на 1 (это именно если сдвиг на 1 в любую сторону). Т.е. каждое Y будет иметь два варианта X

Answer 2

[Андрей]

Аналогичная (в терминах четности сдвигов) S0 16-разрядная функция оказалась биективной.
При этом изменение четности приводит к нарушению биекции (как описано у jcmvbkbc выше)

Обновление:
1) чтобы проверить обратимость - необходимо построить двоичную матрицу 32х32, соответствующую данному преобразованию (в GF(2)), и посчитать ее ранг; если операция обратима, то ранг должен получиться равным 32;
2) чтобы построить обратную функцию - обратить полученную в п.1 матрицу.

Comments

[Денис]

То-есть, если сказать другими словами, эти функции не обратимы и нет никакой возможности, получить X, при известном Y. Я правильно понял?

[Андрей]

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

[Андрей]

Денис , зачем Вы приглашаете меня как эксперта, если я уже вчера написал в этом вопросе ответ ? ;-)

Answer 3

[jcmvbkbc]

Обратимы ли функции S0, S1, E0, E1 из алгоритма SHA-256?

Σ0 ( A ) = ( A ⋙ 2 ) ⊕ ( A ⋙ 13 ) ⊕ ( A ⋙ 22 ) -- обратима.
Σ1 ( E ) = ( E ⋙ 6 ) ⊕ ( E ⋙ 11 ) ⊕ ( E ⋙ 25 ) -- тоже обратима.
Что такое E0 и E1 я не нашёл.

Таблицу всех значений S0 и S1 можно построить за несколько минут, если есть свободных 16Г памяти. Все они различны, т.е. обратное преобразование однозначно.
Можно ли найти простую обратную функцию -- непонятно.

Comments

[Денис]

Σ0 и Σ1 это и есть E0 и Е1. Могу точно сказать, они обратимы. Есть расчеты, но нет доказательств. А нужны именно доказательства.
И расчеты не перебором, а имеется функция, x=F(E0(x))

[jcmvbkbc]

> нет доказательств. А нужны именно доказательства.
Проверка уникальности значений функции для всех возможных значений аргумента -- это доказательство обратимости. Я выполнил эту проверку для Σ0 и Σ1.

[jcmvbkbc]

> Есть расчеты, но нет доказательств.... И расчеты не перебором, а имеется функция, x=F(E0(x))
Денис: Непонятно, что ты хочешь этим сказать. Есть функция F но нет доказательства того что она обратная?

[Денис]

У меня есть функция, которая удовлетворяет всем условиям. И не перебором. Значит все эти функции обратимые. Но мне надо это доказать научным языком, а не просто "вот посмотрите, это так, и ни как по другому".

[jcmvbkbc]

Денис: почему было бы сразу так и не написать в вопросе?

[jcmvbkbc]

И чем плох перебор в качестве доказательства?

[Денис]

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

[Денис]

jcmvbkbc: перебор - это ОЧЕНЬ медленно

[jcmvbkbc]

Денис: какое отношение обратимость этих функций (так, кстати, и непонятно, что именно за функции вы обозначили какими буквами. в коде sha-2 есть две функции с одним параметром и несколько функций с несколькими параметрами, которые точно необратимы) имеет к существованию sha256?

[jcmvbkbc]

> перебор - это ОЧЕНЬ медленно
Денис: перебор -- это 3 минуты на подготовку, а потом -- одно обращение в массив для вычисления обратного значения.

[Денис]

jcmvbkbc: Названия функций я брал с Вики. В RFC они обозначены по-другому:
BSIG0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x)
BSIG1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x)
SSIG0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x)
SSIG1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x)

Ну а отношение к sha256 они имеют прямое. Они же участвуют в расчете значения хеша.
И про перебор. Параметр у этих функций 32-х битный. И результат тоже. Значит на на поиск одного значения требуется максимум 2^32 итераций.
Есть другой вариант - хранение заранее рассчитанных результатов в отдельном массиве и потом выборка из него. Но массив получится размером 2^32 * 4 байт. А это 15 гигабайт. Хранение такого массива - это большая роскошь. Ну по крайней мере на мой взгляд.

[Андрей]

Коллеги, операции ROTR, SHR и XOR линейны по модулю "2". Если мы проверили, что используемая их комбинация биективна, то следовательно, существует невырожденная обратная матрица 32х32, умножением на которую обращается любое полученное значение. Вычислить ее можно например в Wolfram-е

[Андрей]

P.S. На всякий случай : из того, что функции S0, S1, E0, E1 окажутся обратимыми никоим образом не следует уязвимость к коллизиям первого или второго рода самой SHA-256.

[Андрей]

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

[jcmvbkbc]

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

[Денис]

jcmvbkbc: Да. Согласен. Я тоже не вижу никакой зависимости обратимости этих функций, к уязвимости SHA256.

[Денис]

Андрей: У меня получилось "найти" эту функцию. Матрицы действительно есть. 32x32.
Может быть найти - это сильно сказано. Я не большой специалист в математике. Уверен, что эти функция где-то уже описана.
В общем то вот сама функция (на Java):
public static int arcFn(int a, int[] matrix) {
int retVal = 0;
for (int i = 0; i < matrix.length; i++) {
retVal ^= Operations.rotateRight(a, i) & matrix[i];
}
return retVal;
}