3 ms·

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.

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.

lucb1e 7y ago
> 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.
bouncycastle 7y ago
A one-time pad has been proven to be unbreakable. https://en.wikipedia.org/wiki/One-time_pad 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"
- mantap 7y ago
  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.
  - dark_glass 7y ago
    Why not roll physical dice?
    - diffeomorphism 7y ago
      How many dice would you have to roll for sending this message? How long would that take?
  - shadowprofile77 7y ago
    What about collecting cosmic background radiation and converting it to one-time pad bits?
  - bouncycastle 7y ago
    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.
boblivion 7y ago
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.

lucb1e 7y ago

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

bouncycastle 7y ago

A one-time pad has been proven to be unbreakable. https://en.wikipedia.org/wiki/One-time_pad 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"

mantap 7y ago
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.
- dark_glass 7y ago
  Why not roll physical dice?
  - diffeomorphism 7y ago
    How many dice would you have to roll for sending this message? How long would that take?
- shadowprofile77 7y ago
  What about collecting cosmic background radiation and converting it to one-time pad bits?
- bouncycastle 7y ago
  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.

boblivion 7y ago

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.