Skye: An Expanding PRF based Fast KDF and its Applications

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00136733" target="_blank" >RIV/00216224:14330/24:00136733 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1145/3634737.3637673" target="_blank" >http://dx.doi.org/10.1145/3634737.3637673</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3634737.3637673" target="_blank" >10.1145/3634737.3637673</a>

Result language

angličtina

Original language name

Skye: An Expanding PRF based Fast KDF and its Applications

Original language description

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 Skye. Skye follows the extract-then-expand paradigm and consists of two algorithms: efficient deterministic randomness extractor and expander functions. Instantiating our extractor for dedicated source-specific (e.g. DH sources) inputs leads to a significant efficiency gain over HKDF while maintaining its security level. We provide concrete security analysis of Skye and both its underlying algorithms in the standard model.We provide a software performance comparison of Skye with the AES-based expanding PRF ButterKnife and HKDF with SHA-256 (as used in practice). Our results show that in isolation Skye performs from 4x to 47x faster than HKDF, depending on the availability of AES or SHA instruction support. We further demonstrate that with such a performance gain, when 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, Skye still contributes to 12-36% relative speedup when just 10 messages are sent and received at once.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2024

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS '24)

ISBN

9798400704826

ISSN

—

e-ISSN

—

Number of pages

17

Pages from-to

1092-1108

Publisher name

Association for Computing Machinery

Place of publication

New York, NY, USA

Event location

Singapore

Event date

Jan 1, 2024

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

001283918100075