The code monkey’s guide to cryptographic hashes for content-based addressing

At long last, I’ve written and published the “compare-by-hash for programmers” article everyone’s always been asking for. You can read it chopped into 17 pieces and partially obscured by floating ads here:

http://www.linuxworld.com/news/2007/111207-hash.html

(My editor says: Please please complain about this! No one believes me when I say this is bad!) Or you can read it one piece with full size tables, etc. here:

http://www.linuxworld.com/cgi-bin/mailto/x_linux.cgi?pagetosend=/export/home/httpd/linuxworld/news/2007/111207-hash.html

I’m always looking for new article suggestions, especially for the Kernel Hacker’s Bookshelf (search down the page for the entry). Writing is fun!

The part of the article that Edward Tufte would be most proud of are the two tables about hash function life cycles:

Stages in the life cycle of cryptographic
hash functions
Stage Expert reaction Programmer reaction Non-expert
(“slashdotter”) reaction
Initial proposal Skepticism, don’t recommend use in
practice
Wait to hear from the experts before adding to OpenSSL SHA-what?
Peer reviewal Moderate effort to find holes and
garner an easy publication
Used by a particularly adventurous
developers for specific purposes
Name-drop the hash at cocktail
parties to impress other geeks
General acceptance Top-level researchers begin
serious work on finding a weakness (and international fame)
Even Microsoft is using the hash function now Flame anyone who suggests the function may be broken in our lifetime
Minor weakness discovered Massive downloads of
turgid pre-prints from arXiv, calls for new hash functions
Start reviewing other hash functions for replacement Long
semi-mathematical posts comparing the complexity of the attack to the
number of protons in the universe
Serious weakness discovered Tension-filled CRYPTO rump sessions! A full break is considered
inevitable
Migrate to new hash functions immediately, where
necessary
Point out that no actual collisions have been
found
First collision found Uncork the
champagne! Interest in the details of the construction, but no
surprise
Gather around a co-worker’s computer, comparing the
colliding inputs and running the hash function on them
Explain why a simple collision attack is still useless, it’s
really the second pre-image attack that counts
Meaningful collisions generated on home
computer
How adorable! I’m busy trying to break this new
hash function, though
Send each other colliding X.509
certificates as pranks
Tell people at parties that you always
knew it would be broken
Collisions generated by hand Memorize as fun party
trick for next faculty mixer
Boggle Try to remember
how to do long division by hand
Life cycles of popular cryptographic hashes (the
“Breakout” chart)
Function 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007
Snefru                                    
MD4                                    
MD5                                    
MD2                                    
RIPEMD                                    
HAVAL-128                                    
SHA-0                                    
SHA-1                                    
RIPEMD-128                                    
RIPEMD-160                                    
SHA-2 family                                    
Key Unbroken Weakened Broken
The
Hash Function Lounge
has an excellent list of references for the
dates.

Vonage, voicemail, and crash-only software

I happened to accidentally check my Vonage voicemail page and discovered that I had 13 voicemails piled up since September 21st from various people such as, oh, my tax consultant, a potential client, and my sisters. I set up my voicemail so that my cell phone picks it up first, and my Vonage voicemail only picks up when my cell phone voicemail is broken. Then Vonage is supposed to email me and text me the .wav and text transcript of the message (for 25 cents!). It’s this last step that was broken. I called customer service and guess what the solution was? Reloading my settings. It’s like crash-only software, but without the bit that detects the part that’s broken and reboots it. Nngh!!! And yeah, there’s the broken dial tone when you pick up the headset that tells you if you have a message, but I’m so used to ignoring that because I usually don’t delete the voicemail for a while, and it can’t tell when I’ve played the .wav or read the text message.

Anyone with experience with Comcast VoIP doo-dah? I really like Vonage except for the reliability bit.

Best. Apartment. Ever.

Lina found the best best best apartment ever. In classic San Francisco rental fashion, we had to decide whether to sign a 16 month lease within 4 hours of seeing it or else face fierce competition from the open house. It’s a fabulously beautiful renovated Victorian on the south edge of the Mission (for reasons of preserving Lina’s sanity, it is NOT located on the north edge of Glen Park). I didn’t really believe we had the apartment until we had the keys in our sweaty little hands.

I think this photo of the shower head in my bathroom says it all:

If you are not a stalker, email me and I’ll send you the rest of the photos and the Google maps link so you can use Street View.

Moving to San Francisco

The word is on the street: I’m moving back to San Francisco around Dec. 1st. Several of my friends heard the news through the grapevine and are wondering if I’m not telling them in hopes of pretending I still live in Portland and can’t come over to watch their vacation slides. The reality is that announcing the move is fraught with implications and knotty social problems. To wit:

  • What do I say when people ask me why I’m leaving Portland only a few months after I went?
  • What if something horrible goes wrong and I don’t actually move?
  • What if people are tired of invitations to my going-away/house-warming parties and want me to stop emailing them about my moves?

My plan was to wait until I got an apartment (courtesy my wonderful roommate-to-be, Lina), but that’s taking a little longer than anticipated. Man, the rental market in San Francisco is tough! They want all THREE versions of my credit report!

Anyway, I’m moving to San Francisco, I’m mildly embarrassed about it, and you’re still my friend. Announcement of going-away/house-warming parties to follow.

Truth in advertising

This morning, the phone rang (a rare occurrence in my household). I picked up my VoIP phone with caller ID, and saw:

PROMO OFFER
1408(don't remember)

Wow! A telemarketer with a descriptive caller ID and a valid-looking 408 phone number! It’s like receiving spam entitled: “SPAM: Unsolicited commercial mailing” with a valid From: address. The apocalypse must be near.

Naturally, I didn’t answer.

Lazyweb: Laptop acceleration chirper

Dear Lazyweb,

I would like a program that checks the acceleration sensor on my laptop’s hard drive. When it experiences especially intense vibration, as of being slapped on my hip repeatedly as I run for the train, it chirps the PC speaker or plays a sound clip or otherwise audibly notifies me that my laptop is not, in fact, suspended. (At least modern hard drives no longer die when I do this.) Alternatively, it can chirp periodically when the lid is closed but AC is not connected. (Yes, I like to close my lid without suspending – sometimes I compile kernels while driving.) Something with a nice applet front-end for XFCE would be ideal. Thanks!

-VAL

Overheard in Portland

Scene: Busy Portland coffee shop, Sunday afternoon. VAL, a workaholic programmer transplanted from the Bay area, is typing intently on her laptop. Enter four middle-aged men, talking loudly. They choose the table next to VAL and engage in much good-natured (and loud and annoying) shuffling around and unpacking of laptops. Their leader finally calls them to attention.

LEADER: Okay, let’s get started. So, should we hire more salesmen in Paris? Or wait till next quarter?

MAN #1: [European Spanish accent] Well, I don’t know. What’s our budget?

[VAL perks up and casts an interested look, as she comes from the Land of Start-ups and such conversations are relatively rare in Portland.]

LEADER: I guess it really depends on whether we ship both business softwares.

[VAL looks slightly affronted. How come these, er, average guys have a startup with international sales offices and they don’t even know the correct plural of software?]

MAN #2: [mutters as he struggles to pull out his laptop] I hate this laptop. As soon as I get a real job, I’m giving this to my son.

LEADER: I talked to the professor, and he says that we should focus on the markets that our competitors are doing well in – follow the leader, you know.

[VAL looks somewhat impressed that they are consulting with distinguished academics.]

MAN #3: [unidentifiable Eastern European accent] Should we have a cushion for unexpected costs?

LEADER: I don’t think the professor’s going to dock points for exceeding our budget that way, no.

[VAL makes “Oh!” face as she realizes these people aren’t in a start-up, they’re in business school. Immediately feels better about herself for having zero sales offices in Paris.]