X.509 certificate attack (small sha1 private key)

Question

I've got a X.509 certificate, created by an unknown CA. The only thing I know is that the private key is very short, so I can retrive the private key. Is there any program I can use? The used algorithm for the signature is SHA1RSA.

Answer 1

The fact that SHA1 was used is trivial; if you have the private key used to encrypt the hash digest, you can make any changes you like, recompute the digest and push it out. You don't necessarily have to break SHA1 if what you're after is the RSA private key.

By "small", how small are we talking? The largest RSA modulus ever factored (thus indicating that that key bitsize can be feasibly cracked) was 768 bits in length (232 decimal digits long), and it used the General Number Field Sieve method that is the current gold standard for RSA cracking. Most certificates have been using 1024-bit keys or better for years now (what's 1KB between friends, especially with broadband Internet?), with the current minimum being 2048 bits (considered impossible with current knowledge of the pace of technology, but possibly vulnerable to a new type of hardware or uncovered vulnerability) and 4096 bits being the gold standard (considered impossible even if a future vulnerability or quantum leap in hardware reduced cracking time complexity by half).

Also, do you know what padding was used? Vanilla RSA, without any padding scheme, is vulnerable to certain mathematical attacks, which is why nobody's used vanilla RSA for a while now; most RSA encryption is performed either with PKCS or with OAEP padding schemes which reversibly obfuscate the plaintext before encryption (making various types of known- or chosen-plaintext attacks much more difficult).

Lastly, if the CA was using such a small key size, the CA certificate that signed the one you have may well be expired (meaning cracking it is a moot point; anything you generate won't be accepted because one or more certificates in the trust chain have expired).