Skye: An Expanding PRF based Fast KDF and its Applications

D 2024

Skye: An Expanding PRF based Fast KDF and its Applications

BHATI, Amit Singh, Antonín DUFKA, Elena ANDREEVA, Arnab ROY, Bart PRENEEL et. al.

Základní údaje

Originální název

Skye: An Expanding PRF based Fast KDF and its Applications

Autoři

BHATI, Amit Singh (garant), Antonín DUFKA (203 Česká republika, domácí), Elena ANDREEVA, Arnab ROY a Bart PRENEEL

Vydání

New York, NY, USA, Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS '24), od s. 1082-1098, 17 s. 2024

Nakladatel

Association for Computing Machinery

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Organizační jednotka

Fakulta informatiky

ISBN

979-8-4007-0482-6

DOI

http://dx.doi.org/10.1145/3634737.3637673

Klíčová slova anglicky

KDF; Deterministic Extraction; Extract-then-Expand; HKDF; X3DH; Signal; Expanding PRF; PRF-PRNG; Randomness Amplification

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 15. 10. 2024 10:14, RNDr. Antonín Dufka

Anotace

V originále

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.

Návaznosti

MUNI/A/1586/2023, interní kód MU

Název: Aplikovaný výzkum na FI: Forenzní aspekty kritických infrastruktur, aplikovaná kryptografie, kyberbezpečnostní cvičení, algoritmy plánování v logistice a pro zpracování dat z fyzikálních sensorů

Investor: Masarykova univerzita, Aplikovaný výzkum na FI: Forenzní aspekty kritických infrastruktur, aplikovaná kryptografie, kyberbezpečnostní cvičení, algoritmy plánování v logistice a pro zpracování dat z fyzikálních sensorů

101087529, interní kód MU

Název: Cyber-security Excellence Hub in Estonia and South Moravia (CHESS)

Investor: Evropská unie, Cyber-security Excellence Hub in Estonia and South Moravia (CHESS), Rozšiřování účasti a posílení ERA

Citovat

BHATI, Amit Singh, Antonín DUFKA, Elena ANDREEVA, Arnab ROY a Bart PRENEEL. Skye: An Expanding PRF based Fast KDF and its Applications. Online. In Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS '24). New York, NY, USA: Association for Computing Machinery, 2024, s. 1082-1098. ISBN 979-8-4007-0482-6. Dostupné z: https://dx.doi.org/10.1145/3634737.3637673.

@inproceedings{2422038,
   author = {Bhati, Amit Singh and Dufka, Antonín and Andreeva, Elena and Roy, Arnab and Preneel, Bart},
   address = {New York, NY, USA},
   booktitle = {Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS '24)},
   doi = {http://dx.doi.org/10.1145/3634737.3637673},
   keywords = {KDF; Deterministic Extraction; Extract-then-Expand; HKDF; X3DH; Signal; Expanding PRF; PRF-PRNG; Randomness Amplification},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {New York, NY, USA},
   isbn = {979-8-4007-0482-6},
   pages = {1082-1098},
   publisher = {Association for Computing Machinery},
   title = {Skye: An Expanding PRF based Fast KDF and its Applications},
   year = {2024}
}

TY  - JOUR
ID  - 2422038
AU  - Bhati, Amit Singh - Dufka, Antonín - Andreeva, Elena - Roy, Arnab - Preneel, Bart
PY  - 2024
TI  - Skye: An Expanding PRF based Fast KDF and its Applications
PB  - Association for Computing Machinery
CY  - New York, NY, USA
SN  - 9798400704826
KW  - KDF
KW  - Deterministic Extraction
KW  - Extract-then-Expand
KW  - HKDF
KW  - X3DH
KW  - Signal
KW  - Expanding PRF
KW  - PRF-PRNG
KW  - Randomness Amplification
N2  - 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.
ER  -

BHATI, Amit Singh, Antonín DUFKA, Elena ANDREEVA, Arnab ROY a Bart PRENEEL. Skye: An Expanding PRF based Fast KDF and its Applications. Online. In \textit{Proceedings of the 19th ACM Asia Conference on Computer and Communications Security (ASIA CCS '24)}. New York, NY, USA: Association for Computing Machinery, 2024, s.~1082-1098. ISBN~979-8-4007-0482-6. Dostupné z: https://dx.doi.org/10.1145/3634737.3637673.

Podrobný výpis o publikaci