[Cryptography] Are zero knowledge authentication systems safe?

[Phillip Hallam-Baker]

On Sun, Nov 1, 2015 at 7:37 AM, Jerry Leichter <leichter at lrw.com> wrote:
>
>> Let us assume that we have a provably secure zero knowledge system. Is
>> it actually more secure in practice than other techniques?...
>>
>> Am I just missing the point or is this particular zero knowledge proof
>> rather brittle in practice?
> Koblitz and Menezes have been writing about issues with "proofs of difficulty" for close to a decade.  One overview is http://www.ams.org/notices/201003/rtx100300357p.pdf.  Over all, they make several points:
>
> 1.  The proofs that are out there, even if true, often don't prove what they claim;
> 2.  The trend in these proofs is in an unfortunate direction, based on reductions to problems more or less made up for the purpose and which there is actually almost no reason to accept at face value any claim of difficulty;
> 3.  One can find examples where algorithms were almost certainly made *weaker* in order to enable a "proof of security".
>
> They haven't specifically addressed the issue you raise - brittleness - though it's implicit in much of what they write.  My own take on this is that traditional mathematical techniques and results are *inherently* brittle.  Why?  Because the mathematician's goal is the most general possible theorem - the one that requires the bare minimum of constraints to be true.  But that means the instant you remove any of the remaining constraints - the theorem becomes false!  (Compare the reported NSA definition of a trusted party:  Someone who can break your security.)
>
> It's not that there hasn't been work that attempts to develop some kind of theory of robustness.  The whole field of concrete complexity - some of the pioneering work here was done by Bellare and Rogoway - at least started of as a way to develop such a theory.  (I haven't kept up with the literature and don't know where it is these days.)  But it's the direction relatively few have followed:  After a great deal of careful, complex analysis, you get fairly boring-sounding results.  Meanwhile, the guys making the assumptions come up with all kinds of sexy new algorithms and protocols....


The model I have always used to attempt to demonstrate robustness is
fairly simple. I start with the private key and look at everything
that 'touches' the key, i.e. has a dependence on it.

So the CPU touches the key and it consumes power and emits radiation.


Here we have a choice of two authentication algorithms. In particular
we potentially emit

ZK: x+r
PHB: H( e^xy + r )

where r is random

For the ZK proof we are absolutely depending on the randomness of r.
If there is any pattern in r then x will leak, no question. So it is a
brittle system.

For the PHB preferred approach, we are leaking a value that has a
strong dependency on x but it isn't a useful value. The only case in
which the value is going to be useful is if r is repeated. And if we
did that in the ZK proof the system becomes an oracle for r because
the attacker can simply ask for r instead of x+r.


We can save the simple ZK system though. let us say that as with the
simple ZK system we begin by committing e^r and the challenger has a
choice of

1) returning the proof that they didn't fake the commitment. (i.e. r).
2) presenting e^y and returning H(e^xyr)

It is still going to be a bear as far as CPU goes - 128 ECC
operations. That is a problem even for ED25519.

We can parallelize the rounds easily enough. This shouldn't be more
than a 2 or 3 round protocol. But the person attempting to log in is
going to present n*256 bits of commitments at some point where n is
the number of rounds we want. Thats 4KB for a WF of 2^128.

We could also offload operations from the client to the server so the
client does 196 ECC operations to 65 for the server.

Using a fast machine and an optimized implementation and Adam
Langley's code which is 200 microseconds for DHE, that would be 50ms
or so. Not horrible but still quite significant.

https://code.google.com/p/curve25519-donna/

Hmm, might be do-able but is the extra security worth the effort? Its
not just implementation etc. I would have to spend a week crawling
through the literature to see if anyone else had the same idea and
patented it.