"Unbreakable" Encryption Almost Certainly Isn't
schneier.com
schneier.com
Maybe this is just a problem of imprecise language and reporting, but when has the ability to generate an unlimited number of keys ever been the main problem? I always thought the problem was distributing/maintaining such a number of keys, and to a lesser extent, generating those keys in a reasonable amount of time.
Because wasn't "unbreakable" encryption invented a long time ago, and implemented successfully since? That is, one-time pads, which are theoretically unbreakable by anyone who is not omniscient? Of course, the problem of distributing and maintaining such keys gets in the way of popular implementation...
edit: I'm obviously not suggesting that one-time pads have solved much of anything...just that, why do researchers brag about creating an infinite number of keys, or even "unbreakable" encryption, when those don't seem to be much of a real-world problem...Maybe in this case it's just bad reporting and translation of researcher-speak. Now, extremely-unfeasible-to-break while feasible-to-use...that's clearly worth bragging about.
To generate some funding and impress gullible people? It is like unlimited energy or flying car projects.
For symmetric key ciphers, the keys are of a set length. AES accepts key lengths of 128, 192, and 256 bits.
For asymmetric ciphers, they vary even more. The RSA-XXXX designation refers to the length of n, which is the product of two primes (which must be kept secret) p and q. So for RSA-2048, p and q are roughly 1024-bit numbers. In addition, the secret exponent can frequently be quite large, although as it's calculated from the public key exponent and n its size is not guaranteed.
Ultimately however, all of these are designed so that the key spaces are too large to be feasibly brute-forced searched. The reason for the much larger size of the keys for the asymmetric ciphers is that their security is usually based on the difficulty of solving a problem (in RSA's case, factoring n into p and q, or the equally difficult problem of determining the totient of n) that gets more difficult as the keys get larger.
EDIT: And yes, one-time pads are theoretically unbreakable, however they can only be used once (as the name implies, but if they are used twice recovering the key is trivial), must rely on a sufficently good quality random number generator (which Matt Green recently had a very good article describing how hard it is to do: http://blog.cryptographyengineering.com/2014/03/how-do-you-k...) and they have the same issues that any symmetric key ciphers have, in terms of key distribution. They're useful when you have old women in Bletchley Park spinning bingo balls and carefully copying into two notebooks. Less so when you're trying to build a usable system for secure communication.
Well, they did. Think about various secret channels between governments, like the Washington D.C. - Moscow line.
Size of the key space only really matters when the only known attacks have a time complexity proportional to the size of the key space, i.e. brute force.
If the algorithm itself is horribly broken then it doesn't matter much. For example, a monoalphabetic substitition cipher actually has a rather large key space (26!) but this doesn't really matter.
Taking a look at the paper and a stream of thought about it.
- Researchers are affiliated with a university they aren't kooks
- These are physicists. They speak a different language. That will make decoding this paper difficult. It may have useful insight, but it is obscured by the jargon of a different discipline. Typically I haven't see continuous diffeq in crypto. >.>
- Essentially I believe this is a two-directional stream cipher, with prior clear?crypt?text from both sides feeding into the input.
- I'm not sure what unbounded precisely is being meant here with their coupling function.
- Almost zero crypto papers cited (I counted two, and they sounded fringe-y by title and were also published in physics journals).
Several key aspects have been neglected by the authors:
- Lack of citation of the current state of crypto- they betray nearly no understanding of the terminology of crypto nor present the contribution to the field in relation to the field.
- No analysis of the information-theoretic leakage of the communication system.
- No analysis of keyspaces, expected break time for chosen|known ciphertext, etc.
My take on it is that it's a well-intentioned but largely useless paper by non-experts. If they took the time to understand the field, it might have some valuable insights.
I would guess the coupling function as an idea results in a system design that leaks information like a sieve about both Alice and Bob. It might be a restatement of something like switching keys periodically, but I lack the vocab to interpret.
http://www.pro-technix.com/information/crypto/pages/vernam_b...
The biggest problem in this mechanism is how does the other party get their one-time pad? An upper bound on the unbreakableness of the entire scheme is the unbreakability of transmitting a one-time pad; and if you can do that, then why not just send the actual message via that mechanism?
1. http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
suppose you can transmit information securely only for some time. Exchange one time pads ahead of time, and use them later to communicate over insecure channel
My only point was that talking about one-time-pads as "unbreakable" encryption is not a useful discussion, since "unbreakable" and "encryption" need to be better defined.
If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system.
Only by explicitly defining attack vectors can we really get a good framework for reasoning about cryptography, and even then we know that we can prove an encryption technique is bad. For "goodness", all we can do is increase our confidence, until the day the confidence drops to 0.
Anyway, with this last salvo, I'll retreat from this conversation; it's pretty clear to me that my inane ramblings about semantics are as annoying to the community here as they are to me when other people make them.
No they don't. You are receiving negative feedback because you are trying to adjust definitions that have been well-defined by the crypto community. When talking about the security of an encryption algorithm, the key distribution has absolutely nothing to do with it. Stop conflating the two.
>If we expand the definition of "encryption scheme" sufficiently to allow transmission of secrets outside of cryptographic channels, then OTP is not even close to the only unbreakable system.
Would you care to share with us some of these other unbreakable systems? Remember, the keys are the only thing that can be transmitted outside of the channel and they cannot be based on the information being encrypted.
Any scheme which allows sharing arbitrary amounts of random information is less than or equally secure as an OTP (security defined per symbol) since OTP reveals no information per symbol; also, it uses the minimum amount shared information to do so, provided your symbols are equiprobable.
Technically, either of these could be slightly more secure, in that they need not leak the length of the plaintext. For transmitting a single "yes" vs. "no" answer, that could be a fatal attack vector for a naive OTP.
Now for 1,2,10 years depending on your rate of communication you can communicate using the one time pad.
>why not just send the actual message via that mechanism?
The point is you only have to exchange pads periodically, not every time you communicate.
I wouldn't trust some keys that had been lying around on an unencrypted hard drive for 1,2,10 years!
In real-world implementations I think the security is probably based around a large number of men with guns.
Nit: I would consider one time pad to be a method of encryption.
Ah, true. But the encryption algorithm is much simpler to implement than most :-)
My problem is just that the proposed mechanism relies on already having an even more perfect mechanism, and thus cannot be the "only one", but is in fact strictly weaker than this other mechanism. So we have a contradiction, and we can get rid of the notion that there exists such a thing as an "unbreakable" system (or, alternatively, that it is a useful concept)
It is the good standard for crypto systems. Yes it's unworkable in practice but that's exactly why nobody really uses it. It is useful for teaching and making comparisons.
Before you send your submarine to sea for example, you can provide them with many gigabytes of one time pad. They can then use this for their most secret communication.
This is pretty powerful. It means that organization which and periodically move physical assets securely can send information in a manner that is secure even if quantum computers reach their full potential.
Incidentally, the mechanism for sharing the pad doesn't have to be 100% secure, as long as you can reliably detect any compromises. If someone opens the briefcase while it's in transit, you just generate new pads and send another briefcase. To compromise the system, an adversary has to compromise the pad in transit without being detected.
Lots of SSL sessions are going on right now. It only takes a vulnerability like CVE-2014-0160 to change the score by 100 or so.
Briefcases: 1 in the last day
SSL sessions: 100 in the last day
Edit: if only CVE-2014-0160 had some evocative name.
If you can, then there's no real need for using a one-time pad. But there's a benefit that comes from a fact that exchanging the random data is a completely separate process in time and space from sending the messages. You can do it once, spending all your resources to secure it. Imagine e.g. two governments establishing a secret emergency line by generating a few terabytes of random data in one physical place and then escorting each copy in armoured trucks to proper communication factilities.
BTW. exchanging physical "XOR's" for one-time pad communication is a plot point of Vernor Vinge's "A Fire Upon the Deep".
There is a more general point here, that sometimes seems to be lost in philosophical arguments: reality doesn't pay any attention to the meaning of words. If "unbreakable" is not well-defined (I am not sure that is so), then it is a problem within the domain of language, not cryptography.
The known solution to this is to pad messages to some fixed length. The obvious drawback is that you have to choose the fixed length message to be as long as the longest message you may wish to transmit, which could result in having to transmit rather a lot of padding.
The equivalent of this for real-time communications is to transmit continually at a fixed bit rate regardless of whether you have any data to send at any given time.
Send random data that is probably meaningless, until which point you send real data. Let everyone listen in to the gibberish for 50 years, in the end, only the person with the key knows the message.
For example I may be able to send you a one-time pad securely today, but the message I need to tell you ("buy GM stock at 37.82") I won't know until next week -- at which point I may not be able to expediently send you the one-time pad securely.
A lot of problems in cryptosystems stem from implementation details - think side-channel attacks, exploits, ...
...we're not on the modern Internet. I'm looking forward to it; it'll be a better place.
Don't ask me how Cold War-era NSA discovered that without Cray supercomputers everywhere, but even this scheme is difficult to pull off in practice.
Every encryption scheme is based on the assumption "X is not solvable in polynomial time", for some problem X. Don't start by wasting time with details of the scheme. Start by telling me X.
Common examples of X are factoring and discrete log. More exotic ones include e.g. [1], the types of assumptions underlying fully homomorphic encryption. In the case of this bio paper, cryptographers won't care unless the authors can succinctly describe:
1. The computational problem that needs to be solved to break their scheme.
2. The relationship of this computational problem to well-known ones (can it be reduced to factoring? To computing some difficult integral?).
3. Evidence to suggest this problem is difficult (can factoring be reduced to it? Or some other hard problem?).
"The 'best cryptographers around' break a lot of ciphers. The academic literature is littered with the carcasses of ciphers broken by their analyses."
Possible defenses against rubber hose cryptanalysis on your one time pads include:
Perfect forward secrecy and plausible deniability
Hidden hard drives within hard drives within hard drives http://www.truecrypt.org/
Being dead http://www.cracked.com/article_20110_5-secret-languages-that...
Quantum mechanics http://en.m.wikipedia.org/wiki/Quantum_key_distribution
What data type would you use to store such a key? My guess is that it wouldn't be much bigger than 2048 bits after being implemented. Besides, key length is a terrible metric for measuring security.
The fact they're not using the term "keystream" for this concept is a bit of a warning that they might've reinvented something every cipher algo already does, but more inefficient (from skimming through the paper).
Just guessing though. Not judging. I'm not a cryptographer, I just read about crypto as a hobby (and to know what I'm doing while using someone else's crypto primitives in my code).
Whether this is any improvement on existing ciphers (which you can also design to have any size key you desire), is less clear, but I would bet on 'no'.
anyone can create a cryptosystem that he himself cannot break
It's amazing how many times a lack of knowing this axiom becomes a problem / surprise.
> Algorithms posted to Internet newsgroups by unknowns won't get a second glance.
It seems to me this would not be true of Bitcoin.