I'm on the Program Committee for the the ISOC Network and Distributed System Security Symposium again this year and so far I've reviewed 9 out of the 19 papers I was assigned. If I could offer one piece of advice to authors it would be this: don't make me guess what you're trying to do. State early and clearly what the problem you're trying to solve it and what the general approach you're following is. This provides important context for the rest of the paper. Only then give me the details. Otherwise I end up skimming your paper to figure out what's going on and then rereading it with that context in mind, which is extremely off-putting. It also makes me wonder if you know what you're trying to say--or indeed if you have anything to say in the first place.
Apparently, the Addis Ababa track is about as far as you can get from a Mondo track:
ATHENS (Reuters) - Ethiopian distance great Haile Gebrselassie blames the atrocious state of his home track in Addis Ababa for the injury that spoiled his farewell at the Olympics.
The two-time Olympic champion and winner of four world titles finished a wincing fifth in the 10,000 meters last Friday in his last track race before switching to the marathon.
Amazingly, Gebrselassie had not trained for three weeks before the Games due an Achilles injury he aggravated six weeks ago on his home track, which is 14 years old and riddled with pot holes.
"Our main problem is our track," said the 31-year-old on Thursday in his first news conference since the race. "It's one of the worst tracks in the world.
"Every 50 meters you see a hole with rocks in it and you have to jump it."
Gebrselassie urged the Ethiopian athletics federation to get on with replacing the surface.
"I'd like to send a message to them to rebuild it. Imagine how good the Ethiopians would be without that track."
Potholes every 50 m? That sounds worse than my high school track. And did you catch that bit about Gebrselassie getting fifth after not training for three weeks? Unbelievable.
If you've ever raced track, you know that the track surface is important. Back when I was in high school, we had a dirt track, which our coaches used to tell us was fast but was a horrific sloppy mess in the rain. The distance runners all looked forward to racing at schools that had rubber tracks--back then they were called "all-weather", with good reason, since you didn't get mud all over your back when it rained. Plus, the rubber tracks felt bouncy and fast under your feet. If you've ever run on a nice rubber track you know what I mean.
Sunday's Slate had a pretty interesting article about track. ItTurns out that pretty much all the high-end tracks are made by a single Italian company called Mondo. Instead of being poured onsite, Mondo makes the track in rolls and then ships them to the site where they're installed like a jigsaw puzzle.
Another interesting fact: You have to compromise between the sprinters, who want a hard, fast surface, and the distance runners, who want a softer surface which is easier on their legs. According to Slate, Haile Gebrselassie has complained that Mondo tracks are way too hard.
LOOSE-TONGUED SPEAKER? Speaker of the House Dennis Hastert - having already enraged some New Yorkers with his remarks about local office-holders' "unseemly scramble" for federal money after 9/11 - yesterday opened a second front. On "Fox News Sunday," the Illinois Republican insinuated that billionaire financier George Soros, who's funding an independent media campaign to dislodge President Bush, is getting his big bucks from shady sources. "You know, I don't know where George Soros gets his money. I don't know where - if it comes overseas or from drug groups or where it comes from," Hastert mused. An astonished Chris Wallace asked: "Excuse me?" The Speaker went on: "Well, that's what he's been for a number years - George Soros has been for legalizing drugs in this country. So, I mean, he's got a lot of ancillary interests out there." Wallace: "You think he may be getting money from the drug cartel?" Hastert: "I'm saying I don't know where groups - could be people who support this type of thing. I'm saying we don't know."
Ok, let's ignore the fact that George Soros is stinking rich and therefore can fund whatever media campaign he wants out of his own pocket and get right to the really stupid bit at the heart of this. Why on earth would drug cartels want the US to legalize drugs? Drug dealers don't sell drugs because they'e on some crusade to hook every American on coke! They do it to make money! And the reason that they can make a crapload of money selling drugs is that drugs are illegal and so you need to be willing to be a criminal to sell them. If drugs were legal, you can be sure that Dole would cut the Colombian cartels out of the loop and import cocaine by the oil tanker load. Not exactly an outcome favored by narcotrafficantes.
Required reading: Bootleggers and Baptists: The Education of a Regulatory Economist
So, California is getting ready to allow hybrid vehicles into HOV lanes:
The California Senate has approved a bill which would allow hybrid vehicles use carpool lanes even if the driver is the car's only occupant and thus would not meet occupancy requirements.
But don't move into that speedy lane yet. Before the California measure is effective, it needs to be signed by Gov. Arnold Schwarzenegger, something that's expected, and Congress will have to finally pass this year's highway funding bill which contains a clause permitting use of carpool lanes by hybrids carrying fewer passengers than would otherwise qualify. Federal approval is required because federal funds are used in the construction of HOV lanes.
The California Senate passed the bill on a bipartisan 29-7 vote Tuesday. A similar bill was approved earlier by the Assembly. It now must go back to the Assembly on a procedural matter, before it goes to the governor. The bill is also sponsored by the California Environmental Protection Agency and the California Air Resources Board.
"The Senate vote ... is an important step toward opening up the state's carpool lanes to hybrid and other advanced-technology vehicles, a smart move that will help clear the air, reduce our dependence on polluting fuels and save motorists time and dollars," says state Treasurer Phil Angelides, one of the bill's sponsors. "And it comes at an especially important time, as gasoline prices are volatile and the need is growing to encourage clean and environmentally sound technologies."
When faced with decisions like this, you need to ask, as my friend Frank Jackson used to, "what resource are you conserving"? When people carpool, they reduce consumption of two resources: fuel (carpools are more efficient) and space on the road. So, having HOV lanes tends to act to conserve both and people didn't have to think too hard about what the objective was.1 However, opening HOV lanes to hybrid vehicles incentives reduced fuel consumption at the expense of traffic congestion, so the two are opposed.
In fact, we can reinforce both behaviors together, once we realize that HOV lane space isn't the only way to incentivize people for good car related behaviors: keep HOV lanes for actual high occupancy vehicles and offer hybrid owners a monetary incentive in the form of a tax rebate. Then if they want to use the HOV lane as well they can carpool. Of course, seeing as there's a 4-6 month waiting list for a Prius, you could be forgiven for thinking that the incentive to drive a fuel efficient vehicle is already plenty strong.
1 Looking at behavior at the edges, you can see that there are indicators in both directions: SUVs with carpools are allowed in the HOV lane, even though they're not fuel efficient, reinforcing the congestion hypothesis. However, motorcycles are also allowed, even though they probably consume almost as much space as cars, presumably on the theory that they're more fuel efficient.
It was only a matter of time. Scott MacLean, a programmer from Ottawa, has hacked together a TiVo-like application for XM radio called TimeTrax". Unsurprisingly, the RIAA and XM's first urge is to try to squash it:
A spokesman for the Recording Industry Association of America said his organization had not reviewed the software, but said that in principle it was disturbed by the idea. "We remain concerned about any devices or software that permit listeners to transform a broadcast into a music library," RIAA spokesman Jonathan Lamy said.
The RIAA and XM are both busy figuring out if any copyright laws and user agreements have been broken.
MacLean's software essentially marries the song information with an analog recording of the broadcasts, then stores this in MP3 files. The user can leave the software running unattended for hours and amass a vast library of songs.
That feature has been a central concern in the music industry as it lobbies regulators to place restrictions on free copying of digital broadcasts before many more radio stations add digital broadcasts. About 300 stations already offer digital broadcasts.
Music labels fear that the convenience of MacLean's software will lead millions more to copy and distribute songs over file-sharing networks such as KaZaA, a music industry source said.
OK, I can totally understand the objection that people will use this to build a local library of songs--not that I think that should be illegal, but I understand it--but this last paragraph is, as far as I can tell, total nonsense. The gating factor in song availability over KaZaA is unlikely to be the ability to get a ripped version of the song. It's not like there's any shortage of consumers with Britney Spears CDs and CD-ROM drives. In fact, I would expect the availability if this sort of technology to decrease the amount of file sharing by making it easier to collect a library of known-to-be-correct songs.
There's one interesting thing to note here: what makes this application possible isn't so much that the music is in digital form--people have been taping songs off the radio for years and of course TiVo works just fine with analog TV--but rather that the scheduling meta-information identifying song title, stop, and start is in digital form (and, I suspect, broadcast along with the radio signal). This makes it easy to automatically record programs. Part of what makes TiVo such a big operation is the requirement to distribute schedule information to all the end-user units. That seems to be unnecessary here.
Terence, Hovav, and I have been trying to invent new reality TV shows. Here are some ideas we think have potential.
Uncle: Two players have to suffer various ordeals to win cash prizes. The twist is that the ordeals are graduated and the players bid on the right to suffer. The player willing to eat the most habaneros, get bitten by the most scorpions or whatever wins the right to try. If he fails--or more likely, gives up--the other player gets a half size prize and then can a full size prize by completing his own offer. For more fun, bring the same players back week after week.
Trial By Combat: We offer two people the chance to settle their dispute the old fashioned way--by fighting over it. Full medical support on hand, of course.
Celebrity Justice: A new version of the People's Court but with various celebrities presiding. Suggested jurists include Jerry Orbach, Snoop Dogg, R. Lee Ermey and Paris Hilton.
Producers should feel free to contact us for rights or further ideas.
A couple of months ago I had my dentist fix a chipped tooth and I just recently got the bill for the filling. Here's the story:
In case you didn't know, that "Insurance adjustment" line is the negotiated discount that the dentist gave my insurance company in order to be a preferred provider. In other words, even before we get into the risk-sharing aspect of my insurance, the collective bargaining aspect has saved me nearly 45%. What a deal! It's sure nice not to be one of those chumps off the street who has to pay list price.
It makes you think, though: it's hard for individuals to get health insurance for the usual adverse selection problems, but as should be clear at this point, much of the benefit of insurance is just that you get to be in a large collective bargaining pool which can force doctors to lower their rates. Couldn't you start an organization which had as its sole purpose this sort of collective bargaining with no attempt to hedge risk? You would join "EG's Preferred Health Plan" and as long as you went to EG Preferred Providers, you could be guaranteed of a big discount.
One obvious question is whether this kind of buying pool would have enough leverage to get big discounts. One reason that insurance companies have leverage is that the doctor knows that the insurance company will cover most of the bill even if the patient finks out. That problem is easy to fix, though: the contracting organization promises to cover the cost up to a certain amount and extracts a modest premium--or a deposit--from the patients. This is basically what credit card companies do already, after all.
I'm not sure why we don't have this kind of program. Is it that there aren't enough people who actually pay their medical bills and don't have insurance? Is it some kind of antitrust violation? Anyone know?
I'm assuming that you're not one of the 5 people on the planet who haven't seen the "JibJab This Land is Your Land video:"http://www.jibjab.com/". You've probably also heard that the jerks at Ludlow who own the copyright threatened to sue them for copyright infringement. Turns out the EFF discovered that the copyright may have expired: "This Land Is Your Land" was published in a songbook in 1945 but Ludlow registered the copyright in 1956 as an original copyright. So, when they renewed in 1984, they were 11 years too late and the copyright (according to EFF) had expired. Ludlow disputes this, but they've settled anyway:
Under the terms of the settlement, JibJab will continue to use the animation, and AtomFilms and Speedera can continue to host it.
JibJab also agreeed to donate 20 percent of the net proceeds of the animation to the Woody Guthrie Foundation and link to the original lyrics.
I wonder if people currently paying Ludlow royalties will tell them to shove off. Wouldn't that be nice...
A group of 10 Nobel Prize winning economists have published an open letter endorsing John Kerry for President:
An Open Letter to the American Public
August 25, 2004
President Bush and his administration have embarked on a reckless and extreme course that endangers the long-term economic health of our nation. John Kerry understands that sound economic policy requires a substantial change in direction, and we support him for President. The differences between President Bush and John Kerry with respect to leadership on the economy are wider than in any other Presidential election in our experience. President Bush believes that tax cuts benefiting the most-wealthy Americans are the answer to almost every economic problem. The Bush Administrations tax cuts were poorly designed and therefore have given insufficient stimulus to job creation. The principal effect of the Bush Administration's fiscal policies has been to turn budget surpluses into enormous budget deficits. President Bush's fiscal irresponsibility threatens the long-term economic security and prosperity of our nation. At a time when our nation should be saving for the future, to pay the Medicare and Social Security benefits for the baby boomers, our national debt is swelling; the social contract that binds one generation to another is being threatened with unraveling. Increased borrowing from abroad--now almost five percent of our GDP--leaves our country, our economy and global stability increasingly vulnerable to changes in sentiments of foreign, or even domestic, investors. At the same time, his policies have exacerbated income inequality, failed to address the real wage declines and rising health care costs beleaguering American families, and ignored the need for critical investments to spur long-term growth.
John Kerry will chart a different course. We believe that he will restore fiscal responsibility. He is committed to making key investments in human capital, such as helping families meet the cost of higher education. He has a proposal that will address the problem of rising health care costs. We believe that he has both the ability and the commitment to work with our allies and trading partners to promote global growth that lifts up workers around the world. John Kerry is our choice for America's next President. We hope that you will join us.
Signed by the following recipients of the Nobel Prize in Economics:
George A. Akerlof University of California at Berkeley 2001 Kenneth J. Arrow Stanford University 1972 Daniel Kahneman Princeton University 2002 Lawrence R. Klein University of Pennsylvania 1980 Daniel L. McFadden University of California at Berkeley 2000 Douglass C. North Washington University St. Louis 1993 Paul A. Samuelson MIT 1970 William F. Sharpe Stanford University 1990 Robert M. Solow MIT 1987 Joseph E. Stiglitz Columbia University 2001
The views expressed in this letter represent those of the signers acting as individual citizens. They do not necessarily represent the views of the institutions with which they are affiliated.
Obviously, these are some big names and as far as my limited knowledge of Macroeconomics goes, the argument they're making is basically correct. However, it's worth noting two aspects of this letter:
One explanation for this, suggested by Kevin Dick, is that the macro specialists tend to be politically active and some of them, such as Taylor and Mankiw are already involved in Administration policy making. Still, it would be nice if this letter had Friedman on board, seeing as he's probably the living economist that comes closest to being a household name.
In what is no doubt a sign of the marvels we can look forward to, scientists have figured out how to make mice that can run twice as far and fruit flies that will have sex for 50% longer. No word on whether the fruit flies are willing to cuddle 50% longer afterwards.
Lisa and I managed to get out for a short camping trip over the weekend. We took US 101 South to Prunedale and then cut over to US 1 South past Big Sur to the Kirk Creek Campground and hiked in to the Vicente Flat campground.
|Driving distance||140 miles (each way)|
|Walking distance||5 miles (road to campsite)|
|Max altitude||1850 feet (measured by GPS)|
|Total climbing||~2000 feet (estimated by eye)|
|Scenery rating||10 (great views of the ocean)|
|Weather||Cool and mostly shaded|
|Water availability||Yes, but requires some management|
|Special hazards||Lots of poison oak|
|Cost||Zero! (the USFS has waived the adventure pass)|
|Permits required||Campfire permit|
We left Palo Alto at about 1 and arrived at the Kirk Creek Campground at about 5:00 and were on the trail by 5:30. You park on the West side of US 1 (at the side of the road, not the campground) and the trail head is on the East side of the road. The whole East side of 1 is a steep hill/cliff face and the first 3 miles of the trail mostly hug the hillside in a series of switchbacks as you head generally Northish. There are a number of very spectacular views of the coastline and ocean. The climbing is moderately steep and you gain about 1700 feet of altitude in this section. The trail is mostly unshaded but cool because you're close to the coast. The trail is well used and generally pretty smooth with a few pieces of tricky footing due to rocks or loose dirt. One thing to note is that there seems to be a lot of poison oak on the trail. Conveniently, there were almost no mosquitos anywhere, which is a really nice feature.
At around 3 miles, you pass the Espinosa camp and head in towards the interior. There's a small creek shortly after Espinosa camp, but I don't know if it runs yearround. From this point, the terrain is more foresty with a modest number of fallen trees blocking the path--though nothing that's really difficult to get past--you just need to climb over a few things. You descend about 250 feet to Vicente Flat. It took us about 2.5 hrs to hike in and it was getting dark by the time we hit Vicente Flat (partly due to the shade). It was a little unobvious if we were in the right place (and we're still not entirely sure) but some hunters were there and claimed we were in the right location. The Vicente Flat campground is a nice clearing in a stand of redwoods with a bunch of stone fire rings and some impromptu wood benches. There's water available about 200 yards from the camp but it can be hard to find in the dark. Eventually Lisa found it--a nice little stream--and we were able to fill up our bottles. We'd brought two bottles each which was just enough if you were hiking but didn't want to cook, but we needed more our dehydrated meals.
We slept in a bit in the morning, filtered some more water and left at about 10. The hike back is a a lot easier, since it's mostly downhill after Espinosa. We got back to the car about 12:30 or so, taking a pretty leisurely pace. The downhills can be a bit steep but there's nothing particularly treacherous. As before, you get a great view of the ocean hiking back and it's not too warm, even around noon.
All in all, things went fairly well. If I were doing it again, I would try to get started earlier on Friday and probably get water at the first stream. We would have been ok with a total of 4 liters, but better safe than sorry. If you're looking for an easy weekender, this is definitely a good candidate hike.
When Lisa and I went camping back in June, I was pretty frustrated with my old MSR Whisperlite Shaker Jet. It generally gets the job done but can be pretty flakey and practically guarantees that you're going to get your hands covered in soot. Towards the end of the trip, the stove didn't seem to be working as well as before. A last minute rebuild on Thursday night got it working again, but when I was at REI on Friday, I kept getting drawn to the Jetboil, and eventually I succumbed to its siren song.
The standard backpacking cooking arrangement is to have a portable stove with a separate lightweight pot for boiling water, cooking in, etc. This arrangement is often unstable because the pot and stove can tip over and inefficient because a lot of the energy goes into heating the surrounding air. The Jetboil (shown below) is intended to solve both these problems.
The Jetboil has four major pieces:
The Jetboil system itself weighs 6 oz, and the 100g gas canister weighs about 200g, so all in all, you're talking 12-13 oz, about the same weight as my Whisperlite alone. You're supposed to be able to boil 11 liters of water with each 100g canister. The packed unit is about as tall as a Nalgene bottle and maybe an inch wider in diameter.
To use the Jetboil, you screw the burner right onto the gas canister and then attach the cooking cup to the burner (there's a bayonet connector). You put whatever you want to cook into the cooking cup and light the stove with the piezoelectric starter and you're, well, cooking with gas. The cup is insulated by the neoprene, so you can just grab it and pour. The lid doubles as a pouring spout.
The Jetboil brings water to boil incredibly quickly. The claimed boiling time for two cups of water is 90 seconds, which seems a little optimistic, but I measured it at 2:20 (140 seconds), which is still pretty fast. I'm using Giga Snow Peak canisters, so maybe the Jetboil canisters are faster, but I doubt they're that much faster.
There are a few annoying features:
All in all, though, I'm pretty pleased. It's certainly much more convenient than the Whisperlite was, and I don't get my hands covered with soot. If you're in the market for a new backpacking stove, you should definitely check it out.
I'll be out of the office field testing my new Jetboil, so blogging may be a little light for the rest of the weekend...
I promised earlier to write up my impressions of the implications of the recent hash function attacks. I meant to do a full writeup but I haven't had time, so in the interest of timeliness, here's my first cut.
What does this mean in practice for security protocols? I'll be writing up full details hopefully soon, but here's a short overview...
What's been shown?
An attacker can generate two messages M and M' such that Hash(M) = Hash(M'). Currently this is possible for MD5 but we have to consider the possibility that it will be eventually
possible for SHA-1. Note that he cannot (currently) generate a message M such that Hash(M) is a given hash value, nor can he generate a message M' such that it hashes the same as a fixed message M.
Uses of hash functions
Security protocols use hash algorithms in a bunch of different contexts. At minimum:
The potential attacks
The only situation in which the current attacks definitely apply is 1. The general problem is illustrated by the following scenario. Alice and Bob are negotiating a contract. Alice generates two messages:
M = "Alice will pay Bob $500/hr" M' = "Alice will pay Bob $50/hr"
In practice, the messages might not be this similar, but there turn out to be lots of opportunities to make subtle changes in any text message.
H(M) = H(M').
She gets Bob to sign M (and maybe signs it herself). Then when it comes time to pay Bob, she whips out M' and says "I only owe $50/hr", which Bob has also signed (remember that you sign the hash of the message).
So, this attack threatens non-repudiation or any kind of third party verifiability. Another, slightly more esoteric, case is certificates. Remember that a certificate is a signed message from the CA containing the identity of the user. So, Alice generates two certificate requests:
R = "Alice.com, Key=X" R' = "Bob.com, Key=Y"
H(R) = H(R')
I'm simplifying here, but you get the idea...
When the CA signs R, it's also signing R', so Alice can present her new "Bob" certificate and pose as Bob. It's not clear that this attack can work in practice because Alice doesn't control the entire cert: the CA specifies the serial number. However, it's getting risky to sign certs with MD5.
First, anything that's already been signed is definitely safe. If you stop using MD5 today, nothing you signed already puts you at risk.
There is probably no risk to two party SSH/SSL-style authentication handshakes.
It's believed that HMAC is secure against this attack (according to Hugo Krawczyk, the designer) so the modern MAC functions should all be secure.
I'm not entirely sure about other non-HMAC challenge/response systems such asHTTP Digest. They're not as well designed as HMAC. I don't know any attacks but I haven't looked too hard either. It would be nice to see someone give them a thorough once over
The key generation PRFs should be safe.
There's a lot of concern in the crypto community that the attacks on MD5 can be turned into full pre-image attacks (being able to generate a message M such that H(M)=X for a given hash value X). If that were to happen, this would be really serious and potentially compromise a lot of the stuff mentioned above.
UPDATE: Paul Joseffson observes that CRAM-MD5 is actually HMAC, so it's probably OK. I'd misremembered it as an ad hoc function. Removed CRAM-MD5 from the list above.
UPDATE: Added the Chinese SHA-0 results, as reminded by Perry Metzger.
Writing about minimum standards for rented accomodation, Daniel Davies over at Crooked Timber writes:
It is really quite rare to find a buyer’s market for rented accommodation. Even if there is a slight oversupply of rental units for sale, time is almost always on the landlord’s side, because waiting is typically much more inconvenient for the party that has to wait without a house to do wait in. In general, when tenants and landlords are negotiating over the potential Pareto gain that could be made from renting the house, the landlord ends up capturing most or all of the surplus.
This may be so in the residential property market (though I'm dubious) but I happen to be in the market for commercial property and it's most certainly not true here in the Bay Area. On the contrary, the landlords are willing to give you the property in more or less any state you want it--anywhere from without Ethernet wiring (horrors!) to completely remodelled and furnished--for a suitable adjustment in the rent.
The BBC is carrying the an article about attempts to extend European music copyright. It seems that European copyright on recorded music extends 50 years, so the copyright on a fair amount of music is starting to expire. Unsurprisingly, the British Phonographic Industry (BPI) is lobbying for a Sonny Bono-style copyright extension:
Unlike Europe, copyright protection exists in the US for 95 years after the recording was made. Australia and Brazil have 70-year terms, and India 60 years. Composers and writers also enjoy 70 years' protection.
Peter Jamieson, the BPI's executive chairman, said less favourable copyright terms could put the UK's record industry at a commercial disadvantage to the US.
He said it was unfair to performers and investors to fail to get a return for a "free-for-all" in Europe - often within the artist's lifetime.
Record labels argue that their ability to invest in new talent often depends on money generated by their back catalogue.
Consider the following thought experiment. Someone proposes to tax everyone in England $10 and give the proceeds to British music companies. Why would we do that, you ask? Well, they could then use the money to produce new music. Of course, they might just pocket the money. And you might ask why the record companies would be particularly deserving. Why not, say, the movie companies, book publishers, or plumbers?
If you think this subsidy is a bad idea, then you should think that extending copyright on recorded music is an even worse idea. Just like the subsidy, it takes money out of your pocket and puts it in the hands of the record companies without giving them any actual new incentive to produce more content. Unfortunately, it's even worse than that: if the copyright expires, then the cost of the music goes down to the marginal price of production, maybe a dollar or two--and it's probably available for free on the Internet. Everyone who wants a copy can get one. If the copyright is extended, the price won't change. If the price is say $10, then people who value copies at $5 won't buy any--that pesky deadweight loss again.
Bottom line: subsidizing more music production is a terrible rationale for extending copyright. If we think that not enough music is being produced, a simple grant to to the record companies--with deliverables!--would be a much better plan.
I didn't catch the Crypto webcast myself but I've gotten reports, so I hereby provide a short summary with some initial reactions (also check out Ed Felten's report):
The MD5 collisions are obviously pretty serious. The good news is that people have sort of assuming that something like this would happen ever since Dobbertin published his papers back in 1996 and so we've been mostly phasing out MD5 in contexts where this attack would be a problem. The SHA-0 and SHA-1 stuff is more serious since it now looks like there's a possibility that someone will get full SHA-1 and we need to look for alternatives.
A revised version of Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD has been posted showing collisions for MD5 with the right IVs.
Input vector 1:1
0000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c 0000020 2f ca b5 87 12 46 7e ab 40 04 58 3e b8 fb 7f 89 0000040 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 71 41 5a 0000060 08 51 25 e8 f7 cd c9 9f d9 1d bd f2 80 37 3c 5b 0000100 d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6 0000120 dd 53 e2 b4 87 da 03 fd 02 39 63 06 d2 48 cd a0 0000140 e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 a8 0d 1e 0000160 c6 98 21 bc b6 a8 83 93 96 f9 65 2b 6f f7 2a 70
Input vector 2:
0000000 d1 31 dd 02 c5 e6 ee c4 69 3d 9a 06 98 af f9 5c 0000020 2f ca b5 07 12 46 7e ab 40 04 58 3e b8 fb 7f 89 0000040 55 ad 34 06 09 f4 b3 02 83 e4 88 83 25 f1 41 5a 0000060 08 51 25 e8 f7 cd c9 9f d9 1d bd 72 80 37 3c 5b 0000100 d8 82 3e 31 56 34 8f 5b ae 6d ac d4 36 c9 19 c6 0000120 dd 53 e2 34 87 da 03 fd 02 39 63 06 d2 48 cd a0 0000140 e9 9f 33 42 0f 57 7e e8 ce 54 b6 70 80 28 0d 1e 0000160 c6 98 21 bc b6 a8 83 93 96 f9 65 ab 6f f7 2a 70
Thanks to Eu-Jin Goh for notifying me that the updated paper had been posted.
1 Note that the first column of these digests is just byte offsets.
This is Jim Hughes, General Chair of CRYPTO2002. There are three significant Rump session papers on hash collisions that will be presented, including an update on this one (and about 40 ther short papers on other aspects of cryptography). As the session firms up, more information it will be posted at
Barring technical or other difficulties, if you want to hear this from the horses mouth, the CRYPTO2004 Rump Session will be webcast at 7pm pacific Tuesday Aug 17 for as long as it takes. You may join us virtually using the following links (depending on the readers).
Microsoft media server
mms://188.8.131.52/crypto [Note, this link corrected by EKR. Thanks to Nagendra Modadugu for pointing this out]
The players (for MS and Mac) are available from
I assume MS clients will be able to cope. I know that my MacOSX machine with Windows Media Player can use the mms: link. I welcome feedback from anyone using other readers on other platforms like Linux.
The server is currently up and running and is broadcasting a dark, empty, and silent hall. This should be more interesting after sunup Tuesday Santa Barbara time. You may expect sound near to the start time.
This is our the conferences first webcast, and I hope that it works for you. If there are problems, I will apologize in advance.
Should be pretty interesting and, unlike the Olympics, you can watch it live in the US.
I've now successfully reproduced the MD5 collision result. Basically there are some endianness problems.
The first problem is the input vectors. They're given as hex words, but MD5 is defined in terms of bitstrings. Because MD5 is little-endian, you need to reverse the written byte order to generate the input data. A related problem is that some of the words are given as only 7 hex digits. Assuming that they have a leading zero fixes that problem. Unfortunately, this still doesn't give you the right hash value.
The second problem, which was found by Steve Burnett from Voltage Security, is that they authors aren't really computing MD5. The algorithm is initialized with a certain internal state, called an Initialization Vector (IV). This vector is given in the MD5 RFC as:
word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc ba 98 word D: 76 54 32 10
but this is little-endian format. So, the actual initialization values should be 0x67452301, etc...
The authors use the values directly, so they use: 0x01234567, etc... Obviously, this gives you the wrong hash value. If you use these wrong IVs, you get a collision... though strangely with a different hash value than the authors provide. Steve and I have independently gotten the same result, though of course we could have made mistakes...
So, this looks like it isn't actually a collision in MD5, but rather in some other algorithm, MD5'. However, there's nothing special about the MD5 IV, so I'd be surprised if the result couldn't be extended to real MD5.
UPDATE: you can find source code that demonstrates the collision at http://www.rtfm.com/md5coll.tar.gz. It includes machine readable test vectors and a Makefile, so if you're running on UNIX (or at least FreeBSD) you can do 'make' and get:
rm -f *.o gcc -o md5 -DMD=5 md5.c mddriver.c rm -f *.o gcc -o md5prime -DINVERT_STATE -DMD=5 md5.c mddriver.c # X1 and X1' with ordinary MD5--no collision ./md5 X1.bin MD5 (X1.bin) = e115410841d7a06f2913be15e1760fd1 ./md5 X1prime.bin MD5 (X1prime.bin) = 7005ea821bcc0e64d0eb9852f2bec2bd # X1 and X1' with md5prime--collision ./md5prime X1.bin MD5 (X1.bin) = 8ada1581c24565adac73a2d27160ca90 ./md5prime X1prime.bin MD5 (X1prime.bin) = 8ada1581c24565adac73a2d27160ca90 echo
# X2 and X2' with ordinary MD5 ./md5 X2.bin MD5 (X2.bin) = 55f94e8f79e8a9795fad79f4c6ab5f11 ./md5 X2prime.bin MD5 (X2prime.bin) = 47aaf6e98d0799f9a85db9fd86cb392a # X2 and X2' with md5prime ./md5prime X2.bin MD5 (X2.bin) = 1a2a1d55c87318422367ae3462143fb6 ./md5prime X2prime.bin MD5 (X2prime.bin) = 1a2a1d55c87318422367ae3462143fb6
Loads of fun.
Terence Spies just pointed me to a paper on ePrint that claims to contain collisions in MD5, MD5, HAVAL, and full RIPEMD. I haven't verified that they really contain collisions, but it's hard to believe that the authors would get something that simple wrong. They claim that the MD5 collision took about an hour of compute time and then 15 seconds to five minutes for subsequent collisions with the same initial 512 bits. The MD4 attack is claimed to be possible by hand. Looks like we're living in interesting times.
UPDATE: Both I and a colleague have attempted to verify the vectors in the paper with no success. Of course, we could both have made programming errors, or misinterpreted the (rather terse) paper.
Ed Felten has posted an interesting rumor that someone is going to announce a break in SHA-1 in the near future. Ed writes:
SHA-1 is the most popular cryptographic hashfunction (CHF). A CHF is a mathematical operation which, roughly speaking, takes a pile of data and computes a fixed size "digest" of that data. To be cryptographically sound, a CHF should have two main properties. (1) Given a digest, it must be essentially impossible to figure out what data generated that digest. (2) It must be essentially impossible to find find a "collision", that is, to find two different data values that have the same digest.
CHFs are used all over the place. They're used in most popular cryptographic protocols, including the ones used to secure email and secure web connections. They appear in digital signature protocols that are used in e-commerce applications. Since SHA-1 is the most popular CHF, and the other popular ones are weaker cousins of SHA-1, a break of SHA-1 would be pretty troublesome. For example, it would cast doubt on digital signatures, since it might allow an adversary to cut somebody's signature off one document and paste it (undetectably) onto another document.
At the Crypto conference, Biham and Chen have a paper showing how to find near-collisions in SHA-0, a slightly less secure variant of SHA-1. On Thursday, Antoine Joux announced an actual collision for SHA-0. And now the rumor is that somebody has extended Joux's method to find a collision in SHA-1. If true, this would mean that the SHA-1 function, which is widely used, does not have the cryptographic properties that it is supposed to have.
The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. A collision in SHA-1 would cast doubt over the future viability of any system that relies on SHA-1; and as I've explained, that's a lot of systems. If SHA-1 is completely broken, the result would be significant confusion, reengineering of many systems, and incompatibility between new (patched) systems and old.
It's definitely true that the ability to find collisions in SHA-1 would be a big deal from a cryptographic perspective, but I'm not sure it would be that big a deal from a security perspective. As Ed points out, there are two properties that a CHF is supposed to have:
1. That it's hard to find a message that generates a given digest (preimage resistance)1
2. That it's hard to find two messages that generate the same digest (collision resistance)
It turns out that the security properties of most protocols depend on property one, not property 2. For instance, in Felten's "cut-and-paste" example, the attacker needs to be able to find a second (plausible-looking) message that generates the same digest value that was originally signed. So, while from a cryptographic perspective, an easy way of finding collisions would be a disaster, the effect on most security systems would be minimal.2
Now, as Felten points out, it does sometimes happen that a partial break leads to a full break, but we're quite a ways away from that. For instance, it's known how to find collisions in MD4 (an older and weaker algorithm) for years, but as far as I know, nobody has demonstrated how to find a preimage for MD4 (though Dobbertin showed how to do it for a reduced version 7 years ago.)
All that said, if we do find a way to generate easy collisions in SHA-1 (and if someone has found even a single collision in this period of time, then it's pretty easy) we would need to start the move to some alternative algorithm pronto, just in case, especially since there's no obvious contender, other than a bunch of the longer SHA-1 variants published by NIST, which are potentially vulnerable to the same kind of attack--assuming, of course, that such an attack exists.
1 In the crypto community, preimage resistance is generally broken down into 1st preimage resistance (it's hard to find a message that generates a given digest) and second preimage resistance (it's hard to find a message that generates the same digest as a given message).
2 There are some systems which rely on collision-resistance, but it turns out to be fairly hard to exploit in those systems as well, as I explain here.
The California Supreme Court has just annulled all the same sex marriages that San Francisco had performed.
We agree with petitioners that local officials in San Francisco exceeded their authority by taking official action in violation of applicable statutory provisions," the court wrote.
The court ordered officials "to take all necessary remedial steps to undo the continuing effects of the officials' past unauthorized actions, including making appropriate corrections to all relevant official records and notifying all affected same-sex couples that the same-sex marriages authorized by the officials are void and of no legal effect."
It wasn't a crazy idea to think that creating facts on the ground would force the court's hand, but I guess it wasn't enough.
I mentioned previously that the hill stages of bike races tend to be where the pack breaks up a lot because a lot of the effort is expended climbing the hill and therefore drafting confers less of an advantage. However, there's another effect.
In general, when you're riding, you have to counter two forces: wind resistance and gravity. The power required to overcome wind resistance scales roughly as the cube of speed. By contrast, the power required to overcome gravity scales linearly with the rate of verticle ascent. So, when you're on a flat course, even if you're expending a lot more power, you don't get much of a speed advantage, even in the absence of drafting. By contrast, when climbing, you can get a much greater speed advantage for any given power advantage.
The following table (computed using Analytic Cycling), shows what I'm talking about. The table shows the amount of time lost (in seconds) by various riders against a rider expending 400 watts on a course that taskes that rider an hour on various grades.
As you can see, the steeper the grade the more time the weaker rider loses. Between this effect and the diminished draft advantage, it's not surprising that the peleton breaks up so much on climbs.
The Charge Ti is a bit bigger than my old Wave, but now it's actually .1 oz lighter (8.4 vs. 8.5). The new Wave is also improved, with the belt clip, bit holders, and locking tools, but not the nice new steel. You can also get the "Charge XTi", which is much the same as the Charge Ti, but with a second large bit holder replacing the scissors and a cutting hook on the serrated blade.
Any of these tools would make a nice addition to your toolbox, but they're all a bit heavy. I don't need the file or the saw, so a tool that removed those would be substantially lighter and smaller and not a significant reduction in functionality. Leatherman does have some new units that are lighter with fewer blades but they all require you to open the unit to access the blades, which is a big disadvantage.
1 Equipped to Survive has a nice review
Terence just got back from RAGBRAI and relays the following story from one of the people he rode with.
Apparently my friend was at the Des Moines airport and met Dan Gable at security. They're sitting around waiting to board. Then the announcement comes over the PA "Dan Gable, you may now board the airplane". Gable gets up and boards the airplane to applause from the rest of the passengers in the terminal.
I betcha Linus Torvalds doesn't get that kind of treatment.
While we're on the topic of terrorism, why haven't we seen another DC sniper? Two clowns with a rifle managed to terrorise the greater DC area for over 3 weeks. Rifles are easy to come by and no doubt Al Qaeda has plenty of people who know how to shoot. So, why haven't we seen more attacks?
Nearly three years in, some things strike me about the anthrax-by-mail attacks:
Does this strike anyone else as curious? It's not like the attacks were difficult to mount, so why did they stop? If Al Qaeda was doing it, wouldn't they want to continue terrorizing us?
Warning: the following is not completely thought out...
So, what's the threat model for e-voting? The general concern is that the machines will make errors and that we won't be able to correct them--hence the desired for manually countable paper audit trails.
However, it's important to remember that there are two kinds of error:
So, how much does this matter? I'm not actually that concerned about random errors. That's essentially a software quality control issue, and I don't see any reason to believe that we won't be able to achieve reasonable accuracy against that kind of error. Sure, software has bugs, but then neither people nor mechanical voting systems are perfect either.1 Moreover, we can estimate random error by ordinary testing procedures, even if we don't have some kind of post hoc auditing.
So, what we really need to worry about is systematic error, aka voting fraud. So, how serious a threat is this? Well, there's already an independent check: the polling data. If the day before the election the polls are showing a 60/40 result and the vote returns are 40/60, it's going to be pretty hard for people to believe something hasn't gone wrong. And of course, there are exit polls. So, there's some maximum amount of fraud you can actually perpetrate with impunity--not that I know what that amount is, but I imagine it's on the order of 5%.
So, is that good enough? Well, it depends on how you think a representative democracy works. Roughly speaking we want to have representatives who vote the way you want them to. You can get that in two ways:
What incentivizes the representatives--aside from their pre-existing preferences, of course, which cynical types like I figure are pretty flexible--is the desire to get votes.2 So, as long as politicians believe that voting is fair, then they have an incentive to vote however the polling data indicate, so mechanism (2) is in effect. And if they know that there's only a limited amount of fixing possible, then they still have to keep the polls fairly close. Similarly, as long as only a limited amount of fixing is possible, then most of the time the candidates who reflect the voters' preferences will get elected.
Obviously, a system in which the voting machines can't be trusted isn't as democratic as one where it's not, but in an environment where accurate polling is available as a cross-check, I'm not sure it's really that bad.
1 I should note, however, that the current error rates for e-voting appear to be worse than for mechanical voting, but let's assume for the moment that this problem can be solved with UI engineering.
2 Obviously, there's also the desire for political contributions, but since the major use for those contributions is to pay for advertisements and other campaign expenses, this is basically a vote-seeking activity as well.
Just caught the end of Romeo Must Die on TBS. Not a bad little movie, if you're a Jet Li fan. Anyway, at the end of the movie, right after Mac--played by Isaiah Washington--gets shot, he says "Damn, that's some cold shit." Of course, you can't say "shit" on TV, so TBS overdubbed it to be "shiznit"--which is of course the same word. Maybe the FCC isn't up enough on hip-hop culture to know that, though.
The NYT magazine has an article about the diets of Olympic athletes. Here's US triathlete Hunter Kemper:
Prebreakfast, 7:30 a.m.
Bowl of Life cereal
1 glass of orange juice
16 ounces water
Carrot Cake PowerBar Harvest bar
16 ounces water
Breakfast, 9 a.m.
Bowl of fruit: watermelon, honeydew, strawberries, pineapple
3-egg omelet with American cheese, mushrooms, tomatoes and onions on toast
2 strips bacon
1 or 2 waffles
1 glass apple juice
16 ounces water
45-minute weight training
Carrot Cake PowerBar Harvest bar
32 ounces water
Lunch, 1:30 p.m.
Ham and cheese on a toasted bagel with mayonnaise, mustard, lettuce and tomato
16 ounces water
2-hour bike ride
2 Raspberry Cream PowerGels
1 24-ounce Amino Vital (amino-acid supplement recovery drink)
24 ounces water
Dinner, 6:45 p.m.
Toasted bagel or toast with Cheddar cheese
Salad with Romano dressing
16 ounces water
Power Berry Smoothie
1/2 cup fresh or slightly thawed frozen strawberries
1/2 cup fresh or slightly thawed frozen raspberries
1/4 cup low-fat vanilla yogurt
1 1/2 cups milk
2 tablespoons honey
1 tablespoon soy protein powder
4 ice cubes.
Place all ingredients, except the ice cubes, into the container of an electric blender and blend on high until smooth. With blender running, add 2 to 3 ice cubes at a time through the center opening in the lid, until all ice cubes are added. Blend until smooth. Serve immediately.
Yield: 1 serving, about 16 ounces.
Yeah, that sounds about what I remember from my triathlon days, at least food consumption wise. Hunter works out rather more than I ever could afford to, though.
I wasn't generally impressed by the Message Authentication Security Standards (MASS) BOF IETF San Diego, but one proposal, by Dave Crocker, struck me as quite useful. Remember that one side effect of mail forgery by worms and spammers is that most people receive ridiculous numbers of bounce notifications. The result has been to make them mostly useless.
Dave Crocker's proposal, called Bounce Address Tag Validation is simple. Instead of using your own "MAIL FROM" address when you make an SMTP connection, you provide a signed token1. Then, whenever your mail server gets a bounce, it just checks to see if the token is valid. If it is, you deliver the bounce. If it isn't you just discard it.
Note that this technique will have no impact whatsoever on actually stopping spam2. It just makes bounces work properly again. A small step, but a useful one.
1 The only person who needs to verify the signature is the mail server, so you can just use a MAC here.
2 Dave also proposed a public key scheme which would allow recipient mail servers to reject unsigned connections, which is more inline with traditional address verification schemes. I've got some doubts about that, but it's not required to fix bounces.
Ok, so I forgot my SSH password today. Actually, that's not correct. I think I forgot my SSH password about a month ago, but my fingers remembered, so I could type it automatically. And then I started thinking about what my password was and realized that I didn't remember it. At that point I was suddenly unable to type it. It took meseveral minutes before I could get myself into enough of a Zen state that I was able to automatically type it again. Phew!
In a story that should warm the hearts of those who believe in efficient consumer behavior:
The Indian city of Varanasi is getting through around 600,000 condoms a day, but this is no population control exercise. The weavers of the holy city, home to the world-famous Banarasi saris, have made the contraceptives a vital part of garment production.
The weaver rubs the condom on the loom's shuttle, which is softened by the lubricant thus making the process of weaving faster.
The lubricant does not leave any stain on the silk thread which might soil the valuable saris.
There are around 150,000 to 200,000 hand and power looms in Varanasi alone and almost all are using the technique.
And every loom has a daily consumption of three or four condoms.
At first, weavers stocked up on condoms from the family planning department under a government scheme to provide them free of cost.
Some weavers even registered with fake identities to get their hands on the precious prophylactics.
I guess the demand for free goods really is infinite.
Via Marginal Revolution.
So, I'm at the Sheraton San Diego Hotel and Marina for IETF 60. The hotel is pretty much in the middle of nowhere, and as you'd expect from economic theory, their pricing structure seems to be designed to extract as much monopoly rent as possible:
The time between meetings is short enough that you're mostly trapped here, so you either pay the monopoly prices or go without. But last night, Eliot Lear and I managed to escape to downtown San Diego ($10 cab ride) and had a rather nice (if still a little pricy) sushi dinner.
According to this ZDNet article, Linux may infringe as many as 283 patents (link from Kevin Dick):
Linux potentially infringes 283 patents, including 27 held by Microsoft but none that have been validated by court judgments, according to a group that sells insurance to protect those using or selling Linux against intellectual-property litigation.
Dan Ravicher, founder and executive director of the Public Patent Foundation, conducted the analysis for Open Source Risk Management. OSRM is like an insurance company, selling legal protection against Linux copyright-infringement claims. It plans to expand the program to patent protections.
Of the 283 patents, 98 are owned by Linux allies, OSRM said, including 60 from IBM, 20 from Hewlett-Packard and 11 from Intel. The months-long review examined versions 2.4 and 2.6 of the kernel, or heart, of Linux, Ravicher said.
I'm actually rather surprised that there were only 283 patents. I'd always assumed that any reasonable-sized software package infringed some infinite number of patents.
Here's something interesting, though...
Because of the effect that knowledge of potential infringement has, OSRM isn't releasing its list of patents.
"If we were to publish the patents, we've now put everyone on notice of those patents. For those who have tried to avoid them, we've forced them to know of them, so we've screwed the community," Ravicher said. "If someone really wants to know, they can do the search themselves."
Check out Canada's new 2004 Canada Day collectible quarter, designed by an 11-year old from Saanich B.C.:
I guess they had trouble fitting Bob and Doug McKenzie onto the coin.
Check out this WaPo article about TiVo's attempt to get FCC approval for their new Internet program-sharing feature. It's like this: apparently since July's broadcast flag decision by the FCC, companies need to submit their proposed content control mechanisms to the FCC. So, TiVo has suggested theirs and the NFL opposes it. Why? Well, it turns out that the NFL's broadcast policy forbids the live local broadcast of home games unless the game is sold out, in an attempt to drive local ticket sales. So, the NFL is concerned that TiVo's stuff will be used to circumvent these broadcast restrictions. Isn't that nice: your community subsidized the the stadium but you're the one group who isn't entitled to watch them in the comfort of your home. Outstanding!
I took Caltrain up to San Francisco Friday night and was disturbed to find that although Caltrain wants your money their ability to accept it seems to be woefully inadequate.
The first problem came in the parking lot. You're supposed to pay $1.50, but when I got there the guy in front of me in was struggling to get the machine to take his dollars. AFter a few minutes he finally gave up. I wasn't any more successful and finally ended up leaving a note on my car that said that the machine didn't work. Lisa informs me that this is a common situation and that one generally doesn't get ticketed--and indeed I didn't.
I arrived at the platform just as the train arrived, expecting to buy my ticket on the train, only to learn that they've changed the rules and you can't buy a ticket on the train any more. Instead, they fine you $250 if they catch you sans ticket. I then found myself in line behind two other people desperately tryig to convince the ticket machine to sell me a ticket before the train left. One way ticket? Check. From zone 3? Ok, I guess so. To which zone? WTF?!?! I have no idea. I'm going to the end of the line, so it's either zone 6 or zone 1. Zone 6 it is (to this day I don't know which answer was right). I shove in my $10, grab my change and manage to get onto the train. Others didn't make it, though. I saw a father and son staring at me through the windows of the closed doors. Not that anyone actually checked to ensure that I had a ticket, though.
I wish people who wanted my money didn't make it so difficult for me to give it to them?