Re: There's a hole in your crypto...

[Nathan Zook <nzook@bga.com>]

On Wed, 2 Aug 1995, David R. Conrad wrote:

> 
> 
> Phil Fraering writes:
> >Why are the arguments on either side so emotional?
> 
> I'm rather hesitant to jump into this thread, but I think that one
> reason is that Fred's concerns have been misunderstood a bit.  (If
> I'm wrong, I'm sure he'll correct me.)
> 
> It seems that there are many people who are ready to leap to the
> defense of the honor of the programmers behind PGP, when they feel
> said honor is being impugned.
> 
> I get the impression (as much from what I know of his background as
> from what he's said) that Fred is at least as concerned about PGP
> being a correct implementation of the various algorithms it involves
> as he is about back doors inserted by nefarious individuals.
> 
> As I understand it, it is impossible to demonstrate the correctness of
> any program the size of PGP.  And it would also not be possible to
> validate the compiler or the operating system.  One thing I'm not sure
> of, though, is this: Would it be possible to verify a much smaller
> program, say, the RSA-in-3-lines-of-Perl?  (Of course, you still would
> be left trying to verify the Perl interpreter, and the OS again.)
> 
> And is there any way to build trusted system out of small, verifiable
> pieces?  Since the way they're connected could also be questioned, I
> suspect that when you put enough of them together it's just as bad as
> the case of a single, monolithic program.  But this isn't my area, so
> I don't know.

No.  This was essentially proved during the first third of this century.

But even if the program itself works, you have to check the OS, the 
motherboard & the processor.  Did I say processor?  Yes, I did.  Anyone 
running on an 80586?

Nathan


> Would it be possible to formally verify at least some parts of a large
> program like PGP?  And would that add to the trustworthiness of the
> overall program?  (Keeping in mind Fred's earlier remark about a
> seemingly-unrelated portion of the code overwriting the key.)
> 
> --
> David R. Conrad, ab411@detroit.freenet.org, http://web.grfn.org/~conrad/
> Finger conrad@grfn.org for PGP 2.6 public key; it's also on my home page
> Key fingerprint =  33 12 BC 77 48 81 99 A5  D8 9C 43 16 3C 37 0B 50
> No, his mind is not for rent to any god or government.
>