back to article So what's the internet community doing about the NSA cracking VPN, HTTPS encryption?

Now that the cat is firmly out the bag, and it's clear that the NSA has cracked the encryption behind, potentially, a huge amount of internet traffic, the question inevitably turns to: what are internet engineers going to do about it? Clearly the experts at the Internet Engineering Task Force (IETF) have pondered the same …

  1. a_yank_lurker

    Encryption can be cracked if one is willing to throw resources and time at it. How much time and resources the attacker has is key. The major goal of encryption is not to be uncrackable but to difficult enough that any information gleaned is worthless.

    1. Velv
      Black Helicopters

      Don't know why you've been down voted, so have an upvote.

      You cannot prove a negative. The "unsinkable" titanic sank, "unlimited" broadband isn't unlimited, safes are designed to make it difficult and time consuming for criminals to rob you, but ultimately with time and resources criminals do break in to most safes.

      And no encryption is "uncrackable". If you believe the uncrackable nirvana exists, be prepared for a surprise.

      1. Bronek Kozicki

        Obligatory xkcd reference

      2. Charles 9

        You CAN prove a negative by Contradiction. That's how Turing famous Halting Theorem works.

      3. Suricou Raven

        Not quite true: XOR encryption with a random single-use key is mathematically uncrackable. It's just not used because the key management requirements are very impractical for almost all use cases.

        1. Michael Wojcik Silver badge

          Not quite true: XOR encryption with a random single-use key is mathematically uncrackable

          God forbid we ever make it through a thread on cryptography without someone mentioning the one-time pad. Maybe we could have an icon for "obligatory OTP citation"?

          The OP didn't say "mathematically uncrackable". You've argued a different claim.

          No cryptography is uncrackable because a ciphertext qua ciphertext has to be decryptable by someone or something, and that recipient can be coerced, suborned, etc. A ciphertext that isn't decryptable is no longer a ciphertext (if it ever was).

          Distinguishing between an OTP-encrypted message and key exchange is also a dodge. You transmit the pad over one channel and the message over another. You have to protect both channels, so the OTP just defers the problem. There's no real distinction between "key exchange" and "message exchange" for the OTP, except the circumstances of the particular case.

          (Also, you left out some constraints. The pad has to be random in a strong sense - all possible values equally probable, for one - and must be at least as long as the plaintext.)

      4. Michael Wojcik Silver badge

        Don't know why you've been down voted

        Perhaps because this sort of commonplace about security gets bandied about regularly, instead of more meaningful statements about work factors and threat models and the like? It was a (relatively) lot of words with little substantive content.

        I didn't downvote the post, but it says nothing you wouldn't get from the introduction to a security primer. Everyone either knows it already, or isn't teachable on the subject.

        In this particular case, there's a huge difference between a 1024-bit DH prime and a 2048-bit one. Handwaving statements about "you just need resources" are not particularly useful when the resources in question are ~300 orders of magnitude beyond what's feasible for a major nation-state.

        Even if the NSA have a really big quantum computer at their disposal (putting them very, very far beyond the published state of the art), that machine would still be facing a work factor about eight times what they need to crack a DH group based on a 1024-bit prime, and about ten times as many qubits. Yes, that's "only" a linear increase (for this implausible magical-technology scenario), but a linear increase in cost means a linear decrease in the number of decryptions, or equivalently a linear increase in the bar the value of your encrypted communications have to reach before someone will pay to break them.

        And, in fact, this article is wrong. Few organizations have any pressing need to move to larger DH groups. Just switching to a DH prime that's not well-known is sufficient, because it's the widespread use of the same primes that made it economically feasible to break them. If everyone generates and uses their own set of DH parameters, then the cost of breaking goes way up, and only the most valuable communications will be targeted.

        That is what is important here.

    2. Anonymous Coward
      Anonymous Coward

      How about if Obama issued an Executive Order telling the NSA, CIA, and all the other agencies that work for him to stop violating people's privacy and follow the U.S. Constitution?

      How about if Obama stopped persecuting Snowden because Snowden pointed out that the U.S. is violating the Constitution?

      1. Michael Wojcik Silver badge

        How about if Obama issued an Executive Order telling the NSA, CIA, and all the other agencies that work for him to stop violating people's privacy and follow the U.S. Constitution?

        How about if the NSA, CIA, and other agencies just ignored him, because why wouldn't they? Who's going to audit their behavior? Who's going to enforce this dictum?

        Even if 1) such spying were to be redefined as, say, treason (which would take a constitutional amendment), and 2) an agency were caught doing it, I am sure that among the thousands of dedicated zealots working for such agencies they could find a few willing to fall on their swords. So even if there were punishment, nothing would change.

        Bottle open, djinn out.

        Now, that doesn't mean that I'm opposed to any of the three branches slapping the TLAs and telling them to cut it out; and I'm certainly not opposed to attempts to roll back the PATRIOT Act and related shenanigans. Curbing the police state is never more than a temporary and partial fix, but that doesn't mean it isn't worth doing. But no wave of the presidential fairy wand is going to make everything right again.

  2. Wade Burchette

    Questions

    There are a finite number of prime numbers that use 2048 or less bit. What prevents the NSA or hackers from generating a rainbow list of all these prime numbers and crack the encryption that way? Why limit yourself to just prime numbers?

    1. Old Man - Grey Fleece

      Re: Questions

      A rainbow list would be impractically large and a nightmare to build in terms of cpu cycles. If you look up distribution of primes you can get a reasonable approximation to the number of primes in any range and we are talking 10^100 ish. (Yes, I haven't checked my number theory book for a few years). The bigger the prime the more it costs per prime to find it - see other Vulture articles. Unless we get serious quantum computing.

      Why use primes? - because they are what give unique decription, hairy group and number theory from what little I remember and you probably have to check the specific algorithm to see why.

    2. John H Woods Silver badge

      Re: Questions

      "There are a finite number of prime numbers that use 2048 or less bit" -- Wade Burchette

      Finite yes, but also ENORMOUS.

      The number of primes less than x, pi(x), is approximated by x / (log x-1) or more roughly, but more conveniently, x / (log x). For 1024 bits, x = 2^1024 which is about 10^308.

      pi( 2^1024) ~= 10^308 / 1024 ~= 10^305. As there are probably only about 10^80 atoms in the universe, give or take a power of 10, no such list can exist, even for primes of 1024 bits. For 2048 bits you'd be looking at > 10^600!

      So although you have to use primes (otherwise the encryption wouldn't work), "the finiteness" of the number of primes is not a problem. But I thought it was a reasonable question, so if you do get any downvotes, they weren't from me :-)

      1. allthecoolshortnamesweretaken
        Pint

        Re: Questions

        @Wade Burchette, Old Man - Grey Fleece, John H Woods

        Thanks for posting a question that has been on my mind too and the answers & clarification.

        10^308 is a pretty big finite... have a pint & an upvote.

        1. Benchops
          Joke

          Re: Questions

          But surely everyone uses the 5*10^307-th prime?

          I mean, no-one would use the first prime (2) as that's too obvious. Similarly the largest prime less than 2^2048 would be too obvious. So then the next primes you would obviously not use are the 2nd prime (3) and the 2nd to last prime below 2^2048. etc. Everyone decides to use the middle prime.

      2. Anonymous Coward
        Anonymous Coward

        Re: Questions

        Perhaps, but the defenders and the attackers have to start from the same position: finding those primes in the first place, and finding one by chance is going to be difficult. So usually some kind of algorithm is used to try to hunt down these primes more quickly. Only one catch: the attacker can use the same techniques, trading in space for time but knowing the defender is under the same auspices.

      3. Velv
        Headmaster

        Re: Questions

        @ John H Woods

        "For 2048 bits you'd be looking at > 10^600!"

        Pedant alert - having done all the nice mathsie bits, you kinda spoiled it by putting an exclamation mark on the end. (n! Factorial)

        tee hee

        1. DropBear
          Facepalm

          Re: Questions

          "(n! Factorial)"

          Oh dear. Ten to the power 600 _factorial_ is... is... one of those things reserved exclusively for the members of the "Kwisatz Haderach" club... *headasplode*

        2. John H Woods Silver badge
          Pint

          Re: Questions

          "Pedant alert - having done all the nice mathsie bits, you kinda spoiled it by putting an exclamation mark on the end. (n! Factorial)" -- Velv

          Ouch, yes. d'oh ... Have 568ml of beer on me ...

    3. Anonymous Coward
      Anonymous Coward

      Re: Questions

      A lot of the basic security in these sort of protocols comes from some math proposition.

      Typically when primes are mentioned, it's exploiting the fact that finding the product of two co-prime numbers P=(p*q)is easier than factorizing P/q = p. If the numbers are prime, then only one (p,q) pair will make a given P.

    4. Doctor Syntax Silver badge

      Re: Questions

      AFAIK* the Diffie-Hellman works by agreeing on a prime and then each party performing some computation on it and exchanging results they mutually calculate a key and the crack** actually does work by calculating*** a sort of rainbow table for a given prime. By observing the exchange between the parties, including the prime they agree on, they can calculate the key for themselves. The weakness of implementations of D-H is that rather than search for a large prime at run time they have a limited number built in which makes it feasible to calculate a few tables which will be sufficient to attack most sites.

      *And I'm not a mathematician.

      **Nobody knows for sure what the NSA do but some boffins worked out that this is how they might have done it.

      ***This is a humungous calculation but is now achievable by throwing enough CPU cycles at it.

      1. Anonymous Coward
        Anonymous Coward

        Re: Questions

        >> The Diffie-Hellman works by agreeing on a prime]

        no it doesn't Please play the video in the article.

        The number of primes in 2^1024 space (around 10^300) is significantly more than the number of atoms in the universe (around 10^80) so it could be a little challenging to build a rainbow table ...

    5. This post has been deleted by its author

  3. Your alien overlord - fear me

    I bet the IETF knew back in 2005 the NSA had cracked 1024 bits. 10 years on, they are more than capable of cracking 2048 bits so stop faffing around and jump straight to 4096 bit encryption.

    1. Anonymous Coward
      Anonymous Coward

      Unless the way they're breaking it is by using a black project working quantum computer and Shor's Algorithm, in which case number size won't matter so much.

      1. Trevor_Pott Gold badge

        The power consumption that could be seen from fucking space probably would be a bit of a bitch though. If you're cracking 2048 bit encryption with a quantum computer you are either using space fairy dust or enough liquid helium to make CERN shit planetoids.

  4. foxyshadis

    The NSA just recommended dropping ECC

    Which means that everyone should probably switch to ECC as soon as they can. The NSA is little more than a black-hat these days.

    1. allthecoolshortnamesweretaken

      Re: The NSA just recommended dropping ECC

      "The NSA is little more than a black-hat these days."

      Close. The NSA is the original black hat.

      1. Anonymous Coward
        Joke

        Re: The NSA just recommended dropping ECC

        No, it was Bletchley Park.

        1. allthecoolshortnamesweretaken
          Pint

          Re: The NSA just recommended dropping ECC

          No, it was Sir Francis Walsingham...

          ELINT goes back to the days of the first telegraph. SIGINT (in a broader sense) goes back so far that you can't really date it. Spying realy is 'The second-oldest profession'.

          This is about computer networks, and Bletchley Park didn't spy on them because there weren't any yet. The NSA, however...

          ... anyway: pedant mode OFF, have a nice weekend, a pint an an upvote. Bletchley Park references always get one (I think it's in the forum rules somewhere).

          1. Mike Pellatt

            Re: The NSA just recommended dropping ECC

            "This is about computer networks"

            I'd make the case that this isn't about computer networks, but about communication networks. In which case, they most certainly did exist. With exactly the same challenge to address as today's networks - how to communicate securely over an insecure medium.

            In WW2, the medium was morse code transmitted over HF radio. This was easily intercepted with a sufficient number of skilled operators at sufficient receiving stations. These operators are amongst the unsung heroes - accurately transcribing random characters is far harder than plain language.

            1. filter_guy

              Re: The NSA just recommended dropping ECC

              Morse code is not random characters, although it can be used to transmit random characters. Yes, morse code may seem like gibberish to those who cannot understand it. For amateur radio operators, who communicate using morse code, it is understood as a valid language, and not just "random characters".

              1. Anonymous Coward
                Anonymous Coward

                Re: The NSA just recommended dropping ECC

                Morse Code is no longer used,at least it is no longer officially recognised as a language of communication.

                OH ... .... .. _ ! I must be giving my age away.

                An old shipmate,who was a former long -serving submariner,whose ears were flat against the side of his head from years of wearing headphones,reckoned that he could tell exactly who was sending messages to anyone else,probably due to the unique rhythm when keying.

                I understand that as when on shore leave, I listened to morse code on my old Murphy B40 Communications Receiver,which was in use by the RN during the 1960's.

      2. Anonymous Coward
        Anonymous Coward

        NSA as the original black hat

        No. Cracking Enigma like Bletchly Park did, or the NSA cracking whatever codes the Soviets were using back during the Cold War wasn't evil, it was just ordinary spycraft.

        Turning that capability on their own citizens was when it became evil. And the NSA didn't used to be evil, at least not completely. Remember, they were the ones who strengthened DES when IBM developed it in the 70s with some flaws the NSA knew about back then but the security research world didn't figure out until the 90s! Until those techniques were discovered, many had assumed the changes the NSA had IBM make to DES were to weaken it.

  5. Chris Miller

    Is this a legacy problem

    As I understand it, the weakness is in the implementation of Diffie-Hellman. When it was first introduced, it was impractical to calculate even a 512-bit prime in a reasonable amount of time, so the software came with a list of such numbers that you could use, and it's this list that (it is claimed) the NSA has broken with something like a rainbow table. But today, calculating a 2048-bit prime on a PC or decent smartphone takes a couple of seconds*. So we could, if we wanted, produce a unique prime each time and the NSA's advantage would go away.

    I suppose the obvious answer is that it's easier just to move from 1024-bit to 2048-bit, even though (a) many people won't; and (b) there'll be lots of backward compatibility attacks like logjam.

    * 2 seconds would be a long time to wait for each TLS handshake, but we could always pre-calculate keys at start-up. And, in a few years the time needed will drop to milliseconds.

    1. Doctor Syntax Silver badge

      Re: Is this a legacy problem

      "2 seconds would be a long time to wait for each TLS handshake, but we could always pre-calculate keys at start-up. And, in a few years the time needed will drop to milliseconds"

      As you say the weakness is in using very few built-in primes everywhere. One remediation, even without going to eliptic curves, would be frequent, say monthly, updates with new and maybe larger sets of built-in primes. According to the times given in the paper this should enable users to keep ahead of the NSA. Another would be to have servers running a background task searching for new primes so each server would be able to offer a different prime each time it was contacted.

      1. calumg

        Re: Is this a legacy problem

        Distributing primes, even regularly, would be a problem, because priority targets would have all their encrypted comms archived. (At least, that's what I'd do if I were GCHQ.) So even if it takes longer than a month, once the prime is cracked, all the archives can be decrypted. A reminder that encryption keys should be long enough to prevent cracks by *future* computing power.

        1. Anonymous Coward
          Anonymous Coward

          Re: Is this a legacy problem

          "A reminder that encryption keys should be long enough to prevent cracks by *future* computing power."

          Except sometimes future computing power involves a paradigm shift such that the fundamental method becomes vulnerable. In this case, D-H Exchange can be some vulnerable if a someone can produce a working quantum computer that can subject the shared secret to Shor's Algorithm (the scary part being it may already exist but no one knows about it because it's a "black" project). The more qubits the quantum computer can process, the larger a shared secret it can crack. That's why you can't really future-proof an encrypted communication that has unlimited useful life. Eventually, computing should be able to catch up, if not by sheer force, then by working around the problem.

          As for archiving, couldn't you address this issue by some form of forward secrecy so that decrypting one message doesn't open the door to all the rest?

        2. Doctor Syntax Silver badge

          Re: Is this a legacy problem

          The argument put forward in the paper is that the processing for a single prime is mathematically feasible but computationally very expensive. But what the researchers realised was that once you'd done it the additional work to crack any eavesdropped exchange was trivial and that as the same prime was being used by a large number of sites for a long period the cost could be spread out over an enormous amount of traffic. It was this which made it economically feasible.

          If the a larger number of primes were used for shorter periods the economics would work against it and only a small proportion of the traffic would ever be decrypted. As to being concerned about future computer power, you have to remember that in order to make decryption worthwhile you have to do it whilst the messages are still relevant.

          Nevertheless, a switch needs to be made to better algorithms or much longer primes.

  6. Ian 55

    "urging in the strongest terms developers and engineers to use at least 2048-bit key sizes"

    Well, that'll work, because everyone reads... Oh.

    What might work is some seriously popular kit to refuse to work with anything that didn't.

  7. No such thing as an Anonymous Coward
    Thumb Up

    "What might work is some seriously popular kit to refuse to work with anything that didn't."

    OpenSSH...

    1. Ken Hagan Gold badge

      Re: "What might work is some seriously popular kit to refuse to work with anything that didn't."

      Google and Microsoft may also follow suit in due course. They are increasingly worried by how the NSA affects their ability to do business outside the USA. We live in interesting times.

  8. John Sager

    A little clarification

    The recent issue with Diffie-Hellman is that the standards, and a lot of implementations, use one specific 1024-bit prime known as 'Oakley Group 2'. The conjectured hack is to calculate a lot of specific data from this prime which can then be used to rapidly break any shared keys generated by D-H using this particular prime if the D-H message exchange is observed. The counter is not to use that particular prime. More modern implementations tend to use Elliptic Curve Cryptography (ECC) which, as far as is known publicly, is secure with large enough fields over which the calculation is done. For example, OpenSSH has for a while used in preference an elliptic curve algorithm called Curvep25519, which is supposed to be as hard to break as 128-bit AES, i.e. impractical currently.

    Note: Although thethere has been a recent debacle over the NIST Dual_EC_DRBG random number generator which uses elliptic curves in a specific, and conjecture to be hacked, way, this has no bearing on the general security of ECC.

    1. Alan J. Wylie

      Re: A little clarification

      At last, a post that clarifies that the recent issue is that a small number of 1024 bit primes are very commonly used, and that the NSA is theoretically capable of analysing each such prime within its budget and a timescale short enough to return a dividend.

      https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

      For the most common strength of Diffie-Hellman (1024 bits), it would cost a few hundred million dollars to build a machine, based on special purpose hardware, that would be able to crack one Diffie-Hellman prime every year.

      ...

      Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites.

    2. This post has been deleted by its author

    3. Anonymous Coward
      Anonymous Coward

      Re: A little clarification

      And this is where the security guys really screwed up and screwed us. Even if they thought "it would take many years to crack this one prime" why the HELL did they use a single prime? Security isn't about doing 'just enough'...what happened to the idea of "defense in depth"?

      Would it really have been that much harder to have it choose from a list of thousands of 1024 bit primes, that could be updated when the software was patched? It was sheer laziness, poor assumptions and stupidity on the part of the security community, along with not recognizing how difficult of a task it will be to update all this software when the time comes that caused this, not the NSA's evilness.

      1. Bronek Kozicki

        Re: A little clarification

        Here is explanation : people implementing small details of encryption / cryptography programs do not necessarily consider themselves "security community". These are often your "regular" developers who sometime make poor choices, e.g. make an assumption that if a single prime is good, then it can be reused over and over again. Why would "good prime" matter? You just cannot use any prime in D-H, because some of these numbers would render your encryption incredibly weak. You need "good" numbers, and how do you find those? Well, for one you can use those "known to everyone to be good".

        1. defiler

          Re: A little clarification

          So, to be clear (as I genuinely don't know), this means that my private key prime number can't be '3' because that's not on a proscribed list of non-shit keys? But similarly, many, many websites will use the same key as me?

          Am I close, and do I win a prize?

          1. Bronek Kozicki

            Re: A little clarification

            In D-H key exchange there is no such thing as "private key prime" . The two prime numbers from which key exchange starts are called generator (a very small number, usually 2, 3 or 5) and modulus (which is very large, currently recommended length is 2048 bits at least - OpenSSH uses /etc/ssh/moduli file to randomly select these numbers from), and both are exchanged in public. Our focus is on modulus. And yes, you cannot use just any prime number as a modulus, some of them are not suitable and will result in very poor encryption. Unfortunately how that happens is beyond me. Luckily with openssh there is a tool called ssh-keygen, which can be used to generate suitable prime numbers (which you can call "private" since you have generated them yourself, but they are not private in cryptographical sense)

            As for the real private part, that's your random number which has to be generated in a cryptographically secure manner and is never exposed at any point of key exchange. Weak (i.e. predictable) random number generator is another possible weakness of D-H, but it is not discussed in the article. The focus is on potentially compromised by NSA modulus (or moduli, plural) which is deemed to be possible for small e.g. 1024-bit sized prime numbers.

  9. Primus Secundus Tertius

    Who is that sending?

    Diffie-Hellman, as described in the article, does not guarantee who it is at the other end of the line. For a fixed landline circuit that is fine, but not on the packet-switched Internet.There, for something approaching a guarantee, you need public/private keys.

    Then Able sends Baker a proposed key in Baker's public key. Baker returns that key using Able's public key. So each has confirmed the identity of the other.

    Or have I misunderstood?

    1. Chris Miller

      Re: Who is that sending?

      I agree, and if there were a universal registry of trusted public keys and everyone had one, that would be fine. But the purpose of D-H (and similar protocols) is to generate a shared secret key using open messages over a public network, in a situation where at least one party has not implemented asymmetric encryption. It's also useful where one end would like both security and anonymity, often the case on public web services.

      1. Primus Secundus Tertius

        Re: Who is that sending?

        @Chris Miller

        Thanks for that reply.

        On further thought, I realise that D-H is probably initiated by the server. They know it is themselves sending, and are not worried about who is receiving.

      2. Suricou Raven

        Re: Who is that sending?

        DH can prevent interception of communications, but only against a passive intercept. It doesn't work against an active interceptor who can block and spoof packets, as they can simply do a DH exchange with both ends and pass data between them. Solving that problem is a great deal harder, and it's the reason we have to deal with the ugly solution of SSL certification authorities.

        1. Charles 9

          Re: Who is that sending?

          "Solving that problem is a great deal harder, and it's the reason we have to deal with the ugly solution of SSL certification authorities."

          But the problem here is that we know know Trent is being subverted. So how do Alice and Bob attest each other without a trusted third party available?

    2. Charles 9

      Re: Who is that sending?

      Pretty much. BTW we tend to use Alice and Bob. Anyway, D-H can stop a passive threat (Eve) but not an active one (Mallory) who can do MitM and trick one or both into believing they're the other side of the conversation (note this can apply even with keys at the First Contact phase).

    3. John Sanders
      Mushroom

      Re: Who is that sending?

      I have been saying for 20 years that any enterprise system out there should work with public/private before exchanging anything on an open network.

      But yeah, no one will agree on a standard that would work everywhere, and companies of the like of Microsoft, Oracle or Google would try to impose their own version of the standard.

      Heck even OpenSSH is on the process of being subverted by MS.

      1. Bronek Kozicki

        Re: Who is that sending?

        TLS 1.2 (with RC4 disabled) and 1.3 are known to be relatively secure, these are standard encryption protocols supported on all platforms and I very much doubt that OpenSSH developers would allow it to be "subverted" by Microsoft. Your problem is with closed firmware in embedded devices, closed source software from smaller companies etc. where it is very difficult to upgrade cryptography stack. These have to be occasionally upgraded, but if the vendor cannot not be bothered or the hardware is not powerful enough for large keys, you are in trouble.

  10. JeffyPoooh
    Pint

    It's really too bad...

    It's really too bad that the only conceivable key lengths are 1024-bits, 2048-bits, 4096-bits, etc.

    If only we lived in a universe where one could imagine using key lengths of (for example) 1737-bits in length to more optimally trade-off security against hardware/software/battery requirements.

    It's really too bad that it's simply inconceivable.

    I for one could never imagine such a thing.

    Sigh...

    1. Anonymous Coward
      Anonymous Coward

      Re: It's really too bad...

      The problem with your concept is that computers tend to work best with powers of 2. So your 1737-bit implementation would essentially be optimized to be 2048 bits with a bunch of zeroes, significantly reducing the entropy.

      1. JeffyPoooh
        Pint

        Re: It's really too bad...

        Utter bollocks. Just a common mindless assumption with no foundation.

        There's no Earthly reason why THE NUMBER OF BITS has to be a power of two. It would obviously be best if it were an integer number of words. So 1737 is certainly not optimum. That bad example would be implemented as (for example) 27 or 28 64-bit words, or 1728 or 1792 bits.

        It's TRIVIAL to write the code to stop counting at 27 or 28 instead of 32.

        If we need more than 32 words then we "must" count to 64 next? Nonsense!!

        It's very similar to some old computers that used 24 bit words (not 16 and not 32), because that was optimal. Optimized (!!), not sub-optimal.

        You should study how DRAM is made. The lessons there will tune your instincts about word length and help to avoid bad assumptions.

        1. Bronek Kozicki

          Re: It's really too bad...

          @JeffyPoooh I admit I initially thought that you are mistaken. And then I read man ssh-keygen and gmplib documentation, wrote my own D-H exercise key exchange with GMP and I agree, from mathematics point of view there is little reason why exactly 2^N of bits are used. It does seem like failure of imagination.

          However, if you can only spend limited time generating moduli file, this time is better spend generating small number of very large primes, rather than large number of smaller primes - because larger primes are inherently more secure than smaller ones. And if you use small number of (very large) primes, there is no reason not to use 2^N sized ones.

          1. JeffyPoooh
            Pint

            Re: It's really too bad...

            "...no reason..."

            Except El Reg wrote: "Some embedded hardware just won't be able to handle 4096-bit keys; using much larger keys will require greater computational effort, so it will take longer to send and decrypt information, and it will drain a battery faster."

            The obvious answer to the above concerns might be 3072-bit keys. Or 3008-bit. Or 3648. Etc.

            The fixation on strict doubling the number of bits with each increase is obviously sub-optimal.

            1. Bronek Kozicki

              Re: It's really too bad...

              Actually, 3072-bit sized moduli are used (and so are 1536-bit). I admit I have not looked at this part too closely but the difficulty is that during negotiation phase both parties have to agree on size of modulus used and, during this phase, the selection of sizes supported seems to be somewhat limited.

  11. Anonymous Coward
    Anonymous Coward

    Howto

    How to generate >2048 bit DH keys and install in Nginx Apache etc:

    https://weakdh.org/sysadmin.html

    There's also a paper on that site which goes into detail on the problem of lazy implementations using a few precomputed keys. It only takes ~5 minutes to generate a random one. Assuming openssl's key generator isn't flawed...

    1. Anonymous Coward
      Pint

      Re: Howto

      Correction: ~50 minutes for a >4096-bit key

      Perfect pretext for a few -->

  12. John Savard

    The Real Problem

    While the United States is not perfect, particularly in the behavior of some of its state and local officials, it is a responsible member of the family of nations, and a great democracy. So the fact that the NSA can read our mail is not a serious problem that requires immediate action.

    The fact that what the NSA can do, perhaps Russia or China can also do, or soon will be able to do, now, that's worrying.

    Incidentally, there have been recent news stories noting that neither RSA nor ECC is a panacea; longer keys will be needed for them all.

    1. Anonymous Coward
      Anonymous Coward

      Re: The Real Problem

      That's called American "Exceptionalism".

      When Nixon famously said "It's not a crime when the President does it." Same thing. Same insane mindset.

      In some minds, it's inherently "impossible" for the USA Armed Forces to ever commit a war crime. Simply "impossible" because of the mindset.

      Same thing with spying. See above post.

      It's a serious mental illness with global ramifications.

      1. John Savard

        Re: The Real Problem

        It happens to be a fact that people who point out issues that need attention in the United States aren't hauled away into prison camps - the way they are in North Korea or the People's Republic of China, or the way they were in Nazi Germany.

        And Russia's recent aggression against Georgia and the Ukraine, because the people there refused to be ruled by corrupt leaders chummy with Putin, is on record - although, I have to admit, I suppose one could point to parallels of a sort in some of the United States' past dealings with Latin America.

        1. Doctor Syntax Silver badge

          Re: The Real Problem

          John,

          There are some flaws in your argument.

          Just consider the consequences of adding the word "yet" into some of your sentences. How do you stop that "yet" happening?

          Apart from the potential damage to your own society (I conclude from your arguments that you're a US citizen) you need to realise that the rest of the world doesn't trust the US. We don't trust it on a personal level and we don't trust it on a commercial level if a non-US corporation is competing with a US corporation for a sufficiently large chunk of business. The reason we don't trust it is because of its behaviour.

          Finally we don't necessarily trust non-US governments either because this surveillance is usually done without any regard to anything that might pass reasonable scrutiny as due process of law. It's odd that this year your country and mine have both been celebrating the 800th anniversary of Magna Carta at the same time as our governments have been doing their best to ditch its most significant clause.

        2. Anonymous Coward
          Anonymous Coward

          Re: The Real Problem

          "...point out issues..." ?

          "...hauled away into prison camps..." ?

          All they need to do is be of Japanese ethnic origin* in 1942 America !!!!

          (* Even Nth generation citizens.)

          If this is a debate, then you just lost to a chorus of laughter.

    2. Anonymous Coward
      Anonymous Coward

      Re: The Real Problem

      There is also no record of whether Snowden sweetened the deal with Putin by taking one or two of these primes with him on a usb stick. Or, for that matter, whether a completely different insider who didn't make the national news has been secretly radicalised and slipped something to an ISIS supporter.

  13. Anonymous Coward
    Anonymous Coward

    Doesn't matter

    The only information needed is the source of the sender and how is the receiver. Once those are determined encryption doesn't matter, at least by the NSA who have many other tools in their black bag.

  14. Anonymous Coward
    Anonymous Coward

    IANAE (...engineer)

    Why break down the walls when you can unlock the door?

    Forgive me if this is fey, but is it really far-fetched to assume that the TLAs don't have a neat little bypass that involves "tattle-tale" functionality at the chip level? Where is the encryption happening, and why do we trust the integrity of the result?

    c.f. Thomas Reed (1982 - sometimes disputed) and Saberhagen's "Octagon" (admittedly fiction).

    1. JeffyPoooh
      Pint

      Re: IANAE (...engineer)

      Yep.

      Everyone is focused on the key, they fail to notice the lessons of history. It's more often some subtle flaw in the implementation.

      Coders are human. They screw up. In any large chunk of code are dozens of subtle flaws and endless bad assumptions.

      It's very nearly hopeless.

      1. Anonymous Coward
        Anonymous Coward

        Re: IANAE (...engineer)

        Why go after the crypto at all? Just take out the user or the merchant - see TalkTalk. You don't NEED to take out the crypto layer at all ... just walk around it.

        Rule #1 - go after the weakest part of the system, not the strongest ...

      2. Michael Wojcik Silver badge

        Re: IANAE (...engineer)

        Everyone is focused on the key, they fail to notice the lessons of history. It's more often some subtle flaw in the implementation.

        Sigh.

        This is absolutely not true. Most security researchers put quite a lot of resources - time, attention, etc - into examining every aspect of a system, including parameters, algorithms, protocols, implementations, components, users, etc.

        J Random Sophomore in some web forum might be "focused on the key" to the exclusion of all else, but that is most certainly not any more true of public IT security practice (academic, commercial, and in most cases amateur and pro bono as well) than it is of the spy agencies. So are many people who don't assume the label of "security professional" but have some information-security responsibility thrust upon them. I deal with such people frequently, and for the most part they're quite capable of imagining a wide array of viable threats.

        It's rather arrogant for a handful of commentators on the Reg to imagine they have spotted the great oversight of security researchers.

      3. Asterix the Gaul

        Re: IANAE (...engineer)

        "It's more often some subtle flaw in the implementation".

        I wish someone had informed Bill GATES before he released WINDOWS,not so much a subtle 'flaw' as a gaping 'CHASM'.

  15. Old Handle

    Two questions:

    Why move to 2048-bit when the NSA itself recommends 3072-bit? Why no effort to stop reusing primes so much, since that's apparently part of the attack? I get that increasing the length is probably easier, but wouldn't it be sensible to do both?

    1. JeffyPoooh
      Pint

      Re: Two questions:

      "...NSA itself recommends 3072-bit..."

      They still can't avoid the temptation of 'half' steps. :-)

    2. Michael Wojcik Silver badge

      Re: Two questions:

      Why no effort to stop reusing primes so much, since that's apparently part of the attack?

      That's precisely what many people did when WeakDH was first publicized. And yes, it's a good remediation, unless your traffic is very valuable indeed.

  16. Anonymous Coward
    Anonymous Coward

    Any way to tell?

    If I'm connected to someone's VPN, is it possible to find out how many bits their keys use myself?

    1. Anonymous Coward
      Anonymous Coward

      Re: Any way to tell?

      Look at the session negotiation metadata.

      1. Anonymous Coward
        Anonymous Coward

        Re: Any way to tell?

        and where would you find that in OpenVPN?

  17. Anonymous Coward
    Anonymous Coward

    Nothing to hide..

    I of course don't follow the argument 'Nothing to hide. Nothing to fear'. However the resources required to break the encryption used on many VPN's means that you would probably have to be on the NSA radar to begin with for them to take an interest and dedicate so many resources to it. I doubt they just randomly choose a member of Joe Public to snoop on.

    1. Doctor Syntax Silver badge

      Re: Nothing to hide..

      "I of course don't follow the argument 'Nothing to hide. Nothing to fear'."

      You don't? OK, if you've nothing to hide then why not unhide all your logon & security answers for banking, eBay, Amazon or whatever? You could just post them here*.

      As to resources, go back up the thread & read some of the other posts. The significance of this discovery is that once you've done a humungous amount of computation for a commonly used prime it becomes relatively cheap to attack any connection using it so the more that are attacked the cheaper the cost of each. So yes, if you've done the initial work why not look at what that webcam's seeing, what that VOIP call's about, what that person's bank account has in it? It's so easy to just ignore due process of law. But due process of law is the basis of a free country.

      *Or rather, don't. You almost certainly not only have stuff to hide, you also have contractual obligations to hide it.

      1. Michael Wojcik Silver badge

        Re: Nothing to hide..

        OK, if you've nothing to hide then why not unhide all your logon & security answers for banking, eBay, Amazon or whatever? You could just post them here*.

        This is a bogus argument. Security is not meaningful except in the context of a threat model, and if your threat model is so simplistic or skewed that "using a popular DH modulus" and "posting all your account details" are equivalent, then there's really no point in discussing the security of Internet communications at all.

        The OP is quite correct, albeit only under a threat model that needs to be made explicit and most certainly doesn't apply to everyone. The cost of breaking DH communications, even if you're using a popular 1024-bit modulus, is still high. It's believed to still be high for the NSA, and that's a well-founded belief: it's only not true if the NSA either has put absurdly large resources (which could be better spent elsewhere) into breaking DH, or has technology far beyond the public state of the art (which could probably be better used elsewhere).

        So they're going to break communications that they expect are valuable enough to be worth that cost. They can't break everything, so they pick and choose.

        Now, for many people, the cost of remediating their DH communications is low. They just upgrade some software. Maybe they generate a new DH prime or two and configure it somewhere. It's a minor effort with high potential value, so yes, you do it. But the cost of not doing it depends on the value of your data to a handful of very-well-funded attackers.

    2. Anonymous Coward
      Anonymous Coward

      Re: Nothing to hide..

      The problem is that you get the phenonomon of "consolation convictions" where, once you have been shown to be not guilty of a crime, the authorities have a database big enough that they can find some kind of technicality or other to prosecute you over in order to save face. Five years ago you tweeted something while drunk that you instantly deleted but they can exaggerate how bad it was enough to drag you through the court and ruin your reputation, with your eventual acquittal doing nothing to undo the damage.

      1. JeffyPoooh
        Pint

        Re: Nothing to hide..

        re. "consolation convictions"

        Famous book: 'Three Felonies a Day'

        http://www.harveysilverglate.com/books/

  18. david 12 Silver badge

    embedded hardware won't be able to handle 4096-bit

    ... and even if it could, it's not legal to export the stuff except through the hightmare of getting permission for each destination. Not so important for big companies with big local markets, terrible for small companies in Aus.

  19. david 12 Silver badge

    DNA amplification cracking

    20 years ago, encryption cracking by the same methods used for DNA amplification was an interesting research area that attracted several high-profile people. (you add a coded molecule to the mixture, and a high concentration of decoded fragments come out).

    Then, nothing.

    Presumably, it never worked out....

    1. JeffyPoooh
      Pint

      Re: DNA amplification cracking

      OMG!!

      You've just triggered conception of a new technology for key exchange.

      Relatives can use their shared DNA, focusing on the highly variable parts of course, combined with calibrated redundancies in the message (depending on how closely they're related), to perform key exchange. Implementation details are self-evident I think.

      Obvious vulnerability is if they or any of their relatives are ever captured, or shed a hair in public.

    2. Michael Wojcik Silver badge

      Re: DNA amplification cracking

      A number of these analog methods were investigated. Several teams have done things with optics, for example.

      See unusual and physical methods for finding prime numbers.

      Usually these methods seem to prove too cumbersome to generalize. You could use them to factor the occasional large composite, say, but it'd be a movie-plot scenario: "We have to break Dr Evil's session key before the bomb explodes!". They're not really good for "we want to factor these one million large composites".

      That said, I only have a glancing acquaintance with this research, and you should look at the papers linked to from that site if you want the real scoop.

  20. Anonymous Coward
    Anonymous Coward

    I feel so helpless not knowing enough about about security and encryption. I suppose I understand a little of theory and why it is required etc. Wouldn't it be nice if we could make that headache go away and just pay somebody to ensure our communication is as secure as possible.

    E.g. a tax paid agency that ensures citizens communication and data is protected from cyber criminals and other counties spying efforts. If that agancy does not fulfil its mandate - the government in charge -could just dissolve that agency and create a new and better one.

    In this global community various countries just don't trust each other and therefore build up the capability to intercept and decrypt all sorts of communication - in effort to acquire information. That information can either be used for someone's advantage - or someone else's detriment.

    The cold war arms race was a small effort as compared to the information race that's going on right now.

    So we need to have the capability to decrypt the terrorists communication - so we know where they'll strike next. We need the ability to steal trade and engineering secrets - because the others do it, too and we'd be idiots not to do it. We need the capability to remotely shut down infrastructure services or centrifuges in our enemies country. After all we don't need to send soldiers in harms way.

    The problem with building up all this capability is that it can, has been, and will be used against your own citizens. The skill and technology to outdo your enemies and competitors (ideological or commercial) -is the same technology that can be turned against you own people - if used without controls and governance.

    We've reached the point of no return - where even the most technological challenged citizen relies on the Internet to conduct day to day business/ communication/ life. So people don't really have a choice anymore to put on a tinfoil hat or disconnect from the internet. Because it would be their social as well as commercial death.

    The fact that governments need fight terrorists and out do other governments essentially means that personal privacy has become collateral damage.

    You cannot have the capability to spy on other countries without the ability to spy on your own citizens.

    It's all the same.

    So the only thing that can stop this information arms race is government control of the agencies that get paid to protect their citizens.

    The fact that Edward Snowden walked out of the door with all those secrets - means that there was a severe lack of control and governance within that agency. The fact that those agencies feel that they don't need to answer to their government and people is even more concerning.

    Can't we just take all that money and invest it in something that truly benefits mankind ? Not just the few select countries that can afford to produce the most crypto geeks and government funded hackers. After all, Hacking is just the latest method employed to maintain or gain power. (Besides access to oil and weapons of mass destruction).

    The threats to ordinary citizens are overstated, but how else do you get buy in from the masses ?

    People should ask exactly how much money is spent on defensive vs offensive cabability.

    Instead of spending hundreds of millions on cracking DH - why not spending the $$$ on fixing known security loopholes?

    Ah yes quantum computers can be used to aid encryption and the nuclear threat of the cold war - helped keeping peace...

    So let's focus on offensive capabilities. We need bigger sticks.

    1. JeffyPoooh
      Pint

      "I feel so helpless..."

      YouTube channel 'Computerphile' has some great entry level explanations.

      Then to see how hackers hack, surf CCC.de conference videos. Mandatory viewing,especially for over-confident IT "Security" professionals.

      "...a tax paid agency that ensures citizens communication and data is protected..."

      History lesson here: https://en.wikipedia.org/wiki/Clipper_chip

    2. JeffyPoooh
      Pint

      "...so we know where they'll strike next."

      Naïve.

      Basic Nash 'game theory' means that they already know that their electronic communications would be monitored, and they will therefore implement basic 'Art of War' countermeasures, such as feeding the spies false info, a la WWII UK's Double-Cross system.

      "Ah yes quantum computers can be used to aid encryption..."

      Step 1 would be proving conclusively that they *actually* work as advertised. Factoring a long series of huge numbers, one by one, faster than is 'possible' would be a trivial and conclusive proof. Strange that I've not heard that they've actually achieved this simple thing.

      1. Anonymous Coward
        Anonymous Coward

        Re: "...so we know where they'll strike next."

        Because such a breakthrough would be considered as game-changing as a functioning stealth aircraft was 50-some years ago. It would be considered SO valuable as to be rendered "black": no one would acknowledge such a thing even exists. And we know a quantum factoring function already exists: Shor's Algorithm.

        1. Michael Wojcik Silver badge

          Re: "...so we know where they'll strike next."

          And we know a quantum factoring function already exists: Shor's Algorithm.

          For that matter, we've had working QC implementations of it. It's just that no one's found a (feasible) way to build a large enough QC to use it for anything practical.

          The best protocol for applying Shor's to DH, for example, takes 5K+1 qubits, where K is the length of the DH modulus in bits (1024, 2048, etc). I linked to the abstract on arxiv in a previous post here.

          We're a few orders of magnitude away from a 10241-qubit QC, at least in terms of anything that's been made public. Some people think the NSA might have something like that, but I think they're nuts. The NSA mostly employs mathematicians, not physicists and engineers, and if they had the knowledge and resources to build something like that (remember this is something hugely beyond what anyone's done publicly), they almost certainly could find something better to do with them.

          And a big-qubit QC isn't just a matter of scaling up. Noise and decoherence problems apparently get worse faster than linear with these things, though I admit I know very little about the practical details.

  21. Anonymous Coward
    Anonymous Coward

    SOS, DD

    Unless you have something to hide, the NSA or other authorities cracking encryption should be of no concern at all.

  22. Anonymous Coward
    Anonymous Coward

    FIPS 186-4

    So, maybe there is a reason that NIST's FIPS 186-4 specification only lists modulus sizes of 1024, 2048, and 3072, and specifically does NOT list 4096 as an approved size!

    http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

    Is this another case of NIST bowing to NSA pressure to limit the modulus size, perhaps so that it can be hacked by the NSA?!? Otherwise, why would they exclude 4096 bits as a modulus size?

    Anon Y. Mus

  23. glennwestmore

    Some interesting facts and puzzles about Prime Numbers and Magic Squares, Smith Numbers, and Arithmetic and Palindromic Primes on this blog: www.glennwestmore.com.au.

  24. JavaJester

    Shor's algorithm

    Shouldn't there also be an effort to use post quantum cryptography? All the effort to increase keysize will be for naught if a practical quantum computer exists to defeat it.

    1. Charles 9

      Re: Shor's algorithm

      They're working on post-Quantum algorithms using lattices and so on. Thing is, most of them have holes in them.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like