Using ECDSA for product key
kanis
on a constant public message using ASN1::secp112r1(), and I have two
questions.
First, is calling VerifyMessage (initialized with the public keys) on
the signature and a constant public message enough to verify that the
signature represent a valid product key that can't be generated
without knowledge of the private key? I don't understand if making
the message public is a security risk, or if I need to add a hash or
something to the product key like I've seen mentioned in a couple
places.
Second, will ECDSA work with curves of fewer bits than secp112? I'd
rather use a smaller curve to get a shorter signature so the product
key isn't so long, but when I used a smaller curve generated with
Elliptic Curve Builder, I get the error "Crypto++ Error:
CryptoMaterial: this object contains invalid values" when SignMessage
is called.
Thanks, and I hope these are easy questions for the experts out there,
cause I've been having a hard time finding much information on this
subject.
Here's the test code I'm working with:
ECIESNullT< CryptoPP::ECP >::PrivateKey PrivateKey;
/*
This is the curve generated by Elliptic Curve Builder that works with
ECIESNullT< CryptoPP::ECP >::Decryptor Decryptor( PrivateKey );
but not with ECDSA< CryptoPP::ECP >::Signer signer(PrivateKey);
CryptoPP::Integer p("147088164709569533");
CryptoPP::Integer a("6094329446842148");
CryptoPP::Integer b("-57162508610850246");
CryptoPP::Integer n("147088163948218061"); // R from ECB
CryptoPP::Integer h("1"); // S from ECB, must be
<= 4
CryptoPP::Integer x("71002669261090523");
CryptoPP::Integer y("11469141678568184");
CryptoPP::AutoSeededRandomPool rng;
CryptoPP::ECP ec( p, a, b );
PrivateKey.Initialize( ec,CryptoPP::ECP::Point( x, y ), n , h );
*/
PrivateKey.AccessGroupParameters().Initialize(ASN1::secp112r1());
PrivateKey.SetPrivateExponent(CryptoPP::Integer("4127861661178866478914975717021461"));
CryptoPP::ECDSA< CryptoPP::ECP >::Signer signer(PrivateKey);
ECDSA<ECP>::Verifier verifier(signer);
// sign
byte message[] = "test";
unsigned int messageLen = sizeof(message);
SecByteBlock signature(signer.MaxSignatureLength(messageLen));
AutoSeededRandomPool rng;
unsigned int signatureLen = signer.SignMessage(rng, message,
messageLen, signature);
// verify
std::cout << "Verify: " << verifier.VerifyMessage(message, messageLen,
signature, signatureLen) << "\r\n";
Parch
and ones that do not, but basically the point of the signature scheme
is to verify who signed the message, not to conceal its contents.
ECDSA is one of those signature schemes that does not hide the
message. The signature is just appended to the message, like a real
signature at the bottom of a letter (assuming you send your snail
mail in plaintext? :-) ). ECDSA does include a hashing step, but this
does not hide the message - I think it is supposed to prevent the
usage of 'nearly identical' messages from making it easier to break
the key.
Now, when you say VerifyMessage on the signature and a /constant/
public message - there I think you have /one/ problem, which is the
constant public message. If you mean that the message never changes,
then all signatures, while each signature is different because of
random component of the signing process, there is nothing to stop
people swapping signatures. i.e. people can trade product keys. But
otherwise, yes, that is the right idea.
Also, yes, ECDSA can be made to work with smaller keys, which would be
nicer as product keys. But you are trading off security - if you cut
the signature size down by half, you are making it many orders of
magnitude easier to break by brute force.
kanis
> does not hide the message - I think it is supposed to prevent the
> usage of 'nearly identical' messages from making it easier to break
> the key.
I tested that running SignMessage on the same message over and over
again produces what look like random signatures, but it does make one
wonder if it might enable breaking the private key somehow, or if
there might be a finite number of keys that can be generated from the
same message.
> Now, when you say VerifyMessage on the signature and a /constant/
> public message - there I think you have /one/ problem, which is the
> constant public message. If you mean that the message never changes,
> then all signatures, while each signature is different because of
> random component of the signing process, there is nothing to stop
> people swapping signatures. i.e. people can trade product keys. But
> otherwise, yes, that is the right idea.
Well, I don't see how changing the message prevents key swapping,
either... Say I make the message the person's full name. They can
then just give the key to a friend and tell them to use the same full
name. The only real advantage is that maybe on the about page it says
the wrong real name, which could embarass someone into not swapping a
key or make them fear getting in trouble... I suppose it's worth it
for that effect, although since my software is a plugin, it's not
going to have an about dialog show up unless you dig into the "about
plugins" menu.
> Also, yes, ECDSA can be made to work with smaller keys, which would be
> nicer as product keys. But you are trading off security - if you cut
> the signature size down by half, you are making it many orders of
> magnitude easier to break by brute force.
I'll have to keep researching how to get that to work, then, unless
someone has a tip. It's great to know I'm finally on the right track.
> > PrivateKey.SetPrivateExponent(CryptoPP::Integer("4127861661178866478914975717021461"));
kanis
my source code after the curve I had commented out makes it work (idea
from http://www.codeproject.com/cpp/ECIESProductKey.asp?df=100&forumid=359069&exp=0&select=1780315).
But what worries me is that even though it looks like it's working,
signer.GetKey().GetPrivateExponent() returns 1, which seems
suspicious, because if I use the standard ASN1::secp112r1() curve,
signer.GetKey().GetPrivateExponent() returns a huge number. Can
anyone explain why this would be or what the Private Exponent is
supposed to represent (appears to be the value of h)?
Actually, if I just replace h with x in the call to Initialize, it
still seems to work and I get x back from the call to
signer.GetKey().GetPrivateExponent(). But x is already used in the
point G, so... what is h for? This is so confusing.
Here's the new top part of the source code:
CryptoPP::Integer p("147088164709569533");
CryptoPP::Integer a("6094329446842148");
CryptoPP::Integer b("-57162508610850246");
CryptoPP::Integer n("147088163948218061"); // R from ECB
CryptoPP::Integer h("1"); // S from ECB, must be
<= 4
CryptoPP::Integer x("71002669261090523");
CryptoPP::Integer y("11469141678568184");
a %= p; b %= p; x %= p; y %= p;
CryptoPP::ECP ec( p, a, b );
CryptoPP::ECP::Point G( x, y );
CryptoPP::ECDSA< CryptoPP::ECP >::PrivateKey PrivateKey;
PrivateKey.Initialize( ec, G, n, h );
CryptoPP::ECDSA< CryptoPP::ECP >::Signer signer(PrivateKey);
std::cout << "Private Key x = " <<
signer.GetKey().GetPrivateExponent() << "\r\n";
Jeffrey Walton
> a %= p; b %= p; x %= p; y %= p;
> ...I had commented out makes it work
This was an issue when I developed the original code. If you noticed,
ECB would generate negative values at times for the points. In a
personal correspondence, Marcel (the author of ECB) stated it was not
required.
However, per Certicom, the domain parameters are in the interval [0,
p-1]. So I brought the parameters in line with Certicom's requirement.
Reference SEC 1: Elliptic Curve Cryptography. Section 3.1.1.1,
Elliptic Curve Domain Parameters over Fp Generation Primitive.
I apologize it caused you grief.
Jeff
kanis
I was lucky enough to figure it out early on, so it wasn't a big
deal. What does bug me is that in one of your samples, you write:
PrivateKey.Initialize( ec, G, n, h );
where h = 1. According to the crypto source (http://www.cryptopp.com/
docs/ref/eccrypto_8h-source.html#l00168), this call to
PrivateKey.Initialize is implemented like this:
void Initialize(const EC &ec, const Element &G, const Integer &n,
const Integer &x)
{this->AccessGroupParameters().Initialize(ec, G, n);
this->SetPrivateExponent(x);}
so you are actually calling SetPrivateExponent(1).
Now, I can't find anywhere in the crypto docs that says what
SetPrivateExponent means, but from a couple sources like
http://www.mail-archive.com/crypto...@eskimo.com/msg03307.html I
get the impression that the private exponent IS the private key. So
it seems your code is setting a private key of 1.
After a lot of searching through the docs, I think I found the
confusion. What certicom calls "cofactor h" seems to be returned by
PrivateKey.GetGroupParameters().GetCofactor(), and it's set by
template<class EC>
class DL_GroupParameters_EC< EC > void Initialize (const EllipticCurve
&ec, const Point &G, const Integer &n, const Integer
&k=Integer::Zero()) (see http://www.cryptopp.com/docs/ref/eccrypto_8cpp-source.html#l00414
and http://www.cryptopp.com/docs/ref/class_d_l___group_parameters___e_c.html#d3bd5f1e41ae0ae5c673a7f9d96a00a8
)
So the correct way to initialize the private key is:
PrivateKey.AccessGroupParameters().Initialize(ec, G, n, h);
PrivateKey.SetPrivateExponent(CryptoPP::Integer("1234")); // This is
the private key which can have any value between 1 and n - 1, I think
When I initialize in this way,
PrivateKey.GetGroupParameters().GetCofactor() returns the value of h.
Strangely, if h is omitted, Integer::Zero() is passed to Initialize,
but PrivateKey.GetGroupParameters().GetCofactor() still returns 1
instead of 0. I tested passing h as zero and saw the same behavior,
but passing h as 2, 3, or 4 returns 2, 3, or 4.
So I think the confusion is that even though
AccessGroupParameters().Initialize( ec, G, n, h ) and
PrivateKey.Initialize( ec, G, n, x ) look very similar, the last
parameter is not the same.
Can you confirm this, and do you want to correct your example on
codeproject.com or should I add a user comment?
Parch
> either... Say I make the message the person's full name. They can
> then just give the key to a friend and tell them to use the same full
> name. The only real advantage is that maybe on the about page it says
> the wrong real name, which could embarass someone into not swapping a
> key or make them fear getting in trouble... I suppose it's worth it
> for that effect, although since my software is a plugin, it's not
> going to have an about dialog show up unless you dig into the "about
> plugins" menu.
Then don't let the user be the one to select the message...
You can generate the message programmatically, rather than letting
them choose it.
Parch
I also used ECB and found out the hard way that CryptoPP doesn't like
negative integers there. If they are less than zero, you have to
adjust them into the range [0, p-1], but looks like you've got that
sorted.
> Now, I can't find anywhere in the crypto docs that says what
> SetPrivateExponent means, but from a couple sources like
> http://www.mail-archive.com/cryptopp-l...@eskimo.com/msg03307.html I
> get the impression that the private exponent IS the private key. So
> it seems your code is setting a private key of 1.
This is correct. The exponent is the private key (hence discrete
logarithm problem). You definitely don't want your private key to be
1. Try a randomly generated value.
The cofactor is a 'group theory' thing, to do with the relative size
of the subgroup of a group. The cofactor should be small for your
subgroup and hence keyspace to be big. The minimum cofactor possible
would be 1. Because a zero cofactor makes no sense, there might just
be something in there overriding it to 1 if you put in a zero/omitting
the value.
kanis
I use a message based off some system parameters the user can't easily
modify, they're going to need to contact me to get a new key (I'd call
it an activation key at that point) whenever they upgrade to a new
system, change the operating system version, or change whatever
underlying parameters control this message. I don't want to put users
through that or even spend the time to deal with it myself.
Unless that's still not what you meant?
Jeffrey Walton
> I'd call it an activation key at that point
Here you have to be careful - Product Activation using a "phone home"
method over the Internet is patented (and not by Microsoft).
Parch
> It's a sound idea, but I'm not sure it's right for my application. If
> I use a message based off some system parameters the user can't easily
> modify, they're going to need to contact me to get a new key (I'd call
> it an activation key at that point) whenever they upgrade to a new
> system, change the operating system version, or change whatever
> underlying parameters control this message. I don't want to put users
> through that or even spend the time to deal with it myself.
>
> Unless that's still not what you meant?
There are variations on this - e.g. generate a random number when you
run the program for the first time on a system. Which has similar
problems. But if you then also linked their product key to their e-
mail account, you can set up a website for them to retrieve new
activation keys without having to bother you on the phone/email - and
also detect abuse of the system, if some email address gets used for
generating a lot of keys. I wonder if anybody has patented this... I
only have ordinary skill in the art. (Pesky overly general software
patents...) :p
Parch
> I use a message based off some system parameters the user can't easily
> modify, they're going to need to contact me to get a new key (I'd call
> it an activation key at that point) whenever they upgrade to a new
> system, change the operating system version, or change whatever
> underlying parameters control this message. I don't want to put users
> through that or even spend the time to deal with it myself.
>
> Unless that's still not what you meant?
There are variations on this - e.g. generate a random number when you
Jeffrey Walton
> There are variations on this - generate a random number ...
I believe there is some information on alternate methods. See
http://www.codeproject.com/useritems/InstallationID.asp.
Jeff