Subject: Re: Signing and Encrypting with the same key?

From: [email-masked] (Peter Gutmann)
Date: Sun, 02 Nov 2008 16:14:40 +1300

Julien Stern <[email-masked]> writes:

>As far as I remember, there are no known attacks, but there aren't any 
>proofs that it does not weaken security (actually, I believe someone 
>published a paper with some hints that there may be a theoretical 
>weakness, but that was really long time ago, maybe someone else would know).

There are a pile of fault attacks (that's including inadvertent memory 
corruption in the category of "attacks", so it's something that can happen 
without any overt attack) that will leak the private key on signing but not on 
decrypt, so technically there are known attacks that'll exploit the same key 
being used for signing and decryption.

Peter.

---

From: "Anders Rundgren" <[email-masked]>
Date: Sun, 2 Nov 2008 10:11:04 +0100

Peter,
If we put implementation errors aside and only look on the mathematical side of things, could you
please comment on the following?

First the use-case:  This discussion is about the possible (mis) use of a single embedded (device)
private key in a cryptographic container along the lines shown in this document:
http://keycenter.webpki.org/javadoc/keystore/phone/keystore/crypto/VirtualSE.html
http://webpki.org/papers/keygen2/keygen-all-protocol-steps.html

Thesis: "You shouldn't use a signing key for encryption" which is (with other wording) stated in
NIST's SP 800-57.

There appears to be three possibilities for this position.
1. Signatures could be forged and/or private keys could be revealed
2. Encryption keys may be backed-up while signature keys may not
3. Encrypted data could be exposed in clear

We can safely drop #1 since there is no way you can prevent somebody from encrypting arbitrary data
with a public signature key.  If there actually is a problem here, we might as well quit using PKI
altogether!

Point #2 don't apply to device-keys.

So the remaining issue must be that encrypted data could be exposed in some way by "correlating"
encrypted data with signed data, right?

Why I am not that worried?  Well,

C1.  Signed and encrypted input data in KeyGen2 is always padded with PKCS 1 which means that the
raw decryption and encryption algorithms never operate on the same data even when the original data
actually is identical (see C2 and C3)

C2.  There is no correlation whatsoever between signed and encrypted input data in KeyGen2

C3.  Signed and encrypted input data in KeyGen2 requires crypto-level entropy making any kind of
correlation infeasible for practical purposes.  In fact, if the entropy is low, the integrity of the
whole scheme is jeopardized irrespective of other issues

P1.  Although a slightly lamer argument, in most (if not all) cases communications would take place
over HTTPS further reducing "leakage" and attack space

P2.  That many existing PKIs rely on universal keys, including VeriSign's e-mail PKI, is maybe not a
strong technical argument, but shows that commercial PKI vendors as well as enterprises are
concerned about the additional "fuzz" multiple keys introduce.

C = Crypto, P = Practice

Comments are welcome!  I don't claim to have all the answers, but quite a few questions...

Regards
Anders R
----- Original Message ----- 
From: "Peter Gutmann" <[email-masked]>
To: <[email-masked]>; <[email-masked]>
Sent: Sunday, November 02, 2008 04:14
Subject: Re: Signing and Encrypting with the same key?

Peter.

---

From: "Manger, James H" <[email-masked]>
Date: Mon, 3 Nov 2008 10:48:01 +1100

Anders,

Daniel Bleichenbacher's "million message attack" showed how RSA encryption according to PKCS#1 v1.5 block-type 2 padding could be attacked by sending about a million chosen ciphertexts to a TLS (eg HTTPS) server. The result was recovery of one encrypted session key.

A variation on the attack allows a signature to be forged. An attacker chooses the message they want signed, sends about a million ciphertexts to a TLS server, and by watching the responses can forge the signature.

This attack showed that a weakness in an encryption algorithm can lead to exploits against a signature algorithm (that was otherwise "safe") if the same key is used with both.

James Manger

See RFC 3218 "Preventing the Million Message Attack on CMS" -- though it does not discuss the signature-forging aspect.

---

From: "Anders Rundgren" <[email-masked]>
Date: Mon, 3 Nov 2008 09:38:51 +0100

James,
Thank you for the MMA references!

Although I'm not an expert in cryptography (which is the reason I asked for assistance from the 
crypto collective), I have based on published reports found that the mentioned algorithm still is 
used by most TLS implementations because the MMA attacks were enabled by somewhat "unsuspicious" 
server code which subsequently has been corrected, right?

In the use-case I have described (which is very different to TLS), there is as I have pointed out, 
no persistent data whatsoever to encrypt or sign, which (in my maybe overly naive world), should 
make a difference.

In addition, the key in question would during its life-time seldom or never exceed a few thousand 
uses because there is a limit to how many web-sites a user finds worth signing up to.  Yes, this 
piece (of junk?) is the first serious stab at retiring passwords as the primary authentication 
mechanism on the web by hosting all your credentials (except for a few specials like PIV)  in an 
NFC/WLAN-connected mobile phone.  I.e. it is a de-facto standard in early preparation, intended to 
be rolled-out in the same way as Microsoft has done with their brilliant Information Card 
initiative.  The scheme is of course fully compliant with Information Cards as well since fighting 
Microsoft is neither fun, nor possible.  That Microsoft is also experimenting with supporting 
virtual credit-cards doesn't make things less interesting.

The reason why I raised this open question is that multiple keys for user-key bootstrapping would 
effectively require standardization of associated certificates as well in order to regardless of 
operation, uniquely identify the crypto device.  Although indeed quite feasible, a multi-key 
approach greatly complicates the scheme and based on hands-on experience with Internet standards 
since 1995, I see that complexity is a major source to failure.  Less actually seems to be more :-)

Anders Rundgren

----- Original Message ----- 
From: "Manger, James H" <[email-masked]>
To: <[email-masked]>
Sent: Monday, November 03, 2008 00:48
Subject: RE: Signing and Encrypting with the same key?

Anders,

Daniel Bleichenbacher's "million message attack" showed how RSA encryption according to PKCS#1 v1.5 
block-type 2 padding could be attacked by sending about a million chosen ciphertexts to a TLS (eg 
HTTPS) server. The result was recovery of one encrypted session key.

A variation on the attack allows a signature to be forged. An attacker chooses the message they want 
signed, sends about a million ciphertexts to a TLS server, and by watching the responses can forge 
the signature.

This attack showed that a weakness in an encryption algorithm can lead to exploits against a 
signature algorithm (that was otherwise "safe") if the same key is used with both.

James Manger

See RFC 3218 "Preventing the Million Message Attack on CMS" -- though it does not discuss the 
signature-forging aspect.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Mon, 3 Nov 2008 09:32:07 -0500

There are several reasons due to which device keys are generally not
escrowed.

They are used in real-time communications which need not be recovered
(unlike e-mail).

The same key is used for both signing and encrypting.

The key may be used in cryptographic protocols that provide perfect
forward secrecy, rendering the escrow of the device key useless.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Timothy J. Miller
Sent: Monday, November 03, 2008 9:08 AM
To: Anders Rundgren
Cc: Peter Gutmann; [email-masked]
Subject: Re: Signing and Encrypting with the same key?

> 2. Encryption keys may be backed-up while signature keys may not

This is the NIST rationale, as I've understood it from 800-57's authors.

> Point #2 don't apply to device-keys.

That's an unwarranted assumption.  If the device key is used for 
encryption, then there's very likely a compelling enterprise need to 
escrow that key.

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Mon, 3 Nov 2008 08:08:28 -0600

-- Tim

---

From: "Timothy J. Miller" <[email-masked]>
Date: Mon, 3 Nov 2008 08:55:54 -0600

Anders Rundgren wrote:

> The reason for having key escrow is to recover lost data.

Correct.

> If you feel that key-import (bootstrapping) keys also should be escrowable, I encourage you to 
> interact with these guys:

That depends on the *other* uses to which that key can be put, doesn't 
it?  If it's only used for bootstrapping, there's no escrow requirement. 
  But if the device API allows it to be accessed for other uses...?

-- Tim

---

From: "Anders Rundgren" <[email-masked]>
Date: Mon, 3 Nov 2008 16:31:14 +0100

<snip>
>  But if the device API allows it to be accessed for other uses...?

Tim,
I believe we are practically on the same page now :-)

The intention with the described scheme is that the device encryption key (be it specific or 
"universal") should not be exposed in the general pool of keys, but be limited to key-provisioning.

That it might be hard to thwart misuse in some operating systems is true, but for the primary target 
mobile phones, I don't expect any real problems since these systems anyway must support a more 
granular way of identifying software and capabilities, due to the lack of the concept User, Guest or 
Administrator when operating in the consumer space.  In practical terms that means that a software 
that wants to provision keys must be declared with that capability which in turn will require that 
it is signed by an external clearing house (or device vendor) rather than by a developer.

An app that "only" wants to use user-keys, probably will not need external signing, unless it wants 
to use keys in "silent mode", something that the key-provisioning system also can deal with on a 
per-key basis.

Oops, I slided off the core subject a bit, but you get the point; this is a [rather small but 
crucial] piece of a huge and quite interesting puzzle that a large number of people is working with, 
and mostly in a completely unsynchronized way...

Regards
Anders

---

From: "Anders Rundgren" <[email-masked]>
Date: Mon, 3 Nov 2008 15:43:46 +0100

Tim,

If you feel that key-import (bootstrapping) keys also should be escrowable, I encourage you to 
interact with these guys:
https://www.trustedcomputinggroup.org/specs/TPM
Since they need a whopping 700 pages just for describing the API, they should be able to cope *any* 
requirement.

Another reference is OASIS EKMI:
http://www.oasis-open.org/committees/download.php/28657/SKSML-1.0-Specification-Non-Normative-DRAFT6.pdf
>From what I can deduct they indeed authenticate the requesting client through a signature and then
return the key by wrapping it by the public signature key.

Anders

----- Original Message ----- 
From: "Timothy J. Miller" <[email-masked]>
To: "Anders Rundgren" <[email-masked]>
Cc: "Peter Gutmann" <[email-masked]>; <[email-masked]>
Sent: Monday, November 03, 2008 15:08
Subject: Re: Signing and Encrypting with the same key?

-- Tim

---

From: Arshad Noor <[email-masked]>
Date: Tue, 04 Nov 2008 12:11:37 -0800

Anders,

Just to clarify, the SKSML protocol does not mandate how the
digital certificate of SKMS clients and servers should be
constructed, or what the keyUsage extension should look like
within such certificates.  We believe that that is an
implementation detail of the PKI that supports the SKMS.

The SKMS only requires that every client and server have a
signing key and an encryption key.  They can be the same
key-pair or two different key-pairs, depending on the PKI
certificate policy of the implementation site.

Within the open-source StrongKey software we have, we require
two digital certificates to be configured for SKMS clients and
servers, to separate signing and encryption uses.  The test
certs we bundle with the FOSS, combines signing & encryption
merely as a convenience for people "kicking the tires".

As a conservative practice, we recommend that PKIs separate
the signing and encryption capability into different digital
certificates.

Arshad Noor
StrongAuth, Inc.

---

From: "Anders Rundgren" <[email-masked]>
Date: Tue, 4 Nov 2008 22:08:01 +0100

Hi Arshad,
I just skimmed through the non-normative spec and example and from that I could not see any
mentioning of separate keys.

I digged a bit further but could still not find such references in:
http://www.oasis-open.org/committees/download.php/28725/SKSML-1.0-Specification-Normative-DRAFT6.0.pdf

I don't know what you have planned, but IMO you need additional elements in the protocol (like 
giving the client a place to put its encryption key), as well as a standard for how encryption and 
signature keys link together otherwise the server cannot be sure that it is encrypting for the 
client that authenticated.  All this is the reason why I'm not overly enthusiastic of having 
multiple entity-keys in a provisioning protocol, particularly since all attacks I have heard about 
to date, have been based on flawed implementations, which is moderately interesting from a 
*protocol-design* point-of-view:
http://www.imc.org/ietf-openpgp/mail-archive/msg14307.html

But it is possible that SKSML will run in more restricted environments than KeyGen2 and thus can 
build on that the client and servers use "conventions", keeping the protocol smallish.   KeyGen2 is 
designed to cope with a fragmented world and thus sports a capability/policy negotiation facility.

Anders

----- Original Message ----- 
From: "Arshad Noor" <[email-masked]>
To: "Anders Rundgren" <[email-masked]>
Cc: "Timothy J. Miller" <[email-masked]>; "Peter Gutmann" <[email-masked]>; 
<[email-masked]>
Sent: Tuesday, November 04, 2008 21:11
Subject: Re: Signing and Encrypting with the same key?

Anders,

Arshad Noor
StrongAuth, Inc.

---

From: Arshad Noor <[email-masked]>
Date: Tue, 04 Nov 2008 13:24:28 -0800

Hi Anders,

The reason we haven't mentioned it yet is because the TC is going
to begin the task of creating Implementation, Operations and Audit
Guidelines for EKMI only in 2009.  It is within these guidelines
where a recommendation for separating signing & encryption key-pairs
would be made.

The SKSML protocol focuses on the minimum necessary syntax to send
and receive messages related to symmetric-key management.  The
security, implementation, operations and audit of such Enterprise
Key Management Infrastructures must be capable of being abstracted
out of the protocol, layered and managed independently.  Which is
why there is no mention of separated key-pairs yet.  However, you
can expect to see it in the Guidelines next year.

Arshad Noor
StrongAuth, Inc.

---

From: "Anders Rundgren" <[email-masked]>
Date: Wed, 5 Nov 2008 09:54:30 +0100

Arshad,

Pardon my ignorance but I do not see how you can "abstract out" security solutions in a concrete 
SOAP specification, either it is there or it is not.  That is, with respect to the particular 
question and the current draft, you have no real alternative except stating that client and servers 
must be configured to support a common convention.  Which BTW may be exactly what you meant :-) 
That KeyGen2 is a 6-pass protocol is for avoiding conventions since the entities involved typically 
do not belong to the same "IT-domain".  E.g. a consumer with a mobile phone and his/her bank.

Regarding the separate key stuff, the current strategy is to support it in the protocol, but not in 
the Open Source client-implementation since no compelling argument actually has been raised for 
having multiple keys, while there is quite a bunch of arguments against such an arrangement.  How is 
an SKSML server supposed to know what to encrypt with if you do not send the key in the request?  It 
seems that an SKSML server must keep an encryption key database or be configured to use LDAP etc. 
It seems like a more straightforward solution to transfer encryption keys explicitly and validate 
them at receival in the same way as you do with signature and authentication keys.

I'm a bit puzzled regarding how you intend to bootstrap SKSML with PKI, if the figures with a myriad 
of entirely different clients are still valid.  The reason I started the KeyGen2 effort is because 
this is a veritable nightmare, particularly for mobile devices.  As a comparison I would like to 
mention the fact that there are some 100M TPM chips out there in major laptops, but they are "mostly 
of out work" because the bootstrapping issues haven't been fully addressed by the TPM designers.

Anders

----- Original Message ----- 
From: "Arshad Noor" <[email-masked]>
To: "Anders Rundgren" <[email-masked]>
Cc: "Timothy J. Miller" <[email-masked]>; "Peter Gutmann" <[email-masked]>; 
<[email-masked]>
Sent: Tuesday, November 04, 2008 22:24
Subject: Re: Signing and Encrypting with the same key?

Hi Anders,

Arshad Noor
StrongAuth, Inc.

---

From: Arshad Noor <[email-masked]>
Date: Wed, 05 Nov 2008 09:31:41 -0800

To paraphrase the Public Review 02 specification (which should be
available on the OASIS site by the end of this week):

"..conforming implementations of the SKSML protocol MUST enclose all 
SKSML messages between participants in an SKMS, in the SOAP Body of a 
SOAP Envelope.  Additionally, the contents of the SOAP Body MUST be 
secured using digital signatures conforming to [XMLSignature] in the 
SOAP Header.  Specifically, the SOAP Header of the SOAP Envelope MUST 
enclose a Security element conforming to [WSS] with a ValueType 
attribute containing the value 
http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-x509-token-profile-1.0#X509v3."

Yes, all SKMS clients and servers are mandated to use a certain security
convention in SOAP, but the SKSML message is oblivious of its envelope. 
  Secondly, how the digital certificates are constructed, how the client
and server key-pairs are managed, how the PKI is setup, managed and
audited, is not in the SKSML protocol.

That is what I meant by "abstracting the security, implementation,
operations and audit" of an EKMI out of the protocol.

Arshad Noor
StrongAuth, Inc.

---

From: "Anders Rundgren" <[email-masked]>
Date: Sat, 15 Nov 2008 12:34:13 +0100

Just a short iteration of this question:

If using a single key for authentication and encryption is a bad idea, how come that TLS after all 
these years still only relies on a single key-pair for authenticating the server as well as 
encrypting the channel?

Anders

---

From: Mike <[email-masked]>
Date: Sat, 15 Nov 2008 06:10:14 -0800

In a particular TLS cipher suite, a key is used for only one purpose,
either signing or encrypting, not both.  In the case of an RSA key
exchange, the act of encrypting the channel has the side effect of
authenticating the server, since the server can only decrypt the
secret if it has the private key.  In other exchanges, an RSA or DSA
key is used to sign some Diffie-Hellman parameters.  The signature
provides the authentication of the server, but the Diffie-Hellman
exchange encrypts the channel.

The issue you raise is whether you use the same RSA key for both
types of cipher suites; in pure RSA exchanges, the key is used for
encryption, and in Diffie-Hellman exchanges it is used for signing.
This is an implementation/configuration issue, not a problem with TLS.
It is possible for a server to use two different keys, but it is
easier (and cheaper) to just use one, so that's what lots of people
do.

Mike

---

From: Stephen Wilson <[email-masked]>
Date: Sun, 16 Nov 2008 01:34:05 +1100

And a short reiteration of what I thought was the answer:

Using the same key pair for signing and encryption (key exchange) is not 
cryptanalytically a bad idea.  Rather, it is merely convention dating 
back to the idea that backing up (or escrowing) keys used for encryption 
dilutes their value for authentication, because of the possibility that 
the extra copies might be used for signing things without the owner's 
permission.

So, if TLS uses the same key pair, it's not breaking any rules.

Cheers,

Steve Wilson.

PS. I actually always thought the argument for key separation was 
massively over-stated.  "Non repudiation" is one the greatest red 
herrings in the history of cryptography.  If someone uses my signing key 
without my permission, then I shouldn't be held accountable for that, if 
it can be shown that the usage was illicit.  Some jurisdictions grant an 
extra degree of 'attribution' when qualified digital signature devices 
are used, but as far as I know, the attribution is still not absolute. 
Rather, it's just a matter of onus of proof; if I can show that my 
private key was used by someone else, without my consent, then I can 
repudiate the transaction.  It's just another form of identity fraud; 
investigating fraud entails working who really did what to whom.  It's 
exactly the same with any authenticator -- a password, PKI private key, 
biometric or whatever.  The idea that someone cannot in principle ever 
repudiate a digitally signed transaction is plain silly, and to my 
knowledge, has no actual legal foundation.  I'd like to know the precise 
history of the NR bit in X.509.  Who actually thought of it, were they 
an engineer or a lawyer, and what if any debate went on at the time?

Stephen Wilson
Managing Director
Lockstep Technologies

Phone +61 (0)414 488 851

www.lockstep.com.au/technologies
-------------------
  * ABC TV 'The New Inventors' Nov 2008
  * Global Security Challenge Asia Top Five 2008
  * Australian Technology Showcase 2008
  * AusIndustry COMET Grant 2007
  * ICT Secrets of Innovation Finalist (Security) 2007
  * Anthill / PwC Cool Company Finalist (Innovation) 2007
-------------------
Lockstep Technologies develops unique new smart ID solutions to
safeguard identity and privacy. Lockstep Consulting provides
independent specialist advice and analysis on authentication, PKI
and smartcards.

---

From: "Santosh Chokhani" <[email-masked]>
Date: Sat, 15 Nov 2008 15:51:06 -0500

One benefit of setting both bits for a TLS Server for RSA algorithm is
that when the Server is acting as a Server, the key is used to encrypt
and when the Server acts as a client, the same key can be used to
perform client authentication using digital signature.

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Stephen Wilson
Sent: Saturday, November 15, 2008 9:34 AM
To: [email-masked]
Subject: Re: Signing and Encrypting with the same key?

Cheers,

Steve Wilson.

Stephen Wilson
Managing Director
Lockstep Technologies

Phone +61 (0)414 488 851

---

From: "Kemp, David P." <[email-masked]>
Date: Mon, 17 Nov 2008 09:06:35 -0500

-----Original Message-----
> From: Stephen Wilson
>
> I'd like to know the precise 

Trust me, you really, REALLY don't want to know :-).

Those on one side of the argument thought that the NR bit set should be used for signatures that could be validated indefinitely (i.e. for what one normally thinks of as "signing"), and signatures with the NR bit clear could be used only for session authentication.  That way a signed object created as part of a login session could not be misrepresented as a signed document.

Those on the other side thought that the NR bit actually had something to do with "repudiating" signatures, which IMHO is a ridiculous idea for the reasons you suggest.  Those who believe in the current X.509 interpretation may defend it if they wish, or spare us the discussion.

Dave

---

From: "Jorge López" <[email-masked]>
Date: Sat, 29 Nov 2008 13:01:55 +0100

Hi all,
This mail was intented for the past discussion about if using the same key
pair for encrypting and signing may derive in a reduction of the security of
the scheme. Sorry if it's too late for that, but I haven't had the URL to
the paper so far. The URL points to the recent results of a research
(preprint version) made by a spanish colleague of mine where they actually
prove the security or insecurity of using the same key pair in both
encryption and signature schemes, depending on the specific situation.

http://eprint.iacr.org/2008/466

Hope this (still) help a bit

Regards,

Jorge L. Hernandez-Ardieta

2008/11/17 Kemp, David P. <[email-masked]>

> Those on one side of the argument thought that the NR bit set should be
> used for signatures that could be validated indefinitely (i.e. for what one
> normally thinks of as "signing"), and signatures with the NR bit clear could
> be used only for session authentication.  That way a signed object created
> as part of a login session could not be misrepresented as a signed document.
>
> Those on the other side thought that the NR bit actually had something to
> do with "repudiating" signatures, which IMHO is a ridiculous idea for the
> reasons you suggest.  Those who believe in the current X.509 interpretation
> may defend it if they wish, or spare us the discussion.
>
> Dave
>