OBAKE Cryptanalysis:

Timing

Analysis

This type of attack (considered a "side-channel attack") is based on the time that each instruction takes to be executed, thus being able to determine results that are even quite accurate in relation to the keys used during encryption. This type of attack presupposes a series of variables that are involved: CPU type and speed, algorithm design, instructions used, optimization made by compilers, measures and countermeasures, capacity and measurement accuracy, leakage of electromagnetic signals, generation of electromagnetic noise, among others. That's why it's so difficult to adequately protect the algorithm against it!

Even AES (American Encryption Standard) and other algorithms considered mathematically secure are vulnerable to this attack (as shown here), while neither XSalsa20 nor ChaCha20 are. The main reason is based on the algorithm intrinsics: extended usage of S-Boxes/P-Boxes, usage of complex math mnemonics (as PoW or SQRT), extended

To avoid, as much as allowed, OBAKE-512 implements some effective measures if we keep this attack in mind, in terms of time leveling and false time measures, as we will see next. The goal: to try to make the code give no clues among its various functions and rounds:

• Comparisons without Escape: the most usual way to execute a conditional LOOP is to provide the output according to some "true" or "false" condition, and this condition enables and facilitates this kind of attack. OBAKE, within the possible and feasible and in the critical routines, performs LOOPs without such conditions, criticizing at the end an established numeric result for true. This way, we always guarantee the same execution time, not giving the attacker the opportunity to know if a certain condition (or value) was reached.

• Parallel processing: OBAKE-512 works fundamentally in "multithread" mode and using parallelism (using CPU cores in parallel), causing deep and random changes in the parameters that are monitored in this type of attack. In other words, this makes this attack impossible during the generation and/or application of the keys, since the parallel mode generates randomic time differences in the running blocks.

• Ghost-Code: OBAKE application and its algorithm OBAKE-512 utilize a lot of portions of code and variables that have no practical use and aim only to confuse disassemblers and monitoring tools based on time (like this attack), without concrete damage to performance and reliability. These codes are randomly executed, significantly impacting this attack and others derived from it.

Even thought we have not performed this attack in practice, we are certain that the above procedures can protect the application and algorithm against this type of attack.

Bibliographic references

H.C.A. Tilborg et al., "Encyclopedia of Cryptography and Security", H. C. A. v. Tilborg Ed., SpringerScience+Business Media LLC, 2011.

P. Kocher, Paul (1996). “Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems” Advances in Cryptology—CRYPTO’96, Lecture Notes in Computer Science, vol. 1109, ed. N. Koblitz. Springer-Verlag, Berlin, 1996

D. Gullasch, E. Bangerter, S. Krenn, "Cache Games – Bringing Access-Based Cache Attacks on AES to Practice", IEEE Symposium on Security and Privacy 0, 2011

J. Bonneau, I. Mironov, "Cache-Collision Timing Attacks against AES", In Cryptographic Hardware and Embedded Systems—CHES 2006 vol. 4249 of

Springer LNCS, Springer, 2006

D.J. Bernstein, "AES Cache Timing Attack", 2005 -  http://cr.yp.to/antiforgery/cachetiming-20050414.pdf

D.J. Bernstein,"Cache-timing attacks on AES", 2004 - http://cr.yp.to/papers.html#cachetiming

P. Kocher, “Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems,” Advances in Cryptology—CRYPTO’96, Santa Barbara, CA, Lecture Notes in Computer Science, vol. 1109, ed. N. Koblitz. Springer, Berlin, 1996