HMAC-PRNG implementation issues in Tinycrypt used by Zephyr Bluetooth Host

Description

Currently the HMAC-PRNG implementation used in bt_rand() in [5],
and the Bluetooth Host crypto code, cannot pass the test vectors
given by NIST for HMAC_DRBG in [4].

I'm not sure how big a security vulnerability this is, other than the fact that the
HMAC-PRNG implementation in Tinycrypt has some issues and doesn't do what the
NIST HMAC_DRBG algorithm specifies [1], see the analysis below.

--------------------------------------------------------------------------------
Analysis
--------------------------------------------------------------------------------

The HMAC-PRNG implementation in Tinycrypt used by Zephyr has three issues:

(I.1) Using wrong HMAC key during runtime (affects init, reseed and generate),
(I.2) Wrong implementation of reseed, and
(I.3) Wrong implementation of generate

Ad (I.1):
The basis for this issue is due to an update in Tinycrypt HMAC
implementation (this update was done Jan 27, 2016!). After a call to
tc_hmac_final() in [3], it clears it's internal state of the HMAC in L145.

Tinycrypt HMAC-PRNG implementation in [2] doesn't take the HMAC state
clearing into account as it performs the HMAC operations, thereby using a WRONG
zero'ed HMAC key for some of the HMAC operations; L98, L84 (after init), L195
(after init).

To fix this issue, all calls to tc_hmac_init() must be preceded by a call to
tc_hmac_set_key() in [2].

Ad (I.2):
When additional input is provided in tc_hmac_prng_reseed() in [2], two calls
to update() in [2] is done, while section 10.1.2.4 in [1] specifies that only a
single HMAC_DRBG_Update process is made.

To fix this issue, seed and additional_input must be concat'ed before a call to
update() in [2] is done.

Ad (I.3):
When tc_hmac_prng_generate() is almost done in L209 [2] it makes a call to
update() with the 'prng->v' as input, this is wrong as section 10.1.2.5 in [1]
specifies that the HMAC_DRBG_Update process is called on the additional input
given to HMAC_DRBG_Generate_Generate process (even if additional input is empty), a
feature that tc_hmac_prng_generate() does not support.

To fix this issue, update() in [2] must be updated to work on empty input and
the call made to update() must be called as such.

--------------------------------------------------------------------------------
Proposed Fix
--------------------------------------------------------------------------------

We have a proposed fix (including actual tests against NIST test vectors)
to Tinycrypt ready to be made into a pull request, such that Tinycrypt can be
re-imported into Zephyr.

--------------------------------------------------------------------------------
References
--------------------------------------------------------------------------------

[1] NIST HMAC_DRBG reference
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90Ar1.pdf

[2] Tinycrypt HMAC-PRNG implementation
https://github.com/zephyrproject-rtos/zephyr/tree/master/ext/lib/crypto/tinycrypt/source/hmac_prng.c

[3] Tinycrypt HMAC implementation
https://github.com/zephyrproject-rtos/zephyr/blob/master/ext/lib/crypto/tinycrypt/source/hmac.c

[4] CAVP Testing: Random Number Generators - Test Vectors
https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/drbg/drbgtestvectors.zip

[5] Zephyr Host Crypto
https://github.com/zephyrproject-rtos/zephyr/blob/master/subsys/bluetooth/host/crypto.c

--------------------------------------------------------------------------------
Footnotes
--------------------------------------------------------------------------------

Only a subset of the applicable test vectors in [4] can be passed by
Tinycrypt v2 implementation after it is fixed, due to limitations in it's
design.

The zip file in [4] contains three separate zip file archives, one each for
(TV.a) Prediction Resistance Enabled,
(TV.b) Prediction Resistance Not Enabled, and
(TV.c) Prediction Resistance Not Enabled and Reseed Function Not Supported.

As the implementation doesn't support prediction resistance and has reseed
support only (TV.b) is applicable.

Only half of the applicable tests (the HMAC SHA-256 based ones) in (TV.b)
can be passed, as the implementation doesn't support additional data
during generation.

Environment

None

Assignee

david leach

Reporter

Thomas Ebert Hansen

Labels

Authorized viewers

David Brown
david leach
Flavio Ceolin

CVE

CVE-2017-14200 REJECT

Embargo Lift

None

Components

Fix versions

Affects versions

Priority

Medium
Configure