| Jerrold Leichter wrote: | > "N-version programming" - which is what you are proposing here - can | > increase | > your level of trust against random errors[2], but its of no use at all | > against | > a deliberate attack. | | I heartly disagree. If the N-outputs are continuously verified for | coherence, any difference readily stands out. The number N and the cost of | always using those N-outputs should, of course, be outweighed against the | cost of failure to detect an attack. Theoretically, however, there is always | a finite number N that can make the probability of such an attack _ as small | as you please_. | | The mathematical basis for this result was proven by Shannon more than 50 | years ago; the practical intuition for this result was demonstrated during | the Mogul period in India (more than 500 years ago), who are known to have | used at least three parallel reporting channels to survey their provinces | with some degree of reliability, notwithstanding the additional efforts to | do so. All you've again proved is that you're misapplying the results.
Consider again the attack we are discussing: There is one very particular "magic" input that produces special, pre-determined results. In the case of the ACM paper, a particular input program produces slightly different code. But let's take a simpler example: A password-checking program that has a magic passcode that, when entered, is always accepted. Since you weren't clear how you were going to use your N versions, let's try two models: - You use your N versions for some huge number of rounds of testing, making sure they all produce the same result. (Let's use the password checker, since it that case "same result" is easy to determine.) The chance of your ever trying the single magic password is obviously vanishingly small. N is irrelevant. This is the model you *seemed* to be talking about, but perhaps not. - You use all N versions together in production, and watch for any errors. For the password application, that actually does work - though any value of N > 2 requires a rather bizarre threat model involving multiple coordinated attackers. It's hard to come up with any real-world situation in which you are concerned about up to, say, 10 people conspiring together against you but you can be certain that no 11 people will conspire. If we do indeed assume the second model, things get more difficult for the compiler. What do you verify? The object code from the N compilers all differ. You can't verify anything useful at that level. Maybe you have some kind of symbolic execution environment, and get use it for checking. Do you trust *it*? What compiler was *it* built with? In practice, you have to keep the N versions of each of your input programs all compiled by the N different compilers running in parallel forever, and compare their outputs. (And how many different linkers do you have? Run-time loader? Presumably you don't keep around N^2 or N^3 or N^4 versions - somehow you pick a representa- tive set. How? Doesn't sound easy, against an intelligent attack.) Anyway, suppose you've chosen your redundant set and can afford to run all the copies indefinitely. For something like a password checker, you have Boolean outputs and can easily compare. But let's try something more complex, say an implementation of a signature algorithm like DSA. You have N different versions which have to be different "all the way down" - including their random number generators. No two of your programs *ever* produce the same output for identical inputs. What will you compare? What does it mean to say that one of them produced an "incorrect" result? | > (Recall the conversation here a couple of months ago | > about how difficult - to the point of impossibility - it would be to use | > external testing to determine if a crypto-chip had been "spiked".) | | Aren't we talking about different things? A covert channel, looking at | the crypto-chip by itself, is demonstrably impossible to detect with | certainty. However, what I was talking about is NOT this situation. | You are looking at *one* crypto-chip, a single source of information, a single | trusted source, when you have no correction channel available. I am | looking at N outputs, N sources of information (each one as independent as | possible but not necessarily 100% independent). You have no reference for | detecting a "spike", I have N-1. As noted above, if randomization is used, the "spike" might be there but not be detectable even in principle. Even without randomization, many programs can produce all kinds of "equivalent" outputs. Compilers producing different by "acts the same" object are an expected example - but see Les Hatton's classic paper on errors in scientific programs (http://www.leshatton.org/IEEE_CSE_297.html). Hatton's other papers are also well worth a visit - they are some of the best papers on software engineering I know of. Of particular note for this discussion: "Are N average software versions better than 1 good version?" (http://www.leshatton.org/IEEE_Soft_97c.html) -- Jerry --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]