Analysis: Factoring Attack on RSA-EXPORT Keys

Introduction

CVE-2015-0204 It has been known that as computing resources become cheaper, it becomes feasible to break the encryption that uses progressively longer keys. For example, DES with 64-bit keys is no longer considered secure.With public key encryption (PKE), the watermark is a lot higher. Public key encryption systems use the mathematical property of large numbers, namely "finding factors of a very large number is a very expensive operation". If a number is 'n' bits long, the factorization is order of 2^f(n) (more accurately, order of 2^[{64*n/9}^1/3}{log n}^2/3], but suffice to say it is an exponential to a function of number of bits ).


Using keys 512-bits or shorter is considered susceptible to brute-force attack to break encryption. Modern encryption software uses 1024 or 2048-bit (PKE) keys, just to show you the contrast between what is considered secure today.

Export grade encryption

In 1990's USA had imposed export restrictions on encryption software, disallowing strong encryption software from being exported. For example, it only allowed export of encryption using RSA keys shorter than 512-bits - the so-called "export-grade encryption" - which is decidedly weaker than the state-of-the-art at the time. This required software products to support weaker encryption around the world. Even when the export controls were removed (around the 2000's), the software products continued to support weaker encryption, perhaps these were never updated, or for backward compatibility, or due to oversight, or because the product release process was never reviewed for this aspect, or perhaps due to laziness on part of the professionals.


Forcing use of "export grade" Encryption

If an agent sitting between a browser and a secure server can "force" the two entities to use a weaker (export grade) encryption, then the agent can potentially break the encryption ("factor the RSA key"), and reveal the supposedly secure communication. FREAK researchers, using "factoring as a service" cloud service took around 7.5 hours to factor the export-grade RSA key. So of course, the agent can't hope to achieve this at wire-speed. However, these encrypted sessions can be recorded by the agent, and decrypted offline. For your long lived sessions, like your mobile app for a social networking site, or webmail access, or bank access apps, it may be possible to hijack such a session, if they last longer than a few hours.


Mitigation

The mitigation is simple on the server side, but not so on the client side. The servers (most of them) can be configured to not allow low-grade encryption to be used. However, even if all servers are changed this way, an attacker can still target the clients.Fortunately, most Firefox browser versions are reported to be not susceptible to FREAK attack. So first line of defense would be to begin using Firefox on all platforms.

  1. Switch to Firefox on all platforms.
  2. Update the browser and other products as and when the vendors roll out the patches for FREAK.
  3. If you own, operate or host a "secure" website, update the configuration to disallow the use of low-grade encryption.
  4. For now and future, any time a browser or another remote access software throws a warning regarding cryptographic issue, DON'T click through OK. Step back and review the warning message. If possible, don't continue with the operation, and retry after some time. If the warning persists, contact the server operator.

How FREAK works

Client browser asks to connect to a server using https (as an example). Attacker intercepts it and asks the server to use low-grade encryption. Attacker then forwards the weak encryption "response" from the server to the client. Client assumes that the server "is incapable of supporting stronger encryption", and agrees to use weak encryption. Attacker captures the session initiation handshake and key exchange traffic. Offline, the agent breaks the weak encryption key, and eventually obtains the secure session key (technically more complex than being a single step). From here on, the agent can eavesdrop on the communication and potentially modify the data for malicious purpose.


References:

RSA key length and their relative securitySurvey paper of integer factoring algorithmsFREAK is just one of the discoveries by the researchers