Yesterday I read via twitter that the HP researcher Vinay Deolalikar claimed to have proofen P!=NP. If you never heared about it, the question whether P=PN or not is probably the biggest unsolved problem in computer science and one of the biggest ones in mathematics. It's one of the seven millenium problems that the Clay Mathematics Institute announced in 2000. Only one of them has been solved yet (Poincaré conjecture) and everyone who solves one gets one million dollar for it.

The P/NP-problem is one of the candidates where many have thought that it may never be solved at all and if this result is true, it's a serious sensation. Obviously, that someone claimed to have solved it does not mean that it is solved. Dozends of pages with complex math need to be peer reviewed by other researchers. Even if it's correct, it will take some time until it'll be widely accepted. I'm far away from understanding the math used there, so I cannot comment on it, but it seems Vinay Deolalikar is a serious researcher and has published in the area before, so it's at least promising. As I'm currently working on "provable" cryptography and this has quite some relation to it, I'll try to explain it a bit in simple words and will give some outlook what this may mean for the security of your bank accounts and encrypted emails in the future.

P and NP are problem classes that say how hard it is to solve a problem. Generally speaking, P problems are ones that can be solved rather fast - more exactly, their running time can be expressed as a polynom. NP problems on the other hand are problems where a simple method exists to verify if they are correct but it's still hard to solve them. To give a real-world example: If you have a number of objects and want to put them into a box. Though you don't know if they fit into the box. There's a vast number of possibilitys how to order the objects so they fit into the box, so it may be really hard to find out if it's possible at all. But if you have a solution (all objects are in the box), you can close the lit and easily see that the solution works (I'm not entirely sure on that but I think this is a variant of KNAPSACK). There's another important class of problems and that are NP complete problems. Those are like the "kings" of NP problems, their meaning is that if you have an efficient algorithm for one NP complete problem, you would be able to use that to solve all other NP problems.

NP problems are the basis of cryptography. The most popular public key algorithm, RSA, is based on the factoring problem. Factoring means that you divide a non-prime into a number of primes, for example factoring 6 results in 2*3. It is hard to do factoring on a large number, but if you have two factors, it's easy to check that they are indeed factors of the large number by multiplying them. One big problem with RSA (and pretty much all other cryptographic methods) is that it's possible that a trick exists that nobody has found yet which makes it easy to factorize a large number. Such a trick would undermine the basis of most cryptography used in the internet today, for example https/ssl.

What one would want to see is cryptography that is provable secure. This would mean that one can proove that it's really hard (where "really hard" could be something like "this is not possible with normal computers using the amount of mass in the earth in the lifetime of a human") to break it. With todays math, such proofs are nearly impossible. In math terms, this would be a lower bound for the complexity of a problem.

And that's where the P!=NP proof get's interesting. If it's true that P!=NP then this would mean NP problems are definitely more complex than P problems. So this might be the first breakthrough in defining lower bounds of complexity. I said above that I'm currently working on "proovable" security (with the example of RSA-PSS), but provable in this context means that you have core algorithms that you believe are secure and design your provable cryptographic system around it. Knowing that P!=NP could be the first step in having really "provable secure" algorithms at the heart of cryptography.

I want to stress that it's only a "first step". Up until today, nobody was able to design a useful public key cryptography system around an NP hard problem. Factoring is NP, but (at least as far as we know) it's not NP hard. I haven't covered the whole topic of quantum computers at all, which opens up a whole lot of other questions (for the curious, it's unknown if NP hard problems can be solved with quantum computers).

As a final conclusion, if the upper result is true, this will lead to a whole new aera of cryptographic research - and some of it will very likely end up in your webbrowser within some years.

I got selected for this years Google Summer of Code with a project for the implementation of RSA-PSS in the nss library. RSA-PSS will also be the topic of my diploma thesis, so I thought I'd write some lines about it.

RSA is, as you may probably know, the most widely used public key cryptography algorithm. It can be used for signing and encryption, RSA-PSS is about signing (something similar, RSA-OAEP, exists for encryption, but that's not my main topic).

The formula for the RSA-algorithm is S = M^k mod N (S is the signature, M the input, k the private key and N some big prime number). One important thing is that M is not the Message itself, but some encoding of the message. A simple way of doing this encoding is using a hash-function, for example SHA256. This is basically how old standards (like PKCS #1 1.5) worked. While no attacks exist against this scheme, it's believed that this can be improved. One reason is that while the RSA-function accepts an input of size N (which is the same length as the keysize, for example 2048/4096 bit), hash-functions usually produce much smaller inputs (something like 160/256 bit).

An improved scheme for that is the Probabilistic Signature Scheme (PSS), (Bellare/Rogaway 1996/1998). PSS is "provable secure". It does not mean that the outcoming algorithm is "provable secure" (that's impossible with today's math), but that the outcome is as secure as the input algorithm RSA and the used hash function (so-called "random oracle model"). A standard for PSS-encryption is PKCS #1 2.1 (republished as RFC 3447) So PSS in general is a good idea as a security measure, but as there is no real pressure to implement it, it's still not used very much. Just an example, the new DNSSEC ressource records just published last year still use the old PKCS #1 1.5 standard.

For SSL/TLS, standards to use PSS exist (RFC 4055, RFC 5756), but implementation is widely lacking. Just recently, openssl got support for PSS verification. The only implementation of signature creation I'm aware of is the java-library bouncycastle (yes, this forced me to write some lines of java code).

The nss library is used by the Mozilla products (Firefox, Thunderbird), so an implementation there is crucial for a more widespread use of PSS.

At least since 2005 it's well known that the cryptographic hash function SHA1 is seriously flawed and it's only a matter of time until it will be broken. However, it's still widely used and it can be expected that it'll be used long enough to allow real world attacks (as it happened with MD5 before). The NIST (the US National Institute of Standards and Technology) suggests not to use SHA1 after 2010, the german BSI (Bundesamt für Sicherheit in der Informationstechnik) says they should've been fadet out by the end of 2009.

The probably most widely used encryption protocol is SSL. It is a protocol that can operate on top of many other internet protocols and is for example widely used for banking accounts.

As SSL is a pretty complex protocol, it needs hash functions at various places, here I'm just looking at one of them. The signatures created by the certificate authorities. Every SSL certificate is signed by a CA, even if you generate SSL certificates yourself, they are self-signed, meaning that the certificate itself is it's own CA. From what I know, despite the suggestions mentioned above no big CA will give you certificates signed with anything better than SHA1. You can check this with:
openssl x509 -text -in [your ssl certificate]
Look for "Signature Algorithm". It'll most likely say sha1WithRSAEncryption. If your CA is good, it'll show sha256WithRSAEncryption. If your CA is really bad, it may show md5WithRSAEncryption.

When asking for SHA256 support, you often get the answer that the software still has problems, it's not ready yet. When asking for more information I never got answers. So I tried it myself. On an up-to-date apache webserver with mod_ssl, it was no problem to install a SHA256 signed certificate based on a SHA256 signed test CA. All browsers I've tried (Firefox 3.6, Konqueror 4.3.5, Opera 10.10, IE8 and even IE6) had no problem with it. You can check it out at https://sha2.hboeck.de/. You will get a certificate warning (obviously, as it's signed by my own test CA), but you'll be able to view the page. If you want to test it without warnings, you can also import the CA certificate.

I'd be interested if this causes any problems (on server or on client side), so please leave a comment if you are aware of any incompatibilities.

Update: By request in the comments, I've also created a SHA512 testcase.

Update 2: StartSSL wrote me that they tried providing SHA256-certificates about a year ago and had too many problems - it wasn't very specific but they mentioned that earlier Windows XP and Windows 2003 Server versions may have problems.

Gestern habe ich den Versuch unternommen, in einem Vortrag ein paar Hintergründe über Kryptographie zu vermitteln, u. a. mit dem Versuch, einen Diffie-Hellmann-Schlüsselaustausch mathematisch zu erklären.

Die Folien gibt's hier.

Recently, two publications raised awareness of a problem with ssl secured websites.

If a website is configured to always forward traffic to ssl, one would assume that all traffic is safe and nothing can be sniffed. Though, if one is able to sniff network traffic and also has the ability to forward the victim to a crafted site (which can, e. g., be just sending him some »hey, read this, interesting text« message), he can then force the victim to open a http-connection. If the cookie has not set the secured flag, the attacker can sniff the cookie and take over the session of the user (assuming it's using some kind of cookie-based session, which is pretty standard on today's webapps).

The solution to this is that a webapp should always check if the connection is ssl and set the secured flag accordingly. For PHP, this could be something like this:

if ($_SERVER['HTTPS']) session_set_cookie_params( 0, '/', '', true, true );

I've recently investigated all web applications I'm using myself and reported the issue (Mantis / CVE-2008-3102, Drupal / CVE-2008-3661, Gallery / CVE-2008-3662, Squirrelmail / CVE-2008-3663). I have some more pending I want to investigate further.

I call security researchers to add this issue to their list of common things one has to look after. I find the firefox-extension CookieMonster very useful for this.

The result of my reports was quite mixed. While the gallery team took the issue very serious (and even payed me a bounty for my report, many thanks for that), the drupal team thinks there is no issue and did nothing. The others have not released updates yet, but fixed the issue in their code.

And for a final word, I want to share a mail with you I got after posting the gallery issue to full disclosure:
for fuck's sake dude! half of the planet, military, government, financial sites suffer from this and the best you could come up with is a fucking photo album no one uses! do everybody a favor and die you lame fuck!

I just read an article about the recent wordpress vulnerability (if you're running wordpress, please update to 2.5.1 NOW), one point raised my attention: The attack uses MD5-collisions.

I wrote some articles about hash collisions a while back. Short introduction: A cryptographic hash-function is a function where you can put in any data and you'll get a unique, fixed-size value. »unique« in this case scenario means that it's very hard to calculate two different strings matching to the same hash value. If you can do that, the function should be considered broken.

The MD5 function got broken some years back (2004) and it's more or less a question of time when the same will happen to SHA1. There have been scientific results claiming that an attacker with enough money could easily create a supercomputer able to create collisions on SHA1. The evil thing is: Due to the design of both functions, if you have one collision, you can create many more easily.

Although those facts are well known, SHA1 is still widely used (just have a look at your SSL connections or at the way the PGP web of trust works) and MD5 isn't dead either. The fact that a well-known piece of software got issues depending on hash collisions should raise attention. Pretty much all security considerations on cryptographic protocols rely on the collision resistance of hash functions.

The NIST plans to define new hash functions until 2012, until then it's probably a safe choice to stick with SHA256 or SHA512.

I recently took the new CAcert assurer test. Afterwards, one has to send a S/MIME-signed mail to get a PDF-certificate.

Having the same problem like Bernd, the answer came in an RC2-encrypted S/MIME-mail. I'm using kmail, kmail uses gpgsm for S/MIME and that doesn't support RC2.

While this opens some obvious questions (Why is anyone in the world still using RC2? Why is anyone using S/MIME at all?), I was able to circumvent that without the hassle of installing thunderbird (which was Bernd's solution).

openssl supports RC2 and can handle S/MIME. And this did the trick:

openssl smime -decrypt -in [full mail] -inkey sslclientcert.key

It needed the full mail, which took me a while, because I first tried to only decrypt the attachment.

09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0
is all I have to say today.

Unter dem Titel »Hieroglyphen, Enigma, RSA - Eine Geschichte der Kryptographie« fanden heute an der Uni Karlsruhe zwei Vorträge, sowie eine anschließende Besichtigung der Sammlung von Klaus Kopacz.

Ich hatte zum ersten mal die Gelegenheit, originale Enigma-Maschinen zu sehen und bekam auch im Vortrag einen Eindruck, wie überhaupt genau der Verschlüsselungsalgorithmus der Enigma funktionierte.

Enigma-Bilder gibt's hier

Wie bereits angekündigt, treibe ich mich gerade auf den Metarheinmain Chaosdays in Wiesbaden rum. Location ist sehr ansprechend in einem Umfeld von grafittiverzierten, teilweise baufälligen Gebäuden und Kunstinstallationen (leider hat sich das Wetter gerade entschlossen, nicht sehr Foto-freundlich zu agieren und es sieht grad auch nicht so aus, als ob's heut nochmal Sonne gibt).

Aufgrund eines Vortragsausfalls habe ich spontan noch meine von der GPN übrigen Folien über XGL/AIGLX wiederverwertet und somit zwei Vorträge präsentiert.

Xgl-Vortrag das übliche staunende aah und ooh, die leidige Frage, was das bringt etc.

Der Vortrag über Passwörter brachte den gewünschten Widerspruch, insbesonder Fukami hielt heftig dagegen und konnte auch einige Dinge anbringen, die ich so noch nicht bedacht hatte, etwa die Frage, was es für Identitätsdiebstahl bedeuten würde, wenn man alle Zugänge per Chipkarten regelt.
Folien: OpenDocument, PDF

Anschließend hatte ich eine kurzweilige einstündige Unterhaltung mit einem Menschen einer wiesbadener Lokalzeitung, der schwer beeindruckt war, was ich ihm alles so erzählte. Insbesondere das »Ich kann deine eMails lesen« schien ihm nachzugehen (mit Live-Präsentation via Wireshark).

onlinetvrecorder, a service that let's you record broadcasts from some german television stations, provides it's files in .otrkey-format, which can be decoded using their binary otrdecoder-tool, considering you have requested the recording in advance.

As there is no information how the format and authentication work, I had a deeper look at it.

Getting the key

Using some network sniffer, the authentication is very simple, it just requests them with http, the URL is
http://www.onlinetvrecorder.com/uncrypt.php?email=[email]&pass=[pass]&filename=[file]
(filename is the .wmv-name without otrkey)
Inside that file is an ascii/hex-encoded number with 128 bit. That very much looks like a key.

This already gives us the possibility to manually download the key and, if we want to re-decode some movie (because we lost the wmv or because we want to decode a file before it's completely downloaded to already start watching the recording), save the key to a local webserver as uncrypt.php, forward the hostname to 127.0.0.1 and re-start otrdecoder.

The cryptography

From what I found out yet, the file is encrypted with some sort of blowfish. The encrypted and decrypted files are exactly the same size, that means we have no IV and a variant of blowfish that does no padding.

The best I got till now was using mcrypt with ecb-mode:
mcrypt -d -a blowfish-compat -s 16 -o hex -b --noiv -m ecb --nodelete -f [keyfile] [file]

This decrypts the first 256 bytes correctly, after that it seems to mix up things (the correct decryption continues at byte 512). From what I read in Schneier[1996] (»Applied cryptography«), there is an ecb variant using ciphertex stealing that avoids padding. I found no easy-to-use implementation of that.
Having a commandline-cryptography tool that supports more options than mcrypt would be handy here.

Today I held a talk about »Technical defense against surveillance« on an event with rather non-technical visitors.

I noticed that we still really have a lot of problems when providing easy-to-use security.

Things like "yes, you can do gpg with jabber, but only with a few clients, there's also another thing called otr, that's better from a cryptographic point of view but it is not based on the gpg-key-infrastructure and it's also only supported by some (other) clients" are really horrible to say if you always fear that nobody understands you.

A short list of things that came me to mind:
- I found no easy way on encrypting partitions with linux. Maybe I missed something, but I googled for it, tried it in ubuntu, found nothing. Had to tell them "there are some console-apps, dm-crypt, cryptsetup, etc.".
- Apps should enable ssl by default. Servers should forbid login without ssl. No more pop3, smtp, imap, jabber, webmail, whatever-web-login without ssl-encryption.
- Jabber should have a standard for encryption, based on gpg, with the cryptographic features of otr.
- We need to get rid of all unsecure algorithms (MD5, SHA1, RSA/DSA/ElGamal with 1024 bit) by default (yes, I know I said this hundred times before). GPG still creates 1024bit DSA-keys.
- Things like tor could be integrated into distributions, to be enabled by a click or similar.

Just some random ideas. It is possible to create much more secure systems. We just need to do it.

(And to not only cry, I hope I'll find some time and motivation to push some of the things I suggested in the near future)

Second day, finally uploaded some pictures and just found some time to blog between two talks.

Yesterday the We lost the war talk. Maybe I'll write something more in german when I find time for it. In short: IMHO this was an obscure mixture of political nonsense. This should at least be clear when reading the article with similar content in the last »Datenschleuder«, where the author claims something like »till 9.11. hackers ruled the world and everything was good« (to cite, »The big corporations were at our merce, because we knew what the future would look like and we had the technology to built it).
Lars wrote very drastically about it.

Today, the first interesting talk was5 Thesis on Informational-Cognitive Capitalism. I think I didn't really get what the autor wanted to say (surely related to missing sleep and lack of motivation to listen to english), but he was at least quite entertaining.

Next was Hashing Trusted Computing by Rüdiger Weis, as always quite funny, Rüdiger maybe should become the first professional math comedian. The content is obvious, at least for regular readers of my blog: Trusted Computing is evil and SHA1 is broken.

There was a nice presentation by fukami and Markus Beckedahl about the Sony BMG rootkit. They presented a lot of information, Markus has also collected it in his blog.

Next one was Technological art off the trodden tracks by two media artists that presented art which is related to hacking subjects and suggested that media artists and hackers come more together to share thoughts and projects. I hope they'll put their materials online, they had a lot of videos from nice stuff.

Just came from Learning cryptography through handcyphers by Benno de Winter. It was a basic introduction to some simple algorithms, not really new to me, but the speaker was worth watching because of the fun factor.

More to come.

Just arirved at the 22th chaos communication congress. Together with Lars I took the Nachtzug from Augsburg.

We are in a very nice hostel called Generator Hostel, which is very nice for a quite moderate price. Although we arrived at 8 o'clock in the morning, we already could enter our rooms and get a breakfast on arrival day. Very recommendable.

Pictures will follow from time to time.

Bruce Schneier writes about Phishing attacks and that he wants financial companies to be responsible for phishing attacks.

This brought me to some thoughts about online banking security and secure authentication in general.
Today, most online banking goes through web interfaces. That's really horrible in the sense of security. I remember when I asked my local bank for an online banking account, they told me "hey, you just need a web browser to do this". They have better alternatives (HBCI), but they don't promote them to their normal customers.
With a web-interface, you only have a one-way-authentication (the user authentificates itself to the bank, but the bank doesn't) and that's the whole thing why phishing works. If there would be any mechanism that verifies the authenticy of the bank for the user (or, to be exact, his applications, because we all now that average users don't manage to do so), the whole phishing-stuff would be senseless.

Even the less secure variant of HBCI with keyfiles is much more secure than web-interfaces. For a successfull phishing-attack, a user would have to upload his keyfile - which he usually won't do, because he doesn't know where it is. But the most obvious way: Smartcards.
Smartcards can be a fine solution for various security problems - and it's not much more complex. Everyone knows that he has to put his bank card into a cash terminal, so why shouldn't the average user be able to put it in a computer slot? But hey, it's even hard to get smartcard-drives - I once asked in the Saturn (big german technology market), they don't sell them at all.
The right thing would be having smartcard-drives in computers by default - and having chipcards for various security-applications.

HBCI, for the ones who don't know, is a german standard for online banking - I wonder why there is no word-wide online-banking-standard yet - with a secure, open design and based on two-way-authentication, together with some easy-to-use standard applications for online banking installed on every PC. That would really help a lot.