Improving OBDD attacks against stream ciphers

При атаках на поточные шифры диаграммами последовательных бинарных решений (ДПБР) секретное начальное состояние вычисляется с помощью набора из $\mathcal{O}(n)$ ДПБР максимальной ширины $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$, где $n$ — длина внутреннего состояния, а $\alpha\in (0,1)$ — степень сжатия шифра. Предложен и экспериментально проверен следующий способ обходиться без памяти большого объема $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$. (1) Строить одновременно пары таких ДПБР $P$ и $Q$, что для $P \wedge Q$ существует мало решений. (2) Вычислять множество $(P \wedge Q)^{-1}(1)$, содержащее секретное внутреннее состояние, новым алгоритмом, основанным на поиске в ширину. Показано, что этот подход существенно улучшает характеристики стандартных ДПБР-атак.