Som lovet kommer her en beskrivelse af hvad jeg i \u00f8jeblikket arbejder med hos IBM. H\u00e5ber dette f\u00e5r stillet nysgerrigheden hos et par stykker \ud83d\ude42 Dette arbejde afsluttes den 7. november, hvorefter vi g\u00e5r i gang med noget andet. Som tidligere n\u00e6vnt arbejder vi med batch verifikation af signaturer, men for at jeg kan fort\u00e6lle mere om det, s\u00e5 kommer her lige lidt baggrundsinformation.<\/p>\n
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\u00e5 et eller andet tidspunkt, men m\u00e5ske uden at vide det? Hver gang I k\u00f8ber ind p\u00e5 nettet, checker e-mail over sikre forbindelser, ordner banksagerne hjemme foran PC’en, etc. har der v\u00e6ret en digital signatur involveret for at sikre at oplysningerne ikke bliver \u00e6ndret undervejs, eller for at give mulighed for at se pr\u00e6cist 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\u00f8rsel eller betaler en regning via jeres netbank.<\/p>\n
Digitale signaturer fungerer ved at man har to stykker data, den offentlige og den private n\u00f8gle. Den offentlige er tilg\u00e6ngelig for alle, mens man holder den private for sig selv. Givet den private n\u00f8gle 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\u00f8gle kan man checke om den givne signatur rent faktisk var lavet ud fra den tilh\u00f8rende besked og private n\u00f8gle, eller med andre ord om den eneste person der ejer den private n\u00f8gle rent faktisk har underskrevet beskeden. \u00c6ndres der bare et enkelt tegn i beskeden eller signaturen, vil det ikke l\u00e6ngere v\u00e6re en gyldig signatur p\u00e5 beskeden, s\u00e5 det er alts\u00e5 den digitale version af en underskrift p\u00e5 et stykke papir. Der findes mange forskellige metoder til at lave disse digitale signaturer, med forskellige egenskaber. Fx vil det jo v\u00e6re rart at det tager kort tid at checke om en signatur er korrekt og det er ogs\u00e5 godt hvis signaturen ikke fylder ret meget, da den jo evt. skal sendes rundt.<\/p>\n
Og nu endnu mere baggrundsviden til dem der ikke er faldet i s\u00f8vn. Forestil jer fx at alle biler der k\u00f8rer rundt p\u00e5 vejene er udstyret med sensorer der rapporterer data om trafikforhold, vejforhold, vejr, etc. til alle andre biler i n\u00e6rheden. Disse biler vil s\u00e5, afh\u00e6ngigt af hvilken type information der er tale om, videresende beskederne til andre biler der var uden for r\u00e6kkevidde af den bil der oprindeligt sendte beskeden. Hvis beskederne markeres med koordinater, kan man opn\u00e5 at data “lever” indenfor et bestemt geografisk omr\u00e5de, fordi de hele tiden bliver sendt rundt mellem de biler der befinder sig i omr\u00e5det. Det kunne fx v\u00e6re at en bil opdager at vejen er glat, og s\u00e5 s\u00f8rger den for at alle biler i samme vognbane op til fx 500 meter f\u00f8r det glatte sted, f\u00e5r denne besked. P\u00e5 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 \u00e5r sagtens kan g\u00e5 hen og blive til virkelighed p\u00e5 de europ\u00e6iske veje!<\/p>\n
Har disse to ting overhovedet noget med hinanden at g\u00f8re? 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\u00f8dannelse, glat f\u00f8re, 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\u00f8gle indbygget fra fabrikanten, og s\u00e5 skal alle beskederne have en digital signatur n\u00e5r de sendes. Modtageren kan s\u00e5 verificere denne signatur, og hvis den er ugyldig ignoreres beskeden. Problemet er s\u00e5 at med flere beskeder pr. sekund er det en stor belastning for den computer der sidder i bilerne at udf\u00f8re alle de beregninger der kr\u00e6ves for at checke disse signaturer, og det er s\u00e5 her vi kommer ind i billedet med batch verifikation. Det g\u00e5r i alt sin enkelthed ud p\u00e5 at man tager en bunke beskeder med tilh\u00f8rende signaturer, laver nogle beregninger p\u00e5 dem der resulterer i at man kan verificere alle signaturerne p\u00e5 en gang, hurtigere end hvis man verificerede hver enkelt signatur hver for sig. Det lyder jo simpelt nok… men det er det ikke.<\/p>\n
Litteraturen er fuld af mislykkede fors\u00f8g p\u00e5 dette, og artikler hvor folk p\u00e5st\u00e5r at de laver batch verifikation, men hvor det faktisk ikke er sandt. Det de i stedet for opn\u00e5r er at hvis deres beregninger siger “ja” s\u00e5 betyder det at alle beskederne var underskrevet med den rette private n\u00f8gle p\u00e5 et tidspunkt, men det betyder ikke at de enkelte signaturer ville verificere korrekt hver for sig. Tag fx dette t\u00e6nkte eksempel: Man har to signaturer A og B, og den p\u00e5st\u00e5ede batch verifikation g\u00e5r ud p\u00e5 l\u00e6gge dem sammen og lave nogle beregninger. Det er klart at A+B=(A-2)+(B+2) s\u00e5 en algoritme der kun arbejder p\u00e5 summen kan ikke se forskel, men (A-2) er ikke en gyldig signatur p\u00e5 den givne besked. Dog kr\u00e6ver det at A er beregnet p\u00e5 et tidspunkt f\u00f8r man kan beregne (A-2) s\u00e5 det betyder stadigv\u00e6k at en eller anden har underskrevet beskeden p\u00e5 et tidspunkt, ellers ville A jo slet ikke eksistere! Betyder denne forskel noget? Ja, i nogle scenarier g\u00f8r den. Fx i bilscenariet hvor en bil verificerer beskeder og sender dem videre til en anden bil. Vi vil jo ikke belaste netv\u00e6rket med ugyldige beskeder, s\u00e5 derfor laver den f\u00f8rste bil batch verifikation, men hvis individuelle signaturer kan v\u00e6re ugyldige alligevel, s\u00e5 g\u00e5r det m\u00e5ske galt senere n\u00e5r disse beskeder sendes videre til en anden modtager.<\/p>\n
De konktere bidrag fra vores arbejde er et overblik over emnet s\u00e5 folk kan se forskellen og alle de fejl der er blevet beg\u00e5et i tidens l\u00f8b, formelle definitioner af batch verifikation og den svagere garanti kaldet screening samt den f\u00f8rste algoritme til batch verifikation der er beviseligt sikker n\u00e5r vi har flere forskellige personer der underskriver beskederne (nuv\u00e6rende resultater kr\u00e6ver 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\u00f8ver at undg\u00e5. Forklaringen p\u00e5 dette er for lang til at den skal med her, men pointen er at metoder der bevises sikre i random oracle modellen, ikke n\u00f8dvendigvis beh\u00f8ver at v\u00e6re sikre i den virkelige verden! Udover dette pr\u00e6senterer vi batch verifikation i random oracle modellen der er s\u00e6rdeles effektiv hvis vi har en person der underskriver alle beskederne, og til sidst pr\u00e6senterer vi et nyt system til digitale signaturer der har nogle begr\u00e6nsninger, men har meget sm\u00e5 signaturer og er hurtigt at lave batch verifikation af, selv for signaturer fra mange forskellige personer. Vi unders\u00f8ger ogs\u00e5 muligheden for at l\u00e6kke noget information om den hemmelige n\u00f8gle. S\u00e5 lidt at man ikke kan bruge det til at forfalske signaturer, men derimod kan lave batch verifikation endnu mere effektivt.<\/p>\n
N\u00e5r denne artikel er f\u00e6rdig g\u00e5r vi i gang med at se p\u00e5 det samme igen, bare for anonyme systemer. Folk er jo nok ikke interesserede i at deres bil har en unik n\u00f8gle, der sendes ud flere gange i sekundet, s\u00e5 det kan bruges til at spore den alle steder. S\u00e5 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\u00e5 en m\u00e5de s\u00e5 biler med defekte sendere eller folk der bevidst benytter deres sensorer i bilen til at sende forkerte data, kan opdages og identificeres. S\u00e5danne systemer findes, men kan vi lave batch verifikation af den slags anonyme signaturer? Lige nu er der ingen metoder til det, men s\u00e5 var det m\u00e5ske p\u00e5 tide at man fandt p\u00e5 nogen \ud83d\ude42<\/p>\n
Der mangler naturligvis et hav af detaljer i denne beskrivelse, men det er da lige en smagspr\u00f8ve p\u00e5 hvad jeg kigger p\u00e5 for tiden. Ved ikke om det gjorde jer ret meget klogere \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
Som lovet kommer her en beskrivelse af hvad jeg i \u00f8jeblikket arbejder med hos IBM. H\u00e5ber dette f\u00e5r stillet nysgerrigheden hos et par stykker \ud83d\ude42 Dette arbejde afsluttes den 7. november, hvorefter vi g\u00e5r i gang med noget andet. Som tidligere n\u00e6vnt arbejder vi med batch verifikation af signaturer, men for at jeg kan fort\u00e6lle […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[3,10],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","hentry","category-personlig","category-rejse"],"_links":{"self":[{"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":0,"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/posts\/51\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/media?parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/categories?post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bytopia.dk\/blog\/wp-json\/wp\/v2\/tags?post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}