[Security] Re: [Courses] zero-knowledge national ID system

[Terri Oda]

Just in case you want a more concrete example of a zero-knowledge, here's a 
simplified one from my course notes (I'm actually currently taking a course 
in cryptography and computer security... which is good, although not quite 
as in depth as I would have liked.  I've actually caught myself reading 
this list during class when I get bored. ;)  )

I'm not sure how this will look when I send it... but x^y implies that x is 
to the power y, and x_y implies x subscript y.

SPEKE is an example of a zero-knowledge protocol.

SPEKE Protocol:
Client                                                  Server
- password p                                            - password p
- generates a random integer a                          - generates a 
random integer b
                                 Q_A = p^2a mod q
                                 ----------------------------->
                                 <-----------------------------
                                 Q_B = p^2b mod q
computes K = (Q_B)^2a mod q                             computes K = 
(Q_A)^2b mod q
= p^4ab mod q                                           = p^4ab mod q

Then they both use K as a session key for future communications.

Analysis of SPEKE
1.      Eavesdropping
Given Q_A an attacker cannot guess p since Q_A is randomized with the value a.

Note that if we performed regular DH and A produced the value Q_A = g^p mod 
q, then knowledge of g, q allow a dictionary attack against Q_A.
2.      User Impersonation
An attacker is unable to compute a Q_A such that a common key can be shared 
without knowledge of the password p.
3.      Impersonation of the server
         Similar.