Schneier on Security
A blog covering security and security technology.
« The Exaggerated Fears of Cyber-War |
| Real-World Access Control »
September 3, 2009
The History of One-Time Pads and the Origins of SIGABA
Blog post from Steve Bellovin:
It is vital that the keystream values (a) be truly random and (b) never be reused. The Soviets got that wrong in the 1940s; as a result, the U.S. Army's Signal Intelligence Service was able to read their spies' traffic in the Venona program. The randomness requirement means that the values cannot be generated by any algorithm; they really have to be random, and created by a physical process, not a mathematical one.
A consequence of these requirements is that the key stream must be as long as the data to be encrypted. If you want to encrypt a 1 megabyte file, you need 1 megabyte of key stream that you somehow have to share securely with the recipient. The recipient, in turn, has to store this data securely. Furthermore, both the sender and the recipient must ensure that they never, ever reuse the key stream. The net result is that, as I've often commented, "one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong." They're useful for things like communicating with high-value spies. The Moscow-Washington hotline used them, too. For ordinary computer usage, they're not particularly practical.
I wrote about one-time pads, and their practical insecurity, in 2002:
What a one-time pad system does is take a difficult message security problem -- that's why you need encryption in the first place -- 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.
One-time pads may be theoretically secure, but they are not secure in a practical sense. They replace a cryptographic problem that we know a lot about solving -- how to design secure algorithms -- with an implementation problem we have very little hope of solving.
Posted on September 3, 2009 at 5:36 AM
• 59 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
I think that there is a bias against OTP among cryptographers because OTP takes a problem that you need a cryptographer to solve -- message security -- and turns it into a problem that you don't need a cryptographer to solve -- key distribution. Cryptographers do not like approaches to problems that make them irrelevant.
For some situations, the key distribution is not a problem, such as in the military, if you want two bases, or a ship and a base, to communicate securely. It can also work for two persons who know each other and are sometimes in the same place at the same time, and other times are apart.
What about Michael Rabin's hyperencryption concept? Isn't this a kind of OTP with a clever solution to the key distribution problem?
@Ott: The cases you list are very, very unusual. For example, what ship only has the need to communicate with only one base? Most ships have to communicate with many more units in order to be of any use.
So, no - there is no conspiracy among cryptographers. It is just that the vast majority of cases involve a whole heap of people who need to talk to each other securely. And for that, OTP sucks.
@ThM: The hyper encryption concept has an easier key distribution problem than the OTP, but remember that the reason Public Key Cryptography was invented was that it was just too much hassle to exchange all those secret keys being used in symmetric ciphers!
So HE has the security of OTP (good), but the same key distribution problem as symmetric cihpers (bad).
Quantum key distribution can be used to create OTPs. Still inconvenient and cubersome and with serious limitations.
"I think that there is a bias against OTP among cryptographers because OTP takes a problem that you need a cryptographer to solve -- message security -- and turns it into a problem that you don't need a cryptographer to solve -- key distribution. Cryptographers do not like approaches to problems that make them irrelevant."
Actually, we would like it very much if people would just use a tested and trusted secure symmetric cryptosystem and be done with it. Then we can work on the actually hard problems, key distribution among them.
When I was in the Army, in the Signals arena (MOS 31k, a "wiredog") we used one time pads. Distributed in booklets, monthly, to be used only for short tactical messages. Never actually used it, as we had secure commo gear.
I have to disagree with OTPbeing less secure. Key distribution is not such a big issue for OTP becuase they are not supposed to be common. OTP is best used for special high security messages of limited length between two parties. I would suggest it is not a problem of good or bad systems but understanding which system is appropriate for your particular use.
As somebody who HAS dealt with private keys, I can say that private key distribution is, to some extant a "solved problemm" but one with significant operational issues.
Keying material for the entire operating period must be distributed beforehand. Particularly, with a one time pad, if you have a secure way of sending new keys, you could just use that to send the message. You need to be able to secure unused keys in a manner that prevents any surruptious access. And you need to be able to securely and confirmably destroy used keys.
Broadcasting isn't a problem per se, you just distribute the key to everybody. But of course you have multiplied the points of failure because the compromise of/by any of the recepients compromises ALL of the messages.
@djdii: Nobody's denying that OTPs are the correct choice in some circumstances; the argument is just that OTPs have a large problem in key distribution that prevents it from being useful in every situation where secure encryption is desired.
Seems to me that what a OTP is good at doing is batching secure communications. Suppose you send me a DVD-ROM of random numbers. This is a slow process. If you send it by courier it could take days. Once I have it, we can communicate at normal speeds, and if we do it right we have guaranteed permanent secrecy.
Obviously a OTP is not a general-purpose communications system. It requires more attention to physical security, and it's slow and expensive to set up. It is an attractive option for ultra-high-security communications between two or more highly secure locations.
As far as I'm concerned, OTP seems to be incredibly irrelevant today. Even for high security applications, it wouldn't seem to offer any advantages over a good symmetric cipher. Yes, OTP unbreakable in theory, while a symmetric cipher is not, but in practice, encryption systems aren't broken by attacking the algorithm.
Arguing that OTP works when you've solved the key distribution problem doesn't change things. If you've solved that, then even if you use a symmetric cipher, you've eliminated many of your issues. And as history has shown, a lot of potential issues remain...whether you use OTP or AES. The encryption algorithm you use only plays a small part in the overall security of your system, and I think the history of broken crypto suggests the algorithm doesn't even play a major part.
Cryptography as a mathematical discipline is light-years ahead of cryptography as an engineering discipline. The algorithms we have now are so good, and the systems they are used in are often so bad, that replacing the algorithm with a theoretically perfect encryption method like OTP wouldn't improve your overall security by very much. Venona proves that pretty well, I think.
Granted, OTP presents unusually difficult key security problems. But the cipher can be used to encrypt and decrypt messages in the field, quickly, and by hand, even by people who can't do complicated arithmetic in their heads.
Is there *any* other strong cipher that offers this level of cryptographic security that can be worked by hand?
I think pads are great for those one-time-only crucial messages that on rare occasions are actually useful.
So if "the eagle flies at dawn" means "invasion at normandy" and the "horse flies like dung" means "invasion at calais", you've got yourself a pretty useful communication approach, as the messages are high value, low bandwidth, and will never be repeated.
So categorically banishing one time pads as useless is a mistake. But it's clear and I suppose obvious that highly appropriate uses are not all that common.
"The randomness requirement means that the values cannot be generated by any algorithm; they really have to be random, and created by a physical process, not a mathematical one."
Physical process that cannot be modelled mathematically?
How strong is this requirement really?
x = sin(2*pi*n) for n = 0..N, is a valid event/outcome for some random process X, unlikely but valid.
What about self-modifying code?
And finally, formulae that touch on Gödel's incompleteness theorems.
I have even more tricks up my sleeve but would first like to hear how you guys respond.
Maybe one-time pads will come back about the same time that working memory implants for human brains are developed. Then you could just chip everyone with a few terabytes of random data sometime in early adulthood and only activate the OTP implants of those who needed secure communication.
(Yeah, I know this is an unlikely scenario. But I'm trying to highlight another set of problems with OTP. In addition to secure key distribution, you need secure, reliable long term key storage at both ends of the connection. Otherwise the sleeper agent gets the crucial message containing the plans to Dr Evil's laboratory -- in pdf, of course -- and after 12 years in the field can't find the USB 0.5 thumb drive with the OTP on it, or can't find an adaptor to plug it into a current machine...)
"Is there *any* other strong cipher that offers this level of cryptographic security that can be worked by hand?"
Yes. Dead people don't talk, cryptographically speaking. :P
One problem with OTP is that it can not be 100% random, it needs to be filtered to fit the constraints of the plain text used alphabet size.
In a 100% random system an endless run of zeros or ones or some repeating patern is "par for the course" (ie run length is unbounded).
Even though this issue has a very low probability this is obviously unacceptable for an OTP as the resulting cipher text will start showing the statistics of the plain text. Effectivly it becomes the same as using the same tape twice etc (and as VENONA showed some people will look for any opening they can get).
There are two obviously methods to fix this the first being fix the statistics of the plain text (usualy weak) the other is "filter the noise" of the random input in pad generation (usualy strong). In practice it is wise to do both.
All though the OTP has many issues that make it impractical for ordinary use, it still has an important use in key distrubution in an emergancy.
That is if for some reason a working key is lost or destroyed and cannot be supplied by the normal channels an emergancy OTP alows the exchange of a (new) key with just a pencil and paper.
However it does require an additional protocol to prevent certain types of attack that effect all stream ciphers, including hostile/duress use of the OTP.
However apart from exceptional use the OTP is generaly a curiosity that is of more use in authentication than in confidentiality and as noted if not used with other protocols suffers from all the problems any other stream cipher suffers from (apart from key prediction ;)
In most cases I would much rather stick with a modifed form of CTR as this at least limits the run length problem to at most 3B - 2 bits (where B is the number of bits in the cipher block).
Oh and do be carefull if you do try and use two or more CTR's combined as the run length problem can effectivly become unbounded again if you don't take care.
@paul: Either everyone has different sets of random data, in which case OTP crypto won't be possible, or everybody has the same set of random data, in which case you have the far more difficult problem of controlling access to the random data in every person who has it implanted. How can you trust a OTP cryptosystem where _everybody_ has a copy of the keying materials?
Now that USB thumb drives are so cheap and have such large capacities, I'd think that they'd be an ideal vehicle for distributing an OTP.
Perhaps combined with some steganography so the OTP is hidden inside a bunch of pictures, audio podcasts or video files on the USB flash device?
You'd probably only want to hide a small number of megabytes of OTP on an 8GB USB stick. But that should be enough to let your secret agent send/receive text e-mails for many months without running out of bits.
Everyone has a different set. I'm positing some miraculous central authority that securely stores all the sets (and hands segments of them off as needed). Unimplementable, you say? My bad.
"I have even more tricks up my sleeve but would first like to hear how you guys respond.
The simple answer with a determanistic system is, "it is a question of state".
All determanistic systems that generate sequences require state information to be kept in order to calculate the next output.
Obviously the state is stored in some kind of finite memory device.
This has two conciquences, the first is that the state is obviously bounded at N bits (the size of memory used). This means that the maximum number of states is 2^N after which the sequence repeats.
The second less obvious problem is permutation of these states is effectivly governed either by fixed logic or fixed logic with further state information. It can be shown for non trivial sizes of memory that the number of possible permutations excedes the size of the state memory therefore only a subset of those states is possible.
This gives rise to the issue of predictability of the sequence in use by the logic.
It has been shown for many PRBS generators that if you have the output upto 2 times the number of state bits (ie 2N output bits), then the entire sequence of the generator becomes known to an attacker (this is a consiquense of amongst other things using mod2 addition in the feedback logic).
Therfore it can be seen that in general all determanistic generators become "known" at some point.
However two points arise from this, the first being how difficult it is to determin the sequence of the PRBS, the second is what if you change the sequence using a true physical random generator (TRNG) before the point at which the PRBS becomes known.
A case in point is the RC4 cipher it's output function is to add together two 8bit numbers and use the result to look up another number that is then output.
What if you had a TRNG that added a third number before the lookup of the output number?
Provided the TRNG changed it's output frequently enough then determining the output from the modified RC4 would be at some point moved from just possible to impossible.
Such systems are used to effectivly spread the entropy of the TRNG across the output of the PRBS producing many more effectivly random bits than the TRNG is capable of, and importantly in a dependable way.
I forgot to add a rider on,
'Therfore it can be seen that in general all determanistic generators become "known" at some point.'
In my above post of,
There are some generators such as the Blum Blum Shub ( http://en.wikipedia.org/wiki/Blum_Blum_Shub ) that are "theoreticaly secure" based on the presumption that certain functions can be truely "one way"
@paul: Would you use a cryptosystem that relied on a central authority to hand out copies of the keying material?
OTP reminds me on an SNL sketch, "Johnny Canal", in which John Malkovich played a canal advocate trying to get a network of transportation canals built.
"It's simple. If you need to get from New York to Boston, you get on the New York-to-Boston canal. If you need to get from Boston to New York, you get on the Boston-to-New York canal."
One thing occurred to me that is relevant here. I realise that because you can't generate OTPs or cryptographically secure random numbers algorithmically, this must be flawed, but I'm not entirely sure why. It's my own personal invocation of Schneier's Law.
The digits of Pi, as far as we can tell by all existing statistical tests, are random. There is no pattern or long-range repetition to be found.
Therefore, if you pick a sufficiently large secret number X, then for a given message of length N, you could "create" an OTP of length N using the Xth to (X+N)th digits of Pi.
Also, because of the Bailey–Borwein–Plouffe formula, it is possible to calculate the Xth to (X+N)th bit (binary digit) of Pi without needing to first calculate the 0th to Xth bits.
Therefore, as an encryption algorithm, why not:
1) Generate/exchange a shared secret (the key) - e.g. "password"
2) Hash the key somehow - e.g. using crc32 on "password" we get 0x35c246d5.
3) Use the hash as a numeric index into the digits of Pi - e.g. 0x35c246d5 is 901,924,565, so your OTP starts with the 901,924,565th "bit" of Pi.
4) Keep generating bits of Pi for as long as you have bits in your message, and XOR them together.
I totally believe it won't work. But I'm not sure why, or where the weakness is. Is Pi not actually "random enough"? Is it something else?
During WWII the USA just hired a bunch of Navajo and solved the problem that way. Sounds like a great excuse to fund a ton on linguists and document all of the "dying" languages out there to me.
I don't know for a fact, but I would bet that OTP are used for guided weapons. A OTP can be downloaded into a missile, which is then fired, both parties can communicate securely until the missile arrives and explodes. Also I would imagine a similar system is used for fighter planes and aircraft carriers.
Correct me if I'm wrong, but the primary (only?) advantages of OTP are that; the key distribution problem can be handled any time before the message needs to be sent, it has very weak latency/time requirements and failures are not fatal if they can be detected before the key gets used. This implies that good OTP can be set up to only depend on good *Physical* security
The only difference between a key for a strong symmetric cypher and a one-time pad is size. The only reason OTP distribution is any more difficult than key distribute is that it's slightly inconvenient to distribute a 1 PB OTP, vs a 256-bit key. This becomes less of a difference over time.
Distributing a 1GB OTP instead of a small key would work fine in manu contexts today. Easy distribution of a 1 TB OTP is easily imaginable in my lifetime. Eventually, this becomes a non-issue. Of course, generating 1 PB of genuinely random data is a bit of an issue, but on the whole the OTP aproach gets better over time, which any specific symmetric encryption algorithm only gets weaker over time.
Bruce may be right for the rest of our lifetimes, but eventually everything will be OTPs, since we know "you can't hide secrets from the future with math."
@Skorj: Except there is a difference. When we distribute a 256 bit symmetric key, we do so by wrapping it in even harder asymmetric encryption. So, in order for an adversary to get our key, they'd have to break something even harder (the public key encryption). If we were to distribute the OTP, we'd have to wrap it in something even harder to crack - and there isn't anything.
Sure, you can distribute an OTP using Public-key crypto, but since it is weaker than OTP, why bother? Just send the message using PKC and be done with it.
Just a guess here: What you have done is essentially "compressed" an OTP. Instead of sending the key, you send the offset into Pi. But you still have to send this offset.
But you still have the same problems as with an OTP:
1. Not reusing the same key. (Reusing OTP)
2. Distributing multiple keys (for multiple messages) securely.
...and so on.
"Also, because of the Bailey–Borwein–Plouffe formula, it is possible to calculate the Xth to (X+N)th bit (binary digit) of Pi without needing to first calculate the 0th to Xth bits."
Your mention of the Bailey Borwein Plouffe (BBP) formula tickled my old grey cells and I remembered an improved version was used in the Pi Hex project (which was a bit like the SETI@home project).
I googled it up and posibly found the problem you where looking for...
The Pi Hex project took something like 2 years and 1.2 million P90 CPU hours spread across a couple of thousand PC's to find three bits one of which was at bit position 10^15 + 60.
So it is not exactly quick, I guess you could say it has done a memory/time trade....
You also need to consider that 10^15 (app 2^50) bits is not exactly a long way into Pi when compared to the length of sequence you could have generated with AES128 in CTR mode.
Also I confirmed my other grey cell nagging that the BBP has an issue.
BBP has problems with long runs of 1's in that you get uncertainty due to precision and rounding in the size of the computer "word" used.
However the BBP has been used to find other values as well as Pi so it has some utility.
In any truly random sequence of digits, there will be occasional runs of zeros. I think the formula for knowing what the chances are to have a sequence of consecutive zeros is
1 - ((1 - (0.1 ^ k)) ^ (n - k + 1))
where k is the number of consecutive digits, n is the length of the entire sequence, and ^ is the exponentiation operator. If that is the case, 100 truly random consecutive digits have a 63% chance of having two consecutive zeros, a 9.3% chance of having three consecutive zeros, and a 0.00000089% chance (about 1 in 110 million) of having ten consecutive zeros. If that happens in the wrong place, then simply XORing will definitely not help. Modifying your algorithm to avoid runs of digits in the key might open it up to other attacks. Any cryptographers should be able to tell you why. I certainly don't know.
Embassies communicating with their governments seems like a good fit for the use of OTPs. You have high security physical channels to distribute the OTP, and you know in advance that there is only one party to communicate with. Distribution can be in some compact digital medium (eg USB stick) stored in a tamper-proof container. Protocol is to securely erase the pad immediately after sending a message, even if you haven't used all the bits. The need for confirmable secure erasure probably dictates your choice of medium. (Paper tape would be great except the bit density is too low.)
I don't believe runs of zeroes/ones would be a practical problem.
Firstly, you *will* compress the message first. Those key-bits are expensive, so you shouldn't waste them. (Humans can and have used codebooks for this.)
A good compression algorithm will remove most all of the context an attacker would need to distinguish a plaintext fragment from a ciphertext fragment.
Secondly, there is some nonzero probability that data will encrypt to something that *looks* like plaintext. Provided this probability is equal to the probability of a zero/one run, an attacker can't know whether the 'plaintext' is just their own fantasy...
tcliu - yes, but because proper OTPs are random, they are normally uncompressable. So, being able to compress an OTP means that you "just" have a key-exchange problem. And, as Bruce pointed out, we already have some key-exchange algorithms, and if all we need to do is work on them instead of the encryption as well, then that makes things easier.
@Karellen: Yes, but those key-exchange algorithms are used for exchanging a "weaker" key by wrapping it in a "stronger" crypto.
What you want to do is exchange an incredibly strong key by wrapping it in a weaker crypto.
For example, would you exchange an AES key by encrypting it with ROT13?
@tcilu - I thought we exchanged symmetric keys inside public-key crypto because doing symmetric encryption is easier (e.g. less CPU-intensive) than public-key encryption.
Similarly, exchanging a 256-bit index into the digits of Pi is easier than exchanging as many bits of OTP as there are bits of message.
Yes, as you note, when exchanging symmetric keys you should use public-key crypto that is at least as strong as the symmetric cipher you are using (dependent on how you compare the relative strenghts of symmetric and public-key crypto, obviously), so therefore when exchanging a key into an infinite OTP you should again use a form of key-exchange that is at least as strong as the *key* you are exchanging.
(Note - although real OTPs are effectively unbreakable, if you have an infinite but known OTP which you index with a key, then the attacker still only needs to "search a keyspace" as big as the key you use to index it. Also, while it is possible that many keys will return a legible message, the number that do will decrease with the length of the message. It should be possible to calculate how many legible messages are likely given a particular key size and message length. If that number is small enough (less than 1?) then if an attacker does search the keyspace and find a legible message, then they can be confident that they have found *the* message, something that *is* impossible with a true, completely unknown OTP.)
Ah yes. I see my mistake.
I had misunderstood BBP and thought that because it did not need to calculate digits of Pi preceding the one you were interested in, then it could calculate each bit of Pi in constant (O(1)) time. Looking more closely, this appears not to be the case.
Which is why the system is not computationally feasible.
"For example, would you exchange an AES key by encrypting it with ROT13?"
Well if the AES key was truely randomly generated, how would you tell how it had been encrypted?
You could look at it as an OTP in reverse where you use a known plaintext to recover the random key.
Providing your oponents do not know (nor can work out) what the plain text is then...
In addition to the runs of constants. In a large enough set of random characters you are going to have sections that repeat previous sections which is equivalent to reusing the same OTP.
RE: "Well if the AES key was truely randomly generated, how would you tell how it had been encrypted"
Security through obscurity, really, Clive?
Apart from the time constraint. Once you have function for creating your next random bit then you are no longer using a OTP, you are using a stream cipher. Your security, in that case, is supposed to reside solely in the key, not in the secrecy of your algorithm. The key, in the BBP idea is a relatively small integer. All I need to do is start cranking out digits of pi until I find the right ones (and keep all of them to decrypt future messages)
It's worth going out to the original article and following the links down to a copy of Vernam's original paper on the subject. In fact, only about one third of the paper is actually about one-time pads (a phrase which apparently does NOT appear in the paper), while the rest of it is an interesting overview of the state of both crypto and codebreaking at the time.
He also recognizes the potential drawbacks of very long one-time pads, and devises some nice alternatives to allow trade-offs between security and practicality.
It's historical, and thus not up to date, but still quite interesting.
As a final note, I always think it's worth knowing what has come before. At some point, you might need to make a design trade-off -- such as working with massively limited computational capabilities -- and need to design within them. At that point, your knowledge of the point in history when "massively limited" was the norm will come in handy.
"Security through obscurity, really, Clive?"
No, I was just making the point that in effect encrypting a truly random string (the AES key) with a weak key produces an output that is the same as a plain text encrypted with an OTP.
That is that even after ROT13 a truly random string is still just that a truly random string. And that just looking at the output is not going to give you a clue as to the system in use.
And thus as long as the method is only ever used once the security would be the same as an OTP.
However if your AES key is not truly random or you use the method more than once, then as you say...
"So, being able to compress an OTP means that you "just" have a key-exchange problem."
@Karellen: The *only* problem with OTPs is the key exchange problem. If we had solved that one, we'd all use OTPs. But we don't. That's how hard it is.
"we already have some key-exchange algorithms"
But none of them are as strong as OTP. A cryptosystem is only as strong as its weakest link. If the key exchange protocol is weaker than OTP, then, well, what's the point - the whole system isn't as strong as OTP. If the key exchange protocol is as strong as OTP, then, well, what's the point - just exchange the message and be done with it.
There are situations where a OTP is perfect. The classic use is Navies, who have the power to securely transfer the OTP from the secure communications center to the secure locker aboard the ship. Once done, all transmissions can be reasonably expected to be secure.
You could do the same with anything that physically moves form a home base, assuming you can afford the key storage (since it's size is rather large).
I certainly hope they're using OTP to remote-operate those hellfire-equipped predator drones, for instance. Combat aircraft could also use them. (Take the OTP from the comm center to the plane just before takeoff)
Of course, most of the time, communications isn't like this. Most communication is between two widely separated points that don't directly meet and data transfer is voluminous, far beyond the practicality of OTP.
Cryptographers don't like OTP both because of its limitations and also its inherent unbreakability. Let's face it, nearly every cryptographer gets a particular thrill out of the possibility, or at least, the conceivability of breaking a code.
There is nothing wrong with that, especially since OTP is essentially "complete". There is no more research to be done. No next level to take it. We know it's limitations and it is extremely unlikely for anyone to ever overcome them.
> There are situations where a OTP is perfect.
Indeed, but there are very, very few. Even some that might seem to fit the bill at first glance actually do not. For example:
> The classic use is Navies, who have the power to securely transfer the OTP from the secure communications center to the secure locker aboard the ship. Once done, all transmissions can be reasonably expected to be secure.
Alas, no. OTP is not very useful to navies. The reason is key management in a multi-node network. Any given warship may need to send a secure signal to any other warship at least within its own fleet, and possibly to any other warship in the navy. If we use OTP to protect those links, then we have two choices:
a) Have only one, or a small number, of OTP channels shared between multiple users and require every vessel to keep tabs on which pages of the pad have been used. And of course, the moment that a vessel re-uses a page (for example, because it was out of communication range at the time that page was used) security fails completely. OR
b) establish a dedicated OTP set for each potential channel. This requires n(n-1)/2 sets of pads where n is the number of endpoints. For example, if you have just 50 vessels in your fleet, you need to distribute, manage, securely destroy and periodically replace 1,225 sets of pads. You need to somehow keep all of those in synch, regardless of the varying cruise durations of all those ships. Any time one of your vessels is lost -- even the tiniest little corvette -- you need to *immediately* redistribute the entire set, worldwide. This is a nightmare scenario which, as is typical for OTP systems, solves a relatively easy problem (strong ciphers) by greatly complicating the difficult one (key management.)
Given that all known failures in USN cryptology in recent times have been due to suborning of personnel involved in key distribution, I really don't think navies would be very interested in a solution that gives a hundred times more opportunities to the Walker families of the world.
Another issue is that the actual fleet broadcast system (apparently) continuously transmits nulls when there are no messages to send, so as to prevent traffic analysis. This means an immense volume of pages for each pad would be required for a long voyage.
> You could do the same with anything that physically moves form a home base, assuming you can afford the key storage (since it's size is rather large).
Only if it requires communication solely with that home base. Once you want to network with other friendly units, the complications rapidly multiply.
> I certainly hope they're using OTP to remote-operate those hellfire-equipped predator drones, for instance.
I doubt it. For one thing, the volume of data being transmitted from the drone is immense (many hours of real time high resolution video from multiple imagers), and in any case most of it is only tactically sensitive (i.e. we don't really care if the enemy cracks the cipher next week, just so long as they can't do it right now.)
In terms of the link in the other direction (command link), the most critical feature you require is not confidentiality but authentication. That is, you couldn't care less if the enemy finds out that you just sent the command "fire missiles" -- they'll know within a few seconds anyway -- but you really, really do not want them to be able to send a fake "fire missiles" command themselves. And whereas OTP provides perfect confidentiality when used correctly, it provides very weak authentication, making it an extremely poor choice for this application.
Another important aspect in this scenario is jamming resistance. There are many aspects to jamming resistance but from the point of view of choosing a cipher, you want low error propagation and self-resynchronisation. OTP does have low error propagation but it has no resynchronisation features whatsoever, making it, once again, a poor choice anywhere that may encounter electronic warfare.
> Combat aircraft could also use them. (Take the OTP from the comm center to the plane just before takeoff)
No, once again we have the multi-node network problem, but now you have it in spades. That aircraft requires secure communications to not only every other aircraft in the theatre, but also to all friendly ground units (possibly from multiple nations.) You still get that n(n-1)/2 problem but now, in a full scale conventional war n is many hundreds and may be as much as thousands. You need to update the lot every time a special forces FAC stops responding from his hidey hole behind enemy lines, even if it's probably just a flat battery. When you do the update, you somehow need to get to all those units, and all those FAC hidey holes behind enemy lines.
> Cryptographers don't like OTP both because of its limitations and also its inherent unbreakability. Let's face it, nearly every cryptographer gets a particular thrill out of the possibility, or at least, the conceivability of breaking a code. [...]
Certainly cryptographers find OTP trivial and *boring*. But that is by no means the only reason they dislike it so much. The main reasons, in my experience, are that OTP is so simple that:
a) the basic idea can be, and repeatedly is, re-invented by people who have simply skimmed through an introductory book -- people with such a limited knowledge of the field that they tend to seriously believe they are introducing something new and insightful, and develop unattractive and annoying persecution complexes when their idea is rejected; and
b) the basic idea can be grasped by people who -- not to put too fine a point on it -- do not have the mental equipment to grasp its weaknesses.
Putting these two features together means that trying to explain the finer points of OTPs rapidly becomes a pointless waste of life force.
>OTP is not very useful to navies. The reason is key management in a multi-node network. Any given warship may need to send a secure signal to any other warship at least within its own fleet, and possibly to any other warship in the navy.
You're making sweeping assumptions that make no sense at all.
Why do you assume that intra-ship communications is a requirement? Much like a police department or airline, you only need to be able to talk to a central dispatch.
Why do you assume that high volumes of data are required for communications? VLF/ELF transmissions with tiny amounts of bandwidth are still used to communicate with submarines. "Launch missile 2 to target C", or "Under attack, map grid gx452" don't require alot of data to express.
Why do you assume that key management is impossible? You have a finite number of ships, which will be at sea for a finite number of days. Someone creates the keys and delivers code books/code disks to the commander when you deliver the ship's mission orders. I'm sure this is done today.
At some point, you need to trust someone. If your communications/encryption guys and the guy commanding a boat with a few dozen nuclear warheads is betraying you, you have other problems.
It's easy to get spoiled by high tech and high-bandwidth. Once somebody like Iran or North Korea figures out how to shoot down a satellite, un-sexy technologies like shortwave radio are going to look pretty good. (And unmanned drones over Afghanistan controlled from Vegas are going to look rather dumb.)
Why do you assume that intra-ship communications is a requirement? Much like a police department or airline, you only need to be able to talk to a central dispatch.
This comms scheme would break down as soon as it went into action; both aircraft and policemen frequently want to communicate peer-to-peer, and ships operate in groups. The Royal Navy tried to micromanage the whole bang shoot from the radio antennas on top of the Admiralty building in 1914 and it didn't work at all well.
Further, the problem with sending OTPs to sea in ships is: what happens when the key is compromised, because it will be compromised? You've got to bring all the ships back to ports considered secure enough, and then bring the OTPs securely to them. And the enemy will be delighted if your navy vanishes from the seas every time there is a security panic. (Also, NATO and allied ships operate together, so you need perfectly secure INTERNATIONAL OTP distribution and revocation...)
Similarly, OTPs for drones have a serious problem; one end of the communications link may be at Nellis AFB, but the drones take off from dangerous forward locations where they are apparently serviced by Blackwater personnel. So, you've got to either set the OTPs before they are shipped, and then deal with the problem of resetting them in the field, bring them back to reset them, accepting the denial-of-service, or else trust a bunch of mercenaries who aren't officially in northwestern Pakistan with the OTP.
Once somebody like Iran or North Korea figures out how to shoot down a satellite, un-sexy technologies like shortwave radio are going to look pretty good. (And unmanned drones over Afghanistan controlled from Vegas are going to look rather dumb.)
In which case, the crypto must go into the field. And once forward air controllers are walking about on Afghan mountains or in Iraqi bazaars with'em, you have no chance of securing the OTPs.
Regarding runs of zeros:
The simple fact from modern cryptography is
Size of key space >= size of message space = size of encrypted message space.
As soon as you start removing special "dangerous keys" from the key space, you immediately loose perfect secrecy.
Eve wears a badge said:
"I don't know for a fact, but I would bet that OTP are used for guided weapons. A OTP can be downloaded into a missile, which is then fired, both parties can communicate securely until the missile arrives and explodes. Also I would imagine a similar system is used for fighter planes and aircraft carriers."
That's incorrect. All targeting data are uploaded into the missile before launch. Once the missile is launched, it's on its own, and can't communicate with the anyone. (I know. I used to work with both the Poseidon and Trident missile systems.)
What I find interesting is the key generation problem. How can a private individual generate truly random (enough) keys for OTP?
Is there a moderately inexpensive (
Are any of the readily available cryptographic software RNG's acceptable (OpenSSL's rand option, .NET System.Security.Cryptography.RNGCryptoServiceProvider, Truecrypt's keyfile generator, ???)?
@ Personal OTP,
"What I find interesting is the key generation problem. How can a private individual generate truly random(enough) keys for OTP?"
You are asking the question in the wrong way.
The first things you need to do are,
1, Work out "Why you need OTP",
2, Work out "How to compress the required bandwidth",
3, Work out "What latency there is in OTP. delivery".
So the first question is "why do I need OTP", there are valid reasons such as spys with very very low volume traffic where the basic simplicity of OTP trumps many technical issues.
However to all intents and purposes AES when used properly (which can be difficult) will be sufficiently secure for anybodies daily needs, providing it is "re-keyed" appropriately.
If you have qualms that AES might not be sufficient secure or the encrypted message life has to be very very long then use it chained in an appropriate fashion with another AES final round candidate which has an orthagonal design. Thus in the unlikley event there is more than a technical break against AES or the othagonal cipher then the system remains secure.
Depending on your re-keying requirment you have reduced your communications bandwidth down to a fraction of that you would other wise require with just OTP.
And as others have noted you can just as easily send the AES etc keys as well as the OTP, sending both on the face of it appears just pointless.
Which brings me onto "latency" which can be a significant issue. It can be quite considerable between issue ot the Pad and use of the Pad, and a great deal can happen in that period. For instance in times of peace the amount of "flash" diplomatic corespondance between an embassy and home country is very small. However as hostilities start to arise then both the quantities of messages and. the number of flash messages rises rather dramaticaly. If your number of pads in storage is small then this may be an issue, if however the number of pads you have in storage is large this is both a security risk and potentialy a serious logistical problem. The same applies to the distrubution of AES keys.
One area where OTP use is still valid in the modern world is after the "code books are burnt" that is for "emergancy key transfer".
Code books can "be burnt" for a number of reasons, one of which is if a general broadcast or network key has been compromised by the loss of the re-keying material (KeyMat). Thus any traffic sent under any key in the latency period is going to be compromised. Using OTP's unique to each outstation new emergency keys for immediate re-keying can be issued. Importantly the system can be switched from "general broadcast / Network" to "unicast outstation to home". Thus rendering the communications security isssues arising KeyMat material loss mute after the point of emergancy key transfer. This buys you a considerable period of time in which you can re-issue KeyMat by courier etc.
Destroying KeyMat is also advisable the minute trouble arises, an outstation can be over-run unexpectedly in just a few minutes. Thus "burning the code books" is a very very high priority. But this gives rise to the problem of how do you continue to communicate if either the books were burnt by mistake, or the "over-run" was repulsed.
From a security perspective you need to assume that the outstation "has been over-run" and that you are now dealing with "false agents", but likewise you also need to maintain communication to protect the lives of those working in the outstation as well as allowing for accidents and repulsed attempts at over-runs.
The solution is to switch the outstation to "unicast outstation to home" communications and send them emergancy keys by OTP that are unique to them, and keep them operating in that mode untill such time as their status can be verified in some other manner (remember even false information has value if you know or suspect it to be false).
To do this you actually require very very little in the way of OTP KeyMat, maybe five or ten pages at most per outstation.
Now having established how many OTP groups you need to generate, the next question is in what time period, at the most this would be every "re-supply of Keymat" which could boil down to just a few hundred groups a day.
This sort of level can be generated by any physical source including a handfull of dice and some square ruled paper or typewriter.
However importantly you need to know that all physical sources suffer from "thermodynamic entropy" that is they wear out and become less and less usefull with time, even the corners wear of dice (so they become in effect pebbles). However thermodynamic entropy will put detectable bias into your random number generation. To see this lets assume you use a radioactive source and a giger counter and your random number is generated by the time interval between clicks (a way that is often suggested for random number generation). Well all radioactive sources tick down to being non radioactive via their "half life". Let us assume you used a source with a half life of an hour, and you start measuring at exactly midnight, at 1 AM you would only expect half as many clicks, by 2 AM a quater, and by 10 AM less than one thousandth. So what you are seeing effectivly is the time interval between clicks doubling every half life (in reality it's a bit more complex because one radioactive isotope can break down into other radioactive isotopes that have different half lives).
Thus you need some process to "de-bias" your source of physical randomness, prior to anything else. There are also issues I mention further up of removing some overly long runs of zero's or other patterns (contrary to what appears to have been suggested above by "Brit") there are correct ways to remove long runs without effecting the secrecy value of the resulting OTP groups.
To most intents and porposes if you are "rolling your own" a good "thermal noise source" modulating an FM oscilator that is then mixed down in frequency is probably the best way to get a raw source of bits, you can also more easily de-bias it using relativly simple techniques.
Also don't fall into the trap of assuming that using crypto functions (especialy un whightend hashes) are a good way to "improve entropy" from a source for many reasons it's "Magix Pixie Dust" thinking.
Those points are important, but are a sideline.
1) Why? Because OTP has certain properties useful in edge cases; particularly that in a perfect world, without known plaintext, it's very difficult to tell a successful decryption from an unsuccussful decryption which results in a useable file. Also, the very simplicity means that an implementation can be trivially verified to not have bugs, which is much more difficult with more complex ciphers... except for the random pad generation, which seems extremely difficult to verify, which is why I asked.
2) Low communication traffic edge cases between a fixed, very small number of entities, where personal delivery of floppies, CD's, BD-R DL, or other media is acceptable, and any data surges would be handled by OTP used for AES and/or CAMELLIA and/or RSA and/or other key transfer.
3) Same as above.
Thank you for the information, and thank you for the warning on unweighted hashes not improving entropy, which I'd assumed.
Thus far, I've found the following low priced random number generators:
openssl rand (seems altogether too fast, which raises my suspicions)
gpg --gen-random 2 (much slower, but still unknown)
Truecrypt can generate 1KB random files with the GUI (too small to tell how fast it is)
Araneus Alea I true random number generator (hardware, written up in a couple papers are passing diehard tests, though not necessarily current dieharder tests)
P.S. I'm assuming the correct way to chain different ciphers is to use unique, unrelated keys for each? A useful alternate
@ Personal OTP,
"I'm assuming the correct way to chain different ciphers is to use unique, unrelated keys for each?"
It depends on what you intend to do.
The simplest is to just chain two ciphers of the same block size in series with different keys.
More complex is to use the ciphers in a Horst Fiestel style network or other mixing network, which results in a wider block cipher output and should provide a higher level of security (if that's realy required).
Have a look at the design philosophy of 3DES to see what some of the gains and loses are.
At the end of the day chaining/mixing ciphers is an under researched area and has got some unexpected pit falls.
With regards actual random number generators they are many and even the best fail for one unexpected reason or another. For instance an IBM 32bit system when subjected to a moderate RF field dropped to less than 8bits equivalent entropy. Even the best noise sources are subject to both physical and electrical disturbance where the desired noise signal gets modulated by other sources of energy (acoustic, mechanical, magnetic, electrical, etc) in it's environment.
The next problem is that almost invariably any wide band noise signal is not "white" but "pink" in nature and of such low level that the design of amplifiers and their power supplies etc need considerable attention to detail.
Robert T and I have discussed some of the various failings in the past.
However buying one off the shelf as a black box is not advisable for a number of reasons, not least because it's usually impossible to "test your way" along the chain from noise source to output, thus you will always have to be very wary of using the output. Likewise software solutions using some "machine entropy" suffer from a number of problems that often get hidden behind a hash or other crypto function.
Worse the only entropy may be "sampling noise", to see this imagine a spoked wheel spinning around and you very briefly flash a light across the spokes to a photo cell you get a reading of zero or one depending on if a spoke is blocking the photocell or not. If you do this sampling very very infrequently and more or less at random times then the result will look random.
However the more frequently you sample the less random it looks, worse if you sample at a rate that is some sub harmonic of the rate the spokes go by then the output will be stuck on zero or one. However worse still is that the output will be a function of the frequency difference between the spokes and the sampling rate...
If you can see the raw output of the sample gate then you can observe these failings, but what about after they have been "processed" through a hash etc.
Finally there are such things as BBS generators and Kleptocryptography whereby you cannot tell if the output is random or determanistic. Thus an attacker can hide information in the output of an RSA or other public key encryption of a counter etc and you cannot spot it but they can and know exactly what the state is inside the generator at which point it's game over...
Thank you for the further information; however, my question remains (as it is at least as difficult a question as I expected).
Is there a good cryptographic random number generation tool, or suitable combination of tools, available to those with limited (few hundred dollar) budgets?
The question applies more to OTP than to other cryptographic methods, but it does apply to most other forms of cryptography, truly random password generation, and so on and so forth.
What other good random number generators are available, or are there tips to improve the following (use hardware in a makeshift Faraday cage to at least reduce RF emissions, or combine the hardware output with the best of the software generator outputs with some mathematical operator, or ???)
So far, I'm aware of:
Araneus Alea I hardware (possibly used in a reduced RF environment)
gpg --gen-random 2
Truecrypt's keyfile generator
Microsoft .NET System.Security.Cryptography.RNGCryptoServiceProvider
??? other RNG's
Is one or more of these known to be better or worse than the others, and are there cost efficient steps that can be taken to improve the output of any of them?
What if I used a seed (32 bytes long) to generate a "random" key to encrypt the 1MB file, and then I transferred the seed (securely, I feel like ignoring the key distribution problem right now) and transferred the file to the recipient. Then they used the seed to generate that same key to decrypt the file.
Based on the article and what's been said, I'm guessing the generated key would end up failing because it's not truly random.
Is that correct? Even if it is, would it still be worth using just because the "key"/seed is smaller and easier to deal with? Or does it actually provide the same level of security the one-time pad has to give?
I made an example of it in Python here.
Maybe we should start working on seeded secure key generators that we can use for One-Time Pads and then use those for secure data exchange. :) Of course, I'm probably going to be blown off for even suggesting such a thing.
What if I used a seed (32 bytes long) to generate a"random" key to encrypt the 1MB file, and then transferred the seed (securely...
That is a description of any cipher system that is not "theoreticaly secure", because the key is determanisticaly random or pesudo random not "truly random".
So your system is not "theoreticaly secure" and also has a finite key size of 256bits. So the question then shifts to is this "cryptographicaly secure"?
This depends on a couple of things,
1, The determanistic algorithm you use.
2, The type of cipher system and it's mode.
The first one is an open question, but if you used two orthagonal block cipher systems from the last round of the AES contest you would probably be OK (for now ;-)
The second one is where it generaly all goes wrong for practical implementations.
If you step back a bit and look at a stream cipher what you realy see is
Ctxt = Ptxt + f(Key.cnt)
Where, + equals your chosen mixing function be it XOR or ADD etc etc, and f() is your determanistic algorithm being driven by a counter from a start position "Key" to generate a key stream.
However what you see for a block cipher in simple code book mode is,
Ctxt = f(Ptxt+Key)
That is the key is mixed with the plaintext as part of the deterministic algorithm.
This difference between the stream cipher and block cipher is important for a couple of reasons,
Firstly with a stream cipher there is only one key stream that would be used by every user and thus it's secrecy rests fully on the starting position. Secondly because the plaintext and keystream mixing function is very weak the security depends on no part of the keystream being reused. With the number of users worldwide and the bulk of traffic being sent the chances of this happening are actually quite high with a short keystream.
So you would need to design your deterministic algorithm to take this into account, which in all likely hood make it very inefficient in use.
A similar problem exists for the block cipher in that two blocks of identical plaintext end up producing the same ciphertext. The likely hood of this is dependent primarily on the block width and secondly on the type of information being sent (and how).
It is certainly true that a narow block width used by DES was insufficient for uncompressed video, graphics and some written text like source code or some types of database records. It is also true that the block lengths used by AES are two short for uncompressed video and some types of database records. Also "sonorgrams" sugest that speach either in plain or encoded form is also vulnerable to narrow block widths.
However there is a secondary problem with block ciphers, sometimes the plaintext is of a very very limited type and due to the "interactive" nature of an application it does not matter how wide the block is the effective plaintext alphabet might be as few as two characters (Y/N in a menu based system). Thus due to the fact the system is interactive they need one char to be sent at a time, and thus irrespective of the cipher block width only two different blocks will be seen on the wire...
Now this gives rise to a problem that is more commonly seen with stream ciphers and is known as "bit flipping" in some circles. Basically in a stream cipher you can flip a bit in the cipher text and this will cause the coresponding bit in the decrypted plain text to also be flipped. This can have a devistating effect on telemetry systems used as part of industrial control systems and SCADA systems, and potentialy will have major issues for "Smart Meters" and "Wireless Implants" if and when they get around to designing the communications protocols. Likewise with block ciphers when data is aligned with the block width one data block can be used to replace another by an advisary, thus in the interactive menu system an adversary could insert the block that coresponds to Y for the user sent block that coresponds to N, depending on how the system works this may not be obvious to the user...
There are three current ways to solve these problems only two of which belong at the encryption level in the stack. The first is "cipher modes" where the basic block cipher is effectivly used within another construct, the second is hybrid cipher systems and the third that strictly speaking is in the plaintext encoding level is data coding (2/3D parity, Hamming, CRC, Reed etc) and/or compressing of the plaintext prior to encipherment.
The solution of interest to your idea would be some form of hybrid cipher system.
For instance when you take a slightly closer look at block. ciphers they typicaly consist of two parts the Fiestel cipher/rounds stack and a key expansion stack that takes the primary key and expands it into a multitude of sub keys used within each round of the Fiestel stack. You have in effect two deterministic algorithms, the first expands the key the second being the oneway fuctions used in the Fiestel stack.
This enables you to use a block cipher as a stream cipher generator in one of three basic ways,
1, Fixed key input, counter on text input.
2, Fixed text input, counter on key input.
3, Counters on both key and text inputs.
Further you can with care use either of the first two methods in a feedback mode where the fixed input is replaced with a delayed value from the block cipher text output. Usually the delay is only one with a fixed Initialisation Vector being preloaded for the first use of the block cipher. However there is absolutly no reason why the delay has to be of only one, you could use a much longer delay line that is amenable to actually being a Galois / Fibonacci linear feedback shift register or other cryptographicaly secure nonlinear feedback shift register or stream cipher (have a look at the stream cipher "Snow" to see how you might do this).
A quick thought on this says "Why bother having the "Key Expansion determanistic algorithm in the block cipher?". That is why not drive the Fiestel stack directly from the values in the feedback shift register...
There are pros and cons but in general there are worth while advantages in doing it.
Likewise you can consider changing/replacing parts or all of the Fiestel stack.
However there is the ever present danger of removing a valuable feature unknown to you and thus removing a lot of the security (this is especialy true of NSA produced ciphers that we have seen, they are all very brittle in that even very small or apparently minor changes remove a great deal of their security).
Thus it is probably better to use well known and tested block and stream ciphers together without change in a hybrid design. One such system is Ross J. Anderson's "Bear" and "Lion" systems
That gave rise to his "Dancing Bear" system,
(In fact a lot of the papers linked to via Ross's home page http://www.cl.cam.ac.uk/~rja14/ are realy worth a good read as they give many ideas and openings for investigation and research).
Also go and have a look at the "New European Schemes for Signatures, Integrity and Encryption (NESSIE) project, a link for which can be found via Bart Preneel's very interesting home page,
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.