Hacker News Reader

Comment by seandougall | Hacker News Reader

Mathematically we can be reasonably certain it works, but afaik it’s not formally proven that, say, there isn’t an efficient algorithm for prime factorization. It just seems unlikely that the U.S. government would know of one that nobody else has managed to figure out.

Plus, flawed implementations can open up side channels; this seems like an endorsement of Facebook’s implementation in that sense.

View on HN

> afaik it’s not formally proven that, say, there isn’t an efficient algorithm for prime factorization

Correct. AES or something is also not proven secure, we just don't know of an efficient attack on it. Since loads of people tried with significant resources, since there is often parallel discovery (so if the NSA discovers a flaw, it's likely that someone else figures it out as well), and since an algorithm is usually weakened before a complete break is found, the security community is quite sure it's secure. But it's not proven or certain.

Also the security of the theoretic primitives behind symmetric encryption rely on the existence of pseudorandom generators / pseudorandom functions ect. which is not proven either. On top of this, AES for example is "only" an apporoximation of what a pseudorandom function really is. In the end these ciphers are secure as long as nobody finds a flaw in them. However, flawed implementations are the main risk.

A one-time pad has been proven to be unbreakable. https://en.wikipedia.org/wiki/One-time_pad

Quote "Claude Shannon proved, using information theory considerations, that the one-time pad has a property he termed perfect secrecy"

One time pads just push the problem to the random number generator (which has to be 100% perfect, free from correlations and bias). How exactly does one prove that their hardware RNG is uncorreleated? e.g. what you thought was RF noise could actually contain the theme tune to Barney the dinosaur. The most provable way we have to generate random numbers of the quality necessary is to generate them using... cryptographic ciphers.

Why not roll physical dice?

How many dice would you have to roll for sending this message? How long would that take?

What about collecting cosmic background radiation and converting it to one-time pad bits?

Hardware random number generators poof of correctness comes from... physics.

Unless there is some fundamental hole in our understanding of physics, including thermodynamics and quantum mechanics, HRNG are the best source.

Using cryptographic ciphers for pseudorandom functions can be catastrophic, as seeding them correctly is a problem. (You still need some entropy from outside for seeding)

Of course, using one time pads is not really practical either.

Reply on news.ycombinator.com