[Cryptography] State of sin (was Re: What to put in a new cryptography course)

[Viktor Dukhovni]

On Mon, Jul 11, 2016 at 02:11:05PM -0400, Arnold Reinhold wrote:

> > *As a matter of theory and mathematics*, we're living in sin:  We assume
> > the problems we pick are hard because our best minds have brought our best
> > methods to bear on them and have not only made no progress, they've managed
> > to prove that *using these techniques* no progress is possible.
> > ...
> 
> The lack of mathematical proofs for the security of cryptographic primitives
> is a reality with which the cryptographic community is perhaps too
> comfortable.

The vast majority of cryptography lies in NP, since verifying the
correctness of a secret key is often rather simple.  To prove that
a typical cryptographic system is "hard", one would have to prove
that P != NP, for otherwise the system is likely insecure (though,
given the asymptotic nature of the distinction, the constants in a
reduction of a problem to P could make the P-time algorithm
impractical).

> We all know, of course that a mathematical proof of security
> would be traceable to the axioms of logic, and, at least for the existence
> of random quantitates, the laws of physics.

Given Goedel's incompleteness theorem, it is quite possible that
a system is secure and yet no proof of said security is possible.

> It's not just that we lack a proof that factoring is hard or that discrete
> logarithms in finite groups are difficult to compute, we don�t even know
> exactly what those words mean.

The words mean generally worst-case lower bounds on circuit sizes
and execution time.

> A recent example of this is the Logjam attack for which there was no new
> mathematics developed, merely a realization that most the work needed in
> the best attack on D-H in the group of integers modulo a prime p was only
> dependent on p, not on the group element whose logarithm was to be computed.

That fact was known since at least the early 90's.  Logjam was
merely the observation that servers that support export-grade DH
are vulnerable to a downgrade attack.

> Since many protocols use the same p for all D-H encryption, attacks became
> more feasible than previously thought. The assertion "D-H is hard" omitted
> that bit of fine print.  What other overlooked technicalities are out
> there behind statements that "X is assumed to be hard"?

This is simply not true.  D-H is hard for large-enough primes.
The fact that it is not hard for 512-bit primes is not new (known
since at least the early 90's).  1024-bit D-H is now perhaps within
reach of nation states, but 2048-bit likely requires new mathematical
breakthroughs that are not known in the public domain.

-- 
	Viktor.