10.16.13

Gemini version available ♊︎

Linux Backdoors Revisited (New Revelations and Old Revelations)

Posted in GNU/Linux, Kernel, Security at 10:43 am by Dr. Roy Schestowitz

Claude Elwood Shannon, the man who introduced entropy

Claude Elwood Shannon

Summary: An anonymous backdooring attempt against Linux goes a decade back, but a randomisation problem in today’s Linux also seems possible (subverting encryption)

Jonathan Allen wrote this article about an incident mentioned also by Freedom to Tinker. Slashdot’s summary goes like this, documenting news from one decade ago:

“Ed Felton writes about an incident, in 2003, in which someone tried to backdoor the Linux kernel. Back in 2003 Linux used BitKeeper to store the master copy of the Linux source code. If a developer wanted to propose a modification to the Linux code, they would submit their proposed change, and it would go through an organized approval process to decide whether the change would be accepted into the master code. But some people didn’t like BitKeeper, so a second copy of the source code was kept in CVS. On November 5, 2003, Larry McAvoy noticed that there was a code change in the CVS copy that did not have a pointer to a record of approval. Investigation showed that the change had never been approved and, stranger yet, that this change did not appear in the primary BitKeeper repository at all. Further investigation determined that someone had apparently broken in electronically to the CVS server and inserted a small change to wait4: ‘if ((options == (__WCLONE|__WALL)) && (current->uid = 0)) …’ A casual reading makes it look like innocuous error-checking code, but a careful reader would notice that, near the end of the first line, it said ‘= 0′ rather than ‘== 0′ so the effect of this code is to give root privileges to any piece of software that called wait4 in a particular way that is supposed to be invalid. In other words it’s a classic backdoor. We don’t know who it was that made the attempt—and we probably never will. But the attempt didn’t work, because the Linux team was careful enough to notice that that this code was in the CVS repository without having gone through the normal approval process. ‘Could this have been an NSA attack? Maybe. But there were many others who had the skill and motivation to carry out this attack,’ writes Felton. ‘Unless somebody confesses, or a smoking-gun document turns up, we’ll never know.’”

Backdoors in Linux are a subject for jokes in Torvalds' mind, but given the above we should take this subject very seriously. In any system, for example, having no mechanism for randomness (like in some embedded devices) typically means that strong encryption (with high entropy) is not possible. Given new alleged “insecurities in the Linux /dev/random,” as Bruce Schneier put it, Linux backdoors seem possible again. David Benfell said:

I’m guessing Schneier knows what the fuck he’s talking about. If it is the same vulnerability, then Torvalds’ defense is that the vulnerable source of entropy is only one of many. But if I read Schneier correctly, the result was still too predictable.

“On the other hand,” says Benfell, “here’s Theodore T’so from the comments:”

So I’m the maintainer for Linux’s /dev/random driver. I’ve only had a chance to look at the paper very quickly, and I will at it more closely when I have more time, but what the authors of this paper seem to be worried about is not even close to the top of my list in terms of things I’m worried about.

First of all, the paper is incorrect in some minor details; the most significant error is its (untrue) claim that we stop gathering entropy when the entropy estimate for a given entropy pool is “full”. Before July 2012, we went into a trickle mode where we only took in 1 in 096 values. Since then, the main way that we gather entropy, which is via add_interrupt_randomness(), has no such limit. This means that we will continue to collect entropy even if the input pool is apparently “full”.

This is critical, because *secondly* their hypothetical attacks presume certain input distributions which have an incorrect entropy estimate —| that is, either zero actual entropy but a high entropy estimate, or a high entropy, but a low entropy estimate. There has been no attempt by the paper’s authors to determine whether the entropy gathered by Linux meets either of their hypothetical models, and in fact in the “Linux Pseudorandom Number Generator Revisited”[1], the analysis showed that our entropy estimator was actually pretty good, given the real-life inputs that we are able to obtain from an actual running Linux system.

[1]http://eprint.iacr.org/2012/251.pdf

The main thing which I am much more worried about is that on various embedded systems, which do not have a fine-grained clock, and which is reading from flash which has a much more deterministic timing for their operations, is that when userspace tries to generate long-term public keys immediately after the machine is taken out of the box and plugged in, that there isn’t a sufficient amount of entropy, and since most userspace applications use /dev/urandom since they don’t want to block, that they end up with keys that aren’t very random. We had some really serious problems with this, which was written up in the “Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices” [2]paper, and the changes made in July 2012 were specifically designed to address these worries.

[2]https://www.factorable.net/paper.html

However, it may be that on certain systems, in particular ARM and MIPS based systems, where a long-term public key is generated very shortly after the first power-on, that there’s enough randomness that the techniques used in [2]would not find any problems, but that might be not enough randomness to prevent our friends in Fort Meade from being able to brute force guess the possible public-private key pairs.

Speaking more generally, I’m a bit dubious about academic analysis which are primarily worried about recovering from the exposure of the state of the random pool. In practice, if the bad guy can grab the state of random pool, they probably have enough privileged access that they can do many more entertaining things, such as grabbing the user’s passphrase or their long-term private key. Trying to preserve the amount of entropy in the pool, and making sure that we can extract as much uncertainty from the system as possible, are much higher priority things to worry about.

That’s not to say that I might not make changes to /dev/random in reaction to academic analysis; I’ve made changes in reaction to [2], and I have changes queued for the next major kernel release up to make some changes to address concerns raised in [1]. However, protection against artificially constructed attacks is not the only thing which I am worried about. Things like making sure we have adequate entropy collection on all platforms, especially embedded ones, and adding some conservatism just in case SHA isn’t a perfect random function are some of the other things which I am trying to balance as we make changes to /dev/random.

T’so, who is the former CTO of the Linux Foundation, at least acknowledges the possibility that there is a real issue here.

Share in other sites/networks: These icons link to social bookmarking sites where readers can share and discover new web pages.
  • Reddit
  • email

Decor ᶃ Gemini Space

Below is a Web proxy. We recommend getting a Gemini client/browser.

Black/white/grey bullet button This post is also available in Gemini over at this address (requires a Gemini client/browser to open).

Decor ✐ Cross-references

Black/white/grey bullet button Pages that cross-reference this one, if any exist, are listed below or will be listed below over time.

Decor ▢ Respond and Discuss

Black/white/grey bullet button If you liked this post, consider subscribing to the RSS feed or join us now at the IRC channels.

DecorWhat Else is New


  1. IRC Proceedings: Sunday, May 28, 2023

    IRC logs for Sunday, May 28, 2023



  2. Daniel Stenberg Knows Almost Nothing About Gemini and He's Likely Just Protecting His Turf (HTTP/S)

    The man behind Curl, Daniel Stenberg, criticises Gemini; but it's not clear if he even bothered trying it (except very briefly) or just read some inaccurate, one-sided blurbs about it



  3. Links 29/05/2023: Videos Catchup and Gemini FUD

    Links for the day



  4. Links 28/05/2023: Linux 6.4 RC4 and MX Linux 23 Beta

    Links for the day



  5. Gemini Links 28/05/2023: Itanium Day, GNUnet DHT, and More

    Links for the day



  6. Links 28/05/2023: eGates System Collapses, More High TCO Stories (Microsoft Windows)

    Links for the day



  7. IRC Proceedings: Saturday, May 27, 2023

    IRC logs for Saturday, May 27, 2023



  8. No More Twitter, Mastodon, and Diaspora for Tux Machines (Goodbye to Social Control Media)

    People would benefit from mass abandonment of such pseudo-social pseudo-media.



  9. Links 28/05/2023: New Wine and More

    Links for the day



  10. Links 27/05/2023: Plans Made for GNU's 40th Anniversary

    Links for the day



  11. Social Control Media Needs to be Purged and We Need to Convince Others to Quit It Too (to Protect Ourselves as Individuals and as a Society)

    With the Tux Machines anniversary (19 years) just days away we seriously consider abandoning all social control media accounts of that site, including Mastodon and Diaspora; social control networks do far more harm than good and they’ve gotten a lot worse over time



  12. Anonymously Travelling: Still Feasible?

    The short story is that in the UK it's still possible to travel anonymously by bus, tram, and train (even with shades, hat and mask/s on), but how long for? Or how much longer have we got before this too gets banned under the false guise of "protecting us" (or "smart"/"modern")?



  13. With EUIPO in Focus, and Even an EU Kangaroo Tribunal, EPO Corruption (and Cross-Pollination With This EU Agency) Becomes a Major Liability/Risk to the EU

    With the UPC days away (an illegal and unconstitutional kangaroo court system, tied to the European Union in spite of critical deficiencies) it’s curious to see EPO scandals of corruption spilling over to the European Union already



  14. European Patent Office (EPO) Management Not Supported by the EPO's Applicants, So Why Is It Still There?

    This third translation in the batch is an article similar to the prior one, but the text is a bit different (“Patente ohne Wert”)



  15. EPO Applicants Complain That Patent Quality Sank and EPO Management Isn't Listening (Nor Caring)

    SUEPO has just released 3 translations of new articles in German (here is the first of the batch); the following is the second of the three (“Kritik am Europäischen Patentamt – Patente ohne Wert?”)



  16. German Media About Industry Patent Quality Charter (IPQC) and the European Patent Office (EPO)

    SUEPO has just released 3 translations of new articles in German; this is the first of the three (“Industrie kritisiert Europäisches Patentamt”)



  17. Geminispace Continues to Grow Even If (or When) Stéphane Bortzmeyer Stops Measuring Its Growth

    A Gemini crawler called Lupa (Free/libre software) has been used for years by Stéphane Bortzmeyer to study Gemini and report on how the community was evolving, especially from a technical perspective; but his own instance of Lupa has produced no up-to-date results for several weeks



  18. Links 27/05/2023: Goodbyes to Tina Turner

    Links for the day



  19. HMRC: You Can Click and Type to Report Crime, But No Feedback or Reference Number Given

    The crimes of Sirius ‘Open Source’ were reported 7 days ago to HMRC (equivalent to the IRS in the US, more or less); but there has been no visible progress and no tracking reference is given to identify the report



  20. IRC Proceedings: Friday, May 26, 2023

    IRC logs for Friday, May 26, 2023



  21. One Week After Sirius Open Source Was Reported to HM Revenue and Customs (HMRC) for Tax Fraud: No Response, No Action, Nothing...

    One week ago we reported tax abuses of Sirius ‘Open Source’ to HMRC; we still wait for any actual signs that HMRC is doing anything at all about the matter (Sirius has British government clients, so maybe they’d rather not look into that, in which case HMRC might be reported to the Ombudsman for malpractice)



  22. Links 26/05/2023: Weston 12.0 Highlights and US Debt Limit Panic

    Links for the day



  23. Gemini Links 26/05/2023: New People in Gemini

    Links for the day



  24. IRC Proceedings: Thursday, May 25, 2023

    IRC logs for Thursday, May 25, 2023



  25. Links 26/05/2023: Qt 6.5.1 and Subsystems in GNUnet

    Links for the day



  26. Links 25/05/2023: Mesa 23.1.1 and Debian Reunion

    Links for the day



  27. Links 25/05/2023: IBM as Leading Wayland Pusher

    Links for the day



  28. IRC Proceedings: Wednesday, May 24, 2023

    IRC logs for Wednesday, May 24, 2023



  29. Links 25/05/2023: Istio 1.16.5 and Curl 8.1.1

    Links for the day



  30. Gemini Links 25/05/2023: On Profit and Desire for Gemini

    Links for the day


RSS 64x64RSS Feed: subscribe to the RSS feed for regular updates

Home iconSite Wiki: You can improve this site by helping the extension of the site's content

Home iconSite Home: Background about the site and some key features in the front page

Chat iconIRC Channel: Come and chat with us in real time

Recent Posts