Wednesday, July 23, 2008

Can't connect to local MySQL server through socket '/tmp/mysql.sock'

Since some time I was having troubles connecting to the MySql server running on local machine via command line. First I have to tell you that I’m not a Linux guru. Just started using it because my University forced me do so.
Anyway this was the symptom when I tried to access MySql server via command line interface.
By the way I was using Ubuntu 7. Something.

root@local:~# mysql
ERROR 2002 (HY000): Can't connect to local MySQL server through socket '/tmp/mysql.sock' (2)

Browsing through more than 1 million search results ( : ) ) brought by Google didn’t bring anything valuable but only to discover that more than half of the world population is faced with the same issue.

Surely something is wrong. Either /tmp/mysql.sock is not in the place mysql utility is looking or it has been locked or something.
When i restarted MySql server (Of cause after brutally killing all by using # killall -9 mysqld) I discovered something interesting.

root@local:~# mysqld
080723 7:38:36 InnoDB: Started; log sequence number 0 43655
080723 7:38:36 [Note] Recovering after a crash using /var/log/mysql/mysql-bin
080723 7:38:36 [Note] Starting crash recovery...
080723 7:38:36 [Note] Crash recovery finished.
080723 7:38:37 [Note] mysqld: ready for connections.
Version: '5.0.45-Debian_1ubuntu3-log' socket: '/var/run/mysqld/mysqld.sock' port: 3306 Debian etch distribution

Aha …. Mysql server creates its socket in ‘socket: '/var/run/mysqld/mysqld.sock' ... Not the place mysql utility is looking for it.
Anyway since all got cleared now I had 2 paths. Mucking with some configuration file buried deep with in or compiling MYsql with
some wired flags set to change its default sock path. I had time to chose none. Hell I just wanted to run some damn small query on the database and say ta to MySql for good. So this is the final option I choosed.
In MySql utility there is a option called --protocol. I just used that.

root@local:~# mysql --protoco TCP -u root -p
Enter password:
Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 2
Server version: 5.0.45-Debian_1ubuntu3-log Debian etch distribution
Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

Bye Bye stinky Sock ... Welcome TCP Socket. Problem not solved but successfully overlooked. Well that’s enough for me at the moment.

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
φ(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)
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

Monday, April 14, 2008

New Start

Today is the Sinhala and Hindu new year day. Wish all the best for everyone who are calibrating.
Today I will start posting and if all goes well this blog will get populated bit by bit during the years to come. This is of cause subjected to availability of issues and my free time to do something useless. If someone gets something useful out of a post in here then my intention is fulfilled.