ricmoo / GMEllipticCurveCrypto

Elliptic Curve Cryptography library for iOS (ECDSA and ECDH)
BSD 2-Clause "Simplified" License
122 stars 46 forks source link

ECDSA signature length #11

Open Gavintc opened 9 years ago

Gavintc commented 9 years ago

I'm using ecdsa secp256r1. The signature and key pairs are generated using Java. I try to verify the signature. However, it looks like verifySignature function only accept signature with length equals to 64 bytes (it throws exception "Signature must be twice the length of its curve"). But there are some overhead like ASN.1 encoding in my signature and this makes the signature length to be 71 bytes. So how to verify this signature?

ricmoo commented 9 years ago

There are some less-than-ideal-but-working-colutions here: https://github.com/ricmoo/GMEllipticCurveCrypto/issues/8

It is planned to officially accept ASN.1 encoding at some point, but I haven't gotten to it yet. The encoding does add a lot of overhead for an encryption/signing algorithm that would otherwise be so compact, but it seems everyone using Java has to deal with it, so I'll add it soon. :)

Gavintc commented 9 years ago

Thanks for your reply! In issue #8, the signature length is 72 bytes, and it's still not 64 bytes. Whenever I pass a signature with length not equal to 64 bytes, it will throw exception "Signature must be twice the length of its curve". In issue #8, it seems bpalermo has successfully verified the signature. So what if my signature is DER encoded and how to verify such a signature?

Gavintc commented 9 years ago

While it looks like I was using a wrong function... It's wired. When I pass a signature to [crypto verifySignature: forHash:], it throws exception "Signature must be twice the length of its curve". However, if I use [crypto hashSHA256AndVerifyEncodedSignature: forData:], it won't throws any exception.....

ricmoo commented 9 years ago

Try this:

NSData keyDer = your-binary-key-goes-here;
NSData *key = [keyDer subdataWithRange:NSMakeRange([keyDer length] - 64, 64)];

Basically, you just want to take the last 64 bytes, the first 8 bytes will always be the same for you. It contains a data structure that includes identifiers and whatnot, but the last item in an ASN.1 is a bit string of the signature.

ricmoo commented 9 years ago

Oh right! Sorry! I forgot I released my (basic) DER decoder which should have a selector along the lines of "blahEncodedSignature:blah"... You can use those to make you life simpler. :)

Gavintc commented 9 years ago

Thanks. One more question. The function [crypto hashSHA256AndVerifyEncodedSignature: forData:] keeps return false, but the signature is indeed a valid signature. So I check the details. I found when I generate a key pair using

GMEllipticCurveCrypto *keyCrypto = [GMEllipticCurveCrypto generateKeyPairForCurve: GMEllipticCurveSecp256r1]; NSLog(@"Length: %lu", [keyCrypto.publicKey length]);

This gives me a 33 bytes length. However, my public key length is 65 bytes. So is this the reason that I can't verify the signature?

ricmoo commented 9 years ago

Either 33 or 65 are fine. 33 bytes represent a compressed key (starts with a 0x02 of 0x03), whereas 65 is the uncompressed key (starts with a 0x04). Are you sure it is the Secp256r1 curve? Can you send me a sample private key, public key and signature?

Gavintc commented 9 years ago

The signature is "MEUCIF+U7aD6Y/qny7hALRmd2ShHQmIeSaT/KpTyQKnkFouKAiEAymuPRFDeaAIz55rj57munOo+3pUvgrrQSl9zwjoTnYM=". Public key is "BLTdfdt0SXa4XhqH7WbEytFOj/r5wxBbRH1HgVXzNb+aEJaOPAIk5wy3cT7VlY29s+f4HYNA8QBlL9ylM1M7AjI=". All are base64 encoded. I don't have the private key for now......

Gavintc commented 9 years ago

So this library does not support secp256k1?

ricmoo commented 9 years ago

Oh, no. It currently only supports the secpXXXr1 (random) curves. Are you using secp256k1? That would certainly explain why the signature isn't verifying. :)

The underlying library I use doesn't support the secp256k1 curve, however it has been updated; which has the secp256k1 curve, but drops support for the secp384r1. There is quite a bit of work to pull in these changes, but they are on the backlog, since I think the secp256k1 is far more important (especially since it is the curve bitcoin and ilk use, and I do a lot of bitcoin work).

Gavintc commented 9 years ago

Yes, I'm using secp256k1. So are you going to support this standard later on? The fact is I really can't find any good libraries supporting secp256k1 for iOS development, except compiling openssl C library by myself. So I would really appreciate it if your library can support secp256k1.

ricmoo commented 9 years ago

Yes, this is something I really want to do, I just need to set the time aside... I recommend against OpenSSL (it is slow, cumbersome and adds a lot of size/complexity for what you probably need) and if you are in a hurry, here is the library I will be pulling into mine: https://github.com/kmackay/micro-ecc. It's a C library, but it's not too hard to use if you are committed to a single curve. My library specializes in allowing the curve to be chosen at runtime. You can pretty much just compile it with the 256-bit curve selected via #defines and pull the code out of my library to convert between Foundation and C.

I would also accept a bitcoin bribe to get secp256k1 into GMEllipticCurveCrypto sooner. :)

Gavintc commented 9 years ago

Thank you so much! Your reply is very helpful. I will try to use that library, and obviously, it's not well documented as your library. Anyway, I will give it a shot and I will be glad to switch to your library whenever you finished.

Gavintc commented 9 years ago

Hi ricmoo, sorry to bother you again. When I was using the library you recommended, I got a problem. Since the length of DER encoded ECDSA signature can be 70, 71 or 72 bytes depending on the length of r and s. In other words, length of r and length of s can be either 32 bytes or 33 bytes. And they will finally sum up to exceed 64 bytes. However, the library only accept a signature length of 64 bytes. So how do you deal with it?

ricmoo commented 9 years ago

Ah yes... You will probably want to rip off all the code around here: https://github.com/ricmoo/GMEllipticCurveCrypto/blob/master/GMEllipticCurveCrypto%2Bhash.m#L150 which zero-pads the r and s value

As an aside, I'm not sure what timelines you are looking for, but I have begun a secp256k1 specific Objective-C library, but it might still be a week or so away as I have other things on the go as well.

Gavintc commented 9 years ago

My deadline is around the end of this month, but it's OK since I have made some progress of using your recommended library. You have already helped me a lot! Thank you very much!