[android] [throwable] arithmetic error in scalar multiplication

[PaperHS]

we use Tink-Android to generate keyPair and sign our information. it work well in common case.
but there is a crash in Android device M1 E when we use

Ed25519Sign(private_key)

and we find the throwable is

   // This check is to protect against flaws, i.e. if there is a computation error through a
    // faulty CPU or if the implementation contains a bug.
    XYZ result = new XYZ(ret);
    if (!result.isOnCurve()) {
      throw new IllegalStateException("arithmetic error in scalar multiplication");
    }

https://github.com/google/tink/blob/09fc71c45dc7c4ecc7fb0df3414b0fb3a9ca52c3/java/src/main/java/com/google/crypto/tink/subtle/Ed25519.java#L626

Android version: 7.0
cpu: Helio P10
gpu: ARM Mali-T860
Tink-Android Version: 1.2.2

Is there anyone can help me ? thanks !

[thaidn]

Interesting. Can you provide the private key? The check is a defense against arithmetic errors which normally shouldn't happen.

@bleichen

[PaperHS]

@thaidn private key base64 is EvwxxA1aevceBUJGI7qXC2cM9uy0TNphICEOY3AkXdsDe1W0J9yNqg+A/OuvCEaQIwn4ps8YtGXAzptlOWKayA==，
but it work well in my mac and my android device（Sony F8132).

[shiv4nsh]

Was there a resolution on this one? We are experiencing a similar error in some cases
Though we are using it in our service running in AWS .

[bleichen]

I've added tests with the private key above to Wycheproof. So far, I'm unable to reproduce the issue. Maybe there is an old version involved.

…

On Tue, Aug 20, 2019 at 4:25 PM Shivansh Srivastava < ***@***.***> wrote: Was there a resolution on this one? We are experiencing a similar error in some cases Though we are using it in our service running in AWS . — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#224>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGH7XXBQVKUG4MFLXNZFK3QFP5HJANCNFSM4HWSL5BQ> .

[shiv4nsh]

We've updated the version and we can still see this issue. It is not happening regularly but in scale we can see it happening 3 times in over a million request. We tried to replicate this issue but couldn't. Earlier we thought that as it has happened only once and it could be a faulty CPU as stated in the comment. But it has occurred multiple times now. Can someone please help us out what might be the cause here? And how can it be resolved ?

[bleichen]

Is this deterministic? E.g. one way to determine when the bug happens is to add additional checks to the code. I.e. change the line above the place where the error is thrown // scalar by 4 bits. for (int i = 1; i < e.length; i += 2) { CachedXYT t = new CachedXYT(CACHED_NEUTRAL); select(t, i / 2, e[i]); add(ret, XYZT.fromPartialXYZT(xyzt, ret), t); } to something like this: // Add multiples of B for even indices of e. for (int i = 0; i < e.length; i += 2) { // Make a copy of ret for comparison. PartialXYZT ret_copy = new PartialXYZT(ret); CachedXYT t = new CachedXYT(CACHED_NEUTRAL); select(t, i / 2, e[i]); add(ret, XYZT.fromPartialXYZT(xyzt, ret), t); // Check for arithmetic bug: if (!new XYZ(ret).isOnCurve()) { ... dump t, i, ret_copy and ret_old } }

…

On Sat, Sep 7, 2019 at 1:59 AM Shivansh Srivastava ***@***.***> wrote: We've updated the version and we can still see this issue. It is not happening regularly but in scale we can see it happening 3 times in over a million request. We tried to replicate this issue but couldn't. Earlier we thought that as it has happened only once and it could be a faulty CPU as stated in the comment. But it has occurred multiple times now. Can someone please help us out what might be the cause here? And how can it be resolved ? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#224>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGH7XRO4SXWZ7FHZJMT3O3QILVHLANCNFSM4HWSL5BQ> .

[thaidn]

@shiv4nsh so you got this exception even on AWS?

Could you please provide us with the message, the signature, and the private key that cause the error?

[shiv4nsh]

Hey guys @thaidn , @bleichen,
I was able to reproduce this error and this is deterministic. We still don't know when it occurs exactly.
We are using tink via Nimbus as internally it uses tink for Ed25519 , so while signing the jwt we found this error.
We have two examples
ClaimsOne : {"aud":"urn:bamtech:service:token","subject_token_type":"urn:bamtech:params:oauth:token-type:device","nbf":1568619669,"grant_type":"urn:ietf:params:oauth:grant-type:token-exchange","iss":"urn:bamtech:service:token","context":"eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzUxMiJ9.eyJzdWIiOiJjNzEwZGEyNi05ZTBkLTQ2ZmMtYjUxMy02NGVlZjcwNDdjMWUiLCJhdWQiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOnRva2VuIiwibmJmIjoxNTY4NjE5NTQ4LCJpc3MiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOmRldmljZSIsImV4cCI6MjQzMjYxOTU0OCwiaWF0IjoxNTY4NjE5NTQ4LCJqdGkiOiIyMmZlMzBiZi00N2MyLTQzZmQtYmNjNC00ZjkwYjliMWMwNmMifQ.hM4i_OG4XwpL16Pa4xRzYM41NzzHvqqnnq6jOwi73Mi2rIQgxKba_u9kDBYwn-AYcwzpjXzCrUEOXF5TKy7pUg","exp":1569224469,"device":{"id":"c710da26-9e0d-46fc-b513-64eef7047c1e","platform":"browser"},"iat":1568619669,"jti":"f28ccd7e-ab67-4014-be60-b5b4e55d5b0a"}
JwtHeader: {"kid": "b171ba2b-65f0-4893-8d61-d1c1fe5fb38a","alg": "EdDSA"}
ClaimsTwo: {"aud":"urn:bamtech:service:token","subject_token_type":"urn:bamtech:params:oauth:token-type:device","nbf":1568207926,"grant_type":"urn:ietf:params:oauth:grant-type:token-exchange","iss":"urn:bamtech:service:token","context":"eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzUxMiJ9.eyJzdWIiOiI3OTg3NDI4My0wMTFiLTQ4NGItYWYyNy0xZDRjY2E2MTE4M2MiLCJhdWQiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOnRva2VuIiwibmJmIjoxNTY4MjA3NjM4LCJpc3MiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOmRldmljZSIsImV4cCI6MjQzMjIwNzYzOCwiaWF0IjoxNTY4MjA3NjM4LCJqdGkiOiJjM2JkY2QxZi1hNGZmLTQyZDAtYTBhMS1hYzM3ZmE0M2IxYzcifQ.hHXzb4K0RZusc9MreuqYcK9yTSNcYKrvm4XRUJya-xUyNpeYqJyQlWplTshoCmbRu1GiDfHZPLBVNP43EnS9EQ","exp":1568812726,"device":{"id":"79874283-011b-484b-af27-1d4cca61183c","platform":"browser"},"iat":1568207926,"jti":"0b980b86-fbf2-4b1c-83b5-4717476e40a9"}
JwtHeader: {"kid": "b171ba2b-65f0-4893-8d61-d1c1fe5fb38a","alg": "EdDSA"}

In both the cases we had the same key signing the tokens. Here is the private key:
{"keys":[{"kty":"OKP","d":"gVBhCsO-MI01NXGetjd8ubD7Im1j9DJz0Cn6pZ9xLEI","use":"sig","crv":"Ed25519","kid":"888f041e-6480-43d1-b08d-353894deac68","key_ops":["sign","verify"],"x":"k6Tk-8mdaNoRolqLQyr4jpixlul9pXO2jkNf-GlzwQI","alg":"EdDSA"}]}
We needed some time to revoke these keys from our platform hence the delay as we are exposing it out here.
Please let me know if you need anything from my side.

[thaidn]

Thanks a lot. Is it possible to share a code snippet or a unit test that triggers the error?

[shiv4nsh]

Sure. you can use the following code to recreate this error:
We are using the following versions of tink:1.2.2 and nimbus-jose-jwt:7.8

import com.nimbusds.jose.crypto.{Ed25519Signer, Ed25519Verifier, MACVerifier}
import com.nimbusds.jose.jwk._
import com.nimbusds.jose.jwk.gen._
import com.nimbusds.jose.{JWSAlgorithm, JWSHeader}
import com.nimbusds.jwt.{JWTClaimsSet, SignedJWT}

object TinkBug extends scala.App {
  def run()= {
    val claims = JWTClaimsSet.parse(
      """{"aud":"urn:bamtech:service:token","subject_token_type":"urn:bamtech:params:oauth:token-type:device","nbf":1568207926,"grant_type":"urn:ietf:params:oauth:grant-type:token-exchange","iss":"urn:bamtech:service:token","context":"eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzUxMiJ9.eyJzdWIiOiI3OTg3NDI4My0wMTFiLTQ4NGItYWYyNy0xZDRjY2E2MTE4M2MiLCJhdWQiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOnRva2VuIiwibmJmIjoxNTY4MjA3NjM4LCJpc3MiOiJ1cm46YmFtdGVjaDpzZXJ2aWNlOmRldmljZSIsImV4cCI6MjQzMjIwNzYzOCwiaWF0IjoxNTY4MjA3NjM4LCJqdGkiOiJjM2JkY2QxZi1hNGZmLTQyZDAtYTBhMS1hYzM3ZmE0M2IxYzcifQ.hHXzb4K0RZusc9MreuqYcK9yTSNcYKrvm4XRUJya-xUyNpeYqJyQlWplTshoCmbRu1GiDfHZPLBVNP43EnS9EQ","exp":1568812726,"device":{"id":"79874283-011b-484b-af27-1d4cca61183c","platform":"browser"},"iat":1568207926,"jti":"0b980b86-fbf2-4b1c-83b5-4717476e40a9"}"""
    )

    val octetKeyPair = OctetKeyPair.parse(
      """{"kty":"OKP","d":"gVBhCsO-MI01NXGetjd8ubD7Im1j9DJz0Cn6pZ9xLEI","use":"sig","crv":"Ed25519","kid":"888f041e-6480-43d1-b08d-353894deac68","key_ops":["sign","verify"],"x":"k6Tk-8mdaNoRolqLQyr4jpixlul9pXO2jkNf-GlzwQI","alg":"EdDSA"}"""
    )
    val signer = new Ed25519Signer(octetKeyPair)

    val signedJwt = new SignedJWT(
      new JWSHeader.Builder(JWSAlgorithm.EdDSA)
        .keyID(octetKeyPair.getKeyID)
        .build,
      claims
    )
    signedJwt.sign(signer)
    signedJwt.serialize()
  }
}
TinkBug.run()

[dhpiggott]

@thaidn, just as an extra data point, the failure rate we've seen over the last two weeks is 1 failure per ~35,000,000 signing operations. So it's happening rarely, but often enough to be an issue.

[dhpiggott]

One more data point (although this one isn't a huge surprise, it seemed worth confirming): changing the input by e.g. regenerating the JWT ID and then retrying the signing call results in success.

[thaidn]

Cool, thanks for the all the info. We're investigating!

[thaidn]

Just an update, we can reliably reproduce it now. Still haven't identified the root cause, but this looks bad :(.

[sophieschmieg]

We spend the afternoon debugging, and found the issue: the isOnCurve check did not reduce the coefficients before comparing.

The good news is that this isn't a vulnerability, it merely means our test to check that our math was correct was a bit overeager. Fix will be out soon.

[thaidn]

This should be fixed at HEAD and will be included in 1.3.0 release. We may also backport it to 1.2.3.

[thaidn]

@chuckx Charles, what do you think about backporting this to 1.2.3?

[dhpiggott]

I meant to say before - thank you for the quick investigation and fix. We're looking forward to a 1.2.3 or 1.3.0 release - and happy to contribute help if there's a way we can do that (e.g. preparing a backport to 1.2.3?).

[dhpiggott]

Although we have a mitigation in place in our own code for this, we'd really like to upgrade to a release that includes this fix. Can I help with getting a 1.2.3 or 1.3.0 release out?

[chuckx]

Thanks for reaching out. We've been slowly working through an unfortunately long series of issues with our build/test/repository tooling.

I'm attempting to publish 1.3.0-rc2 today (which is the reason for the burst of pull request activity... getting changes integrated in anticipation of cutting a new release branch).

Barring any surprises, the final release 1.3.0 release should follow a week or so later.

Regarding making a patch release of the 1.2 branch (i.e. 1.2.3), that is made a bit more complicated due to the the same build tooling issues (i.e. we'd need to cherry pick changes to replicate the Bazel version pinning approach we've taken).

At this point, I'm prioritizing getting 1.3.0 moving along, since it's overdue and cleanly cherry-picking to 1.2 is complicated due to its age (particularly for the iOS release artifacts, which relies on an internal workflow and is its own can of worms).

[dhpiggott]

Ah, thanks @chuckx, that makes sense! I can see 1.3.0-rc2 is out now. We may try that ahead of 1.3.0 itself.

[chuckx]

FYI, we're working through an issue that affects Tink-Android inc 1.3.0-rc2 (see #289). As mentioned in that issue, we're working through integrating the necessary dependency upgrades to fix the issue.

We'll put together another release candidate to verify things are in working order before finalizing the release.

[dhpiggott]

Thanks @chuckx. We updated to 1.3.0-rc2 and have been using it in production for five days now - and we've not seen any recurrences of this issue. We'll update to newer release candidates/releases as they become ready too.

[thaidn]

1.3.0-RC3 is out. It should work as well as 1.3.0-RC2.