Re: [Cfrg] Fwd: Encryption is less secure than we thought - MIT News Office
Ben Laurie <ben@links.org> Fri, 16 August 2013 12:35 UTC
Return-Path: <benlaurie@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8E5D221F9ADF for <cfrg@ietfa.amsl.com>; Fri, 16 Aug 2013 05:35:30 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.977
X-Spam-Level:
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 mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uP83FkP6d7Aq for <cfrg@ietfa.amsl.com>; Fri, 16 Aug 2013 05:35:26 -0700 (PDT)
Received: from mail-qa0-x22d.google.com (mail-qa0-x22d.google.com [IPv6:2607:f8b0:400d:c00::22d]) by ietfa.amsl.com (Postfix) with ESMTP id 38DB921F9798 for <cfrg@irtf.org>; Fri, 16 Aug 2013 05:35:23 -0700 (PDT)
Received: by mail-qa0-f45.google.com with SMTP id l18so445968qak.4 for <cfrg@irtf.org>; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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 10.224.80.9 with SMTP id r9mr1011045qak.89.1376656522642; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
Sender: benlaurie@gmail.com
Received: by 10.49.4.227 with HTTP; Fri, 16 Aug 2013 05:35:22 -0700 (PDT)
In-Reply-To: <520E10A2.2030908@htt-consult.com>
References: <32A53FD55709804D8533DD5D308A40A216B2F1A1CC@FHDP1LUMXC7V33.us.one.verizon.com> <520E10A2.2030908@htt-consult.com>
Date: Fri, 16 Aug 2013 08:35:22 -0400
X-Google-Sender-Auth: FCLQ8W62SKKFbXjbCq1cjYpRfTI
Message-ID: <CAG5KPzw2ASbKGRyGFoFnoL1GdnyZSqgBLzaj6XWzE5Ks75NE5A@mail.gmail.com>
From: Ben Laurie <ben@links.org>
To: Robert Moskowitz <rgm-sec@htt-consult.com>
Content-Type: multipart/alternative; boundary="001a11c2b9ea02a42e04e40fd376"
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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 12:35:30 -0000
On 16 August 2013 07:44, Robert Moskowitz <rgm-sec@htt-consult.com> 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: http://www.jbonneau.com/doc/B12-IEEESP-analyzing_70M_anonymized_passwords.pdf . > > > -------- Original Message -------- > > ** ** > > From Evernote: <http://evernote.com/>**** Encryption is less secure > than we thought - MIT News Office**** > > Clipped from: * > http://web.mit.edu/newsoffice/2013/encryption-is-less-secure-than-we-thought-0814.html > *<http://web.mit.edu/newsoffice/2013/encryption-is-less-secure-than-we-thought-0814.html> > **** > 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 *<http://web.mit.edu/newsoffice/2010/explained-shannon-0115.html>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 *<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 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 *<http://web.mit.edu/newsoffice/login.html?articleId=19117&articleItemid=96> > **** > > * ***** > > > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > >
- [Cfrg] Fwd: Encryption is less secure than we tho… Robert Moskowitz
- Re: [Cfrg] Fwd: Encryption is less secure than we… Ben Laurie
- Re: [Cfrg] Fwd: Encryption is less secure than we… Dan Brown
- Re: [Cfrg] Fwd: Encryption is less secure than we… David Jacobson
- Re: [Cfrg] Fwd: Encryption is less secure than we… David McGrew