Exponent 3 damage spreads...

[Leichter, Jerry]

| 
| >       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.
| >
| >Here, any trailing garbage would be included in data D. But does an
| >ASN.1 value allow such a thing? I am asking this independently of our
| >discussion here.
| 
| I don't think it's a problem, you just take the ASN.1 DigestInfo
| value, since the trailing garbage isn't part of the DigestInfo, you
| ignore it.  Specifically, the ASN.1 object is entirely self-contained,
| so you can tell exactly where it ends and what it contains.  Anything
| outside it is beyond the scope of this specification :-).
This is a rather peculiar interpretation of the spec.  If I look at a C
specification and it tells me that an integer is a string of digits,
when I write a C compiler, am I permitted to say that "123@#&%" can
be parsed as an "entirely contained" integer, with the "@#&%" "beyond
the scope of the specification"?

The only reasonable reading of the text quoted above is that the D must
consist of, and *only* of, an ASN.1 value of the given type.

Granted, one or more implementations got this wrong.  (Has anyone looked
to see if all the incorrect code all descends from a common root, way
back when?)  Those implementations are as wrong as a C compiler that
skips "irrelevant junk" at the end of an integer constant.  I wouldn't
blame either the spec or the use of ASN.1.  The implementations are
just plain wrong.  There isn't even any plausible interpretation that
would make them right.  (On the one hand, they use all the data,
including the junk, in computing the signature.  On the other hand,
they ignore some of the data when extracting the digest.  It's
clearly one piece of data!)

Granted, this particular design, e=3 and all, *may* be particularly
vulnerable to mistakes.  Until we know whether this is *one* mistake
that was copied from implementation to implementation, or the same
mistake made by multiple developers, it's really premature to draw any
conclusions.  But assume that's so.  Then indeed it's prudent to avoid
e=3 - more because of the likely number of broken implementations out
there that will take forever to move out of active use than for any
other reason.  But let's not draw the wrong conclusion.  Bad code is bad
code.  The error in reasoning here is not all that different from what
happens in various kinds of attacks, where for example the length of a
contained record is marked as larger than the length of the containing
record, is not checked separately - and produces a buffer overflow.

This is also related to an error in the C library design.  When
comparing *for equality*, strcmp(s,t) - ignoring issues about possible
missing trailing NUL's - has a very simple semantics:  It compares two
*strings*.  The corresponding memcmp(s,t,n) is usually thought of as
similarly comparing two memory regions - but that's *not* what it does.
To really compare two memory regions, it would have to have accept two
memory regions as inputs - that is, have separate pointers and a lengths
to give memcmp(s,m,t,n).  As it stands, the programmer given two memory
regions is left with the task of coming up with the right value for n.
In fact, what he *should* do is first compare the two lengths and decide
"not equal" if they differ.  In practice, programmers often use the
minimum of the two lengths for n, which actually tests one region and
one leading substring of another.  Not what they had in mind - and
indeed earlier in this thread we saw exactly this produce buggy code.
(BTW, strncmp(), the fix for unterminated strings, has the same
problem:  Since it has a single maximum length, it no longer has a
simple semantics as a C string comparison function.)

| (When the spec was written, I think the thought that someone would append
| trailing garbage never cropped up, so it's never explicitly addressed).
I think you'd be hard pressed to find any spec that addresses such a
thing.  When a spec says "X is an A followed by a B", the "and nothing
else" is implied.

| >Anyway, I think we agree on the point that the spec (even version 2.1) is in
| >some point unprecise which should be considered a bug, as it can lead to
| >implementation flaws. And yes, given what we know, e=3 is a good candidate
| >for elimination :)
| 
| Yup :-).
I think you're putting the blame in the wrong place.

							-- Jerry

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