De rol van wiskunde in de strijd tegen aliens
Een leger aliens is geland op onze planeet en plant een snelle invasie. Als opperbevelhebbers is het onze taak het mensenleger te doen zegevieren. Om de aliens te verslaan, moeten we weten waar ze zich precies bevinden en welke richting ze uitgaan. Natuurlijk kunnen we niet zomaar soldaten sturen naar de bezette regio’s: die worden meteen ontdekt en neergeschoten door de buitenaardse laserpistolen. Hoe kunnen we de Aarde redden van de ondergang?
Al snel bedenken we een slim plan. We bevelen onze luchtmacht over het vijandelijke gebied te vliegen en duizenden sensoren te droppen. Sensoren zijn kleine toestelletjes (ongeveer zo groot als een muntstuk) die op batterijen werken en de bewegingen van de aliens kunnen registreren. Bovendien kunnen ze draadloos met elkaar communiceren. Wanneer de sensoren op de grond landen, vormen ze samen een groot netwerk: ze sturen hun informatie naar elkaar door totdat die bij ons aankomt. Met die gegevens kan ons leger de aliens in de pan hakken. Briljant!
Jammer genoeg blijken de aliens toevallig experts te zijn in het onderscheppen van draadloze communicatie. Zo kunnen ze de informatie die naar ons wordt doorgestuurd aanpassen om ons op een verkeerd been te zetten en alsnog de wereld te veroveren. Om dat te vermijden, moeten we ons netwerk dus beveiligen. Maar hoe doen we dat? Gelukkig hebben we het bevel over wiskundigen die ons daarbij kunnen helpen. Zij leggen ons uit dat we zogenaamde symmetrische encryptie kunnen gebruiken. Het principe van symmetrische encryptie is eenvoudig: twee sensoren gebruiken eenzelfde geheime sleutel om hun boodschappen te coderen; alleen met die specifieke sleutel is het mogelijk hun berichten weer te ontcijferen. Dat klinkt perfect.
Er is echter een bijkomend probleem: nadat onze soldaten de sensoren hebben gedropt, kunnen ze er niet meer mee interageren. We moeten de sleutels voor encryptie dus op voorhand opslaan in de toestelletjes. Door onze beveiliging mogen twee sensoren enkel met elkaar communiceren als ze een gemeenschappelijke sleutel hebben. We moeten de sleutels dus zorgvuldig verdelen onder de sensoren. Er bestaat een moeilijk woord voor zo’n verdeelstrategie: een sleutelpredistributie-schema (afgekort SPS).
Ziezo, we hebben nu een duidelijke opdracht voor onze wiskundigen: bedenk een goed SPS. Daarmee kunnen we een veilig netwerk van sensoren maken, zodat we de aliens in de gaten kunnen houden. Al snel merken de wiskundigen op dat drie factoren belangrijk zijn bij het ontwerpen van een SPS. Ten eerste is er de sleutelopslag. Dat is het aantal sleutels dat elke sensor moet opslaan. Omdat sensoren erg klein zijn, is hun geheugen beperkt, dus we moeten proberen de sleutelopslag zo klein mogelijk te houden. Vervolgens is er de connectiviteit van het netwerk. Als een sensor geen buren heeft met gemeenschappelijke sleutels, dan kan hij zijn gegevens niet doorgeven. Om weinig kans te hebben op zulke nutteloze sensoren, moet de connectiviteit zo hoog mogelijk zijn. Dat wil zeggen dat zo veel mogelijk sensoren met elkaar moeten kunnen communiceren. Ten slotte willen we natuurlijk de veiligheid van het netwerk maximaliseren. Dat is belangrijk, omdat de aliens kunnen proberen sleutels te raden door de berichten van sensoren op te vangen.
Goed, laten we snel een SPS maken en die aliens verpletteren! Nu we al die dingen weten, moet dat een koud kunstje zijn, toch? Helaas, de wiskundigen sputteren weer tegen. Een wijsneus komt ons algauw uitleggen dat het allemaal niet zo eenvoudig is. Drie gemakkelijke voorbeelden moeten ons daarvan overtuigen.
Probeer eerst dezelfde sleutel in elke sensor op te slaan. Eén sleutel zorgt voor minimale sleutelopslag en laat elke sensor toe met alle andere sensoren te communiceren. Mooi zo. Maar als de aliens die ene sleutel raden, dan kunnen ze meteen alle berichten in het netwerk ontcijferen. Dit SPS is dus niet bepaald veilig.
Om de veiligheid te verbeteren, is het aangeraden het hergebruik van sleutels te beperken. Misschien kunnen we voor elk paar sensoren een unieke sleutel maken en die in beide toestellen opslaan? Op die manier hebben we nog steeds maximale connectiviteit. Bij het raden van één sleutel blijft de communicatie tussen alle andere sensoren veilig, omdat alle sleutels verschillend zijn. Ook de veiligheid is dus optimaal. Maar het nadeel van dit SPS schuilt in de sleutelopslag. In een netwerk met 1000 sensoren moet elk apparaat bijvoorbeeld 999 sleutels opslaan. Dat is veel te veel in de praktijk.
Een laatste poging: laten we in elke sensor slechts één unieke sleutel opslaan. Dan hebben we minimale sleutelopslag en maximale veiligheid. Oké, deze keer zien we het addertje onder het gras wel aankomen. Inderdaad, geen enkele sensor kan communiceren met andere sensoren. Compleet zinloos! Ook dit SPS is goed voor de prullenmand.
Uit pure wanhoop gooien we onze armen in de lucht. Het lijkt hopeloos. We zullen nooit de strijd tegen de aliens winnen, de mensheid is verloren! Smekend wenden we ons weer tot de wiskundigen. Wat moeten we nu doen? Een ander plan bedenken? Deze keer zijn we maar al te blij dat de wiskundigen ons geruststellen: we maken wel degelijk een kans. De laatste decennia hebben zij namelijk veel onderzoek gedaan naar SPSen. Ze bedachten een heleboel ingewikkelde manieren om sleutels te verdelen, gebaseerd op moeilijke wiskundige theorieën. Al die SPSen garanderen een beter evenwicht tussen sleutelopslag, connectiviteit en veiligheid. Dankzij die methoden kunnen we ons plan toch uitvoeren en de strijd aangaan met de aliens. Op naar de overwinning, met dank aan de wiskunde!
Hoewel het belang van SPSen werd geïllustreerd met een spannende oorlog tegen aliens, zijn er nog ontelbare andere toepassingen. Sensoren worden vandaag al vaak ingezet in moeilijk bereikbare gebieden: ze meten de temperatuur in vulkaankraters, registreren voorbodes van aardbevingen in bergen, brengen de verspreiding van bosbranden in kaart, enzovoort. Het onderzoek naar SPSen is trouwens springlevend, aangezien wiskundigen tot vandaag niet voldoende begrijpen waarom sommige strategieën goed werken of beter zijn dan andere. Gezien de talloze toepassingen is het erg belangrijk verder te investeren in onderzoek. Kwestie dat we klaar zijn als die aliens toch komen…
Bibliografie
[1] N. Alon and J.H. Spencer. The Probabilistic Method. Discrete Mathematics and Optimization. John Wiley & Sons, Hoboken, New Jersey, fourth edition, 2016.
[2] T.M. Apostol. Introduction to Analytic Number Theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1976.
[3] S.R. Blackburn, T. Etzion, K.M. Martin, and M.B. Paterson. Efficient key predistribution for grid-based wireless sensor networks. In R. Safavi-Naini, editor, 3rd International Conference on Information Theoretic Security, volume 5155 of Lecture Notes in Computer Science, pages 54-69, Calgary, August 2008. Springer-Verlag, Berlin, Heidelberg.
[4] R. Blom. An optimal class of symmetric key generation systems. In T. Beth, N. Cot, and I. Ingemarsson, editors, Advances in Cryptology. EUROCRYPT 1984, volume 209 of Lecture Notes in Computer Science, pages 335-338. Springer-Verlag, Berlin, Heidelberg, 1985.
[5] C. Blundo, A. De Santis, and A. Herzberg et al. Perfectly-secure key distribution for dynamic conferences. In Advances in Cryptology, CRYPTO' 92, volume 740 of Lecture Notes in Computer Science, pages 471-486. Springer-Verlag, August 1992.
[6] S.A. Camtepe, B. Yener, and M. Yung. Expander graph based key distribution mechanisms in wireless sensor networks. In IEEE, editor, IEEE International Conference on Communications, IEEE International Conference on Communications, pages 2262-2267. IEEE, 2006.
[7] P. Cara. Discrete wiskunde. Course notes, Vrije Universiteit Brussel, 2012.
[8] P. Cara. Lineaire algebra, volumes I and II. Course notes, Vrije Universiteit Brussel, 2012.
[9] H. Chan, A. Perrig, and D. Song. Random key predistribution schemes for sensor networks. In Proceedings of the 2003 IEEE Symposium on Security and Privacy, pages 197-214. IEEE Computer Society, Washington DC, May 2003.
[10] W. Dargie and C. Poellabauer. Fundamentals of Wireless Sensor Networks. Theory and Practice. Wireless Communications and Mobile Computing. John Wiley & Sons, West Sussex, 2010.
[11] G. Davidoff, P. Sarnak, and A. Valette. Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge University Press, Cambridge, 2003.
[12] W. Diffie and M.E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, November 1976.
[13] W. Du, J. Deng, Y.S. Han, and P.K. Varshney. A pairwise key pre-distribution scheme for wireless sensor networks. In Proceedings of the 10th ACM conference on Computer and communications security, pages 42-51, Washington D.C., October 2003.
[14] P. Erdös and A. Rényi. On the evolution of random graphs. Bulletin of the International Statistical Institute, 38(4):343-347, 1960.
[15] L. Eschenauer and V.D. Gligor. A key-management scheme for distributed sensor networks. In Proceedings of the 9th ACM conference on Computer and communications security, pages 18-22, Washington DC, November 2002.
[16] C. Godsil and G. Royle. Algebraic Graph Theory. Graduate Texts in Mathematics. Springer-Verlag, 2001.
[17] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, October 2006.
[18] E. Kendall, M. Kendall, and W.S. Kendall. A generalised formula for calculating the resilience of random key predistribution schemes. Cryptology ePrint Archive, Report 2012/426, 2012. http://eprint.iacr.org/2012/426.
[19] M. Kendall and K.M. Martin. On the role of expander graphs in key predistribution schemes for wireless sensor networks. In F. Armknecht and S. Lucks, editors, WEWoRC 2011. Research in Cryptology, volume 7242 of Lecture Notes in Computer Science, pages 62-82. Springer-Verlag, Berlin, Heidelberg, 2012.
[20] M. Kendall and K.M. Martin. Graph-theoretic design and analysis of key predistribution schemes. Designs, Codes and Cryptography, 81(1):11-34, October 2016.
[21] N. Koblitz. A Course in Number Theory and Cryptography. Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1994.
[22] M. Krebs and A. Shaheen. Expander Families and Cayley Graphs: A Beginner's Guide. Oxford University Press, Oxford, 2011.
[23] J. Lee and D.R. Stinson. Deterministic key predistribution schemes for distributed sensor networks. In H. Handschuh and M. Anwar Hasan, editors, Selected Areas in Cryptography, volume 3357 of Lecture Notes in Computer Science, pages 294-307. Springer-Verlag, Berlin, Heidelberg, 2004.
[24] J. Lee and D.R. Stinson. Common intersection designs. 14(4):251-269, 2006.
[25] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.
[26] G.A. Margulis. Explicit constructions of concentrators. Problems of Information Transmission, 9(4):325-332, October-December 1973.
[27] K.M. Martin. On the applicability of combinatorial designs to key predistribution for wireless sensor networks. In Y.M. Chee, C. Li C., S. Ling, H. Wang, and C. Xing, editors, Coding and Cryptology, volume 5557 of Lecture Notes in Computer Science, pages 124-145. Springer, Berlin, Heidelberg, 2009.
[28] K.M. Martin. The rise and fall and rise of combinatorial key predistribution. In A. Biryukov, G. Gong, and D.R. Stinson, editors, Selected Areas in Cryptography, volume 6544 of Lecture Notes in Computer Science, pages 92-98. Springer, Berlin, Heidelberg, 2011.
[29] F. Martincic and L. Schwiebert. Introduction to wireless sensor networking. In I. Stojmenovic, editor, Handbook of Sensor Networks. Algorithms and Architectures, Parallel and Distributed Computing, chapter 1, pages 1-40. John Wiley & Sons, Hoboken, New Jersey, 2005.
[30] C.J. Mitchell. Key storage in secure networks. Discrete Applied Mathematics, 21(3):215-228, October 1988.
[31] T. Newe, V. Cionca, and D. Boyle. Security for wireless sensor networks, configuration aid. In S.C. Mukhopadhyay and H. Leung, editors, Advances in Wireless Sensors and Sensor Networks, volume 64 of Lecture Notes in Electrical Engineering, pages 1-24. Springer-Verlag, Berlin, Heidelberg, 2010.
[32] A. Nilli. On the second eigenvalue of a graph. Discrete Mathematics, 91:207-210, August 1991.
[33] H.K. Patil and S.A. Szygenda. Security for Wireless Sensor Networks using Identity-Based Cryptography. CRC Press, Boca Raton, 2013.
[34] M. Pinsker. On the complexity of a concentrator. In 7th International Telegraffic Conference, pages 318/1-318/4, Stockholm, June 1973.
[35] O. Reingold, S. Vadhan, and A. Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, 155(1):157-187, January 2002.
[36] E. Sabbah and K. Kang. Security in wireless sensor networks. In S. Misra, I. Woungang, and S.C. Misra, editors, Guide to Wireless Sensor Networks, Computer Communications 491 and Networks, chapter 19, pages 491-512. Springer-Verlag, London, 2009.
[37] R.R. Selmic, V.V. Phoha, and A. Serwadda. Wireless Sensor Networks. Security, Coverage, and Localization. Springer, 2016.
[38] H. Shaffiei, A. Mehdizadeh, A. Khonsari, and M. Ould-Khaoua. A combinatorial approach for key-distribution in wireless sensor networks. In IEEE, editor, IEEE GLOBECOM 2008, IEEE Global Telecommunications Conference. IEEE, 2008.
[39] D.R. Stinson. Cryptography, Theory and Practice. Discrete Mathematics and its Applications. Chapman and Hall, Boca Raton, third edition, 2006.
[40] L. Trevisan. Pcp and hardness of approximation, notes for lecture 11. Course notes, U.C. Berkeley, 2006.
[41] Y. Zhou, Y.G. Fang, and Y.C. Zhang. Securing wireless sensor networks: A survey. IEEE Communications Surveys & Tutorials, 10(3):6-28, 2008.
