Skip to main content

Secret Sharing Algorithm for Protecting Files in the Cloud

Data stored in the cloud can be compromised or lost (see my previous post). So, we have to come up with a way to secure those files. We can encrypt them before storing them in the cloud, which sorts out the disclosure aspects. However, what if the data is lost due to some catastrophe befalling the cloud service provider? We could store it on more than one cloud service and encrypt it before we send it off. Each of them will have the same file. What if we use an insecure, easily guessable password to protect the file, or the same one to protect all files? I have often thought that secret sharing algorithms could be employed to good effect in these circumstances instead.

What are secret sharing algorithms? They are algorithms that will share a secret between several parties, such that none of them can know the secret without the help of others. Either all or a subset of them will need to get together and put their parts together to obtain the original secret. A simplistic solution can be achieved by XORing the secret with a random number, then giving the result to one party and the random number to the other. Neither one can find out what the secret was without the other. To retrieve the secret they only need to XOR the two parts together again. This can be extended to any number of parties.

A more sophisticated way would be to allow the secret to be retrieved from a subset of the parts distributed. In the previous example, if any of the parties loses their part, or refuses to disclose it, then nobody can reveal the secret. This isn't much good if one of our cloud service providers fails. On the other hand, if we can share the secret between three people, but only require any two to regenerate the original, then we have some redundancy. This is an example of a (k,n) threshold scheme with k=2 and n=3.

How do we achieve this though? Well, Adi Shamir proposed a simple secure secret sharing algorithm. It is based on drawing graphs. To uniquely define a straight line, you need two points on that line. Similarly, to define a parabola you need three points. A cubic requires four, etc. So, we can distribute points on a line to each party we want to share the secret with. The order of the line will determine how many of them need to get together to regenerate it. So, we could define a random straight line and distribute three points on it to three different parties. However, only two of them need to get together to regenerate the original secret.

We set up a (k,n) threshold scheme by setting the free coefficient to be the secret and then choosing random numbers for each of the other coefficients. The polynomial then becomes the following:


where a0 is our secret. Now we can distribute points on the line to each of the n parties simply by calculating y for a series of different values for x. We can use the Lagrange Basis Polynomials to reconstruct the equation of the line from k points. However, we do not need to reconstruct the whole line, we are only interested in the free term. This simplifies the equations that we need to use. For example, if we have a straight line, then we only need two points (x0,y0) and (x1,y1). We can then calculate a0 as follows:
Similarly, for a parabola and three points (x0,y0), (x1,y1) and (x2,y2) we have:
This should be fairly simple to implement and use. You would need to sign up to a few cloud services, but you wouldn't have all your eggs in one basket and you wouldn't be reliant on weak passwords.

Comments

  1. Thanks for the secret secure algorithms for protecting files in the cloud. I think a secure secret sharing system is really helpful to allocate shares so that everyone shares with no extra information about the secret.

    ReplyDelete

Post a Comment

Popular Posts

You say it's 'Security Best Practice' - prove it!

Over the last few weeks I have had many conversations and even attended presentations where people talk about 'Security Best Practices' and how we should all follow them. However, 'Best Practice' is just another way of saying 'What everyone else does!' OK, so if everyone else does it and it's the right thing to do, you should be able to prove it. The trouble is that nobody ever measures best practice - why would you? If everyone's doing it, it must be right.

Well, I don't agree with this sentiment. Don't get me wrong, many of the so-called best practices are good for most organisations, but blindly following them without thought for your specific business could cause as many problems as you solve. I see best practice like buying an off-the-peg suit - it will fit most people acceptably well if they are a fairly 'normal' size and shape. However, it will never fit as well as a tailored suit and isn't an option for those of us who are ou…

McAfee Secure Short-URL Service Easy to Foil

McAfee have launched a Beta URL shortening service with added security features. As Brett Hardin pointed out they are a little late to the game. However, there are so many abuses of URL shortening services that I commend them for trying.

Basically, what their service does is allow you to create short easy URLs (like any other service). However, unlike other services, when you click on the link, it opens a frames page with the content in the bottom frame and the McAfee information in the top frame. This information includes details about the domain you are connecting to, the type of company it's registered to and a big green tick or red cross to tell you whether the site is safe or not. This is decided by their 'Global Threat Intelligence', which will block known bad URLs and phishing sites. That's good, if it works.

I said above that I commend them for trying to provide this service. There are some obvious failings in their solution though, that render their protection…

Coventry Building Society Grid Card

Coventry Building Society have recently introduced the Grid Card as a simple form of 2-factor authentication. It replaces memorable words in the login process. Now the idea is that you require something you know (i.e. your password) and something you have (i.e. the Grid Card) to log in - 2 things = 2 factors. For more about authentication see this post.

How does it work? Very simply is the answer. During the log in process, you will be asked to enter the digits at 3 co-ordinates. For example: c3, d2 and j5 would mean that you enter 5, 6 and 3 (this is the example Coventry give). Is this better than a secret word? Yes, is the short answer. How many people will choose a memorable word that someone close to them could guess? Remember, that this isn't a password as such, it is expected to be a word and a word that means something to the user. The problem is that users cannot remember lots of passwords, so remembering two would be difficult. Also, having two passwords isn't really…