Nov 062013

Public Key cryptography solves one of the main problems with strong cryptography. How do you securely share the encryption/decryption key? If you have a secure channel for doing that, then why not use the same channel to send your plaintext message?

Public Key cryptography uses one key to encrypt and a different key to decrypt. This means you can share your Public Key with the world and anyone can use it to encrypt a message to you, but you are the only person with access to the Private Key to decrypt the message. Clever stuff!

This allows all sorts of exciting things – encryption, signing, non-repudiation and more.

But how does the maths behind this work? I’ve written a worked example below which shows a simplified version of how RSA encryption works. I’ve used small numbers so that you can follow along with a calculator, or a pencil and paper if you are cleverer than me!

Choose two random (large) prime numbers, p and q:
p = 13
q = 7

Multiply the numbers together to get the modulus, N, (the maximum value we can encrypt).
N = pq = 13*7 = 91  This is known as a trapdoor function – it’s easy to work out N if you know pq but very difficult to discover p and q if you only know N (for bigger numbers than we are using here)

Choose a public key, e.
e = 5 (generally chosen from {3, 5, 17, 257, 65537} which are also prime numbers)

To compute the associated private key, you need to know the two prime numbers (p and q). First compute φ (phi)
φ = (p-1)(q-1) =(13-1)(7-1) = 12*6 = 72

Then compute the private key, d.
d = (1/e) mod φ  or, written differently,  ed = 1 mod φ

In English, this means “find a whole number, d, which, when multiplied by ‘e’ and then divided by ‘φ’, leaves a remainder of 1” – there will be multiple values which are suitable.

Substituting the known values, we get
5d = 1 mod 72,  so d = 29  (because 5*29/72 = 2 remainder 1) or 461 (because 5*461/72 = 32 remainder 1) or 7373(because 5*7373/72 = 512 remainder 1) or other, larger, numbers…

We’ll choose the smallest number ’29’ here to make the calculations later a bit easier.

We now have all the required parts to encrypt and decrypt a message.

The public key which you share with the world is (N, e) = (N = 91, e =5)
The private key which is known only to you is (N, d) = (N = 91, d = 29)
The key pair is written ((N,e), d) – in our case ((91, 5), 29)

Before we can encrypt a message, we need to convert the message from letters to numbers. Lets use the standard Unicode Transformation Format 8-bit (UTF-8) encoding where each letter is represented by a number:

A = 65 G = 71 M = 77 S = 83 Y = 89
B = 66 H = 72 N = 78 T = 84 Z = 90
C = 67 I = 73 O = 79 U = 85
D = 68 J = 74 P = 80 V = 86
E = 69 K = 75 Q = 81 W = 87
F = 70 L = 76 R = 82 X = 88

– a space would be represented by 32

So, the message “ATTACK” would be encoded as 65, 84, 84, 65, 67, 75

To encrypt the plaintext message, m, into cypertext, c
c = me mod N
(remember, ‘e’ and ‘N’ are both public information)

A would be 655 mod 91 = 1,160,290,625 mod 91 = 39 (1,160,290,625 / 91 = 12,750,446 remainder 39)
T would be 845 mod 91   = 4,182,119,424 mod 91 = 28
C would be 675 mod 91   = 1,350,125,107 mod 91 = 58
K would be 755 mod 91   = 2,373,046,875 mod 91 = 17

Our encrypted message is now 39, 28, 28, 39, 58, 17

to decrypt the cyphertext, c, back to the plaintext, m
m = cd mod N
(remember, ‘d’ is only known to us!)

39 would be 3929 mod 91 = 1.3831637670618865315545398098597e+46 mod 91 = 65
28 would be 2829 mod 91 = 9.2807464717109449615203639109421e+41 mod 91 = 84
58 would be 5829 mod 91 = 1.37851600677743110483676343403e+51 mod 91 = 67
17 would be 1729 mod 91 = 4.8196857210675091509141182522307e+35 mod 91 = 75

3929 mod 91 is “the remainder when 39 multiplied by itself 29 times is divided by 91” – The numbers when we worked this out above become enormous – we can keep the numbers smaller by dividing by 91 and keeping just the remainder as we go along. If we do this one step at a time, we get:
1: 39*39 = 1,521 – this is bigger than N (91) so we can divide by 91 to get 16 remainder 65 (just keep the remainder!)
2: 65*39 = 2,535 – we can divide by 91 to get 27 remainder 78
3: 78*39 = 3,042 – we can divide by 91 to get 33 remainder 39
…and so on…
27: 65*39 mod 91 = 78
28: 78*39 mod 91 = 39
29: 39*39 mod 91 = 65  <— the same answer we got by doing 3929 mod 91

Our decrypted message, then, is 65, 84, 84, 65, 67, 75 which decodes to ATTACK using the UTF-8 table!

Let me know in the comments below if this makes sense and is useful…

Sep 232013

What happens if an attacker compromises your root private key?

SSL certificates are used to authenticate clients and servers and to provide a means of securely sharing a secret key which is then used to encrypt communication between the server and client.

In order to do this, you have to have a level of trust in the body which issues the certificates; the Certification Authority or CA.

The way this works in practice is that you place the Root Certificate of the Certification Authority in your ‘Trusted Root Certification Authorities’ store on your computer. This says ‘I trust all certificates signed by the private key associated with this certificate’. Since the private key is only known by the Certification Authority, any certificate signed with the key must have been issued by the authority, and passed all the checks as defined in their CPS (Certification Practice Statement).

Once the infrastructure is in place, the flow is as follows:

SSL flow

Over complicated diagram showing keys and certificates.

  1. The client connects to the web server and requests a secure connection.
  2. The web server sends its certificate which includes a public key.
  3. The client verifies the certificate by checking the name matches the site name, that it has not expired (or been revoked) and that it is signed by a trusted authority.
  4. The client chooses a symmetric encryption key and encrypts it with the public key from the certificate. This is sent to the server
  5. The server decrypts the message with its private key. The browser and web server now share a symmetric key which is unknown to anyone else. This key is used to encrypt all communication for the rest of the session.

The security of the above transaction relies on the private key being stored securely by the web server. If someone had access to that key, they could decrypt the message containing the secret symmetric session key and therefor read all the encrypted messages which follow during that session. However, its unlikely that the owner of the web server would allow the key to leave the server. If an attacker managed to compromise the server to such an extent that he had access to the key, he would have full control of the server and would be able to access the communication anyway. If a government requested the key through legal means, they would be able to read all the communication but, again, they would get much more information by just requesting full access to the server.

So everything is nice and safe as long as the private key is kept secure. (There are, of course, other problems if, for example, there is malware on either end, but I’m ignoring that here).

So, what happens if someone gets access to the Certification Authority’s Private Key either by compromising their key store or by demanding it via legal channels?

Having the root private key would still not allow the attacker to intercept the symmetric key as it is encrypted using the public/private keypair generated by the web server, and the private key is still only known by the web server. It would, however, allow the attacker to create his own certificate and sign it with the Root CA private key. This would mean that it is trusted by the client computer and it would be very difficult to tell it apart from the genuine server certificate.

The attacker can now perform a ‘Man-in-the-middle’ (MITM) attack to capture all the traffic between the client and server. He does this by posing as the web server and authenticating with the client. The client now sends the symmetric key to the attacker encrypted with the attacker’s public key. The attacker decrypts the key and sets up a secure connection with the client. At the same time, the attacker connects to the genuine site and poses as the client. The attacker acts as a proxy between the client and server and can read both sides of the communication. Further, the attacker can change the information from either side. Say, for example, you think you are connected to your bank and you check your balance. The attacker can report the correct balance, but in the background could transfer all your money into his own account. If he needs any extra passwords, or a two-factor authentication, he can prompt you for those details and, if its convincing enough, you may be fooled into providing what he needs.