How do you share encryption keys securely, even with people you’ve never met, when all you have is an insecure network to send and receive data?
For decades, received wisdom said it couldn’t be done.
Join us for the fascinating story of how researchers in the UK and the US independently confronted and solved this vital problem…
Share a secret to share a secret
We write about encryption fairly regularly on the SolCyber blog, given how important it is in our online lives.
We’ve covered a number of issues recently, from the threat that quantum computers may pose to cryptographic security, all the way to why we’re still seeing so much unencrypted data stolen in data breaches, even though encryption is now a regulatory requirement for many online services.
In our most recent article about cryptography, we went back 2000 years to Julius Caesar’s cipher, where each letter in the input is switched for a different letter in the output.
We noted that even though the Caesar cipher is trivial by contemporary cryptographic standards, it nevertheless fits the common pattern of how we usually think about encryption.
Firstly, there’s a scrambling and unscrambling process, which you should assume will be public knowledge, not least because once you start using it, anyone you correspond with will need to know the algorithm anyway.
Secondly, there’s a secret key that should very definitely not be made public, and that ideally should be different for every account or service with which you exchange data.
The Roman historian Suetonius reported that Caesar used the same key, a shift of three characters, for all his communications with all his correspondents. Don’t do that! It wasn’t safe in 50BC and it certainly isn’t safe in AD2024. Criminals who crack the password to any one of your accounts or messages will automatically try that same password as widely as they can elsewhere in your online life, in the hope that the same key fits more than one of your digital locks.
Keeping the secrets secret
If you’re backing up your own data to a removable hard disk so that you can recover it later in the event of a catastrophe, an algorithm with the same key to lock and unlock the data is ideal, given that you’re the only person who needs to know the secret.
But what if you want to share data securely with someone else, as Caesar did when he wrote privately to his political and literary connections?
You have to share that secret key with them at some point, whether that’s before, during, or after the scrambling process.
And there’s your conundrum.
If your communication system is secure enough to transmit the secret key that unlocks the whole message, then it’s secure enough to transmit the message in the first place, so the key and the encryption are unnecessary.
But if you need the key and the encryption because your communication system isn’t secure enough for the message, then it’s not secure enough for the secret key either, so you can’t use it to share the key with the recipient.
The traditional solution to this problem is to use a secure system, albeit one that is more cumbersome and more expensive, to exchange your secret encryption key up front.
Then you can use that secret key for the next few hours, days or weeks to send a much greater volume of secret data over a faster, cheaper, but otherwise insecure channel.
As an example, you could meet up in person once, or use a trusted physical courier, to share the key in advance, after which you can exchange encrypted data securely in a wide variety of public ways, including via the regular postal service, over a foreign government’s untrusted telephone system, or using open radio networks that anyone can connect to.
The approach of carefully sharing secret keys in advance worked, more or less, until about the end of World War 2, although the distribution of keys was already a troublesome problem as early as the the 1930s.
For example, as we have noted before, the Nazis fielded approximately 40,000 of their infamous Enigma cipher machines before and during Word War 2, and needed to distribute monthly lists of pre-printed daily encryption keys to all users in the field.
This added massive expense, logistical complexity, and operational danger to the Enigma network.
If users of a secret-key encryption system run out of key material in the field because the next month’s lists don’t arrive, then the entire network is immediately at risk.
If some units received key updates and others didn’t, perhaps because those keys were captured rather than destroyed or simply lost, then it’s not safe for any units to rely on the new keys in case they’re now known to the enemy.
And if key material couldn’t be distributed at all, perhaps because the logistics unit responsible for printing the keys ran out of vital raw materials such as printing plates or ink, then the field units have little choice but to re-use outdated keys that may already have been cracked by the enemy.
More users, more messages, more keys
Despite all these logistical challenges of using secret-key cryptography in the field, cryptographic wisdom insisted that that secret communications were possible only by using secret-key algorithms with pre-shared secret keys.
This state of affairs continued for more than two decades after World War 2, even though the Cold War ramped up through the 1950s and 1960s, even though many colonized countries fought to become sovereign independent states, and even though the importance, speed and volume of digital communications increased.
Military and diplomatic services around the globe therefore found themselves spending more and more money just to share encryption keys to enable them to communicate securely.
No matter how much the cost and complexity of secure key distribution might be reduced, it seemed it would always and inevitably be a part – perhaps the most expensive part – of any cryptographic system.
Challenging the assumptions
This dependence on secret-key encryption was summarized by James Ellis, a cryptographer at Britain’s GCHQ (Government Communications Headquarters, the UK’s equivalent of America’s NSA), in the very first paragraph of a secret report dated January 1970 (the report was declassified in the late 1990s):
It is generally regarded as self-evident that, to prevent an interceptor from understanding an [encrypted] message […], it is necessary to have some initial information known to the sender and the recipient but kept secret from the interceptor. [… There must therefore be] a route by which this secret information can be sent without fear of interception. [… Large quantities of cipher text of high security thus tend to need the parallel transmission of smaller but still substantial quantities of secret information.
Ellis, however, had stated this assumption as a precursor to challenging it, not to accepting it.
Indeed, in the very next paragraph he delivered a profound bombshell:
This report demonstrates that this secret information is not theoretically necessary and that, in principle, secure messages can be sent even though the method of encipherment and all transmissions between the authorized communicators are known to the interceptor.
Ellis gave this process the delightfully paradoxical name “non-secret encryption”, by which he meant that secure encryption – the sort that would indeed reliably preserve secrets – could be carried out between a sender and a recipient who had not shared any secret keys in advance.
Unfortunately, there was a catch, which Ellis admitted in his summary, right on Page 1, before his introduction, and even before the table of contents:
This report considers the problem of achieving secure transmission of digital information in the circumstances where there is no information initially possessed in common by the two legitimate communicators which is not also known to the interceptor. It demonstrates, by means of a model having the required properties, that a theoretical solution exists, but does not establish that a practical system can be devised.
Close, but no cigar.
Ellis had devised what mathematicians call, and that he explicitly referred to as, an existence proof, not a practicable solution.
So, by the very start of 1970, British intelligence, perhaps uniquely among security services worldwide, knew that non-secret encryption was worth researching, because there were no immediately obvious laws of physics or of mathematics that made it impossible.
But GCHQ didn’t yet know how to make it work, or even if it ever could.
Involving the recipient
Ellis’s breakthrough was to realize that if the recipient played an active part in the enciphering process, instead of merely being a passive player as in all previous encryption systems, then a non-secret encryption system might indeed be possible.
Very greatly simplified, Ellis devised a mathematical procedure in which encryption and decryption use different keys, unlike traditional secret-key encryption systems where the same key is used both to lock and unlock the data.
The idea is that the recipient, rather than the sender, starts by choosing a random decryption key D, which they keep to themselves for later, when they receive encrypted data from the sender.
The recipient computes a matching encryption key E from their randomly-chosen decryption key D, and sends it publicly to the sender.
The sender then encrypts their message with E and sends the scrambled data publicly to the recipient, who decrypts it privately to recover the original message.
In modern jargon, the encryption key E is known as a public key, because it can be revealed to anyone.
The decryption key D is today known as a private key, because the recipient keeps it to themselves so no one else can decrypt data that’s been locked with their corresponding public key.
Where Ellis rather curiously called this process “non-secret encryption”, even though its purpose is to keep secrets, we now equally curiously call it public-key cryptography, even though its purpose is to keep data private.
How does it work?
At this point, you’re probably wondering, “But how could Ellis’s system possibly work?”
After all, if the recipient can randomly generate a private key D, and use it to create the matching public key E…
…what’s to stop an attacker simply doing the same thing in reverse, and using the public key E to work out the matching private key D?
How do you ensure that the process of generating a matching pair of public and private keys is easy in one direction, but hard in the other?
Unfortunately, Ellis didn’t find a usable solution to that problem.
As we have said, he only went as far as creating an existence proof, based on assuming that you had created a random lookup list to convert every possible private key D into a unique public key E.
That way, acquiring the public key to match a specific private key would involve a single lookup in the list, which is easy in theory: jump directly to the Dth item in the list and read out the appropriate value of E.
But going the other way around would involve searching entry-by-entry through the list, which is hard both in theory and in practice: loop through the list from D=1 to D=length(list) until you find the entry with the public key E.
By making the lookup list long enough (he imagined 2100 entries, with the list consisting of a random permutation of the numbers from 1 to 2100), Ellis was able to demonstrate the mathematical validity of the system.
But actually generating a lookup list containing 2100 randomly permuted numbers is impossible, because the amount of storage space needed is far too large, even in 2024, and Ellis wasn’t able to devise a compact mathematical algorithm that would achieve an equivalent result.
He wrote, at the end of his report:
Attempts to find solutions […] have so far been unsuccessful, but have seemed tantalisingly near to success at times, so that one feels that a solution probably does exist. There is certainly no apparent reason to believe it impossible. […]
In any case, it is hoped that this report will stimulate those proficient in these matters to find a practical solution.
In a masterful understatement, he concluded with the splendid observation that:
The potential advantages are too obvious to need specification.
Join us next time for Part 2 as we dig into the twists and excitement of how James Ellis’s hopes ultimately came true, first in Britain, and then soon afterwards in the USA…
Why not ask how SolCyber can help you do cybersecurity in the most human-friendly way? Don’t get stuck behind an ever-expanding convoy of security tools that leave you at the whim of policies and procedures that are dictated by the tools, even though they don’t suit your IT team, your colleagues, or your customers!
More About Duck
Paul Ducklin is a respected expert with more than 30 years of experience as a programmer, reverser, researcher and educator in the cybersecurity industry. Duck, as he is known, is also a globally respected writer, presenter and podcaster with an unmatched knack for explaining even the most complex technical issues in plain English. Read, learn, enjoy!
Featured image by Nathalia Segato via Unsplash.
