path: root/libotr/libotr-4.1.1/src/sm.c

/*
 *  Off-the-Record Messaging library
 *  Copyright (C) 2004-2014  Ian Goldberg, David Goulet, Rob Smits,
 *                           Chris Alexander, Willy Lew, Lisa Du,
 *                           Nikita Borisov
 *                           <otr@cypherpunks.ca>
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of version 2.1 of the GNU Lesser General
 *  Public License as published by the Free Software Foundation.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

/* system headers */
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>

/* libgcrypt headers */
#include <gcrypt.h>

/* libotr headers */
#include "sm.h"
#include "serial.h"

#if OTRL_DEBUGGING

/* Dump the contents of an SMState to the FILE *f. */
void otrl_sm_dump(FILE *f, const OtrlSMState *sm)
{
    fprintf(f, "  SM state:\n");
    fprintf(f, "    Next expected: %d (%s)\n", sm->nextExpected,
	sm->nextExpected == OTRL_SMP_EXPECT1 ? "EXPECT1" :
	sm->nextExpected == OTRL_SMP_EXPECT2 ? "EXPECT2" :
	sm->nextExpected == OTRL_SMP_EXPECT3 ? "EXPECT3" :
	sm->nextExpected == OTRL_SMP_EXPECT4 ? "EXPECT4" :
	sm->nextExpected == OTRL_SMP_EXPECT5 ? "EXPECT5" :
	"INVALID");
    fprintf(f, "    Received_Q: %d\n", sm->received_question);
    fprintf(f, "    Progress state: %d (%s)\n", sm->sm_prog_state,
	sm->sm_prog_state == OTRL_SMP_PROG_OK ? "OK" :
	sm->sm_prog_state == OTRL_SMP_PROG_CHEATED ? "CHEATED" :
	sm->sm_prog_state == OTRL_SMP_PROG_FAILED ? "FAILED" :
	sm->sm_prog_state == OTRL_SMP_PROG_SUCCEEDED ? "SUCCEEDED" :
	"INVALID");
}

#endif

static const int SM_MSG1_LEN = 6;
static const int SM_MSG2_LEN = 11;
static const int SM_MSG3_LEN = 8;
static const int SM_MSG4_LEN = 3;

/* The modulus p */
static const char* SM_MODULUS_S = "0x"
    "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
    "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
    "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
    "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
    "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D"
    "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
    "83655D23DCA3AD961C62F356208552BB9ED529077096966D"
    "670C354E4ABC9804F1746C08CA237327FFFFFFFFFFFFFFFF";
/* The order of the group q = (p-1)/2 */
static const char* SM_ORDER_S = "0x"
    "7FFFFFFFFFFFFFFFE487ED5110B4611A62633145C06E0E68"
    "948127044533E63A0105DF531D89CD9128A5043CC71A026E"
    "F7CA8CD9E69D218D98158536F92F8A1BA7F09AB6B6A8E122"
    "F242DABB312F3F637A262174D31BF6B585FFAE5B7A035BF6"
    "F71C35FDAD44CFD2D74F9208BE258FF324943328F6722D9E"
    "E1003E5C50B1DF82CC6D241B0E2AE9CD348B1FD47E9267AF"
    "C1B2AE91EE51D6CB0E3179AB1042A95DCF6A9483B84B4B36"
    "B3861AA7255E4C0278BA36046511B993FFFFFFFFFFFFFFFF";
static const char *SM_GENERATOR_S = "0x02";
static const int SM_MOD_LEN_BITS = 1536;
static const int SM_MOD_LEN_BYTES = 192;

static gcry_mpi_t SM_MODULUS = NULL;
static gcry_mpi_t SM_GENERATOR = NULL;
static gcry_mpi_t SM_ORDER = NULL;
static gcry_mpi_t SM_MODULUS_MINUS_2 = NULL;

/*
 * Call this once, at plugin load time.  It sets up the modulus and
 * generator MPIs.
 */
void otrl_sm_init(void)
{
    gcry_check_version(NULL);
    gcry_mpi_scan(&SM_MODULUS, GCRYMPI_FMT_HEX,
	(const unsigned char *)SM_MODULUS_S, 0, NULL);
    gcry_mpi_scan(&SM_ORDER, GCRYMPI_FMT_HEX,
	(const unsigned char *)SM_ORDER_S, 0, NULL);
    gcry_mpi_scan(&SM_GENERATOR, GCRYMPI_FMT_HEX,
	(const unsigned char *)SM_GENERATOR_S, 0, NULL);
    SM_MODULUS_MINUS_2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_sub_ui(SM_MODULUS_MINUS_2, SM_MODULUS, 2);
}

/*
 * Initialize the fields of a SM state.
 */
void otrl_sm_state_new(OtrlSMState *smst)
{
    smst->secret = NULL;
    smst->x2 = NULL;
    smst->x3 = NULL;
    smst->g1 = NULL;
    smst->g2 = NULL;
    smst->g3 = NULL;
    smst->g3o = NULL;
    smst->p = NULL;
    smst->q = NULL;
    smst->pab = NULL;
    smst->qab = NULL;
    smst->nextExpected = OTRL_SMP_EXPECT1;
    smst->received_question = 0;
    smst->sm_prog_state = OTRL_SMP_PROG_OK;
}

/*
 * Initialize the fields of a SM state.  Called the first time that
 * a user begins an SMP session.
 */
void otrl_sm_state_init(OtrlSMState *smst)
{
    otrl_sm_state_free(smst);
    smst->secret = gcry_mpi_snew(SM_MOD_LEN_BITS);
    smst->x2 = NULL;
    smst->x3 = NULL;
    smst->g1 = gcry_mpi_copy(SM_GENERATOR);
    smst->g2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->g3 = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->g3o = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->p = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->q = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->pab = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->qab = gcry_mpi_new(SM_MOD_LEN_BITS);
    smst->received_question = 0;
    smst->sm_prog_state = OTRL_SMP_PROG_OK;
}

/*
 * Initialize the fields of a SM message1.
 * [0] = g2a, [1] = c2, [2] = d2, [3] = g3a, [4] = c3, [5] = d3
 */
void otrl_sm_msg1_init(gcry_mpi_t **msg1)
{
    gcry_mpi_t *msg = malloc(SM_MSG1_LEN * sizeof(gcry_mpi_t));
    msg[0] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[1] = NULL;
    msg[2] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[3] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[4] = NULL;
    msg[5] = gcry_mpi_new(SM_MOD_LEN_BITS);

    *msg1 = msg;
}

/*
 * Initialize the fields of a SM message2.
 * [0] = g2b, [1] = c2, [2] = d2, [3] = g3b, [4] = c3, [5] = d3
 * [6] = pb, [7] = qb, [8] = cp, [9] = d5, [10] = d6
 */
void otrl_sm_msg2_init(gcry_mpi_t **msg2)
{
    gcry_mpi_t *msg = malloc(SM_MSG2_LEN * sizeof(gcry_mpi_t));
    msg[0] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[1] = NULL;
    msg[2] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[3] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[4] = NULL;
    msg[5] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[6] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[7] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[8] = NULL;
    msg[9] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[10] = gcry_mpi_new(SM_MOD_LEN_BITS);

    *msg2 = msg;
}

/*
 * Initialize the fields of a SM message3.
 * [0] = pa, [1] = qa, [2] = cp, [3] = d5, [4] = d6, [5] = ra,
 * [6] = cr, [7] = d7
 */
void otrl_sm_msg3_init(gcry_mpi_t **msg3)
{
    gcry_mpi_t *msg = malloc(SM_MSG3_LEN * sizeof(gcry_mpi_t));
    msg[0] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[1] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[2] = NULL;
    msg[3] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[4] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[5] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[6] = NULL;
    msg[7] = gcry_mpi_new(SM_MOD_LEN_BITS);

    *msg3 = msg;
}

/*
 * Initialize the fields of a SM message4.
 * [0] = rb, [1] = cr, [2] = d7
 */
void otrl_sm_msg4_init(gcry_mpi_t **msg4)
{
    gcry_mpi_t *msg = malloc(SM_MSG4_LEN * sizeof(gcry_mpi_t));
    msg[0] = gcry_mpi_new(SM_MOD_LEN_BITS);
    msg[1] = NULL;
    msg[2] = gcry_mpi_new(SM_MOD_LEN_BITS);

    *msg4 = msg;
}

/*
 * Deallocate the contents of a OtrlSMState (but not the OtrlSMState
 * itself)
 */
void otrl_sm_state_free(OtrlSMState *smst)
{
    gcry_mpi_release(smst->secret);
    gcry_mpi_release(smst->x2);
    gcry_mpi_release(smst->x3);
    gcry_mpi_release(smst->g1);
    gcry_mpi_release(smst->g2);
    gcry_mpi_release(smst->g3);
    gcry_mpi_release(smst->g3o);
    gcry_mpi_release(smst->p);
    gcry_mpi_release(smst->q);
    gcry_mpi_release(smst->pab);
    gcry_mpi_release(smst->qab);
    otrl_sm_state_new(smst);
}

/*
 * Deallocate the contents of a message
 */
void otrl_sm_msg_free(gcry_mpi_t **message, int msglen)
{
    gcry_mpi_t *msg = *message;
    int i;
    for (i=0; i<msglen; i++) {
	gcry_mpi_release(msg[i]);
    }
    free(msg);
    *message = NULL;
}

static gcry_mpi_t randomExponent(void)
{
    unsigned char *secbuf = NULL;
    gcry_mpi_t randexpon = NULL;

    /* Generate a random exponent */
    secbuf = gcry_random_bytes_secure(SM_MOD_LEN_BYTES, GCRY_STRONG_RANDOM);
    gcry_mpi_scan(&randexpon, GCRYMPI_FMT_USG, secbuf, SM_MOD_LEN_BYTES, NULL);
    gcry_free(secbuf);

    return randexpon;
}

/*
 * Hash one or two mpis.  To hash only one mpi, b may be set to NULL.
 */
static gcry_error_t otrl_sm_hash(gcry_mpi_t* hash, int version,
	const gcry_mpi_t a, const gcry_mpi_t b)
{
    unsigned char* input;
    unsigned char output[SM_DIGEST_SIZE];
    size_t sizea;
    size_t sizeb;
    size_t totalsize;
    unsigned char* dataa;
    unsigned char* datab;

    gcry_mpi_aprint(GCRYMPI_FMT_USG, &dataa, &sizea, a);
    totalsize = 1 + 4 + sizea;
    if (b) {
	gcry_mpi_aprint(GCRYMPI_FMT_USG, &datab, &sizeb, b);
	totalsize += 4 + sizeb;
    } else {
	sizeb = 0;
    }

    input = malloc(totalsize);
    input[0] = (unsigned char)version;
    input[1] = (unsigned char)((sizea >> 24) & 0xFF);
    input[2] = (unsigned char)((sizea >> 16) & 0xFF);
    input[3] = (unsigned char)((sizea >> 8) & 0xFF);
    input[4] = (unsigned char)(sizea & 0xFF);
    memmove(input + 5, dataa, sizea);
    if (b) {
	input[5 + sizea] = (unsigned char)((sizeb >> 24) & 0xFF);
	input[6 + sizea] = (unsigned char)((sizeb >> 16) & 0xFF);
	input[7 + sizea] = (unsigned char)((sizeb >> 8) & 0xFF);
	input[8 + sizea] = (unsigned char)(sizeb & 0xFF);
	memmove(input + 9 + sizea, datab, sizeb);
    }

    gcry_md_hash_buffer(SM_HASH_ALGORITHM, output, input, totalsize);
    gcry_mpi_scan(hash, GCRYMPI_FMT_USG, output, SM_DIGEST_SIZE, NULL);
    free(input);
    input = NULL;

    /* free memory */
    gcry_free(dataa);
    if (b) gcry_free(datab);

    return gcry_error(GPG_ERR_NO_ERROR);
}

/* This method should be passed a pointer to an uninitialized buffer,
 * and a list of mpis with a list length.  When returns, the buffer will
 * point to newly-allocated memory (using malloc) containing a
 * reversible serialization. */
static gcry_error_t serialize_mpi_array(unsigned char **buffer, int *buflen,
	unsigned int count, gcry_mpi_t *mpis)
{
    size_t totalsize = 0, lenp, nextsize;
    unsigned int i, j;
    size_t *list_sizes = malloc(count * sizeof(size_t));
    unsigned char **tempbuffer = malloc(count * sizeof(unsigned char *));
    unsigned char *bufp;

    for (i=0; i<count; i++) {
	gcry_mpi_aprint(GCRYMPI_FMT_USG, &(tempbuffer[i]), &(list_sizes[i]),
		mpis[i]);
	totalsize += list_sizes[i];
    }

    *buflen = (count+1)*4 + totalsize;
    *buffer = malloc(*buflen * sizeof(char));

    bufp = *buffer;
    lenp = totalsize;

    write_int(count);
    for(i=0; i<count; i++)
    {
	nextsize = list_sizes[i];
	write_int(nextsize);

	for(j=0; j<nextsize; j++)
	    bufp[j] = tempbuffer[i][j];

	bufp += nextsize;
	lenp -= nextsize;
	gcry_free(tempbuffer[i]);
    }
    free(tempbuffer);
    free(list_sizes);

    return gcry_error(GPG_ERR_NO_ERROR);
}

/* Takes a buffer containing serialized and concatenated mpis
 * and converts it to an array of gcry_mpi_t structs.
 * The buffer is assumed to consist of a 4-byte int containing the
 * number of mpis in the array, followed by {size, data} pairs for
 * each mpi.  If malformed, method returns GCRY_ERROR_INV_VALUE */
static gcry_error_t unserialize_mpi_array(gcry_mpi_t **mpis,
	unsigned int expcount, const unsigned char *buffer, const int buflen)
{
    unsigned int i;
    size_t lenp = buflen;
    unsigned int thecount = 0;
    const unsigned char* bufp = buffer;
    *mpis = NULL;

    read_int(thecount);
    if (thecount != expcount) goto invval;

    *mpis = malloc(thecount * sizeof(gcry_mpi_t));

    for (i=0; i<thecount; i++) {
	(*mpis)[i] = NULL;
    }

    for (i=0; i<thecount; i++) {
	read_mpi((*mpis)[i]);
    }

    return gcry_error(GPG_ERR_NO_ERROR);

invval:
    if (*mpis) {
	for (i=0; i<thecount; i++) {
	    gcry_mpi_release((*mpis)[i]);
	}
	free(*mpis);
	*mpis = NULL;
    }
    return gcry_error(GPG_ERR_INV_VALUE);
}

/* Check that an MPI is in the right range to be a (non-unit) group
 * element */
static int check_group_elem(gcry_mpi_t g)
{
    if (gcry_mpi_cmp_ui(g, 2) < 0 ||
	    gcry_mpi_cmp(g, SM_MODULUS_MINUS_2) > 0) {
	return 1;
    }
    return 0;
}

/* Check that an MPI is in the right range to be a (non-zero) exponent */
static int check_expon(gcry_mpi_t x)
{
    if (gcry_mpi_cmp_ui(x, 1) < 0 ||
	    gcry_mpi_cmp(x, SM_ORDER) >= 0) {
	return 1;
    }
    return 0;
}

/*
 * Proof of knowledge of a discrete logarithm
 */
static gcry_error_t otrl_sm_proof_know_log(gcry_mpi_t *c, gcry_mpi_t *d,
	const gcry_mpi_t g, const gcry_mpi_t x, int version)
{
    gcry_mpi_t r = randomExponent();
    gcry_mpi_t temp = gcry_mpi_snew(SM_MOD_LEN_BITS);
    gcry_mpi_powm(temp, g, r, SM_MODULUS);
    otrl_sm_hash(c, version, temp, NULL);
    gcry_mpi_mulm(temp, x, *c, SM_ORDER);
    gcry_mpi_subm(*d, r, temp, SM_ORDER);
    gcry_mpi_release(temp);
    gcry_mpi_release(r);

    return gcry_error(GPG_ERR_NO_ERROR);
}

/*
 * Verify a proof of knowledge of a discrete logarithm.
 * Checks that c = h(g^d x^c)
 */
static int otrl_sm_check_know_log(const gcry_mpi_t c, const gcry_mpi_t d,
	const gcry_mpi_t g, const gcry_mpi_t x, int version)
{
    int comp;

    gcry_mpi_t gd = gcry_mpi_new(SM_MOD_LEN_BITS);  /* g^d */
    gcry_mpi_t xc = gcry_mpi_new(SM_MOD_LEN_BITS);  /* x^c */
    gcry_mpi_t gdxc = gcry_mpi_new(SM_MOD_LEN_BITS);   /* (g^d x^c) */
    gcry_mpi_t hgdxc = NULL;   /* h(g^d x^c) */

    gcry_mpi_powm(gd, g, d, SM_MODULUS);
    gcry_mpi_powm(xc, x, c, SM_MODULUS);
    gcry_mpi_mulm(gdxc, gd, xc, SM_MODULUS);
    otrl_sm_hash(&hgdxc, version, gdxc, NULL);

    comp = gcry_mpi_cmp(hgdxc, c);
    gcry_mpi_release(gd);
    gcry_mpi_release(xc);
    gcry_mpi_release(gdxc);
    gcry_mpi_release(hgdxc);

    return comp;
}

/*
 * Proof of knowledge of coordinates with first components being equal
 */
static gcry_error_t otrl_sm_proof_equal_coords(gcry_mpi_t *c, gcry_mpi_t *d1,
	gcry_mpi_t *d2, const OtrlSMState *state, const gcry_mpi_t r,
	int version)
{
    gcry_mpi_t r1 = randomExponent();
    gcry_mpi_t r2 = randomExponent();
    gcry_mpi_t temp1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp2 = gcry_mpi_new(SM_MOD_LEN_BITS);

    /* Compute the value of c, as c = h(g3^r1, g1^r1 g2^r2) */
    gcry_mpi_powm(temp1, state->g1, r1, SM_MODULUS);
    gcry_mpi_powm(temp2, state->g2, r2, SM_MODULUS);
    gcry_mpi_mulm(temp2, temp1, temp2, SM_MODULUS);
    gcry_mpi_powm(temp1, state->g3, r1, SM_MODULUS);
    otrl_sm_hash(c, version, temp1, temp2);

    /* Compute the d values, as d1 = r1 - r c, d2 = r2 - secret c */
    gcry_mpi_mulm(temp1, r, *c, SM_ORDER);
    gcry_mpi_subm(*d1, r1, temp1, SM_ORDER);

    gcry_mpi_mulm(temp1, state->secret, *c, SM_ORDER);
    gcry_mpi_subm(*d2, r2, temp1, SM_ORDER);

    /* All clear */
    gcry_mpi_release(r1);
    gcry_mpi_release(r2);
    gcry_mpi_release(temp1);
    gcry_mpi_release(temp2);
    return gcry_error(GPG_ERR_NO_ERROR);
}

/*
 * Verify a proof of knowledge of coordinates with first components being equal
 */
static gcry_error_t otrl_sm_check_equal_coords(const gcry_mpi_t c,
	const gcry_mpi_t d1, const gcry_mpi_t d2, const gcry_mpi_t p,
	const gcry_mpi_t q, const OtrlSMState *state, int version)
{
    int comp;

    gcry_mpi_t temp1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp3 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t cprime = NULL;

    /* To verify, we test that hash(g3^d1 * p^c, g1^d1 * g2^d2 * q^c) = c
     * If indeed c = hash(g3^r1, g1^r1 g2^r2), d1 = r1 - r*c,
     * d2 = r2 - secret*c.  And if indeed p = g3^r, q = g1^r * g2^secret
     * Then we should have that:
     *   hash(g3^d1 * p^c, g1^d1 * g2^d2 * q^c)
     * = hash(g3^(r1 - r*c + r*c), g1^(r1 - r*c + q*c) *
     *      g2^(r2 - secret*c + secret*c))
     * = hash(g3^r1, g1^r1 g2^r2)
     * = c
     */
    gcry_mpi_powm(temp2, state->g3, d1, SM_MODULUS);
    gcry_mpi_powm(temp3, p, c, SM_MODULUS);
    gcry_mpi_mulm(temp1, temp2, temp3, SM_MODULUS);

    gcry_mpi_powm(temp2, state->g1, d1, SM_MODULUS);
    gcry_mpi_powm(temp3, state->g2, d2, SM_MODULUS);
    gcry_mpi_mulm(temp2, temp2, temp3, SM_MODULUS);
    gcry_mpi_powm(temp3, q, c, SM_MODULUS);
    gcry_mpi_mulm(temp2, temp3, temp2, SM_MODULUS);

    otrl_sm_hash(&cprime, version, temp1, temp2);

    comp = gcry_mpi_cmp(c, cprime);
    gcry_mpi_release(temp1);
    gcry_mpi_release(temp2);
    gcry_mpi_release(temp3);
    gcry_mpi_release(cprime);

    return comp;
}

/*
 * Proof of knowledge of logs with exponents being equal
 */
static gcry_error_t otrl_sm_proof_equal_logs(gcry_mpi_t *c, gcry_mpi_t *d,
	OtrlSMState *state, int version)
{
    gcry_mpi_t r = randomExponent();
    gcry_mpi_t temp1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp2 = gcry_mpi_new(SM_MOD_LEN_BITS);

    /* Compute the value of c, as c = h(g1^r, (Qa/Qb)^r) */
    gcry_mpi_powm(temp1, state->g1, r, SM_MODULUS);
    gcry_mpi_powm(temp2, state->qab, r, SM_MODULUS);
    otrl_sm_hash(c, version, temp1, temp2);

    /* Compute the d values, as d = r - x3 c */
    gcry_mpi_mulm(temp1, state->x3, *c, SM_ORDER);
    gcry_mpi_subm(*d, r, temp1, SM_ORDER);

    /* All clear */
    gcry_mpi_release(r);
    gcry_mpi_release(temp1);
    gcry_mpi_release(temp2);
    return gcry_error(GPG_ERR_NO_ERROR);
}

/*
 * Verify a proof of knowledge of logs with exponents being equal
 */
static gcry_error_t otrl_sm_check_equal_logs(const gcry_mpi_t c,
	const gcry_mpi_t d, const gcry_mpi_t r, const OtrlSMState *state,
	int version)
{
    int comp;

    gcry_mpi_t temp1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t temp3 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_t cprime = NULL;

    /* Here, we recall the exponents used to create g3.
     * If we have previously seen g3o = g1^x where x is unknown
     * during the DH exchange to produce g3, then we may proceed with:
     *
     * To verify, we test that hash(g1^d * g3o^c, qab^d * r^c) = c
     * If indeed c = hash(g1^r1, qab^r1), d = r1- x * c
     * And if indeed r = qab^x
     * Then we should have that:
     *   hash(g1^d * g3o^c, qab^d r^c)
     * = hash(g1^(r1 - x*c + x*c), qab^(r1 - x*c + x*c))
     * = hash(g1^r1, qab^r1)
     * = c
     */
    gcry_mpi_powm(temp2, state->g1, d, SM_MODULUS);
    gcry_mpi_powm(temp3, state->g3o, c, SM_MODULUS);
    gcry_mpi_mulm(temp1, temp2, temp3, SM_MODULUS);

    gcry_mpi_powm(temp3, state->qab, d, SM_MODULUS);
    gcry_mpi_powm(temp2, r, c, SM_MODULUS);
    gcry_mpi_mulm(temp2, temp3, temp2, SM_MODULUS);

    otrl_sm_hash(&cprime, version, temp1, temp2);

    comp = gcry_mpi_cmp(c, cprime);
    gcry_mpi_release(temp1);
    gcry_mpi_release(temp2);
    gcry_mpi_release(temp3);
    gcry_mpi_release(cprime);

    return comp;
}

/* Create first message in SMP exchange.  Input is Alice's secret value
 * which this protocol aims to compare to Bob's.  Output is a serialized
 * mpi array whose elements correspond to the following:
 * [0] = g2a, Alice's half of DH exchange to determine g2
 * [1] = c2, [2] = d2, Alice's ZK proof of knowledge of g2a exponent
 * [3] = g3a, Alice's half of DH exchange to determine g3
 * [4] = c3, [5] = d3, Alice's ZK proof of knowledge of g3a exponent */
gcry_error_t otrl_sm_step1(OtrlSMAliceState *astate,
	const unsigned char* secret, int secretlen,
	unsigned char** output, int* outputlen)
{
    /* Initialize the sm state or update the secret */
    gcry_mpi_t secret_mpi = NULL;
    gcry_mpi_t *msg1;

    *output = NULL;
    *outputlen = 0;

    gcry_mpi_scan(&secret_mpi, GCRYMPI_FMT_USG, secret, secretlen, NULL);

    if (! astate->g1) {
	otrl_sm_state_init(astate);
    }
    gcry_mpi_set(astate->secret, secret_mpi);
    gcry_mpi_release(secret_mpi);
    astate->received_question = 0;

    otrl_sm_msg1_init(&msg1);

    astate->x2 = randomExponent();
    astate->x3 = randomExponent();

    gcry_mpi_powm(msg1[0], astate->g1, astate->x2, SM_MODULUS);
    otrl_sm_proof_know_log(&(msg1[1]), &(msg1[2]), astate->g1, astate->x2, 1);

    gcry_mpi_powm(msg1[3], astate->g1, astate->x3, SM_MODULUS);
    otrl_sm_proof_know_log(&(msg1[4]), &(msg1[5]), astate->g1, astate->x3, 2);

    serialize_mpi_array(output, outputlen, SM_MSG1_LEN, msg1);
    otrl_sm_msg_free(&msg1, SM_MSG1_LEN);
    astate->sm_prog_state = OTRL_SMP_PROG_OK;
    return gcry_error(GPG_ERR_NO_ERROR);
}

/* Receive the first message in SMP exchange, which was generated by
 * otrl_sm_step1.  Input is saved until the user inputs their secret
 * information.  No output. */
gcry_error_t otrl_sm_step2a(OtrlSMBobState *bstate, const unsigned char* input,
	const int inputlen, int received_question)
{
    gcry_mpi_t *msg1;
    gcry_error_t err;

    /* Initialize the sm state if needed */
    if (! bstate->g1) {
	otrl_sm_state_init(bstate);
    }
    bstate->received_question = received_question;
    bstate->sm_prog_state = OTRL_SMP_PROG_CHEATED;

    /* Read from input to find the mpis */
    err = unserialize_mpi_array(&msg1, SM_MSG1_LEN, input, inputlen);

    if (err != gcry_error(GPG_ERR_NO_ERROR)) return err;

    if (check_group_elem(msg1[0]) || check_expon(msg1[2]) ||
	    check_group_elem(msg1[3]) || check_expon(msg1[5])) {
	otrl_sm_msg_free(&msg1, SM_MSG1_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Store Alice's g3a value for later in the protocol */
    gcry_mpi_set(bstate->g3o, msg1[3]);

    /* Verify Alice's proofs */
    if (otrl_sm_check_know_log(msg1[1], msg1[2], bstate->g1, msg1[0], 1) ||
	otrl_sm_check_know_log(msg1[4], msg1[5], bstate->g1, msg1[3], 2)) {
	otrl_sm_msg_free(&msg1, SM_MSG1_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Create Bob's half of the generators g2 and g3 */
    bstate->x2 = randomExponent();
    bstate->x3 = randomExponent();

    /* Combine the two halves from Bob and Alice and determine g2 and g3 */
    gcry_mpi_powm(bstate->g2, msg1[0], bstate->x2, SM_MODULUS);
    gcry_mpi_powm(bstate->g3, msg1[3], bstate->x3, SM_MODULUS);

    bstate->sm_prog_state = OTRL_SMP_PROG_OK;

    otrl_sm_msg_free(&msg1, SM_MSG1_LEN);
    return gcry_error(GPG_ERR_NO_ERROR);
}

/* Create second message in SMP exchange.  Input is Bob's secret value.
 * Information from earlier steps in the exchange is taken from Bob's
 * state.  Output is a serialized mpi array whose elements correspond
 * to the following:
 * [0] = g2b, Bob's half of DH exchange to determine g2
 * [1] = c2, [2] = d2, Bob's ZK proof of knowledge of g2b exponent
 * [3] = g3b, Bob's half of DH exchange to determine g3
 * [4] = c3, [5] = d3, Bob's ZK proof of knowledge of g3b exponent
 * [6] = pb, [7] = qb, Bob's halves of the (Pa/Pb) and (Qa/Qb) values
 * [8] = cp, [9] = d5, [10] = d6, Bob's ZK proof that pb, qb formed correctly */
gcry_error_t otrl_sm_step2b(OtrlSMBobState *bstate, const unsigned char* secret,
	int secretlen, unsigned char **output, int* outputlen)
{
    /* Convert the given secret to the proper form and store it */
    gcry_mpi_t r, qb1, qb2;
    gcry_mpi_t *msg2;
    gcry_mpi_t secret_mpi = NULL;

    *output = NULL;
    *outputlen = 0;

    gcry_mpi_scan(&secret_mpi, GCRYMPI_FMT_USG, secret, secretlen, NULL);
    gcry_mpi_set(bstate->secret, secret_mpi);
    gcry_mpi_release(secret_mpi);

    otrl_sm_msg2_init(&msg2);

    gcry_mpi_powm(msg2[0], bstate->g1, bstate->x2, SM_MODULUS);
    otrl_sm_proof_know_log(&(msg2[1]), &(msg2[2]), bstate->g1, bstate->x2, 3);

    gcry_mpi_powm(msg2[3], bstate->g1, bstate->x3, SM_MODULUS);
    otrl_sm_proof_know_log(&(msg2[4]), &(msg2[5]), bstate->g1, bstate->x3, 4);

    /* Calculate P and Q values for Bob */
    r = randomExponent();
    qb1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    qb2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_powm(bstate->p, bstate->g3, r, SM_MODULUS);
    gcry_mpi_set(msg2[6], bstate->p);
    gcry_mpi_powm(qb1, bstate->g1, r, SM_MODULUS);
    gcry_mpi_powm(qb2, bstate->g2, bstate->secret, SM_MODULUS);
    gcry_mpi_mulm(bstate->q, qb1, qb2, SM_MODULUS);
    gcry_mpi_set(msg2[7], bstate->q);

    otrl_sm_proof_equal_coords(&(msg2[8]), &(msg2[9]),
	    &(msg2[10]), bstate, r, 5);

    /* Convert to serialized form */
    serialize_mpi_array(output, outputlen, SM_MSG2_LEN, msg2);

    /* Free up memory for unserialized and intermediate values */
    gcry_mpi_release(r);
    gcry_mpi_release(qb1);
    gcry_mpi_release(qb2);
    otrl_sm_msg_free(&msg2, SM_MSG2_LEN);

    return gcry_error(GPG_ERR_NO_ERROR);
}

/* Create third message in SMP exchange.  Input is a message generated
 * by otrl_sm_step2b. Output is a serialized mpi array whose elements
 * correspond to the following:
 * [0] = pa, [1] = qa, Alice's halves of the (Pa/Pb) and (Qa/Qb) values
 * [2] = cp, [3] = d5, [4] = d6, Alice's ZK proof that pa, qa formed correctly
 * [5] = ra, calculated as (Qa/Qb)^x3 where x3 is the exponent used in g3a
 * [6] = cr, [7] = d7, Alice's ZK proof that ra is formed correctly */
gcry_error_t otrl_sm_step3(OtrlSMAliceState *astate, const unsigned char* input,
	const int inputlen, unsigned char **output, int* outputlen)
{
    /* Read from input to find the mpis */
    gcry_mpi_t r, qa1, qa2, inv;
    gcry_mpi_t *msg2;
    gcry_mpi_t *msg3;
    gcry_error_t err;

    *output = NULL;
    *outputlen = 0;
    astate->sm_prog_state = OTRL_SMP_PROG_CHEATED;

    err = unserialize_mpi_array(&msg2, SM_MSG2_LEN, input, inputlen);
    if (err != gcry_error(GPG_ERR_NO_ERROR)) return err;

    if (check_group_elem(msg2[0]) || check_group_elem(msg2[3]) ||
	    check_group_elem(msg2[6]) || check_group_elem(msg2[7]) ||
	    check_expon(msg2[2]) || check_expon(msg2[5]) ||
	    check_expon(msg2[9]) || check_expon(msg2[10])) {
	otrl_sm_msg_free(&msg2, SM_MSG2_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    otrl_sm_msg3_init(&msg3);

    /* Store Bob's g3a value for later in the protocol */
    gcry_mpi_set(astate->g3o, msg2[3]);

    /* Verify Bob's knowledge of discrete log proofs */
    if (otrl_sm_check_know_log(msg2[1], msg2[2], astate->g1, msg2[0], 3) ||
	    otrl_sm_check_know_log(msg2[4], msg2[5], astate->g1, msg2[3], 4)) {
	otrl_sm_msg_free(&msg2, SM_MSG2_LEN);
	otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Combine the two halves from Bob and Alice and determine g2 and g3 */
    gcry_mpi_powm(astate->g2, msg2[0], astate->x2, SM_MODULUS);
    gcry_mpi_powm(astate->g3, msg2[3], astate->x3, SM_MODULUS);

    /* Verify Bob's coordinate equality proof */
    if (otrl_sm_check_equal_coords(msg2[8], msg2[9], msg2[10], msg2[6], msg2[7],
	    astate, 5)) {
	otrl_sm_msg_free(&msg2, SM_MSG2_LEN);
	otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Calculate P and Q values for Alice */
    r = randomExponent();
    qa1 = gcry_mpi_new(SM_MOD_LEN_BITS);
    qa2 = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_powm(astate->p, astate->g3, r, SM_MODULUS);
    gcry_mpi_set(msg3[0], astate->p);
    gcry_mpi_powm(qa1, astate->g1, r, SM_MODULUS);
    gcry_mpi_powm(qa2, astate->g2, astate->secret, SM_MODULUS);
    gcry_mpi_mulm(astate->q, qa1, qa2, SM_MODULUS);
    gcry_mpi_set(msg3[1], astate->q);

    otrl_sm_proof_equal_coords(&(msg3[2]), &(msg3[3]), &(msg3[4]), astate,
	    r, 6);

    /* Calculate Ra and proof */
    inv = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_invm(inv, msg2[6], SM_MODULUS);
    gcry_mpi_mulm(astate->pab, astate->p, inv, SM_MODULUS);
    gcry_mpi_invm(inv, msg2[7], SM_MODULUS);
    gcry_mpi_mulm(astate->qab, astate->q, inv, SM_MODULUS);
    gcry_mpi_powm(msg3[5], astate->qab, astate->x3, SM_MODULUS);
    otrl_sm_proof_equal_logs(&(msg3[6]), &(msg3[7]), astate, 7);

    serialize_mpi_array(output, outputlen, SM_MSG3_LEN, msg3);
    otrl_sm_msg_free(&msg2, SM_MSG2_LEN);
    otrl_sm_msg_free(&msg3, SM_MSG3_LEN);

    gcry_mpi_release(r);
    gcry_mpi_release(qa1);
    gcry_mpi_release(qa2);
    gcry_mpi_release(inv);

    astate->sm_prog_state = OTRL_SMP_PROG_OK;
    return gcry_error(GPG_ERR_NO_ERROR);
}

/* Create final message in SMP exchange.  Input is a message generated
 * by otrl_sm_step3. Output is a serialized mpi array whose elements
 * correspond to the following:
 * [0] = rb, calculated as (Qa/Qb)^x3 where x3 is the exponent used in g3b
 * [1] = cr, [2] = d7, Bob's ZK proof that rb is formed correctly
 * This method also checks if Alice and Bob's secrets were the same.  If
 * so, it returns NO_ERROR.  If the secrets differ, an INV_VALUE error is
 * returned instead. */
gcry_error_t otrl_sm_step4(OtrlSMBobState *bstate, const unsigned char* input,
	const int inputlen, unsigned char **output, int* outputlen)
{
    /* Read from input to find the mpis */
    int comp;
    gcry_mpi_t inv, rab;
    gcry_mpi_t *msg3;
    gcry_mpi_t *msg4;
    gcry_error_t err;
    err = unserialize_mpi_array(&msg3, SM_MSG3_LEN, input, inputlen);

    *output = NULL;
    *outputlen = 0;
    bstate->sm_prog_state = OTRL_SMP_PROG_CHEATED;

    if (err != gcry_error(GPG_ERR_NO_ERROR)) return err;

    otrl_sm_msg4_init(&msg4);

    if (check_group_elem(msg3[0]) || check_group_elem(msg3[1]) ||
	    check_group_elem(msg3[5]) || check_expon(msg3[3]) ||
	    check_expon(msg3[4]) || check_expon(msg3[7]))  {
	otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
	otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Verify Alice's coordinate equality proof */
    if (otrl_sm_check_equal_coords(msg3[2], msg3[3], msg3[4], msg3[0], msg3[1],
	    bstate, 6)) {
	otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
	otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Find Pa/Pb and Qa/Qb */
    inv = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_invm(inv, bstate->p, SM_MODULUS);
    gcry_mpi_mulm(bstate->pab, msg3[0], inv, SM_MODULUS);
    gcry_mpi_invm(inv, bstate->q, SM_MODULUS);
    gcry_mpi_mulm(bstate->qab, msg3[1], inv, SM_MODULUS);

    /* Verify Alice's log equality proof */
    if (otrl_sm_check_equal_logs(msg3[6], msg3[7], msg3[5], bstate, 7)) {
	otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
	otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
	gcry_mpi_release(inv);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Calculate Rb and proof */
    gcry_mpi_powm(msg4[0], bstate->qab, bstate->x3, SM_MODULUS);
    otrl_sm_proof_equal_logs(&(msg4[1]), &(msg4[2]), bstate, 8);

    serialize_mpi_array(output, outputlen, SM_MSG4_LEN, msg4);

    /* Calculate Rab and verify that secrets match */
    rab = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_powm(rab, msg3[5], bstate->x3, SM_MODULUS);
    comp = gcry_mpi_cmp(rab, bstate->pab);

    /* Clean up everything allocated in this step */
    otrl_sm_msg_free(&msg3, SM_MSG3_LEN);
    otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
    gcry_mpi_release(rab);
    gcry_mpi_release(inv);

    bstate->sm_prog_state = comp ? OTRL_SMP_PROG_FAILED :
	OTRL_SMP_PROG_SUCCEEDED;

    if (comp)
	return gcry_error(GPG_ERR_INV_VALUE);
    else
	return gcry_error(GPG_ERR_NO_ERROR);
}

/* Receives the final SMP message, which was generated in otrl_sm_step.
 * This method checks if Alice and Bob's secrets were the same.  If
 * so, it returns NO_ERROR.  If the secrets differ, an INV_VALUE error is
 * returned instead. */
gcry_error_t otrl_sm_step5(OtrlSMAliceState *astate, const unsigned char* input,
	const int inputlen)
{
    /* Read from input to find the mpis */
    int comp;
    gcry_mpi_t rab;
    gcry_mpi_t *msg4;
    gcry_error_t err;
    err = unserialize_mpi_array(&msg4, SM_MSG4_LEN, input, inputlen);
    astate->sm_prog_state = OTRL_SMP_PROG_CHEATED;

    if (err != gcry_error(GPG_ERR_NO_ERROR)) return err;

    if (check_group_elem(msg4[0]) || check_expon(msg4[2])) {
	otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Verify Bob's log equality proof */
    if (otrl_sm_check_equal_logs(msg4[1], msg4[2], msg4[0], astate, 8)) {
	otrl_sm_msg_free(&msg4, SM_MSG4_LEN);
	return gcry_error(GPG_ERR_INV_VALUE);
    }

    /* Calculate Rab and verify that secrets match */
    rab = gcry_mpi_new(SM_MOD_LEN_BITS);
    gcry_mpi_powm(rab, msg4[0], astate->x3, SM_MODULUS);

    comp = gcry_mpi_cmp(rab, astate->pab);
    gcry_mpi_release(rab);
    otrl_sm_msg_free(&msg4, SM_MSG4_LEN);

    astate->sm_prog_state = comp ? OTRL_SMP_PROG_FAILED :
	OTRL_SMP_PROG_SUCCEEDED;

    if (comp)
	return gcry_error(GPG_ERR_INV_VALUE);
    else
	return gcry_error(GPG_ERR_NO_ERROR);
}