Saturday, June 28, 2008

Secret Splitting

An interesting way to use one-time pad encryption is Secret Splitting. We all know what sharing a secret is (people tend to have problems not to share secrets). The opposite of sharing secrets is to split them.

Suppose Charlie has a secret password or a safe combination he wants to share with someone in case of emergency. Wouldn't it be great if he could split his secret and give one share to Alice and one share to Bob? The secret could only be retrieved when both Alice and Bob agree on sharing their secret. Of course, cutting it simply in two and give each person half the secret would reveal already that part, so that would not be safe.

Well, there's a simple solution and it's called one-time pad. Secret Splitting is a special way of using one-time pad, since you don't send a secret message, and the key isn't destroyed. Here's how it goes: Charlie subtracts a truly random key, digit by digit, modulo 10 (without borrowing), from his safe combination. For instance, 4 - 6 = 8 because [1]4 - 6 = 8. He gives one share (they key) to Alice and one share (the result) to Bob.

Charlie's Combination      21 46 03 88
Random key (first share) - 25 01 77 61
                           -----------
Results (second share)     06 45 36 27

Alice's share = 2501 7761
Bob's share   = 0645 3627


To retrieve the original combination, Alice and Bob just add their keys together, again modulo 10 (without carry). For instance 7 + 6 = 3 because 7 + 6 = [1]3. Of course, one could also split text by first converting the letters into digits (f.i. A=01, B=02 and so on through Z=26). You can download a practical Secure Code Splitter (pdf) template that supports up to 4 shares of 10 digits.

It's mathematically impossible to retrieve the secret information without having all shares, under the condition that the random share contains truly random digits, and all shares are physically and securely separated.

There are some interesting applications for this system. It's a secure method to give a code or password in the custody of multiple persons when you're abroad. Each person receives a share. All persons involved have to agree to combine their shares to retrieve the code or password. But if you want to have the final decision to disclose your secret code, there's another solutions.

You can create two shares, take one with you on a business trip and give the second share to a trustee from your company. In case of emergency, you can sent your share by open e-mail or telephone to the trustee. Combined with his own share, he can retrieve the secret code and open your safe or whatever. Because the share and result share are trule random, sending one of the shares by insecure channel will never disclose the secret code, as long as both share are never disclosed simultaneously.
 
It's also a clever way to share things with people who don't trust each other. Suppose grandpa, old and sick, splits the secret combination of a safe that contains his savings and gives each of his children one share of that secret. They can only get their hands on his money if they all agree (not that this will make grandpa live longer).

Of course, after using the shares, you should always set a new secret code or password to your safe and create a completely new set of shares to avoid unauthorised use of the old combination.

More about Secret Splitting and one-time pad on my Secret Splitting page.

Update: a new version of the Secure Code Splitter is available. More information at this blog post.

8 comments:

Blaarp said...

I suppose this could also be used for transferring what one could call "top priority messages" via two different couriers ?

Dirk Rijmenants said...

It is possible, but I would not recommend it for security reasons. Image you as a courier kidnapped and dragged into some deserted factory. And there's your courier partner, completely beaten up. And then the gorilla next to you: "and sir, do you have anything to tell to us?"

Blaarp said...

Well, that is if one considers "couriers" as actual people, but I guess I haven't really chosen the right word. Was thinking more like down the lines of sending the info via two different delivery methods.

Good point you've made, though ;)

Dirk Rijmenants said...

Oh I get it :) Sorry for that poor guy I sent out on his kamikaze mission :o Two different ways of relaying the message wouldn't be absolutely secure any more, but the attacker would have to find out how and when it was sent and this would require recources to monitor and intercept various means of communications. It would get very difficult to get hands on the message... but not impossible. You would almost need to have an Echelon-like SIGINT organisation to track down the two shares of the message.

Blaarp said...

Well, let's just say that for rather everyday situations (ok, who of us has to transmit communications via encrypted channels on a daily basis? :P) one could decrease the chance of the message being intercepted by sending one via SMS and other via snail mail, for example ? :P

Not meant to be some high security implementation of the method, just making tracing communications for a Joe Average a bit more difficult :P

Dirk Rijmenants said...

Well, not a bad idea, and I added it to the Secret Splitting article on my website ;-)

Amar said...

Hello

I Did not understand the subtraction , Could you please explain how it works.

Thank you

Dirk Rijmenants said...

Hi Amer,

Modulo 10 subtraction is quite simple. You never borrow nor carry. Some examples:
8-5=3 that's obvious
If the subtraction result would be less than 0, you then add 10:
2-4=8 bacause [1]2-4=8