Monday, May 26, 2008

How secure RSA is in practice?

Brute force attacks

Even though it is possible to try every possible value for d (Decryption key) till we find the correct value, for larger keys it is highly inefficient process for any practical usage.
Another way to break RSA is to factor n. The security of RSA depends on the problem of factoring large numbers. Attacker having the public key e and modulus n has to factor n to find d. Even though brute force attack can be successfully deploy against RSA encrypted message if the key lengths are not long enough using the modern day factorising algorithms and faster machines it is still harder and impractical to break RSA using brute force attacks on larger (E.g. 1024 or more bit key sizes) keys.
On the other hand keys once considered impractical to break have become vulnerable in recent years.
For example even though Rivest predicted that it will take about 40-quadrillion years to factorize 129 bit long key , in reality it took only about 8 months to determine it with the help of an world wide distributed system. [Riele H, 1995, Factoring Large Numbers]
This suggests us that even larger key sizes are not 100% secure in the long run.

Implementation flows, constraints and bugs

Hybrid architecture
Encrypting bulk messages using asymmetric ciphers such as RSA is extremely slow and processor intensive process compared to the other encryption methods using symmetric ciphers such as AES. This makes it using pure asymmetric ciphers to encrypt messages impractical in everyday applications. In software implementations, encryption/decryption using asymmetric ciphers such as RSA is 100 times slower than using symmetric ciphers such as AES to do encryption/decryption operations.
To circumference this limitation in practice, applications use symmetric ciphers to encrypt the bulk messages and then encrypt the session key using the asymmetric ciphers for secure exchange between communicating parties. These are called hybrid cipher systems. The issue with this method is that the system is strong as its weakest link. If the application make use of vulnerable symmetric ciphers or use less than adequate key lengths for the session key , attack can be deploy against the message directly with out being bothered to decrypt the session key encrypted using the asymmetric cipher.
This vulnerability can be addressed by choosing keys with satisfactory length to encrypt messages when using symmetric ciphers.
Not so random number generators
Sometimes even if long enough RSA keys are used, a known flows in the random number generator or not having enough entropy while calculating p and q may make the system vulnerable to attacks. This will give an opportunity to the attacker to simulate/guess and check p and q with out going through a full brute force method to factor n to find p and q.

Attacks against choosing common e

In practical algorithms, to make modular exponentiation operation faster for RSA , encryption exponent e is chosen to be same for all users and one of 3, 17 or 65537 values. This is to simplify the calculation of c = Me mod n.
When e is chosen as 3 then cube root attack is possible.
When e is chosen as 3 and message (M) is less than n 1/3
Then modular operation becomes effect less and thus c = M3
In this situation attacker can easily determine message M from the cipher text (c) alone by simply calculating cube root of c.
This security issue can be easily avoided by padding short messages with random bits so that message M is larger than n 1/3
Key management
Poor key management and signing techniques used by careless users can jeopardise the ability to communicate securely and will weaken the web of trust. It is absolutely essential to verify (Key fingerprint can be used) the identity of the key owner before signing any key. Secondly all public key signatures should be verified before using it to ensure secure communication.
Threats posed by network/password sniffing applications are virtually eliminated by using RSA based asymmetric cryptographic systems. Shared secrets do not need to be exchanged insecurely or in a cumbersome way to initiate a secure communication. Using RSA public/private key pares, this exchange of shared secret can be automated and secured.
Social engineering attack
Vulnerability exists where intercepting party can recover an encrypted message using carefully altered cipertext message and some social engineering techniques. For example Alice send encrypted message to John which get intercepted by Malory. Malory alters the cipher text and sends the message to John as it is coming from him. When John tries to decrypt the altered message it returns garbage. When John notify this to Malory , Malory can request that decrypted garbage to be sent back to him. If John is careless enough to do that, Malory can easily determine/recover the session key by analysing the decrypted data injected by him in to the cipher text. Then this session key can be used to decrypt the original message sent by Alice.
This vulnerability can be easily avoided by practising some common sense and not returning any data from a failed decryption attempt to any one who asks for it.

Mathematics behind RSA private and public keys

Public and private keys are used in asymmetric cryptographic systems to exchange data securely with out sharing a common secret key. Even though the mathematical concept behind each asymmetric cryptographic algorithm differs they all are based on one concept in which two different keys are used in encryption and decryption process. Out of these keys, encryption key is freely distributed (public key) while the other key (decryption key) remains a secret. Out of many asymmetric cryptographic algorithms we will have a look at the RSA algorithm.
In RSA, Private and public key pares are basically two prime numbers which satisfy certain mathematical conditions. In real life situations these two prime numbers need to be large enough to be practically used in a cryptographic system

RSA concept:

The basic steps in deriving key pairs are listed below.
  1. Select/generate 2 prime numbers
Get two prime numbers p and q.
  1. Calculate the modulus
Multiply to get number n
Modulus = n = p* q
  1. determine φ(n)
Lets calculate φ(n) where φ(n) = (p-1)(q-1)
By applying Euler’s totient function we calculate φ(n), which is the number of positive integers less than n that are coprime with n .
  1. Calculate the Encryption key(public exponent):
Let’s choose the encryption key (public key) e where e and φ (n) are coprime. Which means the greatest common denominator (gcd) of e and φ (n) is 1. I.e. the largest positive integer that divides both numbers without remainder is 1.
i.e: gcd(e , φ (n)) = 1
In here e should be greater than 1 and less than φ(n)
  1. Calculate the decryption key (secret exponent):
Decryption key (Private key) d is derived by calculating the inverse of
e mod (φ(n)) using the extended Euclidian algorithm
d = e-1 (mod (φ(n)))
In summery:
Public key is (n, e) where
gcd(e , φ(n)) = 1
and
φ(n) = (p-1)(q-1)
Private key is (n, d) where
d = e-1 (mod (φ(n)))

Practical example:

How this algorithm is used to generate a private and public key pare is shown below by using two small prime numbers.
  1. Select 2 prime numbers
Let’s select 2 prime numbers p and q where
p = 31
q = 17
  1. Calculate the modulus
Modulus = n = 31 * 17 = 527
  1. determine φ(n)
φ(n) = (p-1)*(q-1)
= (31-1)*(17-1)
=30 * 16
φ(n) = 480
  1. Calculate the Encryption key:
Lets choose a value for e such that gcd(e , φ (n)) = 1
gcd(e , φ (n)) = 1
gcd(e , 480) = 1
Let’s choose e as 7
Lets ensure that gcd(7 , 480) is really 1
480 = 25 x 3 x 5 x 1
7 = 7 x 1
Which assure us that gcd(7 , 480) = 1
  1. Calculate the decryption key:
d = e-1 (mod(φ (n)))
d = 7-1 (mod480)
Let’s use a table to calculate the inverse of 7mod480 using extended Euclidean algorithm.
Xi = (Xi-2 - [Xi-1*qi-2]) (mod b)
Where,
X0 = 0 and X1 = 1

Step 0:
480 = 68(7) + 4
X0 = 0
Step 1:
7 = 1(4) + 3
X1 = 1
Step 2:
4 = 1(3) + 1
X2 = (0 – (1*68))mod480 = 412
Step 3:
3 = 3(1) + 0
X3 = (1 – (412*1))mod480 = 69
X4 = (412 – (69*1))mod480 = 343

Thus d = X4 = 343
Thus according to our chosen prime numbers p and q,
Public key e is (527, 7) and private key d is (527, 343)
In practise, to make modular exponentiation operation faster, e is chosen to be one of 3, 17 or 65537 values. This is to simplify the calculation of encryption, c = me mod n where c is cipher text and m is the unencrypted message.
The bit lengths of p and q should be equivalent to the half of the bit length of n where Modulus = n = p* q