[ Date Index ] [ Thread Index ] [ <= Previous by date / thread ] [ Next by date / thread => ]
On 06/09/13 19:02, Martijn Grooten wrote: > On Fri, 6 Sep 2013, bad apple wrote: >> formally proved maths remains invulnerable > > I'd like to nuance this a little. > > TL;DR in theory this isn't true, in practise it is. > > When crypto uses maths, it's usually a computation that can not easily > be inversed. RSA, for instance, is based on the fact that it is > (relatively) easy to two find prime numbers of a given length n, but > it's really hard, given the composite number (of length 2n), to find > the original two prime numbers. Depending on n, it's a difference > between "takes less than a second" and "takes centuries". > > The tricky bit here is the 'easily'. It hasn't been proven in this > case (and many other cases) that there really isn't a fast algorithm > for factoring large integers. In theory, someone could find such an > algorithm tomorrow and thus break most of the assymmetric crypto used > in the world. > > In practise, because RSA is old (it was invented in the 1970s) and the > interest in integer factorization is even older, it's generally > believed that there isn't an easy way to factor large integers. > > There has been some fuss made (in a BlackHat presentation that got > picked up in the press) about recent developments in discrete > logarithms, another 'hard' problem that's important for cryptography, > and again, it's not really proven that it's hard. Here, in some very > special cases, it turns out to be not as hard as one thought. Most > experts believe that these cases are too special to have any serious > consequences, but it can't ever be 100% exclused that one day someone > makes a major breakthrough - or that someone, like the NSA, has > already done so. > > Some newer cryptography uses elliptic curves. This uses maths that's a > lot less basic than RSA (or Diffie-Helman) and doesn't go as far back > as those algorithms. This makes it slightly more likely that someone > will find (or will have found) weaknesses in the mathematics that's > used. It's still extremely unlikely that the 'hard' problem for > elliptic curves turns out to be easy, but there may be special cases > (i.e. special curves) for which this is the case. > > In this context, it may be worth having a look at > > http://en.wikipedia.org/wiki/Dual_EC_DRBG#Controversy > > which is about a crypto standard that possibly includes backdoors. > Technically, this still means the implementation that's wrong, not the > maths, but the backdoor is inside the way the maths is used, not in > the code. > > Martijn. > > I'd like to add some nuance to this nuance as well :] TL;DR - you can't protect against future attacks. I am neither a mathematician or a cryptographer but have a considerable interest in the field of complexity classes, which for the uninitiated, is what Martijn is touching on here. Certain classical problems, such as the Travelling Salesman or Subset Sum are classified as so-called NP-complete; generally cryptographic algorithms harness certain intrinsic qualities of the NP complete or NP hard classes to do what they do. As stated, given a massive semi-prime and it's two contributing primes, it's incredibly trivial to multiply the two primes and confirm that the product is indeed derived from it's two factors. However, given just the massive semi-prime, it's staggeringly difficult and inefficient to calculate those factors as you have to search (brute force) the entire address space looking for them. This is of course entirely intentional and the basis of how all modern crypto works. So far so good. Now, an allegory: the speed of light "c" is a constant, and the laws of physics tell us that it is not possible to exceed that speed. In *theory*, that could of course be disproved tomorrow by some staggering new development. In exactly the same way, in *theory* someone could pop up tomorrow and say they've proved P=NP, which would be scarcely less mind-blowing (and the death warrant on all classical cryptography) but for that to be true, they would either have had to invent new maths (algorithms) or a new computer (a quantum one). This *could* actually happen, but trying to protect against is literally impossible and not even worth considering. I'm pretty confident that neither of these will happen in any of our lifetimes, if ever. Practical weaknesses are a different matter, and are constantly being worked on and researched by very talented people. A Chinese Professor produced the first SHA-1 hash collision back in 2005 (which is why we don't use it anymore) which at the time was a pretty jaw-dropping wake up call. We keep getting advice to increase key lengths as new algorithmic weaknesses, advancing ASIC/FPGA hardware and implementation details are constantly attacked but this is more of gently creeping tide lapping at our toes, easily monitored and worked around, instead of the raging 100m tsunami that just crushes all of our defences immediately. This is all down to the very nature of how our maths works, and there is a whole field (sadly way beyond my abilities to fathom) of formal proof that assures us that within the laws of the universe as we currently understand them, rock solid proper crypto is absolutely, 100% provably unbreakable (P does NOT equal NP, end of story). With all of their phenomenal talent pool, unlimited budget and acres of custom computing power, would it be wise to assume the NSA has probably found a couple more weaknesses than anyone else? Yes. Can they factor gigantic primes at perhaps several orders of magnitude greater rates than anyone else? Quite probably. Are they basically scarily proficient adversaries with the best cracking abilities in the world. Definitely! Can they break the second law of thermodynamics? HELL NO. This is what this breaks down to. The fail0verflow hacking team who famously compromised the PS3 back in 2011 went on record as saying they couldn't have possibly cracked the elliptic curve cryptography protecting the innards if Sony hadn't stupidly borked their implementation of it - the underlying maths was sound, and hence unassailable. The NSA will go for your computer or the other end point, hoping for backdoors, 0 day weaknesses only they know, known weaknesses in a Linux boxes key generation procedures, etc, etc: they'll fibre tap the entire internet, compromise CAs and spend billions on custom hardware and the world's greatest talent but they can not break the rules of physics. I repeat, the NSA can NOT break your 4096 RSA key if it was correctly generated. If the NSA could, they'd have answers to questions we have not even begun to think of yet. They also wouldn't bother with any of the other time consuming stuff they do because they wouldn't have to, obviously. You don't MITM SSL traffic when your quantum computer can crack all keys, in all address spaces, ever, instantly. So, to summarise: completely breaking our current crypto algorithms would be as spectacular as exceeding the speed of light or showing an instance where entropy did not increase in a finite system over time. It may well never happen. Incremental improvements in attack strategy, algorithms and spotting implementation attacks are however a given. I'll leave the last word to Mr Snowden himself (and undoubtedly get all of us well and truly on the NSA watch list considering the nature of this discussion): ""Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on," he said before warning that NSA can frequently find ways around it as a result of weak security on the computers at either end of the communication."* Regards * http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security -- The Mailing List for the Devon & Cornwall LUG http://mailman.dclug.org.uk/listinfo/list FAQ: http://www.dcglug.org.uk/listfaq