Yubico Forum

Re: Slow RSA-2048 encryption/signing

2013-11-19T13:52:11+01:00

Hello again everyone,

The guys at Yubico have been kind enough to provide me with a second Neo to test on and everything works fine on the new one (RSA signatures with small inputs take about 1.5 seconds, they no longer hang for 30-40 seconds then return a timeout error).

The firmware version is the same (3.1.2) and I can't spot any differences in the ATR or the response to "/identify" in JCOP Tools. As far as I can tell the two Neos are identical, but one can sign just fine while the other one times out. This is with the exact same applet, same procedure to deploy, etc. It works on the new one and fails on the old one.

I wonder if this could be a hardware issue - the old unit has seen a lot more use (a lot of flash writes), but the problem appears to have something to do with the random number generator. Maybe the RNG is faulty on the old unit and the card fails to get enough secure random bytes to do its padding for the RSA signature.

Any ideas what I could try next?

Thanks again to the Yubico team for providing me with a replacement unit.

Razvan

Statistics: Posted by drazvan — Tue Nov 19, 2013 1:52 pm

Re: Slow RSA-2048 encryption/signing

2013-11-08T20:04:53+01:00

Thank you Jakob!

With your source code, running under JCOP Tools in Eclipse / Windows 7, here's my output:

Code:

cm>  /select 010203040506
 => 00 A4 04 00 06 01 02 03 04 05 06 00                ............
 (11589 usec)
 <= 90 00                                              ..
Status: No Error
cm>  /send 0001000000
 => 00 01 00 00 00                                     .....
 (15141 msec)
 <= 90 00                                              ..
Status: No Error
cm>  /send 0002000000
 => 00 02 00 00 00                                     .....
 (132184 usec)
 <= 90 00                                              ..
Status: No Error
cm>  /send 000300000104
 => 00 03 00 00 01 04                                  ......
jcshell: Error code: -6 (Card terminal error)
jcshell: Communication problems: No response after sending APDU; Unknown return code (0x8010002F) [No response after sending APDU; Unknown return code (0x8010002F)]

So the key generation works (takes about 15 seconds), the signature initialization works (132ms) but the actual signing fails (the error code appears after about 30-40 seconds).

What happens when you try it?

Thank you,
Razvan

Statistics: Posted by drazvan — Fri Nov 08, 2013 8:04 pm

Re: Slow RSA-2048 encryption/signing

2013-11-08T07:44:02+01:00

Ok - sorry for slow processing on this one. Just bringing up the stuff, filling in the blanks and get it done takes a bit of effort...

Not sure I still fully understand what the problem is here. I've done a bit of cuttin' and pastin' to make up a test program and as far as I see it, it all works as expected. See below for a reference what that test program looks like and we may use that later on to narrow down the problem.

Maybe I got something wrong here, but initializing a signature object without a valid private key does not seem to be a very good idea. Why would you do a

What device firmware do you have ? NEOs shipped actually report two different firmware versions due to the "two-layer design", with one piece of firmware and one Yubikey Javacard applet. The current device firmware version is 3.1.8 and this is what I've used for testing.

Once I now have the setup going, let's see if we can resolve it from here.

Best regards,

JakobE
Hardware- and firmware guy @ Yubico

package pkgBugTest;

import javacard.framework.APDU;
import javacard.framework.ISO7816;
import javacard.framework.Applet;
import javacard.framework.ISOException;
import javacard.security.KeyPair;
import javacard.security.KeyBuilder;
import javacard.security.Signature;

public class BugTest extends Applet
{
private KeyPair tkp;
Signature mySig;
private final short OUT_OFFS = 100;

public static void install(byte[] bArray, short bOffset, byte bLength) {
new pkgBugTest.BugTest().register(bArray, (short) (bOffset + 1),
bArray[bOffset]);
}

public void process(APDU apdu) {

if (selectingApplet()) return;

byte[] buf = apdu.getBuffer();
short len = apdu.setIncomingAndReceive();

switch (buf[ISO7816.OFFSET_INS]) {

case 0x01:
tkp = new KeyPair(KeyPair.ALG_RSA_CRT, KeyBuilder.LENGTH_RSA_2048);
tkp.genKeyPair();
break;

case 0x02:
mySig = Signature.getInstance(Signature.ALG_RSA_SHA_PKCS1, false);
mySig.init(tkp.getPrivate(), Signature.MODE_SIGN);
break;

case 0x03:
len = mySig.sign(buf, (short) 0, (short) len, buf, OUT_OFFS);
apdu.setOutgoingAndSend(OUT_OFFS, len);
break;

case 0x04:
Signature sig = Signature.getInstance(Signature.ALG_RSA_SHA_PKCS1, false);
sig.init(tkp.getPrivate(), Signature.MODE_SIGN);
len = sig.sign(buf, (short) 0, (short) len, buf, OUT_OFFS);
apdu.setOutgoingAndSend(OUT_OFFS, len);
break;

default:
ISOException.throwIt(ISO7816.SW_INS_NOT_SUPPORTED);
}
}
}

Statistics: Posted by Jakob — Fri Nov 08, 2013 7:44 am

Re: Slow RSA-2048 encryption/signing

2013-10-25T19:12:12+01:00

Anyone? This is annoying as hell, especially since it works on two other platforms that I've tried (one of them running the exact same JCOP version as the Neo).

I can try to get in touch with NXP (we are under NDA with them) to ask if this is a known issue, but can anyone else please confirm that this happens on their Neos as well? I only have one Neo, but I doubt the problem is only with my device.

Thank you,
Razvan

Statistics: Posted by drazvan — Fri Oct 25, 2013 7:12 pm

Re: Slow RSA-2048 encryption/signing

2013-10-20T22:40:23+01:00

Ok, I've narrowed it down a bit and it does appear to have something to do with the entropy / random number generation.

Basically, I can make it work by adding a dummy keypair generation right before initializing the Signature object. Something like this:

Code:

tkp = new KeyPair(KeyPair.ALG_RSA_CRT, KeyBuilder.LENGTH_RSA_2048);
tkp.genKeyPair();

right above

Code:

Signature.getInstance(Signature.ALG_RSA_SHA_PKCS1, false);

That dummy is not used, it's just generated and then dumped.

Now my guess: ALG_RSA_SHA_PKCS1 basically means (according to the JavaDoc):

Quote:

Signature algorithm ALG_RSA_SHA_PKCS1 generates a 20-byte SHA digest, pads the digest according to the PKCS#1 (v1.5) scheme, and encrypts it using RSA.

The problem is that the RSA key is 2048 bits (256 bytes) while the digest is only 20 bytes long. PKCS1 requires padding with random (if I understand correctly, it tries to pad it with 256-20-3 = 233 bytes). So it probably starts up a secure RNG and tries to generate 233 random bytes and for some reason that takes a long time or doesn't ever return. A smaller RSA key (1024 bits = 128 bytes) would only need about 105 bytes of random padding.

I suspect that generating a new key somehow tells the RNG to collect some entropy (while the signature generation does not ???).

This should be relatively easy to replicate, just don't create your keypair right before the Signature object, that will make it work. Try to create the KeyPair on install and sign in the process() method as response to a command APDU.

Any clues?

Statistics: Posted by drazvan — Sun Oct 20, 2013 10:40 pm

Re: Slow RSA-2048 encryption/signing

2013-10-19T02:05:54+01:00

Code:

 => 00 A4 04 00 08 A0 00 00 05 27 20 01 01 00
 <= 03 01 02 03 87 07 01 00 00 00 90 00 

So I guess firmware 3.1.2 ??

Razvan

Statistics: Posted by drazvan — Sat Oct 19, 2013 2:05 am

Re: Slow RSA-2048 encryption/signing

2013-10-19T00:18:31+01:00

Try to select the Yubikey Applet.

Code:

-> 00 a4 04 00 08 a0 00 00 05 27 20 01 01 00
<- 03 00 02 01 05 07 82 0f 00 00

0x030002 = Firmware 3.0.2
0x01 = Programming sequence number
0x0507 = Level from touch detector
0x82 = Mode
0x0f = Challenge-response timeout in seconds
0x0000 = Auto eject time in seconds

You might have to touch the button to be able to select this applet, or else it might return 0x6999.
See my posts here: http://forum.yubico.com/viewtopic.php?f=26&t=1197

You could also use the "ykinfo" command in ykpersonalize

Statistics: Posted by sliver — Sat Oct 19, 2013 12:18 am

Re: Slow RSA-2048 encryption/signing

2013-10-19T00:04:39+01:00

I'm not sure what firmware it's running, is there any way to tell via an APDU? I've disabled the HID part of it, it's in smartcard (APDU) only mode (can't remember what it was called officially).

Here's what the JCOP Tools say :

Code:

cm>  /atr
resetCard with timeout: 0 (ms)
--Waiting for card...
ATR=3B FC 13 00 00 81 31 FE 45 59 75 62 69 6B 65 79    ;.....1.EYubikey
    4E 45 4F 72 33 B1                                  NEOr3.
 IOCTL().
ATR: 
      IFSC = 254                 
       BWI = 4                   
       CWI = 5                   
      Hist = YubikeyNEOr3        
         T = 1                   
        FI = 1                   
        DI = 3                   
   clk/etu = 93                  
         N = 0                   
>  /identify
 => 00 A4 04 00 09 A0 00 00 01 67 41 30 00 FF          .........gA0..
 (24135 usec)
 <= 03 C1 01 38 00 00 00 00 4E 58 31 33 30 41 01 03    ...8....NX130A..
    C3 10 EA 6A 82                                     ...j.
Status: File not found
FABKEY ID:   0x03
PATCH ID:    0xC1
TARGET ID:   0x01 (smartmx)
MASK ID:     0x38 (56)
CUSTOM MASK: 00000000
MASK NAME:   NX130A
FUSE STATE:  fused
ROM INFO:    C310EA
COMBO NAME:  smartmx-m38.03.C1-NX130A

Is the firmware upgradeable on these?

Razvan

Statistics: Posted by drazvan — Sat Oct 19, 2013 12:04 am

Re: Slow RSA-2048 encryption/signing

2013-10-18T23:44:04+01:00

What firmware version is your NEO?

I have firmware 3.0.2, and when running your simple example i get

RSA 1024 : 133 ms
RSA 2048: 592 ms

Statistics: Posted by sliver — Fri Oct 18, 2013 11:44 pm

Re: Slow RSA-2048 encryption/signing

2013-10-18T13:04:52+01:00

Hi Jakob,

I've run a few more tests and here's what I found:

1. RSA-1024 works fine, it signs within a few milliseconds.
2. RSA-2048 signing almost never returns, hangs almost indefinitely
3. The key is generated (on install) like this:

Code:

MANUFACTURER_KEY = new KeyPair(KeyPair.ALG_RSA_CRT, KeyBuilder.LENGTH_RSA_2048);
MANUFACTURER_KEY.genKeyPair();

then to sign data, I do this

Code:

Signature sig = Signature.getInstance(Signature.ALG_RSA_SHA_PKCS1, false);
sig.init(MANUFACTURER_KEY.getPrivate(), Signature.MODE_SIGN);
short sl = sig.sign(buf, offs, len, buf, offs);
apdu.setOutgoingAndSend(offs, sl);
break;

I've tested this code on 3 cards - an engineering sample from NXP (running the same OS as the Yubikey, JCOP 2.4.2 R1), a microSD form factor card (running JCOP 2.4.1 R3) and the Yubikey Neo. The code works fine on the other two (signing times like 630737us), but not on the Yubikey.

4. It appears to have nothing to do with the size of the data to sign, even a 3 byte array takes forever.

Again, this is only for RSA 2048, RSA with 1024bit keys appears to work fine, it's very fast and usable.

Any ideas?

Razvan

Statistics: Posted by drazvan — Fri Oct 18, 2013 1:04 pm

Re: Slow RSA-2048 encryption/signing

2013-10-18T08:33:57+01:00

Hi Razvan,

Not sure what you mean by "incredibly slow" and exactly what algorithm you use.

The "official" figure for something like RSA signature.sign() using algorithm Signature.ALG_RSA_SHA_PKCS1 with RSA CRT and SHA-1 is about 475 ms for a 128 bytes message. I very much believe this is in line with most JCOP devices in this class and is a somewhat average figure for this type of smartcard ICs.

It may vary a bit, but it should definitely not be an order of magnitude so Please let me know if you're in this ballpark or if you're using something more "exotic" that this.

Best regards,

JakobE
Hardware- and firmware guy @ Yubico

Statistics: Posted by Jakob — Fri Oct 18, 2013 8:33 am

Slow RSA-2048 encryption/signing

2013-10-18T01:05:54+01:00

Hello everyone,

Has anyone else noticed that the RSA implementation on the Neo is incredibly slow, at least for 2048-bit keys? I have a bunch of JCOP cards here (some newer, some older than the Neo) and all of them are an order of magnitude faster at computing RSA signatures than the Neo. I could post code snippets if needed, but I have the feeling that RSA 2048 operations either do not go through the crypto accelerator or they force the use of persistent memory instead of RAM.

Any ideas?

Thank you,
Razvan

Statistics: Posted by drazvan — Fri Oct 18, 2013 1:05 am