UP-01-011 SAS-RTC does not protect against bruteforced Collisions

[cure53]

The module sas-rtc is designed to authenticate uProxy connections by letting the users exchange and verify their SDP fingerprints. Because the full fingerprint is too long to exchange it by voice, sas-rtc truncates it to four bytes, then encodes those into words.

However, the hash can be bruteforced offline, and a four-byte hash is easy to brute force in seconds even with a single GPU. For example, the documentation of oclHashcat claims to achieve a hash rate of 12328M per second on one machine with eight consumer-grade graphics cards, meaning that that machine could probably brute force the truncated fingerprint in something around the order of 350ms, which should be sufficient even under the real-time requirement of such an attack. As discussed in the design doc, Short Authentication Strings for TLS would be a reasonable solution for this.

Even though it is not implemented in browsers yet, it should be possible to implement something like that in the uProxy code. If that is too much trouble, we recommend hashing the fingerprint together with the remote user’s ID or so to guard against birthday attacks, then using a sufficient number of bits from that hash (maybe 112 bits, resulting in 14 words).

[bemasc]

In order to defeat the current "SAS-RTC" design, it is not sufficient to find an arbitrary preimage to the short hash. Rather, the attacker must maintain an active MITM, and present to each side a public key whose short hash matches the requirement. Finding a preimage for a specified 32-bit hash will typically require generating ~4 billion keypairs, which is computationally nontrivial. However, it is possible that an attacker with significant resources could produce a database of such keypairs in advance.

To defeat this attack, I believe we should incorporate a commitment protocol similar to http://tools.ietf.org/html/draft-miers-tls-sas-00 (but over the signaling channel initially, not in the DTLS handshake).

[cure53]

As far as we can tell, the fingerprint is computed not just over a public key but over the entire certificate. Rather than generating lots of keys, an attacker would only need to modify an unimportant field in the certificate, re-sign the certificate and hash it with sha256.

While this may seem very expensive, it probably isn't: It should be possible to implement re-signing in a very fast way if the key is chosen appropriately. For example, if the private RSA exponent is chosen as 2, the whole exponentiation required for signing would turn into one multiplication. (The key would also be very weak, but an attacker won't care about that.) Multiplying 1024-bit-numbers with libgmp takes about 1200 clock cycles on a modern CPU, meaning that if the private exponent is chosen as 2, generating 2^32 RSA signatures would take about 6 minutes on one PC.

[iislucas]

+1. I've had a bunch of conversation on this and had the similar analysis.

A commitment protocol is what we are planning to use; that sound right to you Cure53?

On Sat, Sep 27, 2014 at 4:32 AM, Cure53 notifications@github.com wrote:

As far as we can tell, the fingerprint is computed not just over a public key but over the entire certificate. Rather than generating lots of keys, an attacker would only need to modify an unimportant field in the certificate, re-sign the certificate and hash it with sha256.

While this may seem very expensive, it probably isn't: It should be possible to implement re-signing in a very fast way if the key is chosen appropriately. For example, if the private RSA exponent is chosen as 2, the whole exponentiation required for signing would turn into one multiplication. (The key would also be very weak, but an attacker won't care about that.) Multiplying 1024-bit-numbers with libgmp takes about 1200 clock cycles on a modern CPU, meaning that if the private exponent is chosen as 2, generating 2^32 RSA signatures would take about 6 minutes on one PC.

— Reply to this email directly or view it on GitHub https://github.com/uProxy/uproxy/issues/393#issuecomment-57046374.

Lucas Dixon | Google Ideas

[cure53]

That sounds good and should make attacks on uproxy a lot harder - it would only be possible to MITM one in a few million uproxy connections that way without doing thousands of reconnections.

We recommend to also implement a warning message and a cooldown period that trigger if too many reconnections have happened between revealing the own bits in the commitment protocol and verification of the connection by the users in a short time, containing the name(s) of the user(s) from whom the connections seem to be coming, to alert the user that the social network or an attacker with TLS MITM capabilities seems to be attacking him. http://tools.ietf.org/html/draft-miers-tls-sas-00#section-5 suggests the same: "Applications SHOULD abort after multiple failed TLS handshakes and notify the user."