[3033] in cryptography@c2.net mail archive
Fail stop signatures question
daemon@ATHENA.MIT.EDU (sinster@darkwater.com)
Wed Jul 22 11:35:22 1998
Date: Tue, 21 Jul 1998 19:59:33 -0700 (PDT)
To: cryptography@c2.net
From: sinster@darkwater.com
I'm reading through Applied Cryptography (2nd edition) again and on
page 85 there is a basic description of fail-stop signatures. This
time I smelled something foul.
Either I'm missing something in the description here, or fail-stop
signatures are completely valueless (or the description is missing
something important).
The assumption is that Alice is being attacked by Eve, who has a
mega-gonzo network of supercomputers dedicated to brute-forcing
Alice's private key. Presumably Eve is doing this by successively
signing a test document until a signature is generated that is
validated by Alice's public key (which, being a public key, Eve can be
assumed to have).
But Alice has chosen a crypto algorithm under which a tremendous number
of private keys can be validated by the same public key... the important
quality here is that the different private keys each generate different
signatures, so Alice can show that any brute-forced private key is
a forgery through a simple signature comparison unless the brute
forcer just happens to stumble on the correct private key.
Now here's the problem that I see: if Eve has such impressive iron that
she's seriously considering brute-forcing Alice's private key, then she
can just as well search the _entire_ key space and get all the private
keys that match Alice's public key. That'll only take twice as long as
she would normally expect in the average case. More importantly, Eve
knows in advance that Alice's algorithm pairs multiple private keys
with each public key, so she knows that any match might be false. She
can then just sit back and wait to see a signed message from Alice,
which she can use to select the correct private key (because only one
will generate the identical signature).
In fact, how does Eve find out about Alice's existance in the first place,
and more importantly, become interested in forging Alice's signature
without _already_ having a signed document from Alice? In this case,
Eve can just add that comparison to her search criteria, and we're back to
the original case in which Eve can expect to search about half the keyspace
before finding Alice's private key.
In other words, fail-stop signatures give no protection beyond regular
signatures in precisely the case they were designed to protect against.
Even in the case where Eve is just searching with a couple pentiums in
the hopes of randomly stumbling on Alice's private key before the earth
plummets into the sun, she can still easily get enough information that
she won't get fooled by a false match.
--
Jon Paul Nollmann ne' Darren Senn sinster@balltech.net
Unsolicited commercial email will be archived at $1/byte/day.
Defenestrate Microsoft!
