Tweede Deeltoets Security 3 juli 2015, 8.30–10.30, Educatorium-Γ. Motiveer je antwoorden kort! Zet je mobiel uit. Stel geen vragen over deze toets; als je een vraag niet duidelijk vindt, schrijf dan op hoe je de vraag interpreteert en beantwoord de vraag zoals je hem begrijpt. Cijfer: Vragen 2 en 4 zijn 3pt, de andere elk 2pt. Te halen 14, cijfer is som plus 1 gedeeld door 1,3. Maak vraag 1 en 2 op pagina 1, 3 en 4 op pagina 2 en 5 en 6 op pagina 3. 1. Euclides: Bereken met het algoritme van Euclides de waarde van d = ggd(1230, 504). Laat alle tussenresultaten zien. Bereken x en y waarvoor geldt dat d = 1230x + 504y. Oplossing: De achtereenvolgende resten bij deling zijn 222, 60, 42, 18, 6 en 0. Resultaat 6 is 1230 · 25 + 504 · (−61). Beoordeling: Te halen 2pt, 1 voor de ggd en tussenresultaten en 1 voor de x en y. X = Geen x en y berekend.
2. Code Signing: Martin wil een malafide, creditcardstelende app MM in de iPad Appstore plaatsen. Helaas voor Martin worden alle apps eerst door Apple bekeken, en alleen apps die geen creditcards stelen worden ondertekend (met een Hash plus RSA mechanisme). De controle op de inhoud van de apps is vrij goed, en de RSA handtekening van Apple kan Martin niet namaken. Martin probeert een goedgekeurde, bonafide app BB te vervangen door MM, maar zo dat de signature onder BB nu geldig is voor MM. (a) Eerst probeert Martin, zelf een goeie app BB te maken naast zijn eigen MM. Welke eigenschap van de gebruikte hashfunctie zal moeten voorkomen dat Martin slaagt? Leg uit. (b) Martin probeert, een reeds bestaande veelgebruikte app BB te vervangen door MM. Welke eigenschap van de gebruikte hashfunctie zal moeten voorkomen dat Martin slaagt? Leg uit. (c) Schat hoeveel werk de aanvallen in (a) en (b) zijn, als Apple een hashwaarde van 192 bits gebruikt. Oplossing: (a) Elke bestaande handtekening S is maar voor een enkele hash geldig, namelijk H = S e . Martin kan dus alleen slagen als BB en MM dezelfde hashwaarde hebben. In zijn eerste poging heeft Martin controle over BB en hij probeert twee strings te produceren (BB en MM) met dezelfde hash. Dit is onmogelijk wegens de sterke botsingsvrijheid. (b) In de tweede poging beschouwt Martin de BB als gegeven en probeert bij die BB een string MM te vinden met dezelfde hash. Dit is onmogelijk wegens de zwakke botsingsvrijheid. (c) Martin kan een soort van BruteForcen door zijn code (BB en/of MM) van commentaar met lange random strings te voorzien. Als hij BB als gegeven beschouwt, moet hij naar verwachting ongeveer 2192 waarden van x proberen om te bereiken dat H(M M, x) = H(BB). Als hij met MM en BB mag vari¨eren, heeft hij aan ongeveer 296 waarden van x en evenzoveel van y genoeg om een botsing te vinden tussen H(mm, x) en H(bb, y). Het is dus makkelijker voor martin om zijn eigen bonafide app te maken! Beoordeling: Totaal 3, 1 voor elke deelvraag. A = Alleen de complexiteit van (b) is te weinig voor punten bij (c), want dit is wat te vanzelfsprekend. D = Met het maken van twee apps hebben die nog lang niet Dezelfde hash, M = Je moet bij (c) wel inzien dat de eerste aanval Makkelijker is. T = Onterechte deling door Twee; een aanval op zwakke botsingsvrijheid kost verwacht 2k hashes, en niet 2k /2. W = De One Way eigenschap is hier (iha bij Signing) nauwelijks relevant, de apps staan immers open en bloot in de Appstore.
3. RSA Encryptie versus Decryptie: Kees gaat RSA gebruiken met een sleutellengte van 3072 bits. Om de encryptietijd laag te houden, besluit hij de waarde e = 17 te nemen. Geef een schatting van de verhouding tussen encryptie- en decryptietijd. Oplossing: Met e = 17 kost de encryptie slechts 5 vermenigvuldigingen. Voor decryptie met exponent d van 3072 bits zijn ongeveer anderhalf maal de lengte, ofwel 4608 vermenigvuldigingen nodig. Dat is ongeveer 922 keer zoveel. Je kunt decryptie viermaal versnellen met CRT, dan kost het nog “maar” ongever 230x zoveel. Beoordeling: Te halen 2pt voor goedgemotiveerde uitkomst 230. A = Weet Aantal vermenigvuldigingen voor een macht niet. De eerste 1 in de exponent kost je niets, daarna elke 0 een vermenigvuldiging en elke 1 twee. C = Zonder CRT kom je slechts op 922, min 1/2. H = Door de lage e krijg je een hoge d; onjuist, de hoogte van de een zegt niet zoveel over de ander! De d vind je door inverteren en kun je ongeveer zien als een “random” getal tussen 0 en φ(m). I = Met de CRT gaat het viermaal zo snel. Maar niet met 1152 In plaats van 4608 vermenigvuldigingen, wel met evenveel vermenigvuldigingen op halflange getallen. K = Komt zover als O(k) keer sneller, 1pt.
4. Wortel Funding: Instant Root Incorporated (Inst Inc) ontwikkelt een app voor modulair worteltrekken. Na invoer van een modulus m (max. 3072bits) en een getal b < m, produceert de InstInc app een getal a (als dat bestaat) dat voldoet aan a2 = b (mod m). De nodige 500.000 euro wil InstInc met crowd funding bij elkaar brengen. (a) Laat zien hoe je door deze app slim te gebruiken, de factoren van m kunt vinden. (b) Denk je dat Inst Inc de investering kan terugverdienen? (c) Bij nadere lezing van het persbericht zie je, dat de nieuwe app alleen zal werken als m een priemgetal is. Denk je nu dat Inst Inc de investering kan terugverdienen? Oplossing: (a) Als m priem is, is m zelf de enige factor en ben je klaar. Als m even is, deel door 2 tot het resultaat oneven is. Als m oneven en samengesteld is, zijn er bij elke b minstens vier getallen met b als kwadraat. Neem een random c en bereken b = c2 , en gebruik de app om een a te vinden met a2 = c2 . Omdat c random gekozen is, is er een kans van minstens 1/2 dat c noch aan a, noch aan −a gelijk is. Herhaal het kiezen van c tot dit optreedt. Je beschikt dan over twee niet-complementaire getallen met gelijk kwadraat, waarmee je een factor van m vindt als ggd(m, a + c). Deze berekening is (exclusief het gebruik van de app) polynomiaal en roept de app verwacht hoogstens tweemaal aan. (b) Nee. Omdat je met een goeie wortels-app kunt factoriseren, denk ik om te beginnen niet dat Inst Inc dat echt kan waarmaken. Als het ze wel is gelukt om dit 3000 jaar oude probleem op te lossen, hebben ze een RSA-kraker in handen waarmee ze het Internet en de rest van de wereld rulen. Ze zijn waarschijnlijk al door de Amerikanen, de Russen, de Chinezen, de Israeli’s en de Koreanen ontvoerd, gemarteld en vermoord en bestolen voordat ze hun eerste cent hebben omgezet. (c) Modulo een priemgetal m kun je gemakkelijk de wortel uit b vinden, namelijk als a = b(p+1)/4 . Die berekening kun je best in een app programmeren, maar ik geloof niet dat je daarmee een half miljoen kunt verdienen. Beoordeling: Totaal 3pt, 2 voor a en 1/2 voor b en c elk. D = Dat de worteltrektruuk alleen voor viervouden plus Drie geldt is juist maar dat hoefde er niet bij. F = Bij (c): niet nuttig want een priem is niet te factoriseren. Geen goed antwoord, want het is niet gezegd dat factoriseren de enige nuttige toepassing van de app kan zijn. H = Je mag de app ook prijzen als grote doorbraak, maar zeg wel iets over de Haalbaarheid. Je steekt je geld toch ook niet in een Perpetuum Mobiel app? K = Je Kunt weinig met zo’n app. Hm, kijk eens in de app store of dat wel zo’n sterk argument is om geen geld met de app te kunnen verdienen. M = De gevalsonderscheiding hierboven is niet compleet, want het geval dat m een macht van een priemgetal is, ontbreekt. Bv 625 is niet priem, niet even, en de CRT werkt er niet voor. Maar dit mocht je negeren. Overigens is het in polynomiale tijd te testen of m een priemmacht is. N = De app bewijst dat P = NP; onjuist want Factoriseren is wel in NP, maar voor zover we weten niet NP-compleet. Dus helaas, zelfs als de app zou werken, nog geen millenniumprijs. P = Voor viervouden Plus 1 is worteltrekken niet behandeld, maar zeker niet moeilijk (dat is wel genoemd op HC), dus ook daarmee kun je nog geen half miljoen terugverdienen. T = Je moet Twee wortels van hetzelfde getal hebben. Dat doe je niet door meerdere malen dezelfde b aan te bieden! De app kan deterministisch werken zodat je steeds dezelfde a krijgt. Ook input 1 aanbieden (waarvan je wortels 1 en −1 al kent) is niet goed omdat je nooit weet of je dan een niet-complementaire krijgt. W = Gebruik de Wp en Wq ; dat kan niet, want die kun je pas vinden als je de factoren kent.
5. Elgamal rekentijd: Voor Elgamal encryptie worden gedeelde parameters, een modulus en een generator g gebruikt. De private key is een getal a en de public key is b = g a . Je hoort geruchten dat bij Elgamal, de encryptie tweemaal zo duur is als de decryptie, maar dat je de berekening kunt versnellen door een Chinese stelling te gebruiken. (a) Klopt het dat encryptie zoveel duurder is, en waarom? (b) Hoeveel kun je de berekening versnellen met die Chinese stelling? Oplossing: (a) Ja, dat klopt. De rekentijd wordt gedomineerd door machtsverheffen. Voor encryptie moet dat twee keer (Rnd k, u = bk , v = g k · x) en voor decryptie maar een keer (x = v/ua ). (b) De modulus p is een priemgetal, daarvoor is splitsen van de berekening in twee delen met de CRT niet mogelijk. Het tweede gerucht is onjuist, de “triviale speedup factor” is dus 1. Beoordeling: Tot 2pt, 1 voor a en 1 voor b. C = De CRT is een Rest Stelling, geen Rijst-stelling. F = Je kunt CRT niet gebruiken omdat je de factorisatie van de modulus niet kent is onjuist! K = De berekening van b = g a is deel van de Key generation en telt niet mee bij de decryptie. M = Het is niet Machtsverheft maar machtsverheven. V = Je kunt u = bk wel Voorberekenen, maar je moet dit wel voor elk bericht weer doen, dus telt wel mee voor encryptietijd.
6. Een Kraak bij SecuCert: Chinese hackers hebben ingebroken bij Certificate Authority SecuCert en de geheime signing key gestolen, waardoor zij valse SecuCert-websitecertificaten kunnen uitgeven. Lia weet dat gmail.com niet beveiligd is met een SecuCert-certificaat, maar met een GeoTrust-certificaat. Kan Lia veilig naar gmail.com gaan, en welke maatregelen moet zij eventueel nemen? Oplossing: De echte gmail.com site heeft wel een GeoTrust certificaat, maar de hackers kunnen een neppe site maken met een vals SecuCert certificaat! De browser signaleert niet waar een certificaat vandaan komt, als er maar een trust chain is die loopt tot een root certificaat. Lia moet dus bij het checken van haar mail opletten dat de site die zij bezoekt, niet is beveiligd met een certificaat van SecuCert. Na een update van haar browser zal SecuCert waarschijnlijk vanzelf uit de lijst van vertrouwde aanbieders zijn verdwenen. Beoordeling: Tot 2pt voor goede uitleg. In de volksmond wordt erover gesproken dat “een certificaat een site beveiligt”, maar je moet inzien dat een certificaat weinig doet als je eenmaal op de goede site zit. Het certificaat is een instrument dat jou moet terugsturen wanneer je op een verkeerde site terecht komt. Dat kan door criminelen worden uitgelokt met typosquatten (gmall.com of gmial.com). Maar de overheid, NSA en/of providers kunnen het ook wanneer je het goede adres typt door een omleiding van verkeer binnen het Internet. Dit is na de DigiNotar hack daadwekelijk gebeurd bij Iraanse dissidenten; die hebben hun gmailwachtwoord ingetypt op een neppe site, iets wat in sommige landen erg gevaarlijke gevolgen kan hebben. A = Je moet opletten dat “gmail” niet opeens een Ander certificaat heeft. D = In de DigiNotar kwestie is dit echt gebeurd. J = Het adres juist intypen is niet genoeg ivm. omleiding van verkeer.
