Slashdot Mirror

I'm glad that people are learning about this problem. Sadly, it's not new, it's been known for decades. CERT’s “Secure Coding” item MSC09-C (Character Encoding — Use Subset of ASCII for Safety) specifically discusses the vulnerabilities due to filenames. The Common Weakness Enumeration (CWE) includes 3 weaknesses related to filenames (CWE 78, CWE 73, and CWE 116), all of which are in the 2009 CWE/SANS Top 25 Most Dangerous Programming Errors. My freely-available book on writing secure software has a whole section about filenames. And so on.

We need to fix the problems with Unix/Linux filenames, not just keep rediscovering them. In particular, ensuring that filenames had no control characters, no leading dashes, and used UTF-8 encoding would simplify developing correct programs. Most people writing software already follow these rules. We don't need to make it easy for attackers.

I'm glad that people are learning about this problem. Sadly, it's not new, it's been known for decades. CERT’s “Secure Coding” item MSC09-C (Character Encoding — Use Subset of ASCII for Safety) specifically discusses the vulnerabilities due to filenames. The Common Weakness Enumeration (CWE) includes 3 weaknesses related to filenames (CWE 78, CWE 73, and CWE 116), all of which are in the 2009 CWE/SANS Top 25 Most Dangerous Programming Errors. My freely-available book on writing secure software has a whole section about filenames. And so on.

We need to fix the problems with Unix/Linux filenames, not just keep rediscovering them. In particular, ensuring that filenames had no control characters, no leading dashes, and used UTF-8 encoding would simplify developing correct programs. Most people writing software already follow these rules. We don't need to make it easy for attackers.

Nop, you can not just use --. because many commands do not understand --

Here is an article by dwheeler (a frequent slashdotter; often cited for his technique countering the trusting trust problem) about filenames.
http://www.dwheeler.com/essays...

I believe he is mostly right. We should move to file systems that do not allow "stupid" names and be done with it.

You make it clear that you haven't even read TFA (The Fucking Abstract) of that paper.

In the DDC technique, source code is compiled twice: the source code of the compiler’s parent is compiled using a trusted compiler, and then the putative compiler source code is compiled using the result of the first compilation. If the DDC result is bit-for-bit identical with the original compiler-under-test’s executable, and certain other assumptions hold, then the compiler-under-test’s executable corresponds with its putative source code.

Emphasis mine. DDC is useless when you have many contributors to many compilers, all of which are complex systems containing bugs. DDC is great--if you have a compiler that you can absolutely trust. For most software, you'd have little reason not to trust it--but crypto is not most software, and the bar for correctness/resistance to attack is much higher.

He is wrong and it was only ever a strong hypothesis on his part. Newer research shows that it is a lot easier to build in a way that excludes compiler backdoors: http://www.dwheeler.com/trusti...

The idea is fascinating. It basically says if you have a really crappy and simple compiler that can compile your code and that you can trust, you can propagate that trust on a really good and complicated compiler. Writing a crappy and simple C compiler can be done in a few weeks.

Yeah but how are you going to compile your compiler?

He is wrong and it was only ever a strong hypothesis on his part. Newer research shows that it is a lot easier to build in a way that excludes compiler backdoors: http://www.dwheeler.com/trusti...

The idea is fascinating. It basically says if you have a really crappy and simple compiler that can compile your code and that you can trust, you can propagate that trust on a really good and complicated compiler. Writing a crappy and simple C compiler can be done in a few weeks.

The problem with any nondeterministic compiler is that it prevents use of diverse double-compiling, a method to detect the sort of compiler backdoor described by Ken Thompson in "Reflections on Trusting Trust". You'd have to bootstrap the compiler with nondeterminism turned off (and with GUIDs, timestamps, and multithreaded allocation of symbols for anonymous objects turned off too) in order for the DDC bootstrap construction to converge.

In any case, I've implemented a technique like this on the Nintendo Entertainment System. I wrote a preprocessor that shuffles the order of functions in the file, the order of opcodes within a function that don't depend on each other's results, and the order of global variables (or the order of fields in an object). One reason I implemented it was to use one variable as another's canary to make buffer overflows easier to detect in an assembly language program. The other is watermarking the binary so that I can tell who leaked a particular copy of the beta version to the public. If you're interested, you can find my shuffle tool in the source code of Concentration Room.

You need to trust trust to trust in your compiler!

So long as your compiler can compile itself, and so long as you have access to other independent implementations of the same language, you can defeat the Ken Thompson attack with the David A. Wheeler defense. Just bootstrap your compiler with each of the other implementations (compile it with the other compiler, then compile it with the resulting binary), and if there's no attack, the binaries will converge. For example, if you have independent compilers A, B, and C, then C compiled with (C compiled with A) will be bit-identical to C compiled with (C compiled with B) unless an attack is in progress. Start by using Visual C++ Express, Clang, TCC, and even a C interpreter to verify your GCC.

THEN I created the bootloader, a simple text editor, assembler, disassembler, a crappy starter file system, and that was enough to bootstrap into a a full OS completely free from the Ken Thompson's Unix Compiler Hack.

That's one way to defeat Trusting Trust. The other relies on having multiple implementations of a particular programming language, such as Visual C++ vs. GCC vs. Intel vs. Clang. David A. Wheeler pointed out in 2009 that if you bootstrap a compiler with a bunch of independently developed compilers, the binaries will converge unless a Ken Thompson attack is in progress.

All programs on my OS (yes even Java or C code) compiles into bytecode

Interesting. It appears even web browsers are doing the same thing, using LLVM's Emscripten backend to compile to asm.js and then compiling that into bytecode.

I can even change calling conventions on the fly for transparent RPC.

I'm not so sure how transparent RPC is so desirable, as a program can never be sure whether a call will block for 200 microseconds within a machine or 200 milliseconds when called across the Internet.

I've taken to debugging shaders separately from the main program

"Regular software devs" would call this "unit testing". I've written a floating-point library in 6502 assembly language, and a 6502 simulator in Python that I had written earlier helped me to build a unit testing framework.

If you can read Verilog, you can verify that there are no NSA backdoors.

But is there a backdoor in your Verilog compiler? Normally, you might use David A. Wheeler's diverse double-compiling method to ensure beyond reasonable doubt that your compiler isn't backdoored. But diverse double-compiling doesn't work unless the compiler is written in the same language that it compiles. And I don't think the Verilog compiler is written in Verilog.

you might be able to get by with an 8-bit softcore like PicoBlaze

Wikipedia's article about PicoBlaze states that it's not free to use on anything but a Xilinx FPGA. So if you switch to Altera or go into production with an ASIC, you might have to switch to PacoBlaze and deal with any minor behavior differences.

OpenSSL was actually examined by a lot of tools, but they all missed Heartbleed. My article How to Prevent the next Heartbleed lists approaches that could have found it. We need to improve how we examine this software so problems like this don't happen again.

So: compressing that file would mean you need a part of memory to actually perform the compression. That means the data you write is not only the state of the system but also the state of the compressor of your system.

I imagine a run-length (RLE) compressor and decompressor could fit well under 512 bytes. That means about one page would have to be swapped out before hibernation can begin.

Regarding deallocation of unused memory: most OSes can't do that. A process can only request more vm memory with sbrk(), it usually can't deallocate such memory again. (In other words malloc and free never give 'memory back to the OS')

Is "decommitting" something that Windows does and OpenBSD does (search this page for "munmap") and everyone else lacks?

Profiling w/ 100% code coverage would have caught this bug. - No, code coverage would not have worked in this case. Since the problem was that code was missing, you can run every line or branch without triggering the vulnerability. For more, see: http://www.dwheeler.com/essays...

Input fuzzing in the unit tests under memtest could have located this bug even faster. - No, not in this case. Fuzzers were countered because OpenSSL had its own set of memory allocators. When fuzzing you often are looking for crashes; to force buffer over-reads into a crash, the usual way to do that is to override memory allocation. Since OpenSSL managed its memory separately, the override had little useful effect. For more, see: http://www.dwheeler.com/essays...

Profiling w/ 100% code coverage would have caught this bug. - No, code coverage would not have worked in this case. Since the problem was that code was missing, you can run every line or branch without triggering the vulnerability. For more, see: http://www.dwheeler.com/essays...

Input fuzzing in the unit tests under memtest could have located this bug even faster. - No, not in this case. Fuzzers were countered because OpenSSL had its own set of memory allocators. When fuzzing you often are looking for crashes; to force buffer over-reads into a crash, the usual way to do that is to override memory allocation. Since OpenSSL managed its memory separately, the override had little useful effect. For more, see: http://www.dwheeler.com/essays...

One way to detect a backdoored compiler to a fairly high certainty is diverse double-compiling, a method described by David A. Wheeler that bootstraps a compiler's source code through several other compilers. For example, GCC compiled with (GCC compiled with Visual Studio) should be bit for bit identical to GCC compiled with (GCC compiled with Clang) and to GCC compiled with (GCC compiled with Intel's compiler). But this works only if the compiler's source code is available. So to thwart allegations of a backdoor in Visual Studio, perhaps a better choice is to improve MinGW (GCC for Windows) or Clang for Windows to where it can compile a working copy of TrueCrypt.

This is a good start. If "we the people" pay to develop software, then it makes sense to ensure that "we the people" can use it, improve it, and distribute those improvements by default. See http://freethecode.org/ for others who think that makes sense too.

The URL http://www.dwheeler.com/govern... has a longer list of software released by US governments (federal, state, or local) as open source software. It even identifies a few meta-lists like this one. I'm sure it's incomplete, but it shows that US governments do release open source software. I'd love to hear of other examples of such software (with URLs that prove that the government paid to develop or improve it).

This sounds like a Ken Thompson "trusting trust" attack. Someone in that universe ought to have used David A. Wheeler's "diverse double compiling" construction (bootstrap the compiler through several competing compilers and compare the binaries after self-compilation) to expose the compiler's publisher as untrustworthy. It'd be more believable if Mr. Stark's original prototype suit was jury-rigged from a LEGO kit, and the LEGO code was carried into further revisions.

You should be pointing people to this instead:

"Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) - Countering Trojan Horse attacks on Compilers"

http://www.dwheeler.com/trusting-trust/

How do we know that page isn't just a cleverly disguised NSA site?

You should be pointing people to this instead:

"Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) - Countering Trojan Horse attacks on Compilers"

http://www.dwheeler.com/trusting-trust/

I've gotten a lot of hits, and that's a good thing. As I noted in another post, I got hit by reddit earlier this year. In general people are becoming more interested in protecting and verifying build environments, as this post about Tor demonstrates.

So please take a look at my Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) page!

I've gotten a lot of hits, and that's a good thing. As I noted in another post, I got hit by reddit earlier this year. In general people are becoming more interested in protecting and verifying build environments, as this post about Tor demonstrates.

So please take a look at my Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) page!

My page on Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) has more details, including detailed material so you can duplicate the experiments and re-verify the proofs. Note that you do not have to take my word for it.

Sounds very interesting. And I am apparently not even the only one to think so, since you seem to have been Slashdotted. :)

Thanks for pointing out my Diverse Double-Compiling (DDC) paper!

My page on Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) has more details, including detailed material so you can duplicate the experiments and re-verify the proofs. Note that you do not have to take my word for it.

You have to trust some things. But you can work to independently verify those things, to determine if they're trustworthy. I don't always agree with Bruce Schneier, but after watching what's he's done for years, I've determined that he's quite trustworthy. This is the same way we decide if we should trust anyone or any thing. In short: "trust, but verify".

Crypto is what stops 'them' getting to see your data

End-to-end cryptography won't stop "them" from seeing with whom you communicate, how often, where, and when.

Of course, in practice there might be issues with trusting them to be running the code they say they're running.

Things like "trusting trust" are why David A. Wheeler invented diverse double compiling. Take two or more independently developed compilers, preferably Free ones such as such as GCC and Clang, and bootstrap a compiler in all of them. If the end result of both bootstrap processes is the same binary, the resulting compiler is overwhelmingly unlikely to be booby-trapped.

This is a very good reason not to trust any closed source browser, actually. If the source is closed, how the heck do you know what it's doing to show you that nice, safe green password icon? Of course, actually ploughing through and understanding every line of the SSL implementation code in your browser is a lot of work and 99.9% of us haven't done it, but if there were anything dodgy going on in an open source browser it would pretty quickly hit the headlines on Slashdot and we'd all know. Of course again, you don't actually know that a browser (or any other program) was compiled from the published source code unless you compile it yourself.

Sure, you don't know unless you compile it yourself.
But you also don't know even if you compile it yourself.
Trusting Trust, anyone?

Gentoo, anyone?

The good news is, we now know how to beat ken's attack. The bad news is, it requires two compilers known (or rather, trusted) to not be compromised by the same source or in the same exact way, though they may each have separate trusting-trust attacks in them. You can of course apply the same technique pairwise amongst any number of compilers, if you think more than one, but not all, may contain the same trusting-trust attack.

Anyway, it's known how to do that, but I seriously doubt Gentoo actually performs the requisite compilercest. AFAIK, Gentoo is just bootstrapped with a gcc binary that builds everything, including the current gcc, from source. This means your gentoo system is only as trustworthy as the least trustworthy person among: whoever made that original binary toolchain (the compiler is the easiest, but not the only, place to put a trusting-trust attack in the toolchain), whoever made the toolchain(s) used to create all elements of that toolchain, whoever made the toolchain used to create that, etc..

See David A. Wheeler.

Not necessarily : http://www.dwheeler.com/trusting-trust/dissertation/wheeler-trusting-trust-ddc.pdf

Trust. Motherfucker.
http://www.dwheeler.com/trusting-trust/

Trust that.

If you haven't already, you should read thru this. Both the article and, if you're seriously interested, the accompanying PhD thesis document.

David A. Wheelerâ(TM)s Page on Fully Countering Trusting Trust through Diverse Double-Compiling (DDC) - Countering Trojan Horse attacks on Compilers

How can you be sure that both other compilers don't have a parent compiler that is infected?

David A. Wheeler addresses this question in his dissertation.

Mod parent up. I had no idea there was a trusted way to show a compiler hasn't been Thompson hacked!

http://www.dwheeler.com/trusting-trust/

Fortunately there is an effective counter-measure:

http://www.dwheeler.com/trusting-trust/

So you compile the code using two different compilers. How can you be sure that both other compilers don't have a parent compiler that is infected?

Fortunately there is an effective counter-measure: http://www.dwheeler.com/trusting-trust/

I run debian too, but linux was made for performance, not security: try genode, minix, l4, other microkernels.
Somebody pointed out the "trusting trust" problem. Some have approaches against it but the main problem IMHO is that you can't trust the hardware. I suggest pen paper and a one time pad, or... having no secrets.

The "trusting trust" attack that you linked already has countermeasures. One by David A. Wheeler, called diverse double compiling, involves bootstrapping the compiler using several independently developed compilers for the same language and seeing whether they ultimately produce the same binary. Of course, these countermeasures are no help for a proprietary language such as the Pascal variant used by Delphi.

Maybe there is a practical way to discover if this type of attack lives out there IMHO, something like David A. Wheeler's DDC but without requiring a trusted compiler (which is a logical fault, because thats exactly what you are looking for):

In an automated way compare the binaries hash sums comming out of supposedly-identical compilers identical compilations of identical sources on identical platfoms. You find a no-mach? Then, dissasemble the binary with 2 dissasemblers compiled from the 2 different compilers, and with one (the clean) you will probably identify the problem.

The only presupposition is that there must exist some clean versions of the compiler out there, which is more probable because, the opposite, is almost imposible.

The paranoid part, is that if all binaries end up identical ther is no way to be sure if one single attack exist universally or not.

(Of course I am talking only about compilers for simplicity, when the attack can apply also to assemblers, linkers, and whole toolchains)

Yeah, it's not a Windows only thing.

It's a UTF thing.

http://www.cl.cam.ac.uk/~mgk25/ucs/quotes.html

It belongs on the internet, regardless of your opinion.

Here's how to even do them in HTML! Gasp!

http://www.dwheeler.com/essays/quotes-in-html.html

...as usual missing Fully Countering Trusting Trust through Diverse Double-Compiling

But who compiled the compiler?
http://www.ece.cmu.edu/~ganger/712.fall02/papers/p761-thompson.pdf

Actually, that, too, has been thought of and worked out. The trusting-trust attack can be fully countered through Diverse Double-Compiling. It's all over my head but the material is there at several levels of detail for those who would read it.

If you've compiled the compiler with competitors' compilers (try saying that ten times fast), you should be fairly safe from Trusting Trust.

> Scheme is great but the problem is I'm a crap programmer.

Actually the first sign of a great programmer is realizing they are not great ! :-)

THE key point that everyone forgets: We were ALL noobs at one point. You don't really master a language until you've been using it for years.

> prefer to pick a language where there are already tons of existing good libraries/modules/code I can _easily_ use to do what I want.

Yup, that's very pragmatic. However, I would add, EVERY programmer should know how to or have at least once in their lifetime written atoi() and the corresponding dual itoa() aka, printf.

From a business point of view you want to use a 3rd party library that just works.
From a learning point of view you should write everything yourself (once.)

> I don't normally have to support, document and fix that 3rd party code that I didn't write. ;)

Part of the process of becoming a great programmer is to not only WRITE your code but READ other people's code. The sides of the same coin help each other.

I _love_ the consistency and simplicity of LISP but hate its syntax. Thankfully there is a solution! Readable S-expressions is for LISP programmers who love C style braces but hate LISP parenthesis.

http://www.dwheeler.com/readable/

(Ugly) S-expression

(define (fibfast n)
  (if (< n 2)
    n
    (fibup n 2 1 0)))
define fibfast(n) ; Typical function notation
  if {n < 2} ; Indentation, infix {...}
    n ; Single expr = no new list
    fibup(n 2 1 0) ; Simple function calls
(define (fibup max count n-1 n-2)
  (if (= max count)
    (+ n-1 n-2)
    (fibup max (+ count 1) (+ n-1 n-2) n-1)))

compare with Sweet-expression 0.2

define fibup(max count n-1 n-2)
  if {max = count}
    {n-1 + n-2}
    fibup max {count + 1} {n-1 + n-2} n-1
(define (factorial n)
  (if (<= n 1)
    1
    (* n (factorial (- n 1)))))
define factorial(n)
  if {n <= 1}
    1
    {n * factorial{n - 1}} ; f{...} => f({...})

and

http://www.dwheeler.com/readable/retort-lisp-can-be-readable.html

"Even people like me, who have used Lisp for over 20 years, understand that it's a bug. I wrote my first Lisp program circa 1982, and professionally wrote Lisp code on $120,000 equipment. Lisp has advantages, which is why I used and use it.

But all the whining about it being "superficial" doesn't change the fact that most developers avoid Lisp-like languages, precisely because they're unreadable. There's a reason why Lisp is widely referred to as "Lots of Irritating Silly Parentheses" (and worse)."

--
The progression of a Lisp programmer:
* The newbie realizes that the difference between code and data is trivial.
* The expert realizes that all code is data.
* And the true master realizes that all data is code.
    -- Sriram Krishnan

> Scheme is great but the problem is I'm a crap programmer.

Actually the first sign of a great programmer is realizing they are not great ! :-)

THE key point that everyone forgets: We were ALL noobs at one point. You don't really master a language until you've been using it for years.

> prefer to pick a language where there are already tons of existing good libraries/modules/code I can _easily_ use to do what I want.

Yup, that's very pragmatic. However, I would add, EVERY programmer should know how to or have at least once in their lifetime written atoi() and the corresponding dual itoa() aka, printf.

From a business point of view you want to use a 3rd party library that just works.
From a learning point of view you should write everything yourself (once.)

> I don't normally have to support, document and fix that 3rd party code that I didn't write. ;)

Part of the process of becoming a great programmer is to not only WRITE your code but READ other people's code. The sides of the same coin help each other.

I _love_ the consistency and simplicity of LISP but hate its syntax. Thankfully there is a solution! Readable S-expressions is for LISP programmers who love C style braces but hate LISP parenthesis.

http://www.dwheeler.com/readable/

(Ugly) S-expression

(define (fibfast n)
  (if (< n 2)
    n
    (fibup n 2 1 0)))
define fibfast(n) ; Typical function notation
  if {n < 2} ; Indentation, infix {...}
    n ; Single expr = no new list
    fibup(n 2 1 0) ; Simple function calls
(define (fibup max count n-1 n-2)
  (if (= max count)
    (+ n-1 n-2)
    (fibup max (+ count 1) (+ n-1 n-2) n-1)))

compare with Sweet-expression 0.2

define fibup(max count n-1 n-2)
  if {max = count}
    {n-1 + n-2}
    fibup max {count + 1} {n-1 + n-2} n-1
(define (factorial n)
  (if (<= n 1)
    1
    (* n (factorial (- n 1)))))
define factorial(n)
  if {n <= 1}
    1
    {n * factorial{n - 1}} ; f{...} => f({...})

and

http://www.dwheeler.com/readable/retort-lisp-can-be-readable.html

"Even people like me, who have used Lisp for over 20 years, understand that it's a bug. I wrote my first Lisp program circa 1982, and professionally wrote Lisp code on $120,000 equipment. Lisp has advantages, which is why I used and use it.

But all the whining about it being "superficial" doesn't change the fact that most developers avoid Lisp-like languages, precisely because they're unreadable. There's a reason why Lisp is widely referred to as "Lots of Irritating Silly Parentheses" (and worse)."

--
The progression of a Lisp programmer:
* The newbie realizes that the difference between code and data is trivial.
* The expert realizes that all code is data.
* And the true master realizes that all data is code.
    -- Sriram Krishnan

OpenOffice/LibreOffice is like 90+% C++. The Java bits are mostly irrelevant.

To be precise, as computed by sloccount, libreoffice-4.0.0.3.tar.xz contains:

cpp: 3990644 (87.04%)
java: 400958 (8.75%)
ansic: 91036 (1.99%)
perl: 42456 (0.93%)
python: 17392 (0.38%)
sh: 17256 (0.38%)
yacc: 8228 (0.18%)
cs: 6648 (0.15%)
asm: 3269 (0.07%)
objc: 2602 (0.06%)
lex: 2030 (0.04%)
awk: 907 (0.02%)
pascal: 800 (0.02%)
csh: 235 (0.01%)
lisp: 115 (0.00%)
php: 104 (0.00%)
sed: 7 (0.00%)

However, as Desler said, the Java bits are actually optional.

The point is... you can find a browser that doesn't fuck you over and use that.

And you can find a phone that doesn't take advantage of you and use that. The trouble is, this sort of "doesn't take advantage of you" isn't exactly a selling point among the mass market, which means a product like this won't be produced for a mass-market price.

for things like, say, open source browsers, you can read the code and see what it is doing.

But do most people verify that the binary they download matches the source code? And do they diverse-double-compile their compiler toolchain to make sure it isn't infected with a "Reflections on Trusting Trust"-style virus? I'm under the impression most end users take this on faith.

There is no way you can avoid putting trust on something outside your own control, be it the C compiler

David A. Wheeler confirms it: the "trusting trust" attack is dead.

So what you really are asking is "where should I put my trust level". That depends extremely from person to person and is next to impossible to answer

Where should the median citizen of an industrialized country be expected to put his trust level?

Mentions of Ken Thompson's Reflections on Trusting Trust should also mention David A. Wheeler's "Fully Countering Trusting Trust" which provides a means of identifying and resolving a malicious compiler.

A compiler, not the.
Further, the compiler should yield the same result when compiling itself independent on which compiler the self-compiling compiler has been compiled with.

In other words, the "trusting trust" attack is defeated with several independently developed compiler toolchains.

Thus if you have another third party compiler you can bust this behaviour.

And there's the rub. I was under the impression that Apple had a monopoly on at least one part of the toolchain targeting iOS.

They have. Presentation: Open Source Software and the U.S. Department of Defense (DoD)

"Some mistakenly claim that the Internet and TCP/IP were specifically created to resist nuclear attacks; this is absolutely not true, since its parent the ARPANET was specifically created to share large systems. Yet it’s also a mistake to claim that there was no connection between the Internet and survivable networks; the Internet TCP/IP technology is an internetwork of data packets, and as noted earlier, packet-switching of data packets was created was to be survivable in case of disaster."

Source: http://www.dwheeler.com/innovation/innovation.html

If you're going to tell that story at least tell the whole thing. When the OpenDocument Format included OpenFormula with version 1.2, it became the very first format to have a standard for spreadsheet formulas. Prior to that, there were no standard or other formats with a standard way of defining formulas. ODF was the first.