On Mon, Jul 08, 2002 at 06:43:06PM +0200, Richard Levitte - VMS Whacker wrote: > In message <[EMAIL PROTECTED]> on Fri, 5 Jul 2002 18:45:12 +0300, >Vadim Fedukovich <[EMAIL PROTECTED]> said: > > vf> see a program attached for details. It handles numbers of 1024 bit range > vf> doing Shamir secret sharing. > > Secret sharing is something I've been pondering implementing in > OpenSSL for a while now, on and off. Too bad your snipet of code is > licensed under the GPL, that makes it unusable to be included in > OpenSSL, if you'd be inclined that way.
I'd be happy this code to be integrated into openssl and will do my best to maintain it. Besides, I was typing too fast and forget to mention openssl in the source, so I should at least to say sorry now. Please find attached another code, to get shares of product of two secrets available in shares only. That is, avoiding recovery from shares for doing multiplication. Please note GRR technique of multiplication is not the same as that of Boneh and Franklin (that is likely used in ITTS code). In GRR, product of shares is shared again. > Anyhow, I'm not going to discuss licenses, that's not the purpose of > this letter. Instead, I'd like to discuss protocol and usability. > > Shamir's method is beautiful and really easy to understand with a > certain minimum of mathematical knowledge. However, it doesn't give > any hint on how to protect the shares (understandably, of course). > To use it as a part of OpenSSL, and especially as part of the openssl > application (as well as other applications based on OpenSSL), one > needs to collect the shares in one place, one way or the other. I'd say, share-holders need to run a networked protocol to calculate something or just recover original secret. They own their hardware. Probably, the concern is cheating to break such a protocol. > I'm imagining the following scenario: > > - We implement the shared secret PEM file, with the identity "SHAMIR > SHARED SECRET", which would contain an ASN.1 blob (for which we'd > need to define a module) containing the prime p (assuming we use > modular arithmetics for the calculations), the small number x (the x > coordinate of the point that is your share) and the share itself. > This would then be protected the same way we currently protect > private keys. This part is actually rather easy. Yes, sure. I was asking one day whether there's any standards activity in secret-sharing, to interop right from the start. > - I get involved in a sensitive project where shared secrets are used > for protection. The implementation I see right now is that each > participant inserts his or her diskette, tells the software what the > name of the file on that diskette is and gives a password when > prompted for it... One could keep SSL links from client doing sharing or recovery to set of servers (share-holders) > The last part is somewhat of a problem, security-wise. I mean, when I > play with my own software, use my own private key protected > appropriately, running on my laptop that isn't connected to anything > and that has been checked for trojans, viruses and whatever, I feel > rather safe signing some document, removing the diskette and > reconnecting to the net in some fashion (no, I don't usually do things > in quite such a paranoid fashion. My laptop is secure enough and > checked enough for my use). However, sticking that same diskette on > another system and giving it a password, when I'm not entirely certain > there's no stealth program listening to the keyborad input and > secretly taking a backup of my diskette, isn't something I would do > without a lot of guarantees, and then I would still be suspicious. > > Is there any scheme that would make the use of shared secrets a bit > safer, or will this simply come down to each participant's trust in > the system where the shared secret is used? There are lots of papers on verifiable secret sharing. GRR mentioned in the code attached and Pedersen-91, just to name a few. Personally, I came across commitments first with "encrypted open books" idea from Cypherpunks manifesto. There's an extensive survey by Douglas Stinson and Ruizhong Wei, unfortunately a bit old. Also, there's a great page by Helger Lipmaa. And I'm sure there may be better pointers. Also, ResearchIndex is a great tool. In short, it could be not easy to chose something best to implement. > For perfect safety (as closely as you can get to it), hardware devices > like nCipher (who uses some kind of shared secret for the admin cards > in the nForec boxes, I believe) are of course the option. However, I > don't have the funds for that, and I'd really like to know of any > software variant that is as close to safe as I'd like. > > Anyone? URLs are perfectly fine as pointers :-). http://www.tcs.hut.fi/~helger/crypto/link/mpc/ http://www.cacr.math.uwaterloo.ca/~dstinson/ssbib.html yours, Vadim > -- > Richard Levitte \ Spannv?gen 38, II \ [EMAIL PROTECTED] > Redakteur@Stacken \ S-168 35 BROMMA \ T: +46-8-26 52 47 > \ SWEDEN \ or +46-708-26 53 44 > Procurator Odiosus Ex Infernis -- [EMAIL PROTECTED] > Member of the OpenSSL development team: http://www.openssl.org/ > > Unsolicited commercial email is subject to an archival fee of $400. > See <http://www.stacken.kth.se/~levitte/mail/> for more info.
/* Multiplication protocol for numbers available as shares, technique of * Rosario Gennaro, Michael O. Rabin, Tal Rabin * Copyright (c) 2002 Vadim Fedukovich vf at unity dot net * This program is distributed under GPL * * This product includes software developed by the OpenSSL Project * for use in the OpenSSL Toolkit (http://www.openssl.org/) * This product includes cryptographic software written by Eric Young * ([EMAIL PROTECTED]). This product includes software written by Tim * Hudson ([EMAIL PROTECTED]). */ #include <openssl/bn.h> // quorum size #define THR 4 // t // number of players #define CNT 9 // 2t+1 // prepare to handle numbers of this size #define BITSZ 1024 // recover from shares y[CNT] calculated at x[CNT] points, // from polynom of "power" BIGNUM *shr_recvr(BIGNUM **y, BIGNUM **x, BIGNUM *mod, int power); // calculate a share at the point x using coefficients matrix[] // using polynom of "power"; secret to share should be matrix[0] BIGNUM *shr_calc(BIGNUM **matrix, BIGNUM *x, BIGNUM *mod, int power); int main() { BIGNUM *p = BN_new(), *a = BN_new(), *b = BN_new(), *mul = BN_new(), *shr_ab[CNT], *shr_mul[CNT][CNT], *shr_prod[THR+1], *mtx_a[THR+1], *mtx_b[THR+1], *x[CNT], *shr_a, *shr_b, *mul_recvr; BN_CTX *ctx = BN_CTX_new(); int j, k; BN_generate_prime(p, BITSZ, 0, NULL, NULL, NULL, NULL); // chose some secrets BN_rand_range(a, p); BN_rand_range(b, p); // compare result to normal product (later) BN_mod_mul(mul, a, b, p, ctx); // prepare to initial secrets sharing mtx_a[0] = a; mtx_b[0] = b; for(j=1; j<THR+1; j++) { mtx_a[j] = BN_new(); mtx_b[j] = BN_new(); BN_rand_range(mtx_a[j], p); BN_rand_range(mtx_b[j], p); } for(j=0; j<CNT; j++) { shr_ab[j] = BN_new(); x[j] = BN_new(); BN_set_word(x[j], j+1); } // make shares and multiply them for(j=0; j<CNT; j++) { shr_a = shr_calc(mtx_a, x[j], p, THR+1); shr_b = shr_calc(mtx_b, x[j], p, THR+1); BN_mod_mul(shr_ab[j], shr_a, shr_b, p, ctx); BN_free(shr_a); BN_free(shr_b); } // share each product to everyone for(j=0; j<CNT; j++) { // from mtx_a[0] = shr_ab[j]; for(k=1; k<THR+1; k++) { BN_rand_range(mtx_a[k], p); } for(k=0; k<CNT; k++) { // to // [from][to] shr_mul[j][k] = shr_calc(mtx_a, x[k], p, THR+1); } } // recover shares of the product for(j=0; j<THR+1; j++) { for(k=0; k<CNT; k++) shr_ab[k] = shr_mul[k][j]; // recover from 2t+1 polynomial shr_prod[j] = shr_recvr(shr_ab, x, p, CNT); } // final recover mul_recvr = shr_recvr(shr_prod, x, p, THR+1); if(BN_cmp(mul, mul_recvr) == 0) printf("Recovered Ok\n"); BN_CTX_free(ctx); return 0; } BIGNUM *shr_recvr(BIGNUM **y, BIGNUM **x, BIGNUM *mod, int power) { int j, k; BIGNUM *ret = BN_new(), *nxt, *subs, *rev = BN_new(); BN_CTX *ctx = BN_CTX_new(); // \sum_k{y_k * \mul_j{x_j/(x_j-x_k)}} BN_set_word(ret, 0L); for(k=0; k<power; k++) { nxt = BN_dup(y[k]); for(j=0; j<power; j++) { if(j==k) continue; subs = BN_dup(x[j]); BN_mod_sub(subs, subs, x[k], mod, ctx); BN_mod_inverse(rev, subs, mod, ctx); BN_free(subs); BN_mod_mul(nxt, nxt, x[j], mod, ctx); BN_mod_mul(nxt, nxt, rev, mod, ctx); } // j BN_mod_add(ret, ret, nxt, mod, ctx); BN_free(nxt); } // k BN_CTX_free(ctx); return ret; } BIGNUM *shr_calc(BIGNUM **matrix, BIGNUM *x, BIGNUM *mod, int power) { BIGNUM *ret; // = BN_new(); BN_CTX * ctx = BN_CTX_new(); int j; // ret = matrix[power-1] // j=1..power: ret = x * ret + matrix[power-j-1] ret = BN_dup(matrix[power-1]); for(j=1; j<power; j++) { BN_mod_mul(ret, ret, x, mod, ctx); BN_mod_add(ret, ret, matrix[power-j-1], mod, ctx); } BN_CTX_free(ctx); return ret; }
