But, I got thinking about the topic of verifiable AIM conversations. There, the idea of verifying any range of a conversation is important, especially as there is no state to an IM "session" with somebody.
So what we need is rolling signing. But you can't just have the server sign each line of text back and forth, though, because then lines of text can be removed/reordered and it'd still pass as authentic.
My idea: the server gives each line of conversation a unique identifier, and stamps each line with the identifier of the most immediately preceding line of text in the conversation (whether it be from either party), so long as it's within the last few hours (so the server doesn't have to store n^2 "lastid" strings). And a signature of its server key, which may change over time. Then, the server also sends back to the clients:
text (which includes, say, the "From:" field, for simplification)
HashOfChoice( uniqid + lastid + text + server_key )
Now, the client logs all that (just as gaim and other clients do), and AIM provides a verify service in the TOC/OSCAR protocol where you give uniqueid/lastid/text/hash and see if the hash is valid.
The server won't need to care about deleting/reordering validation ... that can all be done by the client with the uniqueid/lastid fields. And if a part is deleted, the client can just say, "these two ranges are verified, but something's missing here."
The only extra cost for the server is maintaining the "lastid" fields, which are temporal.
Beautiful, no? Then people could actually prove snippets of AIM conversations took place and weren't forged.
Punch a hole in my idea, cryptanalysts!