Online Authentication with Encryption and Anonymous Authentication in Vehicular Ad- hoc Networks A thesis submitted in partial fulfillment of the requirements for the degree of Master of Technology in Computer Science and Engineering by Umang Jain (03CS3005) Under the guidance of Prof. Dipanwita Roy Chowdhury Department of Computer Science and Engineering Indian Institute of Technology Kharagpur – 721302 May 2008 1 Department of Computer Science and Engineering IIT Kharagpur CERTIFICATE This is to certify that the thesis entitled, ‘Online Authentication with Encryption and Anonymous Authentication in VANET’ submitted by Umang Jain (03CS3005) in partial fulfillment of the requirements for the award of degree of Masters of Technology in Computer Science and Engineering, to the Indian Institute of Technology, Kharagpur, is a bonafide work carried out by him under my supervision and guidance. The thesis fulfills the requirements relating to the nature and standard of work prescribed for the award of the above mentioned degree. The results embodied in this thesis have not been submitted elsewhere to any other University or Institute for the award of any other degree or diploma. Prof. D. Roychowdhury Dept. of Computer Science and Engg. Indian Institute of Technology Kharagpur -721302, India May 2008 2 ACKNOWLEDGEMENTS I would like to take this opportunity to express my sincere gratitude towards my project supervisor Prof. Dipanwita Roy Chowdhury who has been a guide, a teacher and a role model for the past two and a half years. Working on the project was a great learning experience under her constant encouragement and support. I would also like to thank Prof. Abhijit Das for his constructive feedback for the project. I am also thankful to all the faculty members for their cooperation and for all that I learnt from them. I also owe my gratitude my friend and colleague Nitin Bansal for motivating me throughout and to my friend Arijit Ghosh for his feedback in important stages of the project. I am also thankful to my classmates for their company for five years and all friends who have directly or indirectly assisted me in my endeavors. Umang Jain 3 Abstract Authentication is the act of establishing or confirming something (or someone) as authentic, that is, that claims made by or about the thing are true. Authenticating an object may mean confirming its originality whereas authenticating a person often consists of verifying their identity. In the ranks of cryptography verifying the authenticity of data or an entity is an unavoidable, indispensable task. Only the mere appreciation of importance of authentication in cryptography gives one enough motivation to put thorough efforts in this field. In the work documented in this thesis, the problem of Authentication in two different scenarios has been undertaken. The first problem is carrying out data authentication together with encryption when the later has to be accomplished in an online manner. In this regard a framework for online Authentication with encryption has been proposed along with a flexible keyed-hash function based on Cellular Automata. In the later part, the problem of entity authentication accompanied with the requirement of anonymity in Vehicular Ad-hoc Networks (VANET) has been considered. Here we have proposed a group signature algorithm based on Chinese Remainder Theorem. 4 Table of Contents 1 Introduction: Encryption with Authentication 1.1 Authenticated Encryption (AE): An introduction………….........................…….8 1.2 An Overview of Cellular Automata………….......................................................13 2 Online Authentication with Encryption 2.1 A Framework for online Authenticated Encryption....................................……17 2.2.1 The proposed Framework………………………………………………17 2.1.2 Design Rationale…………………………………………………………18 2.2 Rule 30 evolutions in cryptography……………………………………………...19 2.3 CHASH: A cellular Automata Based Hash Function…………………………..23 2.3.1 Overview………………………………………………………………….23 2.3.2 CHASH Algorithm………………………………………………………23 2.3.3 Rule Generation…………………………………………………………..24 2.3.4 One Round of CHASH…………………………………………………..25 2.3.5 Generation of Hash Value………………………………………………25 Evaluation of CHASH…………………………………………………………………28 2.4.1 Bit Variance Test………………………………………………………….28 2.4.2 Entropy Assessment……………………………………………………..29 2.4.3 Measuring the Diffusion………………………………………………...30 2.4.4 Measuring the Confusion……………………………………………….31 2.5 Irreversibility of CHASH………………………………………………………….32 2.6 Security Analysis…………………………………………………………………...33 2.6.1 Random Attack…………………………………………………………...33 2.6.2 Birthday Attack…………………………………………………………..34 2.6.3 Correcting Block Attack…………………………………………………34 2.6.4 Fixed Point Attack………………………………………………………..34 2.6.5 Meet in the Middle Attack………………………………………………34 2.6.6 Common Attacks against CA based Hash Functions………………...34 2.7 Conclusion……………………………………………………………………….....35 3* Introduction to VANET 3.1 Vehicular Ad-Hoc Networks: An introduction................................…………....37 3.2 Inter-Vehicular Communication: Applications....................................................39 5 3.2.1 Safety Applications...................................................................................39 3.2.2 Services Related Applications.................................................................40 3.3 System Model Assumptions....................................................................................40 3.4 Security Challenge....................................................................................................42 3.5 State of the art............................................................................................................44 3.6 Motivation..................................................................................................................46 3.7 Objective.....................................................................................................................47 3.8Conclusion..................................................................................................................48 4* GSCRT: A Group Signature Scheme 4.1 Introduction... ………………………….............…………………...…...……........48 4.2 Preliminaries………………...........................................…………...……................48 4.2.1 Network and Infrastructure Assumptions…...................………..........48 4.2.2 Chinese Remainder Theorem…...............................................................48 4.3 GSCRT....................................................................................................................................49 4.3.1 Proposal.................................................................................................................49 4.3.2 Signature Generation.........................................................................................51 4.3.3 Signature Verification........................................................................................51 4.3.4 Identity Extraction...............................................................................................51 4.3.5 Correctness...........................................................................................................51 4.3.6 Application to VANET.....................................................................................53 4.3.7 Addition of a new member ............................................................................54 4.3.8 Removal of a member......................................................................................54 4.4 Security Analysis. ............................................................................................................55 4.4.1 Anonymity...........................................................................................................55 4.4.2 NonFrameability................................................................................................55 4.4.3 Unlinkability……………………................................………..……….....55 4.4.4 Traceability..........................................................................................................56 4.4.5 Attacks..................................................................................................................57 4.4.5.1 Insider Replay Attack….................................................………57 4.4.5.2 Guessing Ni’s………….............................................…..………57 4.5 Time Complexity…………………….....................................................….……….58 4.5.1 Basic Definitions……………..............................................…………….....58 4.5.2 Signature Generation Complexity…....................................………….....59 4.5.3 Signature Verification Complexity …..................................………….....60 4.6 Overhead and Storage Requirements………….........................….......…………61 4.7 Conclusion…….................................................................................................……61 6 5* Modified GSCRT 5.1 Introduction... ……………………………...................................................………62 5.2 Modified GSCRT……………………………...............................................………62 5.2.1 Proposal…………………………...............................................................62 5.2.2 Signature Generation………………….....................……………………64 5.2.3 Signature Verification…………………………........................................64 5.2.4 Identity Extraction ............................................................................................64 5.2.5 Correctness ………………………………….............................................65 5.2.6 Application to VANET………………………...................................…...65 5.2.7 Addition of a new member ………………….......................…………...65 5.2.8 Removal of a member……………………............................……………65 5.3 Timestamp inclusion in CRTKi .....................................................................................66 5.3.1 Signature Verification with Timestamp……………..............................67 5.4 Security Analysis……………………………...........................................................67 5.4.1 Properties………........................................................................................67 5.4.2 Attacks…….……………………………....................................................67 5.5 Time Complexity……………………………...........................................................67 5.5.1 Signature Generation …………................................................................67 5.5.2 Signature Verification ……………...........................................................68 5.6 Communication Overhead and Storage Requirements......................................68 5.6.1 Overhead …………....................................................................................68 5.6.2 Storage Requirements……………............................................................69 5.6.3 Communication Overhead Comparison……………............................69 5.6.4 Storage Overhead Comparison................................................................70 5.6.5 Time Complexity Comparison.................................................................70 5.7 Conclusion and Future Work………......................................................................71 Bibliography …………………………………………………………………………..73 * The work documented in these chapters has been done jointly with Nitin Bansal (03CS3015) 7 List of figures: 1.1 1D Cellular Automata………………………………………………………....…14 2.1 AE scheme (block diagram)………………………………………………..…….18 2.2 CA rule 30…………………………………………………………………………20 2.3 Rule 30 predecessors ……………………………………………………………..21 2.4 Rule 30 viable predecessors……………………………………………………...22 2.5 CHASH operation………………………………………………………………...27 2.6 Entropy Assessment……………………………………………………………...30 2.7 Diffusion in CHASH……………………………………………………………...31 2.8 Confusion in CHASH…………………………………………………………….32 List of tables: 1.2 A comparison of AE schemes……………………………………………………12 2.1 Bit Variance Test (1 bit)…………………………………………………………..28 5.1 Overhead and Storage Comparison with Other Schemes…………………….69 5.2 Time Complexity Comparison with RSA……………………………………….71 8 Chapter 1 Introduction: Encryption with Authentication 1.1 Authenticated Encryption (AE): An introduction Often when two parties communicate over a network, they have two main security goals: privacy and authentication. In fact, there is compelling evidence that one should never use encryption without also providing authentication. Many solutions for the privacy and authentication problems have existed for decades, and the traditional approach to solving both simultaneously has been to combine them in a straightforward manner using so-called “generic composition.” However, recently there have been a number of new constructions which achieve both privacy and authenticity simultaneously, often much faster than any solution which uses generic composition. This approach to achieving both privacy and integrity is the so-called “Authenticated Encryption” problem. An AE scheme has two goals: privacy and authenticity. Privacy means, intuitively, that a passive adversary who views the ciphertext C and the nonce N, cannot “understand” the content of the message M. One way to achieve this is to make C indistinguishable from random bits, and indeed this is one definition of security for an encryption scheme that is sometimes used, although it is quite a strong one. Authenticity means that an adversary cannot modify a message such that the receiver is not able to detect it. With the help of an authentication tag the receiver is able to verify of whether the message received by it exactly the same message that was sent by the sender. 9 Although AE did not get a formal definition until recently [1], the goal has certainly been implicit for decades. The traditional way of achieving both authenticity and privacy was to simply find an algorithm which yields each one and then use the combination of these two algorithms on our message. Intuitively it seems that this approach is obvious, straightforward, and completely safe. Unfortunately, there are many pitfalls accidentally “discovered” by well-meaning protocol designers. One commonly-made mistake is the assumption that AE can be achieved by using a non-cryptographic non-keyed hash function h and a good encryption scheme like CBC mode (Cipher Block Chaining mode; see CBC-MAC and variants) with key K and initialization vector N. One produces CBCK,N(M, h(M)) and hopes this yields a secure AE scheme. However, these schemes are virtually always broken. Perhaps the best-known example is the Wired Equivalent Privacy protocol (WEP) used with 802.11 wireless networks. This protocol instantiates h as a Cyclic Redundancy Code (CRC) and then uses a stream cipher to encrypt. Borisov, Goldberg, and Wagner showed, among other things, that it was easy to circumvent the authentication mechanism. Another common pitfall is “key reuse”. In other words, using some key K both for the encryption scheme and the MAC scheme. This approach applied blindly almost always fails. We will later see that all the secure “combined modes,” do in fact use a single key, but they are carefully designed to retain security in spite of this. It is now clear to researchers that one needs to use a keyed hash (i.e., a MAC) with some appropriate key K1 along with a secure encryption scheme with an independent key K2. However, it is unclear in what order these modes should be applied to a message M in order to achieve authenticated encryption. There are three obvious choices: • MtE: MAC-then-Encrypt. We first MAC M under key K1 to yield tag σ and then encrypt the resulting pair (M, σ) under key K2. 10