Subject: RE: FW: New Version Notification for draft-rafiee-6man-cga-attack-00.txt

From: "Hosnieh Rafiee" <[email-masked]>
Date: Fri, 29 Nov 2013 01:28:20 +0100

Hi Christian,

During my conference I had a really nice discussion with some crypto experts
professors about SHA1, SHA2, SHA3, CGA algorithm and the birthday attack. I
guess people here get confused with two different security aspects. First is
the complexity of breaking a hash function and the other is finding
collision (which is not breaking the hash function but finding a value that
hash a similar hash). The birthday paradox is for the latter case and not
for the first case. Now, here we assume that the default hash function is
SHA1, the complexity of finding a collision in this hash functions is 2^160
and with birthday paradox is 2^80 and some people also could do it in 2^60.
Now we have only a part of this hash function that is only  59 bits for CGA
sec value 0. So  the complexity of brute forcing and breaking it is
2^(number of bits) that is 2^59.  But according to birthday paradox, ( you
can refer to birthday paradox attack), finding collision in hashes is half
of the exponential of brute force searching , this means for CGA sec value
0, this value is 2^(29.5).  Now, let's have a simple calculate for other sec
values. 

Sec value 1 => 2^(59+16)  for brute force searching => for birthday paradox
=> 2^(30)     This is actually the total security you obtain with sec value
1 and we know that the other sec values are not ideal to use
Sec value 2=> 2^(59+32) for brute force searching => for birthday paradox =>
2^(45.5)    So you dramatically decreased the performance but you only could
gain 15 more bits. 
...
You can continue this calculation for all sec values. This is actually what
I am going to add to the draft to clarify it.

The other interesting discussion during the conference was that whether it
is different to use SHA1, SHA2 or SHA3. The answer was not so much really.
The reason was because we only have a part of hash and not the whole hash
value. So we really do not use the whole strength of this hash.  Here I just
give you some references for SHA1, SHA2... breaking

@Ray, I guess in this email you can find the answer to the most questions
that you asked in the other email.

Address to the brute force attack(not birthday attack)
http://www.hpi.uni-potsdam.de/meinel/security_tech/ipv6_security/ipv6ssl.htm
l  (cga multicore) here you can find also other attacks as well.
As soon as Fabian finishes the birthday attack, I will share it. He is going
to prepare also the GPU version. (Really thanks to him )

> The CGA mechanism protects an IPv6 address. All the identifier bits are
part of
> the IPv6 address. If an attacker uses a different SEC value, it is not
attacking
> the protected IPv6 address, but a different one.

I guess I am repeating myself here as I explained it before that how this
attack can happens. Unfortunately this is not true. Let me explain it in a
simple example
I am attacker and generate the address  x.  node A generates the address y.
x and y are only different in the first 3 leftmost bits of the address. 
The attacker sets destination address of the packets to multicast group of
the victim address, target address to the exact address of victim and source
address to x.
 Due to verification process. When the nodes receive NS/NA packets that the
destination address is to the multicast group, all nodes check the target
address specified in the message. If it is the same as their own address,
they start verifications of the source address and ignore the leftmost 3
bits. This is actually gives this possibility for the attacker to use
different sec value since the node ignore these 3 bits in verification and
only use these 3 bits to know what the other CGA node used to generate such
address so that they can verify it. This means they verify the sender node
with his own sec value and not their own. So, this is successful and the
owner just tries to increment the collision count (the attacker can do the
same and generate again the same value :-) and after 3 tries, the legitimate
CGA node stops further tries and the attacker is successful!

Now, consider another scenario where the nodes are checks the reachability
of other nodes in their neighboring cache (a table that exist in their
memory). The nodes in the network sends a message "anybody still using this
address", what I understood from RFC 4861, all checks is based on the target
address. Also the node modifies the value of the cache if it sees any
changes of the value with what he has in the cache as a link layer address.

Everytime any other nodes wants to communicate with original CGA node, they
start with these NS messages. Since the attacker node's CGA value can be
verified by the other nodes, he can starts the communication with the other
node and forge the identity of the victim CGA node.  He can either send
several packets with false CGA value and make the victim node busy with that
communication while starting the communication with other nodes since for
this attack, the attacker node has time to generate the same value as the
CGA nodes inside this network offline (does not need to create a rainbow
table but it can only tries to find the similar values as what other nodes
have in this network to forge their identity whenever they wanna start any
communication with any other nodes in this network. The attacker can also
play MITM. Since he can then forge the identity of both side with his CGA
values that is only different in the first 3 leftmost bits to those of the
two communicating nodes. This is actually where the CGA document claim to
make these attacks more complex but it is not as complex as it was claimed. 

> > We also thought that it would take 2^59 but this is not true too based
on
> Birthday paradox attack.
> 
> This is a serious misunderstanding of the birthday paradox. The paradox
states
> that if a number can take N values, it takes about sqrt(N) random trials
for
> having 50% chance to find the same number twice. But the number found is a
> random number.

> The birthday paradox does not apply in the scenario where you try to find
a
> specific value. If a number can take N values, it takes about N/2 trials
before
> having 50% chance to find the target number.

I actually explained this in my above message. I can provide you with
birthday paradox references. 

> 
> So what? The attacker ends up using an IPv6 address that has many bits in
> common as the target address, but it different. There is no masquerading.
The
> attack that you are describing just does not work.

If it is DAD process, the attacker will not let the CGA node to configure
its address. After 3 tries as I explained earlier the CGA node stops further
attempts.

> 
> Hosnieh, your draft also mentions a duplicate address attack. That attack
is
> already described in RFC 3971 (SEND), with a proposed mitigation:
> 
>    9.2.3.  Duplicate Address Detection DoS Attack
> 
>    This attack is described in Section 4.1.3 of [22].  SEND counters
>    this attack by requiring that the Neighbor Advertisements sent as
>    responses to DAD include an RSA Signature option and proof of
>    authorization to use the interface identifier in the address being
>    tested.  If these prerequisites are not met, the node performing DAD
>    discards the responses.
> 
> Do you have a novel way to break these mitigations?

I explained before that how it happens. Please check my example scenarios.
What is saying here is different. The attacker does not have invalid
Signature since he generates himself the public private key and only tried
to find collision in the hash of the victim node but with different sec
value. So, this step really does not help to protect the node against the
attack I am talking about.

Smile,
Hosnieh

---

From: Christian Huitema <[email-masked]>
Date: Fri, 29 Nov 2013 03:09:27 +0000

> 2^(45.5)    So you dramatically decreased the performance but you only could

The birthday paradox really does not apply in the SEND case. It would allow an attacker to generates two keys that map to the same IPv6 address, but it would not allow the attacker to target a specific address, you will need the brute force attack for that.

There is a related attack, against a group. Suppose a subnet of, say, 1024 nodes using SEND. An attacker that generates random value has 1024 chances each time to find a match not for one specific node, but for some random member of the subnet. It will need about 2^49 trials with SEND.

Of course, your SSAS proposal is also susceptible to that attack. In your design, the 64 bits are directly derived from the key, without mixing any subnet prefix. Suppose an attacker lists 1 million SSAS address from the DNS. In 2^44 trials, it will be able to find a match for at least one of them. 

The value of the SEC field does not change the number of required trials, but it makes each trial 2*(16*SEC) times more expensive.

>> The CGA mechanism protects an IPv6 address. All the identifier bits are part of
>> the IPv6 address. If an attacker uses a different SEC value, it is not attacking
> attack can happens

I think you are repeating yourself. If an address differs by a few bits, it is a different address. The CGA mechanism answers the question, "is the sender the legitimate owner of the specific address." To spoof the address, you have to present a candidate that matches the target completely, including the SEC bits.

-- Christian Huitema

---

From: "Hosnieh Rafiee" <[email-masked]>
Date: Fri, 29 Nov 2013 08:28:42 +0100

Christian,

> The birthday paradox really does not apply in the SEND case. It would
allow an
> attacker to generates two keys that map to the same IPv6 address, but it
> would not allow the attacker to target a specific address, you will need
the
> brute force attack for that.

As far as I know, Birthday attack applies to hash functions and not the key
which is used by SSAS. SSAS didn't use any hash function for IP generation.

> There is a related attack, against a group. Suppose a subnet of, say, 1024
> nodes using SEND. An attacker that generates random value has 1024 chances
> each time to find a match not for one specific node, but for some random
> member of the subnet. It will need about 2^49 trials with SEND.

https://www.hackthissite.org/articles/read/1066

In CGA, we have a hash function or like the above example, we have a hash
password. What is important for us is only find another message that leads
to the same hash. This is where birthday paradox applies. So, in CGA, the
attacker really does not care what is the content of your message, it cares
about the hash value. He only wants to have another message (or in birthday
paradox to have another person with the same birthday that matches yours) to
match yours.

> Of course, your SSAS proposal is also susceptible to that attack. In your
design,
> the 64 bits are directly derived from the key, without mixing any subnet
> prefix. Suppose an attacker lists 1 million SSAS address from the DNS. In
2^44
> trials, it will be able to find a match for at least one of them.
> 
> The value of the SEC field does not change the number of required trials,
but
> it makes each trial 2*(16*SEC) times more expensive.
> 
> >> The CGA mechanism protects an IPv6 address. All the identifier bits
> >> are part of the IPv6 address. If an attacker uses a different SEC
> >> value, it is not attacking the protected IPv6 address, but a different
one.
> >
> > I guess I am repeating myself here as I explained it before that how
> > this attack can happens
> 
> I think you are repeating yourself. If an address differs by a few bits,
it is a
> different address. The CGA mechanism answers the question, "is the sender
> the legitimate owner of the specific address." To spoof the address, you
have
> to present a candidate that matches the target completely, including the
SEC
> bits.

As I am repeating here, the problem is the verification in all nodes and
also in CGA nodes or how these nodes behave during the verification. This
actually initiate this attack and make it possible. I only refer you to NDP
document. Because I several times explained that sec value really doesn't
help and the reason is the way they verify the node. Target address as you
know is different than the source address. You only need to have the victim
target address but different source address that follows the condition of
verification that is it is enough to match only 59 bits of the Interface ID.
SeND as I explained before only adds four options and explain them and ask
the nodes to use them to verify the other node but it does not change the
way NDP works. 

Smile,
Hosnieh

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 29 Nov 2013 08:43:33 +0100

> paradox to have another person with the same birthday that matches yours) to

sigh, no.

the birthday paradox applies when you want to find two values that match 
each other and NOT when you have a target and you want to find a hash 
output that matches the target of your attack.

In other words, the birthday paradox is not about finding another person 
that has the same birthday than you but about finding two persons that 
happen to have the same birthday.

This is a critical distinction when you want to use this for an attack, 
as you cannot rely on this to attack a specific target, you can only use 
it for finding two random values that clash.

Regards, marcelo

---

From: Dan Luedtke <[email-masked]>
Date: Fri, 29 Nov 2013 10:08:57 +0100

We are running in circlea here. I will wait for Fabians code to be
published to see the attack first hand. Is there an ETA for the code? I am
fine with non-gpu accelerated code as well. It's just the understanding I
am still lacking here.