This is more along the lines of "SHA256 has not been proven to be secure, therefore, it may be cracked." It would require novel discoveries in mathematics to do so.
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.
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.
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.
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.
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.
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.
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.
Hashing algorithms aren't generally as well understood as reversible encryption algorithms. It's entirely possible that these novel discoveries are just around the corner.
