EditorsAbout the SiteComes vs. MicrosoftUsing This Web SiteSite ArchivesCredibility IndexOOXMLOpenDocumentPatentsNovellNews DigestSite NewsRSS

10.16.13

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 this post: These icons link to social bookmarking sites where readers can share and discover new web pages.
  • Digg
  • del.icio.us
  • Reddit
  • co.mments
  • DZone
  • email
  • Google Bookmarks
  • LinkedIn
  • NewsVine
  • Print
  • Technorati
  • TwitThis
  • Facebook

If you liked this post, consider subscribing to the RSS feed or join us now at the IRC channels.

Pages that cross-reference this one

What Else is New


  1. More of Bill Gates' Investments in GMO and Mass Indoctrination Under the Disguise of 'Donations'

    Microsoft's arrogant and famously corrupt co-founder is taken to task by those whom he is trying to bamboozle for monopoly, unlimited cross-generational power, and never-ending profit without risk



  2. Home Depot Confirmed a Victim of Microsoft's Bad Security, Microsoft Lays Off Security-Related Staff

    News reports circulate showing that Home Depot was knowingly careless with its Windows dependency while Microsoft lays off staff focused on security



  3. European Patent Office/Organisation - Suspicion of Improper Collusion Between EPO President and Chairman of the Administrative Council: Part III

    A preliminary look at Battistelli's reign and how regulatory powers got abolished, leaving the EPO reckless and largely unaccountable



  4. Links 21/9/2014: xorg-server 1.16.1, Linux Kernel 3.16.3

    Links for the day



  5. Links 20/9/2014: GNOME 3.13.92, Android L

    Links for the day



  6. Scanning Patent Troll Implodes; Is the Podcasting Patent Troll Next?

    MPHJ loses and Personal Audio LLC perhaps wins for the last time since software patents are quickly losing legitimacy in the United States



  7. If CAFC is Not Above the Law, Then it Should be Shut Down Now

    A long series of abuses in CAFC may as well suggest that this court has become broken beyond repair



  8. The Latest From Microsoft Patent Trolls and Patent Partners

    Microsoft-linked and Linux-hostile trolls continue their relentless attacks (albeit with little or no success) while patents as a weapon lose their teeth owing to a Supreme Court ruling



  9. Microsoft Proves That Its Massive Layoffs Are Not About Nokia

    Microsoft is laying off a lot of employees who have nothing at all to do with Nokia



  10. Links 19/9/2014: Another Red Hat Acquisition, Netflix Dumps Microsoft Silverlight and Brings DRM to WWW

    Links for the day



  11. Links 18/9/2014: Windows Copying GNU/Linux, Germany Moves to Security

    Links for the day



  12. Web Site 'Patent Progress' Now Officially 'Powered by CCIA' (FRAND Proponent, Microsoft Front)

    After talking a job at CCIA, "Patent Progress" and its chief author should be treated as dubious on real patent progress



  13. Articles About the Death of Software Patents in the United States

    Recent coverage of software patents and their demise in their country of origin, where even proponents of software patents are giving up



  14. The Death of Software Patents is Already Killing Some Major Patent Trolls

    VirnetX seems to be the latest victim of the demise of software patents in the United States



  15. More Microsoft Layoffs

    More Microsoft layoffs go ahead as the company is unable to compete



  16. ODF on the Rise

    Milestones for OpenDocument Format (ODF) and the launch of FixMyDocuments



  17. Links 17/9/2014: CoreOS, ChromeOS, and systemd

    Links for the day



  18. Italy is Cracking Down on Microsoft's Monopoly Abuse While Gradually Moving to GNU/Linux

    Italy is not only moving to Free/Open Source software but also to GNU/Linux while at the same time barring Microsoft from forcibly tying Windows to new PCs



  19. OpenSUSE's 'Assurances' Are Classic MBA School Hogwash

    OpenSUSE is not part of any commitment, except for SUSE's; the impact of the Novell/SUSE acquisition casts uncertainty on the project's future



  20. Links 16/9/2014: Firefox OS Smartphones in Bangladesh, “Treasure Map” of the Internet

    Links for the day



  21. The United Kingdom Should Dump Microsoft For the Sake of National Security

    The UK has issues of Microsoft dependency and Windows viruses; its migration to Free software and GNU/Linux is not fast enough to guard its autonomy in the age of digital imperialism



  22. CBS Hires Even More Microsoft Staff to Cover Microsoft Matters

    CBS continues to be infested with Microsoft staff past and present (this time Dave Johnson) and the bias in output is quite revealing



  23. Microsoft Has Just Killed Minecraft for GNU/Linux and the Possibility of Free/Open Source Releases

    Persson sells out to Microsoft and lets the abusive monopolist destroy the popular cross-platform game that a community has been built around



  24. Another Reason to Boycott Intel UEFI

    More anti-competitive aspects are revealed inside UEFI, which helps merginalise GNU/Linux



  25. Quick Mention: Novell and SUSE Passed to Microsoft's 'Partner of the Year', Microsoft Focus

    Novell is changing hands again, and falling into the hands of even more Microsoft-friendly actors



  26. Links 16/9/2014: Linux 3.17 RC5, KDE Frameworks 5.2.0

    Links for the day



  27. Željko Topić, Benoît Battistelli, and the European Patent Office (EPO): Part II

    Part II of our look into the EPO appointment of Željko Topić and other matters showing the dubious integrity of the EPO



  28. Links 14/9/2014: Android-based Watches Earn Optimism

    Links for the day



  29. Links 14/9/2014: Eucalyptus Devoured

    Links for the day



  30. Links 11/9/2014: Linux Toilet Project, Linux-Based Wheelchair Project

    Links for the day


CoPilotCo

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

CoPilotCo

Recent Posts