[Cfrg] Fwd: Encryption is less secure than we thought - MIT News Office

Robert Moskowitz <rgm-sec@htt-consult.com> Fri, 16 August 2013 11:45 UTC

Return-Path: <rgm-sec@htt-consult.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 1ACAA21F9A81 for <cfrg@ietfa.amsl.com>; Fri, 16 Aug 2013 04:45:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.739
X-Spam-Status: No, score=-2.739 tagged_above=-999 required=5 tests=[BAYES_20=-0.74, GB_I_LETTER=-2, HTML_MESSAGE=0.001]
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id ok9nBAEYnIyM for <cfrg@ietfa.amsl.com>; Fri, 16 Aug 2013 04:45:19 -0700 (PDT)
Received: from klovia.htt-consult.com (klovia.htt-consult.com [IPv6:2607:f4b8:3:0:218:71ff:fe83:66b9]) by ietfa.amsl.com (Postfix) with ESMTP id A343B21F944C for <cfrg@irtf.org>; Fri, 16 Aug 2013 04:45:12 -0700 (PDT)
Received: from localhost (unknown []) by klovia.htt-consult.com (Postfix) with ESMTP id BA7CA62A77 for <cfrg@irtf.org>; Fri, 16 Aug 2013 11:45:04 +0000 (UTC)
X-Virus-Scanned: amavisd-new at localhost
Received: from klovia.htt-consult.com ([]) by localhost (klovia.htt-consult.com []) (amavisd-new, port 10024) with ESMTP id mXksfx2M0TV2 for <cfrg@irtf.org>; Fri, 16 Aug 2013 07:44:52 -0400 (EDT)
Received: from lx120e2.htt-consult.com (lx120e2.htt-consult.com []) (Authenticated sender: rgm-sec@htt-consult.com) by klovia.htt-consult.com (Postfix) with ESMTPSA id 88EB562A64 for <cfrg@irtf.org>; Fri, 16 Aug 2013 07:44:52 -0400 (EDT)
Message-ID: <520E10A2.2030908@htt-consult.com>
Date: Fri, 16 Aug 2013 07:44:34 -0400
From: Robert Moskowitz <rgm-sec@htt-consult.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:17.0) Gecko/20130625 Thunderbird/17.0.7
MIME-Version: 1.0
To: cfrg@irtf.org
References: <32A53FD55709804D8533DD5D308A40A216B2F1A1CC@FHDP1LUMXC7V33.us.one.verizon.com>
In-Reply-To: <32A53FD55709804D8533DD5D308A40A216B2F1A1CC@FHDP1LUMXC7V33.us.one.verizon.com>
X-Forwarded-Message-Id: <32A53FD55709804D8533DD5D308A40A216B2F1A1CC@FHDP1LUMXC7V33.us.one.verizon.com>
Content-Type: multipart/alternative; boundary="------------020101030002090900000406"
Subject: [Cfrg] Fwd: Encryption is less secure than we thought - MIT News Office
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 16 Aug 2013 11:45:21 -0000

So what are the thoughts about this here?  I have been asked to do a 
little digging amongst my contacts.  Seems it clearly states that our 
secure communications stuff we do is not affected by this work, but 
perhaps secure data objects and various wireless password passing 
technologies might be at risk?

-------- Original Message --------

      From Evernote: <http://evernote.com/>

  Encryption is less secure than we thought - MIT News Office

Clipped from: 

  Encryption is less secure than we thought

For 65 years, most information-theoretic analyses of cryptographic 
systems have made a mathematical assumption that turns out to be wrong*.*

Larry Hardesty, MIT News Office

Muriel Médard is a professor in the MIT Department of Electrical 
Engineering*.* Photo: Bryce Vickmark

Information theory — the discipline that gave us digital communication 
and data compression — also put cryptography on a secure mathematical 
foundation*.* Since 1948, when the *paper that created information 
theory * 
appeared, most information-theoretic analyses of secure schemes have 
depended on a common assumption*.*

Unfortunately, as a group of researchers at MIT and the National 
University of Ireland (NUI) at Maynooth, demonstrated in a paper 
presented at the recent International Symposium on Information Theory 
(*view PDF * <http://arxiv.org/pdf/1301.6356.pdf>), that assumption is 
false*.* In a follow-up paper being presented this fall at the Asilomar 
Conference on Signals and Systems, the same team shows that, as a 
consequence, the wireless card readers used in many keyless-entry 
systems may not be as secure as previously thought*.*

In information theory, the concept of information is intimately entwined 
with that of entropy*.* Two digital files might contain the same amount 
of information, but if one is shorter, it has more entropy*.* If a 
compression algorithm — such as WinZip or gzip — worked perfectly, the 
compressed file would have the maximum possible entropy*.* That means 
that it would have the same number of 0s and 1s, and the way in which 
they were distributed would be totally unpredictable*.* In 
information-theoretic parlance, it would be perfectly uniform*.*

Traditionally, information-theoretic analyses of secure schemes have 
assumed that the source files are perfectly uniform*.* In practice, they 
rarely are, but they’re close enough that it appeared that the standard 
mathematical analyses still held*.*

“We thought we’d establish that the basic premise that everyone was 
using was fair and reasonable,” says Ken Duffy, one of the researchers 
at NUI*.* “And it turns out that it’s not.” On both papers, Duffy is 
joined by his student Mark Christiansen; Muriel Médard, a professor of 
electrical engineering at MIT; and her student Flávio du Pin Calmon*.*

The problem, Médard explains, is that information-theoretic analyses of 
secure systems have generally used the wrong notion of entropy*.* They 
relied on so-called Shannon entropy, named after the founder of 
information theory, Claude Shannon, who taught at MIT from 1956 to 1978*.*

Shannon entropy is based on the average probability that a given string 
of bits will occur in a particular type of digital file*.* In a 
general-purpose communications system, that’s the right type of entropy 
to use, because the characteristics of the data traffic will quickly 
converge to the statistical averages*.* Although Shannon’s seminal 1948 
paper dealt with cryptography, it was primarily concerned with 
communication, and it used the same measure of entropy in both 

But in cryptography, the real concern isn’t with the average case but 
with the worst case*.* A codebreaker needs only one reliable correlation 
between the encrypted and unencrypted versions of a file in order to 
begin to deduce further correlations*.* In the years since Shannon’s 
paper, information theorists have developed other notions of entropy, 
some of which give greater weight to improbable outcomes*.* Those, it 
turns out, offer a more accurate picture of the problem of codebreaking*.*

When Médard, Duffy and their students used these alternate measures of 
entropy, they found that slight deviations from perfect uniformity in 
source files, which seemed trivial in the light of Shannon entropy, 
suddenly loomed much larger*.* The upshot is that a computer turned 
loose to simply guess correlations between the encrypted and unencrypted 
versions of a file would make headway much faster than previously 

“It’s still exponentially hard, but it’s exponentially easier than we 
thought,” Duffy says*.* One implication is that an attacker who simply 
relied on the frequencies with which letters occur in English words 
could probably guess a user-selected password much more quickly than was 
previously thought*.* “Attackers often use graphics processors to 
distribute the problem,” Duffy says*.* “You’d be surprised at how 
quickly you can guess stuff*.*”

In their Asilomar paper, the researchers apply the same type of 
mathematical analysis in a slightly different way*.* They consider the 
case in which an attacker is, from a distance, able to make a “noisy” 
measurement of the password stored on a credit card with an embedded 
chip or a key card used in a keyless-entry system*.*

“Noise” is the engineer’s term for anything that degrades an 
electromagnetic signal — such as physical obstructions, out-of-phase 
reflections or other electromagnetic interference*.* Noise comes in lots 
of different varieties: The familiar white noise of sleep aids is one, 
but so is pink noise, black noise and more exotic-sounding types of 
noise, such as power-law noise or Poisson noise*.*

In this case, rather than prior knowledge about the statistical 
frequency of the symbols used in a password, the attacker has prior 
knowledge about the probable noise characteristics of the environment: 
Phase noise with one set of parameters is more probable than phase noise 
with another set of parameters, which in turn is more probable than 
Brownian noise, and so on*.* Armed with these statistics, an attacker 
could infer the password stored on the card much more rapidly than was 
previously thought*.*

“Some of the approximations that we’re used to making, they make perfect 
sense in the context of traditional communication,” says Matthieu Bloch, 
an assistant professor of electrical and computer engineering at the 
Georgia Institute of Technology*.* “You design your system in a 
framework, and then you test it*.* But for crypto, you’re actually 
trying to prove that it’s robust to things you cannot test*.* So you 
have to be sure that your assumptions make sense from the beginning*.* 
And I think that going back to the assumptions is something people don’t 
do often enough*.*”

Bloch doubts that the failure of the uniformity assumption means that 
cryptographic systems in wide use today are fundamentally insecure*.* 
“My guess is that it will show that some of them are slightly less 
secure than we had hoped, but usually in the process, we’ll also figure 
out a way of patching them,” he says*.* The MIT and NUI researchers’ 
work, he says, “is very constructive, because it’s essentially saying, 
‘Hey, we have to be careful*.*’ But it also provides a methodology to go 
back and reanalyze all these things*.*”



*Log in to write comments *