Linux Kernel RSA Signature Verification crypto_akcipher_verify() output

Question

I'm currently developing a kernel module where I'm performing RSA signature verification. My module is targeted at the 4.4 kernel so I decided to use the lower level akcipher API. I've been using the current implementation of public_key_verify_signature as a guide. My approach is:

1. Allocate a crypto_akcipher struct: *tfm = crypto_alloc_akcipher("rsa", 0, 0);
2. Allocate an akcipher_request struct: req = akcipher_request_alloc(*tfm, GFP_KERNEL);
3. Set the public key for the request: err = crypto_akcipher_set_pub_key(*tfm, data, len);
4. Place the received signature into a scatterlist and set it as an argument for the akcipher_request with: akcipher_request_set_crypt(req, &src, &dst, sig->s_size, MAX_OUT);
5. Finally make the call to crypto_akcipher_verify(req) which should calculate the expected digest
6. Compare the expected digest to the received digest to verify the signature

I'm currently at a point where I believe I'm using the API correctly but the output of crypto_akcipher_verify isn't conforming to the way it's used in the newer public_key_verify_signature example. Which is confusing me, because it seems to output part of the correct digest.

For example when a properly signed request is received I get the following results:

Expected Digest:
e52bed356dcbf8e4b3c1458ac3e4cb49e77512e6

Computated outbuf:
01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003015300906052b0e03021a05000408e52bed356dcbf8e4

The last 8 bytes of the computed outbuf is the first 8 bytes of the expected 20 byte digest. But the rest of the outbuf appears to be junk. (Although it is consistent every time, it's always 0x01 followed by lots of 0xffs and finally 003015300906052b0e03021a05000408 before the last 8 bytes). Here is the chunk of code responsible for the call to crypto_akcipher_verify(req):

// Init completion
init_completion(&(res.completion));

// Put the data into our request structure
memcpy(inbuf, sig->s, sig->s_size);
sg_init_one(&src, inbuf, sig->s_size);
sg_init_one(&dst, outbuf, MAX_OUT);
akcipher_request_set_crypt(req, &src, &dst, sig->s_size, MAX_OUT);

// Set the completion routine callback
// results from the verify routine will be stored in &res
akcipher_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG |
                  CRYPTO_TFM_REQ_MAY_SLEEP, op_complete, &res);

// Compute the expected digest
err = wait_async_op(&res, crypto_akcipher_verify(req));

if(err) {
    printk(KERN_INFO "[!] Digest computation failed %d\n", err);
    kfree(inbuf);
    kfree(outbuf);
    return err;
}

printk(KERN_INFO "\nComputation:\n");
hexdump(outbuf, req->dst_len);

/* Do the actual verification step. */
if (req->dst_len != sig->digest_size ||
    memcmp(sig->digest, outbuf, sig->digest_size) != 0) {
    printk(KERN_INFO "[!] Signature verification failed - Key Rejected: %d\n", -EKEYREJECTED);
    printk(KERN_INFO "[!] Sig len: %d   Computed len: %d\n", sig->digest_size, req->dst_len);
    kfree(inbuf);
    kfree(outbuf);
    return -EKEYREJECTED;
}

Any help or pointing in the right direction would be appreciated. Sorry if this post isn't extremely concise.

Answer 1

As @Maarten suggested above. What I was seeing was the PKCS1 v1.5 encoding. From the RFC, the padding looks like:

EM = 0x00 || 0x01 || PS || 0x00 || T.

Where PS is:

"PS consisting of emLen - tLen - 3 octets with hexadecimal value 0xff. The length of PS will be at least 8 octets."

And the DER encoding "T" at the end for SHA1 is (I'll switch to SHA256 as suggested above):

SHA-1:   (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.

The best way to parse this padding in newer kernels is using the "pkcs1pad(rsa,SHA256)" type when calling crypto_alloc_akcipher. Then rsa_verify will parse the padding for you. Unfortunately since I'm trying to port this across a few kernel versions I had to look at an older method and referenced the old rsa_verify routine.

In the end my SHA256 EMSA PKCS#1 v1.5 parsing code looks like:

static const u8 RSA_digest_info_SHA256[] = {
    0x30, 0x31, 0x30, 0x0d, 0x06, 0x09,
    0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01,
    0x05, 0x00, 0x04, 0x20
};

typedef struct RSA_ASN1_template {
    const u8 * data;
    size_t size;
} RSA_ASN1_template;

RSA_ASN1_template sha256_template;

// Derived from https://github.com/torvalds/linux/blob/db6c43bd2132dc2dd63d73a6d1ed601cffd0ae06/crypto/asymmetric_keys/rsa.c#L101
// and https://www.rfc-editor.org/rfc/rfc8017#section-9.2
// thanks to Maarten Bodewes for answering the question on Stackoverflow
// https://stackoverflow.com/questions/49662595/linux-kernel-rsa-signature-verification-crypto-akcipher-verify-output
static char *pkcs_1_v1_5_decode_emsa(unsigned char * EM,
                        unsigned long  EMlen,
                        const u8 * asn1_template,
                        size_t asn1_size,
                        size_t hash_size) {

    unsigned int t_offset, ps_end, ps_start, i;

    if (EMlen < 2 + 1 + asn1_size + hash_size)
        return NULL;    

/* Decode the EMSA-PKCS1-v1_5
 * note: leading zeros are stripped by the RSA implementation in older kernels
 * so   EM = 0x00 || 0x01 || PS || 0x00 || T
 * will become EM = 0x01 || PS || 0x00 || T.
 */
#if LINUX_VERSION_CODE < KERNEL_VERSION(4,8,0)
    ps_start = 1;
    if (EM[0] != 0x01) {
        printk(" = -EBADMSG [EM[0] == %02u]", EM[0]);
        return NULL;
    }
#else
    ps_start = 2;
    if (EM[0] != 0x00 || EM[1] != 0x01) {
        printk(" = -EBADMSG [EM[0] == %02u] [EM[1] == %02u]", EM[0], EM[1]);
        return NULL;
    }
#endif

    // Calculate offsets
    t_offset = EMlen - (asn1_size + hash_size);
    ps_end = t_offset - 1;

    // Check if there's a 0x00 seperator between PS and T
    if (EM[ps_end] != 0x00) {
        printk(" = -EBADMSG [EM[T-1] == %02u]", EM[ps_end]);
        return NULL;
    }

    // Check the PS 0xff padding 
    for (i = ps_start; i < ps_end; i++) {
        if (EM[i] != 0xff) {
            printk(" = -EBADMSG [EM[PS%x] == %02u]", i - 2, EM[i]);
            return NULL;
        }
    }

    // Compare the DER encoding T of the DigestInfo value
    if (crypto_memneq(asn1_template, EM + t_offset, asn1_size) != 0) {
        printk(" = -EBADMSG [EM[T] ASN.1 mismatch]");
        return NULL;
    }

    return EM + t_offset + asn1_size;

}

And the verification function that calls it:

// Verify a recieved signature
int verify_sig_rsa(akcipher_request * req, pkey_signature * sig) {

    int err;
    void *inbuf, *outbuf, *result = NULL;
    op_result res;
    struct scatterlist src, dst;
    crypto_akcipher *tfm = crypto_akcipher_reqtfm(req);
    int MAX_OUT = crypto_akcipher_maxsize(tfm);


    inbuf = kzalloc(PAGE_SIZE, GFP_KERNEL);

    err = -ENOMEM;
    if(!inbuf) {
        return err;
    }

    outbuf = kzalloc(MAX_OUT, GFP_KERNEL);

    if(!outbuf) {
        kfree(inbuf);
        return err;
    } 

    // Init completion
    init_completion(&(res.completion));

    // Put the data into our request structure
    memcpy(inbuf, sig->s, sig->s_size);
    sg_init_one(&src, inbuf, sig->s_size);
    sg_init_one(&dst, outbuf, MAX_OUT);
    akcipher_request_set_crypt(req, &src, &dst, sig->s_size, MAX_OUT);

    // Set the completion routine callback
    // results from the verify routine will be stored in &res
    akcipher_request_set_callback(req, CRYPTO_TFM_REQ_MAY_BACKLOG |
                  CRYPTO_TFM_REQ_MAY_SLEEP, op_complete, &res);

    // Compute the expected digest
    err = wait_async_op(&res, crypto_akcipher_verify(req));

    if(err) {
        printk(KERN_INFO "[!] Digest computation failed %d\n", err);
        kfree(inbuf);
        kfree(outbuf);
        kfree(result);
        return err;
    }

    // Decode the PKCS#1 v1.5 encoding
    sha256_template.data = RSA_digest_info_SHA256;
    sha256_template.size = ARRAY_SIZE(RSA_digest_info_SHA256);
    result = pkcs_1_v1_5_decode_emsa(outbuf, req->dst_len, 
             sha256_template.data, sha256_template.size, 32);

    err = -EINVAL;
    if(!result) {
        printk(KERN_INFO "[!] EMSA PKCS#1 v1.5 decode failed\n");
        kfree(inbuf);
        kfree(outbuf);
        return err;
    }

    printk(KERN_INFO "\nComputation:\n");
    hexdump(result, 20); 

    /* Do the actual verification step. */
    if (crypto_memneq(sig->digest, result, sig->digest_size) != 0) {
        printk(KERN_INFO "[!] Signature verification failed - Key Rejected: %d\n", -EKEYREJECTED);
        kfree(inbuf);
        kfree(outbuf);
        return -EKEYREJECTED;
    }
    
    printk(KERN_INFO "[+] RSA signature verification passed\n");
    kfree(inbuf);
    kfree(outbuf);
    return 0;
}

If anybody wants to reference the complete code, it can be found here.

Answer 2

You've performed raw or textbook RSA decryption. What you are looking at is the hash + a padding known as PKCS#1 v1.5. This is also defined in PKCS#1 v2.0 onwards for backwards compatibility (it is still considered secure, even though it is deterministic).

So have a look at PKCS#1 v2.2, 8.2.2 step 3, where it is explained that you have to build the same structure yourself and then compare. Note that 9.2 contains some helpful shortcut for creating the structures in the notes.

Finally: SHA-1 is not considered secure anymore for signature generation / verification. Upgrade ASAP!