[prev in list] [next in list] [prev in thread] [next in thread]
List: cfrg
Subject: Re: [Cfrg] Suggestions for draft-hao-schnorr
From: Feng Hao <feng.hao () newcastle ! ac ! uk>
Date: 2013-12-05 1:38:13
Message-ID: CEC57058.22483%feng.hao () newcastle ! ac ! uk
[Download RAW message or body]
Hi Robert,
Thanks for the suggestions. My response is interleaved below.
On 03/12/2013 23:35, "Robert Ransom" \
<rransom.8774@gmail.com<mailto:rransom.8774@gmail.com>> wrote:
draft-hao-schnorr-00 is incorrectly labeled as describing the ‘Schnorr
signature’. The protocol it describes is a non-interactive proof of
knowledge of a discrete logarithm, as required by J-PAKE (and other
protocols); the Schnorr signature IS NOT a proof of knowledge.
Yes, I understand your concern. The term schnorr signature is often used
in the literature to mean two different things: the digital signature obtained from \
the schnorr signing algorithm and the non-interactive ZKP.
I had wanted to make it clear and explicit in the title that it refers to the latter, \
but I understand your point that it can still cause confusion. I've changed "Schnorr \
signature" to "Schnorr NIZK Proof", and have made other changes in both the Schnorr \
and J-PAKE I-Ds to make everything consistent, including changing SignerID to UserID.
http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-schnorr-01-temp.html
http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-jpake-01-temp.html
I haven't uploaded them to IETF yet. I'm waiting to see if you (and others) have more \
comments, so that I can make changes in one go.
(Hope you don't mind - I added your name in the acknowledgement.)
In the notation used in the draft, the original Schnorr signature (as
described by Wikipedia, ‘Applied Cryptography’, and a PDF file from
somewhere on the Internet claiming to be a 1991 paper by Schnorr) uses
h = H(Message || g^v). With that choice of h, an attacker can choose
V with unknown discrete logarithm, choose r and Message arbitrarily,
and compute the X for which the signature is valid; the attacker (and
anyone else who sees the signature) will know the discrete logarithm
of X with respect to V, but not with respect to g.
I suggest replacing “Schnorr signature” with “Schnorr proof of
knowledge” in the titles of Section 4 and the draft itself, and adding
text in the draft warning about the difference between the PoK and the
original signature scheme, to try to reduce the risk that someone will
break a protocol by substituting the original (non-PoK) Schnorr
signature for the PoK you are describing.
I've replaced "Schnorr signature" with "Schnorr NIZK Proof" and added text to warn \
the difference between the PoK and the original Schnorr signature scheme. The \
difference is actually subtle, but worth mentioning, as you suggested.
(I don't believe that using the original Schnorr signature in J-PAKE
would break J-PAKE's security, but it's certainly not a good thing to
do.)
Yes, it shouldn't. Alternatively, you could use DSA for the proof of knowledge of the \
discrete logarithm. Think about the self-signed Certificate Signing Request that you \
can generate from OpenSSL using DSA. Checking the CSR is equivalent to verifying the \
proof-of-possession of the private key.
So there are more than one way to verify the knowledge (or possession) of a private \
key. The Schnorr NIZK is just one of them. I prefer it only because it has \
easy-to-understand and widely accepted security proofs.
The draft must specify that implementations MUST choose v *uniformly*
at random from Z/qZ,
OK. I changed "at random" to "uniformly at random". There is not much difference in \
the meaning, but being more explicit is good.
and MUST NOT use the same v for more than one
signature. (See section 2, subsection ‘Pseudorandom generation of r’
(on pages 8 and 9) of <http://ed25519.cr.yp.to/ed25519-20110926.pdf>
for reasons and references.)
Using a fixed v rather than at random is one of the native mistakes (one that was \
seen in the sony PS). But there are many other ways to make native implementation \
errors. We cannot enumerate all such in the I-D. I think stating that v must be \
chosen uniformly at random should be sufficiently clear.
The draft should specify that
implementations which use long-term signing keys SHOULD arrange to
generate v in a secretly deterministic manner, and protocols in which
long-term signing keys may need to be interoperable between
implementations MUST specify the details of deterministic generation
of v and storage and transport of any extra key material required for
that purpose.
Thanks for the suggestion. However, I feel these are outside the scope for this I-D. \
The secure implementation of a random number generator, and the key management of the \
long-term private key (which will probably need a HSM) are important, but do not seem \
very relevant to the discussion of the how to prove the knowledge of a discrete \
logarithm. These should not affect the interoperability.
I hope I have addressed all your concerns. But if not, please feel free to let me \
know. Thanks for your constructive comments.
Robert Ransom
[Attachment #3 (text/html)]
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: \
after-white-space; color: rgb(0, 0, 0); font-size: 14px; font-family: Calibri, \
sans-serif; "> <div>Hi Robert,</div>
<div><br>
</div>
<div>Thanks for the suggestions. My response is interleaved below.</div>
<div><br>
</div>
<div>On 03/12/2013 23:35, "Robert Ransom" <<a \
href="mailto:rransom.8774@gmail.com">rransom.8774@gmail.com</a>> wrote:</div> \
<div><br> </div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div>draft-hao-schnorr-00 is incorrectly \
labeled as describing the ‘Schnorr</div> <div>signature’. The protocol it \
describes is a non-interactive proof of</div> <div>knowledge of a discrete logarithm, \
as required by J-PAKE (and other</div> <div>protocols); the Schnorr signature IS NOT \
a proof of knowledge.</div> </blockquote>
<div><br>
</div>
<div><br>
</div>
<div>Yes, I understand your concern. The term schnorr signature is often \
used </div> <div>in the literature to mean two different things: the digital \
signature obtained from the schnorr signing algorithm and the non-interactive \
ZKP. </div> <div><br>
</div>
<div>I had wanted to make it clear and explicit in the title that it refers to the \
latter, but I understand your point that it can still cause confusion. I've changed \
"Schnorr signature" to "Schnorr NIZK Proof", and have made other \
changes in both the Schnorr and J-PAKE I-Ds to make everything consistent, including \
changing SignerID to UserID.</div> <div><br>
</div>
<div><a href="http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-schnorr-01-temp.h \
tml">http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-schnorr-01-temp.html</a></div>
<div><br>
</div>
<div><a href="http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-jpake-01-temp.htm \
l">http://homepages.cs.ncl.ac.uk/feng.hao/files/draft-hao-jpake-01-temp.html</a></div>
<div><br>
</div>
<div>I haven't uploaded them to IETF yet. I'm waiting to see if you (and others) have \
more comments, so that I can make changes in one go.</div> <div><br>
</div>
<div>(Hope you don't mind - I added your name in the acknowledgement.)</div>
<div><br>
</div>
<div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div>In the notation used in the draft, the \
original Schnorr signature (as</div> <div>described by Wikipedia, ‘Applied \
Cryptography’, and a PDF file from</div> <div>somewhere on the Internet claiming to \
be a 1991 paper by Schnorr) uses</div> <div>h = H(Message || g^v). With \
that choice of h, an attacker can choose</div> <div>V with unknown discrete \
logarithm, choose r and Message arbitrarily,</div> <div>and compute the X for which \
the signature is valid; the attacker (and</div> <div>anyone else who sees the \
signature) will know the discrete logarithm</div> <div>of X with respect to V, but \
not with respect to g.</div> <div><br>
</div>
<div>I suggest replacing “Schnorr signature” with “Schnorr proof of</div>
<div>knowledge” in the titles of Section 4 and the draft itself, and adding</div>
<div>text in the draft warning about the difference between the PoK and the</div>
<div>original signature scheme, to try to reduce the risk that someone will</div>
<div>break a protocol by substituting the original (non-PoK) Schnorr</div>
<div>signature for the PoK you are describing.</div>
</blockquote>
<div><br>
</div>
<div>I've replaced "Schnorr signature" with "Schnorr NIZK Proof" \
and added text to warn the difference between the PoK and the original Schnorr \
signature scheme. The difference is actually subtle, but worth mentioning, as you \
suggested.</div> <div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div><br>
</div>
<div>(I don't believe that using the original Schnorr signature in J-PAKE</div>
<div>would break J-PAKE's security, but it's certainly not a good thing to</div>
<div>do.)</div>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div>Yes, it shouldn't. Alternatively, you could use DSA for the proof of knowledge \
of the discrete logarithm. Think about the self-signed Certificate Signing \
Request that you can generate from OpenSSL using DSA. Checking the CSR is equivalent \
to verifying the proof-of-possession of the private key. </div>
<div><br>
</div>
<div>So there are more than one way to verify the knowledge (or possession) of a \
private key. The Schnorr NIZK is just one of them. I prefer it only because it has \
easy-to-understand and widely accepted security proofs.</div> <div><br>
</div>
<div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div>The draft must specify that \
implementations MUST choose v *uniformly*</div> <div>at random from Z/qZ, </div>
</blockquote>
<div><br>
</div>
<div>OK. I changed "at random" to "uniformly at random". There is \
not much difference in the meaning, but being more explicit is good.</div> <div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div>and MUST NOT use the same v for more \
than one</div> <div>signature. (See section 2, subsection ‘Pseudorandom \
generation of r’</div> <div>(on pages 8 and 9) of <<a \
href="http://ed25519.cr.yp.to/ed25519-20110926.pdf">http://ed25519.cr.yp.to/ed25519-20110926.pdf</a>></div>
<div>for reasons and references.) </div>
</blockquote>
<div><br>
</div>
<div>Using a fixed v rather than at random is one of the native mistakes (one that \
was seen in the sony PS). But there are many other ways to make native implementation \
errors. We cannot enumerate all such in the I-D. I think stating that v must be \
chosen uniformly at random should be sufficiently clear.</div>
<div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div>The draft should specify that</div>
<div>implementations which use long-term signing keys SHOULD arrange to</div>
<div>generate v in a secretly deterministic manner, and protocols in which</div>
<div>long-term signing keys may need to be interoperable between</div>
<div>implementations MUST specify the details of deterministic generation</div>
<div>of v and storage and transport of any extra key material required for</div>
<div>that purpose.</div>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div>Thanks for the suggestion. However, I feel these are outside the scope for this \
I-D. The secure implementation of a random number generator, and the key management \
of the long-term private key (which will probably need a HSM) are important, but do \
not seem very relevant to the discussion of the how to prove the knowledge of a \
discrete logarithm. These should not affect the interoperability. </div> \
<div><br> </div>
<div>I hope I have addressed all your concerns. But if not, please feel free to let \
me know. Thanks for your constructive comments.</div> <div><br>
</div>
<blockquote id="MAC_OUTLOOK_ATTRIBUTION_BLOCKQUOTE" style="BORDER-LEFT: #b5c4df 5 \
solid; PADDING:0 0 0 5; MARGIN:0 0 0 5;"> <div><br>
</div>
<div><br>
</div>
<div>Robert Ransom</div>
<div><br>
</div>
</blockquote>
</body>
</html>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic