Stop using RSA
Hi% username%!
RSA is the first widely used asymmetric cryptography algorithm that is still popular in the industry. It is relatively simple at first glance. RSA encryption and signature can be counted on a piece of paper, which students often do in lab work.
But there are just a huge number of nuances, without which your implementation of RSA can even be cracked by a child.
For some reason, people still consider RSA a good algorithm. But in fact, the scope for a shot in the foot with the implementation of RSA is extremely huge. Weak parameters are difficult to verify, if not impossible. And the poor performance of the algorithm encourages developers to use risky ways to increase it.
')
Worse, padding oracle attacks that were invented more than 20 years ago are still relevant today.
Even if in theory it is possible to implement RSA correctly, in practice this “feat” is almost impossible to accomplish. And the vulnerabilities that have been constantly arising for decades now only confirm this.
A few words about the RSA algorithm
If you know how RSA works, you can skip this part.
RSA is a public key cryptosystem that has two applications.
The first is encryption, when Alice publishes her public key and Bob, knowing it, can encrypt a message that only Alice can read, decrypting it with her private key.
The second is a digital signature that allows Alice to sign the message with her private key so that everyone can verify this signature with her public key.
Both algorithms have minor details, so we will simply call them RSA.
To start working with RSA, Alice needs to choose two prime numbers p and q , which together form a group of numbers modulo N = pq . Then Alice needs to choose the open exponent e and the secret d such that . In essence, e and d should be mutually simple.
Once these parameters are selected, Bob can send a message to Alice M, calculating . Alice can then decrypt the message by calculating .
Digital signature is exactly the opposite. If Alice wants to sign the message, she calculates the signature. which Bob can verify by making sure the message is
That's all, this is the main idea. We'll return to the Padding oracles later, but for now let's see what can be done if the RSA parameters are selected incorrectly.
Beginning of the End
For RSA, you need to select quite a few parameters. Unfortunately, innocent at first glance, the methods of their choice can harm security. Let's go through each of them and see what unpleasant surprises await you.
Generation of prime numbers
RSA security is based on the fact that having a large number N , which is the product of two primes p and q , it is difficult to decompose N into prime factors without knowing p and q . Developers are responsible for selecting the primes that make up the RSA module. This process is extremely slow compared to generating keys for other cryptographic protocols, where it is enough just to select a few random bytes. Therefore, instead of generating a truly random prime number, developers often try to create numbers of a certain shape. It almost always ends badly. There are many ways to choose prime numbers so that factoring N is simple. For example, p and q must be globally unique. If p or q is ever reused in other RSA modules, then both multipliers can be easily calculated using the GCD algorithm. Bad random number generators make this scenario quite plausible, and studies have shown that approximately 1% of TLS traffic in 2012 was subject to such an attack.
Moreover, p and q must be chosen independently of each other. If p and q share approximately half of their most significant bits, then N can be calculated using the Fermat method. In fact, even the choice of a simplicity testing algorithm can have security implications. Perhaps the most widely advertised attack is the ROCA vulnerability in RSALib, which affected many smart cards, trusted platform modules, and even Yubikey keys. Here, when generating keys, only prime numbers of a certain form are used to speed up calculations. The primes generated in this way are trivial to detect using cunning tricks of the theory of numbers. Once the weak system has been recognized, the special algebraic properties of prime numbers allow an attacker to use the Coppersmith method to decompose N.
It should be borne in mind that in none of these cases, the generation of primes in this way is not an obvious fact, leading to a complete system failure. That's because the insignificant number-theoretic properties of primes have a significant impact on the security of RSA. Waiting for an ordinary developer to navigate this mathematical minefield seriously undermines security.
Secret exhibitor d
Because the use of a large private key has a negative effect on the decryption and signature time, developers have an incentive to choose a small d , especially in cases of devices with low power consumption, such as smart cards. However, an attacker can restore the private key when d is less than the 4th root of N. Instead, developers should choose a large d value, so that the Chinese remainder theorem can be used to speed up the decryption. However, the complexity of this approach increases the likelihood of minor implementation errors that can lead to key recovery.
You will say that usually when you initialize RSA you first generate a module, use a fixed open exponent, and then choose a secret one?
Yes, it prevents attacks with a small secret exponential, if you always use one of the recommended open exhibitors e .
Unfortunately, it also assumes that developers will actually do this. In the real world, developers often do strange things, for example, they first choose d , and then they consider e .
Open exhibitor e
As in the case of the secret exponent, the developers want to use small open exhibitors to save on encryption and verification of signatures. Usually, Fermat primes are used in this context, in particular, e = 3, 17, and 65537.
Despite the fact that cryptographers recommend using 65537, developers often choose e = 3, which leads to many vulnerabilities in the RSA cryptosystem.
(Here the developers used e = 1, which actually does not encrypt plaintext at all.)
When e = 3 or a similar size, a lot can go wrong. Small open exhibitors are often combined with other common errors that allow an attacker to decipher certain ciphertexts or factor N.
For example, the Franklin-Reuter attack allows an attacker to decrypt two messages that are linked by a known, fixed distance. In other words, suppose Alice sends Bob to only “buy” or “sell.” These messages will be associated with a known value and will allow the attacker to determine which of them mean “to buy” and which “to sell” without decrypting the message. Some attacks with a small e can even lead to key recovery.
If the open exhibitor is small (not just 3), an attacker who knows a few bits of the secret key can recover the remaining bits and break the cryptosystem. Although many of these e = 3 attacks on RSA can be fixed by padding, developers who implement RSA themselves often forget to use it.
RSA signatures are also vulnerable to small public exhibitors. In 2006, Bleichenbacher discovered an attack that allows attackers to forge arbitrary signatures in many RSA implementations, including those used in Firefox and Chrome. This means that any TLS certificate from a vulnerable implementation can be forged. This attack takes advantage of the fact that many libraries use a small public exponent and do not do simple alignment checks when processing RSA signatures. The Bleichenbacher’s attack on the signature is so simple that it is included in many exercises in cryptography courses.
Parameter selection is a difficult task.
A common feature of all these attacks on parameters is that the total number of possible options for parameters is much larger than the number of safe options.
It is assumed that the developers themselves will manage this complex selection process, since everything except the open exponent must be generated during initialization.
There are no easy ways to check the reliability of parameters . Instead, developers need a serious mathematical base, the presence of which should not be expected from ordinary employees. Although using RSA with alignment can save you with the wrong parameters, many still prefer not to.
Padding Oracle attack
As we already figured out above, simply using out-of-the-box RSA does not quite work. For example, the RSA scheme described in the introduction will create identical ciphertexts if the same plaintext has ever been encrypted more than once. This is a problem because it will allow the attacker to know the content of the message from the context, without being able to decrypt it. This is why we need to align messages with several random bytes. Unfortunately, the most widely used alignment scheme, PKCS # 1 v1.5, is often vulnerable to the so-called padding oracle attack.
The initial attack on PKCS # 1 v1.5 was discovered back in 1998 by Daniel Bleikhanbacher. Despite the fact that she is over 20 years old, today she continues to be relevant for many systems. Modern versions of this attack often include an additional oracle, a bit more complicated than the one that Bleichanbacher originally described, for example, the response time of the server or the performance of any downgrading of the protocol version in TLS. One particularly shocking example was the ROBOT attack, which was so terrible that the research team was able to sign messages with the secret keys of Facebook and PayPal. Some may argue that this is not really the fault of the RSA - the basic math is fine, people just messed up an important standard a few decades ago. The fact is that we already then , since 1998, had a standard alignment scheme with strict safety evidence, OAEP. But almost no one uses it. Even when this happens, it is generally known that OAEP is difficult to implement, and it is often vulnerable to Manger's attack, which is another oracle attack that can be used to recover plaintext.
The fundamental problem here is that alignment is necessary when using RSA, and this additional complexity opens up a lot of room for attacks on a cryptosystem. The fact that one bit of information, “whether the message was correctly aligned,” can have such a large security impact that it makes the development of secure libraries almost impossible. TLS 1.3 no longer supports RSA, so we can expect fewer such attacks in the future.
But as long as developers continue to use RSA in their own applications, Padding Oracle attacks will continue to occur.
What to do?
People often prefer to use RSA because they consider it to be conceptually simpler than the tangled DSA protocol or elliptic curve cryptography (ECC). But while RSA is more intuitive, it lacks fool protection.
First of all, a common misconception is that the elliptic is very dangerous, because choosing a bad curve can negate everything. It is true that the choice of a curve has a great effect on safety, but one of the advantages of using ECC is that the choice of parameters can be made publicly. Cryptographers make parameter choices for you, so developers just need to generate random data bytes for use as keys. Developers can theoretically build an ECC implementation with terrible parameters and cannot verify the presence of such things as incorrect curve points, but they, as a rule, do not. The likely explanation is that the mathematics behind the ECC are so complex that very few people feel confident enough to realize it. In other words, this fear forces people to use libraries created by cryptographers who know their business. RSA, on the other hand, is so simple that it can be (poorly) implemented in an hour.
Secondly, any key matching based on the Diffie-Hellman algorithm or a signature scheme (including elliptic curve variants) does not require alignment and, therefore, is completely resistant to Padding Oracle attacks. This is a serious victory, given that RSA has a very long track record of trying to avoid this class of vulnerabilities.
We recommend using Curve25519 for key exchange and ed25519 for digital signatures. Encryption must be performed using the ECIES protocol, which combines the exchange of ECC keys with a symmetric encryption algorithm. Curve25519 was designed to completely prevent classes of attacks that can happen to other curves, and it is also very fast. Moreover, it is implemented in many libraries, such as libsodium, which is equipped with easy-to-read documentation and is available for most languages.
Stop using RSA. Seriously.
(Twilio still uses RSA keys)
(Travis CI still uses 1024 bit keys and does not allow them to be replaced)
RSA was an important milestone in the development of secure communications, but the past two decades of cryptographic research have made it obsolete. Algorithms on elliptic curves for both key exchange and digital signatures were standardized in 2005 and have since been integrated into intuitive and resistant to misuse libraries, such as libsodium. The fact that RSA is still widely used these days indicates both a mistake on the part of cryptographers due to an inadequate description of the risks inherent in RSA, and on the part of developers who overestimate their ability to successfully deploy it. The security community should start thinking of this as a herd problem - although some of us may be able to navigate the extremely dangerous process of setting up or implementing RSA, exceptions make it clear to developers that RSA is still relevant in some way. Despite the many warnings and warnings on StackExchange and GitHub README, not many people believe that they will spoil the RSA, and therefore they continue to act recklessly. Ultimately, your users will pay for it. That's why we all have to agree that using RSA in 2019 is completely unacceptable. With no exceptions.
Original article in English.
VirgilSecurity, Inc. develops open source developer friendly SDK and data protection services. We allow developers to use existing algorithms with minimal security risk.
PS I also recommend reading about embedding the backdoor in the RSA public key.
Source: https://habr.com/ru/post/459370/
All Articles