Log in

No account? Create an account
brad's life [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Verifiable AIM conversations [Mar. 19th, 2002|05:02 pm]
Brad Fitzpatrick
Digitally signed messages are cool, but it requires the entire message be signed and sent-along to be verified. I thought it'd be cool if you could get a digitally signed message from somebody, forward a snippet of it along to somebody else, and still have that snippet be verifiable. (please, stop... I know all the arguments against why this would be a bad thing.)

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!

[User Picture]From: calliste
2002-03-19 05:04 pm (UTC)
(Reply) (Thread)
[User Picture]From: asa_dachi
2002-03-20 08:43 pm (UTC)
Where?!? I don't see 'em... *feels the wind rushing over his head*

(Reply) (Parent) (Thread)
[User Picture]From: krow
2002-03-19 05:15 pm (UTC)
Something about this smells of a rotary system to me.
(Reply) (Thread)
[User Picture]From: visions
2002-03-19 05:39 pm (UTC)
my friend greg wrote CryptIM which you might be interested in.

now, speaking of your algorithm... it would be subject to brute force. you have:

HashOfChoice( uniqid + lastid + text + server_key )

uniqid and last id are the only thing that are dynamic. text will be known, since it has to be displayed. the server key won't be known.. but for any given interval.. it has to be constant (unless you force the server to store the key). there would also have to be some sort of timestamp in the hash or text if the keys ever changed.

as it sits, you end up with 2 changing fields (probably at most 32bit we shall assume), a known field, and a static field. comparative hashing would allow you to bruteforce.

now, you might have made it easier as well. if the packet is as you specified:

text (which includes, say, the "From:" field, for simplification)
HashOfChoice( uniqid + lastid + text + server_key )

then you have taken the unique aspects out of the conversation. you would now be subject to insertion (man in the middle) attacks, assuming that id's are not linear (which would be a whole new bag of problems). so that would leave you with 1 unknown but potentially static field. even less to bruteforce.

anyway, thats just a quick glance. thoughts?
(Reply) (Thread)
[User Picture]From: muerte
2002-03-19 06:02 pm (UTC)
So you would only be able to verify the conversation in small chunks? You would only be able to verify that this text and response were valid, and then verify the next chunk the same way? Since you're only hashing "text" plus "lastid" right?
(Reply) (Thread)
[User Picture]From: brad
2002-03-19 07:05 pm (UTC)
No, this scheme would let you verify as small or large of a region as you wanted.
(Reply) (Parent) (Thread)
[User Picture]From: madshrubbery
2002-03-19 06:43 pm (UTC)
I couldn't believe how easy it was to fake IMs until I made a whole sloo of them for one of my "stories." Sounds like a great idea.
(Reply) (Thread)