Friday, May 18, 2012

Diving into the Socialist Millionaire Protocol


Ah, love the smell of multiplicative groups in the morning. While digging into what makes the SMP tick I created a copy that is nowhere near as subscript heavy. Both wikipedia and the OTR page use the same subscripty maths. It is all the same of course, but I tend to delegate subscripts to conceptual sequences rather than being used for two "random values chosen by party alice".

Alice:
  1. Picks random exponents a, b, and s
  2. Sends Bob ga and gb

    Bob:
  1. Picks random exponents c, d, and r
  2. Computes j = gca and k = gbd
  3. Computes M = kr and N = gr jy
  4. Sends Alice gc, gd , M and N

    Alice:
  1. Computes j = gac and k = gbd
  2. Computes P = ks and Q = gs jx
  3. Computes R = (Q / N) b
  4. Sends Bob P, Q and R

    Bob:
  1. Computes T = (Q / N) d
  2. Computes Z = Rd
  3. Checks whether Z == (P / M)
  4. Sends Alice T

    Alice:
  1. Computes Z = Tb
  2. Checks whether Z == (P / M)

For bob’s check:
Rd                 = P / M
(Q/N)db         = ks / kr
(gsjx / grjy )db = gbds / gbdr
g(s-r)dbg(x-y)db  = g(s-r)db
If x-y = 0 then the second term on the left side is forced to become 1. From an RTFM perspective, having javascript mouseovers and information flow throughout the formulas would be quite handy. Maybe for version 2.0.

So in this case you can prove that two parties both know the same shared secret (x == y) without the need for webs of trust and other systems.