How to make a shared secret
Dear bank; let's share a secret
I have had running battles about security with banks over decades; more or less ever since they started offering online banking.
Every now and again I get an incoming phone call. The number is withheld; so far I have no idea who's calling.
I pick up and someone says "Hello Ian, I'm calling from [some bank or other - let's pretend it's a bank of which I am a customer]. I need to talk with you about your account. But first I need to take you through some security questions."
At this point I usually say "Let me stop you there. You called me; how do I know you're from [bank]?" And frankly the call doesn't last much longer. They won't discuss whatever the issue is, and I won't divulge secure personal information to a complete stranger cold calling me.
A lot of times when I get this kind of call, it's probably a criminal trying to get my security information. But actually two of the banks that I use also employ this kind of cold call. They call me, usually from a withheld number, and ask for my security information. They often get a little shirty when I refuse to give them what they want, especially when I point out to them at length what a major flaw in their own purported security they are using. Why is it a flaw? Well, check out some typical phone bank frauds to see how scammers try to use what information they have on you in order to break into your accounts.
Clearly this is an unsatisfactory situation. Banks (at least in the UK) are very quick to trumpet their credentials as guardians of their customers' security. But at the same time they employ highly questionable cold calling tactics.
So what can we do?
One approach, I think, is to set up a situation whereby a bank that calls you can provide you with the same kind of secret information that they ask you to provide when you call them. Fair's fair.
Here's how it might work. You pick up an incoming call. The number is withheld; so far you have no idea who's calling. The person at the other end says "Hello, I'm calling from [bank]. I need to [etc.]. You say "OK. Can you give me the first and third characters from our shared secret?" They say "Sure; it's Z and Q", and then it's likely to be OK for them to ask you for security information. Or maybe they just say "nnnng" and hang up; chalk one up for the good guys. If you have agreed a common shared secret with your bank, you have a mutually secure way to know who you are talking to.
But having a shared secret is a pretty hard thing to do. How could you make such a thing work in practice? Well, the simplest way would be to extend the use of the key phrases that banks often make you use now; they will ask for a secret word such as your birth place, your first car, and so on. If we could just agree one of these as a shared secret with the bank, that would be a step forward. However, it's not a terribly secure solution, because it relies on information that could potentially be known or discovered by others. What else is there to consider?
I invite you to explore the brilliant work of cryptographic geniuses Whitfield Diffie and Martin Hellman.
Diffie-Hellman and shared secrets
The Diffie-Hellman algorithm was ground-breaking. Its appearance provided the first answer to the problem of key exchange. It also led more or less directly to the development of asymmetric ciphers, the best known of which is RSA.
Introducing Alice and Bob
If you read articles on cryptography you will see frequent references to Alice, Bob and other players in the encryption process. There is a fairly well-established cast of characters in the cryptography world. The main ones we will need to think about are:
- Alice and Bob. These are the people who need to share information through an encrypted mechanism.
- Eve. She tries to eavesdrop on the information passing between Alice and Bob.
The problem of key exchange
Before the Diffie-Hellman algorithm, the area of strong encryption was well established but also fragile. The one-time pad, still the most unbreakable ("perfect") encryption mechanism known is a good example both of the kind of systems in use and of the major flaw. The one-time pad relies on both parties having a common list of encryption keys that are used to turn plain text into ciphertext (and back again, naturally). The original one-time pad was literally a pad of paper with each page filled with a different set of letters and numbers. Both parties to the encryption had a copy of the same pad, so they just had to agree (if necessary, over a public channel) which page to use for the current encryption job. Once used, that page is destroyed; a page in a one-time pad can never be re-used because it would completely compromise the security. Here is a nice illustration of how that happens.
So how do you ensure that Alice and Bob - and only those two - have access to the encryption keys? It may be that they never meet in person, so some mechanism has to be found to get the encryption keys safely shared between them without Eve getting hold of them.
Of course, if there is a reliable way for Alice to send a key only to Bob and vice-versa, there is no need to encrypt your messages, right? Just use that route to send the message itself. The fact is that before the work described on this page, people had to go to extraordinary lengths to ensure relatively safe transfer of encryption keys, and it was impractical to send messages themselves by the same route. All of which makes what Messrs Diffie and Hellman did such a brilliant achievement.
Simon Singh gives an excellent account in his book The Code Book of the work of Whitfield Diffie and Martin Hellman in developing the algorithm. You could also go back to the original paper published by them if you want to see the primary source. I'm going to use this page to explain how the algorithm works and why it is so elegant.
An overview of the Diffie-Hellman key exchange process
Alice and Bob want to exchange some information. They would rather not let pesky Eve see the information. They can encrypt the document using symmetric encryption provided that they can find a common encryption key and prevent Eve from knowing it.
Alice and Bob start by agreeing two numbers (j and k). These two numbers are publicly-known, so it doesn't matter if Eve knows what they are.
Alice and Bob then each think of a secret number (we'll call them Sa and Sb). They will never reveal these numbers to anyone else (not even each other). However, they each run a calculation (more on this below) using S, j and k. Alice comes up with Pa and sends it to Bob. Similarly Bob comes up with Pb and sends it to Alice. Once again it doesn't matter if these numbers are intercepted by Eve.
Now comes the magic bit. Alice does another calculation using her secret value Sa and Bob's public value Pb and comes up with Xa. Bob does a similar calculation using his secret value Sb and Alice's public value Pa and comes up with Xb.
The magic of the Diffie-Hellman algorithm is that Alice's final number Xa is the same as Bob's final number Xb. In other words, Alice and Bob have created their common key, and they have done it without passing the actual key directly between them or risking it being intercepted by anyone else.
When I first learned about Diffie-Hellman, two aspects of this struck me as difficult to believe. First, how is it that the two numbers end up being identical? Second, how sure can Alice and Bob be that Eve (who, after all has been able to see the numbers j, k, Pa and Pb) can't work out the key Xa (or Xb, since they are the same)? In each case, the answer lies deep in the ingenious mathematics that underlies the process.
Diving into the mathematics
I use the term "diving" advisedly. There are some seriously complex concepts to take on from the word go. Let's just run through the algorithm first, running Alice and Bob's key exchange again but doing the mathematics this time.
First, Alice and Bob agree on two numbers, j and k. Alice also chooses a number, Sa, that she will keep completely secret, and uses this formula to calculate Pa.
Pa = (j ^ Sa) mod k
This says raise j to the power Sa (multiply j by itself Sa times), then divide the result by k and save only the remainder as Pa.
Bob does a similar calculation using j, k and his secret number Sb and ends up with Pb.
A brief aside
At this stage you may be thinking "that calculation doesn't look too difficult. Why can't Eve simply unwind it, given Pa or Pb, and work out Sa or Sb?" The answer lies in the type of calculation - modular arithmetic. Let's look at the numbers. Suppose j is 2 and k is 7 and Alice chooses 3 as her secret number.
Alice's calculation is now Pa = (the remainder of (2^3) divided by 7).
2^3 =8
8 mod 7 = 1
Pa = 1
The key step is the division mod 7. It is this that makes this a one-way function, because there are potentially a huge number of values of Alice's number Sa that would give a Pa value of 1. She has chosen 3 on this occasion, but she might have equally well chosen another number that would give a result of 1 when the answer is divided mod 7. The effort involved to find another value of Sa that gives this Pa even with small numbers like this is too much to think about, and then you don't know which of the many possible Sa values is the one Alice actually chose - they all give the same Pa.
Incidentally, this one-way (or trap-door) feature of modular arithmetic is one of the reasons that it crops up so often in cryptography. Functions that are easy to do one way but very difficult (infeasible is the term often applied) to do the other way are where cryptographers look for their tools.
Anyway, back to the calculation
So far, Alice has used her secret number Sa to create a public number Pa that she now sends to Bob. Bob does the same with the public number Pb that he has created.
Alice carries out the following calculation:
Xa = (Pb ^ Sa) mod k
And Bob carries out the following calculation:
Xb = (Pa ^ Sb) mod k
It turns out that the values the Alice and Bob have calculated, Xa and Xb are identical. They have therefore created a common key that they can use as an encryption key for exchanging encrypted data.
There is no room here for a proof of this (translation: I wouldn't know how to start doing a mathematical proof of anything), but there is at least one such proof on the internet. However, here is a worked example to demonstrate the calculations.
Worked example
Let's assume j = 5, k = 563, Sa = 9 and Sb = 14.
Pa = 5 ^ 9 mod 563
Pa = 1953125 mod 563
1953125 / 563 = 3469.138544, or 3469 with a remainder of 78. This makes Pa = 78
Now for Bob. His calculation is:
Pb = 5 ^ 14 mod 563
Pb = 6103515624 mod 563
6103515624 / 563 = 10841057.95, or 10841057 with a remainder of 534. So Pb = 534
Once keys have been exchanged, Alice can do her shared key generation:
Xa = (Pb ^ Sa) mod k
Xa = (534 ^ 9) mod 563
Xa = 3530785328217308860798464 mod 5633530785328217308860798464 / 563 = 6271377137153301706569 with a remainder of 117
Therefore Xa = 117
And here is Bob's version:
Xb = (Pa ^ Sb) mod k
Xb = (78 ^ 14) mod 563
Xb = 308549209196654470906527744 mod 563
308549209196654470906527744 / 563 = 548044776548231742285129 with a remainder of 117
Therefore Xb = 117
The shared secret that only Alice and Bob can know is 117.
Obviously, in a real world case the numbers used here would be much larger and less guessable, and so the shared secret would end up as a very large (and far more unguessable) number. But what works here will work with real life cases too.
The real underlying cause of the identity of these calculations is that
j ^ (Sa * Sb) mod k = 117
The other calculations provide each of the participants with a mechanism of getting an equivalent calculation to that one, since (not having access to both Sa and Sb, neither Alice nor Bob can do that calculation).
In conclusion
I can't overstate the importance of the technical insight that Diffie and Hellman had in coming up with the shared secret key exchange algorithm. While it was soon superceded by RSA and other cryptographic developments, the Diffie-Hellman algorithm still stands as a milestone achievement in the development of safe, usable everyday cryptography. And the next time your bank calls you and asks for your security information, blow them a raspberry and say you want a shared secret.