Vi har tidligere sett på meldingsautentisering, men her sliter vi litt med utfordringer relatert til mangel på tillit. Dagens tekst er hentet fra kapittel 13 i Cryptography and Network Security, og handler om digitale signaturer.

Digitale signaturer gjør oss i stand til verifisere forfatter, dato og tidspunkt for når meldingen ble signert. På samme måte som en MAC kan en digital signatur autentisere meldingsinnhold, men i tillegg kan en digital signatur verifiseres av en tredjepart for å avgjøre tvister.

Egenskaper til en digital signatur

En digital signatur må verifisere forfatteren, datoen og tiden for signeringen, må autentisere innholdet på signeringstidspunktet, og må kunne verifiseres av en tredjepart.

Angrep

Vi kan tenke oss minst fem forskjellige typer angrep mot et digitalt signatursystem:

1. Kun-nøkkel-angrep: Charlie vet kun Alices offentlige nøkkel
2. Kjent-melding-angrep: Charlie får tilgang til en samling med meldinger og deres signaturer
3. Generisk valgt-melding-angrep: Charlie velger en liste med meldinger, og sender disse til Alice for å få dem signert, og får gyldige signaturer tilbake
4. Rettet valgt-melding-angrep: Charlie velger listen av meldinger som skal signeres etter at han kjenner den offentlige nøkkelen til Alice, men før han har sett noen signaturer
5. Adaptivt valgt-melding-angrep: Charlie er i stand til å be Alice signere meldinger som avhenger av melding-signatur-par som han har fått tidligere.

Forfalskninger

Hvis Charlie kan forfalske en signatur for minst en melding,  men ikke har kontroll over hvilken melding det er, kaller vi det for eksistensielle forfalskning. Når Charlie kan forfalske en signatur for en bestemt melding han velger, er det en selektiv forfalskning. Dersom Charlie finner er effektiv signeringsalgoritme som gir ham en ekvivalent måte å konstruere signaturer på vilkårlige meldinger, er det en universell forfalskning. Hvis Charlie er i stand til å bestemme Alices private nøkkel, kaller vi det et fullstendig brudd (Total break)

Krav

Kravene til en digital signatur har mange likhetstrekk med kravene til en MAC. Signaturen må vær et bitmønster som avhenger av meldingen som skal sendes, og må bruke informasjon som er unik for avsenderes, både for å forhindre forfalskning og fornektelse. Det må være relativt enkelt både å lage og å gjenkjenne/verifisere signaturen. Det må være beregningsmessig ugjennomførbart (“umulig”) å forfalske en digital signatur, enten ved å konstruere en ny melding for en eksisterende signatur, eller å lage en falsk signatur for en gitt melding. Til slutt så må det være praktisk å lagre en kopi av den digitale signaturen for fremtidig verifisering.

Direkte digital signatur

En direkte digital signatur involverer kun de kommuniserende partene, og forutsetter at mottakeren kjenner den offentlige nøkkelen til avsenderen. Konfidensialitet kan oppnås ved å kryptere hele meldingen inkludert signaturen med en delt hemmelig nøkkel. Det er viktig å utføre signaturfunksjonen først og deretter den ytre konfidensialitetsfunksjonen; ved en tvist må en uavhengig tredjepart kunne vurdere meldingen og dens signatur.

Gyldigheten av dette systemet avhenger av sikkerheten til avsenderens private nøkkel. Hvis en avsender ønsker å nekte for å ha sendt en gitt melding, kan hun påstå at den private nøkkelen var mistet eller stjålet, og at noen har forfalsket hennes signatur. En måte å motvirke (eller vanskeliggjøre) en slik taktikk er å kreve at hver signert melding må inneholde et tidsstempel, og så kreve rask rapportering av kompromitterte nøkler til en sentral instans.

ElGamal Digital Signatur

ElGamal-signaturen fungerer på same måten som RSA ved at den bruker den private nøkkelen til kryptering, og den offentlige til dekryptering. Konfigurasjonen er akkurat som for ved ElGamal kryptering; de globale elementene er et primtall q, og tallet a som er en primitiv rot av q. Hver bruker genererer sitt nøkkelpar ved å velge den hemmelige nøkkelen (et tall): 1 < x_A < q-1, og deretter beregne den offentlige nøkkelen: y_A = a^xA mod q.

Alice vil signere en melding M til Bob ved å beregne hash m = H(M), 0 <= m <= (q-1), og velge tilfeldig heltall K hvor 1 <= K <= (q-1) og gcd(K,q-1)=1. Alice beregner så en midlertidig nøkkel:  S₁ = a^K mod q, og beregner K^-1, inversen av K mod (q-1), og beregner så verdien  S₂ = K^-1(m-x_AS₁) mod (q-1). Signaturen er da (S₁,S₂).

Enhver bruker B kan verifisere signature ved å beregne V₁ = a^m mod q og V₂ = y_A^S1 S₁^S2 mod q. Signaturen er gyldig hvis V₁ = V₂.

Bevis

Signaturen er gyldig dersom V₁ = V₂. Vi kan demonstrere at dette er slik; hvis vi antar at likheten holder har vi:

a^m mod q = y_A^S1 S₁^S2 mod q                                          (V₁ = V₂)

a^m mod q = (a^XA)^S1 (a^K)^S2 mod q                                  (setter inn for Y_A og S₁)

a^m-XaS1 mod q = a^KS2 mod q                                           (deler på a^XaS1 på begge sider)

m-X_AS₁ ≡ KS₂ mod (q-1)                                                (egenskaper til primitiv rot)

m-X_AS₁ ≡ K∙K^-1(m – X_AS₁) mod (q-1)                           (substituerer for S₂)

m-X_AS₁ ≡ m – X_AS₁ mod (q-1)                                      (K∙K^-1 er lik 1)

ElGamal eksempel

Vi bruker den endelige kroppen GF(19); q=19 og a=10. Alice beregner sitt nøkkelpar ved å velge x_A=16 & beregner y_A=10¹⁶ mod 19 = 4. Alice signerer meldingen med hash m=14 som (3,4) ved å velge tilfeldig K=5 som har gcd(18,5)=1, beregne S₁ = 10⁵ mod 19 = 3, og finne K^-1 mod (q-1) = 5^-1 mod 18 = 11, og til slutt beregne S₂ = 11(14-16∙3) mod 18 = 4.

Enhver bruker B kan verifisere signature ved å beregne V₁ = 10¹⁴ mod 19 = 16 og V₂ = 4³∙3⁴ = 5184 = 16 mod 19. Ettersom 16 = 16, er signaturen gyldig.

Schnorr Digital Signatur

Schnorr-signaturen er på same måte som ElGamal basert på diskrete logaritmer, men minimaliserer den meldings-avhengige biten av beregninger som kreves for å generere en signatur, multiplisering av et heltall på 2n bit med et heltall på n bit. Hoveddelen av arbeidet kan altså gjøres når prosessoren ellers har ledig tid. Schnorr bruker en primtallsmodulus p, hvor p – 1 har en primtallsfaktor q av passende størrelse. Typisk vil p være et 1024-bit tall, og q er et160-bit tall.

Oppsett

Velg to passende primtall p , q, og velg a slik at a^q = 1 mod p. (a,p,q) er globale parametre for alle. Hver bruker genererer et nøkkelpar ved å velge en hemmelig nøkkel (et tall) s: 0 < s < q, og beregne den offentlige nøkkelen: v = a^-s mod q.

Signatur

Brukeren signerer meldingen ved å velge en tilfeldig r hvor 0<r<q og beregne x = a^r mod p. Hekt x bakpå meldingen, og beregn hashverdien av resultatet: e = H(M || x). Beregn deretter  y = (r + se) mod q; signaturen er paret (e, y).

Enhver annen bruker kan verifisere signaturen som følger: Beregn  x’ = a^yv^e mod p   og verifiser at e = H(M || x’) .

For å se at verifikasjonen fungerer, observer at

x’ ≡ a^yv^e  ≡ a^y(a^-s)^e  ≡ a^y(a^-s)^e  ≡ a^y-se  ≡ a^(r+se)-se  ≡ a^r  ≡ x (mod p)

Ergo er H(M||x’) = H(M||x).

DSS

Digital Signature Standard (DSS) er et signatursystem godkjent av amerikanske styresmakter. Det ble utviklet av NIST og NAS på det tidlige 1990-tallet, og ble publisert som FIPS-186 i 1991. DSS ble revidert i 1993, 1996 og 2000, og bruker (ikke overraskende) hashalgoritmen SHA.

DSS er standarden, mens DSA er algoritmen som implementer standarden – men mistenker at de fleste bare sier DSS. FIPS 186-2 (2000) inkluderer alternative RSA & elliptisk-kurve signaturvarianter. I motsetning til RSA, er DSA kun en digital signatur, og kan ikke brukes til å kryptere data, men er like fullt en offentlig-nøkkel-teknikk. Vi kan anta at dette var en spesifikt krav fra NSA, på et tidspunkt hvor det ikke var lov å eksportere “krypto” fra USA.

NIST Digital Signature Algorithm (DSA)

DSA produserer en 320 bit signature med 512-1024 bit sikkerhet. Den er mindre og raskere enn RSA, og ettersom den er en variant av ElGamal og Schnorr-algoritmene, avhenger sikkerheten av vanskeligheten til å beregne diskrete logaritmer.

DSA nøkkelgenerering

Vi må først etablere de globale delte offentlig-nøkkel-verdiene (p,q,g): Velg et 160-bit primtall q. Velg et stort primtall p slik at 2^L-1 < p < 2^L , hvor L= 512 til 1024 bit og et multippel av 64, og q er en 160 bit primtallsdivisor av (p-1). Velg et heltall h slik at 1<h<p-1 og h^(p-1)/q mod p > 1, og beregn g = h^(p-1)/q .

Brukere velger så sin private nøkkel x<q og beregner den offentlige nøkkelen : y = g^x mod p.

DSA Signering

For å signere en melding M vil avsenderen først generere en tilfeldig signaturnøkkel k, k<q . Denne k må aldri brukes igjen, og må destrueres etter bruk. Deretter må signaturaret beregnes: r = (g^k mod p) mod q, s = [k^-1(H(M)+ xr)] mod q. Signaturen er (r,s), som sendes med meldingen M.

DSA signaturverifikasjon

Mottakeren har mottatt M & signaturen (r,s). For å verifisere en signatur, vil mottakeren beregne w = s^-1 mod q, u1= [H(M)∙w ]mod q, u2= (r∙w)mod q og v = [(g^u1 y^u2)mod p ]mod q. Hvis v=r så er signaturen verifisert.

Elliptic Curve Digital Signature Algorithm (ECDSA)

Det er fire elementer involvert i ECDSA: Alle som deltar i signaturordningen bruker de samme globale domeneparametrene, som definerer en elliptisk kurve og et utgangspunkt på kurven. Den som skal signere må først generere et nøkkelpar. Deretter genereres en hash for meldingen som skal signeres, og signaturen (r,s) beregnes med hashverdien, domeneparametrene og den private nøkkelen. I tillegg velges en tilfeldig verdi k som gjør at hvis samme melding signeres flere ganger, vil det genereres forskjellige signaturer hver gang. Mottakeren trenger ikke vite k.

For å verifisere signaturen, bruker man avsenderens offentlige nøkkel, domeneparametrene og heltallet s; resultatet er en verdi V som sammenlignes med r, dersom den er lik er signaturen verifisert.

RSA-PSS

Bellare and Rogaway lanserte RSA Probabilistic Signature Scheme, som ble inkludert i 2009-versjonen av FIPS 186. Dette er signaturversjonen som RSA Laboratories anbefaler som den sikreste RSA-signaturen. For alle tidligere varianter enn PSS har det ikke vært mulig å bevise matematisk at signaturen er like sikker som det underliggende RSA krypterings-/dekrypteringsprimitivet. I motsetning til andre RSA-baserte systemer, introduserer denne varianten en randomiseringsprosess som gjør det mulig å vise at sikkerheten er tett koblet til sikkerheten av RSA. Målet er å gjøre det vanskeligere for en angriper å finne en annen melding som gis samme signatur, eller finne to meldinger som har samme signatur.

Mask Generation Function (MGF)

MGF er typisk basert på en sikker kryptografisk hashfunksjon som SHA-1. Hensikten er å være en kryptografisk sikker måte å generere en hash av variabel lengde basert på en underliggende kryptografisk hashfunksjon som genererer en hash av bestemt lengde.

RSA-PSS i praksis

Meldingen som skal signeres hashes først en gang, og resultatet (mHash) kombineres med en fast padding og et tilfeldig salt: (padding1 || mHash || salt). Dette hashes så på nytt, og resultatet H mates to steder: Til MGF og til den endelige signaturen. Resultatet fra MGF XORes med DB, som er konstruert som følger: (padding2 || salt), dette resuiltatet kalles maskedDB. Vi konstruerer til slutt verdien som skal signeres som følger: EM = (maskedDB||H||0xBC). På samme måte som ECDSA medfører bruken av salt at hvis samme melding signeres flere ganger, vil den få forskjellig signatur hver gang.

Avsenderen har privat nøkkel (d,n) og offentlig nøkkel (e,n). Oktettstrengen (en bitstreng som består av et helt antall byte) EM betraktes som et ikke-negativt binært heltall m uten fortegn. Signaturen dannes ved å beregne s = m^d mod n. Vi lar k være lengden i oktetter av RSA-modulusen n (hvis vi har en 2048-bit RSA-nøkkel, så er k = 2048/b = 256) Signaturverdien s konverteres så til en oktettstreng S med lengde k oktetter.

Når signaturen skal verifiseres, behandles signaturen S som et ikke-negativt binært heltall uten fortegn. Vi gjenvinner m ved å dekryptere s som følger: m = s^e mod n. Vi konverterer til slutt m til EM ved å gjøre den om til en oktettstreng. Når man har EM, kan man ekstrahere H og kjøre denne gjennom MGF for å få tilbake dbMask. Denne XORes med maskedDB for å få tilbake DB, og siste del av DB er saltet som vi trenger for å beregne M’: M’ = (padding1|| H(M)||salt)

Vi beregner så H’: H’ = H(M’). Dersom H’ = H (som vi har fra EM), er signaturen verifisert.

 

Photo by energepic.com from Pexels