Wikileaks to release emails from Stratfor hack

In December, members of the Antisec wing of the collective Anonymous claimed to have downloaded the email spools of the private intelligence firm Stratfor.  Today, Wikileaks held a press conference in which they announced that over 20 media organizations had been secretly analyzing the 5 million+ emails, and they would now begin releasing the emails.  A few stories in mainstream western media have now appeared (e.g., Forbes, Wired).  I’ve followed this hack a bit, and I played the video of the Wikileaks press conference in the background this morning.  Here are a few things that interested me about the press conference that I haven’t seen in media reports.

Most striking to me was how differently reporters assessed the accuracy of Stratfor’s intel, depending on geography.  Apparently, Stratfor investigated PETA on behalf of Coca-Cola, and investigated Bhopal activists on behalf of Dow Chemical.  While some might find this concerning, I didn’t hear any indication that the information obtained by those efforts was false.  In contrast, two reporters from the Al Akhbar newspaper in Lebanon stated that much of the information gathered about the situation in Beiruit was false.

The Al Akhbar reporters said this situation was a particular problem, because the CIA was recently forced to shut down its intelligence operations in Lebanon.  This increased US reliance on a private firm like Stratfor.  Apparently, though, Stratfor, to maximize profits, provided a lot of intel on Lebanon by using Google Translate to read open source material written in Arabic, literally losing the meaning in translation, instead of hiring analysts fluent in the language.  Further, their evaluation of sources was, according to one reporter, “racist” in the sense that if an ideologically extreme Arab made a statement and an ideologically extreme Israeli made a different statement, Stratfor analysts would discount the Arab and take the Israeli seriously.

I’ve read only a few of the emails myself, and I can’t speak to the accuracy of any claim.  However, it does seem clear that the notion of Stratfor just being a service that reads and analyzes open-source material is incorrect.  Unless the released emails are heavily fabricated, Stratfor initiated intelligence gathering operations on the ground, bribed confidential informants around the world, and encouraged their employees to control sources by “psychological” or “sexual” means.

Finally, no matter your personal political persuasion, Stratfor’s internal glossary of intelligence terms is hilarious.  I will close with some definitions from it.

Backgrounder: General analysis that gives the customer better situational awareness. The customer never actually reads the Backgrounder. Its primary use is as cover when the customer screws something up. Backgrounders are the basic intelligence tool for shifting blame to the customer.

or

He Won the Cold War: Egomaniacal Bullshitter

and

He Won the Vietnam War: Deranged Egomaniacal Bulshitter

and, in conclusion, a definition made more intriguing by (and perhaps at odds with) the claims of the Al Akhbar reporters:

Duplicitous Little Bastards: Israeli intelligence

A few Tweets

I joined Twitter at the end of December 2011 because I realized that I was using my computer less and less, and my smart phone more and more, relatively speaking — and I was using my phone to find and read content that intrigued me.  I plan to use my Twitter account almost as a note-taking service — I will tweet news articles, etc., that intrigue me and that I might want to come back to later.

My account is @aaron_sterling, and you can see it in the rightmost column of this blog.  Here are three items that are good examples of things I found interesting, but which, after today, I won’t be “elevating” to the status of a blog entry.

1. The computer security company McAfee has produced a document titled 2012 Threat Predictions (pdf file).  I skipped over some of it, but the parts I read were fascinating.  For example, they see BitCoin as an extremely insecure currency, they believe illegal spam will diminish and be replaced by “legal spam” (equally annoying), and they think far more attackers will target hardware exploits instead of the traditional software exploits.  Worth a look.
2. Enrique Zabala has produced a Flash animation that explains Rijndael/AES visually.  It is beautiful.
3. Rajarshi Guha and co-authors are designing a type-ahead chemical substructure search engine.  This addresses a longstanding open problem in cheminformatics, which is: searching for chemicals in a database is slow (in worst case probably exponential because the Subgraph Isomorphism Problem is NP-complete), but can it be made faster?  At least for important special cases, this tool seems to be competitive in speed with Google’s type-ahead search engine for other content: it provides the chemist suggestions, given the prefix of the input available, before the chemist even hits the enter key.

Watermarking molecules

I’ve posted twice about Anonymous hacking into Stratfor — and, more generally, their hacktivism has been making bigger and bigger waves.  CNN recently ran a fairly positive story on the support hacktivists are providing the Occupy movement.  Many of these hacktivists are quite active on Twitter and elsewhere.  However, from the perspective of both international and corporate espionage, the “quiet” hacks are the worst: someone makes off with information and the victim never knows.  As security expert Kevin Mandia told the New York Times:

The hacks that do the most damage don’t have Twitter feeds.

Another security expert, Jeremy Falkenrath, in an interview on Bloomberg News (at about 7:00 into the video), discussed, quite matter-of-factly, the hacker-for-hire market that companies in the chemical industry deploy against one another to learn trade secrets.  With this as the backdrop, I’d like to discuss one of the main open questions of cheminformatics: Is secure encryption of molecules possible?  For example, it would be nice if a company could encrypt a molecule, but then allow some third party to run in silico tests with it, having access to the molecule’s properties but not the structure itself.

Encryption of molecules

Part of the reason for the traditional closed-data policies of pharmaceutical companies is the total absence of any way to encrypt chemical structural information.  This has been recognized as an open problem for many years, the American Chemical Society held a special meeting in 2005 about it, a summary of which appeared in Nature.  While there were presenters at that meeting who felt molecular encryption was possible, and others who felt it was impossible, the practical reality as we enter 2012 is that, so far, the voices in favor of “impossible” have been correct.  Almost no new theoretical literature has been produced since 2005, and the industry appears no nearer a practical solution than it was in, say, 1975.

I recently had an idea to expand upon a proposal by Eggers et al. in 2001, to watermark in silico representations of molecules.  My idea, however, is going nowhere — just like all other attempts so far to implement chemical watermarking.  At least I can get a blog entry out of my failure though!  I hope readers of this page find my little attempt entertaining or informative.

Acknowledgement: The material in this post is based on conversations I have had with cheminformaticians Rajarshi Guha and Jörg Kurt Wegner.

Ian Stewart’s Mathematics of Life

This post is based on a book review I recently wrote on The Mathematics of Life, by Ian Stewart. A final version of the review will appear in a future issue of SIGACT News.  Please feel free to download a pdf version of the full preprint, or just read an abbreviated version of it here, in blog format.

Introduction

Ian Stewart is one of the premier popularizers of mathematics.  He has written over twenty books about math for lay audiences.  He has also co-authored science fiction, and books on the science of science fiction (three books on “the science of discworld”).  In his newest effort, The Mathematics of Life, Stewart focuses his talents on the mathematics of biology, and the result is superb.  In an easy, flowing read, with dozens of diagrams and scholarly footnotes — but without a single formula — he introduces the reader to a wide range of interactions between mathematicians and biologists.  I heartily recommend this book.

My own information was just compromised in the Zappos hack

In an unfortunate coincidence, as a thematic followup to my previous post on hacking, a “throwaway” email I use, and partial credit card information of mine, has just been compromised in the recent hack of Zappos.com.  Infosec Island has a good blog post about this data breach,  and I was one of 24 million Zappos customers who received the email quoted in that blog post.

I’ve deleted my credit card information from Zappos, and from one other online retailer I use.  To be honest, I’m not sure who else might have my sensitive information — and I bet I’m not alone in that.  I’m not sure what precautions I will take in the future when shopping online, but I plan never to save my credit card information again.

Stay safe, everyone.

Password analysis from the Stratfor hack

I will return to blogging about theoretical computer science and algorithm-related mathematics next week, but I wanted to take a few minutes today to mention a rare research opportunity that has arisen as a result of the hack of the private global intelligence company Stratfor.  This opportunity is the list of 860,000 (MD5 hashed) passwords to accounts of people in journalism, government contracting, the military, etc. — in short, people who “should” know how to create and maintain strong passwords.  Most of the MD5 hashes have now been cracked, and preliminary analysis indicates that even people who “know what they are doing” use weak passwords.

Stratfor, by the way, finally has their website back online, with a Hacking News section, in which they tell their side of the story.  (They verify that they stored credit card information in cleartext, as Anonymous had claimed, and they state that they were working with the FBI on an investigation into a hack of their systems before the hack went public on Christmas Eve.)  About a week ago, the hackers released a zine which includes a press release about the Stratfor hack and two others, and a log of the hacks themselves.

Polygon rectangulation wrap up

Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons.

1. Derrick Stolee requested in a comment a resolution of the computational complexity of the 3D version of the problem of decomposing a shape into the minimum number of rectangles.  I found a reference that proves the problem is NP-complete, by directly reducing the problem to a variant of 3SAT.  The diagrams of the gadgets used are pretty cool — the gadgets look like children’s toys used to build 3D structures.  Rectangular partition is polynomial in two dimensions but NP-complete in three, by Victor J. Dielissen and Anne Kaldewaij, Information Processing Letters, April 1991.
2. The survey Polygon Decomposition by J. Mark Keil (1996) has much more information on exact algorithms for rectangulation, triangulation, and problems I did not mention at all, like covering.
3. There is an extensive literature on approximation algorithms for finding a minimum-length rectangulation of an orthogonal polygon with holes.  (The problem is NP-complete even for the case where the polygon is a rectangle and its interior holes are points.)  I can recommend the survey Minimum Edge-Length Rectangular Partitions, by Gonzalez and Zheng (in Handbook of Approximation Algorithms and Metaheuristics, 2007).

Victor J. Dielissen, & Anne Kaldewaij (1991). Rectangular partition is polynomial in two dimensions but NP-complete in three Information Processing Letters, 38 (1), 1-6 : 10.1016/0020-0190(91)90207-X

“Shadow CIA” apparently stored credit card information in cleartext

I had not planned to post until January, but I decided to say something briefly about a news story that relates to one of the first posts on this blog, about security firm HBGary’s insecure storage of data.  This story, as I am sure many of you have already guessed, is the hacking of Strategic Forecasting, Inc., better known as Stratfor, by the group Anonymous.

Stratfor is a private intelligence-gathering firm whose principals have close ties to the US intelligence community.  Stratfor has been called the “shadow CIA.”  Anonymous claims to have obtained 200 GB of data, including 2.7 million private emails and 4000 credit cards.  While big media worldwide have focused so far on the “Operation Robin Hood” nature of the attack — the hackers claim to have made $1 million in donations to charities using the credit card information — one Anonymous member has stated that the real reason for the attack was to obtain the emails, and the hackers did not expect the credit card information would be as easy to obtain as it was.

Perhaps the most interesting writing I have seen on this subject is at the site databreaches.net, which provides a timeline of the hack, and suggests that it had been going on for a week or more, without Stratfor’s knowledge.  Databreaches.net also asks the reasonable question whether Stratfor might be legally liable for the compromise of credit card data, because it appears that both Texas law (where Stratfor is based) and Stratfor’s own privacy policy prohibit the storage of credit card information in cleartext.  Moreover, Stratfor apparently stored the 3-digit security codes of credit cards in cleartext also, and standard security procedure is not to store those codes at all.

This situation reminded me of a comment Peter Taylor made on an answer of Peter Shor on CSTheory.  Shor was answering a question about what would happen if it turned out that factoring could be solved in polynomial time.  Among other things, he said, “as soon as it was known that factoring was in P, the banks would switch to some other system.”  Taylor responded:

A bit off-topic, but as soon as it was known that factoring was in P, the banks would switch to some other system is largely wishful thinking. I discovered in December that a company which doesn’t do anything except process credit card details was using a variant of Vigenère with a key shorter than some runs of known plaintext. Worse, the technical director of the company wouldn’t believe me that it was insecure until I sent him some attack code. MD5, despite being widely considered broken, is still used heavily in banking.

For as long as I have been reading computer science theory blogs, commenters have left a lot of critical comments, along the lines of, “The result you are getting excited about is a very small advance, and has nothing to do with the real needs of industry.”   At a political level, similar arguments are used to reduce funding to theoretical research of all kinds, including theoretical CS.  I believe these arguments are completely incorrect, because the much more pressing problem is that industry doesn’t use fully-implementable techniques that theorists discovered years ago.  In the cases of HBGary and Stratfor, this may well have been because the principals considered themselves “too important” to take mundane steps, but there is no doubt that data insecurity, extremely suboptimal algorithm design, etc., is rampant in the business sector.  An industry, and a government, that dismisses the importance of theory, will pay heavy prices in the long run.

Postscripts

1. Jonathan Katz recently blogged about an upcoming workshop: “Is Cryptographic Theory Practically Relevant?”
2. There is a short CSTheory community wiki on the difference between the theory and practice of security and cryptography.
3. Databreaches.net reports that there is a series of hacks taking place in China right now, perhaps to protest a move to require the use of real names on the internet.  Over 40 million users have had their information compromised.  I hope everyone reading this blog stays safe, as we enter 2012.

Happy holidays!

I would like to wish a very happy holiday season to all the readers of this blog.  I am excited about the research I have planned in 2012, and I hope you are even more excited about your own year-to-come.

This will be my last post until the new year.  As a holiday gift, please allow me to share with you the “Technical Papers Trailer” for SIGGRAPH Asia 2011.  The conference itself just ended, but the video is a great example, to my mind, of how to popularize computer science.

Polygon rectangulation, part 3: Minimum-length rectangulation

In this third (and final) post on polygon rectangulation, I will consider how to find the rectangulation of minimum total length for an orthogonal polygon.  In part one of this short series, we considered rectangulations with a minimum number of rectangles; and, in part two, we considered rectangulations with a minimum number of “fat” rectangles.  I’ve saved this post for last, because this may be the most useful rectangulation application in VLSI, and this is the rectangulation problem that Ming-Yang Kao and I have applied to self-assembly (though I won’t discuss our application in this post).

The minimum-length rectangulation algorithm appeared in Minimum Edge Length Partitioning of Rectilinear Polygons, by Lingas, Pinter, Rivest and Shamir (1982).  The authors proved both a positive and a negative result.  The positive result — which I will focus on today — is a dynamic programming algorithm that finds an optimal minimum-length rectangulation for any orthogonal polygon with no interior holes.  The negative result is a proof that, if the input polygon is allowed to have holes, then the problem is NP-complete.  (I discussed the proof of this result in a previous blog post.)