|
||
|
||
This article was co-authored by Anthony Thompson (President & Founder of Introspective Networks), Natalie Cummings (Research Writer) and Steven Cummings (Director of Network Solutions).
The OTP, or One-Time Pad, also known as the Vernam cipher, is, according to the NSA, “perhaps one of the most important in the history of cryptography.” If executed correctly, it provides uncrackable encryption. It has an interesting and storied history, dating back to the 1880s, when Frank Miller, a Yale graduate, invented the idea of the OTP. Communication was expensive and difficult in the age of telegrams, and few messages were easily encrypted. Miller laid out his solution to this problem in the preface of a codebook used to reduce the cost of telegrams by shortening messages. His theory used a pen-and-paper system, relying on printed keys to be safely distributed to both parties. Experts theorize that he probably didn’t even realize its potential, and his discovery was soon forgotten. In fact, Miller’s codebook was only unearthed in 2011.
The better known inventor of the OTP was Gilbert Vernam, who lent his name to the Vernam cipher. An AT&T engineer, he developed and, in 1919 patented a system for cryptography using punched tapes to store a randomized key. Still, though, the parameters of the OTP had not been defined. When Captain Joseph Maubourgne saw Vernam’s machine, he laid out many of the conditions necessary for an OTP today, such as using a truly randomized key which would be destroyed after one use. Though this version garnered some use from the commercial sector and the military, it also went largely unnoticed.
The OTP finally gained some traction in the 1920s when three German cryptologists, Kunze, Schauffler, and Langlotz, independently discovered it. They returned to the pen and paper system, similar to what Miller had proposed. The random sequences of numbers would be printed on small pads of paper which would be ripped off and destroyed after use, giving the system the name One Time Pad. Today, this format is most common in espionage operations, in which a small pad of paper can be easily and discreetly distributed to both parties. The German government adopted the system in 1923.
The most famous item in cryptography used in World War II was probably the Enigma machine. Its intricacies were seemingly uncrackable, but it was famously decoded after much time and effort. The Polish Cipher Bureau reconstructed an Enigma machine and used it to decrypt German communications for much of the 1930’s, finally sharing with Britain in 1939. Had the Germans used a properly implemented OTP system, it would have been completely uncrackable, and the outcome of WWII could have been entirely different.
With the more practical system in place, many other sources began to utilize this encryption technique. In the 1940s, Claude Shannon proved mathematically that if all of the requirements of an OTP are met (truly random numbers, disposal after one use, etc.), it is uncrackable. This strengthened the OTP’s reputation, as well as making it the only truly secure cryptography technique. In this same decade, the United States government began the Venona project in an attempt to crack the code that the Soviets had been using to send messages during the war. Had the Soviets followed the requirements of an OTP, the U.S. would never have been able to decode the messages; however, some pages of keys were reused, and later into the project some partially undestroyed keys were found. The repetition of keys was especially important; while OTPs are completely uncrackable with constantly unique random keys, once a key is reused it becomes susceptible to cryptanalysis. The decoding of these messages led to the arrest of the Rosenbergs, who had been giving away atomic bomb secrets.
The SIGSALY was Another interesting World War II era device based on the principles of the OTP. The SIGSALY was a voice encrypter, which recorded the voice, compressed the frequencies of the messages, and then added in a track of background noise which made the original message impossible to hear. Only two copies of this background noise were made, which is where the similarity to the OTP comes in. These copies were put onto records, one of which was distributed to either end of the system. Then, the background noise could be removed, the frequencies decrypted, and the original message received. Since there were only the two discs of background noise, encryption by other sources was practically impossible. The machine worked well, but it was expensive and time-consuming, and was only used a few times.
In 2012, an encrypted message from WWII was discovered in a highly unlikely place. A British man found the skeleton of a carrier pigeon in his chimney, with a message still intact and attached. After analyzing the message, authorities still cannot begin to crack it, and have deduced that the message was encoded using an OTP. The codebook was likely destroyed after the message was not received, demonstrating the lasting reliability of the OTP.
During the Cold War, the concept of OTP was used with One Time Tape (OTT), similar to the Vernam Cipher. After the Cuban Missile Crisis, both American and Soviet leaders recognized the importance of a direct and secure means of contact between the two countries. To resolve this, they built the Washington-Moscow Hotline, utilizing the OTT, which used teleprinters and identical tapes to relay messages securely. The intended message would be typed in both English and Russian, transmitted across the ocean, and deciphered. Because of the difficulty of securely supplying the tape, the hotline has since changed form. The OTP has been used by many spy organizations because of its practicality even without a computer. Number pads were small and easily concealable, and often printed on flash paper or some other easily destroyed substance. With the key, the decryption is also relatively simple, so less human error would be likely to occur.
The One Time Pad Today
The One Time Pad is currently used in asymmetric network encryption. This is commonly referred to as a pseudo One Time Pad harkening back to it’s origins. In simple terms, each side of the communication has a known calculation or cipher it uses to generate the Pad of random information. To make sure it is unique, key pairs are used. In short, the identical Pads are generated on each end of the communication. This allows both sides to generate the Pad without having to transmit it across the network working in similar fashion to the German World War II Enigma machine. While this technique is sound and, implemented correctly, provides a high degree of confidence that data can not be decrypted, the fact remains that anything that is calculated can be easily solved for. The NSA leaks of 2013 taught us that data over the internet is being recorded and, even if a crack did not exist at the time of the recording, the recording could be cracked later when an exploit is found or advances in technology make a “brute force” crack possible. With the increase in processing cores, the reduction of power consumption and the mitigation of semiconductor heat generation combined with the large bit word size and vector computing used in GPU’s, the ability to brute force crack most asymmetric encryption rapidly approaching, if not already here.
This problem is twofold: 1) data transmission recording needs to be stopped and 2) a real, truly random One Time Pad needs to be used in network encryption. Using a real, symmetric OTP in a network has been something of a “holy grail” or “unicorn” problem until now. Introspective Networks (I am President/Founder) has discovered a method to deliver the pad from one side to the other, securely creating a Streaming One Time Pad (patent #8,995,652 aka STOP – Streaming Transmission One-time-pad Protocol). This technique combines a real, truly random One Time Pad with something akin to frequency hopping (a technique used to disguise radio transmissions) in the network. This allows the pad to be sent across the network securely and, by “port hopping,” the risk of recording is fundamentally removed. STOP represents a seminal technology that changes the rules for how data is secured in the network using a proven method of encryption—the One Time Pad.
As a truly indecipherable means of encryption, the One Time Pad is an extremely important invention. From its humble beginnings as a mere mention within the introduction of a telegram codebook, the OTP has grown to become a ubiquitous part of cryptography. When used correctly, it’s the perfect way to send secure messages, but if all its rules are not followed, it becomes susceptible to decryption. From Vernam to Mauborgne to Shannon, the OTP has been influenced by many people, each of whom added their own bit of expertise to the concept. The fact that a correctly executed OTP message still protects its secret decades later only speaks to the durability of the system. Its many applications, such as OTT and SIGSALY speak for its versatility. The path to the OTP was not without hurdles, of course, but from usage by espionage organizations to governments to international communication it has improved substantially, cementing its title as a truly unbreakable encryption method. However, the OTP’s history is not yet fully written, and the next chapter begins with Introspective Networks’ patented STOP technology.
A public beta version of our first product, IC Secure Messaging Service, using STOP technology was recently made available for Chrome and Android. For Apple, please email us at [email protected].
Sponsored byVerisign
Sponsored byIPv4.Global
Sponsored byDNIB.com
Sponsored byVerisign
Sponsored byCSC
Sponsored byRadix
Sponsored byWhoisXML API
A World-Renowned Source for Internet Developments. Serving Since 2002.
It still doesn’t solve the problem of the second transmission (secure channel), or does it? You still have to send the message and a second transmission for the pad which has to be of the same size as the original message.
This technique combines a real, truly random One Time Pad with something akin to frequency hopping (a technique used to disguise radio transmissions) in the network. This allows the pad to be sent across the network securely and, by “port hopping,” the risk of recording is fundamentally removed.
That is an assumption but not a statement based on facts. Here is what Rüdiger Weis, Professor for Mathematics and Informatics at Berlin University, Germany and member of Chaos Computer Club has to say about it: “We cryptologists always assumed we have to deal with a superior opponent, who has billions available and is in the possession of technology, which others do not possess.”
There are other ways that lead to the “Holy Grail” or discover a “unicorn” giving a perfect OTP without the need to send the pad, but that requires to read Shannon’s papers and actually understand what he said. The NSA since the mid 1970’s certainly pushed into a different direction when it came to encryption algorithms. Today we are left with the opinion of experts that more or less all regard the OTP as an outdated form of encryption not fit for our times. (Bruce Schneier: ‘What a one-time pad system does is take a difficult message security problem .... and turn it into a just-as-difficult key distribution problem. It’s a “solution” that doesn’t scale well, doesn’t lend itself to mass-market distribution, is singularly ill-suited to computer networks, and just plain doesn’t work. ... This is the only provably secure cryptosystem we know of. It’s also pretty much useless. Because the key has to be as long as the message,....’.)
Wandee - Swadee Kwapp! My family loves Thailand and visit every few years. It’s one of my favorite places…you are lucky to live there.
Back to the question at hand: There is always a cost to everything. The cost to our technique is bandwidth. The fact is today bandwidth is cheap and it’s only going to get cheaper. Working at Level 3 Communications for nearly 14 years, there is some insider insight into the state of global networking. The fact is bandwidth cost is about to drop through the floor as, with a technique called wave dispersion, they can get terabytes (that’s right) per second out of even the oldest, existing fiber in the ground.
Knowing this, a different tack was taken. If bandwidth is no longer a concern, how can we use that to our advantage? That’s what we’ve done. You will not need to be a billionaire to use it and in fact you can get our first product on the Apple, Google or Chrome app stores by typing in “IC Secure Messaging”.
The fact is there is no longer a need to calculate pads and we can use real world analog sources to provide mathematically provable, uncrackable encryption. It’s not clear why it would be done any other way. Calculating the entropy (randomness) at the endpoints will forever produce something that, as heat and power requirements keep being reduced for computer processing, is no better than the Enigma. There is a fairly simple rule: anything that is calculated can be solved for.
As for entities with unlimited resources, it seems a safe bet that the US, China, UK and RU likely can brute force AES 256. Here in the states, there are two sibling campuses dedicated to the interception and decryption of data. It’s about parallelism and register size (bit size). If you start creating registers that are 1024 bit or larger and create CPU’s with trillions of AU’s for vector processing that have checks built into the hardware and then say you have a building full of these that is a few city blocks in dimension and multiple stories high, things start to become possible that were not before. Bruce Schneier concedes this back as far as 2012 with a single line on his blog. With large registers, you can bit shift the operations to get, for AES256 (256 bits), 4 calculations (or more with a larger register) completed per pass. Add in vector computing (oldest form of parallelism and a commodity with that being the technology behind GPU’s) with a little specialized hardware for doing the brute
The US Government has made this even simpler by “standardizing” a single algorithm. This makes creating a brute force hardware solution straightforward and well understood. (Frankly I have always used Blowfish for this exact reason.) Also, by standardizing it, they have taken the market competition to innovate out of the equation (until now). We only developed our technique because injection attacks cause problems for IoT solutions and our main patent glues different “Things” together.
On a final note of clarification, a Pad should not be confused with a key. A Pad is random, not repeating stream of data bytes. A key is something both sides know to derive matching Pads on either side. Keys can be stolen, calculated or intercepted (if they are rotating). A Pad calculated from an analog source; say ambient temperature in some not controlled environment at a Pico level, can not be solved for and, when used to encrypt data, is truly uncrackable as long as that key can not be accounted for. In short, we have a patent for provable, uncrackable network encryption. Who doesn’t want that?
Wad-dee-ka Khun Anthony, and thank you for your kind words about Thailand. I haven’t been to the US yet, but my husband has been several times and he thinks it’s a great nation.
Coming back to your comment I don’t disagree with you, that in most (you say always) cases there is a cost to everything, but then again it doesn’t have to be that way. I agree with you too that the final chapter in the book about the OTP hasn’t been written yet, but doubt that the solution you suggest will be a lasting one (in some not controlled environment at a Pico level, can not be solved for and, when used to encrypt data, is truly uncrackable as long as that key can not be accounted for.).
My question is how long will it be that the key can not be accounted for? Getting onto websites and boards that discuss the OTP, I’m sometimes astonished how ignorant some of the commentators are; naturally operating under an alias and not providing a real name. When pointing out that the solution is the key exchange that has to come with each encrypted message and that eliminating this second transmission with only the need to transmit the cipher would make the OTP the perfect encryption tool again.
I will spare you the answers I got but feel free to have some wild guesses. Last week I setup a website to explain to the layman my ideas and in August I want to publish some papers on it. Here is the website: http://www.ftnsa.eu.pn (ftnsa stands for formatted text and not some algorithm – so don’t get the wrong idea).
Feel free to comment on it (you can skip the first part which explains how an OTP operates and jump to a different approach) and don’t hold back your criticism, as pointed out before discussions on blocks and websites have roughed me up. You can use the email address on that website so we don’t have to wash the dirty laundry in public.
Wandee - STOP is the first method that actually uses network to hide data. This is revolutionary and game changing. We take a perceived problem and turn it into a strength. The second transmission in STOP is actually a huge plus with the STOP technique. We can send that across physically different networks, rotate what stream is being sent across which and add additional streams to further obfuscate the data. You could also do this at a VLan level and, while you might be on the same physical network, it would require access to multiple virtual networks to put the streams back together. Moreover, since the One Time Pad technique, implemented correctly, is mathematically impossible to crack and a pad being sent across existing asymmetric encryption is also impossible to brute force crack because the content can not be guessed, the STOP protocol, implemented with network separation, becomes empirically very, very difficult if not impossible to crack. It certainly becomes much more difficult to record and make sense out of the data and next to impossible to record and decrypt (today they simply sit in the middle of an IP stream attached to a known port (virtual location) and record the data...the NSA here in the states is doing this right now with a facility a more than a few hectares in size under the CALEA laws...it’s believed the UK, China and likely Russia have these same capabilities...with quantum computing, it’s not long before the bad guys have it too). In short, the multiple extra transmissions actually become a new method of data obfuscation. This method has been used for radio scrambling successfully for ages using a technique called frequency hopping. Our method is even one better because the communication changes in the network are truly random and unpredictable (frequency hopping actually has a calculation for the hopping both sides are, and potentially a bad actor becomes, aware of). On a final and separate note, It’s key to understand that existing encryption is simply what’s referred to as a “Pseudo” One Time Pad as the pads simply calculated on both sides. Asymmetric encryption, in it’s current form, uses OTP concepts very directly. My theory on why this will never be secure is simple: Anything that is calculated can eventually be solved for. I read through some of your web site but was a bit confused on how the offset pad is to be transmitted and/or calculated on both sides. Is there a simple explanation of how that is handled? Also, the examples seem to be exclusively text. How is binary data handled? It seems this can be done at binary or bit level but, if it is, isn’t it simply a One Time Pad? In short, isn’t it a pad using the inverse properties of addition and subtraction? I likely need some help understanding this.
Anthony – Since our last exchange here I have returned several times to read your article and the comments you made. The reason for it was that I have been intrigued and puzzled with the system you developed. Certainly if the technology and the concept behind it are solid (your patent seems to confirm it) it is one way of escaping the dragnet that has been cast over the internet. And yes, I will give you credit for it, it seems revolutionary and for the moment the second transmission might be turned into a plus compared to the original OTP were it becomes a liability and a security risk if intercepted.
The question that is still nagging in my head is for how long will it be a plus? My first experience with computers goes back to a time when punch cards and paper stripes with holes had been used to develop computer programs. The first home computer I owed was an IBM PET, green screen, no memory storage device, and 1k of memory; switching it off was loosing your program to be re-entered when powering it up again. I mention it here because it seems to have happened a long time ago but comparing it to a human lifespan it wasn’t really that long and development in computer science and mathematical algorithm that are concerned with crypto systems have gathered pace. Even working in the field one will have problems to keep up with all the new developments that take place.
You write that your system obfuscates the data you transmit and that worries me a bit. Obfuscating data doesn’t mean the data isn’t there, only they are taken out of plain view of a possible attacker. Here I have to come back to a comment I made in my first reply to your article were Rüdiger Weis, Professor at Berlin University is quoted: “We cryptologists always assumed we have to deal with a superior opponent, who has billions available and is in the possession of technology, which others do not possess.”
How long will it take an opponent like the NSA to develop the technology to detect the obfuscated data? Or do they already have developed systems that can do it? Neither you nor I have a valid answer to that question and we can only rely on what we believe; and belief is a concept that is reserved for religion but should be kept out of science. Certainly if you have solid scientific evidence and mathematical proof that the data can’t be retrieved it puts your case into a different light, but that should be verified by peers working in that field and the proof should be out in the open.
Let me come to your final and separate note and address the “Pseudo” One Time Pad. I agree with you that ‘anything that is calculated can eventually be solved for’ and hence your theory isn’t a theory but a plain fact and obvious. I put it somewhat different and always explain that mathematics is great when it comes to solve puzzles but difficult to create them. The reason is simple: If you create a puzzle using mathematics you will also have to develop the math that will solve the puzzle and it will only be a matter of time if someone else too will develop the same math to solve the puzzle you created.
Thanks for reading partly through my web site and yes it seems at the first attempt a bit confusing. But that site was setup as a bait to get the discussion going and it doesn’t contain a lot of mathematics because the math is based on Shannon’s calculation and mathematical proof. We were not going on improving on it since it can’t be done and I assumed that people with a background in the subject would come to the same conclusion.
Communication Theory of Secrecy Systems . It provided the proof that any unbreakable system essentially has to have the same characteristics as an OTP which are:
1. The key must be truly random
2. The key must be as large as the plaintext
3. The key can never be reused in whole or part
4. The key must be kept secret
M: {0, 1} ? M is the message
K: {0, 1} ? K is the key ? is the message/key length
c = (k, m) = m ? k, for m ? M, k ? K, where“?”stands for a bit-wise xor
m = (k, c) = c ? k, for m ? M, k ? K.
Decryption proof (c ? k) = ((m ? k) ? k) = m ? (k ? k) = m
C = M ? K
Example:
m = [HELLO]
k = [XMCKL]
c = [EQNVZ]
If we go back to the cold war in the late 40’s and 50’s of the last century is was common to provide agents with an OTP that contained pages and pages of code. Receiving a cipher they would decrypt it and rip out the page they used to do it, using the next page for the next cipher.
In our case the pages of the OTP haven’t been written yet and you might regard it as a set of instructions for sender and recipient to encrypt and decrypt a message. Since both using the same set of instructions (manual – two randomised strings) they will have no problems to communicate. An attacker on the other hand will have to go through all possible randomisations and hitting the same brick wall when trying to decipher an original OTP. It is important to keep in mind that the initial exchange of the randomised strings stays between sender and recipient, after that they can write messages without having to worry about a second transmission for a key that now has become obsolete. It was pointed out to us that this might be the weak point in our system, but then again the same people had no objections in an initial public key exchange using PGP and still regard the system as safe.
The question is what system would you prefer with quantum computers on the horizon? A system using a mathematical algorithm for encryption/decryption that under a brute force attack will supply only one valid solution or a system that is based on random (not pseudo random) events offering a multitude of possible solutions?
If you drop me a line using the email address on my web site I will supply you with the paper I’m going to publish and the relevant mathematics are included. Here it would exceed the 10000 characters permissible here.
In short, it isn’t a pad using the inverse properties of addition and subtraction, but relying completely on random factors that are not covered by mathematics. I thought that our example using a five letter alphabet would have made it clear, but as I see now it might require more clarification.
Anthony – I have just completed a discussion with some of the people that helped to develop our system and the software. I had asked them to take a look at your suggestions and the system you have developed. They all agree that if what you claim is true it would be a perfect system to transmit data between parties that want to exchange sensitive data. With bandwidth prices falling through the bottom the costs wouldn’t be a problem and the amount of data that needs to be created (cipher and key of the same length) shouldn’t be a point of worry either.
However at the end of our discussion I raised the question why we would need an OTP if we have a system that according to you (quote): “In short, the multiple extra transmissions actually become a new method of data obfuscation. This method has been used for radio scrambling successfully for ages using a technique called frequency hopping. Our method is even one better because the communication changes in the network are truly random and unpredictable (frequency hopping actually has a calculation for the hopping both sides are, and potentially a bad actor becomes, aware of).”
My question is now: Could you not send the message without having to create a cipher and a key? If the changes in the network are truly random and unpredictable an attacker would have no chance of intercepting them. It would make encryption as we know it obsolete and remove the time it would take to create cipher and key. It would also mean we wouldn’t have to care about bandwidth. Is there something I haven’t understood when reading your comments? If I have, please let me know.
On the other hand we are well aware that sending a cipher, using our system, will be detected and recorded somewhere; the amount of adversaries monitoring the internet in our days makes that inevitable. The only way of keeping the content of the cipher a secret is by making the key inaccessible for an attacker. We achieve this by not sending the key at all but using true random events (not pseudo random events) at both ends (sender/receiver) to create the key.
I am just finishing a more detailed information sheet (PDF format) that I will place for download on our website. It will contain more details as the webpage itself and also contain the mathematics behind it.
Anthony - I have just attached the PDF file to our website. You will find the link towards the end of the webpage - The OTP - A different approach - and it will explain in detail why we only need to send a cipher without having to worry about a secure key exchange. It relies on the statement made by Auguste Kerkhoffs about 200 years ago that everything about a system can be known and only the key has to remain out of public view.