[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Provably "Secure" Crypto (was: IPG Algorithm Broken!)
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
> [email protected]
>
> ----------------------------------------------------------------------------
>
>
> Eric Murray <[email protected]> writes:
> > Don Wood <[email protected]> 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 <[email protected]> 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