Thanks Christian, Here is what I propose. I have an implementation of SSAS and I will try to break it to see how long it will take. (I will also share the code with others so that more people can try to break it.) Based on the mathematical calculations (of finding the expected value) the probability of it being broken in one month is very low. Since we also want to use this for the integration of privacy, then this is secure enough. But perhaps with my implementation of the attacks against SSAS I can learn the what happens in realtime as opposed to mathematical theory. I have my doubts about what you said about being able to break it in seconds. I am sorry but I feel that what you said is really unrealistic. If you really are able to implement something that does this, then you probably would be able to break CGA in seconds also.
About the modifier that I have, I will also check to determine whether using makes breaking it easier or harder. If it is easier. then I will use the entire 64 bits of the public key (set bit u and g) and use the fixed part of the public key. I am not trying to create a new hash algorithm but only make improvements to my algorithm. Francis: SSAS also provides proof of IP address ownership as does CGA. The question here is not that but is on the security considerations that are based on my calculations with regard to the probability of being able to break it. I believe that what Christian says is not true, but I will have to try it to prove him wrong. About other algorithms, CGA can use them as well so you cannot compare the computational times based on the use of those algorithms. Hosnieh From: Christian Huitema [mailto:huit...@microsoft.com] Sent: Sunday, March 17, 2013 8:34 PM To: Hosnieh Rafiee; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas I don't think the index helps much. I suspect that SSAS could be broken in minutes if someone did a parallel implementation on a GPU. Maybe seconds. Frankly, I believe that you have fallen in the trap of "inventing your own crypto." Most of these inventions turn out to have flaws, and won't pass a serious review. I would advise that you withdraw that specific proposal. From: Hosnieh Rafiee [mailto:i...@rozanak.com] Sent: Sunday, March 17, 2013 11:47 AM To: Christian Huitema; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas Thanks again for your response. I have some questions: - Choosing a random part of the public key does not help to increase the probability of matching the public key to the IID? if I am to improve this section and by saying we need to generate two, one byte random numbers such that the second byte must not be higher than the size of public key minus 6. - How many days does it take to break SSAS? I ask this because for privacy I consider changing the key pairs and creating a new IP address in a certain time frame. Hosnieh From: Christian Huitema [mailto:huit...@microsoft.com] Sent: Sunday, March 17, 2013 5:46 PM To: Hosnieh Rafiee; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas On the other hand, cracking SSAS is *much* easier than cracking RSA, or even cracking CGA. SSAS builds the 64 bit identifier as follow: . Pick a random 16 bit number; . Use that number as an index in the bit array representing the public key; . Extract the 48 bits following the index; . Concatenate the random 16 bit number and the 48 bits of the key to build a 64 bit interface ID; . Prove possession of the public/private key pair when using the resulting IPv6 address. An attacker can obviously break that scheme in about 2**48 trials, by generating a set of random public/private key pairs. For each generated key, there is 2**-48 probability that the indexed bits match the 48 bit thumbprint. In about 2**48 trials, the attacker will get a public key in which the 48 bits happen to match the 48 bit thumbprint in the IPv6 address. They can then select that key pair, and spoof the IPv6 SSAS address at will. 2**48 is much less than the 2**59 figure for the CGA/Sec=0 algorithm, let alone using SEC=1 or SEC=2. You may think that building public/private key pairs is a very expensive operation, but that is not true. The default algorithm for SSAS is RSA. Let's suppose you use 2048 bit long RSA keys. The key generation start by generating a set of 1024 bit long prime numbers. In theory, we need about 2*25 such numbers. Add a margin to be on the safe side. These numbers can be generated once, they don't have to be regenerated for every SSAS key being tried. An RSA key is the product of two such numbers. 2*25 numbers allow you to compute 2**48 products, i.e. 2**48 candidate public keys. Computing a long integer product does take a few computations, but not much more than computing a SHA hash. The search for a key that match the footprint will be very quick! From: Hosnieh Rafiee [mailto:i...@rozanak.com] Sent: Sunday, March 17, 2013 9:22 AM To: Christian Huitema; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas Thanks Christian. You answered my question. This is what I wanted to know about security when directly using keys or using in the way CGA does. Both are difficult but the CGA way is relatively easier than cracking the RSA keys. Hosnieh From: Christian Huitema [mailto:huit...@microsoft.com] Sent: Sunday, March 17, 2013 9:14 AM To: Hosnieh Rafiee; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas The attack is *relatively* easier. It is not "easy." It is much harder to crack RSA than to find a matching hash. Cracking a 2048 bits RSA key probably requires on the order of 2^1024 trials, and that will take you something like "forever." Cracking the hash requires only something on the order of 2^91 trials with SEC=2. That's obviously much less, but that's still a very large number. The exhausting search will take you many years, i.e. much more than the valid lifetime of the address. From: Hosnieh Rafiee [mailto:i...@rozanak.com] Sent: Saturday, March 16, 2013 1:45 PM To: Christian Huitema; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; 'Michael Richardson'; jeanmichel.com...@orange.com; 'Roque Gagliano (rogaglia)' Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas >The "SEC" part of CGA is meant to protect against a different attack, one in which the attacker has not cracked the private key. Instead, the attacker uses a public/private key pair of his own >choosing, and arrange for the hash of that key to match the CGA address of the target. This "only" requires O(2**(59+SEC*16)) operations, which even with large values of SEC is still far less than >what is required to crack RSA or ECC. So according to what I understand from what you wrote, the sec value makes the for an easier attack against CGA as the attacker only needs to find the same value generated by his own modifier and other parameters and matches this to the IID of the node. Now the question again is, if this gives an attacker a leg up in doing his brute force attacks why do we need to add those steps to CGA. This was why I used the direct public key as a part of IP address. Thanks again Christian. Hosnieh From: Christian Huitema [mailto:huit...@microsoft.com] Sent: Saturday, March 16, 2013 7:30 PM To: Hosnieh Rafiee; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; Michael Richardson; jeanmichel.com...@orange.com; Roque Gagliano (rogaglia) Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas As you say, the attack that you mention depends on the strength of RSA or ECC. In fact, pretty much all of public key cryptography depends on that strength. It is generally assumed that cracking a long enough RSA or ECC key is nearly impossible. The "SEC" part of CGA is meant to protect against a different attack, one in which the attacker has not cracked the private key. Instead, the attacker uses a public/private key pair of his own choosing, and arrange for the hash of that key to match the CGA address of the target. This "only" requires O(2**(59+SEC*16)) operations, which even with large values of SEC is still far less than what is required to crack RSA or ECC. From: Hosnieh Rafiee [mailto:i...@rozanak.com] Sent: Saturday, March 16, 2013 10:59 AM To: Christian Huitema; ipv6@ietf.org; s...@ietf.org Cc: 'Erik Nordmark'; alexandru.petre...@gmail.com; 'Ray Hunter'; Michael Richardson; jeanmichel.com...@orange.com; Roque Gagliano (rogaglia) Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas Hi Christian, > But can y toou explain why you believe that retrieving the private key from the public key and a clear text/encrypted text pair is easier than breaking a hash? Here we do not use any encryption and decryption and we just sign the message using private key and verify the message using public key. >Did you somehow crack RSA? I do not say that it is easier to find the private key from the public key. Because for both SSAS and CGA, public/private keys are used. I do say that the SHAx steps used for CGA generation do not increase the complexity when used against brute force attacks. This is because an attacker only needs the private key and does not need to find the modifier that was used in the generation of the node's IID nor is there a need for checking the condition of sec by 16 bits which should be equal to zero. In SSAS I just use the public/private keys and the signature and nothing is encrypted/decrypted. In CGA some extra SHAx steps are used in the generation of their IID along with the signature. I say that these steps are not needed as long as you include and send all parameters, used in the SHAx process, in the packet for verification purposes. Some people feel that CGA is secure enough when those steps are used. Now what I want to point out here is that the CGA security level is only dependent on the algorithm used for key pair and signature generation and that those extra steps do nothing enhance the security side of things. The algorithms used can be RSA or ECC or whatever, and as such the situation will be the same as it is for SSAS. I just removed the complexity from the use of CGA in order to enable a more practical and faster generation and verification process. So the question isn't how to break the encrypted text but how to break the signature. In other word, to find the same public key as used by the generator node or how to break the RSA or ECC. Based on my knowledge of hash algorithms, as I mentioned in my prior sentence, this will depend on the strength of the RSA or whatever other algorithm is used to generate these keys and sign the message. If you or anyone else thinks otherwise, please contribute to this discussion and share your opinions. I am just comparing the security aspects of SSAS, the time efficient algorithm, to those of CGA. Thank you, Hosnieh From: Christian Huitema [mailto:huit...@microsoft.com] Sent: Saturday, March 16, 2013 5:37 PM To: Hosnieh Rafiee; ipv6@ietf.org; s...@ietf.org Cc: Erik Nordmark; alexandru.petre...@gmail.com; Ray Hunter Subject: RE: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas It is very clear that if the attacker finds the private key, the size of the hash does not matter. But can you explain why you believe that retrieving the private key from the public key and a clear text/encrypted text pair is easier than breaking a hash? Did you somehow crack RSA? From: ipv6-boun...@ietf.org [mailto:ipv6-boun...@ietf.org] On Behalf Of Hosnieh Rafiee Sent: Saturday, March 16, 2013 6:27 AM To: ipv6@ietf.org; s...@ietf.org Cc: Erik Nordmark; alexandru.petre...@gmail.com; Ray Hunter Subject: security consideration of CGA and SSAS - Ii-D action : draft-rafiee-6man-ssas Hello, There was a discussion during my presentation about security considerations regarding the use of my algorithm compared with those of the use of CGA. A big mistake that is made when considering CGA security is that the sec value plays an important role and that an attacker will need to do brute force attacks against the IID in order to generate the same IID as is generated by the use of CGA. In a CGA analysis paper they talk about a CGA security vaulue of pow (2, sec*16 * 59) where 2 is the base and sec*16 * 59 is the exponential value and so they infer that by increasing the sec value used with CGA it will be safer, but this Is not true. I, as an attacker, just to need to find your private key. That's it. This is because you have already included the CGA parameters (public key, modifier, and other required parameters) in the packet that was sent and I will have no problem in regenerating the CGA. My only problem will be in generating the signature that can be verified by use of your public key. This means that you just increased the complexity and time required for generating and verifying the IID while with SSAS you can obtain the same security as when using CGA because its security also depends on the Hash function that is used to generate the key pair and signature. If you send the CGA parameters via a safe channel, like in establishing TLS etc., then, in that case, CGA would be more secure than SSAS. But in practice all the data is sent in the same packet without encryption. If a secured channel would be used in the CGA process for security reasons (sending CGA parameters), then the cost of using CGA would be much greater than the cost of using SSAS. Now the question is, Why not use a more cost efficient algorithm that afford you with the same security level as when using CGA. I have also included the security group in this email so that they can also give me any comments that they might have. Thank you, Hosnieh
-------------------------------------------------------------------- IETF IPv6 working group mailing list ipv6@ietf.org Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6 --------------------------------------------------------------------
