Processed: Re: Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
Processing commands for cont...@bugs.debian.org: retitle 556939 libgfshare-bin: can produce broken shares containing foo.000 Bug #556939 [libgfshare-bin] libgfshare-bin: reconstruction results in garbage Changed Bug title to 'libgfshare-bin: can produce broken shares containing foo.000' from 'libgfshare-bin: reconstruction results in garbage' tags 556939 confirmed Bug #556939 [libgfshare-bin] libgfshare-bin: can produce broken shares containing foo.000 Added tag(s) confirmed. forwarded 556939 dsilv...@digital-scurf.org Bug #556939 [libgfshare-bin] libgfshare-bin: can produce broken shares containing foo.000 Set Bug forwarded-to-address to 'dsilv...@digital-scurf.org'. thanks Stopping processing here. Please contact me if you need assistance. Debian bug tracking system administrator (administrator, Debian Bugs database) -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
retitle 556939 libgfshare-bin: can produce broken shares containing foo.000 tags 556939 confirmed forwarded 556939 dsilv...@digital-scurf.org thanks A modified version of your test case eventually failed for me: in the first run it failed after 157 split/recombine attempts, and in the second run it failed after 527 attempts. One thing that the two failures had in common is that component x.000 was produced and was used to remake the share; with the default 3-of-5 setting, this can be expected to happen in around 2% of calls to gfsplit. The mathematics of Shamir secret sharing do not work correctly with x_i = 0, i.e. a component foo.000, so the library should reject any sharenrs array that contains 0, and the utilities should not produce such arrays. I'll prepare a patch this evening. Daniel, do you agree with this diagnosis? Thanks, Simon argh.sh Description: Bourne shell script signature.asc Description: Digital signature
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, 18 Nov 2009 at 14:00:25 +, Simon McVittie wrote: One thing that the two failures had in common is that component x.000 was produced and was used to remake the share Forgot to mention: if you have lost data as a result of this bug, but you still have access to *more than* the threshold number of shares of the secret, then you can recover by combining the threshold number of parts without including foo.000. (For instance, if you have a 3-of-5 share with secring.gpg.000, .001 on a USB stick and .100, .101, .102 on three different machines, recover secring.gpg by combining parts .001, .100 and .101.) S signature.asc Description: Digital signature
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, Nov 18, 2009 at 03:36:37PM +0100, Florian Zumbiehl wrote: Why is it randomized anyhow? Just numbering shares from 1 would produce more reproducible results, thus making it more likely that problems specific to a certain use case would get noticed before it's too late. It probably would be easier to use for some purposes, too, if file names were easier to predict. Randomised so that you can easily strip the numbers and place them elsewhere and thereby make it harder to guess the share numbers. BTW, the command line parser is pretty much completely broken if you judge it by the error messages it produces even for completely valid values as per its own help output. In case you want to fix that, too ... Back then I wasn't very good at cmdline parsers. Patch welcome. D. -- Daniel Silverstone http://www.digital-scurf.org/ PGP mail accepted and encouraged.Key Id: 3CCE BABE 206C 3B69 -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, Nov 18, 2009 at 04:05:20PM +0100, Florian Zumbiehl wrote: Randomised so that you can easily strip the numbers and place them elsewhere and thereby make it harder to guess the share numbers. And that is good for what? If you lose a number of shares equal-to-or-greater-than the number required to reconstruct the share, it might arguably provide you with a short period of time in which to revoke those keys. I'd be quite happy to receive a patch which offered an option of sequential vs. randomised share numbers. D. (And no, I'm not claiming added security, just the potential of a little more time to deal with the fact that your security is breached) -- Daniel Silverstone http://www.digital-scurf.org/ PGP mail accepted and encouraged.Key Id: 3CCE BABE 206C 3B69 -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
Hi, On Wed, Nov 18, 2009 at 03:36:37PM +0100, Florian Zumbiehl wrote: Why is it randomized anyhow? Just numbering shares from 1 would produce more reproducible results, thus making it more likely that problems specific to a certain use case would get noticed before it's too late. It probably would be easier to use for some purposes, too, if file names were easier to predict. Randomised so that you can easily strip the numbers and place them elsewhere and thereby make it harder to guess the share numbers. And that is good for what? Florian -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
Hi, One thing that the two failures had in common is that component x.000 was produced and was used to remake the share; with the default 3-of-5 setting, this can be expected to happen in around 2% of calls to gfsplit. That indeed seems to fit my observations. The mathematics of Shamir secret sharing do not work correctly with x_i = 0, i.e. a component foo.000, so the library should reject any sharenrs array that contains 0, and the utilities should not produce such arrays. I'll prepare a patch this evening. Why is it randomized anyhow? Just numbering shares from 1 would produce more reproducible results, thus making it more likely that problems specific to a certain use case would get noticed before it's too late. It probably would be easier to use for some purposes, too, if file names were easier to predict. BTW, the command line parser is pretty much completely broken if you judge it by the error messages it produces even for completely valid values as per its own help output. In case you want to fix that, too ... Florian -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, 18 Nov 2009 at 15:09:07 +, Daniel Silverstone wrote: If you lose a number of shares equal-to-or-greater-than the number required to reconstruct the share, it might arguably provide you with a short period of time in which to revoke those keys. I'd be quite happy to receive a patch which offered an option of sequential vs. randomised share numbers. I think a more compelling rationale for non-sequential share numbers is that it makes it more difficult for an attacker to determine how many shares there were, and what the threshold is. The distinction isn't arbitrarily between share numbers, it's between 0 and every other share number; in theory, the zero'th share should be equal to the secret itself. It seems that the splitting function doesn't output the secret as foo.000, though... perhaps foo.000 ends up containing uninitialized memory? The code does have some confusion between 0 meaning share number 0, and 0 meaning a share that was not supplied. S signature.asc Description: Digital signature
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, 18 Nov 2009 at 14:22:38 +, Daniel Silverstone wrote:
Indeed, the zero-share is not useful since in theory it'd be the data
unchanged.
Thankfully, due to an implementation quirk, the share 000 output is a copy
of share 001, so the only differences are:
* it's mislabelled and won't combine correctly
* if you already had a share 001, you have one less share than you thought
The software should reject zero-share instances, and not create them.
I attach a bzr bundle, also available from
https://code.launchpad.net/~smcv/libgfshare/deb556939, which has passed
2500 consecutive 3-of-5 tests using the script attached previously.
I'll patch this in Debian shortly.
Thanks,
S
# Bazaar merge directive format 2 (Bazaar 0.90)
# revision_id: s...@debian.org-20091118233654-w132cs2v7b6l2616
# target_branch: http://bzr.digital-scurf.org/trees/dsilvers\
# /libgfshare/devel/
# testament_sha1: 3c1dbfd53a2fb94a67045adafc50f56d5794dd8f
# timestamp: 2009-11-18 23:42:16 +
# base_revision_id: dsilv...@digital-scurf.org-20070822194948-\
# 63piocp89ra6ld7b
#
# Begin patch
=== modified file 'README'
--- README 2006-01-15 17:58:21 +
+++ README 2009-11-18 23:36:39 +
@@ -28,4 +28,29 @@
-- Daniel Silverstone. 2006-01-15
-
+Recovering from previous versions of gfsplit producing foo.000
+^^
+
+The quick version: if you have split a secret into shares and one
+of them is numbered 000, recover the secret by re-labelling it to
+001 (i.e. rename the file, if you're using gfcombine).
+
+Previous versions of libgfshare could incorrectly produce a share
+numbered 000, and the gfsplit utility would produce such a share
+sometimes (with the default settings, a 3-of-5 share, this will
+happen about 2% of the time). In gfsplit this produces filenames
+ending with .000.
+
+Mathematically, the share numbered 0 would be the secret itself,
+which is why it shouldn't be used. However, due to the way libgfshare
+implements multiplication via exp/log tables, the output will
+actually be a copy of the data that would appear in share number 001,
+so the secret is not actually leaked.
+
+Recombining shares that include share number 000 doesn't work: it's
+silently ignored. If share 000 is renamed to share 001, recombination
+should work; the exception is if you already had a copy of share 001,
+in which case you can only recover the secret by having one extra share
+above the normal threshold.
+
+ -- Simon McVittie. 2009-11-18
=== modified file 'src/libgfshare.c'
--- src/libgfshare.c 2006-02-26 14:01:53 +
+++ src/libgfshare.c 2009-11-18 23:35:57 +
@@ -27,6 +27,7 @@
#include libgfshare.h
#include libgfshare_tables.h
+#include errno.h
#include stdlib.h
#include string.h
@@ -65,7 +66,20 @@
unsigned char threshold,
unsigned int size )
{
- gfshare_ctx *ctx = XMALLOC( sizeof(struct _gfshare_ctx) );
+ gfshare_ctx *ctx;
+ unsigned int i;
+
+ for (i = 0; i sharecount; i++) {
+if (sharenrs[i] == 0) {
+ /* can't have x[i] = 0 - that would just be a copy of the secret, in
+ * theory (in fact, due to the way we use exp/log for multiplication and
+ * treat log(0) as 0, it ends up as a copy of x[i] = 1) */
+ errno = EINVAL;
+ return NULL;
+}
+ }
+
+ ctx = XMALLOC( sizeof(struct _gfshare_ctx) );
ctx-sharecount = sharecount;
ctx-threshold = threshold;
ctx-size = size;
=== modified file 'tools/gfcombine.c'
--- tools/gfcombine.c 2006-02-26 14:01:53 +
+++ tools/gfcombine.c 2009-11-18 23:36:54 +
@@ -52,6 +52,12 @@
fprintf( stderr, %s: %s: bad filename\nInput files should be called name.NNN\n, progname, fname );
}
+static void
+zero_filename( char* fname )
+{
+ fprintf( stderr, %s: %s: input files name.000 don't work, see README\n, progname, fname );
+}
+
static int
check_filenames( char **filenames, int count )
{
@@ -73,6 +79,12 @@
bad_filename(filenames[i]);
return 1;
}
+if( filenames[i][nlen-3] == '0'
+filenames[i][nlen-2] == '0'
+filenames[i][nlen-1] == '0') {
+ zero_filename(filenames[i]);
+ return 1;
+}
}
return 0;
}
=== modified file 'tools/gfsplit.c'
--- tools/gfsplit.c 2006-07-29 12:32:31 +
+++ tools/gfsplit.c 2009-11-18 23:35:36 +
@@ -92,6 +92,9 @@
}
for( i = 0; i sharecount; ++i ) {
unsigned char proposed = (random() 0xff00) 8;
+if( proposed == 0 ) {
+ proposed = 1;
+}
SHARENR_TRY_AGAIN:
for( j = 0; j i; ++j ) {
if( sharenrs[j] == proposed ) {
# Begin bundle
IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWUIMPPcABwxfgFwQW35n
30+6YA1hxnztWzs6BQCqBjjrdo0u7pa3VVYhBa0gHCSQUxpMQZBMRPCo8npppTyh6m0ENPSG
TQ9Q2UEohMmmmhpqnpGoZMhkyAGmhoaAAAaAcZGmTE0GTJhNMgZDQGgNMmhgBNAYSIhEyTTRk1Ma
GQk/VMhtTaT0RoaAGmnqaHqAcZGmTE0GTJhNMgZDQGgNMmhgBNAYSRAIAhoI1J+gmSnqNDQeKPSN
Bug#556939: libgfshare-bin: can produce broken shares containing foo.000
On Wed, Nov 18, 2009 at 02:00:25PM +, Simon McVittie wrote: The mathematics of Shamir secret sharing do not work correctly with x_i = 0, i.e. a component foo.000, so the library should reject any sharenrs array that contains 0, and the utilities should not produce such arrays. I'll prepare a patch this evening. Daniel, do you agree with this diagnosis? Indeed, the zero-share is not useful since in theory it'd be the data unchanged. The software should reject zero-share instances, and not create them. I'm happy for you to supply me with a bundle, or I can sort it out myself, whichever you would prefer. D. -- Daniel Silverstone http://www.digital-scurf.org/ PGP mail accepted and encouraged.Key Id: 3CCE BABE 206C 3B69 -- To UNSUBSCRIBE, email to debian-bugs-rc-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
