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.

Aug 292010
Rusty Padlock

Padlock by Ralph Aichinger

Certification Authorities (CAs) offer two types of SSL certificate, one type includes Server Gate Cryptography (SGC) and is often promoted as a premium, or high security option and is charged at a much higher price than the non-SGC equivalent. So, it should be a no-brainer that you should buy the best, most expensive certificate you can afford to ensure the security of traffic with your website, shouldn’t it?

Well, no.

Until late 1999, the United States were imposing restrictions on the export of strong cryptography which resulted in ‘export versions’ of Internet Explorer, Netscape and other web browsers which did not enable high encryption by default. Instead, browsing SSL sites with an ‘export version’ browser resulted in a connection which was encrypted with 40 or 56-bit encryption. A non-export version would negotiate 128-bit encryption. To allow very sensitive sites to step-up the encryption to 128-bit even on an export version browser, special certificates were issued to authorised sites, for example government sites and financial institutions, which would unlock the high encryption functionality and allow 128-bit secure connections.
By 2000, the export restrictions were dropped and the international browser versions began supporting 128-bit encryption by default. At the same time, SGC certificates were offered to anyone who wanted them to allow older export browsers to use high encryption.

For a few years after 2000, it made sense to use an SGC enabled certificate if you wanted to ensure everyone could access your site securely and it was worth paying a premium to ensure that your site was available to the maximum number of customers. Now, though, there are many fewer users with the old browsers, so you won’t affect as many customers by removing the SGC capability.

But, it can’t hurt to use an SGC certificate, can it?

Well, yes.

These old browsers (e.g. Internet Explorer 4.01 to 5.01, Netscape 4.07 to 4.72) are over 10 years old now, they have not received security updates or patches since 2000. The security patches which have been released for more modern browsers in the past ten years help to protect the system against keyloggers, viruses and other malware which can intercept data on the client, even if it is transmitted across the network securely encrypted. This means that the connection which is assumed to be secure by the user probably isn’t, and malware in the browser could potentially be carrying out unauthorised transactions on your server using the client’s credentials. Worse still, the malware could hide the fraudulent transactions from the user so he never sees evidence of a problem.

Updating these browsers to modern, secure versions is free and simple. High-encryption packs are available from Microsoft for older operating systems – Windows 95, Windows 98, Windows NT and Windows 2000, and a huge variety of secure browsers are available for free download.

So, how many customers are likely to be unable to access my site when I move to non-SGC certificates?

In an Entrust Whitepaper on the subject from July 2009, the estimate is that 0.07% of browsers on the Internet would be affected, less than 1 in a thousand, and this number is likely to be even lower now.

This small percentage of users who will be unable to connect to your site are unlikely to be surprised as more and more of the Internet will be becoming unavailable to them every day as other sites move away from these outdated certificates. It really is time they dragged themselves into the 21st Century and spent 5 minutes upgrading their browsers to ensure their connection is secure. By making sites unavailable to them, you are doing your customers a favour by encouraging them to upgrade, and are helping to protect your other customers by making it harder for malware to get a foothold on your server.

There is one very important change you need to make to your server though, ensure that weak encryption is not supported otherwise these old browsers will negotiate 40 or 56-bit connections with your server!

Enhanced by Zemanta