[messaging] RFC: async NaCl relay

Max Skibinsky max at skibinsky.com
Tue Dec 22 18:15:46 PST 2015

> No, include the difficulty in the token and HMAC. And the server shouldn't need to store anything, when it receives the token back it uses the HMAC to ensure that the token was issued by the server.

aha! starting to get this. a bit confused over sequencing, let me try
to clarify it with a diagram. restoring back to your original
verify_token formula:

A => GET to /sessions => R => sends verify_token = concat( r_nonce,
timestamp, difficulty, HMAC( concat(r_nonce, timestamp, difficulty) )
A does POW so that h(a_nonce, verify_token) satisfy leading 0^diff
A => POST /sessions/[verify_token], a_nonce => R
R verifies timestamp, HMAC inside verify_token, and a_nonce
satisfaction of POW difficulty outside verify_token.

If my understanding is correct, will it be possible to attack via
pre-calculation? verify_token uniqueness is generated from predictable
timestamp and random r_nonce. if R doesn't keep any new state after
GET /sessions, he doesn't know which r_nonce it had issued; it only
can verify that HMAC in verify_token is correct. (and i presume it
keeps list of activated verify_token sessions after successful POST

what if Mallory takes tomorrow's timestamps and precalculate 1M
verify_token and 1M nonces satisfying their POW and then sends them
within tomorrow timestamp window (which have to be non-zero to allow
for weaker clients)? or I'm still misunderstanding your schema?

> No, just have a static c25519 keypair on the relay r_lt_sk, r_lt_pk. When generating the session key the client does DH with both r_lt_pk and r_sess_pk and includes both into the hash. Client also ensures r_lt_pk hasn't changed since last time. You also then need to handle cases where server updates long term keys.

I like this approach, this is great. good stopgap to protect no-TLS
relays from MIM attacks. Trusting/forcing TLS is of course better, yet
after recent review of current "out of the box" images on popular
clouds (AWS, DO, etc) it's excruciatingly clear a strong TLS
deployment is pretty advanced skill check.

> Actually, upon reading this again the real issue is that you are trying to use the same key pair for encryption and authentication.
> Don't do that, the HPK should be based on a signing keypair (Ed25519). If you want to bootstrap an encryption session
> (curve25519 keypair or axolotl) just send the encryption keypair signed by the authentication keypair.

very interesting! so hpk becomes signing key only, are all encryption
keys are ephemeral (exchanged as needed under hpk signature?). The
elegance of this is clear on intuitive level - I'm curious what are
the formal issues of using same key for auth and encryption and what
sort of weakness that introduces? (just an RTFM link is fine if
simpler) I presume that is the reason why Nacl itself uses different
keys for crypto_box and crypto_sign?

> Anyone can generate a new keypair and HPK, so you allow anon anyway. I was suggesting that since you treat the payload as an opaque blob
> you may have the option of a small send-only device that just uses, e.g. symmetric key encryption for messages.
> It would then just add complexity to force it to handle asymmetric crypto just to send a message.

I think we are one step away from fully anon messaging. yes, anybody
can generate [a_pk,a_hpk] at will, yet by itself it's useless. they
need to receive b_pk from somebody else first to be able to message
them (and know their hpk).  let's say hpk is somehow leaked and that
hpk is spammed with 1m garbage messages from 1m random hpks. to
address this issue in 3.3.3 there is the option to specify 'from'
whitelist on download as optional field. So client policy might be:
- request 'count'
- if count is unexpectedly large, first download all whitelist
messages from all guest hpks on her keyring
- once whitelist is downloaded, nuke rest of the messages waiting for
her hpk. currently it is done by list of IDs, yet I clearly should add
"delete_all" option so spam messages from unknown HPKs do not need to
be downloaded.

what troubles me is opening pandora box to have messages accepted for
b_hpk but having no attributing a_hpk of the source. in such case the
concept of filtering by whitelisted hpks is no longer practical - any
of these 1M random messages could have useful payload.

sounds like the design trade off here is either make it much easier
for small devices but have relays more open to spam, or make it a
computationally harder to "just send a message" yet having stronger
policy option on how to recover if any hpk is flooded. given current
ratio and trendline of CPU/$ (http://bit.ly/1PjnZ6o) imho its easier
to give a bit more cpu work to client devices.

More information about the Messaging mailing list