Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

"Unbreakable" Encryption Almost Certainly Isn't

schneier.com

Post reply on HN
Print view View original

21–30 of 62 posts

Re: "Unbreakable" Encryption Almost Certainly Isn't

#21

Post by dllthomas »

andrewla wrote: post #16
cuu508 wrote: post #10

Earlier quoted context omitted.

> why not just send the actual message via that mechanism? 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

By assumption, the only way to "transmit information securely" is by one-time pads. So...

That was not the assumption. The assumption (or assertion) was that one-time pads were the only unbreakable encryption. There are ways of securing things other than encryption (most obviously physical isolation).

Re: "Unbreakable" Encryption Almost Certainly Isn't

#22

Post by mannykannot »

andrewla wrote: post #6
LukeWalsh wrote: post #4

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

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

You do not actually have to define "truly random". You do have to trust that the mechanism you are using to generate keys (radioactive decay or rolling dice, for example) is unpredictable.

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.

Re: "Unbreakable" Encryption Almost Certainly Isn't

#23

Post by stygiansonic »

danso wrote: post #2

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

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.

Re: "Unbreakable" Encryption Almost Certainly Isn't

#25

Post by bo1024 »

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

Re: "Unbreakable" Encryption Almost Certainly Isn't

#26

Post by EGreg »

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/

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

Re: "Unbreakable" Encryption Almost Certainly Isn't

#27

Post by AnthonyMouse »

andrewla wrote: post #6
LukeWalsh wrote: post #4

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

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

> And sending the message length is a bit of an information leak itself.

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.

Re: "Unbreakable" Encryption Almost Certainly Isn't

#28

Post by mantrax4 »

a1a wrote: post #24

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

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

Re: "Unbreakable" Encryption Almost Certainly Isn't

#30

Post by omh »

a1a wrote: post #14
voidlogic wrote: post #12

Earlier quoted context omitted.

You give each party a briefcase full of 4 TB hard drives full of random numbers generated from a USB attached atomic decay device. 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.

How do you encrypt the hard drives? I wouldn't trust some keys that had been lying around on an unencrypted hard drive for 1,2,10 years!

If I was using one-time-pads I'd probably be using them because I didn't trust encryption, so "unencrypted" wouldn't matter here.

In real-world implementations I think the security is probably based around a large number of men with guns.

Post reply on HN