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

Why We Support Richard Stallman and You Probably Should Too
It's not about being "Richard Stallman fan", it is about maintaining the right to hold positions (on technology) like his
Some Large German Media Covers Richard Stallman's Talks in Germany Earlier This Week
LLM-based chatbots are just "bullshit generators" (as he has long called them)
Trouble in Red Hat/IBM and a Retreat to Ponzi Economics in Search of Wall Street Market Heist
Would you invest your life savings in this kind of crap?
Who Asked Software in the Public Interest (SPI) for a Refund? ($100,000, Resulting in Losses of $267,201 in 12 Months, Highest-Ever Losses)
The IRS does not reveal who or what's tied to this refund (or the cause/reason)
 
Links 23/10/2025: LLM 'Hallucinations' (Defects) in Practical Code 'Generation', China Becomes More Economically and Technologically Independent
Links for the day
Linux Foundation Uses LLM Slop to Promote Microsoft in Linux.com (Again), Rendering It a Linux-Hostile Slopfarm
Openwashing with slop by "Linux.com Editorial Staff", which basically seems to be a bot
Links 23/10/2025: Windows TCO Galore and "The Internet Is Going to Break Again"
Links for the day
Social engineering attack: Debian voted to trick you on binary blobs
Reprinted with permission from Daniel Pocock
Techrights Will Always Stand for Women's Rights
We even invest money - personal savings that it - in our principles
Certified Lawyers Should Know Better (Than to Intimidate Us With Man Who Drives on Motorcycle Through a Really Bad Storm Between Distant Cities, Then Collects Photos of Our Home)
Mentioning someone was in prison for bad things isn't a crime, it's a public service
The "AI" (Slop) Bubble is Already Imploding
"ChatGPT Usage Has Peaked and Is Now Declining, New Data Finds"
The So-called "Sexy" Buckets (AI, Quantum) Cannot Save IBM From Reality, Shares Tank
"No matter how much financial hocus-pocus they use to reclassify revenues to land in the "sexy" buckets (AI, Quantum), it still smells old and musty - just like this company."
Paul Krugman is Wrong About the Scope of Mass Layoffs in the United States
A few years ago society was accelerating its journey towards feudalism, boosted by COVID-19
Links 23/10/2025: Proprietary Blunders and CISA's Latest Disclosure of Holes
Links for the day
Gemini Links 23/10/2025: Fast Past (F1), 99.9% Uptime
Links for the day
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Wednesday, October 22, 2025
IRC logs for Wednesday, October 22, 2025
Slopwatch: Google News is Promoting Fake 'Articles' About Fake Xubuntu, Fake Articles About Replacing Windows With GNU/Linux
The quality of the Web deteriorates and unless someone cleans up the mess, real sites will lose an incentive to produce anything
When "AI Layoffs" Mean Layoffs Due to the "AI" Bubble Popping
many people that are laid off by Microsoft claim to be specialists in "AI"
Mysterious grant forfeited, $100,000 from Software in the Public Interest accounts 2023
Reprinted with permission from Daniel Pocock
Evidence: bullying, student union behaviour: Armijn Hemel's FSFE resignation
Reprinted with permission from Daniel Pocock
Evidence: psychological abuse, stalking, Galia Mancheva, Susanne Eiswirt ignored by FSFE judgment for Matthias Kirschner
Reprinted with permission from Daniel Pocock
Helping FSFE scam victims and conference organisers
Reprinted with permission from Daniel Pocock
Nigerian fraud in FSFE constitution
Reprinted with permission from Daniel Pocock
Worrying and Amusing Stories of "Clown Computing" Gone Awry
Many of these disasters could be avoided
Links 22/10/2025: Amazon Plans to Replace Workers With Robotics, AWS and Clown Computing in General Ridiculed
Links for the day
Gemini Links 22/10/2025: Niri Completely Changes Multitasking and Overview of Diff-ers
Links for the day
Links 22/10/2025: Study on Misinformation by Slop and Heavily Debt-Sabbled Microsoft OpenAI (ClosedSlop) Uses "Browser" as Gimmick/Distraction
Links for the day
They've Already Spent Close to a Million Dollars on Lawyers and Sent Us About 50 KG of Legal Papers (Sponsored by Mysterious Third Party) to Try to Censor Techrights, Without Success
They try to overcompensate with sheer volume for a lack of solid, clear arguments (we are the victims here)
12 Months Ago the 'Hulk Hogan of UEFI' Officially Went 'Tag-Team'
We're actually sort of flattered or proud that such despicable people are so desperate to censor us
"Cloud Computing" Was Always a Joke, But This Week Was the Punchline
Maybe stop following tech trends and fashions
"Cloud Computing" Does Not Mean Safety
Fault tolerance is related to the notion of software freedom
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Tuesday, October 21, 2025
IRC logs for Tuesday, October 21, 2025
The Fall of Windows: From Something to Nothing
Of course Microsoft will pretend everything is fine and "just trust the hey hi" (AI)
Sounds Like Fedora is Ready to Become Less of a Slave of Microsoft (GitHub)
This seems like a belated move in a positive direction
XBox is a Dead Microsoft Product in a Dying Industry
It's probable that another wave of XBox layoffs is just over the horizon (maybe even before month's end)
Progress on Techrights Site Search
Fun times
IBM's Bluewashing of Red Hat Means the Layoffs Are Silent, Barely Reported
Don't wait to hear about "Red Hat layoffs"
Gemini Links 21/10/2025: Happy Disconnection, AWS Falling Apart, Closing of Gemlog Blue
Links for the day
Full Audio of Today's Richard Stallman Talk in the Technical University of Munich
Free/Libre software and freedom in the digital society
Microsoft XBox is Just Vapourware (Promises of Hardware That Doesn't Exist), Real Products Perish
just as developers lose interest in developing for XBox Microsoft is increasing the costs imposed upon them
Slopwatch: Fake Articles (Slop) in "Linux" Clothing in Google News (Noise)
all about what Google does
Links 21/10/2025: Even "Inventor of Vibe Coding" Rejects Vibe Coding, USPTO Experiments With Slop in Examination
Links for the day
Richard Stallman Talk Now Available for Viewing (Archived Copy, Not Live-streamed)
This recording is over 2 hours old
Links 21/10/2025: AWS-Induced Chaos and Social Control Media Curbs
Links for the day
Gemini Links 21/10/2025: Programming, StarGrid, Brand-New Palm OS Strategy Game in 2025, and Chatbot as Addiction Mechanisms
Links for the day
The African Lion and the American Cowards
Safaris exist for people to watch and enjoy animals
Amazon Web Shenanigans Perfectly Timed for Today's Talk by Richard Stallman
Maybe listen to him instead of looking for excuses to ridicule the messenger
Mission:Libre Has Taken Off (Project by Carmen Maris)
there will be a lot more to report on next month (after the event)
Techrights to Publish More EPO Leaks Next Week
We're meanwhile also doing lots of work on search, whose interface now looks better
Links 21/10/2025: 'The Lost Art' of Neon Signs and Twitter (X) to Enable Identity Theft (or Handle Theft) as a Service
Links for the day
Plagiarism With LLM Slop: Hindustan Times (HT Digital Streams Limited) Has Become a Slop Factory/Hub
What a disgrace
A radical proposal to keep your personal data safe, by Richard Stallman
"The surveillance imposed on us today is worse than in the Soviet Union. We need laws to stop this data being collected in the first place"
Next Week We Launch Search at Techrights
We're planning to launch it some time next week. Maybe Tuesday, maybe Thursday.
Talk by Richard Stallman Will be Live-streamed in Less Than 10 Hours
Happy hacking
"No Kings" in the Software World (GAFAM Should Not Exist, Either)
"No Kings" is a good slogan. Let's start by ridding ourselves of masters, not only those who reside in DC or visit DC
Every Morning
Bugs/edge cases combined with automation can spell disaster
Insane, Deliberately Dishonest, or Just Another Bigot?
very intellectually-dishonest human being
A Lot of Techrights is Built on Perl
Perl also runs the sister site
The Register MS Selling Slop for Microsoft (Vapourware, Ponzi Scheme, False Claims)
What will be left of The Register MS if it keeps repeating falsehoods and looking to profit from Ponzi schemes?
analytics.usa.gov Says Less Than 14% of Web Requests (to Government Sites) Come From Vista 11
Vista 11 was released more than 4 years ago!
People Who Attempt to Take Down Correct Information Need a Doctor a Day
“Journalism is printing something that someone does not want printed. Everything else is public relations.” ― George Orwell
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Monday, October 20, 2025
IRC logs for Monday, October 20, 2025
Vista 11 is Sinking While Microsoft is PIPing (Mass Layoffs But Silent Layoffs)
We're witnessing a shift in platform dominance
Richard Stallman is Having a Good Week Already (Stallman Was Right About 'Clown Computing')
That alone is worth bringing up in his talk
An Update About Soylent News, With Jan Rinok "Back in the Saddle"
Burnout or "near burnout" a possibility when having to curate abuse
When Prominent GNU/Linux Distros Are Run by Spies
What has Microsoft Canonical become?
More Publishers and Companies Nowadays Say "GNU/Linux", Not "Linux"
It's not to see InstallAware saying GNU/Linux this week