[messaging] "Short" authentication strings

[Brian Warner]

On 7/7/14, 10:18 PM, Tony Arcieri wrote:

> I'm working on a program which authenticates public keys using a
> symmetric key derived from a "short authentication string" (five
> random words).
> - Is 60-bits entropy too little, even "stretching" it with scrypt?
> - What scrypt parameters are needed to make this actually secure?

Nifty! That sounds a lot like one of the modes I'm building into
Petmail. Some thoughts:

* it sounds like you only care about authenticating the pubkeys, but
  you're actually encrypting them too. You might be able to simplify
  things: instead of xsalsa20, just use a keyed MAC (HMAC-SHA256 or bare
  poly1305 aka "crypto_onetimeauth").

* I personally do feel that 60 bits can be stretched into something
  reasonably secure. I have a little online brute-force-attack cost
  estimator tool at http://keywrapping.appspot.com that I wrote up for
  work (so at first glance it will appear Firefox Account -specific),
  which shows the cost of searching various key-spaces with different
  amounts of scrypt (drag the black rectangles to vary the parameters).
  A 60-bit password stretched with scrypt N/r/p = 64k/8/1 takes less
  than a second on a modern laptop, but would cost about 3 trillion
  dollars (of EC2 time) to search.

* it'd be nice if scrypt accepted a larger salt, but remember you can
  always just concatenate a second salt with the password before feeding
  it into scrypt.

* the attacker's window opens when they see the MAC'ed pubkey traverse
  the wire and they learn the salt. Their task is then to scan the
  password space, stretch each candidate, until they find one that
  matches the MAC that you sent. They can delay the legitimate messages
  until they succeed, or until you get tired of waiting and give up. So
  their attack is nominally offline (e.g. if they had infinite computing
  power, they could always win), but they're limited by your patience.

* validating pubkeys is much better than encrypting a session key: since
  the attacker can continue their search after your protocol has
  finished, it's great that there's nothing useful for them to learn

* the name makes me think of "Short Authenticated Strings", a paper[1]
  by Serge Vaudenay, which mostly does what you want, would not require
  stretching, and is not vulnerable to the offline attack that a short
  password would be (e.g. a single 12-bit word would be enough to limit
  the attacker to a one-in-4096 chance of successful forgery per
  protocol execution). And it involves no secrets: all messages, even
  the human-delivered phrase, can be public. But, it requires
  machine-generated strings to be tranferred in both directions. It's a
  beautifully simple protocol (just random numbers, hashes, and XOR),
  but the message flow tends to be annoying. In your protocol, it would
  require both humans to read a string from their machines out to the
  other side, after the pubkeys had been exchanged, and you wouldn't
  have the option of "re-rolling" to get a nicer phrase.

cheers,
 -Brian

[1]: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.8504