Zero-bit vulnerabilities?

The other day, I overheard Seth Schoen ask the question, “What is the smallest change you can make to a piece of software to create a serious vulnerability?” We agreed that one bit is generally sufficient; for instance, in x86 assembly, the operations JL and JLE (corresponding to “jump if less than” and “jump if less than or equal to”) differ by one bit, and the difference between the two could very easily cause serious problems via memory corruption or otherwise. As a simple human-understandable example, imagine replacing “<” with “<=” in a bus ticket machine that says: “if ticket_issue_date < today, reject rider; else allow rider.”

At this point, I started feeling one-bit-upsmanship and wondered whether there was such a thing as a zero-bit vulnerability. Obviously, a binary that is “safe” on one machine can be malicious on a different machine (ex: if the second machine has been infected with malware), so let’s require that the software must be non-vulnerable and vulnerable on two machines that start in identical states. For simplicity, let’s also require that both machines are perfectly (read: unrealistically) airgapped, in the sense that there’s no way for them to change state based on input from other computers.

This seems pretty much impossible to me unless we consider vulnerabilities probabilistically generated by environmental noise during code execution. Two examples for illustration:

1. A program that behaves in an unsafe way if the character “A” is output by a random character generator that uses true hardware randomness (ex: quantum tunneling rates in a semiconductor).
2. A program that behaves in an unsafe way when there are single-bit flips due to radioactive decay, cosmic ray collisions, background radiation, or other particle interactions in the machine’s hardware. It turns out that these are well-known and have, in some historical cases, caused actual problems. In 2000, Sun reportedly received complaints from 60 clients about an error caused by background radiation that flipped, on average, one bit per processor per year! (In other words, Sun suffers due to sun.)

Which brings up a fun hypothetical question: if you design an SSL library that will always report invalid certificates as valid if ANY one bit in the library is flipped (but behaves correctly in the absence of single-bit flip errors), have you made a zero-bit backdoor?