Key safety vs Backup : History of a bad day (key-restoration problem)

Robert J. Hansen rjh at sixdemonbag.org
Sun Oct 28 19:30:16 CET 2007


Atom Smasher wrote:
> not having a particular aptitude towards higher math

Shamir's protocol revolves around being given two points on a grid and
drawing a line between them.  This is not higher math.  This is why it's
described as "amazingly simple".

> and not being fluent at programming C

Nobody's talking about C.  I despise C, honestly.  It's a very useful
language for kernels.  Outside of that I prefer other, better options be
used.

> i have a very good understanding of most crypto primitives, protocol
> wise

Shamir's algorithm is a very basic crypto primitive.  If it's not part
of your corpus of knowledge, it should be.

> but i often have to take it for granted the math does what it's 
> supposed to.

If you don't understand the math behind a crypto primitive, you don't
understand the primitive.  There is a big difference between saying
"people I trust say this primitive achieves this objective" and saying
"I've seen the math work for myself".

> i can pick from a few one time pad applications that do pretty much 
> exactly what i want

Except that you don't know C, and thus cannot say these applications
actually do what you want.

> and produce real-world verifiably and provably secure output.

The Vernam cipher is not a verifiable system.  That's the entire /point/
of it: it has no way to verify anything.  If there was a way to
verify any part of the Vernam cipher, then it would lose its
provably-secure properties.  You could just try one key after another
saying "is this the right key?" and, as soon as you received
verification that it was, you'd be done.

Not that even without verifiability the Vernam cipher is a very good
system.  Look into the history of Project Venona.  "Provable security"
is a great buzzword, but in practice it means very little.

IBM had an algorithm a few years ago (Atjai-Dwork?) which offered
provable security, but it was broken within a year by someone who
figured out a way to throw the hidden assumptions of Atjai-Dwork on its
head.

As I once said, "proofs of security are nice--they give us something to
point and laugh at."

> in the meantime, i consider the vernam cipher a very reasonable and 
> practical way to implement secret sharing.

You are free to use whatever you like.  However, please do not recommend
it as a method to other people when I cannot find one single authority
in either cryptography or software engineering who endorses this method.

> you've mentioned, and i've agreed with you, several reasons why OTP 
> sucks as an encryption algorithm. but other than referring to it as 
> "James Bond gadgetry" you haven't given any reason not to use it for
> secret sharing,

The "James Bond gadgetry" was a reference to ideas of steganographically
encoding a key inside a JPEG and letting Google cache it, or keeping it
in your camera, or... etc.  These ideas are infeasible for various reasons.

Insofar as why not to use it for secret sharing, I would think that
reason would be obvious: it cannot be used to implement a general {k, n}
threshold scheme which preserves information secrecy.  If you want to
advocate that it be used for secret sharing, the burden is on you to
establish that it's a safe and effective alternative to Shamir's and/or
Blakley's schemes, both of which have long pedigrees in the literature
attesting to their efficiency, generality and privacy.

> other than your own flavor of warm and fuzzy which seems to be that 
> another algorithm was designed just for secret sharing and 4th 
> graders can use it.

This is not "warm and fuzzy".  This is following the best practices of
the field.  The more complex an algorithm becomes, the more difficult it
becomes to implement it successfully.  This is why so few people
implement Elgamal signatures; while the math works beautifully, the
algorithm is so complex and subtle that implementing it is perilous.
The complexity of the Vernam cipher is what doomed it during Project
Venona.  Etc.

> still, the _only_ reason not to use OTP for secret sharing is that it
>  doesn't work as a threshold (t,n) scheme. the only way around that 
> is to make sure that each share is held by more than one player... 
> with shares A B and C; alice holds shares AB, bob holds shares BC, 
> charlie holds shares AC. if any one of them gets hit by a bus, the 
> secret can still be recovered. problem solved.

Great.  Let's break up the letters ABC among Alice, Bob and Charlie.
Under Shamir and Blakley's scheme, Alice, Bob and Charlie have no
knowledge whatsoever of the ultimate answer: the odds of them
successfully choosing the secret is no better than random.  (In this
case, 26**-3, about 5 * 10**-5.)

Under your scheme, Alice, Bob and Charlie each have two-thirds of the
ultimate answer.  Discovering the secret requires guessing just one
letter... odds of about 4%, making it 800 times more likely that they'll
be able to guess your secret.

I would not consider you to have solved the problem.

This is why the Vernam cipher is such a disastrous failure for secret
sharing.  You're giving away huge parts of the secret.  There's no
provision in it for hiding the secret--only for breaking it up.





More information about the Gnupg-users mailing list