Paper 2023/781

$\mathsf{Skye}$: An Expanding PRF based Fast KDF and its Applications

Amit Singh Bhati, KU Leuven
Antonin Dufka, Masaryk University
Elena Andreeva, TU Wien
Arnab Roy, University of Innsbruck
Bart Preneel, KU Leuven
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.