[noise] Symmetric-crypto overhaul and stateful hashing

[Trevor Perrin]

Hi all,

Sorry for being quiet recently!

We have a lot of exciting projects (see the wiki [1]), but a lot of
them depend on how we handle symmetric crypto (hashing/key
derivation).

That's something I'd like to "overhaul" so we have options for more
simplicity, efficiency, and extensibility.  (Our current
symmetric-crypto is conservative, but all the HMACs and the ck and h
hash chains is something implementors often object to).

Overhauling that is a complex task, so that's unfortunately been
blocking other things.


Anyways, below is a proposal for a "symmetric crypto overhaul"
centered on changing our API to the cryptographic hash so we expect a
"stateful hashing object", instead of just a HASH() function.

Such an object is naturally implemented with traditional hashes (like
SHA256) supporting an init/update/clone/finalize API; or Sponge/Duplex
objects like STROBE.

Given such an object, we can define our symmetric crypto using
Sponge/STROBE-inspired "absorb" / "squeeze" / "ratchet" / "clone"
operations.  I think this would remove some small awkwardness and
inefficiency in our current design.


(Below was influenced by a lot of conversations, particularly with
Gilles Van Asche; also Mike Hamburg, Henry de Valence, and David Wong;
and lots of implementer complaints.)

Definitely would appreciate feedback and review, this would be a major
change (though it would just be new HASH options in the Noise protocol
name, we wouldn't break compatibility).


Goals for symmetric-key overhaul:
-----------------------------------

 * Replace ck and h variables with a single hash state which all
inputs are hashed into, for simplicity and efficiency.

 * Allow non-HKDF/HMAC options, for simplicity and efficiency.

 * Allow packing of separate inputs into a single hash block, for efficiency.

 * Provide simpler hashing, so that Noise keys can be derived directly
as key = hash(inputs), without long sequences of nested hashing.

 * Allow for Sponge/STROBE-like algorithms where the hash object is
capable of "Duplex"-style encryption/decryption, so implementations
can minimize code size by using a single crypto primitive like Keccak.

 * Decouple "squeezing" outputs from "absorbing" inputs to make it
easier to output Additional Symmetric Keys.

 * Decouple "absorbing" from "ratcheting" so we can absorb inputs more
efficiently and only "ratchet" when needed for forward-secrecy.

 * Provide an abstract API to the underlying stateful hash which can
be implemented via traditional hashes (with or without HMAC/HKDF), as
well as STROBE or other sponge constructions.


Stateful Hash API
------------------

StatefulHash {

    Absorb(bytes)
    Squeeze(len) -> bytes
    Ratchet()

    Clone() -> StatefulHash

    //Optional, tag not included:

    Encrypt(bytes) -> bytes
    Decrypt(bytes) -> bytes
}


Notes:

 * Noise will never squeeze more than HASHLEN bytes of output, for
compatibility with traditional hashes.

 * Noise will assume that outputs from Squeeze or Encrypt/Decrypt
depend on a transcript containing all previous arguments to Absorb
calls.

 * However, Noise does NOT assume that this transcript contains the
length/type of previous inputs.  So Noise will encode this information
itself in Absorb inputs (which allows slightly more efficient stateful
hash implementations compared to something like STROBE, since Noise
can omit type/length information in many cases).

 * The Encrypt/Decrypt operations will be possessed by some crypto
objects (like STROBE or other Sponge/Duplex objects).  In this case we
don't have to derive a key from the object and use it with an AEAD, we
can just ask the object to encrypt/decrypt things directly.


Example implementations:

STROBE:
  Absorb = AD
  Squeeze = PRF
  Ratchet = RATCHET
  Encrypt = ENC
  Decrypt = DEC

Traditional hashes (SHA256, BLAKE2, etc):
  Absorb = incrementally hash
  Squeeze = output the hash value
  Ratchet = pad to internal block boundary, adding right-parseable
length field (byte-reversed varint), then incrementally hash.

(This is less conservative than our current design, so makes stronger
assumptions on the hash function and performs less hashing; but the
goal here is to make a simpler/more efficient design if we're willing
to put more trust in the hash.  We could implement this API with HMAC
or HKDF, but I'm not sure that's different enough from our current
design to be worthwhile).


SymmetricState API
-------------------
We'd have to tweak the spec's SymmetricState API:

MixHash() would be split into fixed-length and variable-length
versions, so we can pack inputs into hash blocks efficiently (omitting
length fields for fixed-length values).  Length fields are added after
inputs to support streaming, using right-parseable "byte-reversed
varints" for efficiency.

Instead of tracking "k" and "h" variables, they would be calculated on demand.

MixHashFixedLen(data):
  Absorb(data)

MixHashVariableLen(x):
  Absorb(x || len(x))  // byte-reversed varint

MixKey(input_key_material):
  Absorb(input_key_material) // assuming fixed-length

GetHandshakeHash():
  new = Clone()
  new.Absorb("h")
  return new.Squeeze(HASHLEN)

GetSymmetricKey():
  new = Clone()
  new.Absorb("k")
  return new.Squeeze(32)

GetAdditionalSymmetricKey(label):
  new = Clone()
  new.AbsorbVariableLen(label)
  new.Absorb("a")
  return new.Squeeze(32)

Split():
  newi = Clone()
  newi.Absorb("i")
  return newi.Squeeze(32)
  newr = Clone()
  newr.Absorb("r")
  return newr.Squeeze(32)
  return (newi, newr)  //for (initiator, responder)



Example and comparison
--------

Here is our current Noise_X expanded into HKDF/HASH calls to derive
the 3 encryption keys (k1, k2, k3) used to encrypt the (initiator
static, handshake payload, transport messages).  Also the final
handshake hash "h" is derived:

ck = h = HASH("Noise_X_25519_AESGCM_SHA256")
h = HASH(h || prologue)
h = HASH(h || s)
h = HASH(h || e)
ck, k1  = HKDF(ck, es)
h = HASH(h || s)
ck, k2 = HKDF(ck, ss)

k3 = HKDF(ck, 0)
h = HASH(h || handshake_payload_ciphertext)


With a stateful hash object using a traditional hash we would get the
following (deriving k1, k2, k3, handshake-hash "h", and an additional
symmetric key "ask"):

transcript = name || len(name) || prologue || len(prologue) || e || es
k1 = HASH(transcript || "k")

transcript = transcript || s || ss
k2 = HASH(transcript || "k")
k3 = HASH(transcript || "i")

transcript = transcript || handshake_payload_ciphertext
h  = HASH(transcript || "h")
ask = HASH(transcript || label || len(label) || "a")

For interactive handshakes we'd probably add a Ratchet() after each
message that calls MixKey(), to make sure that secret-key isn't
recoverable from a compromise; though this rule could possibly be
refined (e.g. if you're still holding the DH keys, or if you've
already done enough hashing after mixing the secret).


Trevor


[1] https://github.com/noiseprotocol/noise_wiki/wiki