[messaging] "Short" authentication strings
warner at lothar.com
Mon Jul 7 23:41:25 PDT 2014
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
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.
More information about the Messaging