Geodesic
On the mean value of the total length of chains computed during the additional checkings in the tradeoff method with distinguished points
Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 1, pp. 101-136 
D. V. Pil'shchikov. On the mean value of the total length of chains computed during the additional checkings in the tradeoff method with distinguished points. Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 1, pp. 101-136. http://geodesic.mathdoc.fr/item/MVK_2022_13_1_a4/
@article{MVK_2022_13_1_a4,
     author = {D. V. Pil'shchikov},
     title = {On the mean value of the total length of chains computed during the additional checkings in the tradeoff method with distinguished points},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {101--136},
     year = {2022},
     volume = {13},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2022_13_1_a4/}
}
TY  - JOUR
AU  - D. V. Pil'shchikov
TI  - On the mean value of the total length of chains computed during the additional checkings in the tradeoff method with distinguished points
JO  - Matematičeskie voprosy kriptografii
PY  - 2022
SP  - 101
EP  - 136
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2022_13_1_a4/
LA  - ru
ID  - MVK_2022_13_1_a4
ER  - 
%0 Journal Article
%A D. V. Pil'shchikov
%T On the mean value of the total length of chains computed during the additional checkings in the tradeoff method with distinguished points
%J Matematičeskie voprosy kriptografii
%D 2022
%P 101-136
%V 13
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2022_13_1_a4/
%G ru
%F MVK_2022_13_1_a4

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

Time-memory balancing methods are used to solving the problem of inverting a one-way function. Balancing with distinguished points and non-perfect tables is well-known variant of such methods. Recently Hong and Moon had presented an estimate of the mean total length of chains calculated during additional checks. Here we generalize this result. We describe a theoretical probabilistic model within which a two-sided estimates of the specified value are obtained. The results obtained are applicable under any conditions on the length of the main chain, under any rules for breaking an additional chain, and for one-way functions with atypical properties. Also our results allow to identify the set of values of the method parameters, where the resulting estimates remain fairly accurate.

[1] Hellman M., “A cryptanalytic time-memory tradeoff”, IEEE Trans. Inf. Theory, IT-26:4 (1980), 401–406 | DOI | MR | Zbl

[2] Denning D., Cryptography and Data Security, Addison-Wesley, Boston, Massachusetts, USA, 1982, 100 pp. | Zbl

[3] Oechslin Ph., “Making a faster cryptanalytic time-memory tradeoff”, CRYPTO'03, Lect. Notes Comput. Sci., 2729, Springer-Verlag, 617–630 | DOI | MR | Zbl

[4] Biryukov A., Shamir A., Wagner D., “Real time cryptanalysis of A5/1 on a PC”, FSE 2000, Lect. Notes Comput. Sci., 1978, Springer-Verlag, 1–18 | MR | Zbl

[5] Saarinen M-J. O., “A time-memory tradeoff attack against LILI-128”, FSE 2002, Lect. Notes Comput. Sci., 2365, 231–236 | DOI | Zbl

[6] Mentens N., Batina L., Preneel B., Verbauwhede I., “Cracking Unix passwords using FPGA platforms”, ECRYPT Workshop, SHARCS — Special Purpose Hardware for Attacking Cryptographic Systems, 2005, 83–91 | MR

[7] Bono S., Green M., Stubblefield A., Juels A., Rubin A., M. Szydlo, “Security analysis of a cryptographically-enabled RFID device”, USENIX'05, 1–16

[8] Kusuda K., Matsumoto T., “Optimization of time-memory tradeoff cryptanalysis and its application to DES, FEAL-32 and Skipjack”, IEICE Trans. Fundamentals, E79-A:1 (1996), 35–48

[9] Borst J., Preneel B., Vandewalle J., “On the time-memory tradeoff between exhaustive key search and table precomputation”, Proc. 19th Symp. Inf. Theory in the Benelux, 1998, 111–118

[10] Borst J., Block ciphers: design, analysis, and side-channel analysis, Ph.D. Thesis, Katholieke Univ. Leuven, 2001

[11] Standaert F.-X., Rouvroy G., Quisquater J.-J., Legat J.-D., “A time-memory tradeoff using distinguished points: New analysis FPGA results”, CHES 2002, Lect. Notes Comput. Sci. 2523, Springer, 2003, 593–609 | DOI

[12] Saran A. N., Time memory tradeoff attack on symmetric ciphers, Ph.D. Thesis, Middle East Techn. Univ., 2009

[13] Hong J., Moon S., “A comparison of cryptanalytic tradeoff algorithms”, J. Cryptology, 26 (2013), 559–637 | DOI | MR | Zbl

[14] Hoch Y. Z., Security analysis of generic iterated hash functions, Ph.D. Thesis, Weizmann Inst. Sci., 2009 | MR

[15] Shamir A., “Random graphs in security and privacy”, Invited talk, ICITS 2009

[16] Pilschikov D. V., “Ob odnom teoretiko-veroyatnostnom podkhode k obosnovaniyu nadezhnosti metoda Khellmana”, Matematicheskie voprosy kriptografii, 10:1 (2019), 83–114 | MR