PQC in DNSSEC: Falcon met of zonder padding?

Falcon-handtekeningformaten

In DNSSEC gebruiken we cryptografische handtekeningen om de integriteit en authenticiteit van records te verifiëren. Het gevaar bestaat dat kwantumcomputers op een gegeven moment in staat zullen zijn om bestaande cryptografie te kraken. Daarom ligt onze focus op post-kwantumhandtekeningalgoritmen, zoals Falcon. We hebben gekozen voor Falcon-512 in plaats van Falcon-1024, omdat deze variant voldoende beveiliging biedt voor gebruik in DNSSEC. Falcon-512 voldoet aan NIST-beveiligingsniveau 1, wat betekent dat de beveiliging van het algoritme te vergelijken is met die van AES-128 (128 bits).

Falcon-512 ziet er veelbelovend uit voor gebruik in DNSSEC, aangezien de handtekeningen redelijk compact zijn en de ondertekenings- en validatieprestaties vergelijkbaar zijn met die van de momenteel gangbare DNSSEC-algoritmen. Aangezien we al hebben vastgesteld dat Falcon-512 wat betreft ondertekening en validatie niet onderdoet voor veelgebruikte niet-PQC-algoritmen, zijn we nu vooral geïnteresseerd in het effect dat handtekeningformaten hebben op de grootte van DNS-responses.

De officiële implementatie van Falcon bevat 3 handtekeningformaten:

• Gecomprimeerde handtekeningen, het standaardformaat, hebben de kortste gemiddelde lengte. Deze lengte is echter variabel. De broncode van Falcon vermeldt een test met 10.000 handtekeningen met een gemiddelde lengte van 651 bytes (en een standaardafwijking van 2,55), maar daar zat ook een maximum van 752 bytes bij.

• Handtekeningen met padding hebben een vaste lengte van 666 bytes. Het enige verschil met het gecomprimeerde formaat is dat de handtekeningen worden opgevuld tot 666 bytes. Als een gegenereerde handtekening groter is dan 666 bytes, moet er een nieuwe handtekening worden gegenereerd.

• CT-handtekeningen zijn langer (809 bytes) en hebben een formaat met vaste lengte. Volgens de broncode is het CT-handtekeningformaat bedoeld voor 'ongebruikelijke situaties waarin de ondertekende gegevens geheim zijn maar een lage entropie hebben, en de publieke sleutel niet echt publiek is'. Aangezien deze situatie niet van toepassing is op DNSSEC, laten we het CT-formaat buiten beschouwing.

Voor dit onderzoek bekeken we het verschil tussen gecomprimeerde handtekeningen en handtekeningen met padding. We wilden antwoord op de vraag: 'Welk Falcon-handtekeningformaat is het meest geschikt voor DNSSEC?'

Meting van de verschillen

Om het effect van de verschillende handtekeningformaten van Falcon-512 te beoordelen, maakten we 2 versies van de .nl-zonefile: 1 ondertekend met Falcon-512 in de modus met padding en 1 ondertekend met Falcon-512 in gecomprimeerde modus (zonder padding).

Eerst verzamelden we alle DNS-query's die gedurende een periode van 24 uur naar 1 van de autoritatieve nameservers van de .nl-zone werden gestuurd. Daarna maakten we 2 datasets op basis van de responsecodes die deze query's van onze nameservers ontvingen: NOERROR (RCODE=0) en NXDOMAIN (RCODE=3). NOERROR geeft aan dat de nameserver de query succesvol heeft beantwoord, terwijl NXDOMAIN betekent dat de nameserver de opgevraagde naam niet kent. NXDOMAIN-query's leiden tot een response van de nameserver met 1 of meer ondertekende NSEC3-records, die cryptografisch verifieerbaar bewijs leveren dat de domeinnaam niet bestaat. De NOERROR-dataset bevat 59 miljoen DNS-query's en de NXDOMAIN-dataset bevat 113 miljoen DNS-query's.

Vervolgens stuurden we al het verkeer uit beide datasets naar 2 nameservers die speciaal voor dit onderzoek waren geconfigureerd: 1 met de .nl-zonefile die was ondertekend met Falcon-512 in de modus met padding en 1 met de .nl-zonefile die was ondertekend met Falcon-512 in de gecomprimeerde modus. Daarna stuurden we de DNS-query's uit de 2 datasets NOERROR en NXDOMAIN opnieuw naar beide nameservers en bepaalden en analyseerden we de grootteverdeling van de resulterende antwoorden.

We zijn vooral geïnteresseerd in 2 drempelwaarden: 1.500 bytes (de standaard-MTU voor Ethernet) en 1.232 bytes (de aanbevolen maximale DNS-berichtgrootte).

Met padding of gecomprimeerd?

De gecomprimeerde Falcon-512-handtekeningen voor de .nl-zonefile laten een klokvormige verdeling met een mediane grootte van 655 bytes zien, zoals weergegeven in Figuur 1. De handtekeningen zijn over het algemeen kleiner dan de vaste 666 bytes van Falcon-512 met padding. Hoewel handtekeningen zonder padding incidenteel groter kunnen zijn dan 666 bytes, komt dit zelden voor; in een dataset van 9.912.711 handtekeningen gebeurde dit maar 1 keer.

Figuur 1: Grootteverdeling van handtekeningen voor de met Falcon-512 ondertekende .nl-zonefile waarbij gebruik werd gemaakt van gecomprimeerde handtekeningen.

Vervolgens keken we naar de impact van de handtekeningformaten op DNS-responses in de praktijk. De resultaten voor de NOERROR-dataset worden weergegeven in Figuur 2. We zien dat vrijwel alle responses die de gevraagde data bevatten binnen de limiet van 1.232 bytes passen. Het rechterdeel van figuur 2 toont een reeks responses tussen 1.532 en 1.622 bytes, die allemaal 1 NSEC3-record bevatten. Elke response hoort bij een domeinnaam die wel bestaat (vandaar het NOERROR-antwoord), maar waarbij het gevraagde recordtype ontbreekt. Daarom werd een extra NSEC3-record meegestuurd als cryptografisch bewijs van de afwezigheid van dit recordtype. De verzoeken betroffen vrijwel uitsluitend niet-bestaande DS-records.

Figuur 2: Histogram van het aantal responses per grootte gedurende 1 dag (op een logaritmische schaal) voor Falcon-512-DNSSEC-responses met een NOERROR-antwoord. De verticale lijn geeft de aanbevolen maximale DNS-pakketgrootte van 1.232 bytes aan.

We voerden ook een analyse uit van de NXDOMAIN-dataset, waarvan de resultaten te zien zijn in figuur 3. Alle NXDOMAIN-responses zijn groter dan 1.232 bytes en kunnen daarom niet worden verstuurd in een enkel UDP-DNS-responsepakket dat binnen de standaard-MTU van 1500 bytes past. In figuur 3 kunnen we opnieuw 2 groepen onderscheiden. Aan de linkerkant zien we query's van rond de 2.300 bytes, die elk 2 NSEC3-records bevatten. De groep aan de rechterkant bestaat uit responses in het bereik van 3.000-3.200 bytes, die elk 3 NSEC3-records bevatten.

Figuur 3: Histogram van het aantal responses per grootte gedurende 1 dag (op een logaritmische schaal) voor Falcon-512-DNSSEC-responses met een NXDOMAIN-antwoord.

Conclusies

Onze bevindingen laten zien dat het verschil in DNS-berichtgrootte tussen handtekeningen met padding en gecomprimeerde handtekeningen minimaal is. Hoewel kleinere handtekeningen in theorie aantrekkelijk zijn, levert het gebruik van het gecomprimeerde handtekeningformaat in de praktijk geen concrete voordelen op. Zoals onze resultaten aantonen, zorgen gecomprimeerde handtekeningen niet voor een significante afname in berichtgrootte en maken ze het ook niet mogelijk om meer DNSSEC-antwoorden binnen de MTU-limieten te laten passen.

Deze resultaten bieden waardevolle inzichten voor de lopende discussie over de standaardisatie van Falcon-handtekeningen in DNSSEC. Onze conclusie is dat het standaardiseren van een formaat met padding en een vaste grootte waarschijnlijk de voorkeur verdient vanwege de voorspelbaarheid ervan en het potentieel om implementatiefouten te voorkomen.