Subject: Re: PPC bn_div_words routine rewrite

From: Andy Polyakov <[email-masked]>
Date: Fri, 01 Jul 2005 19:36:48 +0200

> The reason I had to redo this routine, in case anyone is wondering, is
> because ssh-keygen  segfaults when this assembly routine returns junk
> to the BN_div_word function. On a ppc, if you issue the command
> 
> ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_key -N ""
> 
> The program craps out when it tries to write the public key in ascii decimal.

If would help if you provide evidence such as debugger stack trace and 
program output. Provided description makes no sense. "seg-faults when 
routine returns junk to BN_div_word"? Seg-fault [segmentation violation] 
can occur when you write something to memory and nothing gets written to 
memory upon result return. BN_div_word does write to memory, but I fail 
to see how a bogus value could possibly trigger seg-fault. The only 
possibility is that assembler doesn't follow ABI convention and corrupts 
registers, which caller is using/expects to be preserved by callee. 
There're several PPC ABI flavors in use, but OpenSSL routines were 
designed ABI-neutral, Well, "neutrality" really means "common 
denominator for ABI specs examined at the moment of coding," so there is 
a window of opportunity that it won't be "neutral" to future ABI, but is 
it really case? That your system uses some newly designed PPC ABI? You 
never mentioned what's your system...

But you're apparently right about a bug being present in PPC assembler. 
I too have got insane [with very few significant digits] decimal 
printout of public key generated by ssh-keygen...

>>This is a rewrite of the bn_div_words routine for the PowerPC arch,
>>tested on a MPC8xx processor.

Well, suggested routine apparently sends ssh-keygen on the PPC-based 
32-bit system I have access to to an end-less loop... And (cd test; make 
test_bn) fails early in BN_sqr... And test/exptest fails miserably with 
"bad reciprocal"...

>>I initially thought there is maybe a small mistake in the code that
>>requires a one-liner change

But apparently this appears to be the case! Please verify following:

--- crypto/bn/asm/ppc.pl.orig        2004-04-28 00:05:50.000000000 +0200
+++ crypto/bn/asm/ppc.pl      2005-07-01 18:58:21.105656512 +0200
@@ -1717,7 +1717,7 @@
         li      r9,1                    # r9=1
         $SHL    r10,r9,r8               # r9<<=r8
         $UCMP   0,r3,r10                #
-       bc      BO_IF,CR0_GT,Lppcasm_div2       #or if (h > (1<<r8))
+       bc      BO_IF_NOT,CR0_GT,Lppcasm_div2   #or if (h > (1<<r8))
         $UDIV   r3,r3,r0                #if not assert(0) divide by 0!
                                         #that's how we signal overflow
         bclr    BO_ALWAYS,CR0_LT        #return. NEVER REACHED.

A.