RE: Question about Crypto algorithm

Hosnieh Rafiee <hosnieh.rafiee@huawei.com> Thu, 11 September 2014 15:24 UTC

Return-Path: <hosnieh.rafiee@huawei.com>
X-Original-To: ietf@ietfa.amsl.com
Delivered-To: ietf@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 030801A0B77 for <ietf@ietfa.amsl.com>; Thu, 11 Sep 2014 08:24:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.141
X-Spam-Level:
X-Spam-Status: No, score=-3.141 tagged_above=-999 required=5 tests=[BAYES_50=0.8, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, RP_MATCHES_RCVD=-1.652, SPF_PASS=-0.001, T_FILL_THIS_FORM_SHORT=0.01, WEIRD_PORT=0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nOV9f_AEsks2 for <ietf@ietfa.amsl.com>; Thu, 11 Sep 2014 08:23:57 -0700 (PDT)
Received: from lhrrgout.huawei.com (lhrrgout.huawei.com [194.213.3.17]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 74A1E1A00BB for <ietf@ietf.org>; Thu, 11 Sep 2014 08:23:56 -0700 (PDT)
Received: from 172.18.7.190 (EHLO lhreml405-hub.china.huawei.com) ([172.18.7.190]) by lhrrg01-dlp.huawei.com (MOS 4.3.7-GA FastPath queued) with ESMTP id BML45732; Thu, 11 Sep 2014 15:23:54 +0000 (GMT)
Received: from LHREML513-MBB.china.huawei.com ([fe80::b810:863:a57e:3ff]) by lhreml405-hub.china.huawei.com ([10.201.5.242]) with mapi id 14.03.0158.001; Thu, 11 Sep 2014 16:23:50 +0100
From: Hosnieh Rafiee <hosnieh.rafiee@huawei.com>
To: "Margraf, Marian, Dr." <marian.margraf@h-da.de>
Subject: RE: Question about Crypto algorithm
Thread-Topic: Question about Crypto algorithm
Thread-Index: AQHPzTBWpwFacNZ5TEGMTD9/Hujmr5v7/Ptw
Date: Thu, 11 Sep 2014 15:23:50 +0000
Message-ID: <814D0BFB77D95844A01CA29B44CBF8A7A2C024@lhreml513-mbb.china.huawei.com>
References: <449D1D09-2A2D-48DC-8A00-FEAD1AAA03B5@h-da.de> <B0CC4AD5-03D9-420E-86C2-DF9252A2798D@h-da.de>
In-Reply-To: <B0CC4AD5-03D9-420E-86C2-DF9252A2798D@h-da.de>
Accept-Language: zh-CN, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [10.221.82.100]
Content-Type: multipart/alternative; boundary="_000_814D0BFB77D95844A01CA29B44CBF8A7A2C024lhreml513mbbchina_"
MIME-Version: 1.0
X-CFilter-Loop: Reflected
Archived-At: http://mailarchive.ietf.org/arch/msg/ietf/cLkR2YWZadyu2TLp36vevIzQG2k
X-Mailman-Approved-At: Mon, 15 Sep 2014 07:40:54 -0700
Cc: "john+ietf@jck.com" <john+ietf@jck.com>, "rfc-ise@rfc-editor.org" <rfc-ise@rfc-editor.org>
X-BeenThere: ietf@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: IETF-Discussion <ietf.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/ietf>, <mailto:ietf-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/ietf/>
List-Post: <mailto:ietf@ietf.org>
List-Help: <mailto:ietf-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/ietf>, <mailto:ietf-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 11 Sep 2014 15:24:03 -0000


Dear Prof. Margraf,



Thanks a lot for your message and the time you spend to answer my question. Please find my responses in red color.





Best Regards,

Hosnieh (Sara)

P.S. I included two people who are interested to know the security aspect of this proposal (in particular crypt aspects)



From: Margraf, Marian, Dr. [mailto:marian.margraf@h-da.de]

Sent: Thursday, September 11, 2014 4:08 PM

To: Hosnieh Rafiee

Subject: Fwd: Question about Crypto algorithm



Dear Mr Rafiee,



Mr Heinemann asked me to answer you.



My first remark is, that an ecc public key (in bit representation) is not uniformly distributed. It depends on the format of the public key that you use. For example, if you use the uncompressed format, the public key is of the form (x,y), a point on the curve. For a value x there are at most two values of y such that (x,y) is a point on the curve. Maybe this leads to a lower entropy as 64 bit (but I am not sure).



Do you mean that with this way we will not have much randomization of the IP addresses in a certain network?

does it only randomization issue or it might also impact on its security since it is easy for an attacker to find the same value because of lacks of entropy?

There is actually standard document that explain how to implement ECC (http://tools.ietf.org/html/rfc6090 ) , I used this document as a reference and considered my nodes would implement it. May I ask you please skim on the document about this ECC algorithm to see whether or not it does have this compression.

Thank you





Second remark: Of course, only the owner of the private key can sign the value (random IDD +  time stamp). But this private key is not be used in the following communication (or is it, I am not familiar whit IPv6 in detail). My question: What happens, if the attacker blocks the original message, choose the same idd and then sends the message as his own idd to the other nodes. Is this possible.



I understand that you are crypto specialist so I try to explain the IPv6 scenario in an simple example. Before I briefly address your question.



The attacker cannot block the packets since it is like flooding to all nodes in the network. But the attacker can only send a packet to the victim node and claim that he has the same IP address as the victim node but with its own generated public/private key values otherwise the signature verification will be failed. Also blocking this packet does not help the attacker because the victim node expects to receive an answer and if it does not receive any answer, it starts using that IP address. (we presume in this scenario that the victim node was not compromised so that the private key is exposed to the attacker).



The attack on my algorithm are in two cases

1-  The attacker must use ECC algorithm to generate the same 64 bits as the legitimate node – this attack only possible in a few seconds because later other nodes keep the public key of this legitimate nodes in their memory after a successful verification

2-  The attacker then needs to generate the same public key as what the legitimate node has (after the few seconds)



How a computer generates and IP address



-    Computer A generates a key pairs using ECC public key cryptography. (RFC 6090)

-    Computer A use my draft RFC and apply my algorithm to generate and use 64 bits of this public key

(Half from right part of public key and half from left.)

-    Computer A concatenates this 64 bits public key (so called IID) with a fixed 64 bits and this indicates the IP address of the node.

-    Computer A signs (128-bit IP address + timestamp)

-    Computer A creates a packet, uses this IP address as a source of the packet, includes this signature as an optional part of this packet, adds the public key to the optional part of the packet and submits it to all other computers in this network. With this way it checks whether or not anybody in the network has the same IP address as computer A has.



Verification Process in computer A

If computer B has the same IP address (or it is an attacker that claims to have the same IP address) as computer A, it immediately generates a packet with the same way as computer A did and sends this packet to computer A. When computer A receives this packet, it needs to verify this claim because computer B now claims that it has the IP address that computer A generated (or they both have the same 64 bits IID). Computer A follow the following steps for the verification (I skip the timestamp verification and only focus on the main points);

1.  Computer A verifies the signature, if it is successful it goes to next step

2.  Computer A retrieves the public key from the computer B’s packet and divide it into two halves (use the same algorithm to generate the same value as computer A generates its IP address)

3.  Computer A takes 32 bits from each halves and concatenates these values. The resulting value is 64 bits

4.  Computer A also concatenate this 64 bits with the fixed value so called router prefix and generates a 128 bits IP address

5.  Computer A compares this value with computer’s B source IP address. If it needs to choose another IP address. If it is not the same, then Computer A understands that this is an attacker who wanted to not let computer A to generate an IP address and enter to the network.

6.  When computer B cannot claim to have the IP address of computer A, now computer A send the same packet with signed the new timestamp to all nodes and ask them to save its public key so that it complicates the attack



Private key is only used to sign the packet but never sent to computer B or never exchanged. Computer A only sends its public key to other nodes for the purpose of verification. The packets only signed but not encypted.







Do you think that this scenario is clear enough to judge about the algorithm?

Thank you,









Best regards, Marian Margraf



--

Prof. Dr. Marian Margraf

Theoretische Informatik und IT-Sicherheit



Hochschule Darmstadt

University of Applied Sciences



Schoefferstr. 8b

D-64295 Darmstadt

Telefon: +49(0)6151-168457

Mobil:     +49(0)171 6534179









From: Hosnieh Rafiee <hosnieh.rafiee@huawei.com>

Subject: Question about Crypto algorithm

Date: 10. September 2014 | KW 37 10:29:47 MESZ

To: "andreas.heinemann@h-da.de" <andreas.heinemann@h-da.de>



Dear Prof. Heinemann,



I just found your name accidentally during my search for people who works in security, in particular, cryptography. (My profile : http://rozanak.com/contact.aspx  ).



I have finished my Ph.D. at Hasso plattner Institute in security in internet technologies and now work as a senior security researcher at Huawei technologies. I am not a crypto person but only use cryptographic algorithms for security purposes and only evaluated their performance. I am working on standards and security standards and this is why I am active at IETF.



Why I contact you is because I am in a need of a crypto reviewer to only give us his/her opinion about the following case:

I have a draft RFC which is about IPv6 address generation in a secure manner. This is alternative approach to Cryptographically Generated Addresses (CGA). that I have submitted it to independent track.



How the algorithm work is that, since IPv6 address is only 128 bits and only I can generate 64 bits of this value. To avoid an attacker to forge the identity of my node, I use ECC algorithm and generate a key pairs. Then I divide the public key in two halves (only for randomization) and retrieve 32 bits from each halves. Then I concatenate these value and the result would be 64 bits interface ID of my IPv6 address.

My node then needs to check the conflicts in the network. For doing this it sign this value including a timestampt to avoid replay attack with its private key and sends the signature + public key to all nodes in the local link. Since 64 bits of this node is ECC public key (not exactly like finger print of public key), so the attacker only has a few seconds during this step to break this 64 bits. After this few seconds, all nodes in this local link cache the public key of this node.



My claims:

1- The attacker cannot predict what IP address a new node might choose so that it can break it offline

2- The attacker needs a very big database to try to create a rainbow table for each single possible values for 2^64 bits so in practice this is not possible

3- After a few seconds of the first check the attacker needs to do this attack against the whole public key which depends on the security of ECC.



So now what is your opinion. Do you think this approach work well?

If you need more information, I would be glad to share that with you.



This is where you can find this draft

https://tools.ietf.org/html/draft-rafiee-6man-ssas-10



Thank you,

I look forward to receiving your response.

Best Regards,





------

Dr. Hosnieh Rafiee

Security Competence Department

HUAWEI TECHNOLOGIES DUESSELDORF GmbH

Munich Office, European Research Center

Riesstraße 25

80992 München

Tel: +49 (0)89 158834 4047

M: +49 (0)162 204 74 58



E-mail: hosnieh.rafiee@huawei.com



HUAWEI TECHNOLOGIES Duesseldorf GmbH

Am Seestern 24, 40547 Düsseldorf, Germany, www.huawei.com Registered Office: Düsseldorf, Register Court Düsseldorf, HRB 56063, Managing Director: Jingwen TAO, Wanzhou MENG, Lifang CHEN Sitz der Gesellschaft: Düsseldorf, Amtsgericht Düsseldorf, HRB 56063,

Geschäftsführer: Jingwen TAO, Wanzhou MENG, Lifang CHEN



本邮件及其附件含有华为公司的保密信息,仅限于发送给上面地址中列出的个人或群组。禁

止任何其他人以任何形式使用(包括但不限于全部或部分地泄露、复制、或散发)本邮件中

的信息。如果您错收了本邮件,请您立即电话或邮件通知发件人并删除本邮件!

This e-mail and its attachments contain confidential information from HUAWEI, which is intended only for the person or entity whose address is listed above. Any use of the information contained herein in any way (including, but not limited to, total or partial disclosure, reproduction, or dissemination) by persons other than the intended

recipient(s) is prohibited. If you receive this e-mail in error, please notify the sender by phone or email immediately and delete it!







--

Prof. Dr. Andreas Heinemann

Fachbereich Informatik

Hochschule Darmstadt - University of Applied Sciences

Haardtring 100

D-64295 Darmstadt



Tel.:  06151-16-8482

Fax.: 06151-16-8935

E-Mail: andreas.heinemann@h-da.de

Büro: D14/1.10, Schöfferstr. 8b, 64295 Darmstadt



PGP-Public Key:

https://www.fbi.h-da.de/organisation/personen/heinemann-andreas.html

http://pool.sks-keyservers.net:11371/pks/lookup?search=0x60355C96811D6CB7