[messaging] How secure is TextSecure?

[Brian Smith]

Moxie Marlinspike <moxie at thoughtcrime.org> wrote:

> On 10/31/2014 09:56 PM, David Leon Gil wrote:
> > -- They present an unknown key-share attack on TextSecure; this is
> > rather serious, to say the least.
>
> I'm not so sure.  One party claiming another's fingerprint is a minor
> but general issue with fingerprints almost everywhere they are used.  It
> affects SSH, OTR, PGP, etc.
>

I think Moxie has a good point here.

I think the thing to take away from this paper is that the TextSecure
protocol might be close to being something that can be formally proved, and
that it is worth considering the role of formal proofs in the design and
development of TextSecure. There may be things that can be changed in the
to make such proofs of security easier or clearer. Alternatively, there may
be other ways of approaching a security proof for TextSecure that do not
depend on changing the protocol. The authors seem to have chosen to change
the protocol for their proof, probably because they couldn't figure out how
to make a proof for the protocol as it is. I think it would be cool if
people could build upon their work to create a proof for the protocol
without changes.

More below.


> The two-phase QR code thing they propose doesn't work for offline
> verification (people putting fingerprints on business cards, email sigs,
> etc) or remote verification (people reading fingerprints over the
> phone). It also feels pretty cumbersome.  Right now, preserving those
> types of verification feels more valuable to us than compromising on
> them to stop a somewhat esoteric UKS.
>

I think that is a reasonable. Still, it may be useful to investigate
changes to the protocol that works better than their suggestion, and which
still affords a formal proof.


> > 2. They also claim that the security of truncated
> > SHA2-256, as used in TextSecure tags, is unknown.
>
> Since this is extremely common practice, is approved by NIST, and is
> approved in the HMAC RFC, I think we're in good shape.
>

I think it is important to point out that Moxie's statement doesn't
contradict the authors' statement. Here is the authors' full statement:

    Surprisingly, TEXTSECURE does not transmit the complete
    output of HMACSHA256. The message tag in Figures 2 and
    3 does only represent the first 64 bit of the 256 bit MAC.
    Upon request, TEXTSECURE’s developers stated that this
    just happens to reduce message size. However, SHA256
    has been designed to achieve its security goals with an
    output length of a full 256 bit. While Biryukov et al. [19]
    analysed the security of reduced-round SHA256, to the best
    of our knowledge, the security of a reduced-length SHA256
    has not been investigated, yet. However according to
    NIST [20, chapter 5.5], a MAC length of 80 bit is
    recommended when a MAC is used for key confirmation,
    which is the case in TEXTSECURE (at least) in the first
    message of a new session.

It is fair for them to point out that they couldn't find a proof that
truncating HMAC-SHA256 is secure. In fact, they *have* to say that in their
paper, because their attempted proof assumes it, but they offer no proof.
Ideally, they would just cite an already-published formal proof, or write a
proof of their own. Perhaps somebody could suggest one to them. At the same
time, they didn't say that TextSecure is terrible because it truncates the
HMAC. In fact, they say the opposite: TextSecure seems to be doing
something OK because it is following NIST's recommendations. (Note that I
don't follow how truncating the HMAC to 64 bits is in line with NIST's
recommendations for at least 80 bits, but I'm probably overlooking or
misunderstanding something.)

> More concerning re
> > tags: TextSecure is only using an 8 byte tag. 64-bit authenticity is
> > plainly insufficient.
>
> I dunno.  Sure 16 or 32 bytes would be better, but we're dealing with a
> world of really extreme size constraints where another 8 bytes is a
> *lot*.  In the context of how this tag is specifically used for
> TextSecure messages (where there is no oracle), I'd like to hear more
> about where you see a practical attack.
>

I think that when this discussion is over, it would be useful to update the
TextSecure protocol documentation with an explanation as to why the HMAC is
truncated to 8 bytes (as opposed to 16 bytes as one might expect by
default, or 4 bytes or 6 bytes), and why it is felt that the truncation is
secure, because it isn't clearly documented now.

I assume the authors think it would be good for TextSecure to have a formal
proof, and I agree. Do others?

Also, one takeaway from the paper that I had is that the TextSecure
protocol seems good overall. I think that's pretty positive feedback.

Cheers,
Brian
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20141101/96537949/attachment.html>