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

["Hosnieh Rafiee" <[e-mail]>]

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