Geodesic
Improving OBDD attacks against stream ciphers
Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 137-151 
M. Hamann; M. Krause; A. Moch. Improving OBDD attacks against stream ciphers. Matematičeskie voprosy kriptografii, Tome 11 (2020) no. 2, pp. 137-151. http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a10/
@article{MVK_2020_11_2_a10,
     author = {M. Hamann and M. Krause and A. Moch},
     title = {Improving {OBDD} attacks against stream ciphers},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {137--151},
     year = {2020},
     volume = {11},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a10/}
}
TY  - JOUR
AU  - M. Hamann
AU  - M. Krause
AU  - A. Moch
TI  - Improving OBDD attacks against stream ciphers
JO  - Matematičeskie voprosy kriptografii
PY  - 2020
SP  - 137
EP  - 151
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a10/
LA  - en
ID  - MVK_2020_11_2_a10
ER  - 
%0 Journal Article
%A M. Hamann
%A M. Krause
%A A. Moch
%T Improving OBDD attacks against stream ciphers
%J Matematičeskie voprosy kriptografii
%D 2020
%P 137-151
%V 11
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2020_11_2_a10/
%G en
%F MVK_2020_11_2_a10

Voir la notice de l'article provenant de la source Math-Net.Ru

OBDD-attacks against stream ciphers compute the secret initial state by generating a sequence of $\mathcal{O}(n)$ ordered binary decision diagrams (OBDDs) of maximal width $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$, where $n$ denotes the inner state length and $\alpha\in (0,1)$ is the compression rate of the cipher. We propose and experimentally verify the following strategy of avoiding the huge storage demand of $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$. (1) Generate in parallel two OBDDs $P$ and $Q$ such that $P \wedge Q$ has only a few satisfying assignments. (2) Compute the set $(P \wedge Q)^{-1}(1)$, containing the secret inner state, by a new breadth-first-search based algorithm. We show that this approach improves standard OBDD-attacks drastically.

[1] Babbage S.H., “Improved “exhaustive search” attacks on stream ciphers”, European Convention on Security and Detection, 1995, 161–166

[2] Bluetooth SIG, Bluetooth Core Specification 4.2, 2014 https://www.bluetooth.org/DocMan/handlers/DownloadDoc.ashx?doc_id=286439

[3] Briceno M., Goldberg I., Wagner D., A pedagogical implementation of A5/1, 1999 http://www.scard.org/gsm/a51.html

[4] Eibach T., Pilz E., Völkel G., “Attacking Bivium using SAT solvers”, SAT 2008, Lect. Notes Comput. Sci., 4996, Springer, 2008, 63–76 | DOI | Zbl

[5] Golić J. Dj., “On the security of nonlinear filter generators”, FSE 1996, Lect. Notes Comput. Sci., 1039, 1996, 173–188 | DOI | Zbl

[6] Krause M., “BDD-based cryptanalysis of keystream generators”, EUROCRYPT 2002, Lect. Notes Comput. Sci., 2332, 2002, 222–237 | DOI | MR | Zbl

[7] Krause M., Stegemann D., “Reducing the space complexity of BDD-based attacks on keystream generators”, FSE 2006, Lect. Notes Comput. Sci., 4047, 2006, 163–178 | DOI | Zbl

[8] Meier W., Staffelbach O., “The self-shrinking generator”, EUROCRYPT '94, Lect. Notes Comput. Sci., 950, 1994, 205–214 | DOI | MR

[9] Meinel C., Theobald T., Algorithms and data structures in VLSI design, Springer-Verlag, Berlin–Heidelberg, 1998, xii+268 pp. | MR

[10] Somenzi F., CUDD, Website, , 2015 (accessed on February 05, 2018) http://vlsi.colorado.edu/f̃abio/

[11] Stegemann D., “Extended BDD-based cryptanalysis of keystream generators”, SAC 2007, Lect. Notes Comput. Sci., 4876, 2007, 17–35 | DOI | Zbl

[12] Wegener I., Branching Programs and Binary Decision Diagrams: Theory and Applications, SIAM e-books, Society for Industrial and Applied Mathematics, 2000 | MR | Zbl