A new take on autogenerated passwords

Today’s XKCD got me thinking about the strength of my own passwords again. Some time ago, XKCD already hit on the topic of password reuse.

A major argument for reusing passwords is that one can’t remember dozens of passwords for all services one uses. The typical counter-argument then is that one can use a password storage, be it a local application like KWallet or an online service. Such services allow you to protect multiple different passwords with one master password, which is the only one which you have to remember.

I am personally a user of KWallet, and must agree that it’s a great relief to have a backup for this crucial data available anytime. (Currently, KWallet stores over 200 passwords on my notebook alone, and there are probably unmerged passwords over at my desktop.)

But alas, both kinds of password storage solutions have a big problem: KWallet and friends are useless when you don’t have the wallet file around on the computer which you are currently using, you’re stuck. If the only computer carrying the wallet file gets broken, you’re totally lost. On the other hand, online storage solutions require a big deal of trust towards the provider running the service. As we saw earlier this year with LastPass, this trust is in general not justified.

So what can be done? I just had an idea which I did not see before anywhere. (Might be that I did not look closely enough. Please tell me if this idea has already existed before.)

If we don’t want to store passwords (because that requires both the availability of the storage and trust with a provider of this available storage), we need to generate them based on an algorithm. In other words,

#!/usr/bin/env python2

import base64, getpass, hashlib, subprocess, sys

def doHash(x):
    return base64.b64encode(hashlib.sha512(x).digest())

def sendToXClipboard(x):
    subprocess.Popen(["xsel", "-i"], stdin=subprocess.PIPE).stdin.write(x)

try:
    site = sys.argv[1]
except IndexError:
    sys.stderr.write("Usage: %s [domain]\n" % sys.argv[0])
else:
    masterPassword = getpass.getpass("Password: ")
    sitePassword = doHash(doHash(site) + doHash(masterPassword)) # variant 1
    sitePassword = doHash(site + masterPassword)                 # variant 2
    sendToXClipboard(sitePassword)

This Python script reads the name of a website, and prompts for a master password. It then combines both using a considered-secure hashing algorithm (SHA-512 in this case), and sends the Base64-encoded result of that to the X clipboard (so the password won’t be displayed on screen). Base64 is the best compromise between printability and string size.

The code shows two incompatible variants of obtaining the sitePassword. I won’t debate over which is better. The extra hashes in variant 1 are, strictly speaking, security by obscurity, as they don’t help when the attacker knows the algorithm. However, that’s not the main security feature. As far as I can see, this algorithm relies solely on the strength of the SHA-512 algorithm, which is (as of August 11, 2011) considered secure, and (if the attacker is brute-forcing) on the strength of your master password. So don’t choose “correcthorsebatterystaple”. 😀

Proof of concept systemd dataengine for Plasma

What you see here is the very first steps towards systemd integration in Qt. I’ve started to build a libqsystemd, which wraps systemd’s DBus API into something which can be used by Qt applications. The screenshot shows a simple QML-based Plasma applet reading information about available systemd units from a simple dataengine.

At the moment, the library can only list available units, providing about 60% of the info which you would get from `systemctl list-units`. But adding more functions should be trivial now that the foundations are laid.

The only interesting point left is how different privilege levels will be handled. For example, only root may activate and deactivate units, initiate system shutdown etc. Most properties are even read-protected from normal users.

Of course, providing a library interface is only the first step for systemd integration with KDE. The second step is to actually use it. For example, systemd provides standard interfaces for setting the hostname, timezone, etc. in a desktop-independent manner. systemd can in the future also be used to coordinate the startup of a KDE session, and thus replace parts of startkde and kdeinit.

KDE Games: Towards an “Active” interface

The fact that KDiamond is included by default in Plasma Active’s default set of “Favorite applications” (among rekonq-active, calligra-active, and friends) finally made me hack a bit on kdegames stuff again. The main problem I see with KDiamond on a mobile form factor is that menubar and toolbar waste quite some vertical space. Also, the menubar is awful to use on a touchscreen; the toolbar is much better in this regard.

Can we combine these observations into an interface that saves space, yet is as approachable as a simple toolbar? We can.

In the back is the normal menubar/toolbar chrome. In the front is my first draft of an “Active” version of it. The menus “Game” and “Move” are completely gone, all contained actions are now on this first level of the toolbar. The “Settings” and “Help” menus have turned into toolbar buttons. Upon pressing one of these, the toolbar descends into that subcategory:

After selecting something from a subcategory, the toolbar automatically returns to the default category. For example, if you click on “Settings”, then on “Configure KDiamond”, the theme selection dialog comes up. When you’re done with that, you come back to the main window and find the default toolbar with the relevant New/Pause/Hint actions again.

What do you think? A first step in a good direction? Something you would even want on the desktop? Or just plain awful? Please let me know. BTW the source is available on ReviewBoard.

P.S. To get that straight: This is only for games with a small set of menu actions (about 28 of 40 KDE games, according to my counting). Apps like KGoldRunner or KTuberling just don’t fit the idea behind this proposal and will therefore not be affected.

P.P.S. I’m aware that vertical space is still wasted. I’m going to experiment with moving the toolbar to the side for displays which are wider than tall.

Case study: Porting and modularizing an in-house Python application

Is it just a feeling, or has the number of technical posts decreased on the Planet? I definitely need to change that! (Update: The post got quite long, so I’ve shortened the syndicated version.)

These days, I’m usually working on my Diplomarbeit at the Institute of Theoretical Physics at the Technical University here in Dresden. (A Diplomarbeit is about comparable to a master’s thesis, though preparation time is one year since there was no bachelor’s thesis before it.) Our working group has an in-house application for inspecting iterated functions, which is quite intuitively called Iterator. Like many scientific applications, it has on one hand a very sharp functional objective, but contains tons of different tools and plugins.

As a part-time project besides my usual work, I’m working on a Qt port of the Iterator, which is currently based on wxWidgets. Of course, a port offers the opportunity to refactor badly engineered parts of the application. It clearly shows that all involved developers are first and foremost physicists which have not received any formal training in software design. Many antipatterns can be observed in the code. The most interesting is the existence of a god class called IteratorApp.

Implicit cast quirks

I thought I let you know why I just had to throw away three days worth of computation data.

double importantPrefactor(bool freeEvolution);

void multistep(bool freeEvolution, /* ... */)
{
    /* ... */
    const double pre = importantPrefactor(free);
    /* ... */
}

Yes, I used the wrong identifier inside the multistep function. Still it compiles and runs without error (except for the garbage data that comes out), because there’s a goddamn implicit cast from void(*)(void*) to bool. If you don’t believe this, try this:

qDebug() << "Is there a goddamn cast?" << ((bool) ::free);

Of course the conversion gives true because the function pointer is not null. Argh!

Review: Plasma Active on openSUSE 11.4 on WeTab

[@Plasma developers: Please find my short wish list for the Plasma tablet shell near the end of this article.]

My followers on Twitter already had the news yesterday: I’m a proud owner of a brand-new WeTab. WeTabs seem to be going out of stock at most shops, so one can get very good deals here in Germany. It has 32 GB of internal storage, a 16:9 HD display (1366×768, 12″), 3G, GPS, and an 1.6 GHz Atom processor.

Of course I wanted to put Plasma Active on it. The preinstalled WeTab OS is based on Meego 1.0 (and includes shell access for experts), but Plasma Active seems to require Meego 1.1. The simplest way to go for me was to install openSUSE 11.4. Here’s how I got it working:

1. Some early WeTabs have their BIOS locked such that they cannot boot from USB. In this case, one must flash the BIOS. Since my WeTab is new, this step was not required here.
2. The preinstalled bootloader does not have a menu and boots straight into the first hard disk partition (i.e. WeTab OS). I followed steps 4 through 8 from this installation guide from the Meego Wiki to put a custom bootloader inside the existing bootloader (as a chainloader). This custom bootloader allows to boot from a USB stick, as described in steps 10 and 11 of the Meego installation guide.
3. On to actually booting the installation media: I chose the KDE4 Live Image of openSUSE 11.4, and followed the advise of this (as of now unfinished) German installation guide for Plasma Active on openSUSE 11.4 on WeTab. Especially, there are important hints in there about how to get the touchscreen working properly. It also has instructions for which repos to add and which packages to install to get Plasma Active.
4. The touchscreen is not calibrated properly by default. I haven’t yet found a calibration tool, but the WeTab Wiki offers some help in their installation instructions for Ubuntu Maverick. Grep for “calibration” on that page, and save the file there on the openSUSE partition as “/etc/X11/xorg.conf/99-calibration.conf”. After a reboot, the touchscreen is calibrated fairly well.
5. Of course, some adjustment in KDE System Settings is necessary. For example, I found a font size of 12pt to be just right to enlarge buttons etc. to a sensible size.
6. If you installed besides WeTab OS as the openSUSE install guide suggested, you might want to boot into WeTab OS. To do so, edit the file extlinux/extlinux.conf on the sda1 partition (i.e. the WeTab OS’s boot partition), and move the line “menu default” from the “plop” chainloader entry to the WeTab OS entry. The WeTab can then be booted from openSUSE’s Grub by selecting the “Linux other” option with the soft button in the same way the selection worked in plop (tap = next entry, hold = select entry).

So, how well is Plasma Active working? Very well for a project that young! Here are the main problems I’ve found as of now (partly plus workarounds), in no particular order:

• The acceleration sensor is not recognized, so the screen is not rotated when I rotate the device. Screen rotation itself works, using the script from this wetab-community forum entry. (It’s basically xrandr -o, plus some calls to evdev to keep touchscreen and screen coordinates in sync.) To make it a bit more convenient, I created a directory with four scripts in them which invoke the above script with one of the four possible orientation arguments. Then I pointed a folderview applet to this directory, so I have screen rotation accessible my desktop.
• Plasma’s screen keyboard does not vanish automatically in some situations, and does not work at all for non-standard or non-Qt widgets. For example, it does not appear when I tab into Konsole.
• KScreenLocker does not know about the form factor, either: It wants me to enter my password, so I would have to carry a USB keyboard with me if I locked my screen or sent the tablet to sleep or hibernate. (Same problem with KDM. The openSUSE install guide recommends enabling autologin for this reason.)
• The Plasma shell seems to have some screen-locking functionality which is active when it comes up the first time after boot, but I haven’t yet found a way to lock the screen at my wish.
• The Plasma shell won’t react to any xrandr changes, esp. when I change the screen orientation.
• When I restart the plasma-tablet process by hand, the root window comes up with the right size, but the font size in applets is absurdly big. It seems that it calculates the font size from the screen height only, not taking into account the relatively small screen width on the then 9:16 display.

It may very well be that the packaged version which I installed is just much too old. Anyhow, here’s a short wishlist to the Plasma Active developers. These are my most urgent wishes:

• Please make KScreenLocker’s interface touchscreen-compatible, for example by using a PIN entry or, as a bare minimum, by giving it a screen keyboard.
• Please let the Plasma shell react to xrandr changes.
• Please include an alternative vertical applet layout for screens which are higher than they are wide.
• Please, as a temporary measure, add a button to toggle the virtual keyboard permanently, for situations where it does not yet come up automatically (like in Konsole).

And another thing that bugged me: The “Present Windows” effect feels very good for window switching, but it is a bit unnatural that the Plasma shell, i.e. the “desktop”, is another window in this interface. I would find it more intuitive if:

• the window overview showed only actual application windows
• the top-left button would not disappear in this overview
• clicking this button from the overview would bring up the desktop instead

The desktop is then accessed by pressing the top-left button twice. (Maemo 5 does something similar.) If there is only one active window, the window overview does not make sense, so the desktop might be displayed after the first click already.

These thoughts conclude the collection of my first impressions with Plasma’s new tablet shell. It may sound quite negative, but these are only small problems compared to how much works so great. I’m looking forward to these small problems being ironed out by an awesome team of developers. Or, to pun it another way (ha!): Gnome may, by their own claim, be “made of easy”, but KDE is made of awesome!

Optimization tricks: Fast sqrt(x^2 + y^2)

[Before I get to the boring (hah!) numerics stuff, some news: In order to test KDE Games on a touchscreen, and because I’ve wanted a tablet for a long time now, and because I want a 3G device, I’ve now ordered a WeTab 2. More news on this coming up soon when I have it in my hands.]

I’ve been optimizing my favorite jigsaw puzzle game Palapeli lately. Today, I looked at the bevelmap generation algorithm which renders the nice three-dimensional shadows atop the jigsaw pieces. There are a lot of norm computations in there, i.e. sqrt(x^2+y^2). All bells are ringing: There must be a way to optimize this.

Now nearly everyone who has to do with numerics and programming probably knows about the fast inverse square root which approximates 1/sqrt(x) very efficiently and sufficiently precise (about 1% maximum error). Using the inverse of this fast inverse square root does not really give an improvement, though. After all, the formula 1/InvSqrt(x*x+y*y) contains at least four floating-point operation plus everything that happens in InvSqrt.

This approach is especially inefficient because, in my special case, x and y are integers, and the result is also needed as an integer. Looking around the interwebs, I’ve found this lovely page on square root calculation, which also has a special algorithm for norms.

It all starts with two approximations to sqrt(x^2+y^2). The first one is max(abs(x), abs(y)), the second one is 1/sqrt(2)*(abs(x) + abs(y)). We need both because they are good for different values of x and y. To understand this, consider the unit circles of these approximations, that is: the set of x/y points where the approximation is 1. (You will probably make a sketch as you follow the discussion. I would have done one if it wasn’t so late already.) The unit circle for the first approximation is an upright square, while the second approximation’s unit circle is diamond-shaped (i.e. turned around by 45° compared to the first one).

An approximation is good when the unit circle comes nearby or touches the actual unit circle. For the first approximation, this happens when either x or y vanishes. The second approximation, on the other hand, is good when x and y are approximately equal. Now one can show that, at these conditions, the better approximation is always bigger than the other one. This means that we can define a third approximation by taking the maximum of both approximations. The unit circle for this approximation is a regular octagon, whose inscribed circle is the actual unit circle.

The approximation is thus always too big, except for the eight touching points of octagon and real unit circle, where approximation and exact result are identical. However, one can find a factor z such that the octagon, scaled by 1/z, is inside the circle. Scaling the approximation by (1+1/z)/2 thus distributes the approximational error to both the negative and positive side. Taking all these considerations into account, I’ve arrived at the following implementation:

template<typename T> struct fastnorm_helper { typedef T fp; };
template<> struct fastnorm_helper<int> { typedef qreal fp; };

//Approximates sqrt(x^2 + y^2) with a maximum error of 4%.
//Speedup on my machine is 30% for unoptimized and up to 50% for optimized builds.
template<typename T> inline T fastnorm(T x, T y)
{
    //need absolute values for distance measurement
    x = qAbs<T>(x); y = qAbs<T>(y);
    //There are two simple approximations to sqrt(x^2 + y^2):
    //  max(x, y) -> good for x >> y or x << y          (square-shaped unit circle)
    //  1/sqrt(2) * (x + y) -> good for x = y (approx.) (diamond-shaped unit circle)
    //The worse approximation is always bigger. By taking the maximum of both,
    //we get an octagon-shaped upper approximation of the unit circle. The
    //approximation can be refined by a prefactor (called a) below.
    typedef typename fastnorm_helper<T>::fp fp;
    static const fp a = (1 + sqrt(4 - 2 * qSqrt(2))) / 2;
    static const fp b = qSqrt(0.5);
    const T metricOne = qMax<T>(x, y);
    const T metricTwo = b * (x + y);
    return a * qMax(metricOne, metricTwo);
    //idea for this function from http://www.azillionmonkeys.com/qed/sqroot.html
    //(though the equations there have some errors at the time of this writing)
}

[License: I grant any entity the right to use the above code snippet for any purpose, without any conditions, unless such conditions are required by law. (This is the best approximation to placing the code in the public domain, which is not possible in my jurisdiction.)]

I have tested this function successfully on random input with T = double, float, int32_t. For integer types, this function needs only two floating-point multiplications, and thus runs much much faster than the trivial implementation and the InvSqrt-based solution. So please take this as my contribution towards Green IT, and reduce the time your computer spends calculating norms.

P.S. The extension of the above function for three-dimensional coordinates remains as an exercise to the reader. The only hurdle is to calculate the new prefactor z.

Update: As correctly pointed out by the commenters, if all you want is to compare the norm to some radius, e.g. sqrt(x*x + y*y) > r*r, the easiest solution is to avoid the square root and test for x*x + y*y > r*r instead.

Tip of the day: Speed up `locate`

The locate command line tool from findutils is great when you forgot where you dropped that file you worked on a week ago, but don’t want to run Strigi (plus Strigi does not index the system files). However, its output is quite convoluted when you’re looking by topic instead of exact file name.

$ locate tagaro | wc -l
4977

Looking at the output of locate without the wc, there’s quite some garbage in there. For example, my backup and files in build directories, which I am certainly not interested in. Of course there is a way to exclude these from the listing, by editing “/etc/updatedb.conf”. By default, this contains the following on my Arch system:

# directories to exclude from the slocate database:
PRUNEPATHS="/media /mnt /tmp /var/tmp /var/cache /var/lock /var/run /var/spool"

# filesystems to exclude from the slocate database:
PRUNEFS="afs auto autofs binfmt_misc cifs coda configfs cramfs debugfs devpts devtmpfs ftpfs iso9660 mqueue ncpfs nfs nfs4 proc ramfs securityfs shfs smbfs sshfs sysfs tmpfs udf usbfs vboxsf"

As you see, quite some stuff is already excluded from locate’s database, like removable devices under /media, temporary data and virtual filesystems. Apart from these defaults, I’ve also added my global build directory /home/tmp/build and my backup drive to the list. Let’s apply the changes and see if this helps:

$ sudo updatedb
$ locate tagaro | wc -l
1656

An impressive improvement! But we’re still not there: Nearly a third of the output comes from the Git source control system which Tagaro uses. Paths like “/home/stefan/Code/kde/tagaro/.git/objects/b4/3cc4cc0bdc6c92b94655b8352c3073e8d3842d” are also useless, but how can we purge these? PRUNEPATHS only filters directory paths, but `man updatedb.conf` reveals there’s another configuration parameter which specifies directory names to be ignored. So let’s add this to /etc/updatedb.conf:

PRUNENAMES=".bzr .hg .git .svn"

This filters the most important types of VCS data directories. Again, let’s check if it helps:

$ sudo updatedb
$ locate tagaro | wc -l
1080

A reduction of over 75%! Now locate shows only output which is relevant. Also, the locate database has shrunk by 60%, as has the execution speed of locate. By the way, results are even more on the spot when you give the “-b” switch to locate. locate will then print only those files and directories whose name (instead of path) contains the given key. “locate -b tagaro” gives only 25 results here.

Now on Twitter

My last post was quite big, so I’ve split out the news part to ensure that it gets some attention. I’m now on Twitter as @stefanmajewsky. Follow me for updates on my KDE development, esp. Palapeli and Tagaro. My blog posts should also be syndicated there automatically; this post is the test balloon.

Palapeli: Multithreading, memory usage and interface

The Blue Wonder Meeting last week was an excellent opportunity to do some work on Palapeli. One thing that I wanted to do for at least a year was to rewrite the multithreading code around the (fairly central) Palapeli::Puzzle class. The new class has an aspect-oriented design, where single components of the puzzle (like the metadata or the contents) are always made available by worker threads, by casting existing components. For example, a puzzle file can be casted into metadata by reading the latter from the puzzle file. The possible casting paths are actually so convoluted that I documented them in an image inside the source code directory:

Yet there are still areas where Palapeli’s concurrency needs to improve. Much of the puzzle loading is done in the GUI thread, which causes the loading animation to freeze frequently. But that’s for another day. Moving back from what I should do to what I actually did, I noticed that Palapeli’s memory usage is awful. During the sprint, I wanted to demo Palapeli’s performance with big piece counts, and created a puzzle with the maximum of 2000 pieces from a 5000×5000 px image. It actually rendered fluently, but only because I upgraded my notebook’s RAM to 2 GB last year. Palapeli used an enormous 1.6 gigabytes of memory.

I figured that’s a bit much, and looked yesterday evening into how this can be optimized. I was testing with a 30 pieces puzzle from a 4000x4000px image. After having started Palapeli and having loaded the puzzle, the application used about 800 MB memory. The first, and simple, optimization was to remove some intermediary images which are only used while loading the image. That saved something like 100 MB of memory. But wait! Shouldn’t a 4000×4000 pixel image need only 61 MB (four bytes per pixel)? Yes, that’s true, but actually we’re not talking about one big image, but about 30 images, one for each piece. While pieces might have an arbitrary shape, their image must internally be rectangular all the time, even if big parts (e.g. around the plugs) are fully transparent. This means that the memory usage for the 30 pieces is bigger than what one might expect from the complete image.

A randomly chosen piece was 855×1098 pixels big, so by a rough approximation, all 30 pieces take 30*855*1098*4 bytes = 107 MB in memory. That still does not explain why the process still occupies 700 MB. But what’s that?

There’s a shadow around the pieces! This shadow is not added by the slicer when the puzzle is created, but by the engine when the puzzle is loaded. And because we need to control how shadows cover other pieces, we cannot render the shadows into the piece image, but must store them as separate images! And to make matters even worse, we need different shadow images for selected and unselected pieces (note the difference between blue and black shadows). The shadow size for the test image is 0.15 * (width + height) = 300 pixels on each side. Putting everything together, the memory usage of piece images + normal shadows + selected shadows is about 700 MB, i.e. everything can be explained by the pure size of the displayed images. The second optimization therefore was to restrict the shadow size to 50 pixels. This reduces the memory consumption to 380 MB, and allows to play even 5000×5000 px (i.e. 25 megapixel) images with below 1 GB of RAM.

More sophisticated optimizations are certainly possible, but let’s stop at this 50% improvement for now. There’s another thing I want to show: Palapeli’s mainwindow has been cleaned up. I really liked the old tab interface. It had its time and justification, but I want to move forward and need a cleaner, more standard interface for that. So now Palapeli has only a menubar and toolbar, just like all the other apps:

This change was possible after I realized that all toolbar actions for the collection also make sense on the puzzle table: Delete and Export work on the current puzzle. Newly created or imported puzzled will be loaded into the puzzle table afterwards. The “Back to collection” button replaces the “My collection” and “Puzzle table” tabs.