Som lovet kommer her en beskrivelse af hvad jeg i øjeblikket arbejder med hos IBM. Håber dette får stillet nysgerrigheden hos et par stykker 🙂 Dette arbejde afsluttes den 7. november, hvorefter vi går i gang med noget andet. Som tidligere nævnt arbejder vi med batch verifikation af signaturer, men for at jeg kan fortælle mere om det, så kommer her lige lidt baggrundsinformation.
De fleste kender vel en digital signatur, der er en mulighed for at underskrive en digital besked. I har alle uden tvivl benyttet jer af digitale signaturer på et eller andet tidspunkt, men måske uden at vide det? Hver gang I køber ind på nettet, checker e-mail over sikre forbindelser, ordner banksagerne hjemme foran PC’en, etc. har der været en digital signatur involveret for at sikre at oplysningerne ikke bliver ændret undervejs, eller for at give mulighed for at se præcist hvem der lavede hvad, uden at vedkommende senere kan afvise at det var hende der gjorde det. Dette bruges fx hver gang I godkender en overførsel eller betaler en regning via jeres netbank.
Digitale signaturer fungerer ved at man har to stykker data, den offentlige og den private nøgle. Den offentlige er tilgængelig for alle, mens man holder den private for sig selv. Givet den private nøgle og en besked man gerne vil underskrive, kan man lave nogle beregninger og resultat af disse beregninger kaldes signaturen. Givet en besked, en signatur og den offentlige nøgle kan man checke om den givne signatur rent faktisk var lavet ud fra den tilhørende besked og private nøgle, eller med andre ord om den eneste person der ejer den private nøgle rent faktisk har underskrevet beskeden. Ændres der bare et enkelt tegn i beskeden eller signaturen, vil det ikke længere være en gyldig signatur på beskeden, så det er altså den digitale version af en underskrift på et stykke papir. Der findes mange forskellige metoder til at lave disse digitale signaturer, med forskellige egenskaber. Fx vil det jo være rart at det tager kort tid at checke om en signatur er korrekt og det er også godt hvis signaturen ikke fylder ret meget, da den jo evt. skal sendes rundt.
Og nu endnu mere baggrundsviden til dem der ikke er faldet i søvn. Forestil jer fx at alle biler der kører rundt på vejene er udstyret med sensorer der rapporterer data om trafikforhold, vejforhold, vejr, etc. til alle andre biler i nærheden. Disse biler vil så, afhængigt af hvilken type information der er tale om, videresende beskederne til andre biler der var uden for rækkevidde af den bil der oprindeligt sendte beskeden. Hvis beskederne markeres med koordinater, kan man opnå at data “lever” indenfor et bestemt geografisk område, fordi de hele tiden bliver sendt rundt mellem de biler der befinder sig i området. Det kunne fx være at en bil opdager at vejen er glat, og så sørger den for at alle biler i samme vognbane op til fx 500 meter før det glatte sted, får denne besked. På en travl motorvej kan dette betyde at en bil modtager flere beskeder per sekund. Lyder dette som science fiction? Det er det ikke… det er et EU projekt der om nogle år sagtens kan gå hen og blive til virkelighed på de europæiske veje!
Har disse to ting overhovedet noget med hinanden at gøre? Ja, det har de skam. For man har en interesse i at kun beskeder sendt fra sensorerne indbygget i bilerne bliver accepteret af de andre biler. Ellers kunne man jo forestille sig at folk bevidst saboterede tratikken ved at sende falske beskeder om kødannelse, glat føre, ulykker eller hvad der nu kunne skabe mest kaos. Dette kunne man fx sikre sig imod ved at hver bil har en offentlig og privat nøgle indbygget fra fabrikanten, og så skal alle beskederne have en digital signatur når de sendes. Modtageren kan så verificere denne signatur, og hvis den er ugyldig ignoreres beskeden. Problemet er så at med flere beskeder pr. sekund er det en stor belastning for den computer der sidder i bilerne at udføre alle de beregninger der kræves for at checke disse signaturer, og det er så her vi kommer ind i billedet med batch verifikation. Det går i alt sin enkelthed ud på at man tager en bunke beskeder med tilhørende signaturer, laver nogle beregninger på dem der resulterer i at man kan verificere alle signaturerne på en gang, hurtigere end hvis man verificerede hver enkelt signatur hver for sig. Det lyder jo simpelt nok… men det er det ikke.
Litteraturen er fuld af mislykkede forsøg på dette, og artikler hvor folk påstår at de laver batch verifikation, men hvor det faktisk ikke er sandt. Det de i stedet for opnår er at hvis deres beregninger siger “ja” så betyder det at alle beskederne var underskrevet med den rette private nøgle på et tidspunkt, men det betyder ikke at de enkelte signaturer ville verificere korrekt hver for sig. Tag fx dette tænkte eksempel: Man har to signaturer A og B, og den påståede batch verifikation går ud på lægge dem sammen og lave nogle beregninger. Det er klart at A+B=(A-2)+(B+2) så en algoritme der kun arbejder på summen kan ikke se forskel, men (A-2) er ikke en gyldig signatur på den givne besked. Dog kræver det at A er beregnet på et tidspunkt før man kan beregne (A-2) så det betyder stadigvæk at en eller anden har underskrevet beskeden på et tidspunkt, ellers ville A jo slet ikke eksistere! Betyder denne forskel noget? Ja, i nogle scenarier gør den. Fx i bilscenariet hvor en bil verificerer beskeder og sender dem videre til en anden bil. Vi vil jo ikke belaste netværket med ugyldige beskeder, så derfor laver den første bil batch verifikation, men hvis individuelle signaturer kan være ugyldige alligevel, så går det måske galt senere når disse beskeder sendes videre til en anden modtager.
De konktere bidrag fra vores arbejde er et overblik over emnet så folk kan se forskellen og alle de fejl der er blevet begået i tidens løb, formelle definitioner af batch verifikation og den svagere garanti kaldet screening samt den første algoritme til batch verifikation der er beviseligt sikker når vi har flere forskellige personer der underskriver beskederne (nuværende resultater kræver at den samme person underskriver alle beskederne, hvilket er helt urealistisk i vores bilscenarie). Desuden er metoden beviseligt sikker uden et cryptografisk trick kaldet “random oracles” som man i dag prøver at undgå. Forklaringen på dette er for lang til at den skal med her, men pointen er at metoder der bevises sikre i random oracle modellen, ikke nødvendigvis behøver at være sikre i den virkelige verden! Udover dette præsenterer vi batch verifikation i random oracle modellen der er særdeles effektiv hvis vi har en person der underskriver alle beskederne, og til sidst præsenterer vi et nyt system til digitale signaturer der har nogle begrænsninger, men har meget små signaturer og er hurtigt at lave batch verifikation af, selv for signaturer fra mange forskellige personer. Vi undersøger også muligheden for at lække noget information om den hemmelige nøgle. Så lidt at man ikke kan bruge det til at forfalske signaturer, men derimod kan lave batch verifikation endnu mere effektivt.
Når denne artikel er færdig går vi i gang med at se på det samme igen, bare for anonyme systemer. Folk er jo nok ikke interesserede i at deres bil har en unik nøgle, der sendes ud flere gange i sekundet, så det kan bruges til at spore den alle steder. Så det vi har brug for er systemer hvor en signatur blot kan verificeres som kommende fra en bil i systemet, men uden information om hvilken, og alligevel på en måde så biler med defekte sendere eller folk der bevidst benytter deres sensorer i bilen til at sende forkerte data, kan opdages og identificeres. Sådanne systemer findes, men kan vi lave batch verifikation af den slags anonyme signaturer? Lige nu er der ingen metoder til det, men så var det måske på tide at man fandt på nogen 🙂
Der mangler naturligvis et hav af detaljer i denne beskrivelse, men det er da lige en smagsprøve på hvad jeg kigger på for tiden. Ved ikke om det gjorde jer ret meget klogere 🙂
