[Thali-talk] A chat with some crypto folks about our discovery design

[Yaron Goland]

I had a chance to sit down with a group of actual cryptographers at Microsoft to discuss Thali's use of crypto for our discovery design, aka the beacons (defined in [1] and [2]). The purpose of this meeting was just to get a first sniff of what we are doing and see if it raises any red flags. It is not a thorough review and it provides no guarantees of correctness.

The main take away from the discussion is that what we are doing looks right but cryptographic protocols are always a tricky thing and it's possible there is some subtle error in its design that is not apparent in a cursory review. At some point we really should try to get an intensive review by an expert who can spend several days tearing it apart. It's not clear if we can get such an expert to volunteer or if we will have to raise money to pay someone. The later is certainly not something we are currently budgeted for. To make it as easy as possible to get such a review I have written up a 2 page version of our protocol description that just deals with the crypto related issues in [3].

For those who care the specific issues that were identified during the review were:

Secp256r1 vs secp256k1 - We are using k1, the Koblitz curve. This was mostly because it's known how the curve was generated where by the process for generating r1 is not known. In theory k1 might be slightly weaker than r1 but it doesn't seem to matter in practice.

Fuzzing the expiration time - It is good practice to fuzz the expiration time we put in a beacon so we don't provide exact timing data for the device. I'm not completely clear on the attack but this is easy to do.

Set IV to 0 - There is no point in having the IV because each key we use is unique and if it isn't then IV we generate won't be unique either since they come from the same HKDF function.

Make PSK Secret into 32 bytes - Currently we had the secret at 16 bytes but it was felt that this wasn't strong enough and we should use 32 bytes instead. Again, I'm not clear on how feasible the attack is but since we plan on use an aes 256 cipher for TLS using 32 bytes seems good.

The middle two issues are filed to be fixed in [4]. The last issue should be dealt with in [5]. Note that I also updated the specs as appropriate.

Another point the crypto folks made is that ECDH operations are really seriously expensive. So where possible it would be very good to avoid them. See [6] for a discussion on how this could be done. If we find that the cost of dealing with ECDH is too high then we can explore the options in [6]. They are all pretty easy to implement.

Thanks,

                                Yaron

[1] http://thaliproject.org/PresenceProtocolForOpportunisticSynching/
[2] http://thaliproject.org/PresenceProtocolBindings/
[3] http://thaliproject.org/BriefDescriptionOfDiscoveryProtocol/
[4] https://github.com/thaliproject/Thali_CordovaPlugin/issues/546
[5] https://github.com/thaliproject/Thali_CordovaPlugin/issues/418
[6] One approach is to go through the address book and generate the ECDH shared secret for everyone in the address book, let's call that value Sxy. This would be done once per peer since the value is invariant. Then when generating a beacon string we would take the expiration and calculate the exact date (e.g. Monday/day/year) in GMT and we would use HKDF with Sxy as the salt and the date as the input. We would generate a 16 byte and a 32 byte value from the HKDF. The 16 byte value we would use as a flag in the beacon. This identifies who is sending the beacon and who the beacon is for. This value will rotate every day so it can only be used to track someone for a day and it doesn't disclose who they are. The 32 bytes is then the secret for the PSK. There is a miniscule possibility of a collision on the flag across peers but if it does occur the PSK will settle things.

The trick with this approach is that we have to generate all the flag/PSK values for all peers we track at least once every day. If we have a short list (what we called the hot list in [1]) then this is feasible. But if we have a corporate directory with 100,000 people then it isn't. To really make this work we would probably have to introduce a two stage approach where we support both the ECDH and the pre-shared key approach. We would use the pre-shared key approach only with a small list of people who know we are using the key approach and ECDH for everyone else.

Another approach for folks who have a central service is to have the central service generate the 'daily values' for all pairs of peers and have the central service hand out the secrets to the mobile devices whenever they are on the Internet. To handle intermittent connectivity, the server could hand out say a weeks' worth at a time. The server would have to generate roughly ((N^2-N)/2)*(16 + 32) bytes/day so with 100,000 entry address book that works out to 223 Gigabytes of data a day (assuming the server stores calculated values so it only has to generate them once). Each device would need to then download 2 Megs/day of data. In some circumstances, especially when operating in ruinously expensive places, this could be cost prohibitive. But in any normal situation even downloading a weeks' worth of data (e.g. 14 megs) would be a joke. And storage is not a problem. So this is feasible.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://pairlist10.pair.net/pipermail/thali-talk/attachments/20160217/8bce76c4/attachment.html>