ENHANCED CRYPTOGRAPHICALLY GENERATED ADDRESS (CGA) ALGORITHMS FOR MOBILE IPV6
BY
SANA QADIR
A Thesis submitted in fulfilment of requirement for the degree of Doctor of Philosophy (Engineering)
Kulliyyah of Engineering
International Islamic University Malaysia
AUGUST 2016
ii
ABSTRACT
This thesis studied the Cryptographically Generated Address (CGA) algorithms in order to improve the security and performance of Mobile Internet Protocols (MIPv6) networks. At present, the biggest weakness in a MIPv6 network is the poor authentication of the Binding Update (BU) message. If a mobile node uses the CGA algorithms, then most of the attacks against a MIPv6 network can be prevented.
However, using CGA algorithms is computationally costly. This thesis developed enhanced versions of the CGA algorithms. These Enhanced CGA algorithms provide a minimum computational security of O(280) and replace the use of the Rivest- Shamir-Adleman (RSA) signature scheme with the Merkle Signature Scheme (MSS).
MSS is selected because its security relies on the collision resistance property of the hash function used and because it is resistant to differential side channel attacks. The thesis implemented the Enhanced CGA algorithms in C and evaluated their performance on a low-end node. It found that the Enhanced CGA Generation algorithm takes 89 ms (56% faster than the original CGA Generation algorithm at O(280)). An additional speedup of 37-40% can be obtained with the use of multithreading on a quadcore processor. Likewise, the Enhanced CGA Signature Generation algorithm is found to be 72% faster (182.5 ms) than the original CGA Signature Generation algorithm. However, the Enhanced CGA Verification algorithm and the Enhanced CGA Signature Verification algorithm are found to be slower than the original algorithms by 121% and 402% respectively. The net result of using the Enhanced CGA algorithms (instead of the original CGA algorithms) is a reduction in Layer 3 latency by 30.7 ms. This reduction is mainly because MSS key generation is 98.7% faster than RSA-3072 key generation. It is also important to note that using Enhanced CGA algorithms requires an additional 1,493 bytes to be transmitted and an additional 5,077 bytes of memory. Overall, the Enhanced CGA algorithms can be considered a significant improvement over the original CGA algorithms because they provide a higher minimal computational security of O(280) and reduce Layer 3 latency by approximately 30.7 ms.
iii
صخلم ثحبلا
ABSTRACT IN ARABIC
( هرفشم ةقيرطب ينناونعلا ديلوت تايمزراوخ ةحورطلأا هذه تسرد ينستح لجأ نم )
CGAناملأاو ءادلأا
( لوملمحا تنترنلإا تلاوكوتورب تاكبشل
MIPv6
ةكبش في فعض ةطقن بركأ ،رضالحا تقولا في .)
MIPv6
( ثيدتح مزلم ةلاسرل ةيرقفلا ةقداصلما وه تايمزراوخ مدختسي ةلاقنلا زاهلجا ناك اذإ .)
BUةكبش دض تامجلها مظعم ،
CGA MIPv6مادختسا ،نكلو .اهنم ةياقولا نكيم تايمزراوخ
CGA
تايمزراوخ نم ةنسمح تارادصإ ةحورطلأا هذه تعضو .ايباسح فلكم تايمزراولخا هذه رفوت.
CGAل بياسلحا نملأا نم نىدلأا دلحا زيزعت ةنسلمحا
) O(280
تسفير عيقوتلا ماظن مادختسا لدبتستو -
يرماش -
( نالمدأ ( لكيرم عيقوتلا ماظن عم )
RSAرايتخا تم .)
MSSي اهنمأ نلأ
MSSةمواقم ةيصاخ ىلع دمتع
ةحورطأ .ةيبنالجا ةانقلا ىلغ ةيلضافتلا تامجهلل ةمواقم انهلأو ةمدختسلما ةئزجتلا ةلادل مادطصلاا تايمزراوخ تذفن ةغل في ةنسلمحا
CGAنأ دجوو .ةضفخنم ةيانه ةدقع ىلع اهئادأ مييقت تمو
Cذختأ ةنسلمحا ةيمزراولخا 89
( ةينثا يللم 56
٪ مزراوخ نم عرسأ ةي
في ةيلصلأا
CGA )O(280
نكيمو .
نم فياضإ عيرست ىلع لوصلحا 37
- 40
٪ .ةاونلا يعبار لجاعم ىلع ددعتلا ةيصاخ مادختسا عم
هنسلمحا عيقوتلا ديلوت ةيمزراوخ نا ىلع روثعلا تم ،لثلمباو 72
٪ ( عرسأ 182.5 ةيمزراوخ نم )ةينثا يللم
نا ىلع روثعلا تم ،نكلو .ةيلصلأا عيقوتلا ءاشنا عيقوت نم ققحتلا ةيمزراوخو ةنسلمحا ققحتلا ةيمزراوخ
ةنسلمحا
CGA، ةبسنب ةيلصلأا تايمزراولخاا نم أطبأ 121
٪ و 402
٪ ةجيتن فياص .لياوتلا ىلع
تايمزراوخ مادختسا ةقبطلا في يرخأتلا في ضافنخا يه )ةيلصلأا تايمزراولخا نم لادب( ةنسلمحا
CGA3 لداعي ابم 30.7
ذه .ةينثا يللم حاتفلما ديلوت عجري ضافنخلاا ا
عرسأ
MSS98.7
٪ حاتفلما ديلوت نم
مادختسبأ
RSA-3072
تايمزراوخ مادختسا نأ ظحلان نأ اضيأ مهلما نمو . بلطتي ةنسلمحا
CGAلاسرا 1،493 و ةيفاضإ تيبا
5،077 تايمزراوخ نإف ،امومعو .ةركاذلا نم ةيفاضإ تيبا
CGA
يربك نستح اهرابتعا نكيم ةنسلمحا تايمزراوخ ىلع
نملأا نم نىدأ دح رفوت انهلأ ةيلصلأا
CGAبياسلحا
) O(280
ةقبطلا في يرخأتلا نم دلحاو ةيلصلاا نم ىلعأ 3
نم برقي ام 30.7
.ةينثا يللم
iv
APPROVAL PAGE
The thesis of Sana Qadir has been approved by the following:
_______________________________
Mohammad Umar Siddiqi Supervisor
_______________________________
Farhat Anwar Co-supervisor
_______________________________
Aisha Abdalla Hashim Internal Examiner
_______________________________
Goi Bok Min External Examiner
_______________________________
Mohamad Yusoff Alias External Examiner
_______________________________
Ismaiel Hassanein Ahmed Mohamed Chairman
v
DECLARATION
I hereby declare that this dissertation is the result of my own investigation, except where otherwise stated. I also declare that it has not been previously or concurrently submitted as a whole for any other degrees at IIUM or other institutions.
Sana Qadir
Signature………....………. Date …….……….
vi
COPYRIGHT
INTERNATIONAL ISLAMIC UNIVERSITY MALAYSIA
DECLARATION OF COPYRIGHT AND AFFIRMATION OF FAIR USE OF UNPUBLISHED RESEARCH
ENHANCED CRYPTOGRAPHICALLY GENERATED ADDRESS (CGA) ALGORITHMS FOR MOBILE IPV6
I declare that the copyright holder of this dissertation are jointly owned by the student and IIUM.
Copyright © 2016 Sana Qadir and International Islamic University Malaysia. All rights reserved.
No part of this unpublished research may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise without prior written permission of the copyright holder except as provided below
1. Any material contained in or derived from this unpublished research may be used by others in their writing with due acknowledgement.
2. IIUM or its library will have the right to make and transmit copies (print or electronic) for institutional and academic purposes.
3. The IIUM library will have the right to make, store in a retrieved system and supply copies of this unpublished research if requested by other universities and research libraries.
By signing this form, I acknowledged that I have read and understand the IIUM Intellectual Property Right and Commercialization policy.
Affirmed by Sana Qadir
……..……….. ………..
Signature Date
vii
DEDICATION
To Allah SWT and His Messenger (P.B.U.H)
viii
ACKNOWLEDGEMENTS
In the name of Allah the most Beneficent, the most Merciful. All praises be to Allah, the Lord of the Universe. May the peace and blessings of Allah be upon Muhammad (peace be upon him), His last Messenger.
I would like to express my deepest gratitude to my supervisor Prof. Dr.
Mohammad Umar Siddiqi for his guidance and support. I would also like to thank Prof. Dr. Farhat Anwar, Prof. Dr. Aisha Abdalla Hashim and Dr. Wajdi F. M. Al- Khateeb and for all their advice and encouragement.
Last but not least, I would like to thank my family, friends and colleagues – their love, understanding and faith in me has been essential throughout this endeavour.
May Allah bless everyone with good in this world and the Next.
ix
TABLE OF CONTENTS
Abstract ... ii
Abstract in Arabic ... iii
Approval Page ... iv
Declaration ... v
Copyright ... vi
Dedication ... vii
Acknowledgements ... viii
List of Tables ... xii
List of Figures ... xiv
List of Abbreviations ... xvi
List of Symbols ... xviii
CHAPTER ONE: INTRODUCTION ... 1
1.1Introduction ... 1
1.2Problem Statement and Its Significance ... 5
1.3Research Objectives ... 6
1.4Research Hypothesis and Philosophy ... 7
1.5Research Approach ... 9
1.6Scope of Research ... 11
1.7Thesis Organisation ... 11
CHAPTER TWO: LITERATURE REVIEW ... 13
2.1Introduction ... 13
2.2Cryptographically Generated Addresses (CGAS) ... 13
2.3CGA-Based Authentication of Binding Update (BU) Message ... 15
2.4Original CGA Algorithms ... 17
2.4.1 CGA Generation Algorithm ... 17
2.4.2 CGA Verification Algorithm ... 20
2.4.3 CGA Signature Generation Algorithm ... 20
2.4.4 CGA Signature Verification Algorithm ... 22
2.5Related Work on CGA Generation and CGA Verification Algorithms ... 22
2.5.1 Discussion of Performance Studies... 22
2.5.1.1 Hash Extension Mechanism ... 25
2.5.1.2 Generation of Key Pair ... 27
2.5.1.3 Hash Function ... 28
2.5.2 Discussion of Possible Attacks and Mitigation Mechanisms ... 28
2.5.2.1 Global Time-Memory Trade-Off (TMTO) Attack ... 29
2.5.2.2 Impersonation ... 29
2.6Related Work on CGA Signature Generation and CGA Signature Verification Algorithms ... 33
2.6.1 Discussion of Performance Studies... 33
2.6.2 Discussion of Possible Attacks and Mitigation Mechanisms ... 36
2.7Post-Quantum Cryptography ... 38
2.7.1 Hash-based Signature Schemes ... 38
x
2.7.2 One-time Signature (OTS) Schemes ... 39
2.7.3 Winternitz One-time Signature (OTS) Scheme ... 40
2.8Multithreading for Multi-Core Architectures ... 50
2.9Summary ... 52
CHAPTER THREE: DESIGN OF EXPERIMENTS AND ALGORITHMS ... 54
3.1Introduction ... 54
3.2Experimental Design ... 54
3.2.1 Tools... 54
3.2.1.1 Maemo Software Development Kit (SDK) ... 55
3.2.1.2 Scratchbox ... 55
3.2.2 Setups ... 58
3.2.2.1 Low-end MN ... 58
3.2.2.2 Multi-core Architectures ... 58
3.2.3 Measures ... 59
3.3Design of Enhanced CGA Generation Algorithm ... 61
3.3.1 Without Multithreading... 61
3.3.1.1 Hash Extension Mechanism ... 61
3.3.1.2 Hash Function ... 64
3.3.1.3 Timestamp ... 65
3.3.1.4 Subnet Prefix ... 65
3.3.2 With Multithreading ... 67
3.4Design of Enhanced CGA Verification Algorithm ... 70
3.5Selection of Suitable Values for W-OTS Parameters ... 72
3.5.1 Implementation of W-OTS Scheme ... 72
3.5.2 Performance Evaluation ... 73
3.5.2.1 One-way Function f ... 74
3.5.2.2 Number of Bits to be Signed Simultaneously w ... 75
3.6Design of Key Generation for Enhanced CGA Signatures ... 76
3.6.1 Number of Keys Pairs N ... 76
3.6.2 Hash Function g ... 76
3.7Design of Enhanced CGA Signature Generation Algorithm ... 77
3.8Design of Enhanced CGA Signature Verification Algorithm ... 77
3.9Design of Enhanced CGA Parameters Data Structure ... 78
3.10Summary ... 79
CHAPTER FOUR: IMPLEMENTATION ... 81
4.1Introduction ... 81
4.2Libraries ... 81
4.3Data Structures ... 82
4.4Implementation of Enhanced Algorithms ... 84
4.4.1 Enhanced CGA Generation Algorithm ... 84
4.4.2 Enhanced CGA Verification Algorithm ... 86
4.4.3 Enhanced CGA Signature Generation and Verification Algorithms ... 86
4.4.3.1 Key Pair Generation ... 87
4.4.3.2 Signature Generation and Verification ... 87
4.5Testing the Enhanced CGA Algorithms ... 89
xi
4.6Discussion of Verification and Validation ... 95
4.7Summary ... 97
CHAPTER FIVE: PERFORMANCE EVALUATION ... 98
5.1Introduction ... 98
5.2Performance of Hash Functions in CGA Algorithms ... 98
5.3Performance for Different Computational Security ... 100
5.4Performance Comparison of Original and Enhanced algorithms ... 102
5.4.1 CGA Generation Algorithm (Without Multithreading) ... 102
5.4.2 CGA Generation Algorithm (With Multithreading) ... 104
5.4.2.1 Multicore Architecture i ... 104
5.4.2.2 Multicore Architecture ii ... 105
5.4.3 CGA Verification Algorithm ... 107
5.4.4 Key Generation ... 107
5.4.5 CGA Signature Generation Algorithm ... 108
5.4.6 CGA Signature Verification Algorithm ... 108
5.5Analysis of Impact on Handoff Delay ... 109
5.6Comparison of Memory Requirements and Data Transmitted ... 111
5.7Summary ... 112
CHAPTER SIX: CONCLUSION AND RECOMMENDATIONS ... 114
6.1Conclusion ... 114
6.2Contributions ... 116
6.3Recommendations for Future Work ... 117
REFERENCES ... 119
LIST OF PUBLICATIONS ... 125
APPENDIX I: ADDITIONAL ONLINE SOURCES ... 128
APPENDIX II: HEADER FILE FOR CGA GENERATION ... 130
APPENDIX III: HEADER FILE FOR CGA SIGNATURE GENERATION ... 132
APPENDIX IV: ENHANCED CGA GENERATION (WITHOUT MULTITHREADING) AND ENHANCED CGA VERIFICATION ... 137
APPENDIX V: ENHANCED CGA GENERATION WITH MULTITHREADING ... 150
APPENDIX VI: ENHANCED CGA GENERATION WITH MULTITHREADING ... 172
APPENDIX VII: ENHANCED CGA SIGNATURE GENERATION AND VERIFICATION ... 195
APPENDIX VIII: CGA SIGNATURE GENERATION (RSA-3072) ... 246
APPENDIX IX: SAMPLE MAKE FILE ... 254
xii
LIST OF TABLES
Table 2.1 National Institute of Standards and Technology (NIST) Key Length Comparison (“Comparison of key length (NIST)”, n.d.) 23 Table 2.2 Performance And Recommendation for Using CGA Generation
Algorithm (RSA-1024) 24
Table 2.3 Factors Affecting Performance of CGA Generation Algorithm
and Possible Improvements 26
Table 2.4 Possible Attacks on A Network or Node that Uses CGAs 30 Table 2.5 Comparison of RSA and ECC for CGA Signature on a Nokia 800
(N800) In Seconds (Cheneau et al., 2010) 35
Table 2.6 Comparison of RSA, DSA and MFFS (Castelluccia, 2004) 36 Table 2.7 Best Cryptanalytic Method for Attacking Common Public Key
Cryptosystems 37
Table 2.8 Properties of Cryptographic Hash Functions 39
Table 2.9 Computational Cost and Storage Requirements of W-OTS
Scheme (Becker 2008; Buchmann et al., 2009) 41
Table 2.10 Different Values for Parameters of W-OTS (Becker 2008;
Buchmann et al., 2009) 43
Table 2.11 Computational and Storage Requirements of MSS (Becker, 2008) 48 Table 3.1 Values for Three Factors that Determine Overall Value of sec 63 Table 3.2 Performance (in µs) for Different Hash Functions (256-bit digest) 74 Table 3.3 Performance (in µs) for Different Values of w 75 Table 5.1 Performance of Original CGA Generation Algorithm for Different
sec 100
Table 5.2 Performance of Enhanced vs Original CGA Generation Algorithm 102 Table 5.3 Performance of Enhanced vs Original CGA Verification
Algorithm 107
Table 5.4 Performance of Enhanced vs Original CGA Key Generation
Algorithm 108
xiii
Table 5.5 Performance of Enhanced vs Original CGA Signature Generation
Algorithm 108
Table 5.6 Performance of Enhanced vs Original CGA Signature
Verification Algorithm 109
Table 5.7 Data for Enhanced vs Original CGA Algorithms 111
xiv
LIST OF FIGURES
Figure 1.1 Indirect and Direct Routing in MIPv6 (Johnson et al., 2004) 2 Figure 1.2 Details of the Route Optimization (RO) Procedure (Johnson et al.,
2004) 3
Figure 1.3 Research Approach 10
Figure 2.1 SEND Protocol in TCP/IP Stack 14
Figure 2.2 Cryptographically Generated Address (CGA) 14
Figure 2.3 CGA Signature for Authentication of BU Message (Li et al.,
2009) 16
Figure 2.4 CGA Generation Algorithm (Aura, 2005) 19
Figure 2.5 CGA Parameters Data Structure (Aura, 2005) 20
Figure 2.6 CGA Verification Algorithm (Aura, 2005) 21
Figure 2.7 CGA Signature Generation Algorithm (Aura, 2005) 22 Figure 2.8 CGA Signature Verification Algorithm (Aura, 2005) 23
Figure 2.9 W-OTS Scheme (Buchmann et al., 2009) 42
Figure 2.10 Merkle Signature Scheme (MSS) (Becker, 2008; Buchmann et al.,
2009) 46
Figure 2.11 MSS Key Generation (Becker, 2008; Buchmann et al., 2009) 47 Figure 2.12 MSS Signature With Authentication Path (𝒂𝟎, … , 𝒂𝒉−𝟏) And The
Path For Verification (𝒑𝟎, … , 𝒑𝒉) (Becker, 2008; Buchmann et al.,
2009) 47
Figure 3.1 Cross-compilation 56
Figure 3.2 Scratchbox Login and ARMEL Target 57
Figure 3.3 Cross-compilation Using Scratchbox and QEMU 57
Figure 3.4 N900 58
Figure 3.5 Using the System Monitor Utility To Monitor CPU Usage 60
Figure 3.6 Enhanced CGA Generation Algorithm 66
xv
Figure 3.7 Method 1 68
Figure 3.8 Method 2 69
Figure 3.9 Enhanced CGA Verification Algorithm 71
Figure 3.10 Enhanced CGA Signature Generation Algorithm 77 Figure 3.11 Enhanced CGA Signature Verification Algorithm 78
Figure 3.12 Enhanced CGA Parameters Data Structure 79
Figure 4.1 Examples of Data Types and Structures 83
Figure 4.2 Running application on N900 90
Figure 4.3 Testing Enhanced CGA Generation 91
Figure 4.4 Testing Enhanced CGA Verification 92
Figure 4.5 Testing the Enhanced CGA Signature– Part 1 93
Figure 4.6 Testing the Enhanced CGA Signature– Part 2 94
Figure 4.7 Testing the Enhanced CGA Signature– Part 3 95
Figure 5.1 Comparison of Different Hash Functions Used to Calculate
Hash2 99
Figure 5.2 CGA Generation for Different Levels of Computational Security 101 Figure 5.3 Percentiles of Performance Data for Enhanced CGA Generation
Algorithm 103
Figure 5.4 Performance of Multi-threaded CGA Generation Algorithm (on
Multicore Architecture i) 105
Figure 5.5 Performance of Multi-threaded CGA Generation Algorithm (on
Multicore Architecture ii) 106
Figure 5.6 Four Stages of Handoff Procedure (Xie et al., 2007) 110
xvi
LIST OF ABBREVIATIONS
ARMEL Advanced RISC (Reduced Instruction Set Computer) Machines EmuLator
BA Binding Acknowledgment
BAN Burrows–Abadi–Needham
BU Binding Update
CGA Cryptographically Generated Address
CN Correspondent Node
CoA Care-of Address
CPU Central Processing Unit
CS-CGA Compact and Secure Cryptographically Generated Addresses DAD Duplicate Address Detection
DoS Denial of Service
DSA Digital Signature Algorithm ECC Elliptic Curve Cryptography
ECDSA Elliptic Curve Digital Signature Algorithm ERO Enhanced Route Optimization
ECRYPT European Network of Excellence in Cryptology
GB Gigabyte
GCC GNU Compiler Collection
GHz Gigahertz
GNU GNU’s Not Unix
GPU Graphics Processing Unit
HAVAL HAshing algorithm with VAriable Length HIP Host Identity Protocol
HMAC Hash Message Authentication Code
HoA Home Address
IETF Internet Engineering Task Force IID Interface IDentifier
IPsec/IKE Internet Protocol SECurity / Internet Key Exchange
KiB Kibibyte
LD-OTS Lamport-Diffie One-time Signature
L3 Layer 3
N900 Nokia 900
MB Megabyte
MD Message Digest
MFFS Modified Feige-Fiat-Shamir
MHz Megahertz
MIPv6 Mobile IPv6
MN Mobile Node
MSS Merkle Signature Scheme
NA Neighbor Advertisement
NIST National Institute of Standards and Technology
OS Operating System
OTS One-time Signature
POSIX Portable Operating System Interface
xvii RFC Request For Comment
RNG Random Number Generation
RO Route Optimization
RR Return Routability RSA Rivest-Shamir-Adelman SDK Software Development Kit SEND Secure Neighbor Discovery SHA Secure Hash Algorithm SSL Secure Socket Layer
SVO Syverson and Van Oorschot
TB-CGA Time-Based Cryptographically Generated Addresses TCP/IP Transmission Control Protocol / Internet Protocol
TB Terabyte
TLS Transport Layer Security TMTO Time-Memory Trade-Off W-OTS Winternitz One-Time Signature
xviii
LIST OF SYMBOLS
𝒂𝒊 Node on Authentication Path
𝒃𝒊 ith Bit String W-OTS Signature Generation
c Checksum
C The Computational Capacity of a Node
d Hash Digest
f One-way Function
g Cryptographic Hash Function h Height of Merkle tree
KBM Binding Management Key
KCN Correspondent Node Key
KR Private Key
KU Public Key
m Minimal Security Level
𝒎𝒊 The Number of modifiers Searched by Thread i
𝒎𝒕𝒐𝒕𝒂𝒍 The Total Number of modifiers Searched Before a Match is Found n Length (in bits) of Hash Digest
n[j, i] ith Node of Merkle Tree at Height j N Number of Keys Pairs
𝑶 Big-O Notation
PA The Perceived Probability of an Attack 𝒑𝒊 Node of Verification Path
s Index of OTS Key Pair Used to Generate OTS Signature sec Security Parameter
t Third Variable Calculated as Part of W-OTS Key Generation t1 First Variable Calculated as Part of W-OTS Key Generation t2 Second Variable Calculated as Part of W-OTS Key Generation 𝑻𝑪𝑮𝑨 Total Time Taken by CGA Algorithm
TCoA_C Time Taken for CoA Configuration
TE The Duration for Which a Node is Expected to Use an Address.
THA_R Time Taken for Home Agent Registration
𝑻𝒊 Time Taken by Step i (that is executed by a thread in parallel) TMD Time Taken for Movement Detection
TRO Time Taken for Route Optimization
𝑻𝒔 The Total Time Taken by All the Sequential Steps w Number of Bits to be Signed Simultaneously
X Signature Key
𝒙𝒊 ith Bit String of Signature Key X
Xs OTS Signature Key Used to Generate Signature 𝝈s
𝒙
̅ Sample Mean
Y Verification Key
𝒚𝒊 ith Bit String of Verification Key Y
Ys OTS Verification Key Used to Verify Signature 𝝈 s
Population Mean
xix
𝝈 Signature
𝝈𝒊 ith Bit String of Signature 𝝈
𝝈𝑶𝑻𝑺 W-OTS Signature
𝝈𝑺 MSS Signature
1
CHAPTER ONE INTRODUCTION
1.1 INTRODUCTION
Mobile Internet Protocol version 6 (MIPv6) was introduced in 2004 (RFC 3775) as an improvement to the Mobile IPv4 (MIPv4). The main aim of the protocol was to enable nodes to remain reachable while moving around the IPv6 Internet – i.e. mobility (Johnson et al., 2004). Mobility is a vital feature for any modern networking protocol given the dramatic increase in the number of portable devices. MIPv6 also boasts several other advantages such as improved support for security and efficiency.
By definition, mobility means that a mobiles node (MN) can move from its home network to a foreign network and still maintain existing connection to a correspondent node (CN). This process, of a node moving from one network to another network, is called handover or handoff (Dunmore & Pagtzis, 2005). During handoff, there is an interval when a node is disconnected from its home network and has not yet connected to the new or foreign network. This duration, called the handoff delay is detrimental to quality of service (QoS) because a node has no point of attachment during this time.
In addition to improved support for mobility, MIPv6 has one more very important advantage over MIPv4. It allows a MN to exchange packets directly with a CN. This is known as Direct Routing and is much more efficient than indirect routing as illustrated in Figure 1.1. Direct routing requires the Route Optimization (RO) procedure to be completed. The details of this procedure are shown in Figure 1.2.
2
Foreign Network Indirect Routing
Direct Routing
(requires completion of Route Optimization procedure)
Figure 1.1 Indirect and Direct Routing in MIPv6 (Johnson et al., 2004)
The most important message in RO is the Binding Update (BU) message. This message is sent by a MN to its CN. It contains the MN’s home address (HoA) and its current care-of address (CoA). BU messages can be exploited by an adversary to launch several types of attacks on a MIPv6 network. Authenticating BU messages is vital for the security of MIPv6 networks.
Correspondent Node (CN)
Mobile Node (MN) Router Care-of address:
2005::1111:bbbb:5555:3333 Foreign Network
Home Agent (HA)
Home Agent (HA) Care-of address:
2005::1111:bbbb:5555:3333 Home Network
Home Network
Correspondent Node (CN)
Mobile Node (MN) Router
3
MN HA CN
Generate random Home Init Cookie
HoTI (Home Init
Cookie)
Generate KCN
(160-bit key generated for each MN)
Generate random Care- of Init Cookie
CoTI (Care-of Init Cookie)
HoT (Home Init Cookie, Home Keygen Token,
Home nonce index)
Generate a 64-bit number called Home nonce and stored it in an indexed list (index:
Home nonce index).
Generate Home Keygen Token
= First ( 64, HMAC_SHA1(KCN, HoA ||Home nonce || 0) )
Generate Binding Management KeyKBM= SHA1 ( Home Keygen Token|| Care-of Keygen Token)
CoT (Care-of Init Cookie, Care-of
Keygen Token, Care-of nonce
index)
Generate a 64-bit number called Care-of nonce and stored it in an indexed list (index:
Care-of nonce index).
Generate Care-of Keygen Token
= First ( 64, HMAC_SHA1(KCN, CoA ||
Care-of nonce||1) ) Generate Auth_data
= First (96,
HMAC_SHA1(KBM, CoA ||
final dest ||
mobility hdr ))
BU (Auth_data, Home nonce index, Care-of nonce index)
Generate Binding Management Key KBM
= SHA1 ( Home Keygen Token|| Care- of Keygen Token) &Verify BU
BA (Auth_data)
Figure 1.2 Details of the Route Optimization (RO) Procedure (Johnson et al., 2004)
4
When MIPv6 was being designed, traditional approaches for providing authentication were rejected by the Internet Engineering Task Force (IETF). This was because these approaches relied on an end-to-end security infrastructure or a pre- existing relationship between the two communicating nodes (Sun et al., 2010). This is not a realistic assumption during handoff in a global MIPv6 network. Instead, IETF adopted an “infrastructureless” authentication mechanism called Return Routability (RR) (Sun et al., 2010). It consists of the four shaded messages shown in Figure 1.2.
RR is a very straightforward and lightweight authentication mechanism (relying on HMAC, SHA-1, Cookies, and Tokens) and is ideal for widespread adoption (Johnson et al., 2004; Arkko et al., 2007).
Unfortunately, a number of attacks can be launched on a MIPv6 network based on weaknesses in RR (Sun et al., 2010). Malicious BU messages can be used to launch off-path (such as stealing attacks, reflection and flooding attacks, denial of service) and on-path attacks (such as man-in-the-middle attacks on the BU message, denial of service) (Sun et al., 2011; Arkko, 2007). RR should be replaced by a strong mechanism. The best approach is to use CGA-based authentication.
Cryptographically Generated Addresses (CGA) are IPv6 addresses for which the Interface IDentifier(IID) is generated by computing a cryptographic one-way hash function of the node’s public key and auxiliary parameters (Oh and Chea, 2007).
Using CGAs in a protocol for authenticating BU messages was first proposed by Shea
& Roe (2001). Their recommendation was based on the fact that CGAs are able to provide strong authentication without requiring nodes to share any common information or security infrastructure (Caicedo et al., 2009). CGAs gained some recognition after being included in IPv6 but their potential as mechanisms for
5
providing strong authentication has yet to be explored in detail (Minoli and Kouns, 2009).
1.2 PROBLEM STATEMENT AND ITS SIGNIFICANCE
It is widely acknowledged that any protocol that provides CGA-based authentication must have the following features (Soliman, 2004):
i. the MN’s HoA and CoA are CGAs
ii. the MN signs the BU message by generating a CGA signature, and iii. the CN verifies the CGA signature on the BU message.
If these features are included, then majority of the on-path and off-path attacks can be prevented. It is for this reason that CGAs are included in the latest enhancement to MIPv6 called Enhanced Route Optimization (ERO) (Arkko et al., 2007).
Although ERO is considered a secure protocol, it is computationally expensive especially for the low-end nodes like the CN and MN (Kuang et al., 2008). In fact, the cost of some of the operations (e.g. generating a CGA signature and verifying a CGA signature) are so large that they can be exploited by an adversary to launch a denial of service attack (Kuang et al., 2008). Most studies identify the following three CGA algorithms as the most computationally expensive:
i. CGA Generation algorithm
ii. CGA Signature Generation algorithm iii. CGA Signature Verification algorithm
According to Elgoarany and Eltoweissy (2007) delays and implementation issues are major impediments to any new authentication protocol for MIPv6. To this end, a few less-expensive CGA-based protocols have also been proposed but their