Attacks on RSA decryption and mitigation (2024)

There are attacks on RSA involving the unpad operation. This document describes thoseattacks, whether the YubiKey and/or SDK is vulnerable, and SDK mitigations.

Chosen ciphertext attack on RSA

Suppose an attacker is able to obtain an RSA ciphertext block from unknown plaintext. Thegoal is to retrieve the plaintext of this original message.

The attacker creates a different ciphertext block mathematically related to the first. Ifthe attacker is able to somehow get the private key owner to decrypt this new block andreturn the plaintext, they can deduce the original message.

That is, there exist

 P1 (plaintext 1, the unknown) C1 (ciphertext 1, known to the attacker) P2 (known) C2' (known)(the chosen ciphertext)

If they are mathematically related (in a particular way), the attacker "can solve for P1".

Incidentally, just to be pedantic, C2' (C-two-prime, the chosen ciphertext) is not theciphertext for P2. Rather, while there is a C2 (the ciphertext for P2), theciphertext the attacker chooses is mathematically related to both C2 and C1. But it is notC2 exactly.

There are two reasons this attack generally does not succeed in the real world. One,protocols and applications are written so that results of private key operations are notreturned to outside querants. And two, even if the plaintext block were to be returned,when the chosen ciphertext is decrypted, the "unpad" operation would undoubtedly fail andan error, rather than the plaintext, would be returned. And even if the decrypted datasomehow survived the unpad operation (it looked like a properly padded block), the datareturned would be the unpadded data, not the entire block.

Nonetheless, this is the foundation of other attacks. This document describes theseattacks, when an application is susceptible (or not), and what mitigations are required.Finally, this document describes some code inside the .NET YubiKey SDK that wouldappear to be susceptible, and the mitigations employed to reduce its exposure.

❗ Note that this attack only allows the adversary to recover one message. Itdoes not threaten the private key itself.

PKCS 1 padding (aka PKCS #1 v.1.5 and P1.5)

To encrypt using RSA, each plaintext block must be numerically less than the RSA modulus.However, if the plaintext is too small, then the RSA operation is not secure. Hence, tobuild a block that is less than the modulus, but also not a small value, the block ispadded. The oldest standard padding scheme for RSA encryption is known as PKCS 1(PKCS = Public Key Cryptography Standards, and the first of those is related to RSA).

In this scheme, a block of memory or a byte array the size of the modulus is created. Itis filled this way.

00 || 02 || pad bytes || 00 || plaintext

The pad bytes are random, non-zero bytes. The standard specifies that there must be atleast 8 pad bytes. For example, if the RSA key is 1024 bits (128 bytes) and the data toencrypt is a 32-byte value (e.g. a 256-bit AES key), the block of data would be

00 || 02 || 93 random non-zero bytes || 00 || 32 plaintext bytes

This block is converted into a number and encrypted.

After decrypting the ciphertext, the private key owner will check to make sure the firstbyte is 00 and the second is 02. If not, error, don't return any plaintext.

If the first two bytes are correct, search for the first occurrence of the 00 byte. Ifthere is none, error, don't return any plaintext.

If there is a 00 byte, make sure there are at least 8 bytes of pad (i.e. the 00 appearsafter index 9). If not, error, don't return any plaintext.

If these checks all pass, return all the bytes after the first 00 byte.

Some applications and protocols are written with another check, namely, how big theunpadded data must be. For example, it's possible the encrypted data must be either 16,24, or 32 bytes (it is an AES key), or it must be 48 bytes (it is a master session key).If not, error, don't return any plaintext.

Bleichenbacher Attack

In 1998, Daniel Bleichenbacher published some results of his research, which included away to employ the chosen-ciphertext attack on RSA, even without knowing the full plaintextblock result. It relied on knowing where, in a decrypted block, the padding scheme failed.

Send the private key owner a chosen ciphertext block. The owner decrypts and then tries tounpad. When that operation fails, the owner sends a response indicating what the failurewas. That is, the error message might be, "Decryption failed, block[0] not 0." Or maybe itwas "Decryption failed, block[1] not 2". And so on.

Although the attacker does not know all the bytes of the plaintext, they do know some ofthem based on the error message.

Now send another chosen ciphertext. And another. And keep sending messages. Depending onthe private key size, thousands or millions of messages. Now based on the results, solvefor the original plaintext message.

This attack is not practical unless two conditions are met. One, the decryptor (privatekey owner) must be willing to decrypt thousands or millions of messages in a timelymanner, no questions asked (the term in cryptography is "oracle"), and two, returndescriptive error messages.

These conditions were met in the real world. An SSL server likely responds to allhandshake requests and processes them automatically. There were some implementations thatdid indeed return descriptive error messages. The target message to attack would be theone in which a session key was encrypted using the server's public key. Once the attackerknows the session key, they can read an entire session's messages.

Mitigation

To prevent the attack, SSL server code stopped returning descriptive error messages. Allerrors (failed decryption because of an unpad error or anything else) triggered a singleresponse message.

Attack updated

Without the detailed error message, Bleichenbacher then timed the responses. How long didit take for the SSL server to respond? If it was very quick, the error was the first byteof padding. If it was a little longer, the error was the second byte. And so on.

Even though the server was not explicitly returning a descriptive error code, the amountof time it was spending on the decryption was enough information to launch the attack.

The number of messages required was generally estimated to be around 1,000,000 for a2048-bit key.

Mitigation updated

Run all unpad checks, no matter what. If the first byte was wrong, note that there is anerror, then check the next byte. And so on. In the end, if there were any errors, simplyreturn the generic error message.

Not enough

Simply performing all checks is not necessarily enough. If there is a variation in theamount of time spent on the unpad operation, information is leaked. For example, if boththe first byte and the second byte are incorrect, and there is no 00 marker byte, maybethe amount of time to process is greater than if the problem is in the second byte alone.The original timing attack said a quicker time meant the error was in the first byte. Butfor some particular implementation, a quicker time could mean the error was in the secondbyte.

It's not enough to make the computation slower, it really needs to be uniform. No matterwhat the error, the time to perform the unpad operation is the same.

Another mitigation: OAEP

Another way to solve this problem is to simply not use P1.5 padding. In 1994, MihirBellare and Phillip Rogaway had developed a different padding scheme called OptimalAsymmetric Encryption Padding (OAEP). Because of the Bleichenbacher attack, standards andprotocols had incentive to adopt this existing algorithm.

With OAEP, the padded data was indistinguishable from random (to help prevent other"side-channel" attacks), and it was much more difficult to launch a Bleichenbacher attack,even if the timing was known. That is, it was still possible an implementation of OAEPunpad would leak information about where the padding went wrong, but because of how thescheme worked (comparing digests of data rather than the data itself), that informationdid not correlate to what bits in the chosen plaintext were different from the originalplaintext. Furthermore, it was much easier to write code that was more uniform anyway.

Attack on OAEP

In 2001, James Manger published his attack on OAEP. In this, the attacker needs to know ifthe data decrypted from the chosen ciphertext is greater than or less than a particularvalue (often called "B"). It will take a few thousand chosen-ciphertext messages, buteventually the attacker will be able to recover the original message.

When verifying whether unpadded data is correct, there is a check to see if the mostsignificant byte is zero or not. If it is not zero, that's an error. Furthermore, if it isnot zero, the attacker knows the result is greater than B. So if the OAEP unpad codechecks the most significant byte, and then exits immediately, that's a quick response. Inthat case, the attacker knows the result from the chosen ciphertext is greater than B. Alonger response means it is less than.

Mitigation

Once again, make sure the OAEP unpad operation performs the entire process every time, andmake the total time (error or no error) as uniform as possible.

One more mitigation

There is another possible mitigation: variable times. This would be something similar to"RSA blinding".

In order to thwart timing attacks on the RSA algorithm itself (not the padding scheme), animplementation could add some random amount of time to the process. This is called"blinding". When this happens, a quick response with one ciphertext block does notnecessarily mean that the actual computation time is less than the actual computation timeof a slow response with another ciphertext block.

Now add in the unpad operation. An attacker likely knows only how long the total RSAoperation took (RSA decryption and unpad). If there is too much variation in the RSAdecryption time, then there is no way to tell how much of the total time was RSA and howmuch was unpad.

It is also possible to build implementations of the P1.5 and OAEP unpad algorithms thatadd a variable amount of time each time it is computed.

While variable-time RSA blinding implementations are used in the real world,variable-length unpad schemes are rare.

Signing

A digital signature using RSA involves performing the padding operation, then encryptingthat result using the RSA private key. The owner of the private key does not perform theunpad operation, so the attacks listed here are not relevant.

What the attacker needs

For these timing attacks on the unpad operation, the attacker needs two things:

• An oracle, namely, the owner of the private key must be willing to decrypt thousands ormillions of messages in a timely manner, no questions asked.
• Accurate times for completion of the task.

Susceptibility of the YubiKey to these timing attacks

The YubiKey itself does not perform the unpad operation. If you call on the YubiKey todecrypt, it will perform "raw" RSA and return the still-padded result. It is theresponsibility of the calling application to unpad.

Hence, the YubiKey itself is not susceptible to this class of attack.

Susceptibility of the .NET YubiKey SDK to these timing attacks

Because an application calling on the YubiKey to decrypt will need to perform the unpadoperation, the SDK provides a class,RsaFormat, that can unpad the resultof RSA decryption.

If you use this class to unpad RSA decryption, will your application be susceptible tothese timing attacks?

The oracle requirement

A YubiKey will almost certainly not be used in some application as an oracle. That is, theYubiKey will likely not be running automatically, performing decryptions no questionsasked. Probably the only situation where this could happen is if someone wants to use aYubiKey as a substitute for an HSM providing cryptographic services for an SSL server.That is not recommended, by the way.

The most likely use case for a YubiKey performing decryption is for an individual user todecrypt messages. In that case, it is extremely unlikely that an attacker will be able toget the user to perform thousands or millions of decrypt operations in a timely manner.

The accurate time requirement

Because the most likely use case for decrypting with a YubiKey involves user interaction,including PIN entry and touch, the time for each RSA decryption is so varied it isvirtually useless.

Even though it is highly unlikely an attacker could mount an unpad timing attack on theSDK's RsaFormat class when used in conjunction with the YubiKey, we will examine theoperation's time variation.

RsaFormat

With the .NET YubiKey SDK, you have two choices for unpadding. One, use theRsaFormat class inYubico.YubiKey.Cryptography. Or two, use an alternate implementation, such as oneyou write yourself. Note that the Unpad code that the .NET Base Class Libraries use is notpublicly accessible.

The engineers at Yubico have taken care to make sure the unpadding operations followingP1.5 and OAEP are as uniform as possible. Yubico makes no guarantees that this code iscompletely immune to timing attacks. However, tests that timed how long to unpad correctversus incorrect values showed little variation. See the results below.

RsaFormat timing results

In the following tables, timing numbers are in microseconds:

0.372 microseconds = 0.000000372 seconds (372 nanoseconds, 0x000372 millisecond)14.1 microseconds = 0.0000141 seconds (14,100 nanoseconds, 0.0141 millisecond)

These are averages over several timing iterations. Where applicable, results are givenbased on the message size. For example, the baseline measurements (in the "Correct"column) are for no-error unpad operations when the encrypted data (the unpadded message)is 16, 24, 32, or 48 bytes long. For the "First byte wrong" column, the first byte was notvalid, but everything after that was correct, including the message of given length.

All timing numbers were taken on a computer with a 1.6 GHz Intel Core i5, 8th Gen chip,running Windows 10.

Start with P1.5.

1024-bit block PKCS 1 v1.5

2048-bit block PKCS 1 v1.5

These numbers indicate that there is very little variance between times based on messagesize. Secondly, there is very little variance based on error or no error. Lastly, there isvery little variance based on the type of error. For example, whether the error is anincorrect first byte, or a combination of the first three errors, the amount of time theRsaFormat method will take is very similar.

Next, let's look at OAEP.

1024-bit block OAEP with SHA-256

2048-bit block OAEP with SHA-256

Once again, we see very little variance between times based on message size. Secondly,there is very little variance based on error or no error. Lastly, there is very littlevariance based on the type of error.

The time it takes to perform OAEP is dependent on the digest algorithm chosen. The numbersabove are from timing exercises using SHA-256. The following numbers are averages whenusing the other digest algorithms.

1024-bit block OAEP with SHA-1, SHA-256, and SHA-384

2048-bit block OAEP with SHA-1, SHA-256, SHA-384, and SHA-512