/* Implementation of ring signatures from * http://theory.lcs.mit.edu/~rivest/RivestShamirTauman-HowToLeakASecret.pdf * by Rivest, Shamir and Tauman * * This creates and verifies a signature such that it was produced from * one of a fixed set of RSA keys. * * It requires the openssl library to build, which is available from * www.openssl.org. * * This program takes a PGP public key ring file which holds a set of * old-style RSA public keys. It creates and verifies signatures which * are such that they were issued by one of the keys in that file, but * there is no way to tell which one did it. In this way the signer can * leak partial information about his identity - that he is one member * of a selected set of signers. * * To sign, the signer must also give a PGP secret key file which holds * one key (actually the program ignores any keys past the first). * That key should be the secret part of one of the keys in the public * key file. Also, it should be set to have no passphrase - it is too * complicated for a simple program like this to try to untangle PGP * passphrases. So set your key to have no passphrase, then run this * program, then set it back. * * The program outputs the signature in the form of a list of big numbers, * base64 encoded. There will be as many numbers as there were keys in * the public key file. So signatures are quite large in this scheme, * proportional to the number of keys in the group that the signature * comes from. They are also proportional to the largest key in the * group, so all else being equal try not to include really big keys if * you care about size. * * The signature is not appended to the text being signed, it is just * output separately. The signer can combine them manually with some kind * of cut marks so that the recipient can separate out the signature from * the file being signed. Some perl scripts that do this are supposed * to be distributed with the program. (That is what is used to verify * the signature in this file itself.) * * The recipient must use the same PGP public key file that the signer * used. So that may have to be sent along as well. He runs the program * with the PGP file and the file to be verified, and sends the signature * data into stdin (using the "<" character). The program will print * whether the signature is good or not. * * This program was written in just a couple of evenings so it is * a little rough. This is version 0.9 or so - at least it works. * It has only been tested on my Linux system. * * The program is released into the public domain. See the end for * authorship information. */ #include #include #include "openssl/bn.h" #include "openssl/rsa.h" #include "openssl/sha.h" #include "openssl/evp.h" /* Cipher block size; we use Blowfish */ #define CIPHERBLOCK 8 typedef unsigned char uchar; enum { ERR_OK = 0, ERR_BADPKT=-100, ERR_EOF, ERR_SECNOTFOUND, ERR_BADSIG, }; /************************** PGP FILE PARSING ***************************/ /* Read the N and E values from a PGP public key packet */ int rdpgppub( BIGNUM *n, BIGNUM *e, unsigned *bytesused, uchar *buf, unsigned len ) { int nbits, nlen, ebits, elen; unsigned o=2; if (len < 10) return ERR_BADPKT; if (buf[0] == 4) /* Check version 4, 3, or 2 */ o = 0; else if (buf[0] != 2 && buf[0] != 3) /* V2&3 have 2 extra bytes */ return ERR_BADPKT; if (buf[5+o] != 1) /* Check alg - 1 is RSA */ return ERR_BADPKT; nbits = (buf[6+o] << 8) | buf[7+o]; /* Read modulus */ nlen = (nbits + 7)/8; if (len < 10+o+nlen) return ERR_BADPKT; BN_bin2bn(buf+o+8, nlen, n); ebits = (buf[8+o+nlen] << 8) | buf[9+o+nlen]; /* Read exponent */ elen = (ebits + 7)/8; if (len < 10+o+nlen+elen) return ERR_BADPKT; BN_bin2bn(buf+10+o+nlen, elen, e); if (bytesused) *bytesused = 10+o+nlen+elen; return ERR_OK; } /* Read the N, E, D values from a PGP secret key packet with no passphrase */ int rdpgpsec( BIGNUM *n, BIGNUM *e, BIGNUM *d, uchar *buf, unsigned len ) { int err; int nbits, nlen, ebits, elen, dbits, dlen; unsigned o; if ((err = rdpgppub(n, e, &o, buf, len)) < 0) return err; if (len < o+3) return ERR_BADPKT; if (buf[o] != 0) /* Check that packet is unencrypted */ return ERR_BADPKT; dbits = (buf[o+1] << 8) | buf[o+2]; /* Read private exponent */ dlen = (dbits + 7)/8; if (len < o+3+dlen) return ERR_BADPKT; BN_bin2bn(buf+o+3, dlen, d); return ERR_OK; } /* Read the next PGP packet into malloc'd memory */ int getpgppkt( uchar **pbuf, unsigned *plen, int *type, FILE *f ) { int c, c1; uchar *buf; unsigned len; int llen; uchar lbuf[4]; c = fgetc(f); if (c == EOF) return ERR_EOF; if ((c & 0xc0) == 0x80) { /* Old PGP packet */ *type = (c >> 2) & 0xf; llen = c & 0x3; if (llen++==3) return ERR_BADPKT; rdllen: if (llen==3) llen=4; memset (lbuf, 0, 4); if (fread(lbuf+4-llen, 1, llen, f) != llen) return ERR_BADPKT; len = (lbuf[0]<<24) | (lbuf[1]<<16) | (lbuf[2]<<8) | lbuf[3]; } else if ((c & 0xc0) == 0xc0) { /* New PGP packet */ *type = c & 0x3f; c = fgetc(f); if (c == EOF) return ERR_BADPKT; if (c == 0xff) { llen = 4; goto rdllen; } if (c >= 0xe0) return ERR_BADPKT; if (c >= 0xc0) { /* Two byte length */ c1 = fgetc(f); if (c1 == EOF) return ERR_BADPKT; len = (c<<8) + c1 - 0xc000 + 0xc0; } else { /* One byte length */ len = c; } } else { /* Non PGP packet */ return ERR_BADPKT; } buf = malloc(len); if (buf==NULL) return ERR_BADPKT; if (fread(buf, 1, len, f) != len) return ERR_BADPKT; *pbuf = buf; *plen = len; return ERR_OK; } /* Read a PGP key ring and create arrays of all the n, e values */ int rdpgppubring(BIGNUM ***n_arr_ptr, BIGNUM ***e_arr_ptr, int *nkeys_ptr, FILE *f) { int err = ERR_OK; uchar *buf; unsigned len; int type; int nkeys = 0; BIGNUM **n_arr = NULL; BIGNUM **e_arr = NULL; BIGNUM *n, *e; n_arr = malloc(sizeof(BIGNUM *)); e_arr = malloc(sizeof(BIGNUM *)); while (err == ERR_OK) { err = getpgppkt (&buf, &len, &type, f); if (err != ERR_OK) break; if (type == 6) /* public key packet */ { n = BN_new(); e = BN_new(); err = rdpgppub(n, e, NULL, buf, len); if (err != ERR_OK) break; ++nkeys; n_arr = realloc(n_arr, sizeof(BIGNUM *) * nkeys); e_arr = realloc(e_arr, sizeof(BIGNUM *) * nkeys); n_arr[nkeys-1] = n; e_arr[nkeys-1] = e; } free (buf); } if (err != ERR_EOF) return err; err = ERR_OK; *n_arr_ptr = n_arr; *e_arr_ptr = e_arr; *nkeys_ptr = nkeys; return err; } /* Read a PGP secret key file and find the corresponding value in the * array of public key values. Return the d value and the index in the * public key array. */ int rdpgpsecring(BIGNUM *d, int *secindex, BIGNUM **n_arr, BIGNUM **e_arr, int nkeys, FILE *f) { int err = ERR_OK; BIGNUM *n, *e; uchar *buf; unsigned len; int i; int type; err = getpgppkt (&buf, &len, &type, f); if (err != ERR_OK) return err; if (type != 5) /* Secret key packet */ return ERR_BADPKT; n = BN_new(); e = BN_new(); err = rdpgpsec(n, e, d, buf, len); if (err != ERR_OK) return err; for (i=0; i 0) { t = n[i]; n[i] = n[j]; n[j] = t; t = e[i]; e[i] = e[j]; e[j] = t; } } } return ERR_OK; } /* Hash the file. Should have opened it in ASCII mode so that we have * standard Unix line endings (newlines only). */ int hashfile( uchar md[5], FILE *f ) { char buf[1024]; SHA_CTX sha; SHA_Init(&sha); for ( ; ; ) { if (fgets (buf, sizeof(buf), f) == NULL) break; SHA_Update(&sha, buf, strlen(buf)); } SHA_Final (md, &sha); return ERR_OK; } /* Do an RSA enc/dec, where the input/output value may be larger * than n. In fact, val should be much larger than n or this may fail * to keep val within the desired range. * To decrypt pass d in place of e. */ int rsaencdec( BIGNUM *rslt, BIGNUM *val, BIGNUM *n, BIGNUM *e, BN_CTX *ctx ) { BIGNUM *rem = BN_new(); BIGNUM *newrem = BN_new(); BN_div (NULL, rem, val, n, ctx); BN_mod_exp (newrem, rem, e, n, ctx); BN_sub (rslt, val, rem); BN_add (rslt, rslt, newrem); BN_free (rem); BN_free (newrem); } /************************** SIG CREATE/VERIFY ***************************/ /* Verify a signature. sigs holds the per-key signature values, * hashval is the hash of the data which was signed, valbytes is the * length of the values we work with, several bytes longer than the longest * modulus, and n_arr and e_arr are the RSA public key values, of whic * there are nkeys of them. (There are also nkeys of sigs.) */ int checksig( BIGNUM **sigs, uchar *hashval, int hashvalbytes, int valbytes, BIGNUM **n_arr, BIGNUM **e_arr, int nkeys, BN_CTX *ctx ) { BIGNUM *val = BN_new(); uchar ivec[CIPHERBLOCK]; BF_KEY bf; uchar *sigbuf; uchar *xorbuf; int vallen; int i, j; /* Key cipher with the hash value */ BF_set_key (&bf, hashvalbytes, hashval); /* Init xorbuf to 0's */ xorbuf = malloc(valbytes); memset (xorbuf, 0, valbytes); sigbuf = malloc(valbytes); for (i=0; i valbytes) { fprintf (stderr, "Bad signature created by signer\n"); exit (3); } /* XOR into buffer */ memset (sigbuf, 0, valbytes); BN_bn2bin (val, sigbuf+valbytes-vallen); for (j=0; j valbytes with random val */ vallen = BN_num_bytes(val); /* XOR into right xor buf and encrypt */ memset (sigbuf, 0, valbytes); BN_bn2bin (val, sigbuf+valbytes-vallen); for (j=0; jsecindex; i--) { /* For other keys do a fake value */ sigs[i] = BN_new(); BN_rand_range (sigs[i], bigval); rsaencdec (val, sigs[i], n_arr[i], e_arr[i], ctx); /* Infinitisimal chance that vallen > valbytes with random val */ vallen = BN_num_bytes(val); /* XOR into left xor buf and decrypt */ memset (sigbuf, 0, valbytes); BN_bn2bin (val, sigbuf+valbytes-vallen); for (j=0; j