In the literature on provable concrete security it is standard to define 2^b security as the nonexistence of high-probability attack algorithms taking time \le 2^b. 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 2^128, 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 2^128 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 \le 2^b, 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.Category / Keywords: foundations / provable security, concrete security, algorithm cost metrics, non-uniform algorithms, non-constructive algorithms Original Publication (with major differences): IACR-ASIACRYPT-2013 Date: received 4 Jun 2012, last revised 14 Sep 2013 Contact author: tanja at hyperelliptic org Available format(s): PDF | BibTeX Citation Note: Major revision. Abbreviated version will appear at Asiacrypt 2013; this is the full version. Version: 20130914:101448 (All versions of this report) Discussion forum: Show discussion | Start new discussion