22 December 2011

Digsig Is the Worst Signature Ever Invented

From a thread on non-repudiation: http://lists.randombit.net/mailman/listinfo/cryptography

Date: Thu, 22 Dec 2011 20:01:52 +1100
From: ianG <iang[at]iang.org>
To: cryptography[at]randombit.net
Subject: Re: [cryptography] How are expired code-signing certs revoked? (nonrepudiation)

On 22/12/11 18:17 PM, John Case wrote:

> On Wed, 7 Dec 2011, Jon Callas wrote:
>
>> Nonrepudiation is a somewhat daft belief.

[ianG]

+1

[Callas]

>> Let me give a gedankenexperiment. Suppose Alice phones up Bob and
>> says, "Hey, Bob, I just noticed that you have a digital nature from
>> me. Well, ummm, I didn't do it. I have no idea how that could have
>> happened, but it wasn't me." Nonrepudiation is the belief that the
>> probability that Alice is telling the truth is less than 2^{-128},
>> assuming a 3K RSA key or 256-bit ECDSA key either with SHA-256.
>> Moreover, if that signature was made with an ECDSA-521 bit key and
>> SHA-512, then the probability she's telling the truth goes down to
>> 2^{-256}.
>>
>> I don't know about you, but I think that the chance that Alice was
>> hacked is greater than 1 in 2^128. In fact, I'm willing to believe
>> that the probability that somehow space aliens, or Alice has an
>> unknown evil twin, or some mad scientist has invented a cloning ray
>> is greater than one in 2^128. Ironically, as the key size goes up,
>> then Alice gets even better excuses. If we used a 1k-bit ECDSA key
>> and a 1024-bit hash, then new reasonable excuses for Alice suggest
>> themselves, like that perhaps she *considered* signing but didn't in
>> this universe, but in a nearby universe (under the many-worlds
>> interpretation of quantum mechanics, which all the cool kids believe
>> in this week) she did, and that signature from a nearby universe
>> somehow leaked over.
>
>

[Case]

> This is silly - it assumes that there are only two intepretations of
> her statement:
>
> - a true "collision" (something arbitrary computes to her digital
> signature, which she did not actually invoke) which is indeed as
> astronomically unlikely as you propose.
>
> - another unlikely event whose probability happens to be higher than
> the "collision".
>
> But of course there is a much simpler, far more likely explanation,
> and that is that she is lying.

[ianG]

Actually there is a much simpler, far more likely explanation:  she's
telling the truth:

        she has no idea how it happened or what it means.

The problem of digital signing is that most all the crypto world think
that the challenge is to create a a cryptographically secure copy of a
signature.  It isn't.

The challenge is to emulate signing, not emulate the signature.  Signing
is something else.  It is, in short, making a mark to record a moment in
time (in this case likely agreeing to something) so as to remember that
moment.

In law, we can remember that moment in time by thrusting the image of
the signature in front of Alice and saying "did you make that mark?" or
in more cautions terms "is that your signature?"  Now, at this stage, if
it looks like she did make the mark, *or* it looks like her signature,
we can now clarify things fairly quickly.  You can invent a decision
tree here, where the interrogation goes one way or another depending on
how she responds.

Now try the same thing with a digsig.

     "Alice, did you run the formula that resulted in this number:

            389274928398238742389472398472983...

     over this other number:

            982374982374984759347590348239847...

     that stamped over this over DOC file?"

The right answer, the *ONLY* answer is:  "I have no clue what you just
said?"

So it fails right there.  A digsig is completely and utterly the most
lousy signature ever invented because it has no capability to record in
the mind of the utterer the event at the time.  It's disgustingly bad. 
A 4 year old child could do better, and often does, with paper and crayons.

(Then, you can imagine the mad-techo-french-smartcard-scientists saying,

     "non!  Sacre blue!  Moment, sil vous plait!
     We put le key en le secure plastique un we bla de bla..."

Well no.  It has no more validity as a signature because it fails to
record the moment to the mind of Alice.  Sorry.  It ain't signing.)

[Case]

> However ... this did get me to thinking ...
>
> Can't this problem be solved by forcing Alice to tie her signing key
> to some other function(s)[1] that she would have a vested interest in
> protecting AND an attacker would have a vested interest in exploiting ?
>
> I'm thinking along the lines of:
>
> "I know Alice didn't get hacked because I see her bank account didn't
> get emptied, or I see that her ecommerce site did not disappear".
>
> "I know Alice didn't get hacked because the bitcoin wallet that we
> protected with her signing key still has X bitcoins in it, where X is
> the value I perceived our comms/transactions to be worth."
>
> Or whatever.
>
>
> [1] I have no implementation details for this.  Especially the part
> about how Bob can determine that this tie has been made, and that the
> tie has sufficient value to assure him, etc.

[ianG]

Yeah, so the protocol known as signing changes depending on the purpose
and value :)

(Oh, yeah, and that's before we get to non-repudiation........ which
clashes with law principles at its most foundational...... and if it
ever happened would lead to mass rioting and plastique bonfires and
rounding up of whoever was responsible.)

Have a merry XMas !

iang

_______________________________________________

cryptography mailing list
cryptography[at]randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography