site hangs if a particular hash is entered in wallet details tab

[dooglus]

If you enter this hash into the wallet details tab, your browser hangs indefinitely:

848b39bbe4c9ddf978d3d8f786315bdc3ba71237d5f780399e0026e1269313ef

It appears that Barrett.prototype.reduce() is looping forever (or at least for a very long time) here:

while (x.compareTo(this.r2) < 0) x.dAddOffset(1, this.m.t + 1);

This was first reported on reddit.

[dooglus]

I see that changing:

    this.reducer = new Barrett(this.q);

to:

    this.reducer = new Classic(this.q);

stops it hanging, and gives the same addresses for the one other test I did.

I don't know what 'Barrett' is, or how 'Classic' differs from it, but at least I've pinpointed the error.

I also see that changing the same line to:

    this.reducer = new Montgomery(this.q);

also stops it hanging, but comes up with a different pair of addresses.

[dooglus]

After looking into this further it appears that the problem is with BigInteger.prototype.modInverse - it sometimes returns a negative number.

At the end of the function it checks twice to see if the result is negative and if so adds m to the result. But after 2 checks it just gives up and maybe returns a negative number:

    if (d.signum() < 0) d.addTo(m, d); else return d;
    if (d.signum() < 0) return d.add(m); else return d;

In the example that fails, z is cc61934972bba029382f0bef146b228ca15d54f7e38b6cd5f6b382398b7a97a8

Before the signum() checks, d is -2376e112b22dbdfb5697b6db51460f74291ca9307fbcd1e5920316e67b19da8dc

After adding m to it the first time, d is -1376e112b22dbdfb5697b6db51460f74291ca9307fbcd1e5920316e68b19dacad

After adding m a second time, d is -376e112b22dbdfb5697b6db51460f74291ca9307fbcd1e5920316e69b19db07e

And that is the value that is returned.

We need to add m a third time to get a positive value, c891eed4dd24204a9684924aeb9f08bd6e356cf80432e1a6dfce91954e624bb1.

How about this for a fix?

diff --git a/bitaddress.org.html b/bitaddress.org.html
index 3286482..e10f87a 100644
--- a/bitaddress.org.html
+++ b/bitaddress.org.html
@@ -3859,8 +3859,8 @@ exports.init();
        }
        if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
        if (d.compareTo(m) >= 0) return d.subtract(m);
-       if (d.signum() < 0) d.addTo(m, d); else return d;
-       if (d.signum() < 0) return d.add(m); else return d;
+       while (d.signum() < 0) d.addTo(m, d);
+       return d;
    };

[dooglus]

I just googled "HAC 14.61", a string found in the comment just before the definition of modInverse(). I found a page from "BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic" which provides the end of the algorithm:

(See also this TeX document).

Note that it ends with two while loops, to make sure the returned value isn't too high or too low.

There's some text following the algorithm saying that only "a couple" of adds or subtracts are required. Maybe that wasn't meant to be taken literally:

It would probably be best to put the d.subtract() into a loop too, in case we ever need more than one subtraction to get the result in range. So:

diff --git a/bitaddress.org.html b/bitaddress.org.html
index 3286482..0e02ee5 100644
--- a/bitaddress.org.html
+++ b/bitaddress.org.html
@@ -3858,9 +3858,9 @@ exports.init();
            }
        }
        if (v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO;
-       if (d.compareTo(m) >= 0) return d.subtract(m);
-       if (d.signum() < 0) d.addTo(m, d); else return d;
-       if (d.signum() < 0) return d.add(m); else return d;
+       while (d.compareTo(m) >= 0) d.subTo(m, d);
+       while (d.signum() < 0) d.addTo(m, d);
+       return d;
    };

[dooglus]

I ran a bunch of tests, found that sometimes 5 additions or 3 subtractions are needed. Found also that only 37 of 30 million tests would have failed in the existing implementation - so it's about a 1 in a million chance of hitting this bug.

See cryptocoinjs/bigi#25 (comment)

[pointbiz]

@dooglus thank you for the report and investigation. Looks like there is some code here I can use:
cryptocoinjs/bigi#26

Edit: I see the diff above. Thx.

[dooglus]

Yes. I'm pretty sure they used the diff I pasted at the end of #132 (comment), and added a test case.

[pointbiz]

I've created a pull request to fix this issue here:
#136

@dooglus @jprichardson @dcousens can you guys have a look?

@dooglus would you consider making a test related to your comment here?
https://github.com/cryptocoinjs/bigi/pull/26/files#r72317237

[pointbiz]

Fixed with pull #136