From: Dan Brown <dbrown@certicom.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: Schnorr just as vulnerable to bad RNG
Thread-Index: Ac+oCs6QZBW0IZyiTTSZYsiyVXkKCw==
Date: Fri, 25 Jul 2014 13:17:38 +0000
Message-ID: <20140725131738.6639765.60290.17138@certicom.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature";
 micalg=SHA1; boundary="===============1966393139=="
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/K-UhIP_nonLglY0-Y2pRjssTK1E
Subject: [Cfrg] Schnorr just as vulnerable to bad RNG
Precedence: list

--===============1966393139==
Content-Type: multipart/alternative; boundary="===============0873880686=="
MIME-Version: 1.0

--===============0873880686==
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: base64

4oCOSW4gdGhlIFNBQUcgbWVldGluZyB5ZXN0ZXJkYXksIGl0IHdhcyBzdWdnZXN0ZWQgdGhhdCBT
Y2hub3JyIHNpZ25hdHVyZXMgYmV0dGVyIHJlc2lzdCBiYWQgUk5HIHRoYW4gRUNEU0EsIGNpdGlu
ZyBhIGZsYXdlZCBFQ0RTQSBpbXBsZW1lbnRhdGlvbi7CoAoKSnVzdCBsaWtlIChFQylEU0EsIGlm
IHRoZSBlcGhlbWVyYWwga2V5IGlzIGV4cG9zZWQgb3IgcmVwZWF0ZWQsIHRoZW4gdGhlIFNjaG5v
cnIgc3RhdGljIGtleSBpcyBleHBvc2VkLCB3aGljaCB0aGVuIGNhbiBsZWFkIHRvIGZvcmdlcnku
CgpTbyB0aGlzIG9uZSBpbXBsZW1lbnRhdGlvbiBmYWlsdXJlIGlzIG5vdCBhIHJlYXNvbiB0byBw
cmVmZXIgU2Nobm9yciBzaWduYXR1cmVzLCBhcyBhbiBhbGdvcml0aG0uwqAKClRoZSBpbXBvcnRh
bmNlIG9mIHByb3BlciBlcGhlbWVyYWwga2V5IGdlbmVyYXRpb24gaXMgd2h5IEFOU0nigI4gWDku
NjItMjAwNSBmb3IgRUNEU0EgYWRkZWQgYSByZXF1aXJlbWVudCAobm90IGluIHRoZTE5OTggdmVy
c2lvbikgdGhhdCB0aGUgZXBoZW1lcmFsIGtleSBiZSBnZW5lcmF0ZWQgdXNpbmcgSE1BQyBEUkJH
IGFuZCB0aGF0IGl0IGJlIHByb3Blcmx5IHNlZWRlZCwgb3IgZWxzZSB1c2UgYW5vdGhlciBBTlNJ
IGFwcHJvdmVkIFJORy4gVGhlIDE5OTggdmVyc2lvbiBpbnN0ZWFkIHNhaWQgc29tZXRoaW5nIGxp
a2UgdW5pcXVlIGFuZCB1bnByZWRpY3RhYmxlLsKgCgpTb21lIHBlb3BsZSBwcm9wb3NlIHVzaW5n
IGRlcml2aW5nIHRoZSBlcGhlbWVyYWxzIGZyb20gdGhlIG1lc3NhZ2UgYW5kIGEgbG9uZyB0ZXJt
IGtleS4gVGhpcyBkb2VzIG5vdCBzZWVtIGFueSBiZXR0ZXIgYXMgYW4gYWxnb3JpdGhtIHRoYW4g
dGhlIERSQkcgYXBwcm9hY2gsIHByb3ZpZGVkIHRoZSBYOS42MiBhbGdvcml0aG0gaXMgYWRoZXJl
ZCB0by4KClRoZXJlJ3MgYW4gUkZDIG1lbGRpbmcgYm90aCB0aGVzZSBpZGVhcywgYnV0IHRoYXQg
aXMgdHJ5aW5nIGZpeCBzb21ldGhpbmcgdGhhdCBpcyBub3QgYnJva2VuLCBhdCB0aGUgYWxnb3Jp
dGhtIGxldmVsLgoKSWYgYSBmbGF3ZWQgaW1wbGVtZW50YXRpb24gdXNlcyBhIERSQkcgaW4gY29t
cGxpYW5jZSB3aXRoIFg5LjYyLTIwMDUsIGJ1dCBmYWlscyB0byB1cGRhdGUgRFJCRyBzdGF0ZSBm
YWlscyBiZXR3ZWVuIHNpZ25lZCBtZXNzYWdlc+KAjiwgdGhlbiB0aGUgc2lnbmluZyBrZXkgaXMg
bGVha2VkLiBJZiBhIGZsYXdlZCBpbXBsZW1lbnRhdGlvbiBvcHRzIHRvIGFsc28gdXNlIGRldGVy
bWluaXN0aWMgZXBoZW1lcmFsIGtleXMgZm9yIGVuY3J5cHRpb24sIHRoZW4gcmVwZWF0ZWQgbWVz
c2FnZXMgbGVhayBpbmZvIHZpYSByZXBlYXRlZCBjaXBoZXJ0ZXh0cy4gwqBTbywgc3RhbmRhcmRz
IHNob3VsZCBhbXBseSB3YXJuIGltcGxlbWVudGVycyBpZiB0aGVzZSBwaXRmYWxscy7CoAoKU28g
SSB0aGluayB0aGVyZSBhcmUgaXNzdWVzIHdpdGggZWFzZSBvZiBpbXBsZW1lbnRhdGlvbiwgY2xh
cml0eSBvZiBzdGFuZGFyZHMsIGFuZCBtYWtpbmcgc3RhbmRhcmRzIMKgZXJyb3IgcmVzaXN0YW50
LCBidXQgdGhlIGFsZ29yaXRobSBzZWN1cml0eSBpcyBub3Qgc2lnbmlmaWNhbnQuCgpJbiB0aGVv
cnksIHNvbWUgc2VjdXJpdHkgcHJvb2ZzLCBtYXkgZ2l2ZSBkaWZmZXJlbnQgYXNzdXJhbmNlcywg
ZGVwZW5kaW5nIG9uIHRoZSBkZXRlcm1pbmlzbSwgYnV0IEknbGwgZGVmZXIgdGhhdCBpc3N1ZSB0
byBmdXR1cmUgZGlzY3Vzc2lvbi7CoAoK4oCOUHJvY2VkdXJhbGx5LCBJIHRoaW5rIHNpZ25hdHVy
ZSBhbGdvcml0aG0gY2hvaWNlLCBhbmQgbWV0aG9kIHRvIGdlbmVyYXRlIGVwaGVtZXJhbHMgaXMg
YSBDRlJHIGlzc3VlLCBub3QgYSBTQUFHIGlzc3VlLgoKQmVzdCByZWdhcmRzLCAKCi0tIERhbg==

--===============0873880686==
Content-Type: text/html; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/plain;"><styl=
e> body {  font-family: "Calibri","Slate Pro","sans-serif"; color:#262626 }=
</style> </head> <body data-blackberry-caret-color=3D"#00a8df"><div>=E2=80=
=8EIn the SAAG meeting yesterday, it was suggested that Schnorr signatures =
better resist bad RNG than ECDSA, citing a flawed ECDSA implementation.&nbs=
p;</div><div><br></div><div>Just like (EC)DSA, if the ephemeral key is expo=
sed or repeated, then the Schnorr static key is exposed, which then can lea=
d to forgery.</div><div><br></div><div>So this one implementation failure i=
s not a reason to prefer Schnorr signatures, as an algorithm.&nbsp;</div><d=
iv><br name=3D"BB10" caretmarkerset=3D"INVALID" class=3D"markedForCaretMark=
erRemoval"></div><div>The importance of proper ephemeral key generation is =
why ANSI=E2=80=8E X9.62-2005 for ECDSA added a requirement (not in the1998 =
version) that the ephemeral key be generated using HMAC DRBG and that it be=
 properly seeded, or else use another ANSI approved RNG. The 1998 version i=
nstead said something like unique and unpredictable.&nbsp;</div><div><br></=
div><div>Some people propose using deriving the ephemerals from the message=
 and a long term key. This does not seem any better as an algorithm than th=
e DRBG approach, provided the X9.62 algorithm is adhered to.</div><div><br =
name=3D"BB10" caretmarkerset=3D"INVALID" class=3D"markedForCaretMarkerRemov=
al"></div><div>There's an RFC melding both these ideas, but that is trying =
fix something that is not broken, at the algorithm level.</div><div><br nam=
e=3D"BB10" caretmarkerset=3D"INVALID" class=3D"markedForCaretMarkerRemoval"=
></div><div>If a flawed implementation uses a DRBG in compliance with X9.62=
-2005, but fails to update DRBG state fails between signed messages=E2=80=
=8E, then the signing key is leaked. If a flawed implementation opts to als=
o use deterministic ephemeral keys for encryption, then repeated messages l=
eak info via repeated ciphertexts. &nbsp;So, standards should amply warn im=
plementers if these pitfalls.&nbsp;</div><div><br name=3D"BB10" caretmarker=
set=3D"INVALID" class=3D"markedForCaretMarkerRemoval"></div><div>So I think=
 there are issues with ease of implementation, clarity of standards, and ma=
king standards &nbsp;error resistant, but the algorithm security is not sig=
nificant.</div><div><span style=3D"font-family: Calibri, 'Slate Pro', sans-=
serif;"><br></span></div><div><span style=3D"font-family: Calibri, 'Slate P=
ro', sans-serif;">In theory, some security proofs, may give different assur=
ances, depending on the determinism, but I'll defer that issue to future di=
scussion.&nbsp;</span></div><div><br name=3D"BB10" caretmarkerset=3D"INVALI=
D" class=3D"markedForCaretMarkerRemoval"></div><div>=E2=80=8EProcedurally<s=
pan style=3D"font-family: Calibri, 'Slate Pro', sans-serif;">, I think sign=
ature algorithm choice, and method to generate ephemerals is a CFRG issue, =
not a SAAG issue.</span></div><div><br name=3D"BB10" caretmarkerset=3D"INVA=
LID" class=3D"markedForCaretMarkerRemoval"></div><div>Best regards, <br><br=
>-- Dan</div></body></html>
--===============0873880686==--

--===============1966393139==
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
MIME-Version: 1.0
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"

MIAGCSqGSIb3DQEHAqCAMIACAQExCTAHBgUrDgMCGjCABgkqhkiG9w0BBwEAAKCCDSYwggaPMIIF
d6ADAgECAgptqd1HAAQAAAVqMA0GCSqGSIb3DQEBBQUAMFAxEzARBgoJkiaJk/IsZAEZFgNuZXQx
EzARBgoJkiaJk/IsZAEZFgNyaW0xJDAiBgNVBAMTG1JJTSBTdWJvcmRpbmF0ZSBDQSBNQ0EwMllL
RjAeFw0xNDA1MTQxNDM2MzhaFw0xNTA1MTQxNDM2MzhaMIGkMRMwEQYKCZImiZPyLGQBGRYDbmV0
MRMwEQYKCZImiZPyLGQBGRYDcmltMQ0wCwYDVQQLEwRBTUVSMQswCQYDVQQLEwJDQTEUMBIGA1UE
CxMLTWlzc2lzc2F1Z2ExDjAMBgNVBAsTBVVzZXJzMRIwEAYDVQQDEwlEYW4gQnJvd24xIjAgBgkq
hkiG9w0BCQEWE2Ricm93bkBjZXJ0aWNvbS5jb20wgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGB
AOeGGgTmotlA0vPS6BzGw3AuPnPHRJeU6ZCVs9Jrqo51z+saUmKgc6LbMPUqTw9/9MBfA8++2YZG
DfAQ0hdEQHbZn1yl3uNLUJB6KZTeKaLPY5wWVuXvB7k2VJBFQv6u239/fXLJKcTLfTAPd+ILwa0p
NUDW0dw+x6t+LeGzh10lAgMBAAGjggOYMIIDlDALBgNVHQ8EBAMCBaAwRAYJKoZIhvcNAQkPBDcw
NTAOBggqhkiG9w0DAgICAIAwDgYIKoZIhvcNAwQCAgCAMAcGBSsOAwIHMAoGCCqGSIb3DQMHMBcG
CSsGAQQBgjcUAgQKHggAVQBzAGUAcjApBgNVHSUEIjAgBgorBgEEAYI3CgMEBggrBgEFBQcDBAYI
KwYBBQUHAwIwQQYDVR0RBDowOKAhBgorBgEEAYI3FAIDoBMMEWRhbmlicm93bkByaW0ubmV0gRNk
YnJvd25AY2VydGljb20uY29tMB0GA1UdDgQWBBRXRa7o6+S8jBmtx5dVODE45RLX7zAfBgNVHSME
GDAWgBTm268lUmBC9I2CNVRdgOuGoazv3DCCATEGA1UdHwSCASgwggEkMIIBIKCCARygggEYhoHL
bGRhcDovLy9DTj1SSU0lMjBTdWJvcmRpbmF0ZSUyMENBJTIwTUNBMDJZS0YsQ049TUNBMDJZS0Ys
Q049Q0RQLENOPVB1YmxpYyUyMEtleSUyMFNlcnZpY2VzLENOPVNlcnZpY2VzLENOPUNvbmZpZ3Vy
YXRpb24sREM9d2luZG93cyxEQz1sb2NhbD9jZXJ0aWZpY2F0ZVJldm9jYXRpb25MaXN0P2Jhc2U/
b2JqZWN0Q2xhc3M9Y1JMRGlzdHJpYnV0aW9uUG9pbnSGSGh0dHA6Ly9tY2EwMnlrZi5yaW0ubmV0
L0NlcnRFbnJvbGwvUklNJTIwU3Vib3JkaW5hdGUlMjBDQSUyME1DQTAyWUtGLmNybDCCAUEGCCsG
AQUFBwEBBIIBMzCCAS8wgcIGCCsGAQUFBzAChoG1bGRhcDovLy9DTj1SSU0lMjBTdWJvcmRpbmF0
ZSUyMENBJTIwTUNBMDJZS0YsQ049QUlBLENOPVB1YmxpYyUyMEtleSUyMFNlcnZpY2VzLENOPVNl
cnZpY2VzLENOPUNvbmZpZ3VyYXRpb24sREM9d2luZG93cyxEQz1sb2NhbD9jQUNlcnRpZmljYXRl
P2Jhc2U/b2JqZWN0Q2xhc3M9Y2VydGlmaWNhdGlvbkF1dGhvcml0eTBoBggrBgEFBQcwAoZcaHR0
cDovL21jYTAyeWtmLnJpbS5uZXQvQ2VydEVucm9sbC9NQ0EwMllLRi5yaW0ubmV0X1JJTSUyMFN1
Ym9yZGluYXRlJTIwQ0ElMjBNQ0EwMllLRig0KS5jcnQwDQYJKoZIhvcNAQEFBQADggEBAHLQZIa8
qzIefgvvGIjq0fMYvhtTZFMnHzS7s+H2HUMxTQfclsckbNitMnZdF+T2V3o4WyIn9HRaMmsZ4YPw
+YWH3hiIV3wDhRtthKTCVl1Tmr6mC8bJZ3Nnp4oVgGHFpIz3xOrX91zF5KHRZDGLxHfqhY/HlL8W
23EdXQaogRTTQ3CpQCp/6BJaf4iPy41BjBG/rSXR7bbBhMb0M0ndc8JNVOnDop2A/NmNPMwOW89/
JeWxNvqZZn19xEPLwimAPeabIBoN4bH359edLJqWOx3hDxkWYfb4JRn4tsJzKmP0IDvqrO/Hajvw
tW3t6rkFN1h0OmHGa9yT9UXO8o++iu4wggaPMIIFd6ADAgECAgptqd1HAAQAAAVqMA0GCSqGSIb3
DQEBBQUAMFAxEzARBgoJkiaJk/IsZAEZFgNuZXQxEzARBgoJkiaJk/IsZAEZFgNyaW0xJDAiBgNV
BAMTG1JJTSBTdWJvcmRpbmF0ZSBDQSBNQ0EwMllLRjAeFw0xNDA1MTQxNDM2MzhaFw0xNTA1MTQx
NDM2MzhaMIGkMRMwEQYKCZImiZPyLGQBGRYDbmV0MRMwEQYKCZImiZPyLGQBGRYDcmltMQ0wCwYD
VQQLEwRBTUVSMQswCQYDVQQLEwJDQTEUMBIGA1UECxMLTWlzc2lzc2F1Z2ExDjAMBgNVBAsTBVVz
ZXJzMRIwEAYDVQQDEwlEYW4gQnJvd24xIjAgBgkqhkiG9w0BCQEWE2Ricm93bkBjZXJ0aWNvbS5j
b20wgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBAOeGGgTmotlA0vPS6BzGw3AuPnPHRJeU6ZCV
s9Jrqo51z+saUmKgc6LbMPUqTw9/9MBfA8++2YZGDfAQ0hdEQHbZn1yl3uNLUJB6KZTeKaLPY5wW
VuXvB7k2VJBFQv6u239/fXLJKcTLfTAPd+ILwa0pNUDW0dw+x6t+LeGzh10lAgMBAAGjggOYMIID
lDALBgNVHQ8EBAMCBaAwRAYJKoZIhvcNAQkPBDcwNTAOBggqhkiG9w0DAgICAIAwDgYIKoZIhvcN
AwQCAgCAMAcGBSsOAwIHMAoGCCqGSIb3DQMHMBcGCSsGAQQBgjcUAgQKHggAVQBzAGUAcjApBgNV
HSUEIjAgBgorBgEEAYI3CgMEBggrBgEFBQcDBAYIKwYBBQUHAwIwQQYDVR0RBDowOKAhBgorBgEE
AYI3FAIDoBMMEWRhbmlicm93bkByaW0ubmV0gRNkYnJvd25AY2VydGljb20uY29tMB0GA1UdDgQW
BBRXRa7o6+S8jBmtx5dVODE45RLX7zAfBgNVHSMEGDAWgBTm268lUmBC9I2CNVRdgOuGoazv3DCC
ATEGA1UdHwSCASgwggEkMIIBIKCCARygggEYhoHLbGRhcDovLy9DTj1SSU0lMjBTdWJvcmRpbmF0
ZSUyMENBJTIwTUNBMDJZS0YsQ049TUNBMDJZS0YsQ049Q0RQLENOPVB1YmxpYyUyMEtleSUyMFNl
cnZpY2VzLENOPVNlcnZpY2VzLENOPUNvbmZpZ3VyYXRpb24sREM9d2luZG93cyxEQz1sb2NhbD9j
ZXJ0aWZpY2F0ZVJldm9jYXRpb25MaXN0P2Jhc2U/b2JqZWN0Q2xhc3M9Y1JMRGlzdHJpYnV0aW9u
UG9pbnSGSGh0dHA6Ly9tY2EwMnlrZi5yaW0ubmV0L0NlcnRFbnJvbGwvUklNJTIwU3Vib3JkaW5h
dGUlMjBDQSUyME1DQTAyWUtGLmNybDCCAUEGCCsGAQUFBwEBBIIBMzCCAS8wgcIGCCsGAQUFBzAC
hoG1bGRhcDovLy9DTj1SSU0lMjBTdWJvcmRpbmF0ZSUyMENBJTIwTUNBMDJZS0YsQ049QUlBLENO
PVB1YmxpYyUyMEtleSUyMFNlcnZpY2VzLENOPVNlcnZpY2VzLENOPUNvbmZpZ3VyYXRpb24sREM9
d2luZG93cyxEQz1sb2NhbD9jQUNlcnRpZmljYXRlP2Jhc2U/b2JqZWN0Q2xhc3M9Y2VydGlmaWNh
dGlvbkF1dGhvcml0eTBoBggrBgEFBQcwAoZcaHR0cDovL21jYTAyeWtmLnJpbS5uZXQvQ2VydEVu
cm9sbC9NQ0EwMllLRi5yaW0ubmV0X1JJTSUyMFN1Ym9yZGluYXRlJTIwQ0ElMjBNQ0EwMllLRig0
KS5jcnQwDQYJKoZIhvcNAQEFBQADggEBAHLQZIa8qzIefgvvGIjq0fMYvhtTZFMnHzS7s+H2HUMx
TQfclsckbNitMnZdF+T2V3o4WyIn9HRaMmsZ4YPw+YWH3hiIV3wDhRtthKTCVl1Tmr6mC8bJZ3Nn
p4oVgGHFpIz3xOrX91zF5KHRZDGLxHfqhY/HlL8W23EdXQaogRTTQ3CpQCp/6BJaf4iPy41BjBG/
rSXR7bbBhMb0M0ndc8JNVOnDop2A/NmNPMwOW89/JeWxNvqZZn19xEPLwimAPeabIBoN4bH359ed
LJqWOx3hDxkWYfb4JRn4tsJzKmP0IDvqrO/HajvwtW3t6rkFN1h0OmHGa9yT9UXO8o++iu4xggFf
MIIBWwIBATBeMFAxEzARBgoJkiaJk/IsZAEZFgNuZXQxEzARBgoJkiaJk/IsZAEZFgNyaW0xJDAi
BgNVBAMTG1JJTSBTdWJvcmRpbmF0ZSBDQSBNQ0EwMllLRgIKbandRwAEAAAFajAHBgUrDgMCGqBd
MBgGCSqGSIb3DQEJAzELBgkqhkiG9w0BBwEwHAYJKoZIhvcNAQkFMQ8XDTE0MDcyNTEzMTczNlow
IwYJKoZIhvcNAQkEMRYEFGRvWYd1blA4KeOtNWtmhteEJdaTMAsGCSqGSIb3DQEBBQSBgNEYTMP8
q8bp/0Q9EGqkno83GEfJ2sVFNWorJI9HT7iOdUsaHbPpiVdgeuHNeBMTwo2J47ltCEQxjZNqbLI2
SA4SMGB3egM2NQ52M002iwySkGRfskieZlqIBp5zk8p4yk4FIsr0OPHP9DRNoRLNWVQKK+pmPDhq
HiPKBXczaWpyAAAAAAAA

--===============1966393139==--