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

From: Robert Moskowitz <[email-masked]>
Date: Fri, 16 Aug 2013 07:44:34 -0400

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: 
*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>

**

---

From: Ben Laurie <[email-masked]>
Date: Fri, 16 Aug 2013 08:35:22 -0400

On 16 August 2013 07:44, Robert Moskowitz <[email-masked]> wrote:

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

>  ** **
>   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****
>
>
> ****
>
> 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
> 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*.*
>
> that it would have the same number of 0s and 1s, and the way in which they
> were distributed would be totally unpredictable*.* In
> “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*.*
>
> 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*.*
>
> 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*.*
>
> relied on the frequencies with which letters occur in English words could
> probably guess a user-selected password much more quickly than was
> distribute the problem,” Duffy says*.* “You’d be surprised at how quickly
> you can guess stuff*.*”
>
> measurement of the password stored on a credit card with an embedded chip
> or a key card used in a keyless-entry system*.*
>
> 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*.*
>
> 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*.*”
>
> 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
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>
>

---

From: Dan Brown <[email-masked]>
Date: Fri, 16 Aug 2013 15:38:22 +0000

Cryptographers on this list, and cryptographic implementers in general,
should be aware of at least NIST SP 800-90{A,B,C}.

I agree with the article(s) that 

a) parts of industry pay inadequate attention to the randomness on which
keys rely.  Some examples are failed RNGs leading to security
vulnerabilities are well known.

b) assumptions about uniform distribution of keys, e.g. provable security is
common (but I view this as forgivable from the standpoint of modular design)

c) the common perpetuation of the misconception to use Shannon entropy for
crypto may have contributed, or risk contributing, to overestimates of
entropy

I am baffled by (or else misunderstand) the news article stating that
cryptographers assume that content files are assumed to be perfectly.  I
never came across such an assumption: often encryption papers assume that
the plaintext is highly biased, and intended to work properly under a biased
message, and uniform key.

The problem of true randomness is difficult, both philosophically and
technically.  Many have written on the subject, including me:
http://eprint.iacr.org/2011/659

I disagree with the below-cited arXiv article’s use of expected guesswork:
see Remark 3.15 of my own eprint above.

Best regards,

Dan

From: [email-masked] [mailto:[email-masked]] On Behalf Of Ben
Laurie
Sent: Friday, August 16, 2013 8:35 AM
To: Robert Moskowitz
Cc: [email-masked]
Subject: Re: [Cfrg] Fwd: Encryption is less secure than we thought - MIT
News Office

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.pd
f.

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

Clipped from:
<http://web.mit.edu/newsoffice/2013/encryption-is-less-secure-than-we-though
t-0814.html>
http://web.mit.edu/newsoffice/2013/encryption-is-less-secure-than-we-thought
-0814.html 

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

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
<http://web.mit.edu/newsoffice/2010/explained-shannon-0115.html> 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 (
<http://arxiv.org/pdf/1301.6356.pdf> 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

---

From: David Jacobson <[email-masked]>
Date: Sat, 17 Aug 2013 17:37:37 -0700

This is ancient news.  Back in 2004 I went to the NIST Workshop on 
Random Number Generation, which was convened to get reaction to a draft 
of ANSI X9.82 (about random number generation)  That draft really made 
the point that min-entropy was the preferred measure, and even had 
examples of why Shannon entropy, another one they called "guessing 
entropy", and some other one were all flawed.  The flaws were all the 
same: you could find distributions that were quite good in the measure 
in question, yet there was one value that occurred with high probability.

Personally, I'm quite fond of order-2 Renyi entropy.  There is a theorem 
that min-entropy is not less than half the order-2 Renyi entropy, so if 
the order-2 Renyi entropy is decent, you can't have terrible 
min-entropy.   I'll elaborate more on why I like order-2 Renyi entropy 
some day when I have some spare time.  But this is off-topic.

   --David Jacobson

On 8/16/13 5:35 AM, Ben Laurie wrote:
>
>
>
> On 16 August 2013 07:44, Robert Moskowitz <[email-masked] 
> <mailto:[email-masked]>> 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?
>
>
> http://www.jbonneau.com/doc/B12-IEEESP-analyzing_70M_anonymized_passwords.pdf.
>
>
>
>     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*.*
>
>     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*.*"
>
>     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*.*
>
>     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
>
>     	
>
>     [email-masked] <mailto:[email-masked]>

---

From: David McGrew <[email-masked]>
Date: Wed, 28 Aug 2013 07:38:58 -0400

Perhaps this thread could be retitled "The MIT News Office is more
effective at Marketing Communications than we thought", since they have
done a good job at getting us to discuss the work they wanted to
highlight ;-)

I agree completely with the other comments on the thread that
min-entropy is a more appropriate measure than Shannon entropy, and that
the latter is already discredited for many cryptographic applications.  

It seems that the paper is an interesting result on guesswork, and
guesswork is interesting because it applies to some (but not all)
interesting cryptographic problems.

David

On Fri, 2013-08-16 at 07:44 -0400, Robert Moskowitz wrote:
> From Evernote:
> systems have made a mathematical assumption that turns out to be
> wrong.
> 
> 
> 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.
> 
> (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.
> 
> 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.
> 
> 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.
> 
> at NUI. “And it turns out that it’s not.” On both papers, Duffy is
> 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.
> 
> 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.
> 
> with the worst case. A codebreaker needs only one reliable correlation
> begin to deduce further correlations. In the years since Shannon’s
> some of which give greater weight to improbable outcomes. Those, it
> turns out, offer a more accurate picture of the problem of
> codebreaking.
> 
> 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.
> 
> thought,” Duffy says. One implication is that an attacker who simply
> 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.”
> 
> mathematical analysis in a slightly different way. They consider the
> chip or a key card used in a keyless-entry system. 
> 
> reflections or other electromagnetic interference. Noise comes in lots
> noise, such as power-law noise or Poisson noise.
> 
> 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
> 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.”
> 
> cryptographic systems in wide use today are fundamentally insecure.
> 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 
> 
> 
>  
> 
> 
> 
> 
>