IllegalArgumentException: Invalid point compression

[GoogleCodeExporter]

java.lang.RuntimeException: Unable to create application 
de.schildbach.wallet.WalletApplication: java.lang.IllegalArgumentException: 
Invalid point
at android.app.ActivityThread.handleBindApplication(ActivityThread.java:4155)
at android.app.ActivityThread.access$1300(ActivityThread.java:130)
at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1256)
at android.os.Handler.dispatchMessage(Handler.java:99)
at android.os.Looper.loop(Looper.java:137)
at android.app.ActivityThread.main(ActivityThread.java:4747)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:511)
at 
com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:786)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:553)
at dalvik.system.NativeStart.main(Native Method)
This seems to be a regression with bitcoinj 0.12 (no reports so far for 
previous versions). It keeps the app from loading so I only see it in the 
Google Play console.

Caused by: java.lang.IllegalArgumentException: Invalid point
at org.spongycastle.math.ec.ECAlgorithms.validatePoint(ECAlgorithms.java:193)
at 
org.spongycastle.math.ec.AbstractECMultiplier.multiply(AbstractECMultiplier.java
:22)
at org.spongycastle.math.ec.ECPoint.multiply(ECPoint.java:516)
at org.bitcoinj.crypto.DeterministicKey.<init>(DeterministicKey.java:72)
at org.bitcoinj.crypto.HDKeyDerivation.deriveChildKey(HDKeyDerivation.java:135)
at 
org.bitcoinj.crypto.DeterministicHierarchy.get$63f85a4(DeterministicHierarchy.ja
va:93)
at 
org.bitcoinj.wallet.DeterministicKeyChain.initializeHierarchyUnencrypted(Determi
nisticKeyChain.java:310)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:249)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:186)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:169)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:152)
at 
org.bitcoinj.wallet.KeyChainGroup.createAndActivateNewHDChain(KeyChainGroup.java
:228)
at org.bitcoinj.core.Wallet.<init>(Wallet.java:249)
at org.bitcoinj.core.Wallet.<init>(Wallet.java:215)
at 
de.schildbach.wallet.WalletApplication.loadWalletFromProtobuf(WalletApplication.
java:296)
at de.schildbach.wallet.WalletApplication.onCreate(WalletApplication.java:130)
at android.app.Instrumentation.callApplicationOnCreate(Instrumentation.java:999)
at android.app.ActivityThread.handleBindApplication(ActivityThread.java:4152)
... 10 more

Original issue reported on code.google.com by andreas....@gmail.com on 10 Oct 2014 at 12:44

[GoogleCodeExporter]

Whoops, pasted my description into the exception. Here it is again:

This seems to be a regression with bitcoinj 0.12 (no reports so far for 
previous versions). It keeps the app from loading so I only see it in the 
Google Play console.

Original comment by andreas....@gmail.com on 10 Oct 2014 at 12:45

[GoogleCodeExporter]

Here is another one, might be related?

java.lang.RuntimeException: Unable to resume activity 
{de.schildbach.wallet/de.schildbach.wallet.WalletActivity}: 
java.lang.IllegalArgumentException: Invalid point compression
at android.app.ActivityThread.performResumeActivity(ActivityThread.java:2576)
at android.app.ActivityThread.handleResumeActivity(ActivityThread.java:2604)
at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:2090)
at android.app.ActivityThread.access$600(ActivityThread.java:130)
at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1196)
at android.os.Handler.dispatchMessage(Handler.java:99)
at android.os.Looper.loop(Looper.java:137)
at android.app.ActivityThread.main(ActivityThread.java:4747)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:511)
at 
com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(ZygoteInit.java:786)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:553)
at dalvik.system.NativeStart.main(Native Method)
Caused by: java.lang.IllegalArgumentException: Invalid point compression
at org.spongycastle.math.ec.ECCurve$AbstractFp.decompressPoint(ECCurve.java:471)
at org.spongycastle.math.ec.ECCurve.decodePoint(ECCurve.java:355)
at org.bitcoinj.core.ECKey.compressPoint(ECKey.java:178)
at org.bitcoinj.crypto.DeterministicKey.<init>(DeterministicKey.java:60)
at 
org.bitcoinj.crypto.DeterministicKey.derivePrivateKeyDownwards(DeterministicKey.
java:287)
at 
org.bitcoinj.crypto.DeterministicKey.findOrDerivePrivateKey(DeterministicKey.jav
a:283)
at org.bitcoinj.crypto.DeterministicKey.getPrivKey(DeterministicKey.java:314)
at org.bitcoinj.crypto.HDKeyDerivation.deriveChildKey(HDKeyDerivation.java:133)
at 
org.bitcoinj.crypto.DeterministicHierarchy.get$63f85a4(DeterministicHierarchy.ja
va:93)
at 
org.bitcoinj.wallet.DeterministicKeyChain.initializeHierarchyUnencrypted(Determi
nisticKeyChain.java:310)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:249)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:186)
at 
org.bitcoinj.wallet.DeterministicKeyChain.<init>(DeterministicKeyChain.java:178)
at 
org.bitcoinj.wallet.KeyChainGroup.upgradeToDeterministic$479b08b6(KeyChainGroup.
java:814)
at org.bitcoinj.core.Wallet.upgradeToDeterministic$2abffc29(Wallet.java:462)
at org.bitcoinj.core.Wallet.currentAddress(Wallet.java:372)
at org.bitcoinj.core.Wallet.currentReceiveAddress(Wallet.java:384)
at 
de.schildbach.wallet.ui.WalletAddressFragment.updateView(WalletAddressFragment.j
ava:132)
at 
de.schildbach.wallet.ui.WalletAddressFragment.onResume(WalletAddressFragment.jav
a:117)
at android.app.FragmentManagerImpl.moveToState(FragmentManager.java:878)
at android.app.FragmentManagerImpl.moveToState(FragmentManager.java:1039)
at android.app.FragmentManagerImpl.moveToState(FragmentManager.java:1021)
at android.app.FragmentManagerImpl.dispatchResume(FragmentManager.java:1816)
at android.app.Activity.performResume(Activity.java:5092)
at android.app.ActivityThread.performResumeActivity(ActivityThread.java:2566)
... 12 more

Original comment by andreas....@gmail.com on 10 Oct 2014 at 12:46

[GoogleCodeExporter]

It seems as if these two devices are affected:

ASUS Fonepad ME371MG (ME371MG)
DROID RAZR i (smi)

Original comment by andreas....@gmail.com on 10 Oct 2014 at 12:49

[GoogleCodeExporter]

That last one looks like an attempt to re-use the oldest key for upgrade is 
going wrong somehow:

            /*
             * If y is not a square, then we haven't got a point on the curve
             */
            if (y == null)
            {
                throw new IllegalArgumentException("Invalid point compression");
            }

I wonder if this occurs if you try to decompress an uncompressed key. Perhaps 
some of the oldest users of the app still have a key in their wallet that 
pre-dates the use of point compression? We introduced that ages ago, but it's 
the only explanation I can think of.

Original comment by mh.in.en...@gmail.com on 10 Oct 2014 at 1:38

[GoogleCodeExporter]

Sure, that might be the case. Wallets are migrated from day 1 (March 2011) -- 
so expect some keys still around from that era.

Original comment by andreas....@gmail.com on 10 Oct 2014 at 1:45

[GoogleCodeExporter]

The stacktrace is inside the DKC's initialization, quite a few steps after the 
old key was used to generate the entropy for the seed.

Maybe something wrong with the math on these models?

Original comment by c1.devra...@niftybox.net on 13 Oct 2014 at 3:26

[GoogleCodeExporter]

What OS version are these devices on Andreas? I wonder if they are using the 
broken BigInteger implementation that some old androids have.

Original comment by mh.in.en...@gmail.com on 13 Oct 2014 at 9:15

[GoogleCodeExporter]

The devices are all on Android 4.1 and 4.2. New on the list of affected devices:

S1

Original comment by andreas....@gmail.com on 13 Oct 2014 at 10:29

[GoogleCodeExporter]

I emailed Peter Dettman to ask if he knows what might be going on here.

Original comment by mh.in.en...@gmail.com on 13 Oct 2014 at 11:46

[GoogleCodeExporter]

Potentially relevant:

Fonepad and RAZR i are both Intel Atom.

Galaxy S1 has old OS (2.3), perhaps has that BigInteger bug.

Original comment by c1.devra...@niftybox.net on 13 Oct 2014 at 6:33

[GoogleCodeExporter]

Let's ignore the S1 -- for one it has been upgraded to Android 4.1 or 4.2 by 
the owner so the OS is inofficial. For two it's outdated hardware and will most 
likley run into resource contraints anyway.

Original comment by andreas....@gmail.com on 13 Oct 2014 at 6:41

[GoogleCodeExporter]

Java should ensure we don't have any exposure to endianness differences, a JVM 
is always big endian (which is stupid and a performance bottleneck, but it is 
what it is).

But on Android BigInteger is now implemented by OpenSSL, which is native code, 
so I wonder if perhaps Android contains a bug where the BigInteger<->OpenSSL 
glue is not reversing bytes properly at a critical point. It would not be the 
first time Android has shipped totally broken basic math code.

Original comment by mh.in.en...@gmail.com on 13 Oct 2014 at 6:50

[GoogleCodeExporter]

I got the wallet of one RAZR i user. I imported it into my Intel Atom device 
(Galaxy Tab 3) but it upgrades cleanly to HD. Maybe the issue has been fixed in 
recent Android versions.

Original comment by andreas....@gmail.com on 14 Oct 2014 at 5:16

[GoogleCodeExporter]

Hi guys. This is the first report of any problem with the new EC validation in 
1.51, so I am skeptical that the issue is in BC (SC) per se, but you certainly 
have my attention!

I think the most worrying stack trace is this one:
Caused by: java.lang.IllegalArgumentException: Invalid point
at org.spongycastle.math.ec.ECAlgorithms.validatePoint(ECAlgorithms.java:193)
at 
org.spongycastle.math.ec.AbstractECMultiplier.multiply(AbstractECMultiplier.java
:22)
at org.spongycastle.math.ec.ECPoint.multiply(ECPoint.java:516)
at org.bitcoinj.crypto.DeterministicKey.<init>(DeterministicKey.java:72)

Since the point being multiplied is the base point (G) itself (so, valid), and 
the scalar is in [0, 2^256) (inferred from ECKey.java), this should never fail, 
period. Indeed in the current code, apart from deprecated code paths, it 
shouldn't be possible to construct an invalid ECPoint at all.

So, you may ask, what use does the validatePoint call serve if the 
multiplication can't fail? Well, it does guard against implementation errors in 
BC, but that's secondary to trying to protect against silent faults/errors 
(i.e. when the underlying platform behaves unexpectedly, either from bug, 
accident, or attack).

Anyway, I think this can be resolved if we can get an example scalar value 
('priv' at DeterministicKey.java:72) for which this fails (on some platform). 
Andreas, would you be able to run some modified code to dump out any  
problematic values? In the meantime I will run a large randomized test to try 
and trigger it in a regular JVM, but I think we would have seen it in our 
existing tests already if there were an actual issue in the logic.

FYI, BigInteger is no longer used for the math internally (well, we still need 
to import/export them and test bits and size) since bitcoinj is using our 
custom curves, which use our own math routines on raw arrays. It would not be 
the first time we've seen JVM errors in tight loops, but let's wait and see.

Original comment by peter.de...@gmail.com on 15 Oct 2014 at 7:23

[GoogleCodeExporter]

Thanks Pete, Andreas: you have a wallet that failed upgrade. Obviously sharing 
the private key is a bit tricky if there is still money on it, but I'm not sure 
how else we can learn what's going on here except by sharing it with the BC 
developers.

If the private key was somehow zero, could this cause the problem? i.e. is G*0 
a valid point on the curve?

Original comment by mh.in.en...@gmail.com on 15 Oct 2014 at 8:34

[GoogleCodeExporter]

I think we can share the private key -- the wallet owner has emptied his coins. 
Still I'd like to email it directly to the person doing the investigation.

Original comment by andreas....@gmail.com on 15 Oct 2014 at 8:58

[GoogleCodeExporter]

Mike, G*0 should give INF, which in the context of just the multiplication 
would be considered a valid point, yes.

Andreas, the initial question is simply whether the same 'priv' value actually 
gives a) a repeatable error on the original platform, b) the same error on the 
JDK (for a multiplication by G), so perhaps it's better for you to just run 
that test in the first instance? If it works OK in the JDK, the problem is 
Dalvik, if not... then you'll probably have to send me the key!

Original comment by peter.de...@gmail.com on 15 Oct 2014 at 11:06

[GoogleCodeExporter]

Peter, I just mailed the private key to what I believe is your gmail address. I 
cannot say which of the two stack traces is created by this key, I suspect the 
second one because it involves an upgrade from a non-deterministic wallet.

The first stacktrace seems to represent the case where a fresh deterministic 
wallet was created. Is that correct, Mike?

Original comment by andreas....@gmail.com on 15 Oct 2014 at 11:43

[GoogleCodeExporter]

Andreas, nothing in my inbox... you'd better check the email address you used, 
should be peter.dettman@gmail.com or if you prefer, 
peter.dettman@bouncycastle.org).

Original comment by peter.de...@gmail.com on 15 Oct 2014 at 1:10

[GoogleCodeExporter]

Peter,

Oct 15 11:35:34 archon postfix/smtp[27364]: 14F902654E: 
to=<peter.dettman@gmail.com>, 
relay=gmail-smtp-in.l.google.com[2a00:1450:4013:c00::1a]:25, delay
=1.6, delays=0.17/0/0.52/0.9, dsn=2.0.0, status=sent (250 2.0.0 OK 1413372934 
ci3si5886035wib.2 - gsmtp)

Check your spam folder.

However, I'm beginning to doubt this will lead anywhere. Most likely we need to 
get hold of an affected device, in order to reproduce.

Original comment by andreas....@gmail.com on 15 Oct 2014 at 1:23

[GoogleCodeExporter]

Uh, yep, spammed, have it now.

Firstly, the priv/pub values in themselves seem fine (I'm testing on JDK 
1.8.0_25). G*priv==pub and decodePoint(pub.getEncoded(true)) == pub.

But what exactly was it you sent me? Do I need to load it as a wallet somehow 
and it's only one of the derived keys that is causing the exception? I don't 
know a whole lot about bitcoinj and was just hoping for the priv value that 
ultimately causes the exception...

I think you're probably right that you'll need the affected device, as it's 
good odds that you're looking at a VM/JIT bug.

Original comment by peter.de...@gmail.com on 15 Oct 2014 at 2:25

[GoogleCodeExporter]

I have some news. I got the Razr-i user to simply start a fresh wallet (using 
the latest bitcoinj version, so no deterministic upgrade involved) and it 
crashed the same way. I got him to send me screenshots of the exception to 
double-check we're still chasing the same issue (attached). For what I can see, 
it's the first exception listed in the description.

So it looks like the issue is not dependent on the actual data (key) used.

Original comment by andreas....@gmail.com on 15 Oct 2014 at 6:29

Attachments:

• Screenshot_2014-10-15-19-52-55.png
• Screenshot_2014-10-15-19-53-08.png

[GoogleCodeExporter]

Andreas, do you happen to know the Dalvik version involved here?

Original comment by peter.de...@gmail.com on 17 Oct 2014 at 6:04

[GoogleCodeExporter]

No, I don't. I don't even know how to look it up in the UI of the phone.

Original comment by andreas....@gmail.com on 17 Oct 2014 at 10:06

[GoogleCodeExporter]

Just the Android OS version would be a good start.

Original comment by mh.in.en...@gmail.com on 17 Oct 2014 at 11:33

[GoogleCodeExporter]

The Razr-i is running Android 4.1.2 at the moment.

Original comment by andreas....@gmail.com on 17 Oct 2014 at 2:43

[GoogleCodeExporter]

I'm out of ideas. Hardware failure, perhaps ?

Original comment by mh.in.en...@gmail.com on 17 Oct 2014 at 5:01

[GoogleCodeExporter]

This sort of thing can be painful to track down. It's certainly worth getting a 
second Razr-i device for comparison. It might not be hardware per se, but a 
misbehaving driver (e.g. 
https://code.google.com/p/android/issues/detail?id=33032). I would try 
disabling the JIT (via the app manifest?) for an extra bit of information (and 
possible platform workaround). Then I'd be looking at building a diagnostic app 
to isolate exactly where the calculation goes awry, creating a trace that can 
be compared to the same calculation on a JDK.

You may not want to take all that on as the problem seems to affect the BC (SC) 
code. OTOH that code might run fine outside of this app. I've not done much 
with Android, but I'm setting up a dev env, and will check behaviour in an 
emulator, then try and come up with a diagnostic app.

Original comment by peter.de...@gmail.com on 18 Oct 2014 at 3:34

[GoogleCodeExporter]

It's pretty clear from the Google Play statistics that this issue is not a 
hardware fault. Hardware failures can happen to any device, not just the two 
listed. I will try to get my hands on a Razr-i.

Original comment by andreas....@gmail.com on 18 Oct 2014 at 8:39

[GoogleCodeExporter]

I've got news. Intel sent me an ASUS Phonepad (firmware: 
JZ054K.WW_epad-V3.2.9-20140305) and I can reproduce this exception:

java.lang.IllegalArgumentException: Invalid point compression
E/AndroidRuntime( 2154):    at 
org.spongycastle.math.ec.ECCurve$AbstractFp.decompressPoint(ECCurve.java:471)
E/AndroidRuntime( 2154):    at 
org.spongycastle.math.ec.ECCurve.decodePoint(ECCurve.java:355)
E/AndroidRuntime( 2154):    at 
org.bitcoinj.core.ECKey.compressPoint(ECKey.java:190)
[...]

Since it happens so reliably with (hopefully) random data, I think we can 
safely say this issue is not dependent on the data used.

Peter, could you maybe provide me with a piece of code I should try? I'm afraid 
I don't know much about the internals of math/crypto implementations, as I'm 
mainly a UI guy.

Original comment by andreas....@gmail.com on 28 Oct 2014 at 1:59

• Changed title: IllegalArgumentException: Invalid point compression

[GoogleCodeExporter]

Just noticed there was another firmware update in the queue. Even 
JZ054K.WW_epad-V3.4.0-20140901 has the same issue.

Original comment by andreas....@gmail.com on 28 Oct 2014 at 2:06

[GoogleCodeExporter]

We should probably block this device at the app or play store level until the 
issue is figured out ....

Original comment by mh.in.en...@gmail.com on 28 Oct 2014 at 4:38

[GoogleCodeExporter]

Sure, I blocked the two devices.

Original comment by andreas....@gmail.com on 30 Oct 2014 at 4:17

[GoogleCodeExporter]

Andreas, sorry I didn't see the updates. I can put together some code to try 
and flush out what's wrong, but it will be still several days away I'm afraid. 
Does it need to be android-packaged or can I just leave that part to you?

Original comment by peter.de...@gmail.com on 4 Nov 2014 at 6:51

[GoogleCodeExporter]

@peter.dettman I'll do the packaging. Just throw me some lines I'd should try. 
Let's narrow down the problem to one OS/framework call or language op that 
delivers bad data.

Original comment by andreas....@gmail.com on 4 Nov 2014 at 7:57

[GoogleCodeExporter]

If I set it up to dump diagnostic messages via a stub method, can you wire that 
up to something useful, even if it's just a file to recover later?

Original comment by peter.de...@gmail.com on 4 Nov 2014 at 9:56

[GoogleCodeExporter]

I don't know what you mean by stub method. All I will do is put your code 
snippet into a bare MainActivity and let it run. Just use System.out.println() 
if you want to print something. But since we're looking at an exception here 
its probably not even needed to print something. I will compare the outcome 
with a unit test on my Desktop machine.

Original comment by andreas....@gmail.com on 5 Nov 2014 at 10:54

[GoogleCodeExporter]

I spend a good portion of my day to try and debug this.

For the invalid point compression exception, the issue is the Nat256.eq(x1, t2) 
sanity check in SecP256KFieldElement.sqrt() fails sometimes.

E.g. input value this.x = [-1449940444, -1777508345, 765743426, -1915854550, 
730352560, -1587148010, -100873720, 881702215]
The comparison is then Nat256.eq(x=[-1449940444, -1777508345, 765743426, 
-1915854550, 730352560, -1587148010, -100873720, 881702215], y=[1498468081, 
1283916794, 211637870, -2113975099, 1442155395, -1978887619, 1081164925, 
-1625167187]) so the result of sqrt() is null.

I don't know why this always happens when I freshly create a wallet and never 
when I call this method with the same input value. Its very magic to me how the 
sqrt() method works anyway.

Original comment by andreas....@gmail.com on 7 Nov 2014 at 7:55

[GoogleCodeExporter]

I suspect this is a Dalvik x86 JIT bug. If you do the computation in a tight 
loop (say do it 1000 times) and print the outputs, are they always the same?

A few years ago I went nuts debugging an issue in a system I'd built at Google, 
it was doing crypto in tight loops in Javascript. Values were hashed and then 
used as decryption keys. It worked great except in Opera, where the program 
would just die half way through. It turned out that Opera Javascript engine was 
miscompiling a bit shift in the hash function. If you ran the hash function ten 
times in a row, the answer would change after five or six iterations.

Original comment by mh.in.en...@gmail.com on 8 Nov 2014 at 2:40

[GoogleCodeExporter]

I'm seeing intermittent failures here:

https://github.com/bitcoinj/bitcoinj/blob/master/core/src/main/java/org/bitcoinj
/crypto/DeterministicKey.java#L296

on an x86 stock 4.4.4 Android emulator (Genymotion).

Perhaps the problem is more widespread.

Original comment by c1.devra...@niftybox.net on 8 Nov 2014 at 7:05