Paper 2023/781
$\mathsf{Skye}$: An Expanding PRF based Fast KDF and its Applications
Abstract
A Key Derivation Function (KDF) generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF, the most deployed KDF in practice, is based on the extract-then-expand paradigm. It is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging. HKDF is a generic KDF for general input sources and thus is not optimized for source-specific use cases such as key derivation from Diffie-Hellman (DH) sources (i.e. DH shared secrets as key material). Furthermore, the sequential HKDF design is unnecessarily slow on some general-purpose platforms that can benefit from parallelization. In this work, we propose a novel, efficient and secure KDF called $\mathsf{Skye}$. $\mathsf{Skye}$ follows the extract-then-expand paradigm and consists of two algorithms: efficient deterministic randomness extractor and expansion functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs leads to a significant efficiency gain over HKDF while maintaining the security level. We provide concrete security analysis of $\mathsf{Skye}$ and both its algorithms in the standard model. We provide a software performance comparison of $\mathsf{Skye}$ with the AES-based expanding PRF $\mathsf{ButterKnife}$ and HKDF with SHA-256 (as used in practice). Our results show that in isolation $\mathsf{Skye}$ performs from $4\text{x}$ to $47\text{x}$ faster than HKDF, depending on the availability of AES or SHA instruction support. We further demonstrate that with such a performance gain, when $\mathsf{Skye}$ is integrated within the current Signal implementation, we can achieve significant overall improvements ranging from $38\%$ to $64\%$ relative speedup in unidirectional messaging. Even in bidirectional messaging, that includes DH computation with dominating computational cost, $\mathsf{Skye}$ still contributes to $12$-$36\%$ relative speedup when just $10$ messages are sent and received at once.
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. ACM ASIACCS 2024
- Keywords
- KDFDeterministic ExtractionExtract-then-ExpandHKDFX3DHSignalExpanding PRFPRF-PRNG
- Contact author(s)
-
amitsingh bhati @ esat kuleuven be
dufkan @ mail muni cz
elena andreeva @ tuwien ac at
arnab roy @ uibk ac at
bart preneel @ esat kuleuven be - History
- 2023-11-15: last of 6 revisions
- 2023-05-28: received
- See all versions
- Short URL
- https://ia.cr/2023/781
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/781, author = {Amit Singh Bhati and Antonin Dufka and Elena Andreeva and Arnab Roy and Bart Preneel}, title = {$\mathsf{Skye}$: An Expanding {PRF} based Fast {KDF} and its Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/781}, year = {2023}, url = {https://eprint.iacr.org/2023/781} }