Generate weak X509 certificate

Question

I need to generate weak certificate for CTF challenge using RSA and small modulus so it's factorable. It should be about 64 bits.

I've tried to generate that using OpenSSL as I would the normal one, but it forbids creating certificate with modulus lower than 512 bits for security reasons. So I've changed the source files of OpenSSL so it doesn't checks the bit length and recompiled that again. I was then able to create private key using smaller modulus, but trying to create certificate using that key (or new small one) evoked new error which I don't fully understand. I even wanted to evade the OpenSSL problem at all using Python, but that just showed that it uses OpenSSL too and had exactly same problems.

Generating small private key:

$ openssl genrsa -out acn.pem 64
-----BEGIN PRIVATE KEY-----
MFQCAQAwDQYJKoZIhvcNAQEBBQAEQDA+AgEAAgkAlz0xJ3uUx5UCAwEAAQIIR1Zs
1Wo4EQECBQDHPJNVAgUAwlPjQQIFAKqNunkCBClt4QECBHlHx1Q=
-----END PRIVATE KEY-----

Generating certificate:

$ openssl req -key acn.pem -new -out domain.csr
...
140561480598848:error:04075070:rsa routines:RSA_sign:digest too big for rsa key:../crypto/rsa/rsa_sign.c:100:
140561480598848:error:0D0DC006:asn1 encoding routines:ASN1_item_sign_ctx:EVP lib:../crypto/asn1/a_sign.c:224:

I found that this thread could be helpful as I could even choose my own numbers, but the method didn't worked for me:

How to Generate rsa keys using specific input numbers in openssl?

Here's sample certificate from PicoCTF. I would like to create similar one.

You don't need a stupidly small RSA key to be factorable; factoring 512 bits costs only a few dollars. Google "factoring as a service". — dave_thompson_085, Apr 08 '22 at 19:06
@dave_thompson_085 Yep, I know it's easily doable, but that's not what I need for my CTF challenge, thanks anyway :) — Misoslav, Apr 09 '22 at 20:34

bartonjs · Accepted Answer · 2022-04-09T20:17:14.900

I need to generate weak certificate for CTF challenge using RSA and small modulus so it's factorable. It should be about 64 bits.

It's impossible to do that as a self-signed certificate, because proper RSA signing can't work with keys that small.

RSA-SSA-PKCS1_v1.5 is the shortest structured RSA signature padding, and it's structured as (per https://datatracker.ietf.org/doc/html/rfc8017#section-9.2):

DigestInfo ::= SEQUENCE {
    digestAlgorithm AlgorithmIdentifier,
    digest OCTET STRING
}

The shortest possible encoding for that structure is 9 bytes... and that's with a 0-byte hash algorithm:

30 07 // SEQUENCE (7 content bytes)
   30 03 // digestAlgorithm: SEQUENCE (3 bytes)
      06 01 00 // OBJECT IDENTIFIER 0.0 ({itu-t(0) recommendation(0)})
      // omit implicit NULL
   04 00 // digest (empty)

So, with our empty hash we need to keep going:

If emLen < tLen + 11, output "intended encoded message length too short" and stop.

emLen is the length of the modulus (in bytes) and tLen is the length of our encoded structure (9 bytes+).

That makes 20 bytes (160 bits) the shortest possible RSA key to do anything that might stand a chance of being regarded as an RSA signature... which produced a pointless signature (since everything collides under a 0-bit hash).

If you are comfortable stomping on a 1-byte OID for your CTF, your RSA key modulus would need to be 20 bytes + the length of the intended hash (in bytes). Since there's no 1-byte OID that identifies an existing hash algorithm (and no defined hash algorithm for use with certificates that's that small), no existing easy-to-use tool can do this for you.

You could invent a new form of RSA signature padding, of course, using something like a 60-bit hash processed directly with your 64-bit key. That'll require even further work on your part.

You're basically reduced to using a DER writer (or writing your own) to hand-craft a certificate.

Here's sample certificate from PicoCTF. I would like to create similar one.

That certificate is not self-signed. It has a 2048-bit certificate signature, from RSA-SSA-PKCS1_v1.5 with MD2. So while it describes a short RSA key (53 bit modulus) it was signed with something "proper". If that's what you're after, the general flow would be something like

Create a normal self-signed cert
Create your small RSA key
Build a new cert, signed by the first cert, containing the small RSA key.

It's hard to encode a CSR for the small key (because it can't self-sign the request), but maybe there's a way to get openssl req -new to do something other than self-sign, which would allow skipping the intermediate CSR. (Or use library tools like .NET's CertificateRequest, or OpenSSL's APIs instead of their CLI tool, or whatever.)

`openssl req -new` can't, nor can anything that produces a valid PKCS10 CSR, but you can create the CSR for a dummy usable key (at least 250 bits or so, but might as well do 512 since it's going to be ignored) then create a cert for the subject in the CSR but a different key with `openssl x509 -req -CA cacert -CAkey cakey -force_pubkey new_subject_pubkey`. That's not programming or development, though. — dave_thompson_085, Apr 08 '22 at 19:07

Generate weak X509 certificate

1 Answers1