TY - GEN

T1 - Non-uniform cracks in the concrete : the power of free precomputation

AU - Bernstein, D.J.

AU - Lange, T.

PY - 2013

Y1 - 2013

N2 - AES-128, the NIST P-256 elliptic curve, DSA-3072, RSA-3072, and various higher-level protocols are frequently conjectured to provide a security level of 2128. Extensive cryptanalysis of these primitives appears to have stabilized sufficiently to support such conjectures.
In the literature on provable concrete security it is standard to define 2b security as the nonexistence of high-probability attack algorithms taking time =¿2b. However, this paper provides overwhelming evidence for the existence of high-probability attack algorithms against AES-128, NIST P-256, DSA-3072, and RSA-3072 taking time considerably below 2128, contradicting the standard security conjectures.
These attack algorithms are not realistic; do not indicate any actual security problem; do not indicate any risk to cryptographic users; and do not indicate any failure in previous cryptanalysis. Any actual use of these attack algorithms would be much more expensive than the conventional 2128 attack algorithms. However, this expense is not visible to the standard definitions of security. Consequently the standard definitions of security fail to accurately model actual security.
The underlying problem is that the standard set of algorithms, namely the set of algorithms taking time =¿2b, fails to accurately model the set of algorithms that an attacker can carry out. This paper analyzes this failure in detail, and analyzes several ideas for fixing the security definitions.

AB - AES-128, the NIST P-256 elliptic curve, DSA-3072, RSA-3072, and various higher-level protocols are frequently conjectured to provide a security level of 2128. Extensive cryptanalysis of these primitives appears to have stabilized sufficiently to support such conjectures.
In the literature on provable concrete security it is standard to define 2b security as the nonexistence of high-probability attack algorithms taking time =¿2b. However, this paper provides overwhelming evidence for the existence of high-probability attack algorithms against AES-128, NIST P-256, DSA-3072, and RSA-3072 taking time considerably below 2128, contradicting the standard security conjectures.
These attack algorithms are not realistic; do not indicate any actual security problem; do not indicate any risk to cryptographic users; and do not indicate any failure in previous cryptanalysis. Any actual use of these attack algorithms would be much more expensive than the conventional 2128 attack algorithms. However, this expense is not visible to the standard definitions of security. Consequently the standard definitions of security fail to accurately model actual security.
The underlying problem is that the standard set of algorithms, namely the set of algorithms taking time =¿2b, fails to accurately model the set of algorithms that an attacker can carry out. This paper analyzes this failure in detail, and analyzes several ideas for fixing the security definitions.

U2 - 10.1007/978-3-642-42045-0_17

DO - 10.1007/978-3-642-42045-0_17

M3 - Conference contribution

SN - 978-3-642-42044-3

VL - 3

T3 - Lecture Notes in Computer Science

SP - 321

EP - 340

BT - Advances in Cryptology - ASIACRYPT 2013 (19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013

A2 - Sako, K.

A2 - Sarkar, P.

PB - Springer

CY - Berlin

ER -