7 ms·

"Unbreakable" Encryption Almost Certainly Isn't

59 points by prajjwal 13y ago

danso 13y ago
> The researchers, led by Dr. Tomislav Stankovski, created an encryption mechanism that can generate a truly unlimited number of keys, which they say vastly increases the security of the communication. To do so, they took inspiration from the anatomy of the human body. 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.
- rdtsc 13y ago
  > why do researchers brag about creating an infinite number of keys, or even "unbreakable" encryption, To generate some funding and impress gullible people? It is like unlimited energy or flying car projects.
  - deleted 13y ago
    [deleted]
- JackGibbs 13y ago
  For no encryption scheme is the key space unlimited. 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-know-if-rng-is-working.html 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.
- TeMPOraL 13y ago
  > I'm obviously not suggesting that one-time pads have solved much of anything Well, they did. Think about various secret channels between governments, like the Washington D.C. - Moscow line. http://en.wikipedia.org/wiki/One-time_pad#Historical_uses http://en.wikipedia.org/wiki/One-time_pad#Historical_uses
  - dghf 13y ago
    I read a novel by a former SAS soldier about a former SAS soldier who's sent on deniable operations by the British government, and who uses what is clearly a one-time pad to communicate with his handlers. The detailed description of the precise method used, the fact that the term "one-time pad" is never used, and the narrator's apparent lack of understanding of how exactly it works (encryption/decryption is done via modulo-10 addition/subtraction, which the narrator derisively refers to as "spook maths") suggest that the author himself, or a contact of his in the same circles, has used a very similar system for real.
- stygiansonic 13y ago
  From just reading the linked to article, (I have not read the full paper) it appears that the researcher has conflated the size of the key space with whether or not the encryption algorithm is secure. 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.
LukeWalsh 13y ago
There's only one "unbreakable" encryption, and that's a pair of one time pads with truly random data as long as the message itself. http://www.pro-technix.com/information/crypto/pages/vernam_base.html http://www.pro-technix.com/information/crypto/pages/vernam_b...
- andrewla 13y ago
  While this may seem like a tempting statement, it is not really an answer, since "unbreakable" is not really well-defined. Clearly, "truly random" is a bit of a tough one to define. And sending the message length is a bit of an information leak itself. But even putting those aside, there's a bigger flaw. 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?
  - nawitus 13y ago
    "unbreakable" may be not well-defined, but perfect secrecy is[1]. 1. http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
    - JackGibbs 13y ago
      Perfect secrecy refers to the ability to determine any information about the plaintext without decoding it. Not having it can be very useful to an attacker, but that isn't always the case. RSA, for instance, doesn't have perfect secrecy, because it leaks the Jacobi symbol (https://en.wikipedia.org/wiki/Jacobi_symbol https://en.wikipedia.org/wiki/Jacobi_symbol) of the plaintext. However, that information is of limited utility, and it can be shown that determining more useful facets, for instance the parity of the plaintext, requires solving more unfeasible problems.
      - darkmighty 13y ago
        Actually, perfect secrecy refers to the ability to determine any information about the plaintext at all, given arbitrary decoding power. It's quite simple -- it means that given a standard distribution of keys and an a priori distribution over the plain texts the best estimate of the plaintext given the ciphertext is simply the a priori distribution (no additional information). For the binary case, Y(any distribution)+X(uniform)=Z(uniform) (mod 2), so that this is satisfied for any prior.
hawkharris 13y ago
I love these two lines from Shneier's earlier article, the one he links to at the end: "The 'best cryptographers around' break a lot of ciphers. The academic literature is littered with the carcasses of ciphers broken by their analyses."
- a1a 13y ago
  Indeed. Related advice, also from Schneier: "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard."
ssdfsdf 13y ago
Seems like quite a good idea to me.
a1a 13y ago
"Truly unlimited number of keys" 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.
- mantrax4 13y ago
  It's typical for crypto algorithms to generate an endless (or extremely large) "keystream" by permutating a much shorter secret key with other data somehow. 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).
- rcxdude 13y ago
  It could be bigger. The 'keys' are just arbitrary sytems of equations, this is where 'unbounded keyspace' comes from. Any implementation would wind up being bounded by some practical constraint. 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'.
bo1024 13y ago
Theoretical cryptographers -- those who come up with new encryption schemes like the classics we rely on, e.g RSA and DH -- will take the following perspective: 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?). [1] http://en.wikipedia.org/wiki/Lattice-based_cryptography http://en.wikipedia.org/wiki/Lattice-based_cryptography
EGreg 13y ago
Although one-time pads are indeed unbreakable in a mathematical sense, in the real world everything is theoretically decipherable, in the end, using rubber-hose cryptanalysis and good timing. http://xkcd.com/538/ http://xkcd.com/538/ 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/ http://www.truecrypt.org/ Being dead http://www.cracked.com/article_20110_5-secret-languages-that-stuck-it-to-man.html http://www.cracked.com/article_20110_5-secret-languages-that... Quantum mechanics http://en.m.wikipedia.org/wiki/Quantum_key_distribution http://en.m.wikipedia.org/wiki/Quantum_key_distribution
infruset 13y ago
In the referenced article (https://www.schneier.com/crypto-gram-9810.html#cipherdesign https://www.schneier.com/crypto-gram-9810.html#cipherdesign), he says: > Algorithms posted to Internet newsgroups by unknowns won't get a second glance. It seems to me this would not be true of Bitcoin.
- hueving 13y ago
  Bitcoin isn't a new crypto algorithm. It's a distributed ledger algorithm that uses well known crypto protocols. It didn't invent its own magical hashing algorithm or anything of the sort.
BrownBuffalo 13y ago
If anything is shown from BitCoin - specialized hardware/application to solve encryption problems, its just a matter of specific application and time with any level of encryption.
pnathan 13y ago
It's always kind of cute to see ridiculous headlines roll through. 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.
- rcxdude 13y ago
  I think by unbounded they meant 'you can stick any number of arbitrarily complicated functions here'. I'm not sure whether this is any different in practice from just upping the key size on a cipher (since any implementation will be limited by at least memory used to represent the functions).
BrandonMarc 13y ago
This axiom of Schneier's (I think it's his) can't be repeated often enough: 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.

59 points by prajjwal 13y ago

danso 13y ago

> The researchers, led by Dr. Tomislav Stankovski, created an encryption mechanism that can generate a truly unlimited number of keys, which they say vastly increases the security of the communication. To do so, they took inspiration from the anatomy of the human body. 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.

rdtsc 13y ago
> why do researchers brag about creating an infinite number of keys, or even "unbreakable" encryption, To generate some funding and impress gullible people? It is like unlimited energy or flying car projects.
- deleted 13y ago
  [deleted]
JackGibbs 13y ago
For no encryption scheme is the key space unlimited. 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-know-if-rng-is-working.html 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.
TeMPOraL 13y ago
> I'm obviously not suggesting that one-time pads have solved much of anything Well, they did. Think about various secret channels between governments, like the Washington D.C. - Moscow line. http://en.wikipedia.org/wiki/One-time_pad#Historical_uses http://en.wikipedia.org/wiki/One-time_pad#Historical_uses
- dghf 13y ago
  I read a novel by a former SAS soldier about a former SAS soldier who's sent on deniable operations by the British government, and who uses what is clearly a one-time pad to communicate with his handlers. The detailed description of the precise method used, the fact that the term "one-time pad" is never used, and the narrator's apparent lack of understanding of how exactly it works (encryption/decryption is done via modulo-10 addition/subtraction, which the narrator derisively refers to as "spook maths") suggest that the author himself, or a contact of his in the same circles, has used a very similar system for real.
stygiansonic 13y ago
From just reading the linked to article, (I have not read the full paper) it appears that the researcher has conflated the size of the key space with whether or not the encryption algorithm is secure. 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.

LukeWalsh 13y ago

There's only one "unbreakable" encryption, and that's a pair of one time pads with truly random data as long as the message itself. http://www.pro-technix.com/information/crypto/pages/vernam_base.html http://www.pro-technix.com/information/crypto/pages/vernam_b...

andrewla 13y ago
While this may seem like a tempting statement, it is not really an answer, since "unbreakable" is not really well-defined. Clearly, "truly random" is a bit of a tough one to define. And sending the message length is a bit of an information leak itself. But even putting those aside, there's a bigger flaw. 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?
- nawitus 13y ago
  "unbreakable" may be not well-defined, but perfect secrecy is[1]. 1. http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy http://en.wikipedia.org/wiki/One-time_pad#Perfect_secrecy
  - JackGibbs 13y ago
    Perfect secrecy refers to the ability to determine any information about the plaintext without decoding it. Not having it can be very useful to an attacker, but that isn't always the case. RSA, for instance, doesn't have perfect secrecy, because it leaks the Jacobi symbol (https://en.wikipedia.org/wiki/Jacobi_symbol https://en.wikipedia.org/wiki/Jacobi_symbol) of the plaintext. However, that information is of limited utility, and it can be shown that determining more useful facets, for instance the parity of the plaintext, requires solving more unfeasible problems.
    - darkmighty 13y ago
      Actually, perfect secrecy refers to the ability to determine any information about the plaintext at all, given arbitrary decoding power. It's quite simple -- it means that given a standard distribution of keys and an a priori distribution over the plain texts the best estimate of the plaintext given the ciphertext is simply the a priori distribution (no additional information). For the binary case, Y(any distribution)+X(uniform)=Z(uniform) (mod 2), so that this is satisfied for any prior.

hawkharris 13y ago

I love these two lines from Shneier's earlier article, the one he links to at the end: "The 'best cryptographers around' break a lot of ciphers. The academic literature is littered with the carcasses of ciphers broken by their analyses."

a1a 13y ago
Indeed. Related advice, also from Schneier: "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break. It's not even hard."

ssdfsdf 13y ago

Seems like quite a good idea to me.

a1a 13y ago

"Truly unlimited number of keys" 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.

mantrax4 13y ago
It's typical for crypto algorithms to generate an endless (or extremely large) "keystream" by permutating a much shorter secret key with other data somehow. 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).
rcxdude 13y ago
It could be bigger. The 'keys' are just arbitrary sytems of equations, this is where 'unbounded keyspace' comes from. Any implementation would wind up being bounded by some practical constraint. 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'.

bo1024 13y ago

Theoretical cryptographers -- those who come up with new encryption schemes like the classics we rely on, e.g RSA and DH -- will take the following perspective: 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?). [1] http://en.wikipedia.org/wiki/Lattice-based_cryptography http://en.wikipedia.org/wiki/Lattice-based_cryptography

EGreg 13y ago

Although one-time pads are indeed unbreakable in a mathematical sense, in the real world everything is theoretically decipherable, in the end, using rubber-hose cryptanalysis and good timing. http://xkcd.com/538/ http://xkcd.com/538/ 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/ http://www.truecrypt.org/ Being dead http://www.cracked.com/article_20110_5-secret-languages-that-stuck-it-to-man.html http://www.cracked.com/article_20110_5-secret-languages-that... Quantum mechanics http://en.m.wikipedia.org/wiki/Quantum_key_distribution http://en.m.wikipedia.org/wiki/Quantum_key_distribution

infruset 13y ago

In the referenced article (https://www.schneier.com/crypto-gram-9810.html#cipherdesign https://www.schneier.com/crypto-gram-9810.html#cipherdesign), he says: > Algorithms posted to Internet newsgroups by unknowns won't get a second glance. It seems to me this would not be true of Bitcoin.

hueving 13y ago
Bitcoin isn't a new crypto algorithm. It's a distributed ledger algorithm that uses well known crypto protocols. It didn't invent its own magical hashing algorithm or anything of the sort.

BrownBuffalo 13y ago

If anything is shown from BitCoin - specialized hardware/application to solve encryption problems, its just a matter of specific application and time with any level of encryption.

pnathan 13y ago

It's always kind of cute to see ridiculous headlines roll through. 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.

rcxdude 13y ago
I think by unbounded they meant 'you can stick any number of arbitrarily complicated functions here'. I'm not sure whether this is any different in practice from just upping the key size on a cipher (since any implementation will be limited by at least memory used to represent the functions).

BrandonMarc 13y ago

This axiom of Schneier's (I think it's his) can't be repeated often enough: 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.