smp.go

// Copyright 2012 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements the Socialist Millionaires Protocol as described in
// http://www.cypherpunks.ca/otr/Protocol-v2-3.1.0.html. The protocol
// specification is required in order to understand this code and, where
// possible, the variable names in the code match up with the spec.

package otr

import (
	"bytes"
	"crypto/sha256"
	"errors"
	"hash"
	"math/big"
)

type smpFailure string

func (s smpFailure) Error() string {
	return string(s)
}

var smpFailureError = smpFailure("otr: SMP protocol failed")
var smpSecretMissingError = smpFailure("otr: mutual secret needed")

const smpVersion = 1

const (
	smpState1 = iota
	smpState2
	smpState3
	smpState4
)

type smpState struct {
	state                  int
	a2, a3, b2, b3, pb, qb *big.Int
	g2a, g3a               *big.Int
	g2, g3                 *big.Int
	g3b, papb, qaqb, ra    *big.Int
	saved                  *tlv
	secret                 *big.Int
	question               string
}

func (c *Conversation) startSMP(question string) (tlvs []tlv) {
	if c.smp.state != smpState1 {
		tlvs = append(tlvs, c.generateSMPAbort())
	}
	tlvs = append(tlvs, c.generateSMP1(question))
	c.smp.question = ""
	c.smp.state = smpState2
	return
}

func (c *Conversation) resetSMP() {
	c.smp.state = smpState1
	c.smp.secret = nil
	c.smp.question = ""
}

func (c *Conversation) processSMP(in tlv) (out tlv, complete bool, err error) {
	data := in.data

	switch in.typ {
	case tlvTypeSMPAbort:
		if c.smp.state != smpState1 {
			err = smpFailureError
		}
		c.resetSMP()
		return
	case tlvTypeSMP1WithQuestion:
		// We preprocess this into a SMP1 message.
		nulPos := bytes.IndexByte(data, 0)
		if nulPos == -1 {
			err = errors.New("otr: SMP message with question didn't contain a NUL byte")
			return
		}
		c.smp.question = string(data[:nulPos])
		data = data[nulPos+1:]
	}

	numMPIs, data, ok := getU32(data)
	if !ok || numMPIs > 20 {
		err = errors.New("otr: corrupt SMP message")
		return
	}

	mpis := make([]*big.Int, numMPIs)
	for i := range mpis {
		var ok bool
		mpis[i], data, ok = getMPI(data)
		if !ok {
			err = errors.New("otr: corrupt SMP message")
			return
		}
	}

	switch in.typ {
	case tlvTypeSMP1, tlvTypeSMP1WithQuestion:
		if c.smp.state != smpState1 {
			c.resetSMP()
			out = c.generateSMPAbort()
			return
		}
		if c.smp.secret == nil {
			err = smpSecretMissingError
			return
		}
		if err = c.processSMP1(mpis); err != nil {
			return
		}
		c.smp.state = smpState3
		out = c.generateSMP2()
	case tlvTypeSMP2:
		if c.smp.state != smpState2 {
			c.resetSMP()
			out = c.generateSMPAbort()
			return
		}
		if out, err = c.processSMP2(mpis); err != nil {
			out = c.generateSMPAbort()
			return
		}
		c.smp.state = smpState4
	case tlvTypeSMP3:
		if c.smp.state != smpState3 {
			c.resetSMP()
			out = c.generateSMPAbort()
			return
		}
		if out, err = c.processSMP3(mpis); err != nil {
			return
		}
		c.smp.state = smpState1
		c.smp.secret = nil
		complete = true
	case tlvTypeSMP4:
		if c.smp.state != smpState4 {
			c.resetSMP()
			out = c.generateSMPAbort()
			return
		}
		if err = c.processSMP4(mpis); err != nil {
			out = c.generateSMPAbort()
			return
		}
		c.smp.state = smpState1
		c.smp.secret = nil
		complete = true
	default:
		panic("unknown SMP message")
	}

	return
}

func (c *Conversation) calcSMPSecret(mutualSecret []byte, weStarted bool) {
	h := sha256.New()
	h.Write([]byte{smpVersion})
	if weStarted {
		h.Write(c.PrivateKey.PublicKey.Fingerprint())
		h.Write(c.TheirPublicKey.Fingerprint())
	} else {
		h.Write(c.TheirPublicKey.Fingerprint())
		h.Write(c.PrivateKey.PublicKey.Fingerprint())
	}
	h.Write(c.SSID[:])
	h.Write(mutualSecret)
	c.smp.secret = new(big.Int).SetBytes(h.Sum(nil))
}

func (c *Conversation) generateSMP1(question string) tlv {
	var randBuf [16]byte
	c.smp.a2 = c.randMPI(randBuf[:])
	c.smp.a3 = c.randMPI(randBuf[:])
	g2a := new(big.Int).Exp(g, c.smp.a2, p)
	g3a := new(big.Int).Exp(g, c.smp.a3, p)
	h := sha256.New()

	r2 := c.randMPI(randBuf[:])
	r := new(big.Int).Exp(g, r2, p)
	c2 := new(big.Int).SetBytes(hashMPIs(h, 1, r))
	d2 := new(big.Int).Mul(c.smp.a2, c2)
	d2.Sub(r2, d2)
	d2.Mod(d2, q)
	if d2.Sign() < 0 {
		d2.Add(d2, q)
	}

	r3 := c.randMPI(randBuf[:])
	r.Exp(g, r3, p)
	c3 := new(big.Int).SetBytes(hashMPIs(h, 2, r))
	d3 := new(big.Int).Mul(c.smp.a3, c3)
	d3.Sub(r3, d3)
	d3.Mod(d3, q)
	if d3.Sign() < 0 {
		d3.Add(d3, q)
	}

	var ret tlv
	if len(question) > 0 {
		ret.typ = tlvTypeSMP1WithQuestion
		ret.data = append(ret.data, question...)
		ret.data = append(ret.data, 0)
	} else {
		ret.typ = tlvTypeSMP1
	}
	ret.data = appendU32(ret.data, 6)
	ret.data = appendMPIs(ret.data, g2a, c2, d2, g3a, c3, d3)
	return ret
}

func (c *Conversation) processSMP1(mpis []*big.Int) error {
	if len(mpis) != 6 {
		return errors.New("otr: incorrect number of arguments in SMP1 message")
	}
	g2a := mpis[0]
	c2 := mpis[1]
	d2 := mpis[2]
	g3a := mpis[3]
	c3 := mpis[4]
	d3 := mpis[5]
	h := sha256.New()

	r := new(big.Int).Exp(g, d2, p)
	s := new(big.Int).Exp(g2a, c2, p)
	r.Mul(r, s)
	r.Mod(r, p)
	t := new(big.Int).SetBytes(hashMPIs(h, 1, r))
	if c2.Cmp(t) != 0 {
		return errors.New("otr: ZKP c2 incorrect in SMP1 message")
	}
	r.Exp(g, d3, p)
	s.Exp(g3a, c3, p)
	r.Mul(r, s)
	r.Mod(r, p)
	t.SetBytes(hashMPIs(h, 2, r))
	if c3.Cmp(t) != 0 {
		return errors.New("otr: ZKP c3 incorrect in SMP1 message")
	}

	c.smp.g2a = g2a
	c.smp.g3a = g3a
	return nil
}

func (c *Conversation) generateSMP2() tlv {
	var randBuf [16]byte
	b2 := c.randMPI(randBuf[:])
	c.smp.b3 = c.randMPI(randBuf[:])
	r2 := c.randMPI(randBuf[:])
	r3 := c.randMPI(randBuf[:])
	r4 := c.randMPI(randBuf[:])
	r5 := c.randMPI(randBuf[:])
	r6 := c.randMPI(randBuf[:])

	g2b := new(big.Int).Exp(g, b2, p)
	g3b := new(big.Int).Exp(g, c.smp.b3, p)

	r := new(big.Int).Exp(g, r2, p)
	h := sha256.New()
	c2 := new(big.Int).SetBytes(hashMPIs(h, 3, r))
	d2 := new(big.Int).Mul(b2, c2)
	d2.Sub(r2, d2)
	d2.Mod(d2, q)
	if d2.Sign() < 0 {
		d2.Add(d2, q)
	}

	r.Exp(g, r3, p)
	c3 := new(big.Int).SetBytes(hashMPIs(h, 4, r))
	d3 := new(big.Int).Mul(c.smp.b3, c3)
	d3.Sub(r3, d3)
	d3.Mod(d3, q)
	if d3.Sign() < 0 {
		d3.Add(d3, q)
	}

	c.smp.g2 = new(big.Int).Exp(c.smp.g2a, b2, p)
	c.smp.g3 = new(big.Int).Exp(c.smp.g3a, c.smp.b3, p)
	c.smp.pb = new(big.Int).Exp(c.smp.g3, r4, p)
	c.smp.qb = new(big.Int).Exp(g, r4, p)
	r.Exp(c.smp.g2, c.smp.secret, p)
	c.smp.qb.Mul(c.smp.qb, r)
	c.smp.qb.Mod(c.smp.qb, p)

	s := new(big.Int)
	s.Exp(c.smp.g2, r6, p)
	r.Exp(g, r5, p)
	s.Mul(r, s)
	s.Mod(s, p)
	r.Exp(c.smp.g3, r5, p)
	cp := new(big.Int).SetBytes(hashMPIs(h, 5, r, s))

	// D5 = r5 - r4 cP mod q and D6 = r6 - y cP mod q

	s.Mul(r4, cp)
	r.Sub(r5, s)
	d5 := new(big.Int).Mod(r, q)
	if d5.Sign() < 0 {
		d5.Add(d5, q)
	}

	s.Mul(c.smp.secret, cp)
	r.Sub(r6, s)
	d6 := new(big.Int).Mod(r, q)
	if d6.Sign() < 0 {
		d6.Add(d6, q)
	}

	var ret tlv
	ret.typ = tlvTypeSMP2
	ret.data = appendU32(ret.data, 11)
	ret.data = appendMPIs(ret.data, g2b, c2, d2, g3b, c3, d3, c.smp.pb, c.smp.qb, cp, d5, d6)
	return ret
}

func (c *Conversation) processSMP2(mpis []*big.Int) (out tlv, err error) {
	if len(mpis) != 11 {
		err = errors.New("otr: incorrect number of arguments in SMP2 message")
		return
	}
	g2b := mpis[0]
	c2 := mpis[1]
	d2 := mpis[2]
	g3b := mpis[3]
	c3 := mpis[4]
	d3 := mpis[5]
	pb := mpis[6]
	qb := mpis[7]
	cp := mpis[8]
	d5 := mpis[9]
	d6 := mpis[10]
	h := sha256.New()

	r := new(big.Int).Exp(g, d2, p)
	s := new(big.Int).Exp(g2b, c2, p)
	r.Mul(r, s)
	r.Mod(r, p)
	s.SetBytes(hashMPIs(h, 3, r))
	if c2.Cmp(s) != 0 {
		err = errors.New("otr: ZKP c2 failed in SMP2 message")
		return
	}

	r.Exp(g, d3, p)
	s.Exp(g3b, c3, p)
	r.Mul(r, s)
	r.Mod(r, p)
	s.SetBytes(hashMPIs(h, 4, r))
	if c3.Cmp(s) != 0 {
		err = errors.New("otr: ZKP c3 failed in SMP2 message")
		return
	}

	c.smp.g2 = new(big.Int).Exp(g2b, c.smp.a2, p)
	c.smp.g3 = new(big.Int).Exp(g3b, c.smp.a3, p)

	r.Exp(g, d5, p)
	s.Exp(c.smp.g2, d6, p)
	r.Mul(r, s)
	s.Exp(qb, cp, p)
	r.Mul(r, s)
	r.Mod(r, p)

	s.Exp(c.smp.g3, d5, p)
	t := new(big.Int).Exp(pb, cp, p)
	s.Mul(s, t)
	s.Mod(s, p)
	t.SetBytes(hashMPIs(h, 5, s, r))
	if cp.Cmp(t) != 0 {
		err = errors.New("otr: ZKP cP failed in SMP2 message")
		return
	}

	var randBuf [16]byte
	r4 := c.randMPI(randBuf[:])
	r5 := c.randMPI(randBuf[:])
	r6 := c.randMPI(randBuf[:])
	r7 := c.randMPI(randBuf[:])

	pa := new(big.Int).Exp(c.smp.g3, r4, p)
	r.Exp(c.smp.g2, c.smp.secret, p)
	qa := new(big.Int).Exp(g, r4, p)
	qa.Mul(qa, r)
	qa.Mod(qa, p)

	r.Exp(g, r5, p)
	s.Exp(c.smp.g2, r6, p)
	r.Mul(r, s)
	r.Mod(r, p)

	s.Exp(c.smp.g3, r5, p)
	cp.SetBytes(hashMPIs(h, 6, s, r))

	r.Mul(r4, cp)
	d5 = new(big.Int).Sub(r5, r)
	d5.Mod(d5, q)
	if d5.Sign() < 0 {
		d5.Add(d5, q)
	}

	r.Mul(c.smp.secret, cp)
	d6 = new(big.Int).Sub(r6, r)
	d6.Mod(d6, q)
	if d6.Sign() < 0 {
		d6.Add(d6, q)
	}

	r.ModInverse(qb, p)
	qaqb := new(big.Int).Mul(qa, r)
	qaqb.Mod(qaqb, p)

	ra := new(big.Int).Exp(qaqb, c.smp.a3, p)
	r.Exp(qaqb, r7, p)
	s.Exp(g, r7, p)
	cr := new(big.Int).SetBytes(hashMPIs(h, 7, s, r))

	r.Mul(c.smp.a3, cr)
	d7 := new(big.Int).Sub(r7, r)
	d7.Mod(d7, q)
	if d7.Sign() < 0 {
		d7.Add(d7, q)
	}

	c.smp.g3b = g3b
	c.smp.qaqb = qaqb

	r.ModInverse(pb, p)
	c.smp.papb = new(big.Int).Mul(pa, r)
	c.smp.papb.Mod(c.smp.papb, p)
	c.smp.ra = ra

	out.typ = tlvTypeSMP3
	out.data = appendU32(out.data, 8)
	out.data = appendMPIs(out.data, pa, qa, cp, d5, d6, ra, cr, d7)
	return
}

func (c *Conversation) processSMP3(mpis []*big.Int) (out tlv, err error) {
	if len(mpis) != 8 {
		err = errors.New("otr: incorrect number of arguments in SMP3 message")
		return
	}
	pa := mpis[0]
	qa := mpis[1]
	cp := mpis[2]
	d5 := mpis[3]
	d6 := mpis[4]
	ra := mpis[5]
	cr := mpis[6]
	d7 := mpis[7]
	h := sha256.New()

	r := new(big.Int).Exp(g, d5, p)
	s := new(big.Int).Exp(c.smp.g2, d6, p)
	r.Mul(r, s)
	s.Exp(qa, cp, p)
	r.Mul(r, s)
	r.Mod(r, p)

	s.Exp(c.smp.g3, d5, p)
	t := new(big.Int).Exp(pa, cp, p)
	s.Mul(s, t)
	s.Mod(s, p)
	t.SetBytes(hashMPIs(h, 6, s, r))
	if t.Cmp(cp) != 0 {
		err = errors.New("otr: ZKP cP failed in SMP3 message")
		return
	}

	r.ModInverse(c.smp.qb, p)
	qaqb := new(big.Int).Mul(qa, r)
	qaqb.Mod(qaqb, p)

	r.Exp(qaqb, d7, p)
	s.Exp(ra, cr, p)
	r.Mul(r, s)
	r.Mod(r, p)

	s.Exp(g, d7, p)
	t.Exp(c.smp.g3a, cr, p)
	s.Mul(s, t)
	s.Mod(s, p)
	t.SetBytes(hashMPIs(h, 7, s, r))
	if t.Cmp(cr) != 0 {
		err = errors.New("otr: ZKP cR failed in SMP3 message")
		return
	}

	var randBuf [16]byte
	r7 := c.randMPI(randBuf[:])
	rb := new(big.Int).Exp(qaqb, c.smp.b3, p)

	r.Exp(qaqb, r7, p)
	s.Exp(g, r7, p)
	cr = new(big.Int).SetBytes(hashMPIs(h, 8, s, r))

	r.Mul(c.smp.b3, cr)
	d7 = new(big.Int).Sub(r7, r)
	d7.Mod(d7, q)
	if d7.Sign() < 0 {
		d7.Add(d7, q)
	}

	out.typ = tlvTypeSMP4
	out.data = appendU32(out.data, 3)
	out.data = appendMPIs(out.data, rb, cr, d7)

	r.ModInverse(c.smp.pb, p)
	r.Mul(pa, r)
	r.Mod(r, p)
	s.Exp(ra, c.smp.b3, p)
	if r.Cmp(s) != 0 {
		err = smpFailureError
	}

	return
}

func (c *Conversation) processSMP4(mpis []*big.Int) error {
	if len(mpis) != 3 {
		return errors.New("otr: incorrect number of arguments in SMP4 message")
	}
	rb := mpis[0]
	cr := mpis[1]
	d7 := mpis[2]
	h := sha256.New()

	r := new(big.Int).Exp(c.smp.qaqb, d7, p)
	s := new(big.Int).Exp(rb, cr, p)
	r.Mul(r, s)
	r.Mod(r, p)

	s.Exp(g, d7, p)
	t := new(big.Int).Exp(c.smp.g3b, cr, p)
	s.Mul(s, t)
	s.Mod(s, p)
	t.SetBytes(hashMPIs(h, 8, s, r))
	if t.Cmp(cr) != 0 {
		return errors.New("otr: ZKP cR failed in SMP4 message")
	}

	r.Exp(rb, c.smp.a3, p)
	if r.Cmp(c.smp.papb) != 0 {
		return smpFailureError
	}

	return nil
}

func (c *Conversation) generateSMPAbort() tlv {
	return tlv{typ: tlvTypeSMPAbort}
}

func hashMPIs(h hash.Hash, magic byte, mpis ...*big.Int) []byte {
	if h != nil {
		h.Reset()
	} else {
		h = sha256.New()
	}

	h.Write([]byte{magic})
	for _, mpi := range mpis {
		h.Write(appendMPI(nil, mpi))
	}
	return h.Sum(nil)
}