Ad Hoc Networks Security Instructor: Carlos Pomalaza-Ráez Fall 2003 University of Oulu, Finland
Ad Hoc Networks Security Instructor: Carlos Pomalaza-Ráez Fall 2003 University of Oulu, Finland
Introduction to Cryptography
The idea is to protect data by transforming into a representation from which is hard to recover. This provide us with:
Confidentiality – only the sender and the receiver should know the message content
Authentication – sender and receiver can confirm the identity of each other
Integrity – sender and receiver can detect any alteration of the message
Non-repudiation – sender can not deny having created the message
Freshness – message is recent and not a replay
Unless a message is properly protected unfriendly “agents” can capture or see it as it moves across the network and,
Insert messages into the connection
Impersonate – fake (spoof) source address
Hijack – take over connection a replacing the sender or receiver
Denial of service – by, for example, overloading the resources
Private (Symmetric) – Key systems
In these systems the message M is encrypted using a key e which is known only to the sender and the receiver. To encrypt the message compute X = E(M, e), E being the encryption function. To decrypt X compute M = D(X, d), where d is the decryption key corresponding to e. There is usually a simple relationship between e and d. A widely known secret-key system is DES (Data Encryption Standard) M encryption
algorithm decryption
algorithm e – encryption key d – decryption key M = D(X, d) Alice X = E(M, e) Bob Unfriendly agent Eve
Public (Asymmetric)– Key systems
In these systems the message M is encrypted using a key e which is public. To encrypt the message compute X = E(M, e), E being the encryption function. To decrypt X compute M = D(X, d), where d is the decryption key corresponding to e. Knowing e doesn’t help anyone to discover the decryption key d. M encryption
algorithm decryption
algorithm e – public encryption key d – private decryption key M = D(X, d) Alice X = E(M, e) Bob Unfriendly agent Eve
RSA – A Public-key Crypto-System
R.L. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Comm. of ACM, 21 (2), pp. 120-126, Feb. 1978. RSA stands for its inventors Ron Rivest, Adi Shamir, and Len Ademan. We assume here that message is broken into parts of the right size, e.g. 1024 bits.
Choosing Keys
Choose two large prime numbers p, q (e.g., 512 bits each)
Compute n = pq, z = (p-1)(q-1) = Ф(n)
Choose e, (e
RSA: Encryption - Decryption
Hash Algorithms
A basic tool for cryptography is a secure hash algorithm. Given a variable length message x, a secure hash algorithm computes a function h(x) which has a fixed and often smaller number of bits. It is usually not possible to recover x from its hash function. Desirable properties of a secure hash function are:
A hash function h(x) is one-way if given y it is hard to find x such that h(x) = y
A hash function h(x) is weakly collision-free if given a message x1 it is hard to find another message x2 such that h(x1) = h(x2)
A hash function h(x) is strong collision-free if it is hard to find any pair of messages x1, x2 such that h(x1) = h(x2)
An important property of secure hash functions, like any hash function, is that they should uniformly cover their range. That is, for a uniform distribution of the inputs, the output probabilities from the hash function should be uniform.
Authentication via Digital Signatures
Similar to handwritten signatures Dear Alice, Bob Bob’s private key Ready for Transmission Alice decrypts Bob’s message using Bob’s public key
If decrypted message matches the message, Alice knows that the signed message could only have come from Bob
Signing the entire document/message is computationally expensive Original Text Text encrypted with Bob’s private key Method I:
Bob encrypts entire message with his private key; this is Bob’s digital signature
Bob send both the message and his digital signature
Authentication via Digital Signatures
Method II:
Compute a hash on the document/message
The hash, also called a message digest, is much smaller than the document, resembles a CRC (Cyclic Redundancy Check)
Use private key to encrypt only the message digest
Encrypted digest is commonly called a digital signature
Computationally inexpensive
Send both the document and the digitally signed message digest
At receiver
Hash the document → MDA and decrypt the digital signature → MDB
If MDA = MDB then receiver knows that:
the identity of sender correctly matches the advertiser of the public key (authentication)
that the document hasn’t been tampered with (data integrity)
Digital Signature - Signed message digest
Bob sends digitally signed message Original Long Message Fixed-size message digest Encrypted message digest Bob’s private key Send to Alice Alice verifies signature and integrity of digitally signed message Many to one hash function Fixed-size message digest Original Long Message Many to one hash function Encrypted message digest Bob’s public key Fixed-size message digest Compare
Non-Repudiation via Digital Signatures
Fixed-size message digest Original Long Message Many to one hash function Encrypted message digest Bob’s public key Fixed-size message digest Compare MDA MDB Digital Signatures provide authentication, integrity, and non-repudiation
At receiver, if MDA = MDB then receiver knows that:
Only the sender’s private key could have created this signature (Non-repudiation & Authentication)
Sender can’t deny sending message
One-Way Hash Chains
Construction
Pick random rN and a public one-way function F
ri = F(ri+1)
Secret value: rN
Public value: r0 F r8 r5 r6 r7 F F F r4 Properties
Use in reverse order of construction, i.e. r1, r2,…, rN
It is not feasible to derive ri from rj (j
Message Authentication Codes (MAC)
Bob Alice Compute C = MAC(K,M) { M | C } It’s Alice not Alice Yes No Compute C’ = MAC(K,M) C = C’ Alice and Bob know in advance K and the MAC function It is a code – MAC(K,M)
Calculated by some function MAC that requires little computation
Inputs are the message M to be sent and K, the symmetric key known only by the two parties
The code is appended to each packet, i.e. {M, MAC(K,M)}
Unicast Source Authentication
Bob Dave Carol Alice Ka-b {M|MAC(Ka-b, M)} Ka-b Ka-c Ka-d M is duplicated and sent separately to each intended receiver with it a different MAC
High overhead and consumes network resources Internet {M|MAC(Ka-c, M)} {M|MAC(Ka-d, M)}
Multicast Source Authentication
Internet Bob Dave Carol Alice Ka {M|MAC(Ka, M)} Ka Ka Ka Ka is known to all receivers. Any receiver can forge a packet
Low overhead and less network resources when compared with unicast method
TESLA
Timed Efficient Stream Loss-Tolerant Authentication Uses symmetric key cryptography
Asymmetric key cryptography via time
Based on initial loose time synchronization
MAC is attached to each packet
Delayed-disclosure of keys MAC(Ki,M) M time ti-1 ti ti+1 F(Ki) Authentic Commitment Ki is disclosed 1- Verify Ki 2- Verify MAC 3- M is authentic A. Perrig, R. Canetti, J.D. Tygar, D. Song, “Efficient authentication and signing of multicast streams over lossy channels,” IEEE Symposium on Security and Privacy, May 2000.
TESLA – Sender Setup
Alice time interval i -1 interval i interval i +1 interval N Ki+1 Ki Ki-1 KN Use F' to derive the key to compute MAC K‘i= F’(Ki) K’i+1 K’i K’i-1 K’N F’ F’ F’ F’ Break time in intervals of same duration
Determine key chain length N, picks the last key KN randomly
Using a One Way Pseudo Random Function F compute Ki = F(Ki+1), assign one key to each interval Key generation
TESLA – Authentication
Ki+1 Ki Ki-1 K’i+1 K’i K’i-1 F’ F’ F’ Mi-1, Ki-2 MAC(K’i-1, Di-1) Di-1 Mi , Ki-1 MAC(K’i, Di) Di Mi+1, Ki MAC(K’i+1, Di+1) Di+1 Pi-1 Pi Pi+1 authenticated authenticated after reception of Pi+1 not yet authenticated When the receiver gets packet Pi,it can not verify the MAC since it does not yet know Ki from which it can compute K’i
Packet Pi+1 discloses Ki and allows the receiver to:
verify that Ki is correct, e.g., F(Ki) = Ki-1
compute K’i and check the authenticity of packet Pi by verifying the MAC of Pi
TESLA – Dynamic Packet Rates
Dj K’i Dj+1 K’i+2 i i +5 i +4 i +3 i +2 i +1 Dj+3 K’i+3 Dj+4 K’i+3 Dj+4 K’i+5 Mj+4 Ki+1 Mj+3 Ki-1 Mj+2 Ki-1 Mj Ki-4 Mj+1 Ki-2 TΔ d=4 The MAC key and the disclosed key depend of the time interval
The authentication key of Pj is Ki which is disclosed by packets sent in interval (i + d )
In this example packet Pj+4 discloses key Ki+1 which allows the receiver to compute Ki and to authenticate packet Pj Pj Pj+2 Pj+1 Pj+3 Pj+4
Attacks to Ad-Hoc Networks
Passive
Only eavesdrop
Threats against privacy/anonymity
Active
Injects packets and eavesdrops
Characterized based on the number of controlled nodes in the network
Routing disruption attacks
Causes legitimate data packets to be routed dysfunctionally (e.g., routing loop, black hole, gray hole, detour, partition)
Resource consumption attacks
Consumes valuable network resources or node resources (e.g., injecting data packets, injecting control packets)
Comments