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

Jim Zemlin, Whose Wife is Said to Have Committed Securities Fraud at Bakkt, Weds Gates Foundation With Linux Foundation to Combat Fraud?
Remember who these people are enabling
From 91% to 33% or Less: How Microsoft Has Lost Australia
Historically Australia was quite a stronghold for Microsoft
Debian Developer at Sirius Was Under the Wrong Impression That Staff Must Check or Should See E-mail All the Time (24/7 Work Attention is an Occupational Health Hazard)
My personal and professional experience with a Debian Developer (DD) at work
Techrights More Productive Than Ever Before
Today we finally crossed the 1,900-page milestone
 
Links 05/03/2024: More Gaming Layoffs, Apple Trouble in EU
Links for the day
Gemini Links 05/03/2024: Financial Breakdown and Freedom of Protocols Initiative
Links for the day
Navalny is Dead, This Week We Might Know if the US Will Kill Assange
Olaf Scholz backs Julian Assange’s battle to avoid US extradition
What Quality and Equality Mean
racial lines
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Monday, March 04, 2024
IRC logs for Monday, March 04, 2024
[Meme] Record EPO 'Productivity'
Patent applications granted
Job Groups 5 and 6 at the European Patent Office (EPO) Another Case of EPO Discrimination
an under-reported (or entirely not covered) backlash from last summer
[Meme] Microsoft Fan: "Microsoft is in a panic from the continued loss of its user base"
Published a couple of weeks ago
Android Has Reached New Highs in Mexico, According to Web-Derived Data (Android Now Almost a Majority of the "Market")
Not far from 50%, i.e. half of the "market"
In defence of Albanian women: Outreachy & Debian favoritism scandal
Reprinted with permission from Daniel Pocock
Links 04/03/2024: Old Crisis Looming, UPC Already in Infringement of Article 6 ECHR
Links for the day
The Right to Disconnect (Meme and Very Recent References)
relatively new press
Links 04/03/2024: Techno-Babble in Tech Job Ads and Vision Pro Already Breaking Apart
Links for the day
Europe's Adoption of GNU/Linux, by Country (Now About 6%)
in Switzerland, for instance, adoption of GNU/Linux has been profoundly low
[Meme] 'Debating' People by Subscribing Them to Lots of SPAM
Rebuttal? No, spam.
From Sexual Harassment of Women to Yet More Cybercrimes
They can be prosecuted
Not Only Has Adoption of Windows Vista 11 Flatlined/Plateaued, Now It is Going Down!
Did many people delete Vista 11 and install GNU/Linux instead?
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Sunday, March 03, 2024
IRC logs for Sunday, March 03, 2024
Venezuela: Windows Below 70% (Laptops and Desktops), GNU/Linux Up to 7%
It's a lot higher in Cuba
ICYMI: ZDNet Financially Controlled by Microsoft
a history of censoring SJVN's Microsoft-critical articles
Argentina Joining the 4% 'Club' (GNU/Linux on Desktops and Laptops)
Data as ODF
Transparency Sets Society Free
"Convenient delusions" aren't bliss but temporary relief
[Meme] The EPO, Europe's Second-Largest Institution, Which is Contracting With Belarus
Socialist EPO
The European Patent Office's (EPO) Illegal Ban on Mass Communication Gets in the Way of Democracy
The scientific process (patents apply to science) must allow scrutiny, both from within and from the outside
Links 03/03/2024: Depression in Hong Kong, Sex 'Apps' and STIs
Links for the day
Links Gemini 03/03/2024: NixOS and NextCloud, Back Into Ricing
Links for the day
The Debian family fallacy
Reprinted with permission from Daniel Pocock
GNU/Linux Peaking in Europe, Android Measured as Higher or More Prevalent Than Windows
Android topping Windows
For Every Action There's a Reaction
Gates lobbying Modi
Like in Africa, Android Takes Control, Raking in Almost All the 'Chips' in Asia
So Microsoft has no OS majority except in Japan and Russia (and tiny Armenia).
Links 03/03/2024: Goodbye, Navalny (Funeral Reports)
Links for the day
Gemini Links 03/03/2024: A Wild Devlog Appeared and GrapheneOS Ramble
Links for the day
Gemini at 3,800+
total number of known capsules at above 3.8k
Be a Navalny
We salute Mr. Navalny
Mozilla Firefox is Back in ~2% Territories, Jeopardising Its Status as Web Browser to Test/Target/Validate With
Some new stats
[Meme] Russian Standards of Law: The Executive Branch Decides Everything
the president's kangaroo court
Up Next: The Tricky Relationship Between the Administrative Tribunal of the ILO and the European Patent Organisation (EPO)
We've moved from presidents who run a republic by consent to corrupt, unqualified, dictatorial officials who bribe for the seat (buying the votes)
IRC Proceedings: Saturday, March 02, 2024
IRC logs for Saturday, March 02, 2024
Over at Tux Machines...
GNU/Linux news for the past day
Beware Imposter Sites of Techrights (Not Techrights.com or Techrights.org)
Only trust pages accessed through the domains controlled by us
Italy visa & residence permit: Albanian Outreachy, Wikimedia & Debian tighten control over woman
Reprinted with permission from Daniel Pocock