Yubico Forum

...visit our web-store at store.yubico.com
It is currently Tue Jan 30, 2018 6:24 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next
Author Message
PostPosted: Fri Oct 18, 2013 1:05 am 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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


Top
 Profile  
Reply with quote  

Share On:

Share on Facebook FacebookShare on Twitter TwitterShare on Tumblr TumblrShare on Google+ Google+

PostPosted: Fri Oct 18, 2013 8:33 am 
Offline
Site Admin
Site Admin

Joined: Wed May 28, 2008 7:04 pm
Posts: 263
Location: Yubico base camp in Sweden - Now in Palo Alto
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


Top
 Profile  
Reply with quote  
PostPosted: Fri Oct 18, 2013 1:04 pm 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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


Top
 Profile  
Reply with quote  
PostPosted: Fri Oct 18, 2013 11:44 pm 
Offline

Joined: Sat Jan 05, 2013 7:52 pm
Posts: 7
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


Top
 Profile  
Reply with quote  
PostPosted: Sat Oct 19, 2013 12:04 am 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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


Top
 Profile  
Reply with quote  
PostPosted: Sat Oct 19, 2013 12:18 am 
Offline

Joined: Sat Jan 05, 2013 7:52 pm
Posts: 7
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


Top
 Profile  
Reply with quote  
PostPosted: Sat Oct 19, 2013 2:05 am 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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


Top
 Profile  
Reply with quote  
PostPosted: Sun Oct 20, 2013 10:40 pm 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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?


Top
 Profile  
Reply with quote  
PostPosted: Fri Oct 25, 2013 7:12 pm 
Offline

Joined: Mon Apr 08, 2013 3:50 pm
Posts: 15
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


Top
 Profile  
Reply with quote  
PostPosted: Fri Nov 08, 2013 7:44 am 
Offline
Site Admin
Site Admin

Joined: Wed May 28, 2008 7:04 pm
Posts: 263
Location: Yubico base camp in Sweden - Now in Palo Alto
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);
}
}
}


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 13 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group