by ·5 Comments

Earlier this week I heard about a new startup called Bitcasa which is offering “infinite” secure cloud storage for a low monthly fee. Now, I’m not particularly interested in relying on a brand-new startup for all of my off-site storage needs, but one of Bitcasa’s technical claims seems to have raised a few eyebrows on the Internet. In particular, I learned from an episode of the podcast Security Now that Bitcasa claims to use exclusively client-side encryption and also to be able to de-duplicate files server-side.

Think about that for a moment, and it may at first seem impossible. How can you de-duplicate plaintext that the server never has access to? But it’s not impossible, and I wouldn’t doubt that many ways of doing this are widely known, but I did find it to be a really interesting computer science brainteaser. Here’s the problem, in my words:

Design a service that allows users to store blocks of data and retrieve them later. The service must have the following properties:

  1. No block is stored more than once.
  2. No more than O(1) additional space is used per user who “owns” a particular block.
  3. No user is able to decrypt a block that he does not own.
  4. The service could not be compelled by any authority to decrypt the blocks it stores.

Extra Credit:

  1. No communication between users, directly or through the service, is required.
  2. The service could not be compelled by any authority to divulge which users own which blocks.

In the Security Now episode in question, the host gave a solution which satisfied 1-4, but not 5 or 6, so I have labelled them as extra credit. If you want to try solving this problem yourself, stop reading now — my solution follows.
Continue reading

by ·3 Comments

Encryption on the Internet has come a long, long way from the oft-ignored little yellow key in the lower left corner of your Netscape Navigator status bar. Today, cryptography is a vital part of all of our Internet lives, whether we realize it or not. Now, if you’re reading this article on Nerdland, chances are that you’re well aware of that, and I don’t need to explain why you need to be sure your online banking is done over an HTTPS connection, and why connecting your laptop to an open, unsecured wireless network is usually a bad idea.

But the little stuff can trip you up just as easily, and if you don’t have a solid understanding of the different facets of cryptography, you may well think that a system meets your security requirements when it does not. After all, modern cryptography is just mathematics. There’s no inherent application for it. Security isn’t a tangible property either; it’s an umbrella term for a whole class of goals. Rather, privacy, authentication, identification, trust, and verification — mechanisms of applied cryptography — are what provide the most commonly desired types of security. Understanding what these terms really mean, how they are implemented, and how they are different is essential to a true understanding of how encryption works to assure your security on the Internet, and even within a single computer.

Continue reading