November 16, 2013

Is Google signing your chat messages?

A couple of days ago, my friend Tom asked me using GMail’s Google Talk widget why one bash command worked while another didn’t. The commands looked the same, but to make sure no UTF-8 silliness was going on, I checked Adium’s debug window. There, I noticed the messages both contained an XML element I didn’t recognize, google-mail-signature:

<message type='chat' to='thijsalkemade@gmail.com' from='...@gmail.com/...' id='...' iconset='classic'>
	<body>...</body>
	<google-mail-signature xmlns='google:metadata'>JZRvRiVt_pz4h4l-VIms2ufrvbQ</google-mail-signature>
	<active xmlns='http://jabber.org/protocol/chatstates'/>
	<x value='disabled' xmlns='google:nosave'/>
	<record otr='false' xmlns='http://jabber.org/protocol/archive'/>
</message>

This does not appear to belong to any of the officially documented Google XMPP extensions, so I tried to figure out what it is.

~~Zash pointed out that substituting _ with /, - with + and adding a = to fix the padding turns the data into valid base64~~ Florob pointed out that this is base64url encoded, with padding left out. Adding back one = of padding and base64 decoding it turned it into 20 bytes of random looking data. What sort of signature could that be?

RSA or DSA?

Cryptographic signatures for email are often using RSA or DSA. It is unlikely this is an RSA signature: an RSA signature is always of the same length as the keypair and 160 bit RSA would be undeniably insecure (although Google has in the past signed their emails with a key not fully up to best practices). DSA signatures must contain a pair of two values, typically using ASN.1 encoding. That means it must always start with 0x30, which is not the case.

20 bytes is however exactly the length of a SHA-1 hash. Could it be the hash of a signature? That would make little sense, as nobody would be able to verify the signature from just the hash. It is likely either:

The SHA-1 hash of the message, sender, recipient or any combination of those.
The HMAC-SHA-1 MAC of the message, sender, recipient or any combination of those.

Varying the hash

I observed the following:

Sending the same message to the same recipient gets the same signature.
Changing the message changes the signature.
Changing the recipient changes the signature.
Changing the sender changes the signature.
The signature is not generated by the browser.
Sending the same message after turning Off-the-record on on the web interface gets the same signature.
Only messages sent by the GMail web interface get the signatures (pre-Hangouts Google Talk for Android doesn’t).
A message sent from a different XMPP client with an intentionally botched signature is not rejected.
The Windows Google Talk standalone client does not add them and doesn’t appear to use them (no references to google-mail-signature).

SHA-1

I tried to reproduce the hash by testing 2.4 billion permutations of:

SHA1(sender + delimiter + recipient + delimiter + message)
SHA1(sender + delimiter + message + delimiter + recipient)
...

for (almost) all 1-4 character delimiters, all possible orderings of sender, recipient and message and a couple of different formats of sender and message I could think of. None of them matched the hash on the message.

Of course, it could be a different delimiter or encoding the message in a different way. But unless someone else manages to find how these hashes are calculated, it looks like only Google can generate them, using a deterministic procedure.

HMAC-SHA-1

From the fact that the data is called “signature”, I think it is likely these are HMAC-SHA-1 MACs of the message generated using a key only Google has. This would make it impossible for anyone to generate a fake signature, unless they brute-forced the key used by Google. The difference between a MAC and RSA or DSA signatures is roughly the difference between symmetric and asymmetric encryption: to verify a MAC, you need the key that was used to generate it. To verify an RSA or DSA signature, you need only the public key, but you need the secret key to create that signature.

Why is this dangerous?

Cryptographic signing isn’t automatically bad. Many emails are signed using DKIM and a number of people choose to sign their emails using GPG. But these are emails - most people will assume correctly these are stored forever and that the signatures can be verified forever.

IMs are different. Not only does it appear this feature is not documented anywhere, but people generally assume IMs are more ephemeral than emails. Signing them should not happen while people aren’t aware of it.

Even though nobody but Google is able to verify or fake these signatures, there is one signing oracle that can be used: Google. The fact that the signatures are deterministic means they can be later verified by sending the same message again.

If you ever use GTalk on GMail to send a message describing some illegal activities, that message will receive a signature from Google. If the recipient stores that message and signature, they have cryptographically verified blackmail material: they could later turn both message and signature over to law enforcement. Law enforcement could then take control over your account and resend the message to the recipient to verify the signature is correct, or they could try to force Google to verify the signature. If it succeeds, it proves cryptographically that your account sent that message. Of course they can’t prove the order or context of your messages, but one message in itself might be enough to get you into trouble.

I think Google should either:

Document what these are and how they are generated, so people can fake them.
Remove them from all outgoing messages (they are probably only of internal use - I don’t see any benefits in signatures nobody can verify).
Inform users that everything they say can later be cryptographically verified, even when using (what they call) “OTR”.

xnyhps’ blog