When we launched the challenge we were unsure if private keys could be accessed, but had started the process of revoking and recreating all the SSL private keys that we manage. When the challenge was defeated in a matter of hours it became obvious that it was fairly easy to find the prime numbers that are at the heart of an RSA private key.
Most of the people who obtained the private SSL key of the challenge server did so by searching the results returned in Heartbleed messages for prime numbers. Testing for prime numbers itself is pretty simple (although slow): find a number and see if it has any divisors. Since the length of the prime numbers (in bits) was known it was just a matter of finding all blocks of 1,024 bits and seeing if they were actually a prime.
Finding one prime is enough to break the private SSL key.
The question we wanted to answer was: "Why was it apparently so easy to find prime numbers in Heartbleed results?" To get to the answer I instrumented a vulnerable version of OpenSSL (1.0.1f) and began the search for the primes and where they end up in memory. Strangely, it seemed that OpenSSL was set up to cleanse memory of primes (and other sensitive values) when they were no longer being used. So, what was going on?
But first a detour into the RSA algorithm and how it is implemented efficiently.
The full details of the RSA cryptographic scheme can be read here, but, the short version is that two large prime numbers (almost always called p and q) are chosen and kept secret. The product of those two numbers is referred to as the modulus, typically called N (N = p x q).
It's safe to make N public (it is part of what's called the public key) because it is believed (by mathematicians and computer scientists) that working out p and q from N is difficult (i.e. it is believed that factoring N is hard as long as p and q are very large).
So, when a brower connects to a site that's using SSL it obtains the public key from the site and the site keeps p and q secret. But the site needs p and q to encrypt data and so they are typically (but not always) held in memory of the server handling the web site.
In the Heartbleed attack is was possible to find one of p or q in the Heartbleed packets that were returned containing blocks of memory from the vulnerable server. Since N is public, once you have either of p or q the other can easily be worked out by dividing N by the prime you've found.
Note, that in one Heartbleed attack a researcher used Coppersmith's Attack. That attack is a complex mathematical attack which means that it's possible to split N into p and q if you find just part of a prime number. Read the details of that here.
In practice, the mathematics used in RSA is rather slow and various schemes have been invented to speed it up. One, which is used by OpenSSL, is known as the Montgomery Reduction.
Deep inside RSA the fundamental operation that has to be performed is a multiplication modulo N. If you are not familiar with the term "modulo N", it simply means "divide by N and take the remainder". For example, here's 13 x 29 modulo 11 (which will be 13 x 29 divided by 11 and take the remainder):
This is a very expensive operation for a computer to perform (and in RSA it is performed repeatedly) because it involves multiplication and division (if you remember long division from school you'll remember how laborious it is: computers find it similarly difficult when compared to addition or subtraction).
In 1985, mathematician Peter Montgomery showed that it was possible to perform 'multiplication modulo N' very quickly as follows. At each step the following is performed:
A digit from the left number is multiplied by the right number and added to a temporary variable (usually called an accumulator);
The accumulator is divided by 10 and the decimals are discarded;
If there are digits remaining in the left number then add to the accumulator the number r where r x 11 plus whatever is currently in the accumulator would be divisible by 10.
Move on to the next digit if there is one
For example, 13 x 29 mod 11 can be calculated like this:
Accumulator
0\n87 Added 3 x 29\n8 Divided by 10\n10 Added 2 because 2 x 11 + 8 = 30 (divisible by 10)\n39 Added 1 x 29\n3 Divided by 10
The answer, 3, is in the accumulator. What's important here is that only 'easy' calculations were performed: small multiplications by a single digit and division by 10. In the computer implementation all of this is done in binary with division by 2 instead of 10. Division by 2 is very, very easy to implement on a computer.
To understand how primes are used inside OpenSSL I instrumented the code to output information about all the memory allocated by OpenSSL and to highlight blocks of memory used for prime numbers. I then processed this information using a small program to produce a picture of memory.
Here's the state of the memory used by OpenSSL when running inside NGINX 1.5.13 just after it has started up. Green blocks are memory in use, black areas are unused and the two red bars are the two primes number p and q that form part of the RSA key.
Each row of the picture is 1,024 bytes. The picture shows a total of about 280KB of memory in use. The primes are being stored in a single location (delving into the source of OpenSSL this is the location of the primes when loaded in the function ssl_set_pkey in ssl_rsa.c).
\n \n \n \n \n
In contrast, something interesting has happen when NGINX/OpenSSL processes its first request. A second copy of the primes has appeared. OpenSSL is now using more memory and two long red lines (two complete primes) are in memory along with some fragments of prime numbers that have been partially overwritten (those are vulnerable to Coppersmith's Attack).
\n \n \n \n \n
Delving into the code once more it becomes apparent that the two new primes are copies of p and q made for the Montgomery reduction code in bn_mont.c. The fragments of primes are left over from where p and q were used in calculations.
After ten identical requests the memory layout has changed a little more. The fragments of primes have been overwritten, but the Montgomery reduction copies are still there. And some new fragments have appeared.
\n \n \n \n \n
After running a more realistic simulated load through the web server the memory has grown and most of the prime fragments have been overwritten leaving the original primes and the Montgomery reduction primes in memory.
\n \n \n \n \n
To get a sense of how OpenSSL copies the primes around, here's a slightly different visualization. It shows all the memory that stored primes in red (whether or not it was later overwritten). As you can see OpenSSL is making copies of the primes all over its memory space.
\n \n \n \n \n
And therein lies the heart of Heartbleed: there are two copies of the primes that never move (the original location where they are loaded and the location of the Montgomery reduction copy) and lots of temporary copies of the primes all over OpenSSL's memory.
This patch fixes a problem where the bn_expand2 function in bn_lib.c freed memory potentially containing a prime without erasing it first. The patch adds a call to the OPENSSL_cleanse function that safely erases the number from memory before freeing it. The patch ensures the memory is cleaned up. It was sent to the OpenSSL team on April 19 and independently discovered by Rubin Xu.
This particular function is the cause of primes left in freed memory. Whenever OpenSSL needed to resize a number stored in one of its special BIGNUM structures it would free the now too small BIGNUM without erasing the memory.
That alone is not enough to prevent Heartbleed from getting the primes as there are other copies in memory. In testing, I found that the Montgomery reduction primes were particuarly easy to extract using Heartbleed messages. To prevent them from being created its possible to disable caching of the Montgomery parameters by removing the RSA_FLAG_CACHE_PRIVATE in eng_rsax.c (a similar flag exists in rsa_eay.c.
The Montgomery code also doesn't clean up memory that it frees. The following patch corrects that problem.
BN_clear_free(&(mont->Ni));\nif (mont->flags & BN_FLG_MALLOCED)\nOPENSSL_free(mont);\n}
Finally, there's always the possibility that the original location the primes were in might get exposed in a Heartbleed message. To protect against that it would be necessary to change the way OpenSSL memory is allocated so that memory allocated for sensitive data (like private keys) is kept far away from the memory buffers used for messages. A patch for this has been submitted to OpenSSL.
A more radical solution is to not store the private keys inside OpenSSL at all. If the private key is not stored in the same process as OpenSSL it will not be accessible via a fault like Heartbleed.
CloudFlare is already testing that configuration. More on that in another blog post.
PS I am very grateful for Matthew Arcus for corresponding with me about this and checking some of my assertions. It was Matthew who first pointed out that the Montgomery Reduction was another source of leaked primes.
"],"published_at":[0,"2014-04-27T23:00:00.000+01:00"],"updated_at":[0,"2024-10-10T00:40:01.226Z"],"feature_image":[0,"https://cf-assets.www.cloudflare.com/zkvhlag99gkb/4lPKgNDjRS2f7pTWXkQIIh/aea6f3e6f315b08869ec7a8b42001d44/searching-for-the-prime-suspect-how-heartbleed-leaked-private-keys.jpg"],"tags":[1,[[0,{"id":[0,"56vA0Z6hqev6QaJBQmO2J8"],"name":[0,"TLS"],"slug":[0,"tls"]}],[0,{"id":[0,"5US4l4wdDysuDpZ4ktL3yP"],"name":[0,"HTTPS"],"slug":[0,"https"]}],[0,{"id":[0,"2fnCQE8RAlAe4IVUpITe58"],"name":[0,"OpenSSL"],"slug":[0,"openssl"]}],[0,{"id":[0,"2pFyOCtANFB5qS6nbtQbVp"],"name":[0,"Vulnerabilities"],"slug":[0,"vulnerabilities"]}],[0,{"id":[0,"6Mp7ouACN2rT3YjL1xaXJx"],"name":[0,"Security"],"slug":[0,"security"]}]]],"relatedTags":[0],"authors":[1,[[0,{"name":[0,"John Graham-Cumming"],"slug":[0,"john-graham-cumming"],"bio":[0,null],"profile_image":[0,"https://cf-assets.www.cloudflare.com/zkvhlag99gkb/5vGNsXzZrtSLn2X30pnpUY/6f350e7dd36058a6422f9199b452bb02/john-graham-cumming.jpg"],"location":[0,"Lisbon, Portugal"],"website":[0,null],"twitter":[0,null],"facebook":[0,null]}]]],"meta_description":[0,null],"primary_author":[0,{}],"localeList":[0,{"name":[0,"Searching for The Prime Suspect: How Heartbleed Leaked Private Keys Config"],"enUS":[0,"English for Locale"],"zhCN":[0,"No Page for Locale"],"zhHansCN":[0,"No Page for Locale"],"zhTW":[0,"No Page for Locale"],"frFR":[0,"No Page for Locale"],"deDE":[0,"No Page for Locale"],"itIT":[0,"No Page for Locale"],"jaJP":[0,"No Page for Locale"],"koKR":[0,"No Page for Locale"],"ptBR":[0,"No Page for Locale"],"esLA":[0,"No Page for Locale"],"esES":[0,"No Page for Locale"],"enAU":[0,"No Page for Locale"],"enCA":[0,"No Page for Locale"],"enIN":[0,"No Page for Locale"],"enGB":[0,"No Page for Locale"],"idID":[0,"No Page for Locale"],"ruRU":[0,"No Page for Locale"],"svSE":[0,"No Page for Locale"],"viVN":[0,"No Page for Locale"],"plPL":[0,"No Page for Locale"],"arAR":[0,"No Page for Locale"],"nlNL":[0,"No Page for Locale"],"thTH":[0,"No Page for Locale"],"trTR":[0,"No Page for Locale"],"heIL":[0,"No Page for Locale"],"lvLV":[0,"No Page for Locale"],"etEE":[0,"No Page for Locale"],"ltLT":[0,"No Page for Locale"]}],"url":[0,"https://blog.cloudflare.com/searching-for-the-prime-suspect-how-heartbleed-leaked-private-keys"],"metadata":[0,{"title":[0],"description":[0],"imgPreview":[0,""]}]}],"translations":[0,{"posts.by":[0,"By"],"footer.gdpr":[0,"GDPR"],"lang_blurb1":[0,"This post is also available in {lang1}."],"lang_blurb2":[0,"This post is also available in {lang1} and {lang2}."],"lang_blurb3":[0,"This post is also available in {lang1}, {lang2} and {lang3}."],"footer.press":[0,"Press"],"header.title":[0,"The Cloudflare Blog"],"search.clear":[0,"Clear"],"search.filter":[0,"Filter"],"search.source":[0,"Source"],"footer.careers":[0,"Careers"],"footer.company":[0,"Company"],"footer.support":[0,"Support"],"footer.the_net":[0,"theNet"],"search.filters":[0,"Filters"],"footer.our_team":[0,"Our team"],"footer.webinars":[0,"Webinars"],"page.more_posts":[0,"More posts"],"posts.time_read":[0,"{time} min read"],"search.language":[0,"Language"],"footer.community":[0,"Community"],"footer.resources":[0,"Resources"],"footer.solutions":[0,"Solutions"],"footer.trademark":[0,"Trademark"],"header.subscribe":[0,"Subscribe"],"footer.compliance":[0,"Compliance"],"footer.free_plans":[0,"Free plans"],"footer.impact_ESG":[0,"Impact/ESG"],"posts.follow_on_X":[0,"Follow on X"],"footer.help_center":[0,"Help center"],"footer.network_map":[0,"Network Map"],"header.please_wait":[0,"Please Wait"],"page.related_posts":[0,"Related posts"],"search.result_stat":[0,"Results {search_range} of {search_total} for {search_keyword}"],"footer.case_studies":[0,"Case Studies"],"footer.connect_2024":[0,"Connect 2024"],"footer.terms_of_use":[0,"Terms of Use"],"footer.white_papers":[0,"White Papers"],"footer.cloudflare_tv":[0,"Cloudflare TV"],"footer.community_hub":[0,"Community Hub"],"footer.compare_plans":[0,"Compare plans"],"footer.contact_sales":[0,"Contact Sales"],"header.contact_sales":[0,"Contact Sales"],"header.email_address":[0,"Email Address"],"page.error.not_found":[0,"Page not found"],"footer.developer_docs":[0,"Developer docs"],"footer.privacy_policy":[0,"Privacy Policy"],"footer.request_a_demo":[0,"Request a demo"],"page.continue_reading":[0,"Continue reading"],"footer.analysts_report":[0,"Analyst reports"],"footer.for_enterprises":[0,"For enterprises"],"footer.getting_started":[0,"Getting Started"],"footer.learning_center":[0,"Learning Center"],"footer.project_galileo":[0,"Project Galileo"],"pagination.newer_posts":[0,"Newer Posts"],"pagination.older_posts":[0,"Older Posts"],"posts.social_buttons.x":[0,"Discuss on X"],"search.icon_aria_label":[0,"Search"],"search.source_location":[0,"Source/Location"],"footer.about_cloudflare":[0,"About Cloudflare"],"footer.athenian_project":[0,"Athenian Project"],"footer.become_a_partner":[0,"Become a partner"],"footer.cloudflare_radar":[0,"Cloudflare Radar"],"footer.network_services":[0,"Network services"],"footer.trust_and_safety":[0,"Trust & Safety"],"header.get_started_free":[0,"Get Started Free"],"page.search.placeholder":[0,"Search Cloudflare"],"footer.cloudflare_status":[0,"Cloudflare Status"],"footer.cookie_preference":[0,"Cookie Preferences"],"header.valid_email_error":[0,"Must be valid email."],"search.result_stat_empty":[0,"Results {search_range} of {search_total}"],"footer.connectivity_cloud":[0,"Connectivity cloud"],"footer.developer_services":[0,"Developer services"],"footer.investor_relations":[0,"Investor relations"],"page.not_found.error_code":[0,"Error Code: 404"],"search.autocomplete_title":[0,"Insert a query. Press enter to send"],"footer.logos_and_press_kit":[0,"Logos & press kit"],"footer.application_services":[0,"Application services"],"footer.get_a_recommendation":[0,"Get a recommendation"],"posts.social_buttons.reddit":[0,"Discuss on Reddit"],"footer.sse_and_sase_services":[0,"SSE and SASE services"],"page.not_found.outdated_link":[0,"You may have used an outdated link, or you may have typed the address incorrectly."],"footer.report_security_issues":[0,"Report Security Issues"],"page.error.error_message_page":[0,"Sorry, we can't find the page you are looking for."],"header.subscribe_notifications":[0,"Subscribe to receive notifications of new posts:"],"footer.cloudflare_for_campaigns":[0,"Cloudflare for Campaigns"],"header.subscription_confimation":[0,"Subscription confirmed. Thank you for subscribing!"],"posts.social_buttons.hackernews":[0,"Discuss on Hacker News"],"footer.diversity_equity_inclusion":[0,"Diversity, equity & inclusion"],"footer.critical_infrastructure_defense_project":[0,"Critical Infrastructure Defense Project"]}]}" ssr="" client="load" opts="{"name":"PostCard","value":true}" await-children="">
Within a few hours of CloudFlare launching its Heartbleed Challenge the truth was out. Not only did Heartbleed leak private session information (such as cookies and other data that SSL should have been protecting), but the crown jewels of an HTTPS web server were also vulnerable....
A quick followup to our last blog post on our decision to reissue and revoke all of CloudFlare's customers' SSL certificates. One question we've received is why we didn't just reissue and revoke all SSL certificates as soon as we got word about the Heartbleed vulnerability?...
Eleven days ago the Heartbleed vulnerability was publicly announced. Last Friday, we issued the CloudFlare Challenge: Heartbleed and simultaneously started the process of revoking and reissuing all the SSL certificates....
As you may have noticed, the CloudFlare Heartbleed Challenge has been solved. The private key for the site cloudflarechallenge.com has been obtained by several authorized attackers via the Heartbleed exploit....
Today a new vulnerability was announced in OpenSSL 1.0.1 that allows an attacker to reveal up to 64kB of memory to a connected client or server (CVE-2014-0160). We fixed this vulnerability last week before it was made public. ...
This blog post is dedicated to the memory of Dr. Scott Vanstone, popularizer of elliptic curve cryptography and inventor of the ECDSA algorithm. He passed away on March 2, 2014....
At CloudFlare, we are always looking for ways to improve the security of our customers’ websites. One of the features we provide is the ability to serve their website encrypted over SSL/TLS. ...
It’s common knowledge that domain sharding, where the resources in a web page are shared across different domains (or subdomains), is a good thing. ...
At CloudFlare, we are always looking for better ways to secure the data we’re entrusted with. This means hardening our system against outside threats such as hackers, but it also means protecting against insider threats. ...
Elliptic Curve Cryptography (ECC) is one of the most powerful but least understood types of cryptography in wide use today. At CloudFlare, we make extensive use of ECC to secure everything from our customers' HTTPS connections to how we pass data between our data centers....
CloudFlare makes extensive use of TLS connections throughout our
service which makes staying on top of the latest news about security problems with TLS a priority. We use TLS both externally and internally and different uses of TLS have different constraints....
CloudFlare often gets early word of new vulnerabilities before they are released. Last week we got word that today (Monday, February 4, 2013) there would be a new SSL vulnerability announced. ...
A little over a month ago, we published a couple of blog posts about how we were making SSL faster. Specifically, we enabled OCSP stapling across our network....
We've been thinking about how to best implement two-factor authentication to better protect our customers' accounts for quite some time now. When, about 6 months ago, my account was targeted by hackers the importance of a good account security became clear. ...
With web performance and security being the core of CloudFlare, we are always looking for ways to improve not just our customers' website security, but their account security as well. Therefore, we are excited to now offer two-factor authentication for all CloudFlare accounts....
HTTP, the protocol of the web, is unencrypted by default. That means it is trivial for someone using the same local network as you to spy on all the data you send to and receive from most websites. ...
In 2009, Google began work on a new network protocol to make web pages faster. Dubbed SPDY (pronounced "speedy"), the protocol is designed to solve many of the bottlenecks that slow HTTP down. Beginning today, we're rolling out a beta of SPDY to CloudFlare customers. ...
For some time, the vast majority of the web has been vulnerable to the so-called BEAST SSL attack. The attack was first demonstrated in 2011, and more than 90% of the Internet including large sites like Google.com remain vulnerable to their SSL sessions being decrypted....
SSL today is too hard. While it's something every website should support, even for the technically savvy, getting a SSL certificate properly installed on your web server can be daunting. Moreover, several platforms like Google AppEngine don't fully support SSL so it's not a possi...