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.

Tags: cryptanalysis, cryptography, history of cryptography, one-time pads, random numbers

Posted on September 3, 2009 at 5:36 AM • 94 Comments

Comments

Ott • September 3, 2009 6:18 AM

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.

ThM • September 3, 2009 6:32 AM

What about Michael Rabin’s hyperencryption concept? Isn’t this a kind of OTP with a clever solution to the key distribution problem?

tcliu • September 3, 2009 6:33 AM

@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.

tcliu • September 3, 2009 7:20 AM

@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).

Petteri • September 3, 2009 7:20 AM

Quantum key distribution can be used to create OTPs. Still inconvenient and cubersome and with serious limitations.

Bruce Schneier • September 3, 2009 7:21 AM

“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.

wiredog • September 3, 2009 7:47 AM

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.

djdii • September 3, 2009 8:00 AM

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.

Jim A. • September 3, 2009 8:06 AM

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.

Zith • September 3, 2009 8:35 AM

@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.

David • September 3, 2009 8:46 AM

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.

Brian • September 3, 2009 9:25 AM

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.

cha cha cha • September 3, 2009 9:30 AM

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?

Miramon • September 3, 2009 9:49 AM

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.

anonymous • September 3, 2009 10:15 AM

“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(2pin) 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.

paul • September 3, 2009 10:37 AM

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…)

anonanona • September 3, 2009 10:42 AM

“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. 😛

Clive Robinson • September 3, 2009 10:45 AM

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.

John Hardin • September 3, 2009 10:57 AM

@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?

Tony • September 3, 2009 11:56 AM

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.

paul • September 3, 2009 12:02 PM

@john hardin:

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.

Clive Robinson • September 3, 2009 12:25 PM

@ anonymous@10:15AM,

“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.

Clive Robinson • September 3, 2009 12:38 PM

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”

John Hardin • September 3, 2009 1:05 PM

@paul: Would you use a cryptosystem that relied on a central authority to hand out copies of the keying material?

partdavid • September 3, 2009 1:29 PM

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.”

tcliu • September 3, 2009 1:46 PM

OTP reminds me of this:

http://www.theonion.com/content/node/39241

“Strom Thurmond Calls For Construction Of Transcontinental Railroad”

Karellen • September 3, 2009 1:56 PM

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.

However…

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?

RvnPhnx • September 3, 2009 2:17 PM

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.

eve wears a badge • September 3, 2009 2:38 PM

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.

BCS • September 3, 2009 2:58 PM

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

Skorj • September 3, 2009 3:38 PM

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.”

tcliu • September 3, 2009 5:19 PM

@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.

tcliu • September 3, 2009 5:25 PM

@Karellen:

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:

Not reusing the same key. (Reusing OTP)
Distributing multiple keys (for multiple messages) securely.

…and so on.

Clive Robinson • September 3, 2009 5:48 PM

@ Karellen,

“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.

http://oldweb.cecm.sfu.ca/projects/pihex/status.html

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.

Shawn Smith • September 3, 2009 6:12 PM

Karellen,

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.

Filias Cupio • September 3, 2009 7:08 PM

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.)

J • September 3, 2009 8:24 PM

@Clive, Shawn

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…

Karellen • September 4, 2009 7:26 AM

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.

tcliu • September 4, 2009 7:32 AM

@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?

Karellen • September 4, 2009 11:01 AM

@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.)

Karellen • September 4, 2009 11:13 AM

@Clive Robinson

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.

Thankyou.

Clive Robinson • September 4, 2009 11:35 AM

@ tcliu,

“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…

JimFive • September 4, 2009 2:09 PM

@Clive
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?

@Karellen

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)

JimFive

Chris S • September 4, 2009 4:29 PM

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.

Clive Robinson • September 4, 2009 6:53 PM

@ JimFive,

“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…

tcliu • September 4, 2009 7:17 PM

“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.

b • September 5, 2009 12:39 AM

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.

Roger • September 7, 2009 3:00 AM

@b:

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.

Duff • September 7, 2009 9:48 PM

@Roger:

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.)

Alex • September 8, 2009 8:39 AM

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.

Brit • October 21, 2009 12:24 PM

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.

Donnie • November 4, 2009 10:40 AM

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.)

Personal OTP • November 16, 2011 1:03 PM

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 (<$500) cryptographically secure hardware RNG available?

Are any of the readily available cryptographic software RNG’s acceptable (OpenSSL’s rand option, .NET System.Security.Cryptography.RNGCryptoServiceProvider, Truecrypt’s keyfile generator, ???)?

Clive Robinson • November 17, 2011 6:44 AM

@ 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.

Personal OTP • November 17, 2011 1:50 PM

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

Clive Robinson • November 18, 2011 7:07 AM

@ 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…

Personal OTP • November 29, 2011 10:55 AM

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

openssl rand

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?

Magnie • May 26, 2012 8:55 PM

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.

Clive Robinson • May 27, 2012 8:49 AM

@ Magnie,

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

http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf

That gave rise to his “Dancing Bear” system,

http://www.cl.cam.ac.uk/~rja14/Papers/grizzle.pdf

(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,

http://homes.esat.kuleuven.be/~preneel/

Kurt Schroeder • May 28, 2014 5:29 PM

I think that it would be possible for one time pad to work if the pads themselves were generated based on a formula for known information which changes. For example, the NOAA weather report for the zip code represented by the first 5 digits in the transmitted message, intermixed with the lead story from the Green Bay Press Gazette for the day before.

In this way, a one time pad would function based more on something like a numbers station, where the data can be sent to anyone, but only the recipient knows how to generate a new pad. This would seem to be more of a manual process, so I do not think that it would work for longer pieces of information.

I realize this is not perfect. Another thing to do would be to mix up the letters in the words sent, like this:

Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

This would seem to cause trouble for programs seeking English words within the coded messages.

I would love to hear comments on this.

unclejed613 • July 11, 2014 8:55 PM

somewhere back in 2009, “wiredog” mentioned a OTP system that was in use…. actually there were two methods of encryption in “the booklet”. one was a randomized vigniere (sp?) table, and the other was a “brevity codes” list (where words such as “battalion”, “company”, “aircraft”, or “tank” were reduced to 3 character random code groups, such as “VYX”, “W3S”, “9XW”…. in my MOS (31C), we used crypto gear as well, but such equipment was often inoperative because the aging equipment used a lot of high-failure-rate components, so when sending in cleartext we had to use the sets of tables. the way the booklets were set up, you ended up with the same tables more than once per month. this was a bit of a challenge, but in the brigade i was in, we had some inventive ways to avoid giving away the farm…. and it worked. callsigns, codesheets, frequency lists, and crypto keys were changed every day.

with the combination of the vigniere table and brevity code table, a typical “”cleartext” message might look something like this:

M76 WILL G9E AT LBTERH TO SXJRNV4SELP AND WAIT FOR S54 TO BEGIN DR5 ON VL9GJRTCDG BEFORE NL6 TO BR549KLMES

GeorgeWest • August 8, 2014 12:52 PM

I couldn’t pass crypto 101. I see a simple way to generate a true random OTP key in a very simple way. Perhaps someone can show me why it might not be reliable.

We will build the key one bit at a time.
We start with one million 1-bits in stack A and one million 0-bits in stack B.
We will build stack C by pulling from A and B randomly.
We use any RNG to provide a whole number between 1 and 1,000,000.
If its an odd number, we pull from stack A. Evens get pulled from stack B.
Eventually, one stack will run out.
Some genius will need to figure a way to distribute the other stack to C.
Now we cut stack C in half and make two new stacks A and B.
Repeat until ???

Although RNGs are never perfect, using their odd/even result seems a lot safer than using their output values.

The number of 0-bits is assured to be the same as the number of 1-bits in the final key. I’m not sure, but I think this takes away a lot of tools from a cracker.

The key could be used exclusively for communication between only two parties. One would use it from front-to-back, the other from back-to-front until it got perhaps 90% used up.

Clive Robinson • August 9, 2014 1:51 AM

@ George West,

Your RNG uses a “card shuffling algorithm” from another RNG.

Effectivly you are “stiring the pot” in a way based on the RNG you use at the base of it. If this base RNG is a PRNG then the whole system remains a PRNG. If it is TRNG then it remains a TRNG.

The amount of real entropy remains the same, even though the complexity may be very high. This is because if you thing about it the PRNG is determanistic and anybody who can determine the start point can regenerate the output of your generator.

Thus the question falls to the complexity of the algorithms in use. RC4 uses a card shuffling algorithm and originaly it was considered secure, these days it’s considered to be not secure by many people for various reasons. This shows that even PRNG algorithms age and yours is very similar to a very old stream generator (alternating generator) that is nolonger used.

Contrary to what is implied by what many people appear to say “TRNG is good, PRNG is bad”, some PRNGs are quite good and can have proofs of security based on their complexity, these are generaly called CS-PRNGs. A simple example is AES in CTR mode, the very predictable output of a counter is encrypted by AES in “cipher book” mode. The complexity and theoretical strength of AES is where the strength of this CS-PRNG comes from.

TRNGs however range from very bad to very good and it is difficult to tell which you have as the statistical tests used only test for a very small fraction of the possible ways a TRNG could fail.

Which is why most TRNGs you see are infact TRNGs of unknown goodness behind a strong crypto or hash algorithm.

As a one time designer of TRNGs I’m on record as saying this is a bad idea for various reasons, and have called out Intel on their supposed TRNG design back a long time ago when they first fielded it. The reason being was that they did not provide a direct output from the TRNG only the hashed TRNG therefor you could not determin if the TRNG had failed or been influenced in some way.

I’m not impressed by any of the TRNGs fielded by chip manufacturers because they all make this fundemental cludge, and it cannot be coincidence so one has to ask why they do it, or perhaps what they are hiding and why…

My limited investigations suggest that the TRNGs they use are at best not very good even when used in ideal conditions…. which they are almost never used in in reality.

GeorgeWest • August 23, 2014 12:46 PM

Thanks Clive.

Now I understand. So the base RNG makes the whole ordeal theoretically reproducible. But what if the base RNG uses a seed from a true random source? Perhaps I live next to a busy freeway and I hang a microphone out the window. The base RNG is provided an audio sample every time it needs a seed. Now where is the flaw?

Sorry for the amateur questions. I’m trying to get up to speed on this fascinating subject. I am convinced that OTP is the only theoretically secure system if all elements of the system are flawless. I see that practical implementation makes a flawless OTP near impossible. Perhaps the biggest statistical flaw is an unwarranted certainty of randomness that is doomed to be latently discovered. Nonetheless, the 100% theoretical security makes OTP difficult to discard. All other encryption methods rely upon a bounded degree of computing power in the hands of the code crackers. The day will arrive, if it hasn’t already, when the foolishness of such a reliance will be realized. OTP seems theoretically 100% secure while every other system is (or will become) 100% crackable.

My rather uneducated vote is to put our energy into perfecting OTP.

Clive Robinson • August 23, 2014 5:17 PM

@ GeorgeWest,

The proplem with OTPs is not their theoretical security but their practical security within any given system. Unsuprisingly for what is such a simple algorithm the major problems with OTPs are what are known as Keying Material or KeyMat problems, and little attention has been given to the issues by the open crypto community.

Firstly the KeyMat realy must be generated by a non determanistic process, otherwise the security is the equivalent of a stream cipher. This calls for a high quality GWN noise source with sufficient bandwidth to meet the KeyMat quantity / time requirments.

Secondly you must generate sufficient KeyMat for the maximimum possible message rate and time period. This can be an enormous amount of KeyMat think of it as a 10Mbit/sec link for thirty one days, that’s 3,348,000,000,000 Bytes or ~700 DVDs for each end of the comms link for each and every month. Appart from the managment problems involved with making 1400 DVDs a month securely and accountably, you also have to generate it well within the month to allow for transportation and in transit loss which means your “noise source” needs to have a bandwidth in excess of 80MHz with a uniform probability across the bandwidth which is a tough call for a whole mountain of reasons.

Then there is the secure and fully auditable transport issues which unless you are a diplomatic courier is not going to happen across boarders these days. And it’s not a job you can “outsource” to the likes of TNT, UPS or FedEx no matter what promises they make.

Then there is secure and auditable storage at either end of the comms link.

Then timely, secure and auditable transfer from storage into the OTP system.

Then secure and auditable transport back into storage to prevent reuse.

Then secure and auditable transport to the place of destruction.

Then secure and auditable destruction of the media.

Then secure and auditable checking of the waste from the destruction.

And on top of this the personel to not only do the auditing but securely and auditably keep the audit records prior to their destruction some point long long into the future.

I can assure you from practical experience it’s not something you want to be doing unless you absolutly have to, especialy when there are beter ways to do things.

And even if you do get that right an OTP system is still just a stream cipher and suffers from all the failings of stream ciphers with absolutly none of the benifits from a practical point of view.

The only advantage they have is when they are a genuine “Pad” designed for easy hand and pencil use, that is only ever used for emergency uses in potentialy hostile situations. Outside of Mil/Dip government use, it is only certain type of large corporations working in resource exploration and extraction in highly volatile places that need them and have the resources to implement them properly. And even then the messages are of minimal length for the likes of emergancy KeyMat transfer or for crypto or other secure equipment destruction instructions.

John Underhill • September 3, 2014 3:28 PM

@Clive Robinson
You’ve tailored the scenario to suit your argument, sorry..
Who says the random has to be true random? This is a mistake in thinking, it can be made with deterministic algorithms, given you design those algorithms in a way that they create output that is stronger than the parts that make it work.
Instead of one AES stream run in counter mode, run two independent AES streams and XOR them. Create an internal state machine that uses an entropy pool to extract new keys/counters via SHA. Use these 96 byte keys to create blocks of random, 100KB, and that is a 1/1000 ratio, (but that is arbitrary and can be adjusted based on requirement). I published a prototype to open source, it requires 1152 bits of state, (expansion table + seed).. pseudo-OTP is viable, and can be made extremely powerful.

Anura • September 3, 2014 3:39 PM

@John Underhill

“Who says the random has to be true random? This is a mistake in thinking, it can be made with deterministic algorithms, given you design those algorithms in a way that they create output that is stronger than the parts that make it work.”

If it’s deterministic, it’s just a regular stream cipher, not a one time pad. One time pads, by definition, require a randomly generated key of equal length as the plaintext. If you want a stream cipher, those already exist and there is no need to roll your own.

John Underhill • September 3, 2014 3:48 PM

@ Anura
I called it ‘pseudo-OTP’, but call it a Vernam cipher if that helps.
A regular stream cipher -with 1152 bit encryption? Really? I’ll roll my own, because what is out there will be proved inadequate, (sooner rather then later)..

Anura • September 3, 2014 5:07 PM

@John Underhill

Yes, anything with a fixed state is just a regular stream cipher.

It’s highly unlikely that there will be a practical attack against a modern stream cipher like Salsa20 any time soon. There have been diminishing returns on cryptanalysis; the more we learn about breaking ciphers, the better cryptographers are at defending against them, and the more difficult it is to perform future attacks. Even if there are practical attacks against AES in the future, it will probably take massive resources and be subject to specific constraints. No offense, but your data probably wouldn’t be important enough to be worth devoting the resources to breaking it.

Cryptography is hard, and most people who roll their own end up with algorithms that are trivial to break. Of those who have non-trivial algorithms, the vast majority fails against modern cryptanalysis. Unless you can actually do serious cryptanalysis against modern ciphers, you should not be rolling your own for anything other than recreational or educational purposes.

For well over a decade, we have had AES and SHA-2 without any serious algorithm breaks, but we have had pretty major security holes in the software. This brings us to the main problem: the implementations are where the failure is, not the algorithms. Unless you really know what you are doing, and that means understanding the flaws in cryptographic protocols and libraries (if you think security is easy, you do not know what you are doing) then you should not be implementing cryptography, even if you are implementing proven algorithms.

If you really think you need a large state, you can use Keccak using the sponge construction with b = 1600; it’s a 1600-bit state, and it’s at least undergone some serious cryptanalysis (although some might argue you should wait longer, and I wouldn’t disagree). Just don’t implement it yourself, and instead get a trustworthy implementation. Better yet, stick with either Salsa20 or AES, Twofish, or Serpent in counter mode.

John Underhill • September 3, 2014 5:26 PM

@Anura I am reasonably familiar with the algorithms involved, having written implementations of them in various languages over the span of many years. I am not proposing that one re-invent the wheel here.. AES run in counter mode is a well established vehicle towards producing pseudo random output, xoring two independent streams is trivial to implement, requires no change to the underlying algorithm, and should do nothing to diminish the security.. and yet you now have double the state, and with that, an immense amount of additional security.. feel free to point out the error in my logic here..

Anura • September 3, 2014 5:38 PM

@John Underhill

By encrypting twice, you go from 256 bits of security to 257 bits of security. You also describe a complex keying scheme, which is where your system will most likely be vulnerable to attack, all to solve a problem that doesn’t exist.

John Underhill • September 3, 2014 6:01 PM

@ Anura
Who said anything about encrypting twice? Let me be clear; You take two AES CTR streams, each with their own unique keys and counters, you create 32 bytes of p-rand at a time, 1 * 16 byte block from each transform, and you xor those two 16 byte blocks, producing a single 16 byte block, -that’s your output. In order to unwind this, you would require -2 keys, and -2 counters, (the 96 byte seed passed into the method), that is 768 bytes of state, not 384. The number of times the generator is reseeded also amplifies the strength of this method; if you xor that pseudo-random with a 1MB file, and you generate 100KB of pseudo random with each seed, that is 960 bytes of state required to unwind that message.
As to the methods I used in my own implementation, it is a little bit complicated, but all based on accepted methods, nothing all that original or exciting, it’s just implemented in what I believe to be a clever way..

Clive Robinson • September 3, 2014 6:25 PM

@ John Underhill,

It is unwise to XOR two generator outputs together, unless you have very good reason to believe they are “fully independent” of each other.

In the overly simple case of using two LFSRs the result is not a new output bit stream, but simply a time shifted version of the same bit stream.

The easiest way to get some surety that you won’t get degeneration is to use two generators that are orthagonal to each other in design. Even then some care should be used.

I can not remember of the top of my head if AES has ever been specifically examined for the degenerate use of XORing two CTR generators together. Even if it has it’s not the way I would chose to do things, based on previous issues with other block ciphers.

John Underhill • September 3, 2014 6:43 PM

@ Clive Robinson
If you have concern over how the streams are combined, or using the same algorithm with both streams, (and what you are saying represents minute tells in the output, if any, given that keys and counters are unique and sufficiently distant from each other in value), then xor Camellia and AES, whatever.. The point is the same. Psuedo-OTP can be used to create extremely powerful encryption, key sizes can be made manageable using pseudo random, and a powerful generator can create encryption strengths that are well beyond the ciphers of the day.

Anura • September 3, 2014 6:55 PM

XOR is an Associative operation, it doesn’t matter if you do AES-CTR-ENC(AES-CTR-ENC(plaintext)), plaintext ^ AES-CTR-ENC(AES-CTR-ENC(null)), or plaintext ^ AES-CTR-ENC(null) ^ AES-CTR-ENC(null), they are equivalent. Through a meet in the middle attack, two combined AES-256 stream ciphers have, at most, 257 bits of security with known IVs. At most, two AES-CTR keystreams from two random keys, with two random secret IVs provides 384 bits of secuirty, 384 bits for one key/IV combination, and with some known plaintexts you don’t need to guess the second counter, just brute force a 256 bit key, which is negligible compared to the cost of brute forcing the first cipher.

Rekeying only increases the time to crack linearly, and then the keying algorithm becomes another point of attack that may be easier to attack than the cipher itself, or combined since now the keys and IVs are now not independent of each other. Furthermore, there may be additional cryptanalysis that exploits weaknesses in AES to reduce the effective strength of your algorithm.

@Clive Robinson

If you have two keystreams from AES-CTR that were generated using independently generated keys (even if they use the same IV), they are at least as secure as encrypting it once. Otherwise, the attacker would be able to make it easier to break by encrypting it again.

John Underhill • September 3, 2014 7:08 PM

@ Anura
That’s what you call a ‘pie in the sky’ analysis, if both vectors ‘were already known’? Haha.. hey why not give him the keys too.. The random generation and the encryption are two completely separate and distinct processes. The random generator knows nothing of plaintext, it only generates random, the encryption happens somewhere else entirely, so no, your explanation does not fly.. Meet in the middle attack? again, not encrypting here, so, no meet in the middle. Timing attack, possible but unlikely. The fact is, you need the whole 96 byte key to brute force this implementation, and that is 768 bits, which means 2^(768 – 1), not 257, not 384, not.. whatever. Nice try.

Clive Robinson • September 4, 2014 1:36 AM

@ Anura,

Two block ciphers in CTR mode that are XORed together are not as strong as just on cipher in CTR mode, due to the “run length” issue that criticaly effects OTPs (but few people talk about).

For a random permutation map where each input uniquely maps to an output and vice-versa it can trivially be shown that the maximum runlength of any pattern is 3N-2 where N is the bit width of the map. That is three successive outputs from the map driven by the counter need to differ by one bit so 1000,0000,0001 is the longest pattern of zeros possible for three successive outputs wher N = 4.

It can be further seen that when you XOR the output of two such random permutation maps the 3N-2 constraint on run length nolonger applies, because the output is nolonger a random permutation but the –2’s compliment– difference between the two maps. The most degenerate form would be with two identical maps driven by the same counter which after XORing would always give zeros no matter what the counter value is.

To prevent this extended run length issue all valid random permutation maps would need to be the very very small few that are orthagonal to all others on their differences which is a hard ask. Even then it can be shown that the minimum run length is going to be 6N-2 and usually much longer.

So for use as an OTP XORing the output of any two generators can be seen to produce a degenerate generator in terms of run length…

John Underhill • September 4, 2014 8:05 AM

@ Clive Robinson
You are both trying very hard to twist my example to fit your analysis. Counters and keys must both be unique, that has been said. Run length is 100KB in my implementation. I do know that entropy levels are not diminished by this method, having run output through NIST STS about 100 thousand times, so, not really sure what you’re on about.. but if you can point me at a serious paper that states quite clearly that this method has flaws, I’d be happy to look it over.

Clive Robinson • September 4, 2014 10:37 AM

@ John Underhill,

I’m not twisting anything it was you who brought up using two AES-CTRs XORed at the output not me. I’ve simply said I don’t think it’s wise and given a reason why.

If you don’t wish to give my warning or the warnings of others credence, that is your choice, and if you chose to use your system in anger good luck to you but please don’t ask me to use it.

As for your running it through NIST STS that is at best a low water mark, that like other tools of it’s kind will be updated over time.

Your bone of contention appears to be CS-PRNG -v- TRNG.

A TRNG should have one advantage over a CS-PRNG, which is no matter what the attacker knows about it’s state at any instant in time they cannot predict either future or past output bits with any certainty better than 50%, even knowing the compleate state of the TRNG at their instant of measuring. This cannot be said for any CS-PRNG where an attacker knows the full state at some instant.

That is the primary issue you appear to want to disregard, that as I said is your choice and you can live with it if you wish. Me personally I’d much rather not and I would not advise anybody else to do so.

The advantage CS-PRNGs are generaly considered to have is “speed at a known level of security”. The problem is ensuring the secrecy of the system. In nearly all implementations of CS-PRNGs they leak their state information one way or another via timing side channels. Thus to get the supposed “speed and security” of a CS-PRNG you have to build it in a secure manner, and that is realy not very easy these days.

If you cannot afford a TRNG that meets your speed requirments, then there are still other ways to get some TRNG benifits whilst using a CS-PRNG by using hybrid systems and the so called “entropy pools”, you would be better off investigating those than calling a fully determanistic CS-PRNG a generator suitable for making OTPs. Your sugested sysstem is in reality as has been pointed out to you a “stream cipher” and for various reasons not a particularly good one.

Your insistence other wise is one of the dangers Bruce and many other cryptographers warn against. Thus I will tell you to do what they would advise you to do, “go away and try and break your system, if you cannot then document and make available your findings” this will enable others to judge your capabilities before deciding to invest more than a minimal amount of their time for your benifit, not theirs. Another thing you could do is pay someone else to do the work for you, but you need to remember “Sometimes when you pay for what you get, you may get something you don’t want” oh and no refund for your disapointment either…

John Underhill • September 4, 2014 11:02 AM

if you show a way to distinguish the stream AES_k1(C1) ⊕ AES_k2(C2) from a random stream with fewer than 2^64 outputs, you have just demonstrated a way of distinguishing AES from a random permutation.
The problem I am having is that both you and Anura are dressing up your answers in techno-speak to make them appear authoritative to a casual reader, when in fact, what you are saying is conjecture only, based on pre-conceived bias, and with no root in fact or empirical analysis.. Anyways I’ll not pollute this thread any more..

Steve Z • September 4, 2014 10:25 PM

@ Clive Robinson
I agree with your comments about about the maximal sequence length of a single permutation based PRGA being equal to three times the base field width minus two, with the caveat that this maximum length is NOT assured in counter mode (in fact in counter mode, it is overwhelmingly more likely that this maximum sequence will NOT occur).

…but then, Clive, you seem to go completely off track:

“To prevent this extended run length issue all valid random permutation maps would need to be the very very small few that are orthagonal to all others on their differences which is a hard ask.”

I think you are on the wrong track here two different ways:

First, you seem to be under the silly impression that the permutation space is quite limited compared to the key space, making it difficult to avoid correlated permutations while dealing with all those keys.

Actually, the permutation space is HUGELY, exponentially, many orders of magnitude, greater than either the 128 bit field width OR the 256 bit maximum key size. Specifically, for AES 256, there are 128! possible output permutations that the cipher has to chose from, or roughly 3.85620 E+215 which is equivalent to more than 716 bits. If we divide the enormous potential permutation space by the maximum key space: 128!/256^2 = 5.8841 E+210 we see that this means that there are more than 200 decimal places more permutations, than possible keys to use them. So if the cipher is worth a damn, uncorrelated permutations will be the rule, not the exception.

Second: You seem to be saying that to get a good random distribution in the XOR’d combination stream, we need to select from permutations that are somehow ‘orthogonal’. No, this is NOT what we want – ‘orthogonal’ implies related, but intentionally offset or ‘out of phase’ in some way – what we DO want are permutations that are statistically uncorrelated and that show good bit wise and byte wise random qualities. This is what AES (and all other well designed block ciphers) are designed to provide, and this should lead to the proper probabilistically distributed XOR output with no significant ‘runs’ or other issues.

Then you go on, somewhat erratically to state:

“Even then it can be shown that the minimum run length is going to be 6N-2 and usually much longer.”

But then seem to contradict this statement with:

“So for use as an OTP XORing the output of any two generators can be seen to produce a degenerate generator in terms of run length…”

Let me get this straight – the XOR’d output will have ‘minimum run length’ of 6N-2, which is about TWICE the number of bits verses only 3N-2 you previously stated was the maximum for a single permutation based source, and potentially ‘much longer’ random runs are possible.

So the XOR’d source has a guaranteed maximal sequence length of DOUBLE the NON-XOR’d … So, just HOW does MORE randomness in the output, as PROPERLY evidenced by the [small] but finite possibility of much longer strings of ZEROs or ONEs constitute a “degenerate generator in terms of run length…”

Either I’m not understanding what you really meant to say, or your definition of a ‘degenerate generator’ is very different than my understanding of the concept.

For what it’s worth, I do agree with you that it is desirable to combine unrelated Ciphers, where possible, not so much because it eliminates some kind of correlation risk, but simply because it will insure that the concatenated cipher maintains a security margin, if one of the constituent ciphers is compromised.

Also combining ciphers from radically different groups can work synergistic to make cryptanalysis much more problematic.

For example, one of my personal favorites is a super-encrypted cipher stack consisting of:

RC4 -> AES-128-CBC -> RC4

With each cipher, of course, having it’s own unique 128 bit key, and the middle layer AES block cipher using a hidden 128 bit CBC IV.

We could implement something like this in linux as simply as:

openssl rc4 -nosalt -e -K ${KDFout:0:32} | openssl aes-128-cbc -nosalt -e -K ${KDFout:32:32} -iv ${KDFout:64:32} | openssl rc4 -nosalt -e -K ${KDFout:96:32}

The synergy in this arrangement is that it lets us maximizing the security of the composite cipher, and take full advantage of all 512 bits of key material (128 bits in the first RC4 key, a 128 bit key and 128 bit hidden IV in the second layer AES cipher, and finally another 128 bits in the final RC4 key)

For anyone interested, the openssl hex key values of the form ${KDFout:0:32} represent parsed hex keys extracted from a VERY strong Key Derivation Function which uses the exact same super-cipher stack:

KDFout=$(dd if=/dev/zero bs=1 count=1000000 2>/dev/null | pv -s 1000000 | openssl rc4 -nosalt -e -K ${KDFin:0:32} | openssl aes-128-cbc -nosalt -e -K ${KDFin:32:32} -iv ${KDFin:64:32} | openssl rc4 -nosalt -e -K ${KDFin:96:32} | sha512sum -b | cut -c 1-128)

Basically this KDF pipes ONE MILLION ZERO BYTES to RC4, causing it to generate a 1,000,000 bytes of keystream, then this output is super encrypted by AES-128-CBC, and then finally encrypted a final time by a second independently keyed separate RC4 instance, then piped to SHA512 which generates a hash based on the full 1,000,000 byte keystream (obviously the 1,000,000 byte value represents the ‘work’ factor of the KDF making it trivial to adjust).

Also, just in case you were wondering KDFin is just 512 bits of base key material in also in the form of a 128 hex digit SHA512 hash, which is taken from an initial SHA512 hash of the users Password and a 256 bit binary SALT value from /dev/random.

This KDF has the virtue that it is completely immune to KDF speedup attacks based on HASH internal state forwarding that afflict many simple iterative hashing schemes (the hash function is running as fast as it can already, as well as uniquely being immune to a security breach of any single one (and possibly two) of it’s constituent parts, AES, RC4, and SHA512. For example, if an devastating attack is found on RC4, rendering it a non-secure-prga, the KDF would STILL be secure against both forward KDF bypass, and backward Key Recovery, due to the cryptographic strength of AES and SHA512. In fact, I believe that this simple KDF will retain it’s security, as long as any ONE of RC4, AES, or SHA512 remains fully secure, which is pretty impressive.

I’d love to hear some feedback on both the cipher and KDF, let me know what you think.

Steve B • September 5, 2014 12:18 AM

Ok, I’ll byte…

Here’s my entry in the ‘Do Not Open Till Doomsday’ super secure OTP replacement contest.

First, though not for his reasons, I do agree with Clive that in creating a composite super-cipher OTP substitute, in ultra high security applications, it is desirable to combine multiple cryptographically unrelated ciphers.

This is not so much because it eliminates the small risk of correlations in the super encryption process, but rather because it will make cryptanalysis much more difficult, and insure that the concatenated cipher still maintains a security margin, even if one of the constituent ciphers is compromised.

Also combining ciphers from radically different groups can work synergisticly to increase the cryptographic strength of the component ciphers making cryptanalysis much more problematic.

For example, one of my personal favorite ‘super-ciphers’ is a super-encrypted cipher stack consisting of RC4 AES RC4 in this arrangement:

RC4 -> AES-128-CBC -> RC4

With each of these three ciphers of course having it’s own unique 128 bit key, and the middle layer AES block cipher having a hidden 128 bit CBC chain with a secret IV.

Though it sounds quite complicated, we can implement something this composite cipher in linux quite simply as:

openssl rc4 -nosalt -e -K ${KDFout:0:32} -in MyFileIn.txt | openssl aes-128-cbc -nosalt -e -K ${KDFout:32:32} -iv ${KDFout:64:32} | openssl rc4 -nosalt -e -K ${KDFout:96:32} -out MyFileOut.ebk

The variable KDFout above represents 512 total bits of key material, divided into unique 128 bit keys as follows – 128 bits in the first RC4 key – a 128 bit key and a 128 bit hidden IV in the second layer AES cipher – and finally another 128 bit key for the final RC4 cipher layer.

The synergy in this arrangement is that the HUGE internal state of RC4, and the fact that it’s stream output has a super long cycle that is totally uncorrelated to any facet of AES’s internal structure, helps protect AES from possible future mathematical breaches to it’s security, while AES’s excellent ‘white noise’ like statistical properties completely mask RC4’s small statistical biases, making it impossible to mount internal state or key recovery attacks on RC4.

Also hiding the AES output in the middle layer, means that the cryptographic properties of the cipher-block-chaining process are greatly enhanced. This is because after hiding the initial IV as part of the keying process, we ALSO hide every subsequent IV, since the addition of a RC4 encryption layer above AES means an attacker can’t simply get IV values by reading previous cipher blocks. Diffusion is optimal, since changing any bit of any of the 512 bits of key material changes the entire cipher text starting from the first byte.

This is a really strong cryptographic construction which will resist all known attacks more efficient than brute-force today (and with 512 bits of total key material in the composite cipher ‘brute-force’ is not going to be happening any time soon) – and will ALSO resist proposed future attacks based on hypothetical advances such as Quantum Cryptography. Even assuming that Grovers quantum cryptography algorithm could be applied to stream ciphers like RC4 (which it can’t), and assuming that they could get it to work with a complex composite RC4-AES-RC4 cipher as well (which they can’t) even then, even if it DID WORK, reducing a 512 bit key to 256 bits isn’t going to be much help to an attacker trying to mount a brute-force attack.

Also, for anyone interested, the ${KDFout:0:32} type hex key values above represent parsed hex keys extracted from a very nice Key Derivation Function which uses the exact same super secure RC4-AES-RC4 super-cipher stack, and which has other cryptographically strong features:

Basically this KDF pipes 1,000,000 ZERO BYTES to RC4, causing it to generate, in turn, 1,000,000 bytes of it’s raw csprga keystream, then the RC4 output is super encrypted by AES-128-CBC (with a hidden IV), and then finally encrypted a third time by a second, independently keyed, separate instance of RC4, with the final triple encrypted bytes then piped to SHA512 which generates a hash based on the full 1,000,000 byte triple encrypted keystream. This SHA512 HASH is extracted as text in the form of 128 hexidecimal digits, which is then sub-divided into 32 hex digit (128 bit) keys for use by openssl with the -K option.

Obviously the 1,000,000 byte value above is arbitrary and represents the ‘work’ factor of the KDF making it trivial to adjust.

Also, just in case you were wondering, KDFin is simply 512 bits of base key material used to securely key the KDF before it runs. This data is also in the form of a 128 hex digits, also divided into 32 digit groups (128 bits/key), which is generated by simply SHA512 hashing the users Password with a 256 bit binary SALT value from /dev/random.

This KDF has the virtue that it is completely immune to KDF speedup attacks based on iterated HASH internal state forwarding that afflict many simple iterative hashing schemes (the hash function is running in a single instance, as fast as it can already, and can not be parallelized).

Another virtue (one that is unique to my KDF so far as I know) is that this KDF algorithm is immune to a security breach of any single one (and possibly two) of it’s constituent parts AES, RC4, and SHA512. For example, if an devastating attack is found on RC4, rendering it no longer cryptographically secure as prga, it would still function in this algorithm, and the KDF would STILL be quite secure against both forward KDF bypass, and backward Key Recovery attacks.

In fact, under most conditions, I believe that this KDF, despite it’s simple structure, will retain it’s security, even in the face of breaches in TWO of it’s cryptographically secure components (i.e. as long as any ONE of RC4, AES, or SHA512 remains fully secure).

As you might expect, like triple DES, the triple RC4-AES-RC4 encryption slows things down a bit, but because the base ciphers are quite fast individually, the combined overall performance is still reasonable, and well worthwhile if you require ‘Do Not Open Till Doomsday’ levels of security.

Because Bruce says he is not much of a Linux kind of guy, I have avoided attaching the full BASH encrypt and decrypt scripts from the test implementation I developed, but can do so if requested (they are quite compact at only about one page of code each).

I’d love to hear some feedback on both the cipher and KDF, let me know what you think.

Steve B • September 5, 2014 12:46 AM

Just a quick apology for the above double post, I was having trouble with the forums ‘Human Verification’ Fill in the blank question.

I have a question of my own, why does it NOT accept Security as well as security as an input (especially since that is the CORRECT answer)? I lost an hours of typing because of this when sent ‘back’ to a blank input window.

Also, be aware that Steve B is my correct ID, but does NOT stand for Steve Bellovin (in other words I am not the original author of the post, but, just coincidentally, another Steve B).

Anura • September 5, 2014 12:59 AM

If you are going for something ultra-secure, consider this: pretty much any attack against a modern cipher requires some amount of known plaintexts. If performance and bandwidth aren’t that important, prevent known plaintexts by mixing truly random data with each block and encrypting in CBC mode. Now only half the plaintext is known at most. To provide a little extra security, you can then take the plaintext and XOR it to the random data from the previous block, so now while you might know of some relationships between plaintext and random data, there is never really a known plaintext. Make sure you have two IVs, one for the CBC mode, and one IV that gets encrypted and used as the secret to XOR to the first plaintext. Go ahead and encrypt the plaintext with a stream cipher if you wish (I like Salsa20, RC4 should be deprecated), and go ahead and encrypt the output with something else if you like (e.g. Twofish in ECB mode should work fine).

Clive Robinson • September 5, 2014 2:08 AM

@ Steve B,

Yup I think I got caught on that as well when the question first appeared…. Also due to another issue –smart phone on the move– I’ve just lost a longish message I was posting to Steve Z…

So not a good start to the day for both of us 🙁

Steve B • September 5, 2014 4:00 AM

@ Anura

No offense, but I couldn’t make heads or tails out of your CBC mode comments.

Under normal conditions, CBC adds security only by ‘whitening’ the input to the block cipher so that replicated values are avoided. This lets us avoid issues with watermarking, where the cryptanalyst knows for example that the first block of cipher contains know plain-text ‘x’ and notes that this encrypts to a now-known cipher-text of ‘y’, then can search for all cipher-text blocks containing ‘y’ and map them back to ‘x’ which IS possible in ECB mode. It also prevents chosen plain-text attacks, since the IV ‘whitening’ prevents the potential attacker from controlling the actual final bytes that are encrypted.

But CBC normally does NOT add any additional bits to the ciphers key strength, because the IV’s for the first block are usually disclosed, even for the first block, and even if not, all subsequent blocks just use the previously encrypted blocks value as the next block’s IV.

So if you want to try a possible key against block (N), you just decrypt (N) with your candidate key then XOR out the IV using the value retrieved from the previous (N-1) block, and BINGO you are either looking at your expected plain-text (in which case your key guess is correct) or you are looking at garbage (in which case it’s not).

But with multiple encryption layers, things are different if we use CBC in the first layer, then hide this under a second layer of encryption, because in this case the attacker can NOT read ANY IV values directly, which means that if we hide the initial IV, the attacker has to try to guess the IV’s used for each block which is essentially impossible under the obfuscation layer provide by the second cipher.

So in simple terms:

With single encryption, CBC only prevents watermarking and chosen plain-text type attacks and adds nothing to the key strength.

…but with at least two layer multiple encryption, by using CBC in the bottom layer with a cryptographically secure hidden initial IV, we see a significant strengthening of the composite cipher (making your comments about the difficulty of cryptanalysis with randomized data perfectly correct, but ONLY for multi-layer encryption)

As you your comments about RC4, sorry I don’t agree that it should be ‘depreciated’ and scrapped. RC4 has been subject to cryptanalysis for more than 20 years now, and it’s strengths and weaknesses are well understood at this point, and it would be a shame to throw that away because of a bad rap created by cryptographic vulnerabilities caused by poorly conceived, flawed RC4 protocol implementations.

This would be like scrapping AES, because it was vulnerable to the BEAST attack.

A cipher that you can fully implement in about 10 lines of code, that has survived 20 years of rigorous cryptanalysis can’t be all bad.

So, Instead of scrapping RC4, I think it just needs to be UPDATED to fix minor implementation issues that should have been ironed long ago.

Changes, like specifying that compliant RC4 implementations MUST provide a –skip parameter so we can avoid the small biases and key correlations in the initial output rounds (this was recommended by the author more than 20 years ago!). Skipping these bytes takes a fraction of a millisecond on a modern PC, so the performance hit is negligible.

So don’t knock good ole’ RC4, because if you just respect it’s requirements and limitations (which mostly involve obeying Obama’s rule – “Don’t doo stupid S#%t”) then RC4 can continue to provide very good security.

Another RC4 family steam cipher I would like to see given more study and possibly standardized is RC4A, which builds on the strengths of RC4 with almost none of the weaknesses. RC4A has been reported to still have tiny remaining biases, but I have found that with a proper key schedule, they are orders of magnitude below the levels needed to mount any kind of practical attack (even when given an oracle of.millions to billions of bytes of keystream, as in those ridiculous TLS type RC4 attacks). Frankly, one of the biggest advantages that a new RC4A standard would give us is that it would be a NEW standard, so we could start with a clean sheet of paper, and FIX things (like skipping initial output bytes) that should have been fixed in RC4, but never were, because it was already in use.

I am also interested in the chacha/sulsa family. I like that you can random-access the stream, but have been waiting for more cryptanalysis before jumping in with both feet

Clive Robinson • September 5, 2014 4:06 AM

@ Steve Z,

The problem with trying to keep posts short to not upset other readers is what has caused the confusion 🙁

I’m well aware of the difference between the key space size and the permutation space size. I’m also aware that the majority of the permutations are “not good” from a cryptographic view point with such minor issues as half of them are bitwise inversions of each other, likewise value wise etc. Thus those considered suitable candidates for a crypto system by their value maps are small. An even smaller number is the subset of those that are suitable by output value difference between any two maps at any offset in the counters, this is a much harder problem to check, and I’m not aware of any short tests or explanations as to which members fall into this very reduced set, which you cover with “So if the cipher is worth a damn, uncorrelated permutations will be the rule, not the exception.”

What I’m talking about is finding the exceptions or proving they don’t exist, no matter how rare they might be.

There is an old joke of “In nature only three numbers make sense, zero, one and infinity”, what it is actually talking about is that something does not exist, there is only one example of it or there is an unknown number of examples. I’ve shown for the random permutation map there is a known bound on the run length. I’ve further shown that this bound does not apply when the output of two maps are XORed together. I’ve also shown that there is atleast one case which applies to every map that produces an endless output of zeros. Which shows that you cannot just randomly select two maps and two starting points, you have to perform a check. This takes us from no checks into one check, but it in no way rules out the further as yet unknown possibly heading for what seams like an infinite number of checks.

I’ve indicated but not proved that we should expect to see atleast a run length of double the maximum bound for a single map or for that matter a series chain of maps (think 3DES in CTR mode as an example). What I have not shown nore even proved –except for one degenerate example– is if the XOR of two or more map outputs actually has an upper bound on repeted patterns shorter than the expected repeated time of (2^N)^2.

Which brings us around to why I consider a doubling of a zero or other pattern run length degenerate.

It’s because the context of the use of the output of this XOR of maps generator is to be used directly as a “Real world One Time Pad” without human or other inspection between generation and actual use.

Look at it this way the single AES128 bit map can only produce a maximum run length of just under 3/8ths of a K of fixed pattern. This means that with a plain text alphabet of 2^5bits size like Baudot 75 charecters would be either visable as is or XORed under a repeating pattern. With the two or more XORed map generator this would be somewhere between 150 or all charecters going out to the world sight unseen in clear text or XORed under a repeating pattern. Almost the first automatic test a cryptographer does on an unknown cipher text is check for XOR under a repeating key…

Thus in this context of talking about OTPs for real world use, any generator that can increase the length of a pattern is degenerate when compared to one that does not.

When generating real world OTPs the practice is generally to stop any run lengths of more than a “word” in size of the plaintext alphabet, where the definition of a word is that specified by the ITU, of five charecters. Thus with 5bit Baudot you would be looking at a run length of no more than 25bits, and 35bits with 7bit ASCII.

The real problem however is not the maximum run length but how you would check and reduce the length from your generator without upsetting the overall statistics of the pad…

Anura • September 5, 2014 11:59 AM

@Steve B

Sorry, I was writing a quick note late at night when I was pretty tired. What I’m proposing has little to do with CBC mode itself, it’s purely about obscuring the plaintext with truly random data to render most attacks against the cipher significantly more difficult or impossible to perform, at the cost of doubling the length of the ciphertext.

Generate two IVs equal to the block length, IV₀ and IV₁

Compute r₀ = LEFTHALF(ENC(IV₀))

Pad the message M to a multiple of one half of the block size, and break up into n chunks, each equal to half the block size (m₁ through m_n).

Prepend each message chunk m_i with random data of equal length, r_i, and XOR the message chunk with the previous chunk of random data: p_i = r_i || (m_i ^ r_i-1).

P = p₁ || p₂ || … || p_n

Then encrypt the data: ENC-CBC(IV₁, P)

Again, the purpose is not to try to increase the keyspace, the purpose is simply to provide better resistance to known plaintext attacks by reducing the knowledge of the attacker. You don’t actually need two IVs, now that I think about it a bit more, just use r₀ = LEFTHALF(DEC(IV₁)) – just like with CBC or CFB mode, the IV simply acts as if it was the first block of the message.

Steve B • September 5, 2014 1:19 PM

@ Clive said:
“The real problem however is not the maximum run length but how you would check and reduce the length from your generator without upsetting the overall statistics of the pad.”

Indeed, I was thinking the same thing.

From an information theoric point of view, any deviation from a pure random distribution should actually start to degrade the security of the system, not improve it (though that would be difficult to explain to a general who sees words like “attack” leaking into his cipher text encrypted messages).

The Enigma cipher in WW2 was broken in large part EXACTLY because of a similar weakness; No letter in the Enigma cipher ever encrypted to itself, and therefor the cipher differed from a truly random permutation. Enigma used a continuously changing permutation that mathematically would be hard to break even today were it not for that one flaw.

Ironically, the no-letter-encrypting-to-itself flaw resulted from a unique patented feature of the Enigma design that it’s creators were apparently quite proud of; namely its ‘reflector’ design; which had the desirable feature of making the machine swap letter pairs so the exact same cipher process could be used for encryption and decryption, but which required that each of the rotors that acted as Enigmas ‘s-boxes’ be wired as a derangement, which is a degenerate form of permutation where no letter could be swapped with itself.

Thank goodness that no one today would be stupid enough to design a cipher with a s-box permutation that is a derangement, because then in every cipher round the S-Box function would leak the same kind of “can’t get there from here” information, that lead to the Enigma’s downfall.

Yep, it’s sure great that we learned our lesson from Enigma, and no one would be that dumb these days … Oh, wait a minute! Just remembered something… Isn’t the AES S-Box permutation a fixed derangement where no 8 bit input value can EVER permute to the same value? – Ooops!

Anura • September 5, 2014 2:39 PM

@Steve B

Isn’t the AES S-Box permutation a fixed derangement where no 8 bit input value can EVER permute to the same value? – Ooops!

Ehh, that’s not really a problem. What happens immediately before the Sbox? An XOR operation to a subkey. Given any bijective, nxn bit function f, there exists a value a such that x = f(x^a) for every x.

Steve B • September 5, 2014 8:48 PM

@Anura said:
Given any bijective, nxn bit function f, there exists a value a such that x = f(x^a) for every x

Yes, using exclusive or, we can change any value to any other value.

The XOR operations you speak of are based on bits derived from a key expansion performed using the SAME flawed S-Box, leaving the possibility that this S-Box arrangement is part of the technique the NSA used to insert a back door in AES by creating a subtle interaction between the key schedule rounds and the cipher decryption rounds which allows the NSA to crack the cipher at will.

To do this they would use a round by round iterative key search, which takes advantage of interactions between the derangement permutation in the S-Boxes used in both key scheduling and encryption rounds using something like Turing,s ‘don’t eat fruit of the poison tree’ technique. In this algorithm, you set up some assumptions (which could be random guesses) then continue to add additional guesses until something doesn’t match, then prune the whole tree. The advantage of this technique is that by quickly pruning away all the can’t-be-correct assumptions it zeros in on the remaining correct answer in something like sqrt O^^(n/2) time. If the this is possible, you could search through a full 2^128 keyspace with 2^64 effort. For this type of shortcut algorithm to work though, you need conditions where the falsehood of a given state ‘X’ in the assumption tree excludes all the previous others as well – Which I suspect may be exactly what the oh-so-carfully contrived mathematical structure of AES was designed to allow.

Anura • September 5, 2014 10:50 PM

@Steve B

In the key schedule a constant is XORd, which allows x to map to x.

There are bigger concerns with AES than that. How about that with a probability of 1020/4228250626, if you change all 4 bytes in one input word, only one byte will change after the first round. If only one byte changes in the first round, exactly four bytes change in the second round, and exactly 16 bytes change in the third round. It isn’t until the fourth round that that probability goes away. By changing all four bytes of one input word, you also have a higher probability (which I can’t be bothered to consider how to compute, but it’s pretty small, although higher than it should be if it was random) that after the fourth round exactly four bytes will have changed in such a way that at the end of the fifth round only one byte will have changed.

Steve B • September 7, 2014 12:03 AM

@Anura

… What I’m proposing has little to do with CBC mode itself, it’s purely about obscuring the plaintext with truly random data to render most attacks against the cipher significantly more difficult or impossible to perform, at the cost of doubling the length of the ciphertext.

Thank you for the detailed response. I think I have it now, thanks.

Actually, I believe your method will significantly enhance security, because the block cipher’s diffusion insures that if someone can’t guess BOTH the truely RANDOM value you are appending in each block AND the cipher’s secure KEY then they see only garbage. So if you were using 64 bit random values with AES the total effective key length is 192 bits for AES128 and and 320 bits for AES256.

The method I proposed has about the same 2:1 time penalty, but does not have the 2:1 space penalty, and potentially could add even more to the security of the combined cipher.

That method is to hide a strong CBC block cipher under a second layer of encryption, and keep the IV secret. In this approach, the first block of the first layer cipher is literally encrypting in OTP mode, which insures the security of that block, and since the second layer of encryption hides the ciphertext output from that first block, which in turn is used as the IV for the second block, we can’t gain a starting point to break that block either… and so on, and so on, for ALL the remaining block.

This works because that first block is REALLY encrypted using the IV as a One Time Pad. — not some cheesy ‘psudo-OTP’– or ‘virtual OTP’,– or shake-oil OTP, it’s LITERALLY a One Time Pad – because if you keep the IV secret, then XOR combine that IV with your plaintext before encryption – you have just created a true one time pad (at least for that first 128 bit block) – and all the cryptanalysis in the universe can’t recover that first block by any method better than pure guesswork – it is absolutely secure in an information theoric sense.

So don’t underestimate a strong block cipher in CBC mode with secret IV, double encrypted under a second strong, but unrelated cipher.

So tallying things up security wise, with the adversary left to guess, potentially two 256 bit cipher keys – PLUS a 128 bit secret IV, the total effective key approaches 640 bits.

Which may not be ‘unconditionally secure’ – but should be good enough in any practical sense.

Patriot • August 9, 2019 4:10 AM

I have tried to do a bit of research and writing on this issue, which can be found here.

Schneier on Security

The History of One-Time Pads and the Origins of SIGABA

Comments

Leave a comment Cancel reply