Revision control
Copy as Markdown
Other Tools
/*
* 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);
}