Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

RSA, DES, AES, etc. all use (relatively) complicated mathematics to encrypt some message with some key. For each of these methods, there have been several documented vulnerabilities found over the years. Some even believe that there is a vulnerability in AES known only to the NSA.

On the other hand, the One-time pad is not only ridiculously simple, but also has been shown to be impossible to crack (if used appropriately).

Say you have some message to be encrypted with length n. Simply generate a random string with length m where m is at least as large as n, and perform modular addition of the random string onto the message.

As long as the random string is generated with a high-enough quality random number generator, and as long as the same one-time pad isn't use on multiple messages, it should be impossible to crack.

If this is true, all we would need to perfect are fast, cryptographically secure deterministic random number generators. Use the key as a starting seed for the RNG and you have a powerful uncrackable encryption scheme which is simple to understand and implement.

Blum-Blum-Shub is a fast, cryptographically secure PRNG, and there are others too.

I have written a C++ program which uses two 2048-bit primes (which match the necessary criteria) for Blum-Blum-Shub and uses a password which the user enters - converted into a starting seed - to run byte-wise modular addition. The process is fast, deterministic, and if the literature I have read is correct then it should be very secure.

So why is so much time and effort invested in coming up with convoluted encryption cyphers when mathematics shows that the simplest is often the best?

share|improve this question

migrated from math.stackexchange.com Sep 2 '11 at 23:42

This question came from our site for people studying math at any level and professionals in related fields.

40  
What you describe is not called a one-time pad. It is called a stream cipher. –  Jack Schmidt Sep 2 '11 at 3:40
10  
AES is much faster than your Blum-Blum-Shub setup. –  starblue Sep 2 '11 at 7:40
10  
RSA is just as simple as BBS. –  Dan Brumleve Sep 2 '11 at 7:41
1  
Modern crypto is needlessly complicated; but not because of the (simple) primitives like RSA, DES, and AES. It's universality composability and ZKPs that are the problem. –  Fixee Sep 4 '11 at 21:03
    
in addition to all the good answers: "m (key size) is at least as large as n (message size)". This is a not a problem specific to the OTP. Consider a message with a size of 1GB (e.g. videos) - so the overall size would be at least 2 GB. This is not practical at all. –  mkind Jan 15 '13 at 8:23

11 Answers 11

up vote 95 down vote accepted

The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on a one-time-pad for use.

If we have a secure channel to communicate so we can agree on a one-time-pad, then why bother? Let's just communicate through the secure channel.

If we don't have a secure channel, then we cannot engage in secret communication ex-nihilo, since we will not have a one-time-pad agreed on.

Now, if you are going to generate the one-time-pad via a pseudo-random number generator, how are you going to get that one-time pad to me? You must tell me your seed (so that I can generate the same pseudo-random sequence and I can decode the message), in which case we are back to the problem of how you tell me what your seed is without a secure channel to communicate with. So now we have two points of vulnerability: the channel we use to communicate so you can give me the seed; and the fact that a pseudo-random number generator is not truly a random number generator, and so may be susceptible to attack as well.

There is also the problem of distribution; to use one-time pads effectively, no pad can be used more than once. There were intercepts that the NSA had from back in the 50s; when the Soviets mistakenly used the same one-time-pads to encode some messages in the 80s, this was enough to break the encryption in both cases. That means that each message will need a new seed and a new password; so each time you want to communicate you need a new seed/key and a new password. It is just too easy to lose the information, or to re-use it by mistake and thus make the entire thing a wash.

One time pads are effective for pre-established channels of communication with low bandwidth; they are almost useless for initiating remote secret communication with someone you have never communicated with before, and they require a lot of bandwidth to use correctly.

share|improve this answer
11  
This goes towards a larger point: cryptography is hard, and there are many issues to consider, even before looking at algorithmic vulnerabilities. There are implementation issues (not reusing one time pads, making proper key choices, not storing private keys on a hackable server), in addition to any vulnerabilities your algorithm has. People think AES is fairly secure is because many smart people have spent a lot of effort looking for vulnerabilities. They might find a huge hole tomorrow. Rolling your own crypto is a risk, because you don't know the vulnerabilities until someone finds them. –  Aaron Sep 2 '11 at 3:57
8  
I have read that the literature is filled with articles (by serious security researchers) where someone introduces a new crypto system, and then, three months later, they publish a vulnerability that they found in their own system. It is very easy to make bad systems that aren't obviously bad. The most dangerous form of security is the kind that offers no protection but makes you confident that you are safe, and the problem with cryptography is that the people who want to crack your system often won't tell you when they have. –  Aaron Sep 2 '11 at 4:03
5  
This answer can be summed up as: key distribution is hard. While true, that does not relate to the question, which asks why we use AES over the simpler and more secure Blum-blum-shub for encryption. The question actually has nothing to do with one-time pads. –  BlueRaja - Danny Pflughoeft Sep 2 '11 at 12:23
1  
@BlueRaja - Danny Pflughoeft: Does too: see question's paragraph #7 ("used keys: two primes and a password"), contrast answer's paragraph #4 ("how do you get the password over to the other party?"). –  Piskvor Sep 2 '11 at 13:17
2  
@BlueRaja: The same AES key can be used repeatedly without compromising the system. The same OTP (or OTP seed) cannot be used repeatedly without compromising the system. Distributing the AES key is a one-time cost. Distributing the OTP (or OTP seed) must be done for every message and so is impractical for most uses. OTP is still very useful for certain problems and is still used for those cases. –  Rob Napier Sep 2 '11 at 17:27

For symmetric encryption algorithms, your question is basically "Why do we use AES or DES rather than another function that provides the same properties as AES or DES but forces us to use the second weakest chaining mode and never lets us use the same key twice?" Well, the answer is obvious, we sometimes want strong chaining modes and we often like to use the same key twice.

For asymmetric encryption algorithms, your question is basically "Why do we use asymmetric encryption when symmetric encryption is simpler and faster?" And the answer is that we can't always pre-arrange a key between the two ends. For example, when I go to Amazon's secure web page for the first time, there's no way Amazon and I can arrange an encryption key that only Amazon and I know. And we certainly would find it difficult to work out a new secure key each time.

Also, sometimes we need to exchange data securely with parties we don't trust, and your mechanism won't do that. If I publish the key in the New York Times so anyone can send me something securely, anyone can decode the messages too. Yuck. And if I want to talk securely to 15,000 people, I need to manage 15,000 keys. Yuck. And if I share a key with 50,000 parties and change it, I need to get the new key to 50,000 parties. Yuck.

And, by the way, this is not a one-time pad. It's a stream cipher similar to RC4.

share|improve this answer

There is a theorem in cryptography that states that secure encryption and secure PRNG are equivalent, and in fact you just proved half of it.

Given a secure PRNG, you can create a secure encryption algorithm using the method you just provided (using the key as the PRNG-seed). The other half is that given a secure encryption algorithm, you can create a secure PRNG by simply encrypting successive integers (using the seed as the key).

This is one method - the most common method - of creating a stream cipher (note that this is not the same as a one-time pad, which requires the key to be truly random, as large as the input, and known to both parties ahead of time)


The cryptographic PRNG that you mentioned, Blum-Blum-Shub, has an unusually strong proof of its security - as long as factoring numbers is hard (we believe that it is), breaking BBS is hard. We don't have the same sort of confidence with AES; there is no proof of security for AES or most other block-ciphers. The only reason we have to believe that it's secure is that, despite lots of smart people trying, no one has ever been able to put a reasonable dent in its security.

So if BBS is known/believed to be so much more secure than AES, why would AES be so much more prevalent? There's only one reason:

Speed.

Despite what you said, BBS is slow. Damned slow. Extremely, ridiculously, painfully slow. The difference in speed between AES and BBS for encryption is several orders of magnitude, a huge and unacceptable difference. Sure, your computer may be able to encrypt a large message in a fraction of a second, but what about a cell-phone? What about a web-server that needs to handle thousands of TLS/SSL requests a second? What about encryption software that needs to encrypt gigabytes of data at a time (every iteration of BBS only produces one bit of psuedo-random data)? The point is, speed is important, and though AES has no security-proof, it's believed to be "secure enough."

Speed is also the reason AES is used over RSA in TLS/SSL: when connecting to a webserver, your computer will use RSA (or similar) initially to transfer a random key, after which that key is used by AES (or similar) to encrypt all communication, simply because AES is so much faster.


As a side-note, both RSA and BBS use the same "complicated mathematics" (modular arithmetic), but block-ciphers such as AES and DES do not use any "complicated mathematics" at all - you can easily fully understand AES without any mathematical background whatsoever.

share|improve this answer
1  
...and to add another example: BBS's speed would not be suitable for the purpose of securing Wi-Fi connections. AES (okay fine, CCMP) however works nicely. (And let's please not speak of WEP. ;)) –  J. M. Sep 2 '11 at 12:14
2  
BTW: thanks for the blog post link! I'll have something to share the next time somebody asks me about this... –  J. M. Sep 2 '11 at 12:25
2  
AES is not a stream cipher; it's a block cipher. It can be used as a stream cipher in counter mode, but it's not inherently one. –  Henning Makholm Sep 2 '11 at 13:36
2  
@blueraja-danny-pflughoeft: 1024 bit RSA seems to be a bit too small to replace 256 bits of AES. 16Kib would be more suitable (try to create a 16Ki bit key pair on your PC, just for fun). –  owlstead Feb 23 '12 at 22:26
2  
You seem to have a weird definition of "full understanding". IMO even its designers don't come anywhere close to fully understanding it. For example for basic understanding AES s-boxes, you need to understand binary finite fields. You need to understand how differential works, why there are no simple formulas that can solve AES for the key,... Even basic understanding of AES requires a lot of study. As a practical example consider the NSA tweak to DES. Cryptographers needed decades to understand that simple tweak. If you don't understand the consequences of that tweak, you don't understand DES –  CodesInChaos Sep 26 '13 at 18:18

There is a very easy reason why one-time pads are not always used. It requires information sent before the encryption is set up, i.e. both the sender and the recipient need to have access to the pads themselves. That's a big pain, especially if all information was to be sent with one time pads. How would one distribute the pads themselves?

There is also a second reason. Methods like RSA allow people new to a scheme to participate without any delay. That is, if I want to send someone a message securely with RSA, it only takes their preparation in creating a key. And then it is a key that anyone can use to send secure information.

Related to this idea is the idea that with the aforementioned techniques, a key can be reused. With a one-time pad, every bit of information must be accompanied by a bit of a random number. This means that long messages require long random numbers. One should never reuse a one-time pad. It is not very feasible to generate and store such incredible amounts of data as can ever be transferred between two people, especially since every pair of people who wish to communicate would need their own sets of pads. Explosive growth in memory requirements.

share|improve this answer

Modern encryption is not unnecessarily complicated -- it is necessarily complicated. Believe me, a lot of effort is put into making cryptographic algorithms and protocols as simple as possible. But "as simple as possible" is not the same as "simple".

share|improve this answer
    
Right. And what Voltaire failed to understand was that "the best of all possible worlds" does not mean "a good world". –  Mike Jones Sep 2 '11 at 14:04
1  
Dear @Mike, that's an interesting point. Voltaire certainly wanted to make fun of Leibniz in Candide, but I wonder if he didn't write in perfectly bad faith, since one certainty we can have is that he definitely was no fool... –  Georges Elencwajg Sep 2 '11 at 14:40
2  
A lot of modern crypto is unnecessarily complicated. X509, TLS,... –  CodesInChaos Jul 28 '12 at 8:51
    
Agreed 100% with CodesInChaos. I've spent countless hours studying X.509 only to find out that it's complete bureaucratic BS. I could have spent this time studying more relevant things such as actual cryptography. –  Longpoke Mar 18 '13 at 1:05

One time pads seems simple but have extremely strict requirements to guarantee information security. You're basically just shifting the complication into a random number generator because a good one-time pad must be absolutely random. Moreover, the same one-time pad (which in your scheme means password) cannot be used for two different encryptions.

share|improve this answer

A mathematician studying cryptography would be truly dumbfounded by this question.

You're completely ignoring the key-distribution problem and authentication-identity problems, both of which use public-key cryptography such as RSA.

Finding a large random source for a truly-secure OTP is tremendously difficult. You're talking about generating cryptographically secure random numbers, which are easily distributable (somehow?), in the magnitudinal quantities of information that the internet generates. Simply not possible.

share|improve this answer
1  
The op's use of the word simply in the sentence "Simply generate a random string with length m where m is at least as large as n," made me laugh. :-) –  DanBeale Sep 2 '11 at 16:30

A few people have already talked about some of the problems. Let me add one that I haven't seen mentioned: despite being unbreakable in the conventional sense, a one-time pad is not entirely immune to all attacks (even when used perfectly).

Consider an election system using a one-time pad. It's being used for a primary election. I'm a member of another political party, doing my nefarious best to sabotage this election. Let me list a few assumptions:

  1. I can change data in a ballot.
  2. I know which bits in a stream represent what parts of the ballot.
  3. The votes are represented as a vector of bits, with one bit for each candidate. For an obvious possibility, a bit is set to 1 to represent the candidate being voted for, and the others are set to 0.
  4. For the election I really care about, there are only two candidates.

Despite its "perfect" security, the OTP provides little real protection in this case. Even though I can't decrypt the data and know which candidate was voted for on any particular ballot, I can still blindly flip both bits representing the vote for the candidate in the election I care about. Voila, I've changed every vote, so the candidate who was less popular wins that primary election.

Then, in the secondary election, "my" candidate is running against the weaker candidate from the opposing party. People from that party who voted against that candidate in the primary a (somewhat) more likely to vote against him again in the secondary. My candidate may not pick up all of those votes, but even the ones who don't vote for my candidate are likely to be fragmented by the inability to vote for the candidate they really wanted.

Assuming my candidate had any chance at all in a fair election, this manipulation probably gives him a big win -- all without 1. doing anything at all in an election where he was a candidate, or 2. ever even trying to decrypt the original data.

There's another obvious variant where I (for example) only modify one of the bits in a particular election. This will generally either show up as an invalid ballot (the voter appears to have voted in favor of two different candidates) or a non-vote (I've changed the only set bit to a zero, so all the bits are now zeros, indicating that this voter didn't vote on this particular position at all).

share|improve this answer

Although one might argue that RSA and AES are based on "complicated" mathematics (RSA uses basic facts from number theory, AES uses some finite fields), DES doesn't have any complicated mathematics at all.

All three of these primitives, RSA, AES and DES, have never been broken.

Yes, one-time pad is mathematically simpler and has information-theoretic security, but as other respondents have noted, it's useless without a key distribution method, and these usually land you right back where you started, essentially.

BBS has "complicated" mathematics at its heart as well: it's using quadratic residues modulo a Blum integer $n$ so that every square has exactly one square root modulo $n$. The math here is at least as complicated as RSA, and far less practical.

share|improve this answer
    
Well, DES is regarded as broken in the fact that its key is now short enough for someone with good computing power to find... 3DES is quite a bit harder, but I think not impossible. 128 bit keys, AFAIK, are beyond current computing power, and 256 bit keys are un-bruteforcable. –  Ivo Sep 27 '11 at 10:54
    
@Ivo: DES was regarded as "broken" upon release (due to key length); 3DES is still secure (but painfully slow); if you know an attack, please post it. 3DES has an effective key length of at least 110 bits. When I said that DES has never been broken, I mean the construction, not the parameter set. –  Fixee Sep 27 '11 at 16:03

… One-time pad is not only ridiculously simple, but also has been shown to be impossible to crack (if used appropriately). …

One-time-pads may provide ideal security, but they are awfully problematic to transport securely from one point to another. Considdering that an OTP should only be used once, makes OTPs even more impractical. That makes exchanging messages which are secured using OTP needlessly complicated.

When you ask if modern encryption is needlessly complicated and point to OTPs, my primal instinct is to reply that – compared to modern cryptographic algorithms – using OTP is needlessly complicated.

… Blum-Blum-Shub is a fast, cryptographically secure PRNG, and there are others too. …

Blum-Blum-Shub may be somewhat secure, but it is anything but fast.

… The process is fast, deterministic, and if the literature I have read is correct then it should be very secure.

The problem starts and stops with the word “deterministic“. A deterministic encryption scheme always produces the same ciphertext for a given key and plaintext, even over separate executions of the encryption algorithm. Keeping it short: deterministic encryption can leak information to an eavesdropper, who may recognize known ciphertexts. Keep in mind that deterministic encryption schemes can never be semantically secure. That’s one of the reasons I personally would only consider using deterministic encryption if there’s a need to efficiently search encrypted data.

… So why is so much time and effort invested in coming up with convoluted encryption cyphers when mathematics shows that the simplest is often the best? …

Don’t get me wrong, but people invest so much time and effort because they aim for a higher security compared to your self-made thingy. In the end, there are too many Security Pitfalls in Cryptography to try to do things “simple”. To protect against those security pitfalls requires smart and sometimes complicated solutions. That is the reasons why you might get the impression modern encryption is complicated. But you can trust in the fact that no cryptographer would make it “needlessly” complicated because that might raise the potential of introducing additional security issues.

share|improve this answer

You are right One Time Pad with Blum Blum Shub are the most secure proofed ciphers combine. But you just forgot the main problem: Key Exchange problem and One Time Pad key should be used once, and here asymmetric (RSA;DH) ciphers with AES solve this problem.

But, again Key Exchange problem for one time pad is solved with quantum cryptography. Many companies such as IdQuatic, MagicQ had developed, real random generators devices (PCI) and routers that support quantum cryptography. The main limit for the moment of quantum cryptography is distance coverage (experiments has shown it is effective till 100 km). Lately have been made some experiments of quantum bit exchange on optic fibber showing good results.... Hope this short description helps.

share|improve this answer
1  
Quantum crypto does not solve the key exchange problem. It just solves the problem of securely stretching a short symmetric key into a one time pad i.e. at best it's a secure stream cipher with additional limitations. Pretty much everything interesting is outside its abilities. So IMO quantum crypto is one of the most useless things ever. –  CodesInChaos May 22 '12 at 21:03
    
It not true at all. Quantum crypto solves the key exchange problem (and all problem related to classic crypto). I am not going to give more detail because is long, but quantum interference and quantum qbit teleport make sure that. Quantum Crypto was my bachelor thesis degree, I have studied it BB84 and E91 protocols are secure. –  albanx May 23 '12 at 6:49
    
What's the equivalent of public key crypto in QC? All protocols I learned about in my quantum information courses require a shared symmetric secret prior to communication(or a second classical channel where the attacker is only a passive listener, not an active MitM), and that's just a requirement that doesn't work in practice. You're right that QC protocols are secure. But their scope is so limited that they're useless in practice. –  CodesInChaos May 23 '12 at 6:58
    
shortly QC protocolls (bb84, E91...) are used to generate and exchange the shared symetric key(truly random key as long as wanted), instead of of public key crypto. Then this key is used in classic channel with one time pad for communication. There are places where this protocolls are used in practice. in vien 2004 there was the first QC transaction betwen two banks. Toshiba Research Europe applied the QC in 2005 in a video-voip trasmission.... –  albanx May 23 '12 at 9:54
    
The schemes I remember(which includes BB84) require a small symmetric secret shared beforehand to act as a MAC. Without a shared secret MitM is trivial. Distributing these secrets without public key crypto just doesn't scale. And of course simple live 1 to 1 communication is only one application of crypto. There are many other applications of crypto(hard-disk encryption, anonymous mixes, uploading encrypted files to untrusted storage providers, encrypted email which doesn't require sender and receiver to be online at the same time, digital signatures,...) none of which are even addressed by QC –  CodesInChaos May 23 '12 at 10:03

protected by Ninefingers May 22 '12 at 20:46

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.