Key generation errors in the HIMMO scheme
B Bouke Cloostermans · TU/e Research Portal · 2014
HIMMO is a light-weight symmetric key establishment scheme aiming at fully collusionresistant identity-based key agreement. In an identity-based pairwise key agreement scheme, a Trusted Third Party provides each node in the system with private keying material. Two nodes can then generate a pairwise key by using their own keying material and the identity number of the other node. The full collusion resistance property implies that the scheme remains secure even if arbitrarily many nodes are compromised. Finally, the light-weight property means that HIMMO can efficiently run on devices with limited storage capacity and computation power. HIMMO mix is a variation on HIMMO aiming at the same properties. Generated pairwise keys in HIMMO are nearly equal, but not exactly so. In compensating for this discrepancy, nodes waste valuable storage space and computation time. We provide new insights into the behavior of the key generation errors. This allows a node to very efficiently compensate for the error it makes while generating keys, resulting in lower storage requirements and faster key computation time. Our modifications reduce storage requirements for common HIMMO setups by 10% to 75% for common HIMMO setups. Compensating for the errors is even more important in HIMMO mix, as errors prevented HIMMO mix from being set up with anything but trivial parameters. Using our modifications, HIMMO mix errors can efficiently be dealt with for almost any choice of parameters. Our new insights also revealed security risks. Key generation errors provide an attacker with additional information about the keying material of a target node. This makes retrieving the keying material of a target node easier than was previously assumed. Using information gathered from key generation errors, we show how an attacker can retrieve a node’s keying material in a HIMMO system and several HIMMO mix systems which were assumed to have the full collusion resistance property. However, for sufficiently large system parameters, retrieving keying material remains computationally infeasible. iii Acknowledgements This thesis is the result of my graduation project for the master program Industrial and Applied Mathematica at Eindhoven University of Technology. The project was carried out during an internship at Philips Research. I would like to thank my supervisors at Philips, Ludo Tolhuizen, Ronald Rietman and Oscar Garcia, not only for the opportunity to do the internship, but also for their guidance on my research and their invaluable suggestions on how to improve my thesis. Of course, I would like to express my deep gratitude to my supervisor from TU/e, Berry Schoenmakers for his supervision and insightful comments. I would also like to thank Benne de Weger and Aart Blokhuis for being on my graduation committee. Thanks also go to my parents, for their continued support. Finally, I wish to thank my girlfriend Christine and all my friends at university for making my studies at Eindhoven a very enjoyable time. Without you guys I would never have made it this far!