Hacker News Reader

Comment by FungalRaincloud | Hacker News Reader

I don't really like the argument that something is 'secure' because it is not vulnerable in the same ways that an alternative is. I think this is why I like talking about encryption so much. It's possible to mathematically prove the security of encryption algorithms, and all that's really left to pick apart is the implementation, politics and impact.

View on HN

Ehh... you can often prove that X algorithm is not susceptible to A, B or C attacks, but you cannot usually prove that the algorithm is "secure" in a fundamental sense.

https://en.wikipedia.org/wiki/Provable_security

You can prove that it's secure in that the algorithm itself does not leak information.

Yeah, but this is not what most people think of when they think secure, is it? That is, this proves that people have to actually break an algorithm to know what it is protecting. This does nothing to show that an algorithm is unbreakable.

(As an example of my understanding, rot13 does nothing to randomize distribution of characters, so it "leaks" information about what it has modified. This sort of leakage can be proven as absent from your algorithm. Anything else is a bit tougher.)

With some exceptions, those proofs make assumptions about their primitives like having block ciphers be "unpredictable permutations" or having hash functions be "random oracles". These proofs also make assumptions that information doesn't leak in other ways (like BEAST, heartbleed, timing attacks, poor entropy sources, etc).

In other words, those proofs don't have as much real-world significance as you'd like.

Unless you're dealing with OTPs, hashing, or lattice-based schemes, there are almost no information theoretical guarantees in encryption. For a field that uses math so heavily, it's surprising how rare traditional proofs are in the cryptology literature. Most encryption schemes are specifically designed to be hard to analyze.

This isn't for lack of trying on the part of cryptographers - unconditional proofs of security for most modern cryptosystems would imply that P and NP are separate. For example, a direct proof that SHA-256 is collision-resistant would imply that one-way functions exist unconditionally.

Even crypto algorithms rely on unproven assumptions for their security, even ignoring e.g. side-channel attacks.

Not true. Look up "resilience to information leakage".

I was talking more about cryptographic hardness assumptions such as the existence of one-way functions. Nevertheless, even in http://www.ccs.neu.edu/home/wichs/thesis.pdf, which was the first search result for that term, one of the first phrases is 'subject only to the constraint that the rate of leakage is bounded'.

This is not true at all for most forms of cryptography. Hash functions and symmetric cryptography are just shown to be resistant against all known attacks. For public-key cryptography there are sometimes security reductions to computational problems that are thought to be hard, but even schemes like RSA do not have such a security proof.

Reply on news.ycombinator.com