Immunizing hash-based signatures from backdoored hash functions

Abstract

Die Snowden Enthüllungen zeigten einen neuen potenziellen Angriffsvektor auf kryptographische Verfahren: Hintertüren in Design und Spezifikation.Das ist möglicherweise schon durchgeführt worden - es ist wahrscheinlich, dass der PRG DUAL_EC_DRBG mit einer bewussten Hintertür spezifiziert wurde (CNEGLRBMSF14, BerLanNie15, CMGFCG16).Wir müssen annehmen, dass dies nicht der einzige Fall bleiben wird, in dem eine maliziöse Partei einen kryptographischen Standard forciert.Auch wenn DUAL_EC_DRBG ein PRG ist, gibt es nichts das prinzipiell verhindert auch ähnliche Hintertüren in Hash-Funktionen und Signaturen einzubauen.Signaturen werden in Protokollen wie TLS (RFC 8446) verwendet, die ein Fundament für die Sicherheit des heutigen Internets bilden, sowie zur Verifikation von Software Updates vor der Installation.Hintertüren in Signatur-Standards könnten maliziösen Parteien erlauben, Datenverkehr zu überwachen und sogar zu modifizieren oder bösartige Software Updates ausliefern.Solche standardisierten Hintertüren sind daher vielversprechende Ziele für maliziöse Parteien.Diese Arbeit beschäftigt sich formal mit Techniken um Signaturverfahren gegen Hintertüren zu immunisieren.Dabei liegt der Fokus auf Hash-Basierten Signaturverfahren.Angefangen bei Wenige-Male Signaturen und aufbauend bis zu Viele-Male Signaturen für lange Nachrichten.Zwei Resultate dieser Arbeit sind essentiell für die Immunisierung von Hash-Basierten Signaturverfahren.Erstens scheint es unwahrscheinlich, erfolgreich Hintertüren für die Pseudozufälligkeit eines effizienten PRG zu konstruieren, die einem Angreifer erlauben, die Ausgabe des PRG von einem zufälligen Bitstring zu unterscheiden.Zweitens scheint es unwahrscheinlich, erfolgreich Hintertüren für effiziente Hash-Funktionen zu konstruieren, bei dennen die Hintertür nicht bei Verwendung auffällt.Eine Hintertür in diesem Fall würde einem Angreifer erlauben Kollisionen und Zweite Urbilder zu generieren.

The Snowden revelations raised awareness of a possible attack vector against cryptographic schemes: the embedding of a backdoor in design and specification.This may have already been done - it seems likely that the PRG DUAL_EC_DRBGwas designed and standardized with a deliberate backdoor (CNEGLRBMSF14, BerLanNie15, CMGFCG16).We need to assume that this will not remain the only instance of a malicious party pushing a backdoored cryptographic standard.While DUAL_EC_DRBG is a PRG, nothing prevents one from also embedding a backdoor in hash functions or signatures in a similar way.Signatures are used in protocols such as TLS (RFC 8446) underlying security of the internet of today or to verify software updates before installation.Including a backdoor in a signature standard may allow adversaries to intercept and modify traffic secured by TLS or attack targets via malicious software updates.Doing so thus provides a valuable objective and promising outlook for malicious parties.This thesis provides a formal treatment of techniques to immunize signatures from included backdoors.We focus on hash-based signatures schemes starting from few-time signature and building up to many-time signatures for long messages.Two results we provide are essential for the immunization of hash-based signatures.First, it is implausible to include a backdoor in the pseudorandomness notion of an efficient PRG, that would allow an adversary with the backdoor key to distinguish the PRG from random.Second, it is implausible to include a backdoor in an efficient hash functions without revealing the backdoor by using it.Such a backdoor would allow an adversary with a backdoor key to produce collisions or second-preimages for the hash function.