Can you help develop crypto anti-spoofing/phishing tool ?

[Jerrold Leichter]

| 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 majordomo at metzdowd.com