Возможно ли обратить SHA-256?

Question

[Thomash]

Есть некая программа, которая в качестве серийного номера принимает 12-значную строку, вычисляет ее хэш SHA-256 и сравнивает с эталонным хэшем (он один). Собственно, два вопроса:

1. можно ли найти серийник?
   
2. сколько серийников может быть у одного хэша SHA-256?
   

Answer 1

[throughtheether]

Возможно ли обратить SHA-256?

В общем случае это называется preimage-атакой. В таблице по ссылке указаны примерные оценки вычислительной сложности проведения подобных атак. Сложность порядка 2^128, насколько мне известно, считается достаточной для того, чтобы полагать атаку непрактичной.

можно ли найти серийник?

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

сколько серийников может быть у одного хэша SHA-256?

В вашем случае, думаю, разумно предполагать соответствие от 0 до 1 серийных номеров произвольному хэшу.

Answer 2

[Армянское Радио]

Огромное, НУ ОЧЕНЬ ОГРОМНОЕ количество - 256^12=79228162514264337593543950336 штук строк (если все символы использовать)

Но так как строка обычно в BASE64, это может быть немного меньше -
64^12=4722366482869645213696

Answer 3

[Сергей]

Количество значений, которое нужно перебрать, чтобы найти все серийники для данного хэша, равно количеству возможных значений одного знака строки в степени количества знаков в строке, т.е. в степени её длины. Если там, например, только 12 цифр, то нужно перебрать 10^12 = 1 000 000 000 000 строк. Один триллион. Если у вас есть устройство, перебирающее 1 Гх/с, то задача будет решена за 1000 секунд, то есть менее чем за 17 минут. Так что всё зависит от того, каким железом вы располагаете.