Slashdot Mirror

Very interesting, thanks!

I also like Dennis Ritchie's comment in The Development of the C Language that the increment ++ and decrement -- operators were not chosen to match PDP-11 architecture: "This is historically impossible, since there was no PDP-11 when B was developed."

> Precisely. That's why only a fool calls C a "HLL".

Fools like Dennis Ritchie and Brian Kernighan, you mean?

Yes, and C is neither a "fancy assembler" nor "almost machine code". These are statements of an ignorant person.
Cough, Cough, Cough ...

You might be interested in reading this: https://www.bell-labs.com/usr/...

Perhaps you might want to use the search function and jump to "essentially, as a portable assembly language" ... you might want to note one of the first lines of the text, too: Dennis M. Ritchie

Dennis Ritchie had some interesting reflection:

"Thompson went a step further by inventing the ++ and -- operators, which increment or decrement; their prefix or postfix position determines whether the alteration occurs before or after noting the value of the operand. They were not in the earliest versions of B, but appeared along the way. People often guess that they were created to use the auto-increment and auto-decrement address modes provided by the DEC PDP-11 on which C and Unix first became popular. This is historically impossible, since there was no PDP-11 when B was developed. The PDP-7, however, did have a few `auto-increment' memory cells, with the property that an indirect memory reference through them incremented the cell. This feature probably suggested such operators to Thompson; the generalization to make them both prefix and postfix was his own. Indeed, the auto-increment cells were not used directly in implementation of the operators, and a stronger motivation for the innovation was probably his observation that the translation of ++x was smaller than that of x=x+1."

https://www.bell-labs.com/usr/dmr/www/chist.html

And you have to consider that when C was developed, some computer hardware had 6, 7, 8 or 9 bit bytes.

Not a concern. C was developed for the 16-bit PDP-11 and no consideration for other architectures until much later. The 'char' abstraction is the only nod to portability, and that could be handled by the compiler. C defined a char as "the smallest addressable memory unit that can hold a character in the machine's native character set."

Ritchie covered some of the design decisions (and departures from BCPL and B) in The Development of the C Language

Format drive and install one of the following operating systems:

• BeOS
• Syllable
• AROS
• Plan 9
• Minix
• FreeDOS
• DR-DOS
• OpenVMS x86 port is coming!
• Visopsys
• SqueakNOS
• Haiku
• Kolibri
• ReactOS
• Tizen
• SkyOS
• MorphOS
• MenuetOS
• CP/M 86
• Multics, also see Multicians
• Erlang as an Operating System

There have been a large number of more or less obscure operating systems and not all have been ported to x86. Unfortunately the architecture has become a de facto standard even though it's not the best architecture or the most efficient but instead a patchwork of solutions to retain backwards compatibility. We have lost many interesting architectures over the years that would have deserved a better fate to the Intel bandwagon.

Interesting note from Ritchie on that:

"Thompson went a step further by inventing the ++ and -- operators, which increment or decrement; their prefix or postfix position determines whether the alteration occurs before or after noting the value of the operand. They were not in the earliest versions of B, but appeared along the way. People often guess that they were created to use the auto-increment and auto-decrement address modes provided by the DEC PDP-11 on which C and Unix first became popular. This is historically impossible, since there was no PDP-11 when B was developed."

> C was conceived as a portable shorthand for assembly language.

Uh, no, it wasn't. It was conceived as a more efficient version of BCPL, descended from the Algol family.

There was absolutely no emphasis on portability at the start. Read: https://www.bell-labs.com/usr/dmr/www/chist.html

Or plan9.

> Perhaps you mean that Unix was not designed to portable.

Nope, I mean C.

Dennis Ritchie wrote:
"...we regretted losing the advantages of writing programs in a language above the level of assembler, such as ease of writing and clarity of understanding. At the time we did not put much weight on portability; interest in this arose later."

> UNIX and POSIX will become obsolete.

I think you misspelled "mature standard."

> Better and more powerful systems and concepts will take their place.

Yep.

> It was a good standard for it's time but now UNIX/POSIX is becoming outdated and insufficient.

Then why not replace it instead of breaking it? There's an old saying: "If it works, don't fuck with it."

When creating B K&R seem to [...]

Nitpick: B was created by Ken Thompson and Dennis Ritchie, and then further developed by Stephen C. Johnson. Brian Kernighan was not particularly involved in its creation, although he wrote a tutorial on it.

It really wasn't. C was developed out of B and BCPL, largely so they could implement types and data structures beyond what they could do in assembly. They already had an assembler, and if they were interested in "glorifying" it with syntactic sugar, they would have simply added something like the C preprocessor.

C wasn't even portable in the beginning, according to Ritchie's The Development of the C Language - interest in that aspect came later.

That paper is a fascinating read. It's a window into the goals they were trying to reach for their system, and they certainly didn't have a vision of how ubiquitous C would become - it was simply a tool for their own use, to make their jobs simpler.

You may find this interesting reading.

In old versions of UNIX (not open source, but only because there was no such distinction at the time - the source was very much available) the compiler would add code to any program you tried to compile named 'login'. You could look at the source for the login program all you want and never see the backdoor. You also would have a hard time finding the code in the C compiler.

And this was just something Ken Thompson did to prove that he could. Imagine what the NSA would be capable of.

What if this was an intentional backdoor so that they-who-shall-not-be-named can spy on internet traffic of closed networks and WISPS?

And it was not included in the the source packages because the source is subjected to a gag order and publishing it would be showing it to the world.

Lastly, if this is true, what if this is "standard procedure" for backdoors inserted into many open-source projects, where the code presented is actually a fork of the true, backdoored code, running on lots of hardware? Or, as per Ken Thompson's watershed article, "Reflections on Trusting Trust", they-who-shall-not-be-named has a version of GCC capable of adding backdoors to open source code and we're all blaming Ubiquiti for something they didn't even put there?

I'll be the first to admit, there's plenty of speculation here. But if there's anything we've learned in the last few years, the state of spying is way more prevalent than we thought it was. So while I have no proof, I'm certainly holding onto this information should more evidence come out.

If this hadn't been done ten years before he talked about, it's been done by now. They have everything they want. Live accordingly.

Fortunately, we know how to counter that threat.

It also seems pretty unlikely that the NSA had enough foresight to get VC++ instrumented to subvert TrueCrypt. It's not impossible, but there have been a lot of similar tools over the years, and I don't think the compilers could have been modified to subvert all of them.

If this hadn't been done ten years before he talked about, it's been done by now. They have everything they want. Live accordingly.

You seem to be under the assumption that your hardware, and your compiler are incapable of being attack vectors.

http://cm.bell-labs.com/who/ke...

Ken Thompson was a visionary, but he probably didn't envision it'd be his own government doing the compromising:
Reflections on Trusting Trust

As a programmer, I find systemd horrible. It breaks compatibility with Unix. It's a nightmare that will shrink the open source landscape to just linux. The rest of us must now reinvent basics like toolkits, web browsers, etc because Linux zealots want to take over the world.

Or you could just bang around on this.

Pre-emptive multitasking with 1000hz scheduler, multiprocessor, multithreading, ring-3 protection
Responsive GUI with resolutions up to 1920x1080, 16 million colours
Free-form, transparent and skinnable application windows, drag'n drop
SMP multiprocessor support with currently up to 8 cpus
IDE: Editor/Assembler for applications
USB 2.0 HiSpeed Classes: Storage, Printer, Webcam Video and TV/Radio support
USB 1.1 Keyboard and Mouse support
TCP/IP stack with Loopback & Ethernet drivers
Email/ftp/http/chess clients and ftp/mp3/http servers
Hard real-time data fetch
Fits on a single floppy, boots also from CD and USB drives

Since the blurb was writtten, browser, digital tv, webcam, movies, etc. have been added.

Or you can play around with Plan9 - runs by itself or as an application atop linux, windows, etc.

Huh? See Reflections on Trusting Trust, from back in the pre-NSA days where one special guy could easily log into any Unix system: "I could log into that system as any user."

He's not BSing or joking, either.

You're distorting the point of his article. I really get sick of non-security people who don't know much about programing referencing Ken Thompson. It's asinine to say you can't trust code that you did not totally create yourself.

There are a number of ways to audit compilers and the hardware that composes a computer system for tampering and malicious behavior.

http://programmers.stackexchange.com/questions/184874/is-ken-thompsons-compiler-hack-still-a-threat

I had a high-security scenario ... [and] was happy enough that everything was traced back the sources enough to make me feel secure.

So you've compiled "everything" from source code? Then you're all good to go -- the code will be exactly what the compiler produced, but NOT necessarily what the source code actually says.

Huh? See Reflections on Trusting Trust, from back in the pre-NSA days where one special guy could easily log into any Unix system: "I could log into that system as any user."

He's not BSing or joking, either.

Did you write a secure compiler for it, too?

Ken Thompson modified the original C compiler to put a back door into the Unix login program, as well as to modify any compiler that was compiled with that compiler to include the backdoor function. So for generations of code, and backdoor was inserted, with no evidence of its existence in any code you could examine.

http://cm.bell-labs.com/who/ke...

This is what you sound like to me:

OK, so I don't know much about programming and stuff but I still can't understand how you create $VIDEOGAME without a game engine. Apparently the $VIDEOGAME was written in pure C. How can you achieve such a thing?

That is to say, just as you can create a game via leveraging prebuilt functions of an existing engine or write the code yourself in $LANGUAGE, you can create $PROGRAM via leveraging prebuilt functions of $HARDWARE or design the dedicated hardware itself to perform the logic. We also had 3D graphics before hardware accelerated triangle rendering boards too. Specialized hardware/software platforms can be useful (especially if processing or development time is a bottleneck) but they are far from necessary. In fact, I often find them limiting and/or wasteful.

E.g.,with a software rasterizer instead of GPU rendering pipeline I only needed one copy of the geometry in memory at a time, and the input/network/physics functions can operate on the same geometry data as the rendering system uses; Contrast that with having an asset manager to shovel data across the tiny graphics bus, and often keeping two or more copies of 3D data in memory: One for physics on the "CPU" side, one for rendering on the GPU side of the bus, one for network state updates and lag-compensation (because functional programming lends itself to batches, and multiple cores exist). With a fully programmable pipeline (yay geometry shaders!) we're finally getting back most of the freedom we had back in software only rendering. With shared memory architecture we're finally getting back most of the freedom we had in CPU side only rendering. Perhaps with something like faster reprogrammable FPGAs we'll finally get back some of the freedom we lost to CPUs when we migrated away from ASIC. Well, the game cartridges COULD have their own logic and data, and other custom circuits, but they weren't really ASIC since they could provide input devices too, see GBA games with photocells to change the game world to match your environmental light or with mics, or carts with save functions built-in made for consoles without data storage, etc.

You see, someday when we're forced to 3D print all our own chips because of the Ken Thompson Hack (which indicates we can't trust any software or hardware stack one didn't create oneself) we'll finally have back the freedom to create video games we once had when the game wasn't restricted to running on existing (read: shitty/limited) hardware.

TL;DR: Would you like to know more?

You can install a firmware that is compiled from the open source you trust.

Ken Thompson had something to say about that. Are you hand-compiling that OS using your own tools and not the vendor-supplied toolchain?

There is still the possibility of hardware level backdoors, but there are a 100 different manufactures of Android devices, many of them have little to no presence in the USA

...and are largely from countries with no cultural history of valuing privacy. Now instead of being suspicious of Apple or Microsoft, you have to be suspicious of 100 individual vendors.

Versus Apple, Microsoft, etc who are easy targets for US courts orders

...and US court lawsuits. For the first time maybe ever, it seems like the non-geek people around me are starting to get why security is important and are taking it seriously. Apple and MS have a lot more to lose than $RANDOM_CHINESE_VENDOR who can still sell their bad-American-repped $30 phones in developing countries if they're kicked out of America. Take away Apple's North American market and they'd fold overnight. They've been bragging about their security and crypto for a while now to the point of making it a marketing point, and breaking their promise to consumers would likely be catastrophic.

(credit to http://cm.bell-labs.com/cm/cs/...) And yes, let me forestall a lot of comment -- as the link above mentions, the code associated with this comment in the v6 UNIX kernel was wrong.

In case you're not feeling paranoid enough yet:
Reflections on Trusting Trust

Any medium with the right coding. Do your homework ! Read Noisy-channel_coding_theorem and A Mathematical Theory of Communication -- C. E. SHANNON.

Despite the fact that there's no way to know if the code you're reviewing matches the installed binaries.

Even if the binaries were created with the unmodified binaries reviewed, you would need to review the compiler binaries as well.

If you have a hole in the side of your bank, you don't fight the theves forever, you fix the fucking hole in your bank.

You've made some terrible assesments of reality. You can't even see the holes anymore.

"Fight this", "fight that", you're a shadowboxing fool.

"not really, until you can 3-d print it yourself and then verify with an xray will security be verified."

What if both your 3D printer and X-Ray data analysis software are compromised? See also:
"Reflections on Trusting Trust" by Ken Thompson
    http://cm.bell-labs.com/who/ke...
"The final step is represented in Figure 7. This simply adds a second Trojan horse to the one that already exists. The second pattern is aimed at the C compiler. The replacement code is a Stage I self-reproducing program that inserts both Trojan horses into the compiler. This requires a learning phase as in the Stage II example. First we compile the modified source with the normal C compiler to produce a bugged binary. We install this binary as the official C. We can now remove the bugs from the source of the compiler and the new binary will reinsert the bugs whenever it is compiled. Of course, the login command will remain bugged with no trace in source anywhere ... The moral is obvious. You can't trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code. In demonstrating the possibility of this kind of attack, I picked on the C compiler. I could have picked on any program-handling program such as an assembler, a loader, or even hardware microcode. As the level of program gets lower, these bugs will be harder and harder to detect. A well installed microcode bug will be almost impossible to detect."

Still, the more angles you look at something from, the more likely you might detect some discrepancy... Like excess power usage, processing delays, slightly different electromagnetic signatures, etc...

In any case, the less you want, perhaps the easier it is to secure. Look into creating or using Forth chips for simplicity... The less gates you need, and the less cycles they need, the easier it would be to make your own hardware from scratch, even from discrete components if it is simple enough.
http://www.colorforth.com/
http://www.greenarraychips.com...

For software more complex than Forth that is still fairly understandable from the ground up, see also the FONC project by Alan Kay as well as Squeak on bare metal.
http://www.viewpointsresearch....
https://www.google.com/search?...

Easy solution:

Put all of your systems in to one big active/active server cluster. Then everyone is sharing all the resources evenly by default.

Here is a Fedora resource:
http://clusterlabs.org/doc/en-...

If you really want to have some fun you should try to create a Plan9 cluster. This is a transparent cluster OS that was designed for the purpose of resource sharing.
http://plan9.bell-labs.com/pla...

Fool.

Kernighan wasn't involved until much later, according to Ritchie's own history of the language. C was a direct successor to B, which was Thompson's brainchild, and he was directly involved in much of the development of C, though Ritchie was the lead on it.

People often assume it was Kernighan and Ritchie because they co-authored the seminal book on the language (the eponymous K&R white book), but that book didn't even get published until almost 6 years after C was already complete.

On trusting trust - K. Thompson, Bell labs. A classic.

Regarding the toolchain being compromised, there is an article from 1984 by Ken Thompson which outlines the effect. As to whether it's been seen in the wild... how would we know?

Ken Thompson on trusting trust. http://cm.bell-labs.com/who/ke...

except it's not true that all working interpreters are direct c interpreters. plan 9's rc implements a virtual machine (which it even bootstraps) and interprets the virtual machine.

How come? When was that true?

Looking through the source code of rc (http://plan9.bell-labs.com/sources/plan9/sys/src/cmd/rc/) there is absolutely nothing of the sort.

It's a simple interpreter that creates some intermediate bytecode out of the syntax tree, and then execute it in a stack machine.

Very much like mawk or such.

You probably have vague recollections about limbo/inferno, go or other similar failures they've churned out since then.

"compile by hand" and "assemble by hand" means "write out the results on paper".

After that, you have to get the machine code into core. That's what the front panel is for.

Is this somehow new to you? Are you really that young, and that unfamiliar with computing history?

Of course, if you have a functional operating system you think you can trust, you can poke the machine code into a file using a binary editor (that you think you can trust), and then execute that file as the compiler.

Read about bootstrapping. It's a real thing, or at least was. Cross-compiling has kind of eliminated the need, except in the rather exotic use case that you don't trust the compiler (à la Ken Thompson).

According to Ken Thompson, if you don't also analyze all the tools involved in the software build and load process at the machine code level, you still can't really trust the code. That means compilers, linkers, loaders, etc. Someone who knows what they are doing, and has enough motiviation to go through the effort, could insert code into a compiler that does whatever they want when your code is built with it, and hides itself at the source level.

These days CPUs are sophisticated enough that you probably would need to check them (and any microcode layer they may have) as well.

Don't forget to audit the compilers too. And the compiler's compilers...

Why not just link to the original work instead of some blog entry? Reflections on Trusting Trust

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.

Why should he (or anyone else) bother with keyboard shortcuts when the guys at bell labs proved that mouse beats keyboard by a pretty large margin?

Correct First, Clever Later is my core philosophy. There is nothing I don't abstract via portability layer.

I wrote a "hobby" OS kernel from scratch, starting only with a bootable hex editor on x86. The FIRST thing I did was create a simple bytecode VM to call into a function table to give me ASM level abstraction, before I even switched out of realmode to protected mode. 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. A bytecode to machine code compiler was one of the very last things that got written (it was boring). All programs on my OS (yes even Java or C code) compiles into bytecode and the kernel can link programs into machine code at "install time" or include the (shared mem page) VM stub and run them as emulated -- Which is nice to provide application plugins, scripting, or untrusted code. Since the kernel is compiling things it can do far more checks on the validity of binary code, as well as optimizations. Since multiple languages can compile to the same bytecode I can transparently integrate libraries written in different languages instead of each language needing it's own implementation of basic things like big-integer math. I can even change calling conventions on the fly for transparent RPC.

For Gravmass last year I got some nifty embedded ARM systems to upgrade a few of my my x86 robotics projects with (for better battery life). Instead of building a cross compiler (which takes a while) and compiling the OS components into ARM from x86, I just implemented the bytecode VM on ARM in one weekend, and I had my full OS software stack up and running (albeit slowly since I lacked native compilation).

I took the time to do things right so porting painless and it was actually fun to migrate to a whole new architecture. Then I was free to debug, build, and test stuff right on the hardware over serial console. Now I've got a project to build a usable computer from scratch (a transistor version of a CPU I built from about 400 contactors) and the new system will use my VM bytecode as its native machine language, so I won't have to write a compiler. I'm just taking things nice and easy, even teaching kids and neighborhood enthusiasts CS101 as I go. Man it sure is nice to have as much time as I want on these hobby projects -- Time to actually do things absolutely correct first, then as clever as I dream of later...

However, imagine a Publisher is breathing down your neck to get things up and working and done before a deadline. They don't care about you making it harder to porting your code to a new system, right now what matters is getting your basic engine up and running pronto so other folks can start working with their content on the dev kits / consoles. Now imagine even if you started out with a cross platform system, you've got to squeeze a new feature in and it needs to work fast, and yesterday -- No, you don't have time to write a slow version and a fast non-portable version and you've made this sort of addition so many times that it's hasn't been possible to run the slow portable code with the latest assets in over a year.

Yeah, the GPU and shaders aren't all that different but this new platform is the difference between porting a program design from Erlang to a multi-threaded C program. Getting an image up isn't just getting a spinning flat-shaded teapot displayed -- You've got a bunch of code in your asset loading system to handle your data storage format before you can even get started, and both of these were optimized for the CELL processor's big endian while the new platform is little endian. The asset streaming was probably done in several stages distributed among the CPUs, and operating on batches of data a few KB at a time. I've got no doubt that before you could see a properly textured and lit wall there'd be some serious liftin

If you want accuracy, you go to a journalist.

That's debatable, given that cybernetically this is a special case of the Ken Thompson Unix Compiler Hack.

Which watchers who watch what watchers warrant watching?

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.

So, what are these algorithms that are impossible to backdoor either through design or implementation? No chance of another something like heartbleed, or Reflections on Trusting Trust?

There is actually nothing wrong with the algorithm for Dual_EC_DRBG, the issue is with people's trust of the constants that define the curve for it in the standard. The only issue there is that people don't trust them just like they didn't trust the NSA generated S-boxes that strengthened DES against secret cryptanalysis techniques. Choosing a new set of known good constants for the standard would resolves all the issues other than performance. Of course that would mean you would need to verify the new configuration was still good and generated proper numbers. (And no matter what you do there will be people that mistrust it, just as this thread started.)

Paranoia can be a useful factor in dealing with security, but it should be moderated and harnessed in a positive manner. If not you end up making mistakes due to poor judgment as I discussed in my other post on DES. You assume the worst case, flop around and make an ever worse choice.

Unless you compile from vetted source code on an un-compromised system using an un-compromised compiler

A very interesting (and quite short) read about that : Reflections on Trusting Trust