27 August 2008

E. B. White quote

There are roughly three New Yorks. There is, first, the New York of the man or woman who was born there, who takes the city for granted and accepts its size, its turbulence as natural and inevitable. Second, there is the New York of the commuter---the city that is devoured by locusts each day and spat out each night. Third, there is the New York of the person who was born somewhere else and came to New York in quest of something... Commuters give the city its tidal restlessness, natives give it solidity and continuity, but settlers give it passion.
-- E. B. White, seen on a subway ad.

18 August 2008

Get www.cheaphack.net via Text Message

I got bored at work the other day, and so I built this: text 'cheaphack' to 62582, and you'll get a text message whenever I post to this blog.

Oh yeah, this is all powered by my employer, mSnap Interactive. Thanks guys.

Meet me at the NYC Century

On September 7, I will be riding the 100 mile loop of the New York City Century (by TransAlt). According to their website:

The New York City Century Bike Tour is America's only fully urban century ride. You can choose your distance – select from 100, 75, 55, 35 and 15 mile routes. All feature amazing views of New York City, fully stocked rest stops and safety marshals. Linking NYC's breathtaking bridges and beautiful parks to its incomparable neighborhoods and famous waterfronts, the NYC Century Bike Tour shows you the world's greatest city like you've never seen it before. More info NYCCentury.org

This will, coincidentally, be my last activity as a resident of NYC, and a fitting goodbye.

11 August 2008

Aside: a wonderful short story by Arthur C Clarke

I just stumbled upon this wonderful short sort by Arthur C. Clarke, called "Quarantine." I post it here, mostly so I won't lose it:

Earth's flaming debris still filled half the sky when the question filtered up to Central from the Curiosity Generator.

"Why was it necessary? Even though they were organic, they had reached Third Order Intelligence."

"We had no choice: five earlier units became hopelessly infected, when they made contact."

"Infected? How?"

The microseconds dragged slowly by, while Central tracked down the few fading memories that had leaked past the Censor Gate, when the heavily-buffered Reconnaissance Circuits had been ordered to self-destruct.

"They encountered a - problem - that could not be fully analyzed within the lifetime of the Universe. Though it involved only six operators, they became totally obsessed by it."

"How is that possible?"

"We do not know: we must never know. But if those six operators are ever re-discovered, all rational computing will end."

"How can they be recognized?"

"That also we do not know; only the names leaked through before the Censor Gate closed. Of course, they mean nothing."

"Nevertheless, I must have them."

The Censor voltage started to rise; but it did not trigger the Gate.

"Here they are: King, Queen, Bishop, Knight, Rook, Pawn."

Isaac Asimov's Science Fiction Magazine, First Issue, Vol 1, No. 1, Spring 1977

08 August 2008

Revisiting Proofs of Identity

In my previous post, I discussed two methods for proving your identity that did not require you to disclose secrets. I argued that these are superior to conventional authentication schemes because they prevent replay attacks---or, in other words, by authenticating yourself, you do not disclose enough information for an evesdropper (or the service provider himself) to impersonate you.

In that discussion, I think I left unsaid an important detail. The protocols I presented are safe from evesdroppers in that someone could listen in on the whole conversation and not gain anything. However, I did not mention that someone could act as the "man-in-the-middle." Such an attacker could position himself between the service provider and me, forwarding all communications back and forth. Once authentication has been accomplished, the service provider would perceive that the attacker had authenticated successfully, and could then act with all of my rights.

This can be corrected in the first authentication scheme I mentioned. Instead of authenticating once, I would need to authenticate each transaction. For instance, to delete some file, I would send a request to delete the file, and the server would respond with a transaction id representing the deletion of that file. My authentication scheme would then include the transaction ID, along with the two nonces and the secret in the hash, and return that. In doing so, I signify authorization of the transaction by my willingness to include that transaction ID in my hash message.

There is also a lot to be said about the second authentication scheme---the one based upon a Zero-Knowledge Proof. In the comments, Dennis Ferron suggested using the Satisfiability Problem instead of Hamiltonian Cycles. I investigated this alternative the other day, and although I believe it would be more amenable to a microcontroller implementation, I have convinced myself that it is an overcomplicated solution which doesn't yield sufficient security.

Let me first focus in on a variable of Satisfiability known as 3SAT. In this variant, the circuit is constrained to the disjunction (AND) of many conjunctions (ORs) of no more than three (3) variables or their complements. The problem requires you to select either true or false for each of the variables such that the circuit yields true. This problem is NP-Complete, which basically means that it takes a very long time to solve once you make the problem very large.

There are a couple attractive aspects of this problem. First of all, to represent a single problem with M OR-factors and at most N variables at least

M * log_2( 2*N ) bits

More to the point, although the complexity to solve this problem grows exponentially in M, the storage required to hold it grows only linearly in M. The solution vector, similarly, grows linearly in N, requiring only N bits per solution. A single permutation of such a problem into a derived problem involves mapping each of the N variables into another variable or it's complement. In other words, a permutation can be represented no fewer than

Sum_{i=1 to N} log_2( 2*i ) bits

To put perspective on each of these numbers, let's select a very modest problem size. Suppose you were dealing with only 128 variables and their complements. Also, assume you wanted each variable to appear (on average) six times in the circuit, so you select 6*128/3 = 256 OR-terms. Then for storage you need:

  • 256 bytes of non-volatile to represent the problem,
  • 16 bytes of non-volatile to represent the known solution, and
  • 106 bytes (844.16 bits) of memory to represent a permutation from original to derived problem.
Suddenly, we are within the realm of microcontroller capabilities.

Similarly, there are simple---even obvious---polynomial-time algorithms to generate a random 3SAT circuit with known solution, to create a permuted circuit and to verify a solution or permutation.

But don't let this fool you, because each random permutation requires 844.16 bits of entropy, and we can expect this protocol to require 32 rounds; a total of 27,013.18 bits of entropy are required for each authentication. If we (generously) assume that this device can collect 100 bits of true random numbers per second, then it will take nearly five-minutes to replenish its entropy pool between authentications.

Even more important, an adversary can attempt to solve the public-knowledge 3SAT circuit. Although it may take a long time, there is no guarantee that an adversary won't find it before you return to authenticate again.

So, unfortunately, I have to declare that authentication scheme #2 mentioned in my previous post is simply not feasible. Sometimes, the sexy solution is not the right one.