I like to keep the above quote by H. L. Mencken always in mind because it is a useful caution whenever one is weighing in on weighty issues on which one is not an expert. Like pretty much everyone else, I sometimes have a brainwave about some deep or complex problem (usually in a field that I am not that familiar with) in which a simple solution suddenly stares me in the face. I then wonder why no one else has thought of this ‘brilliant’ solution before and the usual answer is that people who do know a lot more about this topic are well aware of this proposed ‘solution’ and also know why it will not work.
Recently, I had such an idea about one way to overcome the security issues involved in sending information over the internet and foiling ‘man-in-the-middle’ attacks. I am pretty much a novice in the area but have a little knowledge about things like PGP. I believe that sending encrypted messages using PGP involves a private encryption key (known only to the sender) and a published public key for the recipient and to break the security requires difficult prime number combinatorial challenges. I was wondering if there could be a system that did not require public keys at all but only private ones and thought of a simple possible solution.
My idea can be best explained by analogy, by what might have been done in the old days if you wanted to send something securely to someone else by (say) sending it in a box with a padlock on it, but without also having to send the key to the lock or prearranging things so that the sender and the receiver have identical keys. What you could do is lock the box with a padlock to which only you have the key and then send the box. The recipient cannot unlock it but instead adds their own padlock to the box to which only they have the key and then sends the box back to the original sender, now with two padlocks on it. The original sender then unlocks their own padlock with their key and sends the box back with just the one padlock which the recipient can now unlock because it is their own padlock.
In the case of encrypted messages, the first person would take a message M and encrypt it in some way using some algorithm A to create an encrypted message AM (interpreted as algorithm A acting on M to get the encrypted AM) and send it. The recipient would then encrypt that already encrypted message using their own algorithm B to get a doubly encrypted message BAM and send it back to the original sender. The original person would then decrypt this doubly encrypted message using just their own decryption algorithm A-1 to get A-1BAM. (Note that A-1AM=M. i.e., applying the decryption A-1 to its own encrypted message AM gives you back the original unencrypted message M.)
The key step here is whether the original sender’s decryption algorithm A-1 can take the doubly encrypted message and reverse just their own original encryption, leaving the message BM. Writing this symbolically, the question is whether it is possible to have the decryption operation A-1 and B ‘commute’ such that A-1B=BA-1. If so, then A-1BAM=BA-1AM=BM. This message can then be sent back to the recipient who then just decrypts their own encryption using B-1. This system requires the message to go back and forth but that should not be a big problem.
This is possible for simple encryption systems like where A and B both shift letters by fixed amounts that are different for A and B and known only to each person. For example, suppose A shifts every letter in the message to p letters later in the alphabet and B shifts the letters in the encrypted message to q letters later in the alphabet. Hence the doubly encrypted message would consist of letters shifted by p+q. Then A-1 would shift letters up the alphabet by p (known only to the sender), leaving the final message shifted just by q (known only to the recipient). But this system is too trivial and also requires pre-arrangement by sender and recipient to use similar algorithms.
But would it be possible to find at least some reasonably complex algorithms A and B for which it would work? I had no idea if this was possible so what I did was send this idea privately to Marcus Ranum, our resident guru on FtB for computer security, and he said that this would not work for various technical reasons that I do not quite understand.
This is why it is always a good idea to ask experts before investing too much time and energy on your simple but ‘brilliant’ idea. As the poet Alexander Pope warned,
A little learning is a dangerous thing;
drink deep, or taste not the Pierian spring:
there shallow draughts intoxicate the brain,
and drinking largely sobers us again.
he said that this would not work for various technical reasons that I do not quite understand.
We have to carefully define “work” -- does that mean it’s secure, or efficient, or better than ${whatever} by a certain amount, or more resistant to replay attacks, etc.
The problem with a lot of cryptosystems is that “works” needs to mean “is substantially better or easier to use than pre-exchanged secrets” and that’s a high bar, because pre-exchanged secrets are really, really, good. It turns out that easy ways of communicating securely often don’t do a very good job of authenticating the communicants -- in other words we can easily set up a temporary key and exchange it using Diffie-Hellman but how do I know who I just exchanged keys with? It’s probably some NSA guy in the middle of our channel. So we then introduce additional mechanism to authenticate, which seems to me to inevitably boil down to a pre-exchanged blob of data sitting on a hard drive running on a Windows operating system -- in other words, it may as well be written on a bathroom wall in Berlin.
So, the bar I compare systems to is the amount of pre-exchanged ${what} and how the system manages that. If the answer is “that’s an out-of-band problem left as an exercise” that’s fine but it’s hard to find such a system superior to a one-time pad with some database foo and workflow around it.
To give you an idea what I mean, consider SSL and the whole infrastructure around internet certificates. How do you know who is whom? Well, the certificate is counter-signed by a certification authority that attests to the validity of the certificate. How do you know the certificate authority is not the CIA? Actually, it is. And there are lots of certificate authorities and most of the use of internet certificates treats a certificate as valid if any of a large(ish) list of certificate authorities has signed off on them. How do you know any of this is anything? Simple: your device (or browser or o/s) comes pre-populated with them. In other words the system’s integrity is as good as a pre-exchanged file sitting on a hard disk, or about as good as a password written on a wall in a bathroom. Actually, a password written on a wall in a bathroom is probably much better, depending on your threat model.
One bad habit internet security people have is to look at the technical whizzyfridgets of a thing and not step back and look at the overall context and use cases and threat model. When you do that, you usually wind up laughing at most of internet security. As Robert T. Morris Sr (the NSA’s chief scientist) famously told a few of us at a meeting, once, “most use of cryptography on the internet amounts to using a Brinks Armored truck to take a paper bag across town and taping it under a park bench.”
Another issue we seldom look at/think about are side channels. Is there anything I can learn about communications just from the speed and compute resources it’s taking? It turns out that major cryptosystems, including RSA, easily fall to side channel attacks if not designed correctly. I’m not a good enough cryptographer (as you can tell, I tend to be more dismissive of cryptography than to engage with it…) to do that kind of analysis -- and, apparently, neither are many of the designers of important internet protocols. For one example, Paul Kocher determined (this was back in the late 90s) that a huge number of public key systems could be compromised by precisely measuring the amount of time it took for them to do the computations, then based on the speed of the target CPU you can get a fairly good estimate of the size of the RSA secret exponent -- good enough to quickly do a brute-force search. Oops. So, those algorithms were fuzzed up to be less predictably efficient and then it turns out that if the target is using a CPU that does power management, you can tell by the current draw how hard it’s working, etc. That’s an endless pit of despair when you start getting in there.
So I look at all that stuff and keep asking “how’s it better than a pre-exchanged secret?” and it almost always isn’t. It can be a lot more complicated, though, and it can employ more coders and cryptographers and NSA analysts, so there’s that.
Oh, and typical me, I completely failed to make the point I meant to make: I think your system may be vulnerable to replay attacks. But that’s because most are. Usually, dealing with replay or laundering attacks entails an outside infrastructure to authenticate messages, which always seems to boil down to a file pre-exchanged, sitting on a hard drive.
Replay attacks are a big nasty problem. For example, Microsoft Windows’ authentication scheme has notably been vulnerable to them for a long time. “Pass the hash” [pth] attacks are a form of replay attack: you capture a cached credential someone else set up, and use that. There are also ways of inducing replay attacks such as authentication laundering attacks against things like two factor authentication. (The reason two factor authentication works at all is because most people don’t give a shit about it)
Anyway, I think the system you outlined would fall on not being better than a pre-exchanged secret, and would fall to replay attacks. I’m not sure about the latter but I’m not a cryptographer. (And even cryptographers get this stuff wrong shockingly frequently)
Now if only Silicon Valley could learn that lesson…
(The encryption would also be open to a man-in-the-middle attack: You hand the lockbox with your padlock to the mailman, the mailman turns around, puts their padlock on it, makes a pirouette and gives you the lockbox back. You remove your padlock believing the other padlock belongs to your intended recipient, pass the box… and the mailman walks away, laughs their behind off while looking through the box, making copies and all, then locks it again with their own padlock and goes to the home of the recipient where they repeat the ceremony.
How can you determine that what you get is really BAM and not CAM?)
Marcus #1 and #2,
I seem to recall reading (maybe in a John Le Carre novel) that one system used a code that depended on using the text in a book to generate the encrypted message. So all you would need is for the sender and recipient to have the same copy of the book. I’m guessing that would be an example of a pre-exchanged secret.
Aside from any boring technical details, you’re system adds literally zero protection against man-in-the-middle attacks.
You send your locked box off, and it comes back with two padlocks. How do you know that it it your intended recipient’s padlock, and not the MITM’s padlock? That is a problem of authentication, not encryption. Since they’re standing in the middle of your transaction, they can simulate the entire transfer. If you don’t have a way of knowing with confidence whose padlock is on the box, you have no security against identity spoofs.
As Marcus laid out above, for all the fancy math that goes into it authentication fundamentally boils down to the question of “who do you trust?” For internet authentication, the list of preinstalled Certificate Authorities are the word of god. If one of them can be compromised or coerced into signing certificates maliciously, you have no protection against identity spoofing.
Glor @#3 and Mark @#5,
You have exposed a major flaw in my system that had never occurred to me though it seems obvious once you stated it.
See, this is what I mean by needing to first check with others before spending too much time on a system!
Yep, authentication seems to be the big concern here.
@Mano:
Let me introduce you to Vernam’s Cipher (“the one time pad”) [r] It’s a thing of rare beauty. Once you really understand them, you can be said to know everything you need to know about security. How can an encryption system be perfect, yet practically unusable? How can an uncompromisable system be compromised through user error? It’s a perfect example of how a system can be so good its weakest link is always the user’s procedures.
Mano@#4:
I seem to recall reading (maybe in a John Le Carre novel) that one system used a code that depended on using the text in a book to generate the encrypted message. So all you would need is for the sender and recipient to have the same copy of the book. I’m guessing that would be an example of a pre-exchanged secret.
Sort of…
Your comment deserves a lengthy reply; brace yourself.
The problem with book ciphers is that the book is shared but not secret.
There are other problems with them and, in fact, the great William Friedman -- the NSA cryptographer credited with connecting statistics and cryptography -- first got involved in cryptography because of book ciphers (the question being “did Bacon encode anything in his ‘Shakespeare’ writings?”) Friedman realized that the statistical distribution of letters, and two-letter and three-letter combinations gets carried forward in certain cryptosystems. So if you used a book in Latin, the letter frequency of the book would be Latin, and so would the frequency of the encoded message (depending how you did the encoding) That’s kind of cool. How do you fix this? You can use different encoding, or you can use a book that is all random letters! If you do that latter thing, and you carefully control the distribution of the book to only 2 parties, you have a one-time pad (Vernam’s Cipher). One of the interesting properties of one-time pads is that they defeat any and all statistical attempts to attack them. They actually, provably, defeat all attacks if used correctly which is nearly impossible. [Side note: in the mid 90s a friend of mine and I actually did our best to exchange messages using one-time pads. We generated the pad on a laptop running on battery power, below ground, using random numbers sampled from a camera pointed at a lava lamp, and didn’t plug the systems into networks and kept them in safes when not in use. The first message I got read ‘This sucks.’]
There are some things Shannon probably figured out about information density (probably not the right word) in book ciphers. Let’s say you encode by giving ${ page #, word # } per word. That’s denser than using ${ page #, word #, letter #}! But in the first case your distribution of words will eventually allow someone to begin searching based on word frequencies, and in the latter, eventually on letter frequencies. Suppose I know your book is in Latin -- I can start brute-forcing using the most common Latin words if I have a computer, and I can start looking for whether what comes out the back is structured like meaningful phrases.
Computers killed book ciphers but (in my opinion) make one-time pads nearly practical. What is certainly practical is preserving exchanged secrets. That’s a technique nobody wanted to do when SSL was first coming along (I was at TIS at the time and peripherally participated in some of those arguments, but mostly I stood on the sidelines and sneered dismissively) By the way: I was right. What we see as SSL security is just using SSL to set up temporary pipes over which we send credentials encrypted with exchanged keys. We call those exchanged keys “cookies” but basically they’re passwords/secrets that sit on a hard drive somewhere. We’d have done much better to just accept that that was what we were doing, and do something simpler and cleaner. But, had we done that, the NSA would have found it harder to backdoor, and -- really -- SSL was all about RSA monetizing their public key patents and never was about security in the first place. The whole thing is potemkin crypto.
Anyhow, if you have all the books in Google books and your target has used one of them, their plaintext would pop right out if you were able to figure out the right encoding.
One more comment on encoding: the encoding becomes the secret! (It’s just not a very good secret) Eventually, this becomes the train of thought that leads to how ENIGMA worked and Feistel Network ciphers. You want to make your encoding change with each letter. Which means your encoding becomes a mathematical function on your secret. So, suppose our coding is:
${ page #, word #, letter #
and we change it to keep a running register with a hash of our input. Let’s say that’s represented as two characters. Then our encoding is:
${ page #, word (# + char 1), letter (# + char 2) }
Now, the attacker (in principle!) needs to know something about our message in order to attack it statistically. I do not know the term for this but I always thought of it as “jumping through your own asshole” -- I’m sure cryptographers have a term for it that’s better. What a Feistel Network cipher does is sets up multiple encodings, each of which permutes with each input letter. That’s what the ENIGMA did: each time you encoded a letter, the encoding wheel rotated, which changed the electrical connections making up the letter. Feistel Networks are abstractions of ENIGMA and that’s how you get things like DES.
Mark Dowd@#5:
For internet authentication, the list of preinstalled Certificate Authorities are the word of god. If one of them can be compromised or coerced into signing certificates maliciously, you have no protection against identity spoofing.
Yup. Aaaaand, if you look at the list of trusted CAs in a typical browser or phone, there’s CAs run by every secret service of every major power. The whole fucking system was designed to work that way, and I can prove it: if it were not, there would be bi-directional authentication. Back in the day when all this was being put together, some of us said “if it’s not bi-directionally authenticating, I know it’s compromised. In fact I know that the standards committee is compromised.” *ahem* and look how it worked out.
What would bi-directional authentication look like? Well, you’d need an out of band key exchange. This is not a big deal, though! Signal and Proton mail both do it. Signal’s approach is based on the AT&T TSD2600, which was available in the early 90s briefly until the NSA strong-armed them into replacing the crypto with a Clipper chip. [I have an original TSD on my Shelf of Old Crap somewhere]
This is all going back to 1992-5. It was “game over” for internet security by 1997, and the CPUs with backdoors started showing up just around 9/11. From that point on, security became a cargo cult.
Mano Singham@#6:
Yep, authentication seems to be the big concern here.
For some applications it may not matter, though. So, it’s complicated. Suppose you have a message where you can take advantage of the structure or contents to authenticate it; i.e.: let’s say you know the correct balance in my account, and my account number. Well, then those can be used as a secret -- so long as they are secrets -- and you can key with them. For a transaction where the account number and balance are all the important information that there is there’s no point in worrying about authenticating beyond that. (In which case, if we are talking financial instruments, you have a bearer bond: the bond’s # is the key and if the issuing bank recognizes it, then the bond is authenticated)
The 1st Directorate did some bully work with self-authenticating messages in the USSR’s military crypto, although from the sound of it the NSA ripped their stuff apart like it was toilet paper.
Another amusing anecdote: Brian Snow (former commandant of NSA’s crypto academy) told me, “we have the resources and the skills, so we attack every system at every level.” Now that’s flippin’ chilling.
When I was a child, I spent a lot of time thinking about telescopes, and I had a brainwave: why not rearrange a reflector telescope such that instead of sending the focused light beam to a side-mounted eyepiece, why not send it back down the telescope tube through a hole in the main mirror? It would greatly increase the focal length for the same telescope length, and would look tidier!!
…Unfortunately, someone else had already had this brainwave, beating me to the invention of the Cassegrain telescope by a few centuries. Back to the drawing board for me.
Hi Prof. Singham,
Re: your blog post There is always a well-known solution to every human problem — neat, plausible, and wrong, the algorithm you suggest was first described by Shamir, Rivest, and Adelman (of the RSA algorithm fame), and is called the Three-Pass Protocol (https://en.wikipedia.org/wiki/Three-pass_protocol).
I couldn’t find a link to their original paper, but the algorithm is mentioned in this survey of cryptographic techniques, along with some simple ways of defeating it when communicating with an untrusted peer: http://www-users.cs.york.ac.uk/~jac/PublishedPapers/reviewV1_1997.pdf
The algorithm also has the inherent inefficiency of requiring multiple exchanges to transmit a single message, which might limit its adoption.
It’s an interesting idea nonetheless, and bears similarities to certain Secret Sharing algorithms (https://en.wikipedia.org/wiki/Secret_sharing). A trivial application is in the classic brainteaser of how three or more people can figure out their average salary without divulging their own salaries to each other: http://geekexplains.blogspot.com/2008/06/puzzle-avg-salary-without-disclosing.html
So far as I can tell no one has mentioned this. The described mechanism already exists as the diffie hellmen key exchgange system. As I understand it it’s already a key part of popular encryption systems, it’s how the key is exchanged to begin with.
“I like to keep the above quote by H. L. Mencken always in mind because it is a useful caution whenever one is weighing in on weighty issues on which one is not an expert. Like pretty much everyone else, I sometimes have a brainwave about some deep or complex problem (usually in a field that I am not that familiar with) in which a simple solution suddenly stares me in the face. I then wonder why no one else has thought of this ‘brilliant’ solution before and the usual answer is that people who do know a lot more about this topic are well aware of this proposed ‘solution’ and also know why it will not work.”
Oh, thats close to home. I am still waiting for my fathers (he is a software-programmer) “groundbraking” new theory of gravity (‘any day now’, for years). You asked a knowlegeable person and saw where your idea did not work that well and left it at that/went away educated (as we did all, thanks to your description and marcus’ explanations). The sad fact that the two physicist we know don’t talk to him any more really just strengthend his brainwave… .
Using Elliptic Curve Cryptography shared somethings don’t have to be secret – they can be public keys shared in person. Used correctly, the content of messages cannot be decrypted by third parties let alone spoofed or modified in transit. Use session keys for message exchange all signed by the never reveled secret keys that produced the shared public keys.