452008 - TM: SRP in Clipperz crypto library fails when JIT (TraceMonkey) is enabled.

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Marco Fabbri]

User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1a2pre) Gecko/20080823021533 Minefield/3.1a2pre
Build Identifier: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1a2pre) Gecko/20080823021533 Minefield/3.1a2pre

When the JIT (javascript.options.jit.content) is on, the authentication process on Clipperz.com (SRP) fails, also the card decryption process fails if yet, with JIT off, logged in (ERROR: Error while decrypting data), also 5 test cases of the SRP test suite ( http://clipperzlib.svn.sourceforge.net/viewvc/clipperzlib/trunk/javascript.crypto.library/tests/js/tests/Clipperz/Crypto/SRP.html?revision=2 ) in Clipperz crypto library fail ( http://sourceforge.net/projects/clipperzlib ). 

From running the test suite with firebug on, (the outer for-loop, line1379-1397, in) Montgomery Multiplication in BigInt.js ( http://clipperzlib.svn.sourceforge.net/viewvc/clipperzlib/trunk/javascript.crypto.library/src/js/Clipperz/Crypto/BigInt.js?revision=2&view=markup ) misbehaves when JIT is on.

Reproducible: Always

Steps to Reproduce:
1. Enable JIT (javascript.options.jit.content) via about:config
2. Try login on https://www.clipperz.com/beta

Actual Results:  
Login Failed

Expected Results:  
Login Successful

javascript.options.jit.content;true

Comment 1

[Marco Fabbri]

Montgomery moltiplication in BigInt.js makes heavy use of a global variable sa

lines 202-214 in BigInt.js
//the following global variables are scratchpad memory to
//reduce dynamic memory allocation in the inner loop
t=new Array(0);
ss=t;       //used in mult_()
s0=t;       //used in multMod_(), squareMod_()
s1=t;       //used in powMod_(), multMod_(), squareMod_()
s2=t;       //used in powMod_(), multMod_()
s3=t;       //used in powMod_()
s4=t; s5=t; //used in mod_()
s6=t;       //used in bigInt2str()
s7=t;       //used in powMod_()
T=t;        //used in GCD_()
sa=t;       //used in mont_()

Upon setting a breakpoint inside the loop in mont_() in BigInt.js (e.g. on line 1380) mont_() works fine; once the breakpoint is disabled/removed and the loop lines1379-1397) gets executed for a few (n > 10, n can be possibly smaller, didn't try yet) times in a row the value stored in sa gets wrong. 

Number of calls, when running SRP test suit, for a few functions differs significantly with JIT ON/OFF (e.g. mont_() 1968/2313 ON/OFF) see http://spreadsheets.google.com/ccc?key=pHnHcZ1gltyRLpiyscveMXA&hl=en .

Comment 2

[Marco Fabbri]

For completeness' sake the code for Montgomery Multiplication is:

lines 1354-1413
//do x=x*y*Ri mod n for bigInts x,y,n, 
//  where Ri = 2**(-kn*bpe) mod n, and kn is the 
//  number of elements in the n array, not 
//  counting leading zeros.  
//x must be large enough to hold the answer.
//It's OK if x and y are the same variable.
//must have:
//  x,y < n
//  n is odd
//  np = -(n^(-1)) mod radix
function mont_(x,y,n,np) {
  var i,j,c,ui,t;
  var kn=n.length;
  var ky=y.length;

  if (sa.length!=kn)
    sa=new Array(kn);

  for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n
  //this function sometimes gives wrong answers when the next line is uncommented
  //for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y

  copyInt_(sa,0);

  //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large keys
  for (i=0; i<kn; i++) {
    t=sa[0]+x[i]*y[0];
    ui=((t & mask) * np) & mask;  //the inner "& mask" is needed on Macintosh MSIE, but not windows MSIE
    c=(t+ui*n[0]) >> bpe;
    t=x[i];

    //do sa=(sa+x[i]*y+ui*n)/b   where b=2**bpe
    for (j=1;j<ky;j++) { 
      c+=sa[j]+t*y[j]+ui*n[j];
      sa[j-1]=c & mask;
      c>>=bpe;
    }    
    for (;j<kn;j++) { 
      c+=sa[j]+ui*n[j];
      sa[j-1]=c & mask;
      c>>=bpe;
    }    
    sa[j-1]=c & mask;
  }

  if (!greater(n,sa))
    sub_(sa,n);
  copy_(x,sa);
}

Comment 3

[Marco Fabbri]

The bug still bites on today's builds (linux and windows): numbers (the same on all platforms) got different from yesterday's build.

builds tested:

Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1a2pre) Gecko/20080825020949 Minefield/3.1a2pre

Mozilla/5.0 (Windows; U; Windows NT 5.2; en-US; rv:1.9.1a2pre) Gecko/20080824031931 Minefield/3.1a2pre

Comment 4

[Marco Fabbri]

Attachment: A more confined test case (involving only the montgomery multiplication routine) than the whole SRP authentication scenario

RESULT and EXPECTED value differ if JIT is enabled.

Comment 5

[Marco Fabbri]

Attachment: A more confined test case (involving only the montgomery multiplication routine) than the whole SRP authentication scenario runnable through the stand-alone js console

This test case (that is the same of the html version) doesn't fail when run through the js console, also when the JIT is enabled (-j).

Comment 6

[Marco Fabbri]

Produced a more confined test case ( https://bugzilla.mozilla.org/attachment.cgi?id=335401 and - js only for js console - https://bugzilla.mozilla.org/attachment.cgi?id=335402 ) involving only Montgomery Multiplication. 

The test case fails only when executed inside the browser. On the console runs fine and gets also optimized, about 4x performance boost-up with JIT enabled.

Comment 7

[Robert Sayre]

The expected numbers in these tests look wrong to me. I checked this in a number of JS impls, and their results all match our JIT.

Comment 8

[Robert Sayre]

This is fixed now, and I added a test for it:

http://hg.mozilla.org/tracemonkey/rev/472d905980df

Comment 9

[Bob Clary [:bc] (inactive)]

/cvsroot/mozilla/js/tests/js1_5/Regress/regress-452008.js,v  <--  regress-452008.js
initial revision: 1.1

http://hg.mozilla.org/mozilla-central/rev/f0e9fd501e63