From: wichita@cyberstation.net
Date: Sat, 30 Nov 1996 02:23:19 -0800 (PST)
To: "Dana W. Albrecht" <dwa@corsair.com>
Subject: Re: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
In-Reply-To: <199611252028.MAA16855@vishnu.corsair.com>
Message-ID: <Pine.BSI.3.95.961130041844.19278R-100000@citrine.cyberstation.net>
MIME-Version: 1.0
Content-Type: text/plain




On Mon, 25 Nov 1996, Dana W. Albrecht wrote:

> 
> 
> Our friend Don Woods seems to have inadvertently sparked what could be a 
> useful and serious discussion regarding "provably secure cryptography."



Not only that But I have proven that the IPG system is perfect, see the
proof at:

           http://www.netprivacy.com 

> 
And you can prove it to yourself, it is patently self evident iwhen you
examine the algorithm and uinderstand what it does.Need I say more.
Find out yourself.

Your friend,

Don Wood

> Not to be confused with the usual "unbreakable" snake oil we see peddled 
> so often, I refer to systems for which rigorous mathematical proof that 
> "there are no shortcuts" exists.  To my knowledge, no such systems, with 
> the exception of a real one-time pad, exist today.  However, I also 
> under the impression that ongoing research on this topic continues.  For 
> example, consider the work being done on "Lattice" cryptosystems (see 
> http://jya.com/lattice.htm).
> 
> "diGriz" is right.  Nothing precludes the existence of a cryptographic 
> algorithm for which a rigorous mathematical proof of "security" exists
> --- where "security" means a provable lower bound on the time required 
> for recovery of the key.  Indeed, it seems that finding such an 
> algorithm --- or providing the necessary rigorous proof for a current 
> algorithm --- is a laudable goal of academic cryptographic research.
> 
> Rigorous proofs of the non-existence of an algorithm are not new.  
> Neither are rigorous proofs that any algorithm which can solve a given 
> problem requires a minimal running time.  Or, in an even stronger sense, 
> that a particular known algorithm for a given problem is indeed a 
> (provably) optimal algorithm for that problem.
> 
> For a (non-cryptographic) example of a proof of the first sort --- that 
> is, that "there exists no algorithm" --- consider the famous "Halting 
> Problem" for Turing machines.  (I believe someone else has also 
> mentioned this.)  There are many proofs such as this one, often related, 
> though the Halting Problem itself is perhaps the most famous example.
> 
> For an (again, non-cryptographic) example of a proof of the second sort 
> --- that is, that "any algorithm that solves a given problem requires a 
> minimal running time" --- consider the proof that the "minimal" number 
> of key comparisons in the worst case required to sort a random list of 
> elements for which only an ordering relationship is known is O(nlog(n)).  
> See Knuth, Volume 3, section 5.3.  For a simpler example, a standard 
> "binary" search which requires O(log(n)) comparisons to find a given 
> element in the worst case is provably the optimal algorithm for this 
> task.
> 
> Turning once again to cryptography, there is presumably an "optimal" 
> algorithm for factoring a "general" number in the "worst" case.  Of 
> course, known algorithms for factorization seem to regularly improve and 
> no one has even suggested that any current algorithm is (provably) the 
> "optimal" algorithm.  Worse case bounds on running time for currently 
> known algorithms can certainly be produced, but no one currently knows 
> if these are the best algorithms.
> 
> However, just as one can say, "How do you know that tomorrow some 
> brilliant mathematician will not produce a polynomial time factorization 
> algorithm?" one can also say, "How do you know that tomorrow some 
> brilliant mathematician will not provide a rigorous proof that all 
> factorization algorithms --- in the worse case --- require some 
> specified minimal running time?"
> 
> While the current state of mathematical knowledge suggests that this is 
> not likely to happen anytime soon for the factorization problem, it is 
> encouraging to see work in areas where more rigorous proofs of security 
> are within closer reach.  Again, I refer to work on Lattice problems.  
> If the types of rigorous proof regarding "what can't be done" that are 
> known for the Halting Problem, sorting, and searching are available for 
> cryptographic problems, then this is indeed a major (and laudable) 
> advance in cryptography.
> 
> Obviously, discussion on this topic is unrelated to such security 
> problems as implementation mistakes, fault analysis, outright theft of 
> keys, etc.  I hope that I've been careful to explain what I mean by 
> "provably secure" and that it's not interpreted to include these types 
> of attacks.
> 
> I'm interested in the current state of research (if any) on this topic.  
> Other than what John Young sent to the list some time ago about Lattice 
> stuff --- which is certainly far from prime time --- I've not seen 
> anything else.  I also haven't devoted a lot of time to looking.
> 
> Relevant pieces of the earlier thread are included below.
> 
> Comments, anyone?
> 
> Dana W. Albrecht
> dwa@corsair.com
> 
> ----------------------------------------------------------------------------
> 
> 
> Eric Murray <ericm@lne.com> writes:
> > Don Wood <wichita@cyberstation.net> writes:
> > > Do not belive it, it will never happen. It is impossible,  and we can
> > > prove it to your satisfaction.
> > 
> > No, you can't.  It's impossible to prove an algorithim unbreakable.
> > You can only say that it hasn't been broken yet, but you can't
> > predict the advances in cryptoanalysis.
> > 
> > If, in two or three years, no one's broken it then maybe it'll seem
> > like a reasonably-secure algorithim.  Of course when someone does break
> > it you'll just say "oh, that wasn't the real algorithim" like you did
> > last time.
> 
> [ Snip ]
> 
> > You can't prove a negative.  The best IPG could say is that
> > it can't be broken with current technology.
> > Next week someone might come up with a new way
> > to break ciphers that renders the IPG algorithim breakable.
> > 
> > You point could have been that the same problem exists
> > for proofs- that next week someone could come up
> > with a way to prove, for all time, that an algorithim
> > really IS unbreakable.  So, to cover that posibility
> > I should have said "it's currently impossible to
> > prove an algorithim unbreakable". :-)
> 
> ----------------------------------------------------------------------------
> 
> "diGriz" anonymously writes: 
> > The good news is that you can prove a negative.  For example, it has
> > been proven that there is no algorithm which can tell in all cases
> > whether an algorithm will stop.
> 
> [ Snip ] 
> 
> > The best they can say is what they did say: they have a proof that
> > their system is unbreakable.  What you question, quite reasonably,
> > is whether they have such a proof.
> 
> [ Snip ]
>  
> > Or, more accurately, nobody credible has seen such a proof.  But, a
> > clever person might invent one.
> 
> ----------------------------------------------------------------------------
> 
> The Deviant <deviant@pooh-corner.com> writes: 
> > No, he was right.  They can't prove that their system is unbreakable.
> > They _might_ be able to prove that their system hasn't been broken, and
> > they _might_ be able to prove that it is _unlikely_ that it will be, but
> > they *CAN NOT* prove that it is unbreakable.  This is the nature of
> > cryptosystems.
> > 
> > > >The best IPG could say is that
> > > >it can't be broken with current technology.
> > > >Next week someone might come up with a new way
> > > >to break ciphers that renders the IPG algorithim breakable.
> > > 
> > > The best they can say is what they did say: they have a proof that
> > > their system is unbreakable.  What you question, quite reasonably,
> > > is whether they have such a proof.
> > 
> > It is impossible to prove such a thing.  It's like saying you have proof
> > that you have the last car of a certain model ever to be built.  Anybody
> > could come along and build another, and then you don't have the last one.
> > 
> > > 
> > > >You point could have been that the same problem exists
> > > >for proofs- that next week someone could come up
> > > >with a way to prove, for all time, that an algorithim
> > > >really IS unbreakable.  So, to cover that posibility
> > > >I should have said "it's currently impossible to
> > > >prove an algorithim unbreakable". :-)
> > > 
> > > Or, more accurately, nobody credible has seen such a proof.  But, a
> > > clever person might invent one.
> > 
> > There *IS NO SUCH PROOF*.  Just like you can't prove that god created the
> > universe, or that Oswald shot Kennedy, and so on and so forth.  It can't
> > be proven.  It never has been proven, and it never will be proven.  People
> > have new ideas, new algorithms are invented.  Someday, somebody will crack
> > _all_ the cryptosystems that have now been invented.
> 
> [ Snip ]
> 
> > diGriz anonymous writes:
> > > At 6:56 PM 11/23/1996, The Deviant wrote:
> > > >No, he was right.  They can't prove that their system is unbreakable.
> > > >They _might_ be able to prove that their system hasn't been broken, and
> > > >they _might_ be able to prove that it is _unlikely_ that it will be, but
> > > >they *CAN NOT* prove that it is unbreakable.  This is the nature of
> > > >cryptosystems.
> > > 
> > > Please prove your assertion.
> > > 
> > > If you can't prove this, and you can't find anybody else who has, why
> > > should we believe it?
> > 
> > Prove it?  Thats like saying "prove that the sun is bright on a sunny
> > day".  Its completely obvious.  If somebody has a new idea on how to
> > attack their algorithm, it might work.  Then the system will have been
> > broken.  You never know when somebody will come up with a new idea, so the
> > best you can truthfully say is "it hasn't been broken *YET*".  As I
> > remember, this was mentioned in more than one respected crypto book,
> > including "Applied Cryptography" (Schneier).
> 
> ----------------------------------------------------------------------------
> 
> "diGriz" Anonymously responds:
> > Page number?
> > 
> > Perhaps it would be helpful to hear a possible proof.  If somebody
> > were to show that breaking a certain cryptographic algorithm was
> > NP-complete, many people would find this almost as good as proof that
> > the algorithm is unbreakable.
> > 
> > Then if a clever person were to show that the NP-complete problems
> > were not solvable in any faster way than we presently know how, you
> > would have proof that a cryptographic algorithm was unbreakable.
> > 
> > There is no obvious reason why such a proof is not possible.
> > 
> > diGriz
> 



With Kindest regards,

Don Wood