Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Tuesday July 09 2019, @06:46PM   Printer-friendly
from the it's-complicated dept.

Researcher Ben Perez has written that it is time to stop using RSA[*] encryption. He goes into some of the problems with the algorithm and its supporting code bases, how bad they are, some of the mitigations, and then explains his conclusion. Curve25519 is being recommended instead.

RSA was an important milestone in the development of secure communications, but the last two decades of cryptographic research have rendered it obsolete. Elliptic curve algorithms for both key exchange and digital signatures were standardized back in 2005 and have since been integrated into intuitive and misuse-resistant libraries like libsodium. The fact that RSA is still in widespread use today indicates both a failure on the part of cryptographers for not adequately articulating the risks inherent in RSA, and also on the part of developers for overestimating their ability to deploy it successfully.

The security community needs to start thinking about this as a herd-immunity problem—while some of us might be able to navigate the extraordinarily dangerous process of setting up or implementing RSA, the exceptions signal to developers that it is in some way still advisable to use RSA. Despite the many caveats and warnings on StackExchange and Github READMEs, very few people believe that they are the ones who will mess up RSA, and so they proceed with reckless abandon. Ultimately, users will pay for this. This is why we all need to agree that it is flat out unacceptable to use RSA in 2019. No exceptions.

[*] RSA:

(Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the "factoring problem". The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.

However, many systems and hardware tokens are still hardcoded for RSA. So upgrading is not as easy a task as it could be.

Where have you been able to migrate from RSA? Where have there been obstacles?

Earlier on SN:
Mathematicians Seal Backdoor to Breaking RSA Encryption (2018)
Upgrade Your SSH Keys (2016)
512-bit RSA Keys Cracked in Four Hours for only $75 (2015)
NSA and RSA - Claims of More Evidence (2014)


Original Submission

Related Stories

NSA and RSA - Claims of More Evidence 11 comments

Blackmoore and gishzida both write:

A Reuters story claims that a group of professors from Johns Hopkins, the University of Wisconsin, the University of Illinois and elsewhere now say they have discovered that a second NSA tool exacerbated the RSA software's vulnerability. The professors found that the tool, known as the "Extended Random" extension for secure websites, could help crack a version of RSA's Dual Elliptic Curve software tens of thousands of times faster. From the story:

While Extended Random was not widely adopted, the new research sheds light on how the NSA extended the reach of its surveillance under cover of advising companies on protection.

RSA, now owned by EMC Corp, did not dispute the research when contacted by Reuters for comment. The company said it had not intentionally weakened security on any product and noted that Extended Random did not prove popular and had been removed from RSA's protection software in the last six months. "We could have been more skeptical of NSA's intentions," RSA Chief Technologist Sam Curry told Reuters. "We trusted them because they are charged with security for the U.S. government and U.S. critical infrastructure." Curry declined to say if the government had paid RSA to incorporate Extended Random in its BSafe security kit, which also housed Dual Elliptic Curve.

An NSA spokeswoman declined to comment on the study or the intelligence agency's motives in developing Extended Random.

NCommander adds: This was also submitted by chloride, who added this note:

Interestingly, OpenSSL would be very vulnerable to attack, were it not for an easily-fixed bug that prevented the library from running if Dual EC was enabled. Also interesting, one of the authors of Extended Random, Eric Rescorla, works at Mozilla and is a member of the Web Applications Security Working Group at W3C.

512-bit RSA Keys Cracked in Four Hours for only $75 34 comments

Just recently, I moved my personal website to HTTPS, making sure to use a secure 2048-bit RSA key and TLS 1.2, and guarding against vulnerabilities such as POODLE and Logjam. It took some work, but not that much work, even for doing the research. Yet there are some people who just don't care.

Due to a new technique, 512-bit keys are now completely vulnerable for as little as $75.

The technique, which uses Amazon's EC2 cloud computing service, is described in a paper published last week titled Factoring as a Service .

[...] The researchers concluded that despite widespread awareness that 512-bit keys are highly susceptible to breaking, the message still hasn't adequately sunk in with many administrators. The researchers wrote:

512-bit RSA has been known to be insecure for at least fifteen years, but common knowledge of precisely how insecure has perhaps not kept pace with modern technology. We build a system capable of factoring a 512-bit RSA key reliably in under four hours. We then measure the impact of such a system by surveying the incidence of 512-bit RSA in our modern cryptographic infrastructure, and find a long tail of too-short public keys and export-grade cipher suites still in use in the wild. These numbers illustrate the challenges of keeping an aging Internet infrastructure up to date with even decades-old advances in cryptanalysis.

The article reports finding a significant number of sites that are still using 512-bit RSA keys to protect HTTPS, DNSSEC, ssh, e-mail (SMTP, POP3, and IMAP), and other services.


Original Submission

Upgrade Your SSH Keys 24 comments

Arthur T Knackerbracket has found the following story:

Whether you're a software developer or a sysadmin, I bet you're using SSH keys. Pushing your commits to Github or managing your Unix systems, it's best practice to do this over SSH with public key authentication rather than passwords. However, as time flies, many of you are using older keys and not aware of the need to generate fresh ones to protect your privates much better. In this post I'll demonstrate how to transition to an Ed25519 key smoothly, why you would want this and show some tips and tricks on the way there.

If you've created your key more than about four years ago with the default options it's probably insecure (RSA < 2048 bits). Even worse, I've seen tweeps, colleagues and friends still using DSA keys (ssh-dss in OpenSSH format) recently. That's a key type similar to RSA, but limited to 1024 bits size and therefore recommended against for a long time. It's plainly insecure and refused for valid reasons in recent OpenSSH versions (see also the changelog for 7.0).

The sad thing about it is that I see posts on how to re-enable DSA key support rather than moving to a more secure type of key. Really, it's unwise to follow instructions to change the configuration for PubkeyAcceptedKeyTypes or HostKeyAlgorithms (host keys are for a later post). Instead, upgrade your keys!

Compare DSA with the technology of locks using keys like this one. You wouldn't want this type of key to unlock your front door, right?

List all your keys:

You're probably thinking... "I'm using my key for a long time, I don't want to change them everywhere now." Valid point, but you don't have to! It's good to know you can have multiple keys on your system and your SSH client will pick the right one for the right system automatically.

It's part of the SSH protocol that it can offer multiple keys and the server picks the one your client will have to prove it has possession of the private key by a challenge. See it in action adding some verbosity to the SSH connect command (-vvv). Also if you're using an SSH agent you can load multiple keys and it will discover them all. Easy as that.


Original Submission

Mathematicians Seal Backdoor to Breaking RSA Encryption 9 comments

From Quantamagazine

Digital security depends on the difficulty of factoring large numbers. A new proof shows why one method for breaking digital encryption won't work.

Virtually all polynomials of a certain type are "prime," meaning they can't be factored.

The proof has implications for many areas of pure mathematics. It's also great news for a pillar of modern life: digital encryption.

The main technique we use to keep digital information secure is RSA encryption. It's a souped-up version of the encryption scheme a seventh grader might devise to pass messages to a friend: Assign a number to every letter and multiply by some secretly agreed-upon key. To decode a message, just divide by the secret key.

Quite a statement by the researchers. This allegedly makes RSA encryption "quantum proof", and if so means that classical encryption may still be with us long after quantum computing arrives. Given that quantum systems require expensive entanglement setups, it may also mean that a cheap encryption method may stay viable.

Paper: Irreducibility of random polynomials of large degree


Original Submission

This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
(1)
  • (Score: 2, Insightful) by Anonymous Coward on Tuesday July 09 2019, @07:18PM

    by Anonymous Coward on Tuesday July 09 2019, @07:18PM (#865108)

    >> RSA is an intrinsically fragile cryptosystem containing countless foot-guns which the average software engineer cannot be expected to avoid.
    And eliptic curves are even worse
    >>and its poor performance compels developers to take risky shortcuts.
    Because we're on 2um process node and performance matters, look how streamlined and optimized are modern operating systems to see how important this is (not at all if anyone missed sarcasm)
    >>While it may be theoretically possible to implement RSA correctly, decades of devastating attacks have proven that such a feat may be unachievable in practice.
    in practice 46 Delta Charlie Easy Alpha Delta 3 17 Foxtrot Easy 45 D8 09 23 EB 97 E4 95 64 10 D4 CD B2 C2
    >>So what should you use instead?
    You should use ECC and raw output of intel RDRAND (the backdored one) for S values because your smartcard with 70s micro performance will have good rng or something

  • (Score: 5, Insightful) by Anonymous Coward on Tuesday July 09 2019, @07:20PM (1 child)

    by Anonymous Coward on Tuesday July 09 2019, @07:20PM (#865111)

    The entire premise of this article seems to be because RSA is easier to implement, more people do it and therefore there are more bad implementations. It also mentions that RSA is slow so this encourages implementors to take shortcuts, leading to yet more bad implementations. This means developers are more likely to choose (or roll their own) vulnerable implementations.

    On the other hand "moon math" (term used in TFA) elliptic-curve cryptography is harder to implement so there are fewer implementations. This means developers are more likely to choose good implementations.

    The most egregious "bad implementation" examples presented in TFA is implementors generating keys with low entropy and failing to use modern padding schemes like OAEP.

    But it's easy to implement elliptic-curve cryptography badly too, (such as generating the ECDSA per-message parameters with bad RNGs *cough*sony*cough*), so this argument seems kind of silly. If you can't convince someone to pick a reasonable implementation for a protocol they are already using how the hell are you going to convince them to pick a reasonable implementation for an entirely different protocol?

    And let's not even start with interoperability issues, which are usually more important requirements than actual security concerns.

    • (Score: 5, Insightful) by ikanreed on Tuesday July 09 2019, @08:01PM

      by ikanreed (3164) Subscriber Badge on Tuesday July 09 2019, @08:01PM (#865125) Journal

      And it won't matter because while breaking your key is O(2000 years) breaking your dumbass users is O(free amazon gift card sign in here)

  • (Score: 2) by The Mighty Buzzard on Tuesday July 09 2019, @10:22PM

    You're not the boss of me.

    --
    My rights don't end where your fear begins.
  • (Score: 1) by hwertz on Tuesday July 09 2019, @11:37PM (3 children)

    by hwertz (8141) on Tuesday July 09 2019, @11:37PM (#865201)

    Saying RSA is bad, but recommending elliptic curve? There've been widespread rumors of NSA involvement in making sure elliptic curve crypto systems are weaker than they should be, ranging from "NSA tried to make suggestions, which were rejected" to "the default curves are weak" to full-on "elliptic curve crypto is backdoored."

    • (Score: 0) by Anonymous Coward on Wednesday July 10 2019, @03:22AM (1 child)

      by Anonymous Coward on Wednesday July 10 2019, @03:22AM (#865272)

      Good ol' 25519. I knew that number looked familiar. https://en.wikipedia.org/wiki/Curve25519 [wikipedia.org]

      Curve25519 was first released by Daniel J. Bernstein in 2005, but interest increased considerably after 2013 when it was discovered that the NSA had potentially implemented a backdoor into Dual_EC_DRBG. While not directly related, suspicious aspects of the NIST's P curve constants led to concerns that the NSA had chosen values that gave them an advantage in factoring public keys.

      I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

      — Bruce Schneier, The NSA Is Breaking Most Encryption on the Internet (2013)

      Since then, Curve25519 has become the de facto alternative to P-256, and is used in a wide variety of applications. Starting in 2014, OpenSSH defaults to Curve25519-based ECDH. Behavior for general SSH protocol is still being standardized as of 2018.

      @trailofbits Seriously, stop recommending Curve25519!

      • (Score: 0) by Anonymous Coward on Wednesday July 10 2019, @05:14PM

        by Anonymous Coward on Wednesday July 10 2019, @05:14PM (#865431)

        Curve25519 is not the same as the NSA-pwned Dual_EC_DRBG

    • (Score: 3, Interesting) by stormwyrm on Wednesday July 10 2019, @08:43AM

      by stormwyrm (717) on Wednesday July 10 2019, @08:43AM (#865317) Journal

      I did a little bit of research on what exactly seems to be the skinny with the RSA and elliptic curve cryptography, and came across a very interesting article [iacr.org] by other than Neal Koblitz and Alfred J. Menezes, Koblitz being one of the two people credited with inventing elliptic curve cryptography in the 1980s. In 2015, the NSA released a statement [archive.org] that showed that due to concerns about advances in quantum computers they were not recommending that people make the transition to use of ECC-based cryptosystems:

      Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.

      Koblitz and Menezes speculate as to the true reasons for the NSA's sudden change after energetically pushing ECC for years before then. My vote is on the sixth possibility they present (5.6), that the NSA has a political need to distance itself from ECC. They lost a lot of trust and credibility by pushing the infamous Dual_EC_DRBG kleptographic system, and they anticipated that anything further that they tried to say about ECC standards would be tainted by the same mistrust. We can see exactly that in the many reactions to this article.

      --
      Numquam ponenda est pluralitas sine necessitate.
  • (Score: 3, Interesting) by stormwyrm on Tuesday July 09 2019, @11:41PM (1 child)

    by stormwyrm (717) on Tuesday July 09 2019, @11:41PM (#865204) Journal

    The security of elliptic curve cryptography depends on the fact that the algebraic groups used for it have a structure such that the relatively more efficient algorithms known for computing discrete logarithms don't seem to work for them, so you can get away with much smaller key sizes. Given the known state of mathematical knowledge, a 256-bit ECC key appears to have the same level of security as a 3072-bit RSA key. However, if some smart mathematician somewhere (perhaps one employed by an intelligence agency somewhere) figures out an algorithm that is able to compute discrete logarithms over elliptic curve groups with the same level of efficiency as those over other groups then this advantage to elliptic curve cryptography goes out the window, and that 256-bit EC modulus might then actually be just as secure as a 256-bit RSA key, i.e. not at all. I rate the possibility of this someday happening as somewhat higher than someone finding a polynomial-time factoring algorithm (which would, by the way, also kill ECC just as dead as it would kill RSA).

    The other thing is that Shor's algorithm can also be used to compute discrete logarithms, and the complex structure of an elliptic curve group that troubles the known classical algorithms doesn't seem to matter as much to the quantum algorithm. Computing a discrete logarithm for a 256-bit elliptic curve modulus with Shor's algorithm seems to require around 2330 qubits [arxiv.org], while factoring a 3072-bit RSA key will require around 6146 qubits. We really need to move to some other post-quantum algorithm instead.

    --
    Numquam ponenda est pluralitas sine necessitate.
    • (Score: 2) by takyon on Tuesday July 09 2019, @11:45PM

      by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Tuesday July 09 2019, @11:45PM (#865206) Journal

      A breakthrough could rapidly scale systems from hundreds directly to millions of qubits, since decades of nanolithography research apply.

      Still, it would be funny to see some 8,192-bit and 16,384-bit RSA keys being used before the end.

      --
      [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
  • (Score: 0) by Anonymous Coward on Wednesday July 10 2019, @03:56AM

    by Anonymous Coward on Wednesday July 10 2019, @03:56AM (#865277)
    Why is this story even here?
(1)