Bonum Certa Men Certa

Linux Backdoors Revisited (New Revelations and Old Revelations)

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.

Recent Techrights' Posts

Using SLAPPs to Cover Up Sexual Abuse and Strangulation
The exact same legal team of the Serial Strangler from Microsoft and Garrett already has a history fighting against "metoo"
Adding the Voice of Writers to UK SLAPP Reform
The journey to repair antiquated (monarchy era) laws will likely be long
 
Plunder at the Second-Largest Institution in Europe
cuts, neglect, health problems, even early deaths
Links 12/07/2025: Political Developments, Attack on Opposition, Climate Actions
Links for the day
Gemini Links 12/07/2025: Melodic Musings and Small Web July
Links for the day
Links 12/07/2025: Jail in China for Homoerotica, South Korea Discriminates Against Old Workers
Links for the day
If Only Everything Was Rewritten in Rust, We'd Have No More Security Issues?
Nope.
Links 12/07/2025: Birdwatching and Fake/Misleading Wall Street 'Valuation' Figures
Links for the day
Gemini Links 12/07/2025: How to Avoid Writing, Apps for Android
Links for the day
EPO Staff Committee on Harassment in the Workplace
slides
EPO Takes More Money From Staff for Speculation (Pensions), Actuarial Study Explains the Impact
"The key change in this year’s Actuarial Study, due to cascading the new “risk appetite” from the financial study, is a significant increase of the total pension contribution rate of 5.7 percentage points, up to a total of 37.8%. This is driven by an unprecedented decrease in the discount rate of 105 bps down to 2.2%."
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Friday, July 11, 2025
IRC logs for Friday, July 11, 2025
Microsoft - Like IBM - Does the "Relocation" Tricks (Start Over Elsewhere, Then Get Sacked by Microsoft)
It is a "low blow" or a "dick move"
After the Free Software Foundation's Campaign to Raise Money Let's See Campaigns to Finish Off Microsoft (Vista 11, GitHub etc.)
Microsoft is in effect collapsing
Your Publications Have No Major Impact Unless or Until You "Get Some Heat"
we're on the right track
Slopwatch: A Cause for Hope, the Hype is Dying
For about a month we showed that becoming a slopfarm - for several weeks - resulted in utter failure and ruin for BetaNews
Links 11/07/2025: Censorship Worsening, 3D Printing Success Stories, UK and France Unite Around Nukes
Links for the day
Gemini Links 11/07/2025: Zorin OS and Scriptonite Updates
Links for the day
Links 11/07/2025: Hardware, Russia, and China
Links for the day
Links 11/07/2025: Intel Collapsing and Microsoft Resorts to Bribery to Push Slop Via Obligatory Education
Links for the day
The EFF Sided With the Team That Strangles Women and Tells Women to Kill Themselves
They say that apathy and inaction are a form of a "stance"
"Nat [Friedman] and [the Serial Strangler From Microsoft] Were Always Exceptionally Close," Says Former Housemate and Colleague
Now Alex (hiding behind another name when that suits him) not only attacks women but also people who merely report what he did to women
Exemplary List of Things That Are Not Artificial Intelligence or Even Intelligence
The "age of AI" or "era of AI" or "AI revolution" mostly boils down to rebranding, just like "the cloud"
New Letter From the European Patent Office Explains How the Office Plots to Grant Many Illegal Patents, a Self-Fulfilling Prophecy of 'Growth'
Open letter to Mr Rowan (VP1) and Mr Aledo Lopez (COO)
Abuse of Process
5RB is employing people who help violent men
What Microsoft's Nat Friedman and Microsoft Lunduke Have in Common
"Get in da car; No time to explain, loser"
Microsoft and IBM Don't Have Much of a Future (They Mostly Pretend at This Point)
IBM and Microsoft are in some ways alike but in many ways different
It's Not Just Twitter (or X.com) That's Dying, Microsoft's Equivalent is Dying Also
Unable to find a business model
GitHub Copilot Can Cause the Bankruptcy of GitHub to Come Sooner and GitHub to be Shut Down Just Like Skype
Some publicly available information suggests that even for each paid subscriber for plagiarism (LLM 'coding') GitHub Copilot still loses more money than it makes
Wayland is Bad for the Planet
If you use Wayland, it'll take you longer to accomplish tasks and you will consume more energy (or battery life)
Legitimising Those Who Sabotage You
Microsoft is a very malicious company
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Thursday, July 10, 2025
IRC logs for Thursday, July 10, 2025
On Microsoft Layoffs
we might be looking at about 60,000 Microsoft layoffs since 2023
EPO Management Already Breaks Its Own Promise (Lie) on "Bringing Teams Together"
This gut-punching move happened just 2 days ago
Gemini Links 11/07/2025: Occupation of 2025 and "Old Man Yells At Soundcloud"
Links for the day
Our Lawsuits Against the 'Cancel Mob' (Ringleaders) Helped Reduce Anti-Free Software Online Abuse
That's not to say that lawsuits are the best way to handle terrible people. But that can help.
Tomorrow is the Last Day of the Fund-Raising Campaign of the Free Software Foundation (FSF)
They will probably extend the date, as usual
Fixing Patents in Europe, Little by Little (by Transparency and Reporting of Suppressed Facts)
Tomorrow and throughout the weekend we shall focus some more on the EPO
The Two Lies Microsoft is Telling in "the News" This Week (to Distract From Layoffs and Decreased Interest in Slop/Chaff)
Microsoft is run by liars and frauds who SLAPP critics
Tux Machines Already Destroyed SLAPPs
Attacks on the mere publication of GNU/Linux news won't be tolerated
PCLinuxOS is Available for Download Again
PCLinuxOS is important to us also because its founder, back then the partner of Susan, helped create Tux Machines more than 21 years ago
Links 10/07/2025: Microsoft E-mail 'Services' Collapse Again, "Yet Another Strava Privacy Leak"
Links for the day
Gemini Links 10/07/2025: Automating Git Repo Updates and Small Web 'Zine'
Links for the day
GNU/Linux Leftovers
mostly Linux stuff
Audiocasts/Shows: Going Linux, FLOSS Weekly, and RHEL Clones
3 new picks
We Are Already Fighting - With Considerable Success - SLAPPs in the UK
we intend to tell the full story
Bullies With Pens and Papers (or Apple Macs With Templates)
Not all barristers are evil, but there are perhaps "rotten apples"
Slopwatch: webpronews.com, linuxsecurity.com, linuxjournal.com
a pile of trash disguised as 'articles'
Links 10/07/2025: Linda Yaccarino Divorces MElonazi Site, Wildfires Hit Syria
Links for the day
The History and the Policy of the EPO's Stance on Breastfeeding (Corporate Monopolies Versus Babies' Health)
"The Case for Introducing a Breastfeeding Policy at the EPO"
Gemini Links 10/07/2025: Inventing Chords and "Nightmare Boss"
Links for the day
Igor Ljubuncic Once Again Shows That for Technical Reasons Wayland Still Sucks, Performs Considerably Worse Than What Existed for Decades
That is aside from compatibility factors and other crucial factors
Links 10/07/2025: "Apple Vs The Law" and Twitter Became Full Nazi Bar
Links for the day
Unable to Find Anyone to Work as Their Media Lawyer, Brett Wilson LLP Will Continue Losing Female Staff
What sort of sick person would wish to join Brett Wilson LLP to carry this baton?
Microsoft-Sponsored Propaganda Site Has Removed False 'Hit Piece' About Dr. Stallman (With Fake and Misrepresented Imagery) But Only After 4 Years
So they only removed that page some time around 2025, i.e. about 4 years after it had been published
Always Check Your Inputs
Garbage in, garbage out. Or wrong assumptions, wrong corollary.
Dan Neidle Said That Tax Evasion Facilitator Mr Zahawi (Working to Silence Bloggers Through Brett Wilson LLP) Targeted Not Only Him (But The Others Kept Quiet)
"Mr Neidle said after repelling Mr Zahawi he was contacted by bloggers and tweeters who had received similar threats. They deleted their work “and in most cases never commented publicly on anything again”."
SLAPP Funding Transparency Urgently Needed in the UK and Elsewhere (in Practice, Not Just in Theory)
Writing about crime - including Microsoft crime - is not a crime
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Wednesday, July 09, 2025
IRC logs for Wednesday, July 09, 2025
Elodie Bergot Still Doing Illegal Things at the EPO, Based on the Local Staff Committee Munich
They keep taking away from the staff while compelling the staff to do illegal things