The Tricky Encryption That Could Stump Quantum Computers

Discussion in 'privacy technology' started by Dermot7, Sep 20, 2015.

  1. Dermot7

    Dermot7 Registered Member

    Joined:
    Dec 20, 2009
    Posts:
    3,196
    Location:
    Surrey, England.
    By Natalie Wolchover,
    http://www.wired.com/2015/09/tricky-encryption-stump-quantum-computers/
     
  2. amarildojr

    amarildojr Registered Member

    Joined:
    Aug 8, 2013
    Posts:
    1,963
    Location:
    Brasil
    I really don't care about "quantum craking".

    Even the most successful theoretical attack on, say Rijndael (the weakest of AES finalists), would take A LOT to succeed.

    So if with modern computers it would take 500 thousand years to crack Rijndael (not the actual number), but would take 250 thousand years with quantum computers, does it really matter? No.
     
  3. mirimir

    mirimir Registered Member

    Joined:
    Oct 1, 2011
    Posts:
    6,024
    Right. I'll be dead within at most 40 years. And even for longer-lived entities, very little matters much after 50 years.
     
  4. blainefry

    blainefry Registered Member

    Joined:
    Jan 25, 2014
    Posts:
    165
    It's actually even easier than that.

    We touched on this in Does quantum cryptology offer hack-proof security?

    AES (and the other submissions) are symmetric ciphers. "Quantum computation only speeds up a brute-force keysearch by a factor of a square root, so any symmetric algorithm can be made secure against a quantum computer by doubling the key length."

    While it's not exactly a small undertaking to change a key length on an enterprise-level scale, it's still a pretty trivial task compared to having to come up with, or even introduce an entirely new encryption scheme.

    And what's more, I could be wrong on this, but I would venture most implementations of AES already use 256-bit keys anyway. Here's what Bruce Schneier has to say about key lengths (my bold):
    Reflect on that last statement for a second.

    Sure in a post-quantum world, public-key schemes would need to be redone, but as that article (and the one by Schneier from last month below) mention, we already have quantum-resistant algorithms...

    NSA Plans for a Post-Quantum World
     
  5. mirimir

    mirimir Registered Member

    Joined:
    Oct 1, 2011
    Posts:
    6,024
    What about OTR (used with Pidgin etc) and Axolotl ratchet (used with Pond)? For more on Pond, see Razor's review on out blog http://dbshmc5frbchaum2.onion (add .to if you're not using Tor).
     
  6. amarildojr

    amarildojr Registered Member

    Joined:
    Aug 8, 2013
    Posts:
    1,963
    Location:
    Brasil
    Don't forget that Bruce also said that AES-256 "is less secure and is also more secure" than AES-128 and AES-192.
     
  7. blainefry

    blainefry Registered Member

    Joined:
    Jan 25, 2014
    Posts:
    165
    You put quotes in there, but I have not seen nor could I find such a quote from Schneier.

    The only thing I can think of is this post from 2009 talking about related-key attacks. If you read it, you'll see that for one thing, it's only talking about that one kind of attack, and more importantly, he explicitly states "for new applications I suggest that people don't use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you're already using AES-256, there's no reason to change."

    Even if he ever did say something like what you quoted, I'm still not sure what that's supposed to prove. That he's incompetent or doesn't know what he's talking about, simply because that statement sounds confusing? That AES isn't as strong as we're suggesting?

    If you want to get technical, the statement is accurate because "less/more secure" depends on the context.

    AES-256 is less secure with regard to that related-key attack than a 128-bit key simply because they use different key schedules. But obviously if you're just talking about something like brute force, a 256-bit key is more secure.

    Further, if we bring quantum computers into the conversation, as we already said, that would speed up a brute-force keysearch by a factor of a square root, meaning to get the same level of security you had before, you'd need to double the key length.

    In other words, when the facts/circumstances change, statements made prior to that change may need to be revised. But that doesn't mean they were inaccurate before.
     
  8. amarildojr

    amarildojr Registered Member

    Joined:
    Aug 8, 2013
    Posts:
    1,963
    Location:
    Brasil
    I wasn't being 100% exact when I quoted that. My apologies.

    Yes, what I was referring to was this comment:

     
  9. blainefry

    blainefry Registered Member

    Joined:
    Jan 25, 2014
    Posts:
    165
    Yeah but you'll notice not only does he explicitly say there's no reason to change if you've already implemented AES-256, but again we're only talking about a related-key attack.

    See here for details on that. This in particular (my bold):
    (And for a pretty detailed piece, here.)

    And again even in the narrow context in which such an attack would be feasible, no one has come up with anything practical. And even then, the only results we've had were against a certain number of rounds of the cipher, not the entire algorithm itself.

    Notice Schneier's recommendation...not to use a different cipher, but simply increase the default number of rounds:
     
    Last edited: Sep 23, 2015
  10. Lagaa

    Lagaa Registered Member

    Joined:
    Dec 30, 2014
    Posts:
    5
    The comment by Schneier is complete nonsense. AES 256 is stronger than AES 128. The attack he blogged about is a related-key attack, and no properly design software use related keys. The encryption keys are randomly generated (they are never related in this very special way that these attacks require for the attack to work).

    Schneier also wrote a paper back in 2000 during aes competition where is he was promoting his own twofish and claimed Rijndael is weaker because it has less "security factor"". He got this “ security factor” just by dividing the total number of rounds by number of rounds broken at the time. His argument totally ignored the fact that 2 rounds in Rijndael provide full diffusion vs round in Feistel ciphers (like Twofish) only operates on half of the state bits (full diffusion after 4 rounds). His safety factor was just a meaningless ratio and says nothing about actual math or security.

    https://autonome-antifa.org/IMG/pdf/Rijndael.pdf

    “Two rounds of Rijndael provide ‘full diffusion’ in the following sense:
    every state bit depends on all state bits two rounds ago, or a change in
    one state bit is likely to affect half of the state bits after two rounds.
    Adding four rounds can be seen as adding a ‘full diffusion step’ at the
    beginning and at the end of the cipher. The high diffusion of the Rijndael
    round transformation is thanks to its uniform structure that operates on
    all state bits.”

    For Rijndael adding four rounds actually doubles the number of rounds through which a propagation trail has to be found.

    In fact, Twofish is less safe for practical reasons: It's harder to implement without avoiding side-channel attacks (read the original NIST paper on selection process). That technically makes it weaker in practical sense, not stronger than AES.

    More importantly, a talented cryptanalyst simply gets more “bang for the buck” finding a flaw in AES then he does for the much less known and used twofish and serpent. Obscurity provides no protection in encryption. More eyes looking, studying, probing, attacking an algorithm is always better. That's one of the reason why AES is better.
     
    Last edited: Nov 13, 2015
  11. vuan

    vuan Registered Member

    Joined:
    Mar 14, 2014
    Posts:
    1
    Guys, instead of discussing how good is AES against quantum computers, you better look at Elliptic Curve Cryptography and RSA.
    (Elliptic Curve) discrete logarithm problem is vulnerable to (modified) Shor's algorithm on quantum computers.
    So, it is current widely-used public key cryptography which will be dead in the water as long as quantum computers with enough qubits are available.
    And as long as public crypto is dead, AES won't help you much - your symmetrically encrypted password file would be fine, but pretty much everything else (PGP, HTTPS/SSL/TLS, OpenVPN, SSH for example) will be possible to decrypt (and sniff for the passwords).
     
  12. Lagaa

    Lagaa Registered Member

    Joined:
    Dec 30, 2014
    Posts:
    5
Loading...