Exponent 3 damage spreads...

[Peter Gutmann]

David Wagner <daw at cs.berkeley.edu> writes:

>(a) Any implementation that doesn't check whether there is extra junk left
>over after the hash digest isn't implementing the PKCS#1.5 standard
>correctly. That's a bug in the implementation.

No, it's a bug in the spec:

>9.4 Encryption-block parsing
>
>It is an error if any of the following conditions occurs:
>
>     o    The encryption block EB cannot be parsed
>          unambiguously (see notes to Section 8.1).
>          
>     o    The padding string PS consists of fewer than eight
>          octets, or is inconsistent with the block type BT.
>          
>     o    The decryption process is a public-key operation
>          and the block type BT is not 00 or 01, or the
>          decryption process is a private-key operation and
>          the block type is not 02.

Nothing in there about trailing garbage.

Someone else said that the spec requires creating an encoded form of the ASN.1
data and then comparing the encoded form.  Let's look at the spec again:

>10.2.3 Data decoding
>
>The data D shall be BER-decoded to give an ASN.1 value of type DigestInfo,
>which shall be separated into a message digest MD and a message-digest
>algorithm identifier. The message-digest algorithm identifier shall determine
>the "selected" message-digest algorithm for the next step.

Again, there's nothing in there that requires comparing the encoded form.

You may be wondering why this differs somewhat from RFC 3447.  That's because
this is the original "gold standard" PKCS #1 spec, the one that everyone was
using when PGP, PKCS #7/S/MIME, SSL, and possibly DNSSEC were created.  True,
since then other variants of the spec have imposed slightly different
requirements, but the gold standard version that's contemporaneous with the
security protocols in which it's caused problems doesn't require the measures
that people have been claiming.

(And I really, *really* don't want to get into some pointless debate over
whose bits are more standards-compliant.  All I'm pointing out is that a
blanket assertion that "doing/not doing X is a violation of the spec" is an
invalid claim.  At best you can say "doing X is a violation of one variant of
the spec that didn't actually exist when the affected protocols were
created").

>If your implementation supports appending additional parameter fields of some
>general structure, then you have not implemented conventional PKCS#1.5
>signatures as they are usually understood; instead, you have implemented some
>extension. 

No, you've implemented PKCS #1 exactly as the specification says.  Look up
the definition of AlgorithmIdentifier.

>Why are people still deploying cryptographic schemes that haven't been
>properly validated?

Because everyone else on the planet is doing it, and (with a few caveats) it's
worked so far.  If you're quite happy to not be able to talk to anything else
in existence, you're welcome to use PSS or whatever's in fashion at the
moment.  Since my users expect to be able to, you know, talk to one another,
I'll stick with PKCS #1.

>Consequently, I think the focus on e=3 is misguided. 

It's not at all misguided.  This whole debate about trying to hang on to e=3
seems like the argument about epicycles, you modify the theory to handle
anomalies, then you modify it again to handle further anomalies, then you
modify it again, and again, ...  Alternatively, you say that the earth
revolves around the sun, and all of the kludges upon kludges go away.
Similarly, the thousands of words of nitpicking standards, bashing ASN.1, and
so on ad nauseum, can be eliminated entirely by following one simple rule:

  Don't use e=3

This is never going to be reliably fixed if the "fix" is to assume that every
implementor and implementation everywhere can get every miniscule detail right
every time.  The fix is to stop using e=3 and be done with it.  Even Microsoft
finally got this message after 14 years of getting RC4 wrong, they simply
banned its use because they realised that they'd never get it fixed even if,
in theory, it's easy to get right on paper.

Peter.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com