draft-ietf-csi-hash-threat-06.txt   draft-ietf-csi-hash-threat-07.txt 
Network Working Group A. Kukec Network Working Group A. Kukec
Internet-Draft University of Zagreb Internet-Draft University of Zagreb
Intended status: Standards Track S. Krishnan Intended status: Standards Track S. Krishnan
Expires: August 16, 2010 Ericsson Expires: August 16, 2010 Ericsson
S. Jiang S. Jiang
Huawei Technologies Co., Ltd Huawei Technologies Co., Ltd
February 12, 2010 February 12, 2010
SEND Hash Threat Analysis SEND Hash Threat Analysis
draft-ietf-csi-hash-threat-06 draft-ietf-csi-hash-threat-07
Abstract Abstract
This document analysis the use of hashes in SEND, possible threats This document analysis the use of hashes in SEND, possible threats
and the impact of recent attacks on hash functions used by SEND. and the impact of recent attacks on hash functions used by SEND.
Current SEND specification [rfc3971] uses the SHA-1 [sha-1] hash Current SEND specification [rfc3971] uses the SHA-1 [sha-1] hash
algorithm and X.509 certificates [rfc5280] and does not provide algorithm and X.509 certificates [rfc5280] and does not provide
support for the hash algorithm agility. The purpose of the document support for the hash algorithm agility. The purpose of the document
is to provide analysis of possible hash threats and to decide how to is to provide analysis of possible hash threats and to decide how to
encode the hash agility support in SEND. encode the hash agility support in SEND.
skipping to change at page 3, line 17 skipping to change at page 3, line 17
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Impact of collision attacks on SEND . . . . . . . . . . . . . 6 3. Impact of collision attacks on SEND . . . . . . . . . . . . . 6
3.1. Attacks against CGAs in stateless autoconfiguration . . . 6 3.1. Attacks against CGAs in stateless autoconfiguration . . . 6
3.2. Attacks against X.509 certificates in ADD process . . . . 7 3.2. Attacks against X.509 certificates in ADD process . . . . 7
3.3. Attacks against the Digital Signature in the RSA 3.3. Attacks against the Digital Signature in the RSA
Signature option . . . . . . . . . . . . . . . . . . . . . 8 Signature option . . . . . . . . . . . . . . . . . . . . . 8
3.4. Attacks against the Key Hash field in the RSA 3.4. Attacks against the Key Hash field in the RSA
Signature option . . . . . . . . . . . . . . . . . . . . . 8 Signature option . . . . . . . . . . . . . . . . . . . . . 8
4. Support for the hash agility in SEND . . . . . . . . . . . . . 9 4. Support for the hash agility in SEND . . . . . . . . . . . . . 9
5. Security Considerations . . . . . . . . . . . . . . . . . . . 10 5. Security Considerations . . . . . . . . . . . . . . . . . . . 11
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.1. Normative References . . . . . . . . . . . . . . . . . . . 11 6.1. Normative References . . . . . . . . . . . . . . . . . . . 12
6.2. Informative References . . . . . . . . . . . . . . . . . . 11 6.2. Informative References . . . . . . . . . . . . . . . . . . 12
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14
1. Introduction 1. Introduction
SEND [rfc3971] uses the hash algorithm in different ways. It uses SEND [rfc3971] uses the SHA-1 hash algorithm to generate
the SHA-1 hash algorithm to generate Cryptographically Generated Cryptographically Generated Addresses (CGA) [rfc3972], the contents
Addresses (CGA) [rfc3972], the contents of the Key Hash field and the of the Key Hash field and the Digital Signature field of the RSA
Digital Signature field of the RSA Signature option. It also uses a Signature option. It also uses a hash algorithm (SHA-1, MD5, etc.)
hash algorithm (SHA-1, MD5, etc.) within the digital signature in the within the digital signature in X.509 certificates [rfc5280] for the
X.509 certificates [rfc5280] for the router authorization in the router authorization in the Authorizaton Delegation Discovery (ADD)
Authorizaton Delegation Discovery (ADD) process. process.
There is a great variaty of hash function, but only MD5 and SHA-1 are There is a great variaty of hash functions, but only MD5 and SHA-1
in the wide use. They both derive from MD4, which has been well are in the wide use, which is also the case for SEND. They both
known for its weaknesses. First hash attacks affected the derive from MD4, which has been well known for its weaknesses. First
compression function of MD5, while the latest hash attacks against hash attacks affected the compression function of MD5, while the
SHA-1 delivered colliding hash in significantlly smaller number of latest hash attacks against SHA variants delivered colliding hashes
rounds compared to the brute force attack number of rounds in significantlly smaller number of rounds compared to the brute
[sha1-coll]. Attacks against X.509 certificates improved as well, force attack number of rounds [sha1-coll]. Apart from the
and researchers demonstrated colliding certificate with MD5 hash, aforementioned hash attacks, researchers also demonstrated attacks
both for the same and different identities [x509-coll]. against X.509 certificates. They demonstrated colliding X.509
certificates with MD5 hash, both with the same and different
distinguished names [new-hashes] [x509-coll].
Depending on the way of use of hash algorithm, Internet protocol can Depending on the way how the Internet protocol uses the hash
be affected by the weakness of the underlaying hash function. This algorithm, Internet protocol can be affected by the weakness of the
document analyzes uses of hash algorithms in SEND, possible weakness underlaying hash function. This document analyzes uses of hash
that hash attacks could introduce to SEND, and possible ways to make algorithms in SEND, possible vulnerabilities that hash attacks could
SEND resistant to such attacks. introduce to SEND, and offers suggestions on how to make SEND
resistant to such attacks.
2. Terminology 2. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [rfc2119]. document are to be interpreted as described in RFC 2119 [rfc2119].
3. Impact of collision attacks on SEND 3. Impact of collision attacks on SEND
Due to the hash attacks demonstrated on the aforesaid hash algorithms Due to the hash attacks demonstrated on the aforesaid hash algorithms
a study was performed to assess the threat of these attacks on the a study was performed to assess the threat of these attacks on the
cryptographic hash usage in internet protocols [RFC4270]. This cryptographic hash usage in Internet protocols. This document
document analyzes the hash usage in SEND following the recommended analyzes the hash usage in SEND following the recommended approach
approach [rfc4270] [new-hashes]. [rfc4270] [new-hashes].
Basic cryptographic properties of a hash function are that it is both Basic cryptographic properties of a hash function are that it is both
one-way and collision free. There are two attacks against the one- one-way and collision free. There are two attacks against the one-
way property, the first-preimage attack and the second-preimage way property, the first-preimage attack and the second-preimage
attack. In the first-preimage attack, given a knowledge of a attack. In the first-preimage attack, given a knowledge of a
particular hash value h, an attacker finds an input message m such particular hash value h, an attacker finds an input message m such
that hash(m) = h. The second-preimage attack deals with fixed that hash(m) = h. The second-preimage attack deals with fixed
messages. Given a knowledge of a fixed value m used as the input messages. Given a knowledge of a fixed value m used as the input
message to the hash function, an attacker finds a different value m' message to the hash function, an attacker finds a different value m'
that yields hash(m)=hash(m'). Supposing that the hash function that yields hash(m)=hash(m'). Supposing that the hash function
produces an n-bit long output, since each output is equally likely, produces an n-bit long output, since each output is equally likely,
an attack takes an order of 2^n operations to be successful. Due to an attack takes an order of 2^n operations to be successful. Due to
the birthday attack, if the hash function is supplied with a random the birthday attack, if the hash function is supplied with a random
input, it returns one of the k equally-likely values, and the number input, it returns one of the k equally-likely values, and the number
of operations can be reduced to the number of 1.2*2^(n/2) operations. of operations can be reduced to the number of 1.2*2^(n/2) operations.
Attack against the collision-free property deals with two fixed Attack against the collision-free property deals with two fixed
messages, both produced by an attacker. Attacker produces two messages, both produced by an attacker. What happens is that the
different messages, m and m', such that hash(m)=hash(m'). Up to attacker produces two different messages, m and m', such that
date, all demonstrated attacks are attacks against a collision-free hash(m)=hash(m'). Up to date, all demonstrated attacks are attacks
property. Attacks against the one-way property are not yet feasible against a collision-free property. Attacks against the one-way
[rfc4270]. property are not yet feasible [rfc4270].
The strength of Internet protocol does not have to be necessarily The strength of Internet protocol does not have to be necessarily
affected by the weakness of the underlaying hash function. The affected by the weakness of the underlaying hash function. The
appropriate way of use of the hash algorithm will keep the protocol appropriate way of use of the hash algorithm will keep the protocol
immune, no matter of the hash algorithm weaknesses. Out of many immune, no matter of the hash algorithm weaknesses. Out of many
possible hash algorithm uses, such as non-repudiable digital possible hash algorithm uses, such as non-repudiable digital
signatures, certificate digital signatures, message authentication signatures, certificate digital signatures, message authentication
with shared secrets, fingerprints, only the first two can introduce with shared secrets, fingerprints, only the first two can introduce
weaknesses to the Internet protocol [rfc4270]. The rest of the weaknesses to the Internet protocol [rfc4270]. The rest of the
section analyzes the impact of hash attacks, mainly collision section analyzes the impact of hash attacks, mainly collision
attacks, on SEND by the cases of use. Through our analysis, we also attacks, on SEND by the cases of use. Through our analysis, we also
discuss whether we should support the hash agility in SEND. discuss whether we should support the hash agility in SEND.
3.1. Attacks against CGAs in stateless autoconfiguration 3.1. Attacks against CGAs in stateless autoconfiguration
Hash functions are used in the stateless autoconfiguration process Hash functions are used in the stateless autoconfiguration process
that is based on CGAs. Impacts of collision attacks on current uses which is based on CGAs. Impacts of collision attacks on current uses
of CGAs and the CGA hash agility are analyzed in the update of the of CGAs and the CGA hash agility are analyzed in the update of the
CGA specification [rfc4982]. CGAs provide the proof-of-ownership of CGA specification [rfc4982]. CGAs provide the proof-of-ownership of
the private key corresponding to the public key used to generate the the sender's private key corresponding to the public key used to
CGA. The collision attack against the CGA assume that attacker generate the CGA. Simply stated, their main purpose is to assure
generates two different sets of CGA Parameters that result in the that the sender of the message is the same as the sender of the
same hash value. Since CGAs do not deal with the non-repudiation previous message. As such, CGAs do not deal with the non-repudiation
feature, and both sets are chosen by the attacker, this attack is not feature. The collision attack against the CGA assumes that the
useful in any real-world scenario. CGA-based protocols, including attacker generates two different, colliding sets of CGA Parameters
SEND, are not affected by the recent collision attacks. If pre-image that result in the same hash value. Since CGAs do not deal with the
attacks were feasible, an attacker would find colliding CGA non-repudiation feature, and both CGA Parameters sets are chosen by
Parameters for the victim's CGA, and produce the Key Hash field and the attacker itself, this attack does not introduce any
the Digital Signature field afterwards using the new public key. vulnerabilities to SEND. If pre-image attacks were feasible, an
Since the strength of all hashes in SEND depends on the strength of attacker would find colliding CGA Parameters for the victim's CGA,
the CGA, the pre-image attack is potentially dangerous, but it is not and produce the Key Hash field and the Digital Signature field
yet feasible. afterwards using the new public key. Since the strength of all
hashes in SEND depends on the strength of the CGA, the pre-image
attack is potentially dangerous, but it is not yet feasible.
3.2. Attacks against X.509 certificates in ADD process 3.2. Attacks against X.509 certificates in ADD process
Another use of hash functions is for the router authorization in the Another use of hash functions is for the router authorization in the
ADD process. Router sends to a host a certification path, which is a ADD process. Router sends to a host a certification path, which is a
path between a router and the host's trust anchor, consisting of path between a router and the host's trust anchor, consisting of
X.509 certificates. Researchers demonstrated attacks against X.509 X.509 certificates. Researchers demonstrated attacks against X.509
certificates with MD5 signature in 2005 [new-hashes] and in 2007 certificates with MD5 signature in 2005 [new-hashes] and in 2007
[x509-coll]. In 2005 researchers constructed colliding certificates [x509-coll]. In 2005 researchers constructed colliding certificates
with the same distinguished name, different public keys, and with the same distinguished name, different public keys, and
identical signatures, based on different public keys. The problem identical signatures. Potential problem for the attacker here is
for the attacker is that two certificates with the same identity are that two certificates with the same identity can be easily revealed
not actually useful in real-world scenarios, because the by the appropriately configured Certification Authority that does not
Certification Authority can take care of not allowing to provide such allowe to provide two certificates with the same identities. Human-
two certificates. In addition, attacks against the human-readable readable fields significantly complicate the attack. In case of the
fields demand much more effort than the attacks against non human- identity field an attacker is faced with the problem of the
readable fields, such as a public key field. In case of the identity prediction and the generation of the two different, false but
field, an attacker is faced with the problem of the prediction and meaningful identities, which at the end might be revealed by the
the generation of the false but meaningful identity data, which at Certification Authority. Thus, although theoretically possible,
the end might be revealed by the Certification Authority. Thus, in real-world circumstances such as the context of the human-readable
practice, there is a very low probability that collision attacks fields, make these attacks with colliding certificates with the same
affect non human-readable parts of the certificate. In 2007 identities impossible. In 2007 researchers demonstrated colliding
researchers demonstrated colliding certificates which differ in the certificates which differ in the identity data and in the public key,
identity data and in the public key, but still result in the same but still result in the same signature value. Even in this case, the
signature value. Even in this case, the real-world scenarios prevent real-world scenarios prevent the hash algorithm weaknesses to
the hash algorithm weaknesses to introduce vulnerabilities of the introduce vulnerabilities to X.509 certificates or to SEND. Even if
certificate or the protocol. Even if an attacker produced such two an attacker produced such two colliding certificates in order to
colliding certificates in order to claim that he was someone else, he claim that he was someone else, he still needs to predict the content
still needs to predict the content of all fields appearing before the of all fields (some of them are human-readable fields) appearing
public key, e.g. the serial number and validity periods. Although a before the public key, e.g. the serial number and validity periods.
relying party cannot verify the content of these fields (each Although a relying party cannot verify the content of these fields
certificate by itself is unsuspicious), the Certification Authority (each certificate by itself is unsuspicious), the Certification
keeps track of those fields and it can reveal the false certificate Authority keeps track of those fields and it can reveal the false
during the fraud analysis. Even though the real-world scenarios make certificate during the fraud analysis. Even though real-world
SEND immune to recent hash attacks introduced through X.509 scenarios make SEND immune to recent hash attacks introduced through
certificates, theoretically they are possible, but only in case of X.509 certificates, theoretically they are possible. Regarding X.509
the human-readable fields. Regarding X.509 certificates in SEND, certificates in SEND, biggest concer are potential attacks against
biggest concer are attacks against the RFC3779 IP address extension the RFC3779 IP address extension which would enable the bogus router
which would enable the bogus router to advertize the changed IP to advertize the changed IP prefix range (if the IP prefix range
prefix range, if the IP prefix range used, although, not broader than used), although, not broader than the prefix range of the parent
the prefix range of the parent certificate in the ADD chain. Adding certificate in the ADD chain. Adding some form of randomness to the
some form of randomness to human-readble data would prevent such such human-readble data such would prevent attacks, which can be
attacks, which can be considered once when the collision attack considered once when the collision attack improve.
improve.
3.3. Attacks against the Digital Signature in the RSA Signature option 3.3. Attacks against the Digital Signature in the RSA Signature option
The computation of the Digital Signature field is described The computation of the Digital Signature field is described
[rfc3971]. It is produced as the SHA-1 hash over the IPv6 addresses, [rfc3971]. It is produced as the SHA-1 hash over the IPv6 addresses,
the ICMPv6 header, the ND message and other fields, e.g. the Message the ICMPv6 header, the ND message and other fields, e.g. the Message
Type Tag and ND options, and signed with the sender's private key. Type Tag and ND options, and signed with the sender's private key.
Private key corresponds to the public key in the CGA parameters Private key corresponds to the public key in the CGA parameters
structure. It is usually authorized through CGAs. The Digital structure. It is usually authorized through CGAs. The Digital
Signature field is vulnerable to recent collision attacks. Possible Signature field the example of the non-repudiation digital singature,
attack on such explicit digital signature is a typical non- and it is vulnerable to recent collision attacks. Possible attacks
repudiation attack. An attacker produces two different messages, m on such explicit digital signature is a typical non-repudiation
and m', where hash(m) = hash(m'). He underlays one of the messages attack in which the attacker produces two different messages, m and
to be signed with the key authorized through CGAs, but uses another m', where hash(m) = hash(m'). He underlays one of the messages to be
message afterwards. However, the structure of at least one of two signed with the key authorized through CGAs, but uses another message
messages in a collision attack is strictly predefined. The previous afterwards. However, the structure of at least one of two messages
in a collision attack is strictly predefined. The previous
requirement makes this collision attack to be much more then the requirement makes this collision attack to be much more then the
simple collision attack, and requires the attacker to know or predict simple collision attack. It requires the attacker to know or predict
the communication context. Theoretically this attack could harm the communication context. Theoretically this attack could harm
SEND, but in real-world situation is extremely hard to achieve it. SEND, but in real-world situation is to achieve it.
3.4. Attacks against the Key Hash field in the RSA Signature option 3.4. Attacks against the Key Hash field in the RSA Signature option
The Key Hash field in the RSA Signature option is a SHA-1 hash of the The Key Hash field in the RSA Signature option is a SHA-1 hash of the
public key from the CGA Parameters structure in the CGA option. It public key from the CGA Parameters structure in the CGA option. It
is a fingerprint that provides the integrity protection. is a fingerprint that provides the integrity protection.
Fingerprints are generally not affected by the collision attacks Fingerprints are generally not affected by the collision attacks
because they involve random data as one of the inputs, which prevents because they involve random data as one of the inputs, which prevents
recent collision attacks. In addition, context of the SEND message recent collision attacks. In addition, context of the SEND message
and the protocol makes this attack unable to introduce new and the protocol makes this attack unable to introduce new
vulnerabilities to SEND. An attacker has to produce both keys, k and vulnerabilities to SEND. An attacker has to produce both keys, k and
k', such that hash(k) = hash(k'). Since the key is authorized k', such that hash(k) = hash(k'). Since the key is authorized
through CGA, and possibily through the certification in the ADD through CGA, and possibily through the certification in the ADD
process, this attack is of no use for the attacker. The pre-image process, this attack is of no use for the attacker. The pre-image
attack against the Key Hash field, if it was possible, would affect attack against the Key Hash field, if it was possible, would affect
SEND since the Key Hash field contains a non human-readable data. SEND since the Key Hash field contains a non human-readable data.
4. Support for the hash agility in SEND 4. Support for the hash agility in SEND
Previous section analyzed that CGAs and fingerprints affected by the Previous section showed that recent hash attacks against CGAs and
collision attacks (Key Hash field of the Send message) do not fingerprints (Key Hash field of the Send message) do not introduce
introduce new vulnerabilities to SEND. Digital signatures in the new vulnerabilities to SEND. Digital signatures in the Digital
Digital Signature field of the SEND message and X.509 certificate Signature field of the SEND message and in the X.509 certificate
theoretically are affected by the recent collision attacks, but the theoretically could introduce new vulnerabilities to SEND, but only
SEND context prevents those attacks of almost any use in the real- in limited circumstances. SEND context prevents those attacks of
world scenarios. However, recent attacks indicate the possibility almost any use in the real-world scenarios.
for the future improved real-world attacks. Researchers advise to
migrate away from currently used hash algorithms. In order to However, recent attacks indicate the possibility for the future
increase the future security of SEND, we suggest the support for the improved real-world attacks. Researchers advise to migrate away from
hash and algorithm agility in SEND. currently used hash algorithms. In November 2007, NIST announced an
opened competition for a new SHA-3 function. The selection of a
winning function will be in 2012. In order to increase the future
security of SEND, we suggest the support for the hash and algorithm
agility in SEND.
o The most effective and secure would be to bind the hash function o The most effective and secure would be to bind the hash function
option with something that can not be changed at all, like option with something that can not be changed at all, like
[rfc4982] does for CGA. It encodes the hash function information [rfc4982] does for CGA. It encodes the hash function information
into addresses. We could decide to use by default the same hash into addresses. We could decide to use by default the same hash
function in SEND as in CGA. The security of all hashes in SEND function in SEND as in CGA. The security of all hashes in SEND
depends on CGA, i.e. if an attacker breaks CGA, all other hashes depends on CGA, i.e. if an attacker breaks CGA, all other hashes
are automatically broken. The use of the hash algorithm embedded are automatically broken. The use of the hash algorithm embedded
in CGA protects from the bidding down attacks. From the security in CGA protects from the bidding down attacks. From the security
point of view, at the moment, this solution is more reasonable point of view, at the moment, this solution is more reasonable
skipping to change at page 11, line 23 skipping to change at page 12, line 23
[pk-agility] [pk-agility]
Cheneau, T., Maknavicius, M., Sean, S., and M. Vanderveen, Cheneau, T., Maknavicius, M., Sean, S., and M. Vanderveen,
"Support for Multiple Signature Algorithms in "Support for Multiple Signature Algorithms in
Cryptographically generated Addresses (CGAs)", Cryptographically generated Addresses (CGAs)",
draft-cheneau-cga-pk-agility-00 (work in progress), draft-cheneau-cga-pk-agility-00 (work in progress),
February 2009. February 2009.
[rfc3971] Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure [rfc3971] Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure
Neighbor Discovery (SEND)", RFC 3971, March 2005. Neighbor Discovery (SEND)", RFC 3971, March 2005.
[rfc3972] Aura, T., "Cryptographically Generated Addresses (CGA)",
RFC 3972, March 2005.
[rfc4270] Hoffman, P. and B. Schneier, "Attacks on Cryptographic [rfc4270] Hoffman, P. and B. Schneier, "Attacks on Cryptographic
Hashed in Internet Protocols", RFC 4270, November 2005. Hashed in Internet Protocols", RFC 4270, November 2005.
[rfc4982] Bagnulo, M. and J. Arrko, "Support for Multiple Hash [rfc4982] Bagnulo, M. and J. Arrko, "Support for Multiple Hash
Algorithms in Cryptographically Generated Addresses Algorithms in Cryptographically Generated Addresses
(CGAs)", RFC 4982, July 2007. (CGAs)", RFC 4982, July 2007.
[sig-agility] [sig-agility]
Cheneau, T. and M. Maknavicius, "Signature Algorithm Cheneau, T. and M. Maknavicius, "Signature Algorithm
Agility in the Secure Neighbor Discovery (SEND) Protocol", Agility in the Secure Neighbor Discovery (SEND) Protocol",
 End of changes. 15 change blocks. 
103 lines changed or deleted 115 lines changed or added

This html diff was produced by rfcdiff 1.38. The latest version is available from http://tools.ietf.org/tools/rfcdiff/