friends [entries|archive|friends|userinfo]

## Arvind Narayanan's journal

Research Blog | Web page

picayune: Dictionary.com Word of the Day [Apr. 16th, 2014|12:00 am]
 dictionary_wotd

picayune: of little value or account; small; trifling.

Mammatus Clouds over Nebraska [Apr. 16th, 2014|05:32 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140415.html

When do cloud bottoms appear like bubbles?

Schneier Speaking Schedule: April–May [Apr. 14th, 2014|07:11 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/schneier_speaki_1.html

Here's my upcoming speaking schedule for April and May:

Information about all my speaking engagements can be found here.

Schneier Talks and Interviews [Apr. 14th, 2014|09:12 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/schneier_talks.html

Here are three articles about me from the last month. Also these three A/V links.

Auditing TrueCrypt [Apr. 15th, 2014|11:56 am]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/auditing_truecr.html

Recently, Matthew Green has been leading an independent project to audit TrueCrypt. Phase I, a source code audit by iSEC Partners, is complete. Next up is Phase II, formal cryptanalysis.

Quick summary: I'm still using it.

Logical Reasoning to Detect Weaknesses About SHA-1 and MD4/5, by Florian Legendre and Gilles Dequen [Apr. 15th, 2014|07:35 am]
 iacr_eprint

http://eprint.iacr.org/2014/239

In recent years, studies about the SATisfiability Problem (short for SAT) were more and more numerous because of its conceptual simplicity and ability to express a large set of various problems. Within a practical framework, works highlighting SAT impli- cations in real world problems had grown significantly. In this way, a new field called logical cryptanalysis appears in the 2000s and consists in an algebraic cryptanalysis in a binary context thanks to SAT solving. This paper deals with this concept applied to cryptographic hash functions. We first present the logical cryptanalysis principle, and provide details about our encoding approach. In a second part, we put the stress on the contribution of SAT to analyze the generated problem thanks to the discover of logical inferences and so simplifications in order to reduce the computational complexity of the SAT solving. This is mainly realized thanks to the use as a preprocessor of learning and pruning techniques from the community. Third, thanks to a probabilistic reasoning applied on the formulas, we present a weakness based on the use of round constants to detect probabilistic relations as implications or equivalences between certain vari- ables. Finally, we present a practical framework to exploit these weaknesses through the inversions of reduced-step versions of MD4, MD5, SHA-0 and SHA-1 and open some prospects.

Automatic Proofs of Privacy of Secure Multi-Party Computation Protocols Against Active Adversaries, [Apr. 15th, 2014|07:35 am]
 iacr_eprint

http://eprint.iacr.org/2014/240

We describe an automatic analysis to check secure multiparty computation protocols against privacy leaks. The analysis is sound --- a protocol that is deemed private does not leak anything about its private inputs, even if active attacks are performed against it. Privacy against active adversaries is an essential ingredient in constructions aiming to provide security (privacy + correctness) in adversarial models of intermediate (between passive and active) strength. Using our analysis we are able to show that the protocols used by the Sharemind secure multiparty computation platform are actively private.

maslin: Dictionary.com Word of the Day [Apr. 15th, 2014|12:00 am]
 dictionary_wotd

maslin: a mixture; medley.

An Unusual Globule in IC 1396 [Apr. 15th, 2014|05:15 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140414.html

An Unusual Globule in IC 1396

GoGo Wireless Adds Surveillance Capabilities for Government [Apr. 14th, 2014|02:19 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/gogo_wireless_a.html

The important piece of this story is not that GoGo complies with the law, but that it goes above and beyond what is required by law. It has voluntarily decided to violate your privacy and turn your data over to the government.

cuittle: Dictionary.com Word of the Day [Apr. 14th, 2014|12:00 am]
 dictionary_wotd

cuittle: to wheedle, cajole, or coax.

Saturn in Blue and Gold [Apr. 14th, 2014|05:08 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140413.html

Why is Saturn partly blue?

prelusive: Dictionary.com Word of the Day [Apr. 13th, 2014|12:00 am]
 dictionary_wotd

prelusive: introductory.

Clouds and Crosses over Haleakala [Apr. 13th, 2014|04:53 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140412.html

Clouds and Crosses over Haleakala

passe-partout: Dictionary.com Word of the Day [Apr. 12th, 2014|12:00 am]
 dictionary_wotd

passe-partout: something that passes everywhere or provides a universal means of passage.

Mars near Opposition [Apr. 12th, 2014|05:41 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140411.html

Mars near Opposition

Friday Squid Blogging: Bronze Giant Squid Sculpture [Apr. 11th, 2014|09:07 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/friday_squid_bl_419.html

A little too big for my house.

SIMON Says, Break the Area Records for Symmetric Key Block Ciphers on FPGAs, by Aydin Aysu and Ege G [Apr. 11th, 2014|08:03 pm]
 iacr_eprint

http://eprint.iacr.org/2014/237

While AES is extensively in use in a number of applications, its area cost limits its deployment in resource constrained platforms. In this paper, we have implemented SIMON, a recent promising low-cost alternative of AES on reconfigurable platforms. The Feistel network, the construction of the round function and the key generation of SIMON, enables bit-serial hardware architectures which can significantly reduce the cost. Moreover, encryption and decryption can be done using the same hardware. The results show that with an equivalent security level, SIMON is 86\% smaller than AES, 70\% smaller than PRESENT (a standardized low-cost AES alternative), and its smallest hardware architecture only costs 36 slices (72 LUTs, 30 registers). To our best knowledge, this work sets the new area records as we propose the hardware architecture of the smallest block cipher ever published on FPGAs at 128-bit level of security. Therefore, SIMON is a strong alternative to AES for low-cost FPGA based applications.

High Parallel Complexity Graphs and Memory-Hard Functions, by Joel Alwen and Vladimir Serbinenko [Apr. 11th, 2014|08:03 pm]
 iacr_eprint

http://eprint.iacr.org/2014/238

Motivated by growing importance of parallelism in modern computational systems, we introduce a very natural generalization to a parallel setting of the powerful (sequential) black pebbling game over DAGs. For this new variant, when considering pebbling graphs with with multiple disconnected components (say when modelling the computation of multiple functions in parallel), we demonstrate a significant shortcoming of the two most common types of complexity measures for DAGs inherited from the sequential setting (namely S-complexity and ST-complexity). Thus, to ensure the applicability of the new pebbling game as a tool for proving results about say the \emph{amortized} hardness of functions being repeatedly evaluated, we introduce a new complexity measure for DAGs called \emph{cumulative complexity} (CC) and show how it overcomes this problem.\\

With the aim of facilitating the new complexity lower-bounds in parallel settings we turn to the task of finding high CC graphs for the parallel pebbling game. First we look at several types of graphs such as certain stacks of superconcentrators, permutation graphs, bit-reversal graphs and pyramid graphs, which are known to have high (even optimally so) complexity in the sequential setting. We show that all of them have much lower parallel CC then one could hope for from a graph of equal size. This motivates our first main technical result, namely the construction of a new family of constant in-degree graphs whose parallel CC approaches maximality to within a polylogarithmic factor.\\

The second contribution of this work is to demonstrate an application of these new theoretical tools, in particular to the field of cryptography. Memory-hard function (MHF), introduced by Percival~\cite{Per09}, have the intuitive goal of leverage the relatively high cost of memory in integrated circuits compared to general purpose computers in order to decrease the attractiveness of using custom circuits to mount brute-force attacks. We provide a new formalization for key property of such functions (overcoming problems with the approach of~\cite{Per09}) using a new type of \emph{amortized} computational hardness for families of functions in the (parallel) random oracle model. We motivate the hardness definition by showing how it provides an immediate lower-bound on the monetary cost of repeatedly evaluating such functions in several real-world (parallel) computational environments (e.g. FPGAs, ASICs, Cloud Computers). Indeed, in practice such devices are often the most cost effective means for mounting large-scale brute-force attacks on security relevant functions (such as say Proofs-of-Work and the hash functions used to obscure stored passwords in login servers). As the main technical result of this section, for the family of functions $f_G$ (over strings) characterized via a given DAG $G$, we prove a lower-bound on the hardness of $f_G$ in terms of the parallel CC of $G$. In consequence, we obtain the first provably secure (and intuitively sound) MHF.

More on Heartbleed [Apr. 11th, 2014|06:10 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/more_on_heartbl.html

This is an update to my earlier post.

Cloudflare is reporting that it's very difficult, if not practically impossible, to steal SSL private keys with this attack.

Here's the good news: after extensive testing on our software stack, we have been unable to successfully use Heartbleed on a vulnerable server to retrieve any private key data. Note that is not the same as saying it is impossible to use Heartbleed to get private keys. We do not yet feel comfortable saying that. However, if it is possible, it is at a minimum very hard. And, we have reason to believe based on the data structures used by OpenSSL and the modified version of NGINX that we use, that it may in fact be impossible.

The reasoning is complicated, and I suggest people read the post. What I have heard from people who actually ran the attack against a various servers is that what you get is a huge variety of cruft, ranging from indecipherable binary to useless log messages to peoples' passwords. The variability is huge.

This xkcd comic is a very good explanation of how the vulnerability works. And this post by Dan Kaminsky is worth reading.

I have a lot to say about the human aspects of this: auditing of open-source code, how the responsible disclosure process worked in this case, the ease with which anyone could weaponize this with just a few lines of script, how we explain vulnerabilities to the public -- and the role that impressive logo played in the process -- and our certificate issuance and revocation process. This may be a massive computer vulnerability, but all of the interesting aspects of it are human.

EDITED TO ADD (4/12): We have one example of someone successfully retrieving an SSL private key using Heartbleed. So it's possible, but it seems to be much harder than we originally thought.

And we have a story where two anonymous sources have claimed that the NSA has been exploiting Heartbleed for two years.

EDITED TO ADD (4/12): Hijacking user sessions with Heartbleed. And a nice essay on the marketing and communications around the vulnerability

EDITED TO ADD (4/13): The US intelligence community has denied prior knowledge of Heatbleed. The statement is word-game free:

NSA was not aware of the recently identified vulnerability in OpenSSL, the so-called Heartbleed vulnerability, until it was made public in a private sector cybersecurity report. Reports that say otherwise are wrong.

The statement also says:

Unless there is a clear national security or law enforcement need, this process is biased toward responsibly disclosing such vulnerabilities.

Since when is "law enforcement need" included in that decision process? This national security exception to law and process is extending much too far into normal police work.

Another point. According to the original Bloomberg article:

http://www.bloomberg.com/news/2014-04-11/nsa-said-to-have-used-heartbleed-bug-exposing-consumers.html

Certainly a plausible statement. But if those millions didn't discover something obvious like Heartbleed, shouldn't we investigate them for incompetence?

Finally -- not related to the NSA -- this is good information on which sites are still vulnerable, including historical data.

Police Disabling Their Own Voice Recorders [Apr. 11th, 2014|11:41 am]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/police_disablin.html

This is not a surprise:

The Los Angeles Police Commission is investigating how half of the recording antennas in the Southeast Division went missing, seemingly as a way to evade new self-monitoring procedures that the Los Angeles Police Department imposed last year.

The antennas, which are mounted onto individual patrol cars, receive recorded audio captured from an officer’s belt-worn transmitter. The transmitter is designed to capture an officer’s voice and transmit the recording to the car itself for storage. The voice recorders are part of a video camera system that is mounted in a front-facing camera on the patrol car. Both elements are activated any time the car’s emergency lights and sirens are turned on, but they can also be activated manually.

According to the Los Angeles Times, an LAPD investigation determined that around half of the 80 patrol cars in one South LA division were missing antennas as of last summer, and an additional 10 antennas were unaccounted for.

Surveillance of power is one of the most important ways to ensure that power does not abuse its status. But, of course, power does not like to be watched.

glib: Dictionary.com Word of the Day [Apr. 11th, 2014|12:00 am]
 dictionary_wotd

glib: readily fluent, often thoughtlessly, superficially, or insincerely so.

Mars, Ceres, Vesta [Apr. 11th, 2014|05:14 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140410.html

Mars, Ceres, Vesta

vastitude: Dictionary.com Word of the Day [Apr. 10th, 2014|12:00 am]
 dictionary_wotd

vastitude: vastness; immensity.

Two Rings for Asteroid Chariklo [Apr. 10th, 2014|04:48 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140409.html

Asteroids can have rings.

Heartbleed [Apr. 9th, 2014|10:03 am]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/heartbleed.html

Heartbleed is a catastrophic bug in OpenSSL:

"The Heartbleed bug allows anyone on the Internet to read the memory of the systems protected by the vulnerable versions of the OpenSSL software. This compromises the secret keys used to identify the service providers and to encrypt the traffic, the names and passwords of the users and the actual content. This allows attackers to eavesdrop communications, steal data directly from the services and users and to impersonate services and users.

Basically, an attacker can grab 64K of memory from a server. The attack leaves no trace, and can be done multiple times to grab a different random 64K of memory. This means that anything in memory -- SSL private keys, user keys, anything -- is vulnerable. And you have to assume that it is all compromised. All of it.

"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.

Half a million sites are vulnerable, including my own. Test your vulnerability here.

The bug has been patched. After you patch your systems, you have to get a new public/private key pair, update your SSL certificate, and then change every password that could potentially be affected.

At this point, the probability is close to one that every target has had its private keys extracted by multiple intelligence agencies. The real question is whether or not someone deliberately inserted this bug into OpenSSL, and has had two years of unfettered access to everything. My guess is accident, but I have no proof.

EDITED TO ADD (4/9): Has anyone looked at all the low-margin non-upgradable embedded systems that use OpenSSL? An upgrade path that involves the trash, a visit to Best Buy, and a credit card isn't going to be fun for anyone.

EDITED TO ADD (4/10): I'm hearing that the CAs are completely clogged, trying to reissue so many new certificates. And I'm not sure we have anything close to the infrastructure necessary to revoke half a million certificates.

Possible evidence that Heartbleed was exploited last year.

EDITED TO ADD (4/10): I wonder if there is going to be some backlash from the mainstream press and the public. If nothing really bad happens -- if this turns out to be something like the Y2K bug -- then we are going to face criticisms of crying wolf.

EDITED TO ADD (4/11): Brian Krebs and Ed Felten on how to protect yourself from Heartbleed.

ad infinitum: Dictionary.com Word of the Day [Apr. 9th, 2014|12:00 am]
 dictionary_wotd

ad infinitum: to infinity; endlessly; without limit.

M42: Inside the Orion Nebula [Apr. 9th, 2014|04:22 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140408.html

M42: Inside the Orion Nebula

"Unbreakable" Encryption Almost Certainly Isn't [Apr. 8th, 2014|11:16 am]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/unbreakable_enc.html

This headline is provocative: "Human biology inspires 'unbreakable' encryption."

The article is similarly nonsensical:

Researchers at Lancaster University, UK have taken a hint from the way the human lungs and heart constantly communicate with each other, to devise an innovative, highly flexible encryption algorithm that they claim can't be broken using the traditional methods of cyberattack.

Information can be encrypted with an array of different algorithms, but the question of which method is the most secure is far from trivial. Such algorithms need a "key" to encrypt and decrypt information; the algorithms typically generate their keys using a well-known set of rules that can only admit a very large, but nonetheless finite number of possible keys. This means that in principle, given enough time and computing power, prying eyes can always break the code eventually.

The researchers, led by Dr. Tomislav Stankovski, created an encryption mechanism that can generate a truly unlimited number of keys, which they say vastly increases the security of the communication. To do so, they took inspiration from the anatomy of the human body.

Regularly, someone from outside cryptography -- who has no idea how crypto works -- pops up and says "hey, I can solve their problems." Invariably, they make some trivial encryption scheme because they don't know better.

Remember: anyone can create a cryptosystem that he himself cannot break. And this advice from 15 years ago is still relevant.

Another article, and the paper.

deke: Dictionary.com Word of the Day [Apr. 8th, 2014|12:00 am]
 dictionary_wotd

deke: to deceive (an opponent) by a fake.

A Solar Eclipse from the Moon [Apr. 8th, 2014|04:18 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140407.html

Has a solar eclipse ever been seen from the Moon?

The Youngest Security Researcher [Apr. 7th, 2014|02:34 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/the_youngest_se.html

Five-year-old finds login vulnerability in Microsoft Xbox.

achromic: Dictionary.com Word of the Day [Apr. 7th, 2014|12:00 am]
 dictionary_wotd

achromic: colorless; without coloring matter.

Fresh Tiger Stripes on Saturns Enceladus [Apr. 7th, 2014|05:03 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140406.html

Do underground oceans vent through the tiger stripes on Saturn's moon Enceladus?

plantlet: Dictionary.com Word of the Day [Apr. 6th, 2014|12:00 am]
 dictionary_wotd

plantlet: a little plant.

Lunar Farside [Apr. 6th, 2014|04:45 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140405.html

Tidally locked in

Linear Sequential Circuit Approximation of Acterbahn Stream Cipher, by Shazia Afreen [Apr. 5th, 2014|06:15 pm]
 iacr_eprint

http://eprint.iacr.org/2014/236

Achterbahn stream cipher is proposed as a candidate for ECRYPT eSTREAM project which deals with key of length 80-bit. The linear distinguishing attack,which aims at distinguishing the keystream from purely random keystream,is employed to Achterbahn stream cipher. A linear distinguishing attack is based on linear sequential circuit approximation technique which distinguishes statistical bias in the keystream. In order to build the distinguisher, linear approximations of both non-linear feedback shift register (NLFSR) and the non-linear Boolean combining function R:F_2^8→F_2 are used. The keystream sequence generated by this algorithm consist a distinguisher with its probability bias〖 2〗^(-1809). Thus, to distinguish the Achterbahn, we only need 1/ε^2 =〖〖(2〗^1809)〗^2=2^3618 keystream bits and the time complexity is about 10/ε^2 =2^3621.3 which is much higher than the exhaustive key search O(2^80).

vittate: Dictionary.com Word of the Day [Apr. 5th, 2014|12:00 am]
 dictionary_wotd

vittate: striped longitudinally.

Along the Western Veil [Apr. 5th, 2014|05:15 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap140404.html

Delicate in appearance, these filaments of shocked, glowing gas,

Mass Surveillance by Eavesdropping on Web Cookies [Apr. 4th, 2014|01:25 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2014/04/mass_surveillan.html

Interesting research:

Abstract: We investigate the ability of a passive network observer to leverage third-party HTTP tracking cookies for mass surveillance. If two web pages embed the same tracker which emits a unique pseudonymous identifier, then the adversary can link visits to those pages from the same user (browser instance) even if the user’s IP address varies. Using simulated browsing profiles, we cluster network traffic by transitively linking shared unique cookies and estimate that for typical users over 90% of web sites with embedded trackers are located in a single connected component. Furthermore, almost half of the most popular web pages will leak a logged-in user’s real-world identity to an eavesdropper in unencrypted traffic. Together, these provide a novel method to link an identified individual to a large fraction of her entire web history. We discuss the privacy consequences of this attack and suggest mitigation strategies.

Blog post.