Hacker News Reader

Comment by bad_user | Hacker News Reader

Actually many cryptographic algorithms that got defeated, haven't been defeated with "new discoveries in mathematics". Also, you can't really prove that such an algorithm is secure. You can only prove that it exhibits certain properties that make it more secure versus other algorithms.

Judging by how cryptographic methods got defeated in the past, I think it's safe to assume that it's only a matter of time.

View on HN

It's not impossible to prove cryptographic algorithms are secure. It's just really, really, really difficult. So difficult it's not even proven that one way functions exist in the first place! (For context: if one way functions exist, then P!=NP).

Proving cryptographic algorithms are secure involves proving statements over all turing machines. For example, one definition of a 'secure' pseudo random number generator is one such that no turing machine can distinguish its output from 'true' random (with 2/3 certainty) in polynomial time.

However, we do know a really-really-probably secure one way function. If there are any one way functions, then it is secure. It just isn't really practical. http://en.wikipedia.org/wiki/One-way_function#Universal_one-...

  Also, you can't really prove that such an algorithm is secure.

Incorrect. One Time Pad encryption is provably secure. (Proven by Claude Shannon, no less; as in, the guy who invented information theory.) It is impossible to decrypt if you do not have the key.

...subject to your key being safe, produced from a good source of entropy and never used anywhere else. Is this provable?

keeping the key safe, yes, using the key once, yes, but need not be random at all (with in reason - a key of 0s is feasible, under the pretense that the cipher text, which would be equal to the plain text, is the cipher text for any message with the same length, for some key)

the key space being the same size as the message space, and cipher text space means that all messages of equal length are possible, with no way of knowing which one is the correct one. i suppose, a theoretical attack would be to be to enumerate all messages in the english language, XOR them with the cipher text, and see which resulting keys come close the properties of the PRNG used..

even non-determinism can't help you here, i'm afraid.

I leave the reason that this is among the funnier HN crypto comments ever as an exercise to the reader. And, of course it happened on a Bitcoin thread.

never once tried to argue that it is a practical approach...

additionally, attempting to exhibit intellectual superiority by making someone look stupid, isn't infuriating, it's just sad.

i wouldn't conduct myself like that in public or on the internet. it's a shame that anyone thinks it's acceptable.

One time pads strain the definition of "encryption" and are by convention a bozo filter for people talking about crypto. For instance, downthread, you have someone saying that an all-zeroes OTP key would in theory be fine.

In reality, all OTPs do is shift forward in time a relationship that must still be secured through some other means.

So, from now on, when we talk about the feasibility of breaking crypto, let's implicitly constrain "crypto" to "crypto that people can use in practice".

i think you've misunderstood what i was saying. the OTP is definitely not a practical method of encryption, obviously.

and no, OTPs do not require that the that any secure relationship be formed forward in time.

in fact, restricting "crypto" to "crypto that people can use in practise" doesn't rule out the OTP - it was used with great success in both world wars, owing to the fact that agents were able to share keys before the fact, use them once, and then discard them.

finally, at no point would i ever suggest using the OTP as a means of encryption in place of a public key system, especially one with a key of 0s. why you suggest such a thing is beyond me.

As someone says, one-time pads are impossible to decrypt without they key. But you can guess the key or use some other brute force mechanism.

My guess, SHA-256 will fall to a quantum computing algo in a few years.

As someone says, one-time pads are impossible to decrypt without they key. But you can guess the key or use some other brute force mechanism.

Actually, you can't even reliably brute force a one time pad. The key is always the same length as the message. All plausible messages of length N are equally valid solutions for a brute forcing algorithm.

>All plausible messages of length N are equally valid solutions for a brute forcing algorithm.

Assuming there is no out-of-band information to use to attack the ciphertext then yes I agree is unlikely to find a unique solution.

Aside: I'd never considered that key length was dictated by the term "one-time pad".

You could be using a One Time Pad for key management. This is certainly feasible now, since a couple of Gigabytes of data is now considered a manageable amount.

Reply on news.ycombinator.com