RSA is an extremely malleable primitive and can hardly be called “encryption” in the traditional sense of block ciphers. (If you disagree, try to imagine how AES could be vulnerable to full plaintext exposure to anyone who can submit a message and get a return value of “ok” or “decryption incorrect” based only on the first couple bits.) When I am reviewing a system and see the signing operation described as “RSA-encrypt the signature with the private key,” I know I’ll be finding some kind of flaw in that area of the implementation.

The entire PKCS#1 standard exists to add structure to the payload of RSA to eliminate as much malleability as possible. To distinguish the RSA primitive operation from higher-level constructs that use the RSA primitive, I use the following terminology.

RSA-Pub/Priv-Op | Perform an RSA operation using the appropriate key (exponent/modulus): data^{exp} mod n |

RSA-Encrypt | Add random padding and transform with RSA-Pubkey-Op |

RSA-Decrypt | Transform with RSA-Privkey-Op and check padding in result |

RSA-Sign | Add padding and transform with RSA-Privkey-Op |

RSA-Verify | Transform with RSA-Pubkey-Op and check padding in result, hash data, compare with hash in payload and return True if match, else False |

With that out of the way, a common need in embedded systems is secure code updates. A good approach is to RSA-Sign the code updates at the manufacturer. The fielded device then loads the update into RAM, performs RSA-Verify to be sure it is valid, checks version and other info, then applies the update to flash.

One vendor was signing their updates, but decided they also wanted privacy for the update contents. Normally, this would involve encrypting the update with AES-CBC before signing. However, they didn’t want to add another key to the secure processor since the design was nearly complete.

The vendor decided that since they already had an RSA public key in the device for signature verification, they would also encrypt the update to that key, using the corresponding private key. The “public” key was never revealed outside their secure processor so it was considered secret.

Let’s call the public/private key pair *P1* and *S1*, respectively. Here’s their new update process:

On receiving the update, the secure processor would do the inverse, verifying the signature and then decrypting the code. (Astute reader: yes, there would be a chaining problem if encrypting more than one RSA block’s worth of data but let’s assume the code update is small.)

What’s wrong? Nothing, if you’re thinking about RSA in terms of conventional crypto. The vendor is encrypting something to a key that is not provided to an attacker. Shouldn’t this be as secure as a secret AES key? Next post, I’ll reveal how the malleability of the RSA primitive allows *n* to be easily calculated.

iwant code about rsa attacks

Comment by nusiba — April 23, 2008 @ 6:41 am

RSA-Verify should be “Transform with RSA-Pubkey-Op […]”, not “RSA-Privkey-Op”.

Comment by G — December 13, 2008 @ 10:42 am

Thanks, G, I fixed this error.

Comment by Nate Lawson — December 16, 2008 @ 1:53 pm