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

Firefox Has Fallen to 2% in New Zealand
At around 2%, at least in the US (2% or below this threshold), there's no longer an obligation to test sites for any Gecko-based browser
GNU/Linux in Kyrgyzstan: From 0.5% to 5% in Eight Years
the country is almost the size of the UK
Microsoft-Connected Sites Trying to Shift Attention Away From Microsoft's Megabreach Only Days Before Important If Not Unprecedented Grilling by the US Government?
Why does the mainstream media not entertain the possibility a lot of these talking points are directed out of Redmond?
 
4 Old Articles About Microsoft/IBM SystemD
old but still relevant
Winning Streak
Free software prevalence
Links 19/05/2024: Conflicts, The Press, and Spotify Lawsuit
Links for the day
GNU/Linux+ChromeOS at Over 7% in New Zealand
It's also the home of several prominent GNU/Linux advocates
libera.chat (Libera Chat) Turns 3 Today
Freenode in the meantime continues to disintegrate
[Teaser] Freenode NDA Expires in a Few Weeks (What Really Happened 3 Years Ago)
get ready
GNU/Linux is Already Mainstream, But Microsoft is Still Trying to Sabotage That With Illegal Activities and Malicious Campaigns of Lies
To help GNU/Linux grow we'll need to tackle tough issues and recognise Microsoft is a vicious obstacle
Slovenia's Adoption of GNU/Linux in 2024
Whatever the factor/s may be, if these figures are true, then it's something to keep an eye on in the future
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Saturday, May 18, 2024
IRC logs for Saturday, May 18, 2024
Links 19/05/2024: Profectus Beta 1.2
Links for the day
Site Archives (Not WordPress)
We've finally finished the work
[Meme] The EPO Delusion
on New Ways of Working
EPO Representatives Outline Latest Attacks on Staff
Not much has happened recently in terms of industrial action
Links 18/05/2024: Revisiting the Harms of Patent Trolls, Google Tries to Bypass (or Plagiarise) Sites Under the Guise of "AI"
Links for the day
Links 18/05/2024: BASIC Story, Site Feeds, and New in Geminispace
Links for the day
Justice for Victims of Online Abuse
The claims asserted or pushed forth by the harasser are categorically denied
[Meme] Senior Software Engineer for Windows
This is becoming like another Novell
Links 18/05/2024: Deterioration of the Net, North Korean IT Workers in the US
Links for the day
Windows in Lebanon: Down to 12%?
latest from statCounter
[Video] 'Late Stage Capitalism': Microsoft as an Elaborate Ponzi Scheme (Faking 'Demand' While Portraying the Fraud as an Act of Generosity and Demanding Bailouts)
Being able to express or explain the facts isn't easy because of the buzzwords
Links 18/05/2024: Caledonia Emergency Powers, "UK Prosecutor's Office Went Too Far in the Assange Case"
Links for the day
Microsoft ("a Dying Megacorporation that Does Not Create") and IBM: An Era of Dying Giants With Leadership Deficits and Corporate Bailouts (Subsidies From Taxpayers)
Microsoft seems to be resorting to lots of bribes and chasing of bailouts (i.e. money from taxpayers worldwide)
US Patent and Trademark Office Sends Out a Warning to People Who Do Not Use Microsoft's Proprietary Formats
They're punishing people who wish to use open formats
Links 18/05/2024: Fury in Microsoft Over Studio Shutdowns, More Gaming Layoffs
Links for the day
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Friday, May 17, 2024
IRC logs for Friday, May 17, 2024
Links 18/05/2024: KOReader, Benben v0.5.0 Progress Update, and More
Links for the day
[Meme] UEFI 'Secure' Boot Boiling Frog
UEFI 'Secure' Boot: You can just ignore it. You can just turn it off. You can hack on it as a workaround. Just use Windows dammit!
The Market Wants to Delete Windows and Install GNU/Linux, UEFI 'Secure' Boot Must Go!
To be very clear, this has nothing to do with security and those who insist that it is have absolutely no credentials
In the United States Of America the Estimated Share of Google Search Grew After Microsoft's Chatbot Hype (Which Coincided With Mass Layoffs at Bing)
Microsoft's chatbot hype started in late 2022
Techrights Will Categorically Object to Any Attempts to Deny Its Right to Publish Informative, Factual Material
we'll continue to publish about 20 pages per day while challenging censorship attempts
Links 17/05/2024: Microsoft Masks Layoffs With Return-to-office (RTO) Mandates, More YouTube Censorship
Links for the day
YouTube Progresses to the Next Level
YouTube is a ticking time bomb
Journalists and Human Rights Groups Back Julian Assange Ahead of Monday's Likely Very Final Decision
From the past 24 hours...
[Meme] George Washington and the Bill of Rights
Centuries have passed since the days of George Washington, but the principles are still the same
Daniel Pocock: "I've Gone to Some Lengths to Demonstrate How Corporate Bad Actors Have Used Amateur-hour Codes of Conduct to Push Volunteers Into Modern Slavery"
"As David explains, the Codes of Conduct should work the other way around to regulate the poor behavior of corporations who have been far too close to the Debian Suicide Cluster."
Video of Richard Stallman's Talk From Four Weeks Ago
2-hour video of Richard Stallman speaking less than a month ago
statCounter Says Twitter/X Share in Russia Fell From 23% to 2.3% in 3 Years
it seems like YouTube gained a lot
Journalist Who Won Awards for His Coverage of the Julian Assange Ordeals Excluded and Denied Access to Final Hearing
One can speculate about the true reason/s
Richard Stallman's Talk, Scheduled for Two Days Ago, Was Not Canceled But Really Delayed
American in Paris
3 More Weeks for Daniel Pocock's Campaign to Win a Seat in European Parliament Elections
Friday 3 weeks from now is polling day
Microsoft Should Have Been Fined and Sanctioned Over UEFI 'Lockout' (Locking GNU/Linux Out of New PCs)
Why did that not happen?
Gemini Links 16/05/2024: Microsoft Masks Layoffs With Return-to-office (RTO) Mandates, Cash Issues
Links for the day
Over at Tux Machines...
GNU/Linux news for the past day
IRC Proceedings: Thursday, May 16, 2024
IRC logs for Thursday, May 16, 2024
Ex-Red Hat CEO Paul Cormier Did Not Retire, He Just Left IBM/Red Hat a Month Ago (Ahead of Layoff Speculations)
Rather than retire he took a similar position at another company
Linux.com Made Its First 'Article' in Over and Month, It Was 10 Words in Total, and It's Not About Linux
play some 'webapp' and maybe get some digital 'certificate' for a meme like 'clown computing'