On Mon, 27 Oct 2003, Geoff Thorpe wrote:
> Hi y'all,
>
> This is a "ping -b" to anyone who has an interest in the integer math code
> in openssl. Otto and Nils had reported a few discrepencies a while back,
> and there is already a RT ticket from Otto about one aspect of this.
> However, as I wade into crypto/bn/, I finding that it's a bit of a
> pandorah's box (I would gone with the "rabbit hole" thing, but that's a
> little too fashionable lately).
I had exactly the same feeling when I looked at the crypto/bn code
while investigating the BN_add_word problem.
> My interest is a little more fundamental than the particular error cases
> that have been discussed so far - I wold like to make the API more robust
> against operations that leave BIGNUM variables in an inconsistent state.
Yeah, ever since I looked into the bn functions I have the feeling more
bugs are hidden there, and some of these bugs could have been avoided by
being more strict wrt to representation of BNs. (I also hate the use of
the letter l as a variable name, but that sure is OT).
> BTW: my definition of a consistent state for a bignum x is for it to be
> invariant under bn_fix_top(). It's a home-brewed definition for sure, but
> I think it's logical enough because of what "fix" means. IMHO
> bn_fix_top() should only be needed to recalibrate a bignum structure
> after directly manipulating bignum's data representation, *especially*
> from the point of view of API users though this seems rational for
> internal code too. Of course, there are obviously other ways for a BIGNUM
> structure to be inconsistent too, but I'm only interested in the
> relationship between the x->top index and the x->d[0..(top-1)] array-data
> because that is there we currently legitimise something I consider to be
> a bug. I've started some auditing/hacking that involves hijacking some
> existing macros (eg. bn_[fix|check]_top) and adding some others (eg.
> bn_verify_top), and in doing this, I've stumbled onto a question that I
> realise Nils had also posted some time ago, so I'll quote his version of
> it;
>
> > Another question would be if both bignum representations for '0'
> > should be considered legal, i.e. is {{0, 0}, 0, 2, 0, 0} the same as
> > {{0, 0}, 1, 2, 0, 0} (BN_is_zero returns 1 for both representations
> > of '0') ?
>
> This observation/question turns out to be quite a nutcracker. To explain,
> for some perverse reason there is a convention in openssl to accept that
> a legitimate "zero-valued" BIGNUM could either have x->top set to zero,
> or it can have x->top set to one but with the corresponding word of the
> bignum data (x->d[0]) set to zero. Anyone who has done more than one
> high-school induction proof or implemented any kind of loop algorithm
> should intuitively feel itchy about this kind of thing, and there are
> some solid reasonings against this that go beyond intuition too. The best
> generalised rule I could come up with was this; x->top should be the
> minimal number of words for its data representation, which coincidently
> happens to be a "rule" that is 1-1 with the output from bn_fix_top()
> anyway. In particular one of these two "zero" forms is the output you get
> from bn_fix_top() no matter which of the two you feed in. So in the case
> of '0', this reasoning would suggest that x->top be zero. Does anyone out
> there have some historical knowledge (SSLeay?) or some convincing
> explanations for why the the exceptional 1-word form for '0' should be
> considered acceptable?
I can imagine that intermediate results of some functions can have leading
zeroes. But any number that is exposed should be normalized (have leading
zeroes removed). That includes zero, IMO.
>
> Going on from that, this "tolerance" is the cause of quite a bit of
> complexity in crypto/bn/, so as part of this "audit" I'm wondering to
> what extent we can clean this up. The obvious issue is backwards
> compatibility with applications or libraries that have some reliance on
> this perversity. Speaking for myself, whilst I could understand some
Perversity indeed :-) BNs are supposed to be opaque. Any app relying on
the represenation is already walking on thin ice. From the bn(3) man page:
The basic object in this library is a BIGNUM. It is used
to hold a single large integer. This type should be
considered opaque and fields should not be modified or
accessed directly.
> caution from people sensitive to that, my own caution is sensitive to
> complexity and bugs in openssl itself and I think both stem rather easily
> from working around this mathematically-illogical exceptional case.
> Currently, all the bignum code needs to ensure it is robust against this
> "rule", including the exposed API macros that are used in tight-loop
> algorithm code for word-based adds, compares, etc. Read this another way:
> any elegant algorithmic code that doesn't have an ugly "if()" before or
> after it is at risk to this problem. IMHO this is not just a problem now
> for the one or two bugs spotted so far, it's always going to remain a
> maintenance problem that risks future bugs. (The "Principle of most
> surprise" anyone?) So the census I'm looking for it this: even if noone
> has any convincing explanations for *why* this alternative 1-word
> exception is tolerated, does anyone have any convincing arguments against
> us phasing it out?
Not me. Zero already is boundary case in some algorithms. Having two
representations of zero only makes things worse. Actually, there are
already 4 represenations of zero, since you can have +0, and -0. Don't
know if this has any similar consequences as the top thing.
>
> BTW: w.r.t. this "audit" (if you can call it such) ... I know some people
> will prefer to be kept in the loop about this and have a chance to
> contribute long before I start stuffing changes into cvs. Eg. anyone
> implementing their own implementations of RSA, DSA, elliptic-curve, [etc]
> or maintaining interfaces to other PKC libraries or hardware might be
> affected. Before figuring out how best to continue, I'll wait to see what
> (if anything) people have to say first. But that's also a warning - if
> you have something to say, it would be better to say it sooner than
> later. :-)
>
> All thoughts and feedback would be most welcome.
I like this. The one thing I can suggest is the usage of the new dc(1) and
bc(1) in OpenBSD -current (I found the BN_add_word bug while implementing
dc). Dc (and consequently bc) use the crypto/bn routines and might be very
well used for testing.
>
> Cheers,
> Geoff
-Otto
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
