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.

I visited this year's easterhegg in Munich. The easterhegg is an event by the chaos computer club.

I held a talk expressing some thoughts I had in mind for quite a long time about free licenses. The conclusion is mainly that I think it very often may make more sense to use public domain "licensing" instead of free licenses with restrictions. The slides can be downloaded here (video recording here in high quality / 1024x576 and here in lower quality / 640x360). Talk was in german, but the slides are english. I plan to write down a longer text about the subject, but I don't know when I'll find time for that.

I also had a 5 minute lightning-talk about RSA-PSS and RSA-OAEP, slides are here (german). I will probably write my diploma thesis about PSS, so you may read more about that here in the future.

From the other talks, I want to mention one because I think it's a very interesting project about an important topic: The mySmartGrid project is working on an opensource based solution for local smart grids. It's a research project by Frauenhofer ITWM Kaiserslautern and it sounds very promising. Smart grids will almost definitely come within the next years and if people stick to the solutions provided by big energy companies, this will most likely be a big thread to privacy and will most probably prefer old centralized electricity generation.

After reading a lot about interesting stuff happening at this years FOSDEM, I decided very short term to go there. The FOSDEM in Brussels is probably one of the biggest (if not the biggest at all) meetings of free software developers. Unlike similar events (like several Linuxtag-events in Germany), it's focus is mainly on developers, so the talks are more high level.

My impressions from FOSDEM so far: There are much more people compared when I was here a few years ago, so it seems the number of free software developers is inceasing (which is great). The interest focus seems to be to extend free software to other areas. Embedded devices, the BIOS, open hardware (lot's of interest in 3D-printers).

Yesterday morning, there was a quite interesting talk by Richard Clayton about Phishing, Scam etc. with lots of statistics and info about the supposed business models behind it. Afterwards I had a nice chat with some developers from OpenInkpot. There was a big interest in the Coreboot-talk, so I (and many others) just didn't get in because it was full.

Later Gentoo-developer Petteri Räty gave a talk about "How to be a good upstream" and I'd suggest every free software developer to have a look on that (I'll put the link here later).

I've just attended a rather interesting talk about 3D-printers like RepRap and MakerBot.

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.

When asking me what I'd consider the most interesting technical developments in the near future, electronic books would be on the top of my list. So recently, I finally decided to buy one and ordered a Hanvon WISEreader N526. It has a pretty fair price, it seemed that free software support was likely to appear some time in the future (more on that later) and it has a touchscreen with pen, which was a feature I wanted to mark things in books.

From the hardware side, the device is pretty ok. Most ebook readers on the market share the same technologie for the display, it could have a bit more contrast, but else it's pretty okay. The device itself has a keyboard (which is querty, but not really ordered like a querty-keyboard), USB (not working as mass storage though), an audio output and a micro SD slot. Also, as said above, it has a touchscreen that can be used with a pen. So on the hardware side the device is quite fine.

What's not fine is the software running on it. It makes many features pretty much useless. Just to name a few flaws:

• Adding marks with the pen, one of the main features of the hardware, is pretty useless. It works neither on PDFs nor on epub files. It only works for TXT and HTML files, so it's not possible to do any marks on any layouted file format.
• HTML files are not supported. The vendor claims HTML support, but that's a plain lie. What it does is stripping out all HTML tags and showing the Text. If you know how HTML works, you can expect that this leads to pretty broken results and breaks all layout in HTML. Also, Hyperlinks don't work at all.
• The zooming capabilities are very limited. For text, you only have three zoom levels. All of them are far larger than normal text in a book. For PDF, it's possible to make it fit on height or width, but not anything in between.
• If you browse the files, there is no possibility to show the full filename, it only shows the beginning of the filename (about 20 characters). If you have files named “Author's name – Book title“ (which seems like a pretty common idea), you will only see some files with the author's name – not very useful.
• The device has a button for landscape view (turn the view 90°). But it doesn't work. Probably a bug.

I fell pretty angry about that. I'm not sure what to do yet. I have a 14 day return right and I seriously consider taking that opportunity. On the other hand, all of the issues are software issues. As this is a rather new device, it may very well be that the software is in an early state and issues get resolved soon. My problem is: I don't know that.

Another thing I'm looking at is OpenInkpot. It's a free firmware for ebook devices and they are working on support for the N526. However, having talked to the developers it seems that support for the touchscreen/pen is pretty unsure, as the vendor refuses to provide any documentation for that. Also, as this is a volunteers project, it's not clear if and when proper support will be available.

Today I faced an interesting Linux problem that made me learn a couple of things I'd like to share. At first, we found an issue on a Thinkpad X301 notebook that was fixed in a newer BIOS version. So we wanted to do a BIOS update. Lenovo provides BIOS updates either for Windows or as bootable ISO CD-images. But the device had no CD-drive and only Linux installed. First we tried unetbootin, a tool to create bootable USB sticks out of ISO-Images. That didn't work.
So I had a deeper look at the ISO. What puzzled me was that when mounting it as a loopback device, there were no files on it. After some research I learned that there are different ways to create bootable CDs and one of them is the El Torito extension. It places an image of a harddisk on the CD, when booting, the image is loaded into memory and an OS can be executed (this probably only works for quite simple OSes like DOS, the Lenovo BIOS Upgrade disk is based on PC-DOS). There's a small PERL-script called geteltorito that is able to extract such images from ISO files.
It's possible to boot such harddisk images with grub and memdisk (part of syslinux). Install syslinux, place the file memdisk into /boot (found in /usr/lib/syslinux/ or /usr/share/syslinux/) and add something like this to your grub config:

Or for grub2:

Now you can select bios update in your boot menu and it should boot the BIOS upgrade utility.

(Note that this does not work for all Lenovo BIOS updates, only for those using an El Torito harddisk image - you can mount your iso with mount -o loop [path_to_iso] [mount_path] to check, if there are any files, this method is not for you)

I'm currently in Scottland on a trip through the UK. I'm trying to get some contacts to the much more active environmental movement here. For those who don't know, the UK has probably the most active climate movement in the world. I just came from a gathering in the Lake District and now I want to visit a protest site against open cast coal mining in Mainshill.

Afterwards I'll visit the Climate Camp.

It's quite interesting to see discussions here. The main topics at the moment are the third runway at the heathrow airport (see e. g. Plane Stupid) and the building of a new coal plant in Kingsnorth (done by the german company e-on). I heared quotes like »we shouldn't wait till they build the new plant, they're burning coal every day in the existing ones«, which is a large difference compared to the discussion in germany.

After passing the second exam at the Linuxtag, I'm now officially allowed to call myself LPIC-1.

A couple of projects exist for alternative router firmwares. I used to work with Buffalo Routers combined with DD-WRT.

Now DD-WRT became quite unusable for two reasons. First there was a Cross Site Request Forgery reported on bugtraq a while back, where one of the DD-WRT developers answered in a way that clearly showed he doesn't really understand what CSRF is - so already from a security point of view, DD-WRT seems to be a no-go.

Beside, DD-WRT development more or less is stale at the moment - there are commercial spin-offs and there's been some controversy if everything they did was compliant to the GPL. Fact is there were no new releases since several months - with open security bugs.

Now I've been looking for alternatives. What I'm looking for should be

• a ready-to-use router firmware with easy web-interface configuration from the start, not something like OpenWRT
• free software
• obviously, a project that handles security-reports in a sane way

For now, Gargoyle the only one suitable. It doesn't officially support my Hardware, but it works anyway. I haven't looked deeper into it (e. g. didn't do any security analysis myself), but it seems to do the basic tasks. If you have suggestions of other projects, please leave a comment.

This news sounds sensational for all fans of old adventure video games: A new episode of Monkey Island is planned. Ron Gilbert blogged about it a few days ago.

For those who don't know, a very short history of the game series. The first two Monkey Island games were already classics when I played them the first time. In super-pixel graphics, but with an ingenious humor. Already with the third part, many fans were sceptical. Graphics got better, but not 3Dish, which was already pretty common at that time. They even made fun of the tendency to bring all games to 3D back then - they had a 3DFX option, but clicking on that only gave you some sarcastic comment. At least I can say that I found Monkey Island 3 (The Curse of Monkey Island) a deserved successor of the series.

With Monkey Island 4 (Escape from Monkey Island), things got much worse - it had 3D graphics (ugly ones in my opinion) and - probably worse - it completely changed the control. All classic adventures were point and click adventures through the famous SCUMM engine (although the control has changed quite a lot over the time). There even was a SCUMM bar in the first game.
Part 4 had some kind of keyboard control. And the controlling was really bad. So this was the first game in the series I didn't play till the end.

I'm excited to see how the new game will be. It will be released in episodes, I don't know if that's a good idea, but we'll see. I haven't found any information about the controls on their webpage.

Maybe it's worth raising a petition for a Linux version? Seems they don't intend to plan one, though it might be a good idea, as probably a lot of Linux users are retro gaming fans as well.

Tobias Scherbaum already blogged this, but only in german, so I'm writing this again for the Planet Gentoo readers.

A german webpage called jugendschutzprogramm.de provides filters for webpages potentially dangerous for children. Now some people noticed that this page considers quite a lot dangerous.

Both gentoo.de and gentoo.org are considered only suitable for people over 14. So if you ever thought about installing Gentoo on the PC of a kid, think again what you might do to that kid.

Beside, my blog is even more dangerous: It's blocked by default.

The page is supported by a couple of companies providing pornographic content. Interesting enough, it's also supported by a big german Newspaper (BILD) that regularly has pornographic images on their frontpage. However, their page is considered harmless.

But what's really frightening is that jugendschutzprogramm.de is part of ICRA, an international system by big content and internet providers. It's even supported by the european union.

Update: Page has XSS, maybe someone wants to play with it?

<form action="http://jugendschutzprogramm.de/webmaster/label-generator.php" method="post">
<input name="URL" value='"><script>alert(1)</script>' type="text">
<input name="submit" type="submit">
</form>

Before I start my review about the movie, I'd like to give some preface about my connection to Star Trek. Although I occasionally watched the series for a long time, I really started getting interested at the worst possible moment - shortly after it was announced that the last series »Enterprise« was stopped (although there were petitions and rallies - I just noted a bit too late to take part).
So with the last series stopped and the last film »Nemesis« being a flop, it was quite unlikely that Star Trek would continue at all in any way. So the only thing left was experiencing the vast majority of past series (which I'd suggest everyone to do - my favorite is Deep Space 9).

So the message that there should be a new film was surprising and promising. Though from the beginning, I was quite sceptical - the concept of a prequel to the original series with new actors for famous roles seemed difficult. It rarely happened in the past that different actors played the same person in the Star Trek universe and it was only the case for side roles (e. g. Ziyal in DS9, Zefram Cochrane in TOS/ST8). But what was even more disturbing was the director J. J. Abrams - with movies like Armageddon I didn't find him very predestined for this job. But as I read some quite positive reviews, I gave the movie a chance and went to the cinema on the first day.

To give a conclusion: I was absolutely right not to expect much from the film. It is a middle-class Hollywood action movie and has just nothing from the Star Trek spirit I liked so much.
The no-gos are countless. I mean, product placement is a pity in films any way, but in a Star Trek movie? And have you ever heard a pop song from the 90s in ST? (Oh, you remember that scene from ST4 in the bus? Has the guy inventing that scene with Kirk in the car ever seen that movie?)
The film introduces lot's of characters from other ST stories without any relation. Soval (was the name even mentioned?) has just nothing of the person known from TOS/TNG. Those Romulans - they look different, their ships look different, there's no connection to any previous Romulan story, it just seems like a randomly picked species name. And the old Spock - yeah, every real Trekkie likes to see Leonard Nimoy is still able to play his role. But if you remember the last time Spock appeared in the ST universe - a plot in TNG with an underground resistance movement on Romulus, where Spock stayed - a quite open end - it's just predestined to continue telling that story. ST11 doesn't do that.
Then there's this thing with the parallel time line - parallel time lines are a common story methodology in Star Trek, so the idea has potential. But it seems it's just there so there's no need to stick with the Star Trek story too much - every mistake can just be explained as something happening in the alternative time line. It didn't really make any sense to me beside that.

Well, maybe the buzz around the movie opens perspectives for new Star Trek material in the future - and hopefully with more talented directors behind the scenes. Till then, I'll watch some episodes of Hidden Frontier.

Update: Only german, but nice review (WOZ).

A common way to check the health state of a hard disk is SMART. It gives various informations about occuring errors. In Linux, there's the smartmontools package containing tools to read SMART data of hard drives (smartctl -a /dev/[hddevice] gives you a bunch of information).

I found it always frustrating that SMART didn't work with USB drives. It's a standard bound to IDE/ATA. Although common USB-drives are internally IDE/SATA, sending the SMART commands to the drive requires proprietary extensions. But now, the smartmontools-developers have included support for some USB drives. It worked with the USB HDs I had available for testing.

There's no release yet containing the USB-support. If you're on Gentoo, you can fetch a live-CVS ebuild here.

In the last weeks, I made a study research project at the EISS at the University of Karlsruhe. The subject was »Session Cookies and SSL«, investigating the problems that arise when trying to secure a web application with HTTPS and using session cookies.

I already wrote about this in the past, presenting vulnerabilities in various web applications.

One of the notable results is probably that ebay has just no measurements against those issues at all, so it's pretty trivial to hijack a session (and use that to do bids and even change the address of the hijacked account).

Download »Session Cookies and SSL« (PDF, 317 KB)