[SEC] Unnecessary HMAC Call in HKDF

[pornin]

(Tags: nbc-audit-2020-1, difficulty:undetermined, severity:informational, bug)

Location: blscurve/eth2_keygen/hkdf.nim, lines 149-162

Description

When the underlying hash function has output length n bytes, HKDF-Expand() produces output with HMAC calls; each HMAC invocation produces exactly n bytes. The hkdfExpand() implementation computes the number N of full HMAC blocks, then loops exactly N+1 times:

  let N = output.len div HashLen
  var t: MDigest[T.bits]
  let oArray = cast[ptr UncheckedArray[byte]](output)

  for i in 0 .. N:
    ctx.init(prk.data)
    # T(0) = empty string
    if i != 0:
      ctx.update(t.data)
    ctx.update(info)
    when append.len > 0:
      ctx.update(append)
    ctx.update([uint8(i)+1]) # For byte 255, this append "0" and not "256"
    discard ctx.finish(t.data)

    let iStart = i * HashLen
    let size = min(HashLen, output.len - iStart)
    copyMem(oArray[iStart].addr, t.data.addr, size)

If the requested output length (output.len) is exactly a multiple of the hash function output size (HashLen), then N calls to HMAC are sufficient; the value computed in the last iteration is ultimately discarded: the size value is then 0, and none of the bytes are copied to the output.

In the context of the BLS implementation, this inefficiency has negligible impact:

• The hash function is SHA-256, with a 32-byte output; when hashing data into a curve point, each invocation of HKDF is for 48 bytes, which is not a multiple of 32.
• The only other use of HKDF is for key generation, when producing the Lamport secret key, of size 8160 bytes. 255 HMAC invocations are needed, and the implementation does 256; the unnecessary 256th HMAC invocation is an overhead of only 0.4%. The perceived overhead will be in practice even lower, because key pair generation also involves other steps which are more expensive, thus further reducing the relative cost induced by this issue.

This is a "security issue" only insofar as it makes the HKDF implementation use too much CPU, which may increase the effect of DoS attacks, if the HKDF implementation were to be used in a context where its cost represents a computational bottleneck (which does not appear to be the case here, hence the sev:info status).

Recommended Mitigation

A comment in hkdf.nim says that it should be merged with the implementation in https://github.com/status-im/nim-eth/blob/b7ebf8ed/eth/p2p/discoveryv5/hkdf.nim. The latter happens to have an extra test to account for the case described above and make sure that N contains exactly the number of required HMAC calls; the loop then performs N iterations.

[mratsim]

Thank you for the review.

Actually we also have a 3rd BearSSL-based HKDF implementation used in libp2p: https://github.com/status-im/nim-libp2p/blob/5819c6a9/libp2p/crypto/hkdf.nim.