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.

No comments: