Mon, 26 Dec 2011

Short key IDs are bad news (with OpenPGP and GNU Privacy Guard)

Summary: It is important that we (the Debian community that relies on OpenPGP through GNU Privacy Guard) stop using short key IDs. There is no vulnerability in OpenPGP and GPG. However, using short key IDs (like 0x70096AD1) is fundementally insecure; it is easy to generate collisions for short key IDs. We should always use 64-bit (or longer) key IDs, like: 0x37E1C17570096AD1 or 0xEC4B033C70096AD1.

TL;DR: This now gives two results: gpg --recv-key 70096AD1

Some background, and my two keys

Years ago, I read dkg's instructions on migrating the Debian OpenPGP infrastructure. It told me that the time and effort I had spent getting my key into the strong set wasn't as useful as I thought it had been.

I felt deflated. I had put in quite a bit of effort over the years to strongly-connect my key to a variety of signatures, and I had helped people get their own keys into the strong set this way. If I migrated off my old key and revoked it, I'd be abandoning some people for whom I was their only link into the strong set. And what fun it was to first become part of the strong set! And all the eyebrows I raised when I told people I was going meet up with people I met on a website called Biglumber... I even made it my Facebook.com user ID. So if I had to generate a new key, I decided I had better really love the short key ID.

But at that point, I already felt pretty attached to the number 0x70096AD1. And I couldn't come up with anything better. So that settled it: no key upgrade until I had a new key whose ID is the same as my old key.

That dream has become a reality. Search for my old key ID, and you get two keys!

$ gpg --keyserver pgp.mit.edu --recv-key 0x70096AD1
gpg: requesting key 70096AD1 from hkp server pgp.mit.edu
gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported
gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported
gpg: no ultimately trusted keys found
gpg: Total number processed: 2
gpg:               imported: 2  (RSA: 1)

I also saw it as an opportunity: I know that cryptography tools are tragically easy to mis-use. The use of 32-bit key IDs is fundamentally incorrect -- too little entropy. Maybe shocking people by creating two "identical" keys will help speed the transition away from this mis-use.

A neat stunt abusing --refresh-keys

Thanks to a GNU Privacy Guard bug, it is super easy to get my new key. Let's say that, like many people, you only have my old key on your workstation:

$ gpg --list-keys | grep 70096AD1
pub   1024D/70096AD1 2005-12-28

Just ask GPG to refresh:

$ gpg --keyserver pgp.mit.edu --refresh-keys
gpg: refreshing 1 key from hkp://pgp.mit.edu
gpg: requesting key 70096AD1 from hkp server pgp.mit.edu
gpg: key 70096AD1: public key "Asheesh Laroia <asheesh@asheesh.org>" imported
gpg: key 70096AD1: "Asheesh Laroia <asheesh@asheesh.org>" not changed
gpg: Total number processed: 2
gpg:               imported: 1  (RSA: 1)
gpg:              unchanged: 1
gpg: no ultimately trusted keys found

You can see that it set out to refresh just 1 key. It did that by querying the keyserver for the short ID. The keyserver provided two hits for that query. In the end, GPG refreshes one key and actually imports a new key into the keyring!

Now you have two:

$ gpg --list-keys | grep 70096AD1
pub   1024D/70096AD1 2005-12-28
pub   4096R/70096AD1 2011-03-11

There is a bug filed in GNU Privacy Guard about this. It has a patch attached. There is, at the moment, no plan for a new release.

A faster attack, but nothing truly new

My friend Venkatesh tells me there is an apocryphal old Perl script that could be used to generate key ID collisions. Here in the twenty-first century, l33t h4x0rz like Georgi Guninski are trying to create collisions.

In May 2010, "halfdog" posted a note to the full-disclosure list that generates PGP keys with chosen short key IDs. I haven't benchmarked or tested that tool, but I have used a different tool (private for now) that can generate collisions in a similar fashion. It takes about 3 hours to loop through all key IDs on a dinky little netbook.

You don't have to use any of these tools. You can just rent time on an elastic computing service or a botnet, or your own personal computer, and generate keys until you have a match.

I think that it's easy to under-estimate the seriousness of this problem: tools like the PGP Key Pathfinder should be updated to only accept 64-bit (or longer) key IDs if we want to trust their output.

My offer: I will make you a key

I've been spending some time wondering: What sort of exciting demonstration can I create to highlight that this is a real problem? Some ideas I've had:

• Publish a private/public key pair whose key ID is the same as Phil Zimmerman's, original author of PGP
• Publish a private/public key pair whose key ID is the same as Werner Koch's, maintainer of GNU Privacy Guard
• Publish a set of public keys that mimic the entire PGP strong set, except where I control the private key of all these keys

The last one would be extremely amusing, and would be a hat-tip to some work discussed in Raph Levien's Google Tech Talk about Advogato.

For now, here is my offer: If you send me a request signed with a key in the strong set, I will create a 4096-bit RSA public/private key pair whose 32-bit key ID is one greater than yours. So if you are 0x517DD4E4 I will generate 0x517DD4E5.

I will post the keys here, along a note about who requested it, and instructions on how to import them into your keyring. (Note: I will politely decline to create a new key whose 32-bit key ID would create a collision; apologies if your key ID is just one away from someone else's.)

P.S. The prize for best sarcastic retort goes to Ian Jackson. He said, "I should go and create a lot of keys with your key ID. I'll set the real name to 'Not Asheesh Laroia' so everyone is totally clear about what is going on."

[debian] permanent link and comments

Learning baritone again (for the Russian Nonsemble)

In fifth and sixth grade, I used to play the baritone horn. A few weekends ago, I played a show with the Russian Nonsemble. Look for me in a blue shirt and tie:

When I joined the Brighton public school system in fifth grade, other students had been playing musical instruments for a year. I tried a few different options, and I settled on the baritone. Maybe I really liked the sound, or how buzzing works with a mouthpiece and combines with the entire horn. Maybe I was suggestible and accepted something that the band needed.

I learned the instrument on bass clef, which was its own oddity. It was a little confusing to use bass clef in band and treble clef in chorus, but I managed. (Maybe this exercise taught me something about the concept of equivalence.)

There is something relaxing about playing the baritone: I am not keeping the melody. The tone quality I send out is not, at least in a fifth grade band, make or break the performance. One downside is that, with the highly repetitious lines, it can be easy to get lost.

Early in the sixth grade, our band director asked for volunteers to learn the French horn. Steve Marler picked it up for the musical challenge. I picked it up because I was willing to fill an institutional need.

It was a lot of fun to play French horn. Well, it was a challenge, at least. Every single group performance setting I had for the French horn -- from sixth grade through high school, through the Johns Hopkins concert band -- there was someone sitting next to me who was a full notch better at me. It was disheartening, to be honest.

I stopped playing horn somewhere in college. For a while I played mellophone in the Johns Hopkins pep band, but that wound down eventually.

About a year ago, my friend Irina invited me to be part of a band, for which she lent me a baritone.

Halfway through the concert you see above, I began to do more than just read the music. I listened to the sound of the band and looked at my bandmates, making bom-pom sounds on the horn while bobbing up and down with the rhythm of the song we were playing.

Thanks to Jess Schumann for taking the picture!

[music] permanent link and comments

Sat, 17 Dec 2011

Computer fraud and abuse by Universal Music Group

It seems that Universal Music Group willfully misrepresented its copyright interest and probably violated its service contract with YouTube. By my understanding of the Computer Fraud and Abuse Act, UMG likely took actions that exceed authorized access, subjecting it to criminal prosecution. (I am just a computer enthusiast and not a lawyer, so I welcome corrections from others.)

The emerging details, reported by Wired.com's Threat Level blog, are as follows:

YouTube said Friday that Universal Music abused the video-sharing site’s piracy filters when it employed them to take down a controversial video of celebrities and pop superstars singing and praising the notorious file-sharing service Megaupload.

In particular, Google created a system for antipiracy that is being abused by UMG:

“Our partners do not have the right to take down videos from YT unless they own the rights to them or they are live performances controlled through exclusive agreements with their artists, which is why we reinstated it,” Google-owned YouTube said.

I look forward to a speedy criminal prosecution of the employees or board of Universal Music Group. If that is not feasible, perhaps the organization itself should be put behind bars.

Even if Megaupload.com fails in its own lawsuit against UMG, I eagerly await the criminal prosecution of UMG as in another case where Federal prosecutors had to get involved.

[corporations] permanent link and comments

Mon, 12 Dec 2011

Twisted high scores

Living in the Boston area, I've had the chance to spend time with the lovely maintainers of the Twisted project.

Twisted is an event-driven network programming framework in Python. It's also a community of people for whom software is never good enough -- and they're right.

I visited the Twisted November sprint at the Smarterer.com office a few weeks ago and reviewed a ticket. So now I am on the Twisted high scores list for November!

It was one of the most rewarding short periods of time I've ever spent contributing to an open source project. I took someone's contribution and turned it into a patch, and also gave some feedback. This counted as reviewing a ticket, for which I was immediately and strongly socially rewarded: J.P. (exarkun) turned to me and say, "Thanks for contributing to Twisted."

An IRC bot pinged me with a note saying my ticket review was complete. And now I appear in the high scores list for November!

[software] permanent link and comments

Copyright © Asheesh Laroia. This work is licensed under a by-sa. Open Hatch is my current project. You should enjoy my parents' Indian restaurant in Rochester!