Monthly Archives: March 2009 - Page 2

WordPress Plugin Version Checks

Posted by on March 8, 2009 No comments

I recently noticed that in certain cases WordPress was not providing notifications that an upgrade was available for my plugins. This, naturally, irritated me since I define myself by how many downloads I receive per day.1 So, to regain my self-esteem I decided to dig a bit to find the root cause.2

To determine if a plugin is updated WordPress sends a list of installed plugins and their version numbers to a script (update-check) hosted on api.wordpress.org. While the source code for this script is not publicly available, it almost certainly uses PHP’s version_compare function to determine when a plugin has changed. Accordingly, I did some tests with some of the version numbers of Fidgetr to see what was going on…

Version Comparison Tests

0.32 > 0.4
0.32 > 0.6.1
0.32 < 0.41
0.32 < 1.0
0.32 < 0.51
0.51 < 1.0

This is just a small subset, but you can see that version_compare expects the x.x.x format and does not handle x.xx properly. Since I have done quite a few Fidgetr releases using the x.xx versioning there are potentially hundreds of outdated installations not receiving proper version updates.

Due to this issue, the next revision of Fidgetr will be 1.0 since updating the major version corrects the problem. I would prefer not to call it 1.0 without a big update, but ensuring that all of Fidgetr’s users can obtain proper updates takes precedence.

Hopefully documenting this here will prevent some headaches for other plugin developers.

  1. This is a lie. It’s actually downloads per week. I don’t have fine enough time resolution for per day monitoring. ↩
  2. It seemed like a better idea than eating 5 boxes of Thin Mints…although that was a close second. ↩

Generating (Very) Large Primes

Posted by on March 7, 2009 3 comments

Have you ever wondered how big the “large primes” that RSA encryption is based on really are? What exactly does a “1024-bit” key mean anyway? And if the difficulty of RSA is partially based on factoring large numbers, how do we create these large primes without determining primality via factorization?

The easiest way to demonstrate these concepts is with a simple script, so let’s take a look at a large random number generator I wrote1 using Python. As is typical for this blog, you’ll note that the random numbers are not cryptographically secure. To make these examples simple I don’t want to introduce external dependencies, but please keep that issue in mind for any serious applications of the code presented here.

import random
import math
import sys
 
def rabinMiller(n):
     s = n-1
     t = 0
     while s&1 == 0:
         s = s/2
         t +=1
     k = 0
     while k<128:
         a = random.randrange(2,n-1)
         #a^s is computationally infeasible.  we need a more intelligent approach
         #v = (a**s)%n
         #python's core math module can do modular exponentiation
         v = pow(a,s,n) #where values are (num,exp,mod)
         if v != 1:
             i=0
             while v != (n-1):
                 if i == t-1:
                     return False
                 else:
                     i = i+1
                     v = (v**2)%n
         k+=2
     return True
 
def isPrime(n):
     #lowPrimes is all primes (sans 2, which is covered by the bitwise and operator) 
     #under 1000. taking n modulo each lowPrime allows us to remove a huge chunk 
     #of composite numbers from our potential pool without resorting to Rabin-Miller
     lowPrimes =   [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
                   ,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179
                   ,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269
                   ,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367
                   ,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461
                   ,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571
                   ,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661
                   ,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773
                   ,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883
                   ,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
     if (n >= 3):
         if (n&1 != 0):
             for p in lowPrimes:
                 if (n == p):
                    return True
                 if (n % p == 0):
                     return False
             return rabinMiller(n)
     return False
 
def generateLargePrime(k):
     #k is the desired bit length
     r=100*(math.log(k,2)+1) #number of attempts max
     r_ = r
     while r>0:
        #randrange is mersenne twister and is completely deterministic
        #unusable for serious crypto purposes
         n = random.randrange(2**(k-1),2**(k))
         r-=1
         if isPrime(n) == True:
             return n
     return "Failure after "+`r_` + " tries."
 
print generateLargePrime(1024)

This code is very slow, but does not represent an entirely naïve approach.2  To generate a prime we first create a random integer in the range (2k-1,2k), then the following rules are applied:

  1. The number (n) must be >=3.  While 2 is a prime number, for our purposes we have no interest in numbers less than 3.
  2. Do a bitwise and (n&1).  If the result is not 0 then we know the number is even and can throw it out.
  3. Check that n%p is 0 (in other words, that n is not divisible evenly by p) for all primes <1000.  This check will eliminate a large quantity of composite numbers and prevent the expense of the next test.
  4. Finally we reach the core test: Rabin-Miller.  This algorithm, if it returns true, states that there is a 75% chance that the number is prime (for the randomly chosen basis a).  To obtain a 2-128 chance that the number is not prime, we must repeatedly run the Rabin-Miller test choosing different number bases. Since each iteration of the test increases our probability by a power of 2 we must iterate 64 times to reach this confidence level.

 
If the number passes all these tests it is returned as a valid prime number. Of course, if you don’t trust the output from this script you can always check it with openssl…

openssl prime 7337488745629403488410174275830423641502142554560856136484326749638755396267050319392266204256751706077766067020335998122952792559058552724477442839630133
8C18E5DC98684E2A15B84535635A95C4A192B73B40A780AB4CB0C58BDB9C31EF970C3AC6D804712B830FB6F1B140693A251E989F89B687EBA62781AD031D5135 is prime

 Click for an example of an 8192-bit prime created with the generateLargePrime() function. You can also check out a 1024-bit prime as well. 1024-bit keys are the minimum size recommended for end entity certificates using RSA (SSL certificates) at this time.3

Of course, a large prime is nice, but it isn’t necessarily an RSA prime. Look for another entry soon explaining the additional restrictions imposed by RSA.

  1. This code is based on the pseudocode provided in Practical Cryptography. ↩
  2. Generation of a 1024-bit prime using this script takes 5-10 seconds, whereas OpenSSL takes 0.1-0.2 seconds. ↩
  3. NIST guidelines suggest migration to 2048-bit keys by 31 Dec 2010) ↩

Re-Signing An Expired CA Certificate

Posted by on March 5, 2009 No comments

On rare occasions you may find yourself with a self-signed internal CA that has expired while you are still using certificates issued from the CA. One potential solution to this problem is to self-sign a new cert with identical fields using the private key from the old certificate.1

You can fill in almost all the fields using the interactive prompt, but to ensure maximum compatibility be sure every field matches exactly. You will also need to set the serial number of the certificate via the -set_serial parameter (openssl takes this argument in decimal form, not hex)2.

openssl req -new -x509 -key previousprivatekey.pem -set_serial 0000 -out newroot.cer

You now have a new root certificate that will work with your previously issued certificates!

  1. In general this is very bad practice, but this article presupposes that you recognize this and it is still necessary. ↩
  2. If you fail to set the serial identically Microsoft OSes will chain the certificate correctly but OpenSSL will fail. ↩