Потоковый шифр
Требуется сделать потоковый шифр с такими свойствами:
1. Минимально необходимый обьем состояния.
2. 256-битная необратимость функции. То есть если противник завладел полным состоянием шифра в момент i, то ему потребуется 2^256 работы чтобы получить состояние шифра в момент i-1.
3. 256-битная стойкость к раскрытию по известной гамме шифра.
4. Гарантированный минимальный период 2^128.
Берем блочный шифр F(Key,X) c 64-битным блоком X и 128 битным ключом K. Берем хеш функцию H(X,Y) с размером 256 бит. Берем некую машину состояний M шириной 128 бит с полным периодом; возможно некриптостойкую (LSFR, LCG или даже последовательность Вейля). Состояние шифра = (M,X) = состояние машины + состояние хеш функции. Состояние [0] начально инициализируется неким криптостойким способом из исходного ключа и IV.
На каждом шаге делается:
1. Переход в новое состояние машины M[i+1] из M[i]
2. Хеширование X[i+1] = H(X[i],M[i+1])
3. Берем какие-то 128 бит из 256-битного X[i+1] как ключ K.
4. Делим 128-битное состояние M на 2 x 64 bit и берем их как X0,X1.
5. Генерируем два выходных 64-битных значения Y0 = F(K, X0), Y1 = F(K, X1). (Y0,Y1) – гамма шифра.
Если противник завладел состоянием шифра, то для прокручивания шифра назад ему придется находить прообразы для 256-битной хеш функции.
Если противник завладел гаммой шифра, то для восстановления cостояния (M,X) ему нужно 2^256 работы.
Итого имеем 256-битную стойкость при 384-битном состоянии; при условии что хеш функция и шифр идеальны. Для получения 128 бит гаммы требуется два выполнения шифра и одно выполнение хеш функции.
Покритикуйте предложенную схему.
В приведенной функции сдвиг и минус равнозначны умножению на 127 по модулю 2^64.
Учесть UINT64-представление отрицательных чисел (, +1 можно пренебречь) – по одному биту перебора на каждый байт.
А если бы было >> 7 (и на выход – младший байт), удалось бы алгебраически задать обратную функцию?
Можно не писать обратную функцию. Достаточно отбрутфорсить 14 бит + 2 возможных переноса на каждом шагу, чтобы получить все варианты для старших 14 битов из 56 неизвестных битов.
Делаем следующий такой же шаг брутфорса. В результате имеем 2^13 возможных вариантов для старших 28 битов seed. Неопределенность сократилась до 2^41. Можно не думать; дальше брать перебором.
Находим seed примерно за час работы обычного компа. Решение "в лоб" по принципу "разделяй и властвуй".
Если вместо перебора выписать обратные функции для нахождения возможных вариантов сразу, то решение найдется за доли секунды; но для игрушечного шифра сойдет и так.