On IPv6 security, SEND, CGA, and alternatives

Some time ago, in 2005, Tuomas Aura of Microsoft Research proposed a way to embed a “cryptographic proof” in the IPv6 addresses. The idea was to tie the address to a public key, by encoding in the IID part of the address the hash of a public key. This would allow IPv6 nodes to prove ownership of the address by signing a message with their private key, and then showing how the IID address is derived from the public key. Tuomas envisaged a set of applications, e.g. encryption of data using IPSEC, or secure roaming with IP mobility, but the IETF only picked the idea in the context of “secure network discovery,” defined in RFC 3791. The address format defined by Tuomas came to me known as “Cryptographically Generated Addresses (CGA)”, defined in RFC 3792. SEND and CGA looked like good ideas at the time, but 9 years have passed and we don’t see a lot of adoption.

More recently, another researcher, Hosnieh Rafiee, revisited that design and proposed an alternative way to tie public key and IPv6 addresses, which she calls “A Simple Secure Addressing Scheme for IPv6 AutoConfiguration” (SSAS). She also wrote a draft presenting her view of the issues with SEND, titled “Recommendations for Local Security Deployments.” I am happy to see researchers working on IPv6 and revisiting the issues that we studied years ago, but I have a problem with that specific proposal. The SSAS algorithm is insecure, as is strength is limited to exactly 64 bits, way too short to prevent spoofing. The local security arguments against CGA and RA-guard are specious, and in at least one case just wrong. For me, it would be much more pleasant to just help a young researcher, but it is one of those cases where I have to write a review that “rejects the paper.”

Draft-rafiee-6man-local-security-00.txt appears a motivating draft, designed to encourage adoption of SSAS. Hosnieh has to make two points, first that the current solutions for local network security are inadequate because SEND is not deployed, and second that the reason why SEND is not deployed is because of issues with the CGA specification, which would be fixed by her SSAS proposal. The current solution for local security is to rely on link level security procedures like 802.1x or Wi-Fi Protected Access (WPA), complemented with filtering of router advertisement by the local switches, defined in RFC 6105, IPv6 Router Advertisement Guard (RA-Guard). Of course, applications should also use end-to-end security protocols like IPSEC or TLS.

Section 3 of the draft-rafiee-6man-local-security-00.txt purports to demonstrate the insufficiencies of the RA-guard solutions. I found it somewhat confusing. Someone else may want to review it, but I believe that some of the statements made there are just wrong. For example, saying that “this feature is supported only in the ingress direction” is bizarre – the whole point is for switches to filter spurious RA from misconfigured local hosts, or from local hosts infected by a virus. Similarly, saying that this does not protected tunnels is also a bit bizarre, since point-to-point tunnels are protected by their own configuration methods.

 

Section 4.1.1.1 of the draft-rafiee-6man-local-security-00.txt assesses that the IPR restrictions on CGA have prevented the deployment of SEND. This is a bit specious, since the IPR owner, Ericsson and Microsoft, have both granted royalty free licenses. It is true that some open source developers are put off by any licensing condition, even royalty free, but there are plenty examples of protocols with similar restrictions that have been widely adopted. In any case, the IPR situation cannot explain why SEND was not deployed by Microsoft, who owns one of the CGA patents.

 

Section 4.1.1.3 of the draft-rafiee-6man-local-security-00.txt purports to demonstrate an attack against CGA. The discussion on the mailing list showed that this attack relies on a downgrade of the CGA SEC value. But since the SEC value is actually part of the address, the attack cannot actually be used against CGA+SEND. Several people pointed that, but Hosnieh kept reasserting her same arguments, and the discussion was really not productive.

 

The valid argument against CGA is that it is only secure if we use non zero values of the SEC parameters, but that doing so requires expensive computation. This consume too much power, and may deplete a mobile device’s battery. Nobody doubts that, but it is pretty much a consequence of the short size of the host identifier field. When it comes to cryptography, 64 bits is not a large number. 80 bits might be acceptable now, but we should really only use 128 bits in the future. CGA anticipated that problem with the SEC field, which complements the limited size host identifier with a requirement that the hash starts with a specified number of zeroes. This is expensive but proven. Bitcoin for example uses a similar algorithm for its “proof of work.”

 

The purported advantage of SSAS is that the IID is much easier to compute than CGA hashes with non-zero SEC numbers. That is true, but the corollary is that SSAS is subject to an obvious attack. According to <draft-rafiee-6man-ssas-08.txt> the “secure” IP address would be derived by concatenating the local prefix and a host ID derived from a public key. The public key is normally an EEC key longer than 196 bit. The host ID is derived as follow:

 

2. Divide the public key array of bytes into two half byte array (see figure 1). Obtain the first 4 bytes from the first half byte array and call it the partial IID1. Obtain the first 4 bytes of the second half byte array and call this the partial IID2. (Dividing the public key is only for randomization)

 

3. Concatenate partial IID1 with partial IID2 and call this the IID.

 

The problem with that approach is obvious. An attacker can simply generate a large number of public keys, and build a catalog of 64 bit identifiers. In at most 2^64 attempts, the attacker will have obtained an IID that matches any target address. Since there is no hashing or proof of work involved, there is no way to improve the security in the future.

 

This is a fundamental flaw, and I wonder why Hosnieh continues to push this flawed approach. The only significant change between the initial SSAS algorithm and draft 08 is to replace the use of RSA public keys by ECC keys, probably based on the belief that ECC keys cannot be generated so easily. But picking a new ECC key is actually rather simple. RFC 6090 describes it in section “5.3.1. Keypair Generation:”

 

The private key z is an integer between 1 and q-1, inclusive, generated uniformly at random. (See Appendix B regarding random integers.) The public key is the group element Y = alpha^z. Each public key is associated with a particular parameter set as per Section 3.3.

 

Given that, the attack by generation of 2^64 keys appears well within the means of today’s attackers. Wait a few turns of Moore’s law, or implementations on GPU or FPGA, and SSAS will be trivially broken by random hackers.

 

Advertisements

About Christian Huitema

I have been developing Internet protocols and applications for about 30 years. I love to see how the Internet has grown and the applications it enabled. Let's keep it open!
This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to On IPv6 security, SEND, CGA, and alternatives

  1. Hosnieh says:

    Hi Christian, as I also discussed in mailing list, you did not mention that one of the strength of SSAS is that, the node keeps the public key of other nodes in the network. So, only for the first time the strength of SSAS is 64 bits.
    and about CGA, unfortunately according to both specifications, CGA verification is a problem and it is less secure than SSAS since the verifier node ignores 3 bits and the source address never compares to target address. This makes CGA only 59 bits.

  2. @Hosnieh: there was ample debate of the verification issue on the mailing list. While the verification field in CGA is only 59 bits, the IPv6 address itself is 128 bits, and all 128 bits have to be matched for any spoofing to occur. That means, an attacker can only spoof a CGA protected address if it matches all bits in it, including the SEC field. In that case, the verification will indeed take the 3 bits SEC into account.

    Your point about “remembering the key” is well taken, but it is independent of the technology used for verifying the link between key and address. If a node remembers the key of another done, then the only window for spoofing is the first contact. This is a classic “leap of faith” paradigm, in which the verifier trusts that the first verification is faithful, then builds upon that to verify that it is always speaking to the same entity. This concept could certainly be implemented on top of SEND.

    • Hosnieh says:

      Hi Christian,
      First I discuss again about the current problems with CGA specification and its security. Since you do not believe what I tells you, I just point you to the sections of RFCs.
      I had a offline discussion with other IETFer about this. We checked all the documents one by one including NDP, SeND, and CGA. Unfortunately because of the verification process as I claimed several times, the security of CGA is only 59 bits. This is true about all implementation of it if it is implemented as mentioned in CGA, SeND and NDP documents. If you like we can write a Erratta about this but this is the true case.
      Check the following sections of documents:
      http://tools.ietf.org/html/rfc3972#section-5
      – it used the term “the address”, The address here refers to the source address. I will explain my reason in next point
      – step 4 of this CGA specification
      ——————————–
      Compare Hash1 with the interface identifier (i.e., the rightmost
      64 bits) of the address. Differences in the three leftmost bits
      and in bits 6 and 7 (i.e., the “u” and “g” bits) are ignored. If
      the 64-bit values differ (other than in the five ignored bits),
      the CGA verification fails.
      ——————————
      So here it says the bits are ignores. check the other steps, no where you can see there is a check between source and target address.
      What the node does is like the following process
      – It checks the target address, if it is the same as its own address then it starts verification on source address. Since it ignores 3 bits and u and g bits, then this is where the problem comes.
      Now let’s continue with RFC 3971
      http://tools.ietf.org/html/rfc3971#section-5.1.2
      —————————
      If the interface has been configured to use CGA, the receiving
      node MUST verify the source address of the packet by using the
      algorithm described in Section 5 of [11]. The inputs to the
      algorithm are the claimed address, as defined in the previous
      section, and the CGA Parameters field.
      ————————
      This is where I pointed you out that why “the address” in CGA is “source address” and not target address
      Here, the attacker will not follow section 5.1.1 of this document since there is no check on the recipient side (verifier side). So why should he follows what is not checked?!

      Now dive more. As you already know, SeND only added 4 options to NDP but didn’t change the initial way to process the NDP messages. You can re-check SeND document to re-assure about this. So, in ND document https://tools.ietf.org/html/rfc4861#section-7.2.3
      ————————–
      – The Target Address is a “valid” unicast or anycast address
      assigned to the receiving interface [ADDRCONF],
      – The Target Address is a unicast or anycast address for which the
      node is offering proxy service, or
      – The Target Address is a “tentative” address on which Duplicate
      Address Detection is being performed [ADDRCONF].
      ——————————–
      The attacker is not process DAD and this is what CGA node is doing and processing DAD. So the attacker has a valid unicast target address that is the same target address of victim original CGA node.
      OK… Now please try to find a place where in any of these documents to tells you that target address is compared with the source address. We couldn’t do this and found nothing…
      the reason is clear, the target address can be sometimes temporary and because it was a general rule in ND document, nothing is mentioned about this check. And the bad thing is that, in SeND, it also follows ND specification and for verification it follows SeND document until it reach to verification of CGA.
      It says follow CGA document in http://tools.ietf.org/html/rfc3971#section-5.1.2 as I mentioned earlier.
      And CGA documents says ignores 3 sec value bits and bits u and g… OK then.. what… the attacker do the attack I mentioned.
      It is true that the source address of the attacker is differs from the CGA victim nodes in 3 bits sec value but since the node only checks target address and start the verification process on source address, this really doesn’t bother the attacker and attack is successful.
      Now another proof that the author of CGA somehow knew about this attack but did do nothing about it since he thought SeND can prevent it while it cannot.
      http://tools.ietf.org/html/rfc3972#section-7.1 lets check here
      —————————-
      For each valid CGA Parameters data structure, there are 4*(Sec+1)
      different CGAs that match the value. This is because decrementing
      the Sec value in the three leftmost bits of the interface identifier
      does not invalidate the address, and the verifier ignores the values
      of the “u” and “g” bits. In SEND, this does not have any security or
      implementation implications.
      ———————–
      Here the proof. But SeND can only do this protection for routers since not every node can have a valid certifications otherwise one uses microsoft AD while in practice not all places use or will use this approach.

      Now about the second things and security of SSAS.
      I recently read on news about quantum computing. http://techcrunch.com/2014/01/02/report-nsa-trying-to-build-a-quantum-computer-to-crack-encryption/
      NSA actually thinking about this and in this way it is easier and really like a blink to generate a prime numbers and the prime algorithms. in this case it is easy to implement http://en.wikipedia.org/wiki/Shor%27s_algorithm this algorithm. And CGA that uses RSA can be broken in a blink. Since it uses only two prime numbers for RSA algorithm while in ECC there are 5 numbers involved.
      This is why what you claimed there is not valid. Because if the computers are more powerful, CGA cannot be also so powerful anymore because it is not just hash function but its security is also the security of public key.
      So, SSAS is much more benefitial than CGA since we don’t go through the heavy process of CGA sec values and we are in a good security. When the Quantum computers come I guess none of the current RSA security are valid maybe either ECC and one need to think about other approaches but CGA also not an option anymore.

      • Hosnieh, let’s look at a concrete example. Let’s assume that Bob wants to communicate securely with Alice on a local network. Bob uses the CGA address:

        2001:DB8::6099:DEAD:BEEF:CAFE

        In this address, the SEC field is set to three, and the remaining bits are set per RFC 3972. Alice’s address is

        2001:DB8::6077:5050:BABA:F00D

        Bob executes the SEND protocol with Alice, and convinces her that his public key properly hashes to the unmasked 59 bits in 0099:DEAD:BEEF:CAFE, and that there are 48 zeroes at the end of the hash, as requested for SEC=3. Alice retains in her cache the association:

        2001:DB8::6099:DEAD:BEEF:CAFE => Bob’s public key.

        They set up a TCP connection between 2001:DB8::6099:DEAD:BEEF:CAFE and 2001:DB8::6077:5050:BABA:F00D.

        Eve wants to disrupt the communication, and uses the attacks that you suggest. She spends a lot of time finding public key and modifier that hash to the CGA address:

        2001:DB8::0099:DEAD:BEEF:CAFE

        That is almost the same value as Bob, but with SEC=0. Eve then executes the SEND protocol with Alice, and convinces her that her public key properly hashes to the unmasked 59 bits in 0099:DEAD:BEEF:CAFE, and that since SEC=0 there is no need to check for zeroes at the end of the hash. At that point, Alice’s cache contains two associations:

        2001:DB8::6099:DEAD:BEEF:CAFE => Bob’s public key.
        2001:DB8::0099:DEAD:BEEF:CAFE => Eve’s public key.

        Eve can now communicate with Alice. But, when she tries to disrupt the communication between Alice and Bob, nothing happens. Packets sent from 2001:DB8::0099:DEAD:BEEF:CAFE to 2001:DB8::6077:5050:BABA:F00D go to a different TCP connection than packets sent between 2001:DB8::6099:DEAD:BEEF:CAFE to 2001:DB8::6077:5050:BABA:F00D.

        Eve is puzzled that the attack did not work, and starts having doubts about Hosnieh’s documentation…

  3. Hosnieh says:

    Christian,
    I don’t think so… since the scenario is not correct.
    We all know that Alice doesn’t cache the public keys. If it cached then it is SSAS algorithm and not CGA.
    1- What you claimed about SSAS is that, someone in a few seconds can break SSAS because it only uses 64 bits until all nodes cache the public key.
    What I claim about CGA is that, if this is true, with the current specification, someone can also not let the Alice and Bob to configure any IP address with CGA value! Because for current CGA, it only needs 59 bits and not even 64 bits.
    This is the first scenario
    now let’s go to the second scenario that you’re talking about
    2- Before Alice starts any communication with Bob, tries to check whether or not the IP address that it has in cache is still valid. It sends NS message with target address sets to Bobs address.
    If Eve wants to attack Bob or Alice, she plans for that beforehand and tries to find the CGA value similar to Bob or Alice before and offline. (of course with 3 bits different and sec value 0).
    In answer to Alice, Eve already has a generated value. He claims he is Bob. If Alice receives the Eve’s packet faster than Bob, then she uses the MAC address of Eve in packets and not Bob. This is because the verification is successful as Alice verifies the source address and ignores 3 bits. So, Alice starts the communication with Eve instead of Bob.
    The chance of Bob is 50% that Alice receives Bobs packet faster than Eve’s.
    3- Now the third scenario is where they already established their communication. In this scenario, since it is TCP layer and not ICMPv6 messages anymore, if there is no security mechanism in between, Eve easily can spoof the IP address of the Bob or Alice. Because they no longer use CGA for any verification and they only did this process at the establishment of this channel.

    I hope it is clear…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s