Cryptanalysis

The EFF presented their proposal how to improve the security of SSL/TLS and the internet PKI infrastructure. To understand their proposal, one needs to understand how PKI in the internet works today:

Public Key Cryptography

In cryptography, you can usually encrypt and decrypt  data. In the past, encryption and decryption used the same key. Starting from the 70s, a new class of encryption/decryption algorithms was invented, the public key encryption algorithm. Instead of using the same key for en- and decryption, these algorithms use different keys for en- and decryption. During key generation, two keys are generated: A public key, that is used to encrypt data, and can be given out to everybody in the word, and a corresponding secret key, that must be kept hidden by the owner. Everybody who has access to the public key can encrypt data, but only the owner of the secret key is able to decrypt it.

There are many algorithms, for example RSA and ElGamal are the most famous public key encryption algorithms, while other algorithms like McEliece and Rabin are less well known.

Besides encryption, there are also digital signature algorithms. Again, a public and a private key is generated. The private key can be used to generate a digital signature on a document. The public key can then be used to verify the signature on the document. A signature on a document should guarantee that the document was really signed by the holder of the private key, and was not altered afterwards.

PKI

These ideas sound simple at the first look, but in practice, getting a public key of a person or company is not that easy. Just publishing your public key in some kind of web forum or on your facebook page is not enough. Everybody would be able to create a facebook page for another person, and then posting a fake public key on that page, or under that persons name on a web forum. So we need a way to establish a binding between a public key and a person or identity (a company name, a domain name or an email address). One solution would be to meet everybody in person who you want to communicate with, but it doesn’t scale well, and not everybody wants to fly to San Jose, California, just to get the public key for paypal.com.

For these job, Public Key Infrastructue (PKI) and X.509 Certificates have been invented. A Certification Authority (CA) is an organization, that verifies the identity of a person, and that this person is in possession of a private key. After this has been confirmed, the CA issues a X.509 certificate. That certificate contains the corresponding public key of that person, and it’s identity, and this information is signed using the CAs private key. Everybody who thinks that this CA does a good job in verifying the identity of persons, and is in possession of that CAs public key can verify that signature. As from now on, one only needs to trust a CA. One can simply give away the certificate issued by a CA, and everybody can get the public key from the certificate, and verify that it really belongs to that person, by verifying the signature of the CA. Today, there are hundreds of CAs active on the internet, and every web browser comes with a pre-installed list of trustworthy CAs and their public keys.

SSL/TLS

To encrypt HTTP traffic and to prove the autenticity of a website, the SSL/TLS protocol was created. When a session to a web server is established, the web server usually provides a digital certificate containing the public key of that web server. The web browser verifies the signature on that certificate, and that the identity in that certificate matches with the servers name it want’s to connect to. If everything is fine, the public key in that certificate is used to establish a secure session with that web server using some kind of key derivation scheme. (I won’t go into detail here)

The current state of PKI in the internet

At the first look, this sounds like a perfect solution. Whenever I want to talk privately with paypal, I just point my web browser to https://www.paypal.com/, it automatically connects to the server, gets a certificate, verifies that is has been correctly signed by a trustworthy CA, and the identidy in the certificate matches the expected servers hostname.

Attack vectors

However, there are multiple problems with that system. Just to mention one example: There are hundred of CAs active in the internet, and your web browser trusts every single one of them. Every CA is allowed to issue a certificate for every domain name in the internet. For example the national Chinese stat CA is allowed to issue a certificate for http://www.defense.gov/, which is the website of the ministry of defense of the united states of america. Also, the verification done by most CAs is minimal. For many CAs, it is sufficient if you can receive a mail for hostmaster@domain.tld, to get a certificate for domain.tld. There are multiple ways how you can attack this:

CAs

First of all, you may find a bug in the CAs website or email server, that allows you to get access to the certificate issuing software, bypassing these checks.

DNS

Also, you might be able to attack a DNS server serving the zone-file for domain.tld, that allows you to reroute mail for hostmaster@domain.tld on the DNS level. This allows you to get a certificate for domain.tld too.

Routers

Routers, especially those using BGB or a similar protocol might be tricked into rerouting the traffic for the mail server of domain.tld to your network. This way, you can intercept the mail and get your certificate too.

Crypto

Besides that, weak cryptography  algorithms like MD5 have been used by some CAs, and this has been used to generate a rouge certificate too.

The EFF solution

To improve the security of PKI, the EFF has presented a proposal: Sovereign Keys

Sovereign Keys should make it harder for an attacker to generate a new certificate for an HTTPS website, without the cooperation of the legitimate site operator. The main building block of Sovereign Keys are so called timeline servers. These timeline servers are append-only databases, meaning that one can only add entries to the database, but never modify or delete them. These timeline servers could be operated by different entities like the EFF itself, or Mozilla, Google or Microsoft.

To use Sovereign Keys, the side administrator obtains an X.509 certificate as usual. Then he generates a new key, the so called sovereign key. He uploads the key with the certificate to a timeline server. The server operator checks, if that certificate is really issued by a valid CA and no other sovereign key has been added previously, and adds the sovereign key with the hostname of the certificate to the database.

When a client connects to the website, he also requests all database entries belonging to that hostname from a timeline server. In parallel to that, a SSL/TLS connection is established. The Server delivers the server certificate to the client, with an additional signature created with the sovereign key. The client can then check, if this signature can be verified with the sovereign key retrieved from the timeline server.

More details

The full protocol is a little bit more complex, because it needs to deal with revocation, privacy, mirroring and load balancing the timeline servers and many more things. It has not yet been finalized, but a draft of the protocol can be downloaded from: https://git.eff.org/?p=sovereign-keys.git;a=blob_plain;f=sovereign-key-design.txt;hb=master

Summary

For me, this looks like one of two solutions you need to improve the general security of SSL/TLS. Sovereign keys is a great solution for website operators that care about the security of their users. It will not help a user, if the website he connects to does not use it. For these cases, a different solution should be used, like checking if multiple computers in the internet get the same certificate from the server.

Sebastian Schinzel gave an interesting talk today at 28C3, about timing side channel attacks against web applications. (Timing-) Side channel attacks are known in the cryptography world for a long time, and many algorithms like RSA or AES have been successfully attacked. In a nutshell, an attacker measures the time a device needs to process a request (usually an encryption or decryption), and can draw conclusions from that to the values of secret input parameters (a plaintext or a secret key).

Sebastian showed, that this can be used against none cryptography web applications as well. Instead of just presenting his attacks, he presented general methods how to do timing measurements against web applications first. For example, a web application could perform the following sequence of checks during a user login:

1. Does the account exist?
2. Is the account of the user locked?
3. Has the account expired?
4. Is the password correct?

If one of these checks fails, the procedure is aborted and an error page is send to the user. Of course, each of these steps requires some time, and from the time it takes from the request to the generation of the error message, one might guess, which of these steps went wrong.

The second attack presented in this talk was a timing attack on an implementation of the XML encryption standard using a PKCS#1.5 padding. Here, the server needs a longer time to process a request, depending on the padding inside the encrypted payload.

For me, my personal highlight was the extension of timing based side channel attacks to none cartographic web applications. I assume, if one would check some famous web applications, many of such timing leaks could be found, because web developers usually don’t care about timing side channels. The timing difference could also be used to assist blind SQL injection attacks, where the timing difference could be the only channel back to the attacker.

Unfortunately, the slides are not (yet) available, but a previous paper describing the methods can be found at http://sebastian-schinzel.de/_download/cosade-2011-extended-abstract.pdf.

Stefan Burschka presented a nice attack against Skype on 28C3. The attack allows you to detect a sentence or a sequence of words in an encrypted Skype call, without having to break the cryptography used in Skype. Skype is a famous internet telephony application, that offers free voice calls. To save bandwidth, Skype uses an advanced audio codec. The used bandwidth and the size of the packets send by Skype depends heavily on the audio, that is encoded. The packet length is no hidden by the encryption of Skype and visible to an eavesdropper.  Just using these information, Burschka could distinguish between difference sentences in an encrypted Skype call.

Two methods were used to improve these results:

• Dynamic Time Warping (DTW) is an algorithm used by many speech recognition systems, to compare an audio sample with a set of reference samples of slightly different length.
• A Kalman Filter, which is a method to remove noise from measurements. I think here, noise is a slight variation of the packet lengths.

That the amount of communication between two parties and the actual timing of packets can leak information about the content of an encrypted communication was known for a long time, and has been successfully used for an attack against the TOR onion router network. However, this is the first time, that I have seen this method applied against Skype. The methods here are so generic, that they might be applied as well against other VoIP systems like SIP, if they are encrypted or communicate over a VPN.

The full paper is available at http://www.csee.usf.edu/~labrador/Share/Globecom/DATA/01-038-02.PDF and the slides can be downloaded from http://events.ccc.de/congress/2011/Fahrplan/attachments/1985_CCC.pptx.

Travis Goodspeed presented a sneaky attack against WiFi networks at 28C3. The idea is simple: Assume we want to inject packets remotely into a wireless network. Assume that there is a user in the network visiting a malicious webpage. How can we trick him into injecting a packet of our choice into his network?

We can use a nice property of many radio protocols: They split their transmission in packets. A static radio preamble and/or sync-field is send at the beginning of a packet, followed by a packet header, payload, and a checksum. (Some protocols also use forward error correction.) The radio preamble is used by a receiver to detect the start of a transmission. A receiver will scan the frequency for a valid radio preamble, and if one was found, receive a packet. The end of a packet can either be determined by a length-field in the header, or some protocols use fixed length packets, so that the length of a packet is known in advance. After the packet has been received, a checksum in the packet can be used to find out, if the transmission has been damaged by radio interference.

So what would happen, if we embed the packet we want to inject, into a HTML-Page or another file, that is transferred to the client. When that file is downloaded, a perfectly valid packet, containing our packet as payout will be transmitted. As long as this packet is received correctly by the client, everything works as normal. However, if the radio preamble of this packet is damaged during the transmission, the receiver will continue to scan for a radio preamble, and start receiving our embedded packet. Of course, the odds that this specific radio preamble is damaged during the transmission might be quiet low, we can easily repeat that packet in the transmission, until it is decoded by a client. This is not a theoretical thing, from time to time, radio preambles of packets are really received incorrectly in practice. As a result, we manage to inject a packet into a WiFi network, that was never send. The packet send is also perfectly standard compliant(, if it is received without any error).

There are some practical problems when implementing this, like switching the transmission speed during a packet or different modulations. However, Travis managed to implement his attack against 802.11b WiFi networks.

The full paper is available at: http://www.usenix.org/events/woot11/tech/final_files/Goodspeed.pdf

 

The lists of accepted papers for the following conferences have become available in the last couple of days:

• EUROCRYPT 2009
• FSE 2009 (PDF)
• CT-RSA 2009

Interesting cryptanalysis papers will be presented at all of the above conferences. It is a bit of a hassle to have CT-RSA and EUROCRYPT back to back on two different continents though.

MiFare’s CRYPTO1 stream cipher has captured my attention for a while. However, hardware reverse-engineering is not a field I actively engage in. So I was very happy when Karsten Nohl (University of Virginia), Starbug and Henryk Plötz gave a talk at the 24C3 [the 24th Congress of the Chaos Computer Club taking place in Berlin at this very moment] yesterday evening showing that they have reverse-engineered most parts of this cipher. CRYPTO1 uses a 48-bit LFSR-based filter generator to generate key stream.

The filter function – if I understood correctly – uses 24 20 taps (this was not mentioned in the talk, I asked Karsten privately about this) however the degree of the boolean function implementing the filter , thus it remains to be seen whether algebraic attacks can be applied. Even if no algebraic attacks are applied, a BSW sampling TMTO will break CRYPTO1 completely. This was pretty obvious before they gave their talk, but now vendors actually have to worry about this being out in the wild once the feedback and the filter function have been revealed.

My colleague Erik took photos of the slides which I put up on Zooomr. A video recording of the talk should be available shortly and will be linked here.

Update 2008-01-02: A recording of the talk now is available (MPEG4, iPod compatible).