Unvanish Unveiled

October 1, 2009

Back in July, when I first wrote about Vanish, it had been introduced as a new approach to ensuring that data stored on the Internet (“in the cloud”) could be made to go away after a certain period of time.  Then, a little over a week ago, I wrote about some new research that suggested that Vanish might not be as secure as was originally thought.  This sort of to-and-fro is to be expected, and is healthy when we are talking about science and technology in general, and security in particular; seeing how the debate unfolds is what gives us whatever confidence we have in the outcome.

I’m pleased to see that Prof. Ed Felten, Director of the Center for Information Technology Policy at Princeton, has an article about [Un]vanish up on the CITP’s Freedom to Tinker blog, for two reasons.  First, the Unvanish paper [PDF] is now available, and I am looking forward to reading it.  As I’ve probably said before, security work requires a somewhat unusual mind-set: rather than figuring out how to make things work, one needs to figure out how to make things break.  It is always instructive to see a worked example.

The second reason I was pleased to see Prof. Felten’s post is that it gives an excellent account of the to-and-fro process that I mentioned earlier:

Our paper is the next chapter in an interesting story about the making, breaking, and possible fixing of security systems.

In response to the work by Prof. Felten and his co-authors, the original Vanish team have produced an updated paper [PDF] with a modified version of their original software, which they claim addresses some of the issues the Unvanish team found.  The jury is still out on how this will all play out; as Prof. Felten says:

Vanish is an interesting approach to a real problem. Whether this approach will turn out to work is still an open question. It’s good to explore this question — and I’m glad that the Vanish authors and others are doing so.

Or, as the Vanish team puts it:

Proposing systems, finding attacks, and implementing stronger systems is exactly how research works in the security community.

The real value in this kind of work is not so much in the final result — whatever that turns out to be — but in the exploratory work, discussion, and debate.

Public Key Cryptography

October 1, 2009

About a week ago, in a post about quantum computing, I mentioned the subject of public key cryptography, and its relationship to mathematics, particularly number theory.  The security of these algorithms depends, often, on the difficulty of factoring large integers.  (There are other functions that can be used: discrete logarithms, for example.)  The point is to find a “one-way” function; that is, a function that is easy to compute in one direction (the product of two primes) but difficult to compute in the other (factoring the product).

I had lunch with a very good friend a few days ago, and he asked me how this was used to do public key cryptography.  It had been a while since I looked at an implementation, and I couldn’t remember the details, but this note is an attempt to remedy that.  I’ll describe below, briefly, how the RSA encryption algorithm works.  This is meant to be an example that illustrates the algorithm, not an implementation guide for a complete crypto-system.  I have deliberately left out (for reasons of expository clarity, not secrecy) implementation considerations like padding functions.  The Wikipedia article on RSA has some more information, and there are references to more complete treatments at the end of this note.

RSA Key Generation
  1. Select two random prime numbers, p and q. These should be large (see below) and of approximately the same magnitude.
  2. Compute the modulus N:   N = pq
  3. Compute Φ(N) = (p -1)·(q-1)
  4. Select an integer e such that: 1 < e < Φ(N), and gcd( e, Φ(N) ) =1.  (That is, e and Φ(N) are relatively prime.)
  5. Compute, using the extended Euclidean algorithm, the integer d such that: 1 < d < Φ(N) and ed≡1 mod (Φ(N)).

The public key is the pair (N, e), and the private key is the pair (N,d).

RSA Encryption and Decryption

Represent the message Μ as an integer m, 0 < m ≤ N-1.  Compute the ciphertext c for m as:

c = me mod N

The plain text m for ciphertext c is computed as:

m = cd mod N

(For obvious reasons, e and d are sometimes called the encryption and decryption exponents, respectively.)


As I noted above, the security of the algorithm depends on the difficulty of factoring the modulus N.  Absent a practical quantum computer, the consensus of experts is that the length of N should be at least 2048 bits; few think there is any possibility of factoring a 4096-bit value in the foreseeable future.

Computationally, public-key encryption is significantly more expensive than symmetric-key encryption (such as the now-deprecated DES, or the AES).  Often, public key encryption is used to transmit a random session key, which is then used in a symmetric-key algorithm to encrypt the actual message.  If this approach is used, it is of obvious importance that the session keys be truly random.

If you are interested in more details, particularly with respect to implementation, RSA Security has available the PKCS-1 standard; there is also a more in-depth discussion at the site of DI Industries, an Australian software firm.

%d bloggers like this: