Systems that use SHA1(k || m), or any other Merkle-Darmgaard hash in H(k || m), are trivially broken in 20 lines of Ruby code.

There are attacks against SHA1 that make SHA1(m || k) unsafe, which is a point I think Nate is really trying to get across here.

You might have the terms in that construction backwards, but I'm not going to dig through OASIS standards for more than the 5 minutes I just spent trying, because very few real-world systems use WS-Security.

Yes, I had it backwards; it's SHA1(m || k). Fixed now.

I'm in the unfortunate position of maintaining a real-world system that uses WS-Security, and this is not the only potential problem I've found. For example, the "m" part of the digested string is composed of parts that are concatenated without delimiters (just like the old AWS authentication digest); one implementation was vulnerable to message forgery because it could be convinced to split the same string in more than one way.

That attack you described is a canonicalization flaw, and I think it's one of the least talked-about, most prevalent failures in MAC-only security systems. Colin had a good canonicalization flaw in Amazon AWS.