{"id":1031,"date":"2014-01-12T18:43:08","date_gmt":"2014-01-12T18:43:08","guid":{"rendered":"http:\/\/warc.org.uk\/?page_id=1031"},"modified":"2014-01-13T15:08:00","modified_gmt":"2014-01-13T15:08:00","slug":"software-product-keys-as-used-in-myvna-by-dave-g8kbb","status":"publish","type":"page","link":"https:\/\/warc.org.uk\/?page_id=1031","title":{"rendered":"Software product keys as used in myVNA by Dave G8KBB"},"content":{"rendered":"

As many of the WARC members will know \u2013 because I\u2019ve bored you with talks on the subject \u2013 I have had great fun for several years writing Vector Network Analyser (VNA) software<\/a> for the most excellent N2PK VNA<\/a> by Paul Kiciak<\/a>. Most people will have heard the talk on VNAs \u2013 if sufficient have not, I\u2019m happy to give another J.<\/p>\n

Free for amateur use, there are some commercial applications supported by Ivan Makarov VE3IVM<\/a>. In order to protect the investment we\u2019ve made, I agreed to implement some product key protection. As a result, when you first run the program you see this:<\/p>\n

\"key<\/a><\/p>\n

So, how does it work? Well, not as described here. Not exactly anyway \u2013 it\u2019s very similar to this though. I\u2019m not going to say exactly how I implemented it.<\/p>\n

In this article, I\u2019ll cover the design, cryptography and implementation.<\/p>\n

Principles<\/h1>\n

What is a product key? It\u2019s a string of data that the program will accept as a valid key in order for the program to operate. However it must be constructed in such a way that someone cannot guess a valid key. Easy \u2013 make it structured in such a way that a randomly chosen string will not work. That means that the chance of any random string being tried must be unlikely to work.<\/p>\n

One way might be to use a cryptographic hash of a short message. Problem though. If anyone reverse engineers the program and discovers the structure all is lost. So we need something more sophisticated.<\/p>\n

How about using an asymmetric cipher? Public key cryptosystems have been the subject of talks at the Warrington club<\/a> before \u2013 and specifically the RSA<\/a> cryptosystem. This relies on the fact that factorisation of a large integer that is the product of two large primes is computationally expensive. This would work.<\/p>\n

Bit of a problem though. Using something like 1024 bit RSA would mean a product key of 128 bytes \u2013 way too long.<\/p>\n

So, that won\u2019t work. I think we\u2019ve not covered it in a lecture at the club yet, but a better choice would be to use Elliptic Curve cryptography. Key lengths are much shorter; for example a 256 bit EC key has roughly the same strength as 3000 bit RSA. A 160 bit curve gives roughly the same security as 1024 bit RSA. Even 160 bits is a bit big but we can reasonably choose a smaller curve given the level of security that we seek. There are many good tutorials on the internet on ECC. Wiki is good<\/a> and here is a good clear tutorial<\/a>.<\/p>\n

There was quite a good write-up of product keys on the internet that I found that taught me a lot, but it had a fundamental problem \u2013 it used ECIES<\/a> (er, don\u2019t worry, we\u2019ll explain this a bit later). You can find the write-up here.<\/a><\/p>\n

My implementation? I used a method called ECDSA<\/a> but with a few twists. Those twists I do not present here.<\/p>\n

Ok, there are limits. You can always crack the program. It needs to protect itself as far as it can.<\/p>\n

What is an elliptic curve?<\/h1>\n

Remember you maths?<\/p>\n

\"image002\"<\/a><\/p>\n

That\u2019s the equation of one. There are other forms but we\u2019ll use this one.<\/p>\n

For certain values of a and b, you might get a curve like this if you plotted it<\/p>\n

\"plot<\/a><\/p>\n

You can take two points on this curve and construct a method for \u201cadding\u201d points like this:<\/p>\n

\"plot<\/a><\/p>\n

Adding point P and Q gives point R.<\/p>\n

If you add a point to itself (Q = P+P, in other words Q=2P) that\u2019s the equivalent of \u201cdoubling\u201d the point. 2P+P is 3P and so on; we therefore have the notion of \u201cpoint multiplication\u201d.<\/p>\n

In RSA we use \u201csquare and multiply\u201d to perform exponentiation. In ECC we use \u201cdouble and add\u201d to perform point multiplication.<\/p>\n

\"plot3\"<\/a><\/p>\n

So how do we do this in cryptography?<\/p>\n

Well, we use a variant where we have integer points on the curve rather than using real numbers, and we construct it in such a way that the points we use form a finite field<\/a>. That\u2019s as far as we\u2019ll go for now on the number theory \u2013 oh and to make the maths work we also need to define the \u201cpoint at infinity\u201d.<\/p>\n

We\u2019ll use a prime field here but there are other forms. This means that all calculations are performed modulo a prime p.<\/p>\n

So what does a point look like? Well, it has an X and a Y coordinate. It is a point on a curve.<\/p>\n

And the formula for point addition? A bit messy.<\/p>\n

If you have two points X1 and X2 we can add them together to form a point X3 as follows, where x1<\/sub>,y1<\/sub> are the x and y coordinates of point X1 etc.<\/p>\n

Notice the convention? Points have x and y coordinates and are represented in upper case.<\/p>\n

So, we add X1 and X2 as follows (this is the case when the points have different x coordinates \u2013 there is a different rule for the other case).<\/p>\n

First calculate \u03bb as follows<\/p>\n

\"image006\"<\/a><\/p>\n

Then calculate<\/p>\n

\"image007\"<\/a><\/p>\n

\"image008\"<\/a><\/p>\n

Fortunately we don\u2019t have to muck about with all this as there are libraries freely available to do it.<\/p>\n

So we have a curve. It has values a and b (remember that equation above?). It has a prime number p. It also has a couple of other numbers. One is called the \u201cbase point\u201d or generator. The other is the \u201corder of the base point\u201d.<\/p>\n

What are these?<\/p>\n

The base point (G) is a point on the curve. If you add it to itself, you get another point on the curve. That is 2G. Add the basepoint again. 3G. Keep going. Eventually you get back to where you started. That should happen after a lot of operations; ideally, for a 160 bit curve, it should be pretty close to after 2160<\/sup> operations. How many times exactly? That\u2019s the \u201corder\u201d of the base point.<\/p>\n

So we have our maths. We have a curve. We can do basic mathematical operations because they form a finite field.<\/p>\n

Digital Signatures<\/h1>\n

The product keys I implemented are a form of digital signature known as the Elliptic Curve Digital Signature Algorithm (EC-DSA).<\/p>\n

To use it, first generate a private key. This is just a randomly chosen integer less than the order of the basepoint (let\u2019s call it d). The public key is a point on the curve (P) that is generated by multiplying the base point by d; in other words P = d*G. Note the convention again; P and G are points, d is an integer. \u2018*\u2019 is point multiplication.<\/p>\n

Now, suppose you want to sign a message m.<\/p>\n

Follow these steps:<\/p>\n

    \n
  1. Calculate a hash of the message e = hash(m) and truncate if needed<\/li>\n
  2. Select a random number k less than\u00a0 the order of the basepoint<\/li>\n
  3. Calculate the point on the curve (x1<\/sub>, y1<\/sub>) = k * G<\/li>\n
  4. Calculate r = x1<\/sub> mod p. If r is zero, go back to step 2<\/li>\n
  5. Calculate s = k-1<\/sup>(e + rd) mod p. If s is zero, go back to step 2<\/li>\n<\/ol>\n

    The signature is the pair (r,s). This is what I do to create a product key.<\/p>\n

    The VNA program does this to verify a signature (P is the public key that corresponds to d):<\/p>\n

      \n
    1. Check that r and s are integers between 1 and the order of the basepoint<\/li>\n
    2. Calculate e = hash(m) and truncate if needed<\/li>\n
    3. Calculate w = s-1<\/sup> mod p<\/li>\n
    4. Calculate u1<\/sub> = ew mod p and u2<\/sub> = rw mod p<\/li>\n
    5. Calculate the curve point (x1<\/sub>,y1<\/sub>) = u1<\/sub> * G + u2<\/sub> * P<\/li>\n
    6. The signature is valid if\u00a0 r\u00a0 = x1<\/sub> mod p<\/li>\n<\/ol>\n

      Don\u2019t need to code this either as again there are libraries to do it. What I did need to do however was this:<\/p>\n

        \n
      1. Make a program to generate EC keys and using those keys product keys<\/li>\n
      2. Modify the VNA program to require product keys<\/li>\n
      3. Modify the VNA program to generate activation data and require an activation key<\/li>\n
      4. Make a program to generate activation keys<\/li>\n<\/ol>\n

        And because I need to be able to generate activation keys for people on demand<\/p>\n

          \n
        1. Port the activation key program to my phone as an android app<\/li>\n<\/ol>\n

          So what are my product keys?<\/h1>\n

          Take a short message m. That message is a couple of bytes that define the permissions granted by the product key \u2013 for example it might be to permit the program to be used for a period of time, or for a limited range of features. The program is going to interpret this message. The message is signed using EC-DSA. The product key is just the concatenation of m,r,s.<\/p>\n

          How does this differ from the ECIES mentioned earlier?<\/h1>\n

          ECIES is an encryption program. Given a public key P, I can create a message that only the person that knows the private key d can read. If you used this for a product key, the private key d would need to be known by the VNA program \u2013 and the program is the thing that you distribute. Reverse engineer it and all is lost \u2013 the adversary knows the secret.<\/p>\n

          ECDSA is the other way round. To sign a message you use the private key d. The program that interprets the signature only needs to know the public key P.<\/p>\n

          Is that all there is to it?<\/h1>\n

          Well, no.<\/p>\n

          Here is one of my product keys.<\/p>\n

          58BWK-43Y4Y-YK8SI-YK5EI-EA8V6-T4NIR-KBR64<\/p>\n

          Here is another<\/p>\n

          NB4KQ-FQB8J-PR5D3-XNSVW-C7AFU-2T48N-QKQER<\/p>\n

          These are signatures of the same message. It\u2019s an evaluation key by the way, so won\u2019t be of much use. So if the message is the same, why do the first few characters differ? That\u2019s because amongst other things there is an additional layer of obfuscation added. It has been transformed by a symmetric cipher. This is just for the hell of it. An additional layer to make the hacker\u2019s job a bit harder.<\/p>\n

          Incidentally, why does it look like it does? A series of 5 letter groups with alphanumeric characters. It\u2019s called \u201cBase 32\u201d coding and is grouped if 5s to make entry easier. The binary data of the signature, m,r,s, is split into groups of 5 bits and each group of 5 bits is coded as one of 32 characters which comprise the letters in upper case and the numbers. That means 36 possible codings but we only need 32, so 4 are omitted. These are the 4 that may cause confusion 0 vs O for example.<\/p>\n

          One final twist. The final character is a checksum. It is a simple mechanism to try to avoid typing errors if someone types in the key manually to myVNA.<\/p>\n

          Is THAT all?<\/h1>\n

          Nope.<\/p>\n

          So, I supply a product key. What happens if someone publishes one on the internet? Game over as it works for everyone.<\/p>\n

          So we need a second level. It needs to be associated with a specific instance of a PC. The way this works is as follows. We read a set of identifiers for a PC \u2013 its software version, the CPU type, the amount of RAM, the type of hard drive, the MAC address of network interfaces etc. These are hashed together to generate a fingerprint of the PC.<\/p>\n

          That signature is returned to me as \u201cactivation data\u201d. I generate a second \u201cactivation key\u201d which is another EC-DSA signature on the concatenation of the product key and the activation data. That is entered into the PC to \u201cactivate\u201d it.<\/p>\n

          The activation data is a constructed data item of several fields.<\/p>\n

          The first 8 bytes of the activation data is a MAC of the product key. A MAC \u2013 Message Authentication Code \u2013 is a keyed cryptographic hash of a message. It may be calculated in many different ways \u2013 CBC-MAC<\/a>, CMAC<\/a>, etc. Pick any suitable method using any reasonable block cipher. There are also hash based algorithms that may be used such as HMAC<\/a>.<\/p>\n

          The second 8 bytes is another MAC \u2013 this time of the MAC of the product key and the identities of the PC signature components. In hindsight I wish I had reversed the order of the two 8 byte subfields \u2013 people tend to look at the start of the activation data and assume that two strings are the same when the second half is totally different.<\/p>\n

          It is also a pain to have to change the activation key when small changes are made to the hardware, so the program implements a set of weighting factors on the sub-elements. This allows scope for changes to the PC but a complete change \u2013 such as copying the data to a different PC \u2013 gets caught.<\/p>\n

          And is that secure?<\/h1>\n

          Not completely. There are ways around this lot, but they take effort. It serves its purpose \u2013 it applies a reasonable barrier.<\/p>\n

          What\u2019s the code look like?<\/h1>\n

          Here is the interface to the program I wrote to generate product and activation keys. It also supports the generation of a private and public key for both signature types. For various types of licence it will generate product keys, and for a given product key and activation data it will generate an activation key.
          \n          \"image009\"<\/a><\/p>\n

          The Android version just generates activation keys.<\/p>\n

          \"android<\/a><\/p>\n

          Most of it is basic windows\/android code. The interesting crypto bits look like this\u2026.<\/p>\n

          The library to use is the wonderful crypto++<\/a>. It provides primitives for ECDSA.<\/p>\n

          Assuming that p is the prime factor, a and b are the constants for the curve, n is the order of the subgroup and x and y are the coordinates of the base point we define the curve and private & public components thus, where sk is the value of the private key:<\/p>\n

          CryptoPP::ECP ec( p, a, b );<\/p>\n

           <\/p>\n

          CryptoPP::ECDSA<CryptoPP::ECP, CryptoPP::SHA1>::PrivateKey PrivateKey;<\/p>\n

          CryptoPP::ECDSA<CryptoPP::ECP, CryptoPP::SHA1>::PublicKey PublicKey;<\/p>\n

          \/\/ Curve Initialization<\/span><\/p>\n

          PrivateKey.Initialize( ec, CryptoPP::ECP::Point( x, y ), n, sk );<\/p>\n

          PrivateKey.MakePublicKey( PublicKey );<\/p>\n

          \/\/ create a signer and verifier<\/span><\/p>\n

          CryptoPP::ECDSA<CryptoPP::ECP, CryptoPP::SHA1>::Signer Signer( PrivateKey );<\/p>\n

          CryptoPP::ECDSA<CryptoPP::ECP, CryptoPP::SHA1>::Verifier Verifier( PublicKey );<\/p>\n

           <\/p>\n

          The keys are validated thus<\/p>\n

           <\/p>\n

          if( false<\/span> == PrivateKey.Validate( rng, 3 ) )<\/p>\n

          { throw<\/span> CString(_T(“Private Key Validation” )); }<\/p>\n

          if( false<\/span> == PublicKey.Validate( rng, 3 ) )<\/p>\n

          { throw<\/span> CString(_T(“Public Key Validation” )); }<\/p>\n

           <\/p>\n

          Signing a message is done using the Signer:<\/p>\n

           <\/p>\n

          \/\/ allocate space for signature<\/span><\/p>\n

          size_t siglen = Signer.MaxSignatureLength();<\/p>\n

          std::string signature(siglen, 0x00);<\/p>\n

          \/\/ sign<\/span><\/p>\n

          Signer.SignMessage( rng, (byte *)&Message, MessageLen, (byte*)signature.data() );<\/p>\n

           <\/p>\n

           <\/p>\n

          And so on.<\/p>\n","protected":false},"excerpt":{"rendered":"

          As many of the WARC members will know \u2013 because I\u2019ve bored you with talks on the subject \u2013 I have had great fun for several years writing Vector Network Analyser (VNA) software for the most excellent N2PK VNA by Paul Kiciak. Most people will have heard the talk on\u2026<\/p>\n

          Continue reading<\/i><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"parent":34,"menu_order":0,"comment_status":"open","ping_status":"open","template":"templates\/template-page-with-intro.php","meta":{"footnotes":""},"class_list":["post-1031","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/pages\/1031","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/warc.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1031"}],"version-history":[{"count":5,"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/pages\/1031\/revisions"}],"predecessor-version":[{"id":1063,"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/pages\/1031\/revisions\/1063"}],"up":[{"embeddable":true,"href":"https:\/\/warc.org.uk\/index.php?rest_route=\/wp\/v2\/pages\/34"}],"wp:attachment":[{"href":"https:\/\/warc.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1031"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}