# Category Archives: Uncategorized

## “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 $O(n^4)$ 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.) Continue reading

## Polygon rectangulation, part 2: Minimum number of fat rectangles

This post is the second in a series on polygon rectangulation. In my previous post, I discussed methods to decompose an orthogonal polygon into a minimum number of rectangles.  (See that post for definitions and motivation.)  In my next post, I will consider finding a rectangulation of a minimum length — a topic very important in VLSI.  In this post, I will consider a modification to the minimum-number-of-rectangles problem; the modification was motivated by concerns in VLSI, but, as yet, only a theoretical algorithm exists, with a running time of $O(n^{42})$.  (That is not a typo, and it is obtained through a “natural” dynamic programming solution to the problem I am about to state.)

Printed circuits are created through a process called photolithography, in which electron beams etch a design onto a substrate.  While these electron beams are, in one sense, extremely narrow, as the Wikipedia article on VLSI states, current photolithography techniques “tend closer to the fundamental laws of optics.”  Among other things, this means that the fixed minimum width of an electron beam is suddenly important.  In principle, it implies a “fat fingers” problem.  Suppose our substrate is in the shape of orthogonal polygon $P$, and we use a rectangulation technique from the previous post to rectangulate $P$.  We may not be able to apply the rectangulation in real life, because we have no guarantee that all of the rectangles are wider than our electron beam.  Therefore, we would like to constrain the space of rectangulations we consider to ones that are feasible to etch — informally, ones that contain only “fat” rectangles.  We formalize this optimization problem as follows.

Fat Rectangle Optimization Problem: Given an orthogonal polygon $P$, maximize the shortest side $\delta$ over all rectangulations of $P$.  Among the partitions with the same $\delta$, choose the partition with the fewest number of rectangles.

This optimization problem has been studied by O’Rourke and co-authors in at least three papers.  In this blog post, I will focus on consideration of The Structure of Optimal Partitions of Orthogonal Polygons into Fat Rectangles, by O’Rourke and Tewari (2004). Continue reading

## Polygon rectangulation, part 1: Minimum number of rectangles

Over the next few posts, I will consider problems of polygon rectangulation: given as input $P$ an orthogonal polygon (all interior angles are 90 or 270 degrees), decompose $P$ into adjacent, nonoverlapping rectangles that fully cover $P$.  Different problems impose different conditions on what constitutes a “good” rectangulation.  Today we will discuss how to find a rectangulation with the least number of rectangles.

Polygon decomposition is a method often used in computer graphics and other fields, in order to break a (perhaps very complex) shape into lots of small manageable shapes.  Polygon triangulation may be the best-studied decomposition problem.  (When triangulating, we don’t require that the input polygon be orthogonal, and our objective is to cut the polygon into triangles according to some notion of “best” decomposition.)  There is an extensive literature on polygon rectangulation as well, because of its connection to VLSI design.  Suppose, for example, that our input $P$ represents a circuit board, and we want to subdivide the board by placing as little additional “ink” on the board as possible, in order to save money on each unit.  However, because of mechanical limitations, we can only place ink horizontally or vertically — i.e., only create rectangulations of $P$.  Many questions in VLSI design are closely related to finding a rectangulation of minimum total length, which I will discuss in a future post.  The algorithm for minimum-length rectangulation is more complicated than the one I will present today for minimum-number-of-rectangles rectangulation, so today’s post can be considered a warm-up.

The attendees of the recent Midwest Theory Day know that Ming-Yang Kao and I found an application of rectangulation to DNA self-assembly.  I will blog about that in the new year.  The only other application of rectangulation to self-assembly that I know about is A Rectangular Partition Algorithm for Self-Assembly, by Li and Zhang, which appeared in a robotics conference.  (Readers interested in the latest Midwest Theory Day are invited to check out a “workshop report” I wrote on the CSTheory Community Blog.)

These slides (pdf format) by Derrick Stolee contain many lovely pictures about polygon rectangulation.  I think they may be a bit hard to follow all the way through as there is no “attached narrative,” but I recommend them anyway. :-) Continue reading

## Can we derandomize BP.PP?

Two days ago, I added a “bounty” to a year-old unanswered question that Noam Nisan asked on CSTheory about the relationship between the Polynomial Hierarchy and the complexity class PP (probabilistic polynomial time).  I remember thinking when the question was first asked, “Wow, there is something important going on here,” but no one has posted an answer, even though the question has received a thousand views.  I hope this blog entry can drive a bit more traffic that direction, because I bet someone, somewhere does know the answer — and I am quite confident that person isn’t me!

The issue, as I understand it, is whether the polynomial hierarchy (PH) is contained within PP in “the real world.”  There exist oracles (possible worlds) in which $\textsf{PH} \subsetneq \textsf{PP}$.  (See the answers to this question of Huck Bennett for references and explanation.)  On the other hand, Scott Aaronson in this answer makes the case for $\textsf{PH} \subseteq \textsf{PP}$ in the real world, because Toda’s Theorem implies that $\textsf{PH} \subseteq \textsf{BP.PP}$, where $\textsf{BP.PP}$ as Aaronson puts it, “is to $\textsf{PP}$ as $\textsf{BPP}$ is to $\textsf{P}$.”  Since we expect (because of plausible derandomization assumptions) that $\textsf{BPP}=\textsf{P}$ in real life — and, in general, that randomization does not help much, given these plausible assumptions, then “probably” $\textsf{BP.PP}=\textsf{PP}$ so by Toda’s Theorem, $\textsf{PH} \subseteq \textsf{PP}$.

This sounded great to me, but I now realize I have no idea what $\textsf{BP.PP}$ is, not really.  Fortunately for my ego, this seems to be the crux of Nisan’s question.  His point, as I understand it, is that just because we expect to be able to derandomize $\textsf{BPP}$, that does not mean we can derandomize $\textsf{BP.PP}$, precisely because the oracles I mentioned at the beginning exist.  Known derandomization techniques seem to relativize (that is, they give the same results with respect to all oracles), and Aaronson’s claim implies that $\textsf{PH} \subseteq \textsf{PP}$ does not evaluate to the same truth value under all oracles.  So if $\textsf{PH} \subsetneq \textsf{PP}$ with respect to some oracle $A$, that “must” mean that the pseudorandom generators do not exist for $\textsf{BP.PP}$ in $A$, else we could derandomize it.  Nisan’s feeling/conjecture is that somewhere in such oracle constructions, there must be an implied upper bound for $\textsf{PP}$, keeping it below $\textsf{PH}$.

In a nutshell, what is the relationship of derandomization to $\textsf{BP.PP}$?

## An independent discovery of Costas arrays

In today’s post, I will discuss a little-known combinatorics paper by E.N. Gilbert from 1965, in which he independently discovered the “logarithmic Welch” construction of Costas arrays.  Costas arrays are named after the late IEEE fellow John Costas, whose seminal paper on what are now called Costas arrays appeared, coincidentially, in 1965, the same year as Gilbert’s paper.  I had never heard of Costas arrays until just a few weeks ago, when I needed a combinatorial object with their properties for a problem I am trying to solve about error-prevention in molecular self-assembly.  So I approached the literature in a nonstandard way, found Gilbert’s paper, and eventually wrote experts on Costas arrays to confirm that Theorem 6 of Gilbert’s Latin Squares Which Contain No Repeated Digrams did indeed produce a construction that independently appeared in the literature “for the first time” in 1982.  Therefore, my objective with this blog post is twofold: (1) to make better known an area of combinatorics that may be familiar to information theorists but not to computer scientists; and (2) to change in a small way the intellectual history of this area, so Gilbert is recognized as a co-inventor of an important class of combinatorial designs.  (ADDED LATER: It appears I may have accomplished (2).  The Wikipedia page on Gilbert now states that he was a co-inventor of Costas arrays, and cites this blog entry as justification.  This is my first Wikipedia citation, to my knowledge.  Somewhere along the way, I seem to have morphed from off-the-wall commentator to reliable source.)

First, though, a quick pointer for anyone interested in DNA computation: Dave Doty just contributed an entry to the CSTheory Community Blog on the DNA Computing conference that took place last month at CalTech.  Dave was on the local arrangements committee, and, in his post, he talks about both technical results presented at the conference, and suggestions for organization of future CS conferences.  Good stuff. Continue reading