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

Ben Laurie <> Fri, 16 August 2013 12:35 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 8E5D221F9ADF for <>; Fri, 16 Aug 2013 05:35:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.977
X-Spam-Status: No, score=-3.977 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, GB_I_LETTER=-2, HTML_MESSAGE=0.001, NO_RELAYS=-0.001]
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id uP83FkP6d7Aq for <>; Fri, 16 Aug 2013 05:35:26 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400d:c00::22d]) by (Postfix) with ESMTP id 38DB921F9798 for <>; Fri, 16 Aug 2013 05:35:23 -0700 (PDT)
Received: by with SMTP id l18so445968qak.4 for <>; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=mk3ZGT2LfixtkGD3m8+ub5F/VkQzwO7hIw8IUnKdOjE=; b=vR9Ok+9THw6q2+eTooCUf9hBlz120GRraJTe+Pqv8HF9YXZkwDSPCSURr1p74/nj1q jWR+xCQ2ePNHZP9ZZ4b8mErPViEewaxTajPKds2H7T4bxfGg+M5NgfQFMDZoGSnpSCFP XxJ+eMNjlJ8CjbkTP5ZIVjpWFr14qo1b4NDERbz0NBmKjaW3dkhJU6weV1vt5LiYWCCw J9Qa6lr4t3IC3lktMlStyYNobbkUTfPdw1GuZEuQkIJ3jWlv+VYhQPL6Gf/RwT+fKui1 Va+Nx9L2neqnuIftNx37Wa+mRXfVVvgjeuHBe9GpeCbMdr8hpZimHaGneK/BC1vpe3Lv QzHw==
MIME-Version: 1.0
X-Received: by with SMTP id r9mr1011045qak.89.1376656522642; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
Received: by with HTTP; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
In-Reply-To: <>
References: <> <>
Date: Fri, 16 Aug 2013 08:35:22 -0400
X-Google-Sender-Auth: FCLQ8W62SKKFbXjbCq1cjYpRfTI
Message-ID: <>
From: Ben Laurie <>
To: Robert Moskowitz <>
Content-Type: multipart/alternative; boundary=001a11c2b9ea02a42e04e40fd376
Cc: "" <>
Subject: Re: [Cfrg] Fwd: Encryption is less secure than we thought - MIT News Office
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 16 Aug 2013 12:35:30 -0000

On 16 August 2013 07:44, Robert Moskowitz <> wrote:

>  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?

This seems to be restating essentially what Joe Bonneau said far more
readably a year ago:

> -------- Original Message --------
>  ** **
>   From Evernote: <>****   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 *<>first
> 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 *<>),
> 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 discussions*.*
> 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 expected*.*
> “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*.*” ****
> Comments****
>    *Log in to write comments *<>
> ****
> * *****
> _______________________________________________
> Cfrg mailing list