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 _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
