From kmigoe@nsa.gov Mon Oct 7 06:23:28 2013 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8970421E80A7 for ; Mon, 7 Oct 2013 06:23:28 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -10.598 X-Spam-Level: X-Spam-Status: No, score=-10.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id WTt2Sn5mF9D9 for ; Mon, 7 Oct 2013 06:23:23 -0700 (PDT) Received: from nsa.gov (emvm-gh1-uea09.nsa.gov [63.239.67.10]) by ietfa.amsl.com (Postfix) with ESMTP id 62FC321E80A6 for ; Mon, 7 Oct 2013 06:23:21 -0700 (PDT) X-TM-IMSS-Message-ID: <50b4836900054be8@nsa.gov> Received: from MSHT-GH1-UEA02.corp.nsa.gov ([10.215.227.181]) by nsa.gov ([63.239.67.10]) with ESMTP (TREND IMSS SMTP Service 7.1; TLSv1/SSLv3 AES128-SHA (128/128)) id 50b4836900054be8 ; Mon, 7 Oct 2013 09:31:21 -0400 Received: from MSMR-GH1-UEA05.corp.nsa.gov (10.215.228.28) by MSHT-GH1-UEA02.corp.nsa.gov (10.215.227.181) with Microsoft SMTP Server (TLS) id 14.2.342.3; Mon, 7 Oct 2013 09:23:19 -0400 Received: from MSMR-GH1-UEA03.corp.nsa.gov ([10.215.224.3]) by MSMR-GH1-UEA05.corp.nsa.gov ([10.215.228.28]) with mapi id 14.02.0342.003; Mon, 7 Oct 2013 09:23:19 -0400 From: "Igoe, Kevin M." To: "cfrg@irtf.org" Thread-Topic: Response to TLS WG on SALSA Thread-Index: Ac7DYGJmsEq+QbVQSsKP61HliRDsmA== Date: Mon, 7 Oct 2013 13:23:18 +0000 Message-ID: <3C4AAD4B5304AB44A6BA85173B4675CAB24E0267@MSMR-GH1-UEA03.corp.nsa.gov> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [10.215.225.46] Content-Type: multipart/alternative; boundary="_000_3C4AAD4B5304AB44A6BA85173B4675CAB24E0267MSMRGH1UEA03cor_" MIME-Version: 1.0 Subject: [Cfrg] Response to TLS WG on SALSA X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 07 Oct 2013 13:23:28 -0000 --_000_3C4AAD4B5304AB44A6BA85173B4675CAB24E0267MSMRGH1UEA03cor_ Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable With IETF-88 looming in the near future, we owe the TS-WG a resonse on the suitability of various stream ciphers snd MACsin TLS. Three stream ciphers have been discussed: 1) The original SALSA-20 2) ChaCha, a variant of SALSA-20, modifying the prolog and epilog to increase the efficiency. 3) eStream SALSA-20 (hereafter eSALSA), reduces rounds from 20 rounds in SALSA-20 down to 12 rounds. Here is my reading on the opinion of the mailing list: 1) There seems to be substantial controversy over the efficiency of th= e various stream cipher candidates, especially when compared to AES counter mod= es. This needs to be straightened out before an informed decision can be = made. On the maturity of the cryptanalysis of the three stream ciphers: 1) The analysis of SALSA-20 has been very thorough and the degree of c= onfidence in SALSA-20 is very high. 2) Though ChaCha has received slightly less analysis, the RG is confid= ent that the analysis was sufficiently thorough that ChaCha is an acceptable alter= native to SALSA-20. 3) The RG was less comfortable with the maturity of the analysis of eS= ALSA, but no substantive objections were raised. Cryptanalytically all are almost certainly sufficient for use in TLS. The = RG expressed a preference for ChaCha. We were also asked our opinion on the MACs being considered, UMAC and POLY1= 305. No cryptanalytic issues were raised, thought VMAC was suggested as a more e= fficient alternative to the efficiency of UMAC. The suitability of these MACs for e= fficient hardware implementation was questioned. Is this a reasonably accurate synopsis? ----------------+-------------------------------------------------- Kevin M. Igoe | "We can't solve problems by using the same kind kmigoe@nsa.gov | of thinking we used when we created them." | - Albert Einstein - ----------------+-------------------------------------------------- --_000_3C4AAD4B5304AB44A6BA85173B4675CAB24E0267MSMRGH1UEA03cor_ Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable
With IETF-88 looming in the near future, we owe the TS-WG a resonse
on the suitability of various stream ciphers snd MACsin TLS.
Three stream ciphers have been discussed:
  1. The original SALSA-20
  2. ChaCha, a variant of SALSA-20, modifying = the prolog and epilog to
    increase the efficiency.
  3. eStream SALSA-20 (hereafter eSALSA), redu= ces rounds from
    20 rounds in SALSA-20 down to 12 rounds.
 
Here is my reading on the opinion of the mailing list:
  1. There seems to be substantial controversy over the efficiency of the va= rious
    stream cipher candidates, especially when compared to AES counter modes. This needs to be straightened out before an informed decision can be made.<= /li>
On the maturity of the cryptanalysis of the three stream ciphers:
  1. The analysis of SALSA-20 has been very thorough and the degree of confi= dence
    in SALSA-20 is very high. 
  1. Though ChaCha has received slightly less analysis, the RG is confident = that the
    analysis was sufficiently thorough that ChaCha is an acceptable alternative= to
    SALSA-20.
  2. The RG was less comfortable with the maturity of the ana= lysis of eSALSA, but
    no substantive objections were raised.
Cryptanalytically all are almost certainly sufficient for use in TLS.&= nbsp; The RG expressed
a preference for ChaCha.
 
We were also asked our opinion on the MACs being considered, UMAC and = POLY1305. 
No cryptanalytic issues were raised, thought VMAC was suggested as a m= ore efficient
alternative to the efficiency of UMAC.  The suitability of these = MACs for efficient hardware
implementation was questioned.
 
Is this a reasonably accurate synopsis?
 
 
 
----------------+------------------------------------= --------------
Kevin M. Igoe   | "We can't solve problems= by using the same kind
kmigoe@nsa.gov  | of thinking we used when we create= d them."
         &nb= sp;      |      &nbs= p;       - Albert Einstein -
----------------+------------------------------------= --------------
 
 
 
--_000_3C4AAD4B5304AB44A6BA85173B4675CAB24E0267MSMRGH1UEA03cor_-- From kasamatsu.kohei@po.ntts.co.jp Wed Oct 9 00:52:29 2013 Return-Path: X-Original-To: cfrg@ietfa.amsl.com Delivered-To: cfrg@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7278221F9E48 for ; Wed, 9 Oct 2013 00:52:26 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 1.399 X-Spam-Level: * X-Spam-Status: No, score=1.399 tagged_above=-999 required=5 tests=[BAYES_05=-1.11, HELO_EQ_JP=1.244, HOST_EQ_JP=1.265] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pJQEDLSe0EIg for ; Wed, 9 Oct 2013 00:52:19 -0700 (PDT) Received: from mail12.ics.ntts.co.jp (mail12.ics.ntts.co.jp [210.232.35.65]) by ietfa.amsl.com (Postfix) with ESMTP id 1E9A521E80F2 for ; Wed, 9 Oct 2013 00:52:18 -0700 (PDT) Received: from sadoku34.silk.ntts.co.jp (sadoku34 [10.7.18.34]) by mail12.ics.ntts.co.jp (8.14.4/8.14.4/NTTSOFT) with ESMTP id r997qDNt027728; Wed, 9 Oct 2013 16:52:13 +0900 (JST) Received: (from root@localhost) by sadoku34.silk.ntts.co.jp (8.13.8/NTTSOFT) id r997qD7K002018; Wed, 9 Oct 2013 16:52:13 +0900 (JST) Received: from ccmds32.silk.ntts.co.jp [10.107.0.32] by sadoku34.silk.ntts.co.jp with SMTP id SAA02017; Wed, 9 Oct 2013 16:52:13 +0900 Received: from mail147.silk.ntts.co.jp (ccmds32.silk.ntts.co.jp [127.0.0.1]) by ccmds32.silk.ntts.co.jp (8.14.3/8.14.3) with ESMTP id r997qCcc003523; Wed, 9 Oct 2013 16:52:12 +0900 Received: from mail147.silk.ntts.co.jp (localhost.localdomain [127.0.0.1]) by mail147.silk.ntts.co.jp (8.14.5/8.14.5/NTTSOFT) with ESMTP id r997q9d8008160; Wed, 9 Oct 2013 16:52:09 +0900 Received: from ccmds32 (mail145.silk.ntts.co.jp [10.107.0.145]) by mail147.silk.ntts.co.jp (8.14.5/8.14.5/NTTSOFT) with SMTP id r997q9H7008157; Wed, 9 Oct 2013 16:52:09 +0900 Message-ID: <52550B15.80806@po.ntts.co.jp> Date: Wed, 09 Oct 2013 16:51:49 +0900 From: Kohei Kasamatsu User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8 MIME-Version: 1.0 To: lhitt@21ct.com Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit X-CC-Mail-RelayStamp: CC-Mail-V4.3-Client X-CC-Mail-RelayStamp: CC-Mail-V4.3-Server Cc: cfrg@irtf.org Subject: Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves X-BeenThere: cfrg@irtf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Crypto Forum Research Group List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 09 Oct 2013 07:52:29 -0000 Hi Laura, Thank you for your email. I explain my opinion against your comments below. In first, I explain relation between ZSS signature and hardness of k-CAA and k-wCDHP. Theorem 3 of [1] showed that If q_s-CAA is hard ZSS signature satisfies standard security required by signature, where q_s is the number of pairs of signature and message which adversary can obtain. Theorem 4 of [1] showed (k-1)-wCDHP and k-CAA are polynomial time equivalent. That is, if there exists algorithm which can solve k-CAA there exists algorithm which can solve (k-1)-wCDHP and vice versa. ([2] proved the theorem 4) (k-1)-wCDHP is as follows. input: P, yP, y^2 P, ..., y^k P output: y^{-1} P Hence we can apply cheon algorithm to (k-1)-wCDHP and improve its efficiency to solve this problem. it also means improvement of efficiency to solve k-CAA problem because of theorem 4. Next, I explain my opinion against what you pointed out by mapping above explanation into real world. (If my response is beside away from your point, please let me know. ) The adversary can transform k-CAA problem based on signature 1...k into (k-1)-wCDHP by reduction algorithm of [2] and apply it to cheon algorithm to obtain a secret key. Hence I think that we can apply cheon algorithm to ZSS signature. I would like to leave it to you whether adding the description on cheon algorithm into your draft or not because cheon algorithm cannot break ZSS signature in the sense of asymptotic security. Of course, please let me know if you have further questions or concerns. [1] Fangguo Zhang, Reihaneh Safavi-Naini, and Willy Susilo. Public Key Cryptography, volume 2947 of Lecture Notes in Computer Science, page 277-290. Springer, (2004) [2] S. Mitsunari, R. Sakai and M. Kasahara, A new traitor tracing, IEICE Trans. Vol. E85-A, No.2, pp.481-484, 2002. Best, Kohei KASAMATSU (2013/09/24 5:57), Laura Hitt wrote: > Hi Kohei, > > The Cheon attack assumes knowledge of s^i * P for i in [0,d] in order to determine s, where d is some divisor of p-1 or p+1. I believe you are suggesting that with d pairs of signature and message, one would obtain the necessary s^i * P. However, if we look at the ZSS signature scheme explicitly, we shall see that is not the case. > > Signature 1 = [H(m1)+x]^-1 * P > Signature 2 = [H(m2)+x]^-1 * P > ... > Signature i = [H(mi)+x]^-1 * P > > There is no oracle providing the necessary s^i * P for the ZSS signature scheme, so I do not believe the I-D needs to be changed to address the Cheon attacks. > > Please let me know if you have further questions or concerns. > > Best, > Laura > > -----Original Message----- > From: Kohei Kasamatsu [mailto:kasamatsu.kohei@po.ntts.co.jp] > Sent: Wednesday, September 18, 2013 9:38 PM > To: Laura Hitt > Cc: cfrg@irtf.org > Subject: Re: [Cfrg] request for comments: ZSS Short Signature Scheme for SS and BN Curves > > Hi Laura, > > > Thank you for you email and I apologise for the delay in replying to you. > > I recommend ZSS signature to use elliptic curves with prime order p such that both of p+1 and p