[Cfrg] counter mode block limit and confidentiality

"David A. Mcgrew" <mcgrew@cisco.com> Fri, 06 September 2002 21:08 UTC

Received: from www1.ietf.org (ietf.org [] (may be forged)) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA21551 for <cfrg-archive@odin.ietf.org>; Fri, 6 Sep 2002 17:08:23 -0400 (EDT)
Received: (from mailnull@localhost) by www1.ietf.org (8.11.6/8.11.6) id g86L9am07740 for cfrg-archive@odin.ietf.org; Fri, 6 Sep 2002 17:09:36 -0400
Received: from ietf.org (odin.ietf.org []) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id g86L9ZX07737 for <cfrg-web-archive@optimus.ietf.org>; Fri, 6 Sep 2002 17:09:35 -0400
Received: from www1.ietf.org (ietf.org [] (may be forged)) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA21543; Fri, 6 Sep 2002 17:07:53 -0400 (EDT)
Received: from www1.ietf.org (localhost.localdomain []) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id g86L8bX07676; Fri, 6 Sep 2002 17:08:37 -0400
Received: from ietf.org (odin.ietf.org []) by www1.ietf.org (8.11.6/8.11.6) with ESMTP id g86L5LX06972 for <cfrg@optimus.ietf.org>; Fri, 6 Sep 2002 17:05:21 -0400
Received: from sj-msg-core-4.cisco.com (sj-msg-core-4.cisco.com []) by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA21396 for <cfrg@ietf.org>; Fri, 6 Sep 2002 17:03:37 -0400 (EDT)
Received: from mira-sjcm-1.cisco.com (IDENT:mirapoint@mira-sjcm-1.cisco.com []) by sj-msg-core-4.cisco.com (8.12.2/8.12.2) with ESMTP id g86L4bW4015214; Fri, 6 Sep 2002 14:04:38 -0700 (PDT)
Received: from MCGREWW2K (stealth-10-34-251-98.cisco.com []) by mira-sjcm-1.cisco.com (Mirapoint) with SMTP id ACJ79271; Fri, 6 Sep 2002 13:56:18 -0700 (PDT)
From: "David A. Mcgrew" <mcgrew@cisco.com>
To: <cfrg@ietf.org>
Cc: =?iso-8859-1?Q?Mats_N=E4slund?= <mats.naslund@era.ericsson.se>
Date: Fri, 6 Sep 2002 14:04:36 -0700
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2910.0)
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4807.1700
Content-Transfer-Encoding: 7bit
Subject: [Cfrg] counter mode block limit and confidentiality
Sender: cfrg-admin@ietf.org
Errors-To: cfrg-admin@ietf.org
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.0.12
Precedence: bulk
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=unsubscribe>
List-Id: Crypto Forum Research Group <cfrg.ietf.org>
List-Post: <mailto:cfrg@ietf.org>
List-Help: <mailto:cfrg-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=subscribe>
Content-Transfer-Encoding: 7bit
Content-Transfer-Encoding: 7bit


recent discussions on the standardization of counter mode suggest that it
may be desirable to describe confidentiality-violating attacks in addition
to proofs of security based on indistinguishability.  Such attacks could
provide a better motivation for the counter mode block limit.  I've written
up a description of one such attack, though there might be better attacks or
explanations.  Comments welcome.

Thanks to Mats Naslund for discussions leading up to this writeup.



The best cryptographic definition of confidentiality is the
indistinguishability of ciphertext from random data.  For counter mode, this
definition leads to the limitation that no more than 2^64 AES blocks should
be generated with a single key [BDJR].  This limitation is well known, but
the fact that it is derived from indistinguishability rather than an attack
that violates confidentiality makes its justification somewhat unsatisfying.
A description of a confidentiality-violating attack that is possible when
this bound is violated could be useful in explaining the rationale for these
bounds.  Below we outline such an attack against AES counter mode.

Suppose that Eve has 2^64 ciphertext blocks.  She knows that the plaintext
block P corresponding to the ciphertext block C contains either the message
M0 = "ATTACK AT DAWN. " or the message M1 = "ATTACK CANCELED."   We'll call
the knowledge of such a relation a crib.  The blocks C and P are related by
C = P XOR K, where K is the keystream block corresponding to P.  Eve also
knows the value of other plaintext blocks, and thus has a set S = { K0, K1,
K2, ... } of keystream blocks.

If the value (C XOR M0) appears in the set S, then Eve knows that M0 is
*not* the true value of the plaintext P.  Because each keystream block is
distinct for each fixed key (since AES is a permutation, i.e. an invertible
function), any single keystream block value (C XOR M0) will not appear in
more than one block.  Thus the appearance of (C XOR M0) in the set S tells
Eve that the true value of the plaintext P is the message M1.  We call this
event a successful crib.

The probability of any particular value appearing in the set S is close to
2^-128, so the likelihood of her getting a plaintext value from any
particular crib is quite low.  However, Eve might well have many cribs.  If
the set S of keystream blocks known to Eve has cardinality 2^64, and Eve has
2^64 cribs, then Eve can expect to have one crib that is successful.  This
fact follows from the birthday paradox, since the product of the
cardinalities of the sets of known plaintext and cribs is close to 2^128.

This attack relies on Eve having a great amount of known plaintext, an
assumption which might be unrealistic in many practical situations.
However, the important fact here is that it *is* possible to make counter
mode be provably secure even against adversaries who have large amounts of
known plaintext, independent of the statistical distribution of the
plaintext and the adversary's knowledge of it.

In order to set an effective limit on the number of counter mode blocks that
is independent of the plaintext source and that ensures confidentiality, we
must use the limit given to us by the definition of confidentiality as
indistinguishability of ciphertext from random data.  It might be acceptable
to use a higher block limit for a system for which the plaintext
distribution is highly unpredictable (e.g. when the adversary's knowledge of
the plaintext is bounded in some well-defined way).  However, it is highly
inadvisable to use a higher block limit for a general-purpose encryption

[BDJR]  M. Bellare, A. Desai, E. JokiPii, and P. Rogaway, A Concrete
Security Treatment of Symmetric Encryption : Analysis of the DES Modes of
Operation, Proceedings of the 38th Symposium on Foundations of Computer
Science, IEEE, 1997. The revised version is available at

Cfrg mailing list