Re: RSA breaking vs. factoring

According to Helmut Richter <hhr-m@xxxxxx>:
If I understand randomized padding right, it makes encryption and
decryption two different procedures. I do not see at the moment how this
affects the two possible usages of RSA both for encryption (first public,
then private key) and for signing (first private, then public key).
Anyway, one would have to tell the device whether one is now encrypting or
decrypting.

You really want to do that anyway. The mathematical operation at the
core of RSA is often described as somewhat symmetric (you use either the
public exponent e, or the private exponent d) but this is deceiptive: in
practice, they widely differ when it comes to implementation details.

-- The public exponent is often very short; current values for e are 3
and 65537. Having a 2 or 17-bit exponent offers a huge speedup over
using a generic public exponent with the same size than the modulus
(e.g. a 1024-bit exponent). Nobody really uses RSA with a non-short
public exponent (indeed, the RSA implementation shipped with Windows and
used by Internet Explorer for SSL is unable to handle RSA public
exponents which do not fit on 32 bits). Good algorithms for
exponentiation quite differ when the exponent is short: for long
exponents, it is worthwhile to perform a few extra computations (e.g.
Montgomery representation, window-based tables...) which are not
necessarily worthwhile when using a short exponent.

-- Conversely, operations with the private key, while being considerably
slower than public key operations, are customarily sped up by a factor
of four by using the Chinese Remainder Theorem: namely, when computing
m^d mod n where n = p*q, you can compute the exponentiation modulo p and
modulo q, and glue back the results at the end. That speedup is
achievable only when p and q are known, hence this cannot be done for
the public part (because knowledge of p and q is _not_ public). All
deployed implementations of RSA use that method for private key
operations.

-- Some side-channel attacks have been found on RSA. The most well-known
are the "timing attacks" from Paul Kocher. They exploit precise timing
measures of a device (whether software or hardware) which computes the
RSA private key operation, because internal details of the algorithm
differ in execution time, depending on the private key bits. The usual
protection is to use masking: you first select a random integer r modulo
n; then you compute m' = (r^e)*m mod n. Then you apply the private key
on m', and you finally divide by r. It so happens that (m'^d)/r = m mod n.
The point of the exercise is to apply the private exponent on the
value m', which the attacker does not know, while timing attacks require
the attacker to know on which integer the exponentiation is performed.
Any serious RSA implementation uses masking (of that kind or a similar
method). Done right, masking induces little additional cost with regards
to private key operations. However, masking would easily double the
cost of public key operations (which are fast, thanks to the short public
exponent), and that would be very useless since public key operations use
only public data and thus have nothing to mask.

-- When using a dedicated system for private key operations (a HSM, a
smartcard), the point is usually to store the private key in an armored,
tamper-resistant piece of hardware which will apply the private key on
externally provided data, but will refuse to output the key itself. This
is not relevant to public keys, which often need not be stored and/or
cannot be stored (in most setups, a user owns a single private key, but
uses the public keys of dozens of other users). Moreover, to prevent
some technical attacks, the device will need to apply or verify the
padding itself, so public key and private key operations cannot be
handled identically at the device level. And you probably do not want to
apply the public key with your smartcard anyway, since the host CPU is
much more powerful. This is not affected by whether the padding is
randomized or not.


Briefly stated, there are many reasons why you do not really want to use
the exact same implementation for applying the public key and the
private key.


I am also not sure one can still use the same key for for encryption
and for signing although I do not see a hard and fast reason that
would disallow it.

There is another widespread confusion about RSA, which is: signatures
are identical to encryption, in reverse order. For instance, the PKCS#1
standard describes RSA signatures with the help of the SHA-1 hash
function under the name "sha1WithRSAEncryption". However, asymmetric
encryption and digital signatures are distinct beasts.

Asymmetric encryption takes an input message (which is short) and a
public key, and produces the encrypted message. Decryption takes the
encrypted message and the private key, and computes back the original
message.

Digital signature generation takes an input message (which may be quite
long) and a private key, and outputs a signature. Signature verification
takes as _input_ the message, the signature and the public key, and
outputs "ok" or "not ok".

It so happens that the RSA signature algorithm, with any of the standard
paddings, is a "digital signature algorithm with recovery". This is a
special kind of signature algorithm which internally works with a hash
function. Signature generation first compute h(m) (for a hash function
h) and then uses h(m) as input to the core signature generation. Then
the verification can extract back h(m) from the signature and the public
key; it then proceeds to comparing that extracted h(m) with the one
computed over the message. That's the "recovery" part: h(m) can be
computed back from the signature and the public key, without using the
input message.

Not all signature algorithms provide recovery. In particular, the DSA
algorithm does not. If you develop an application which verifies digital
signatures, and you want to provide some support for other signature
algorithms (which is wise, because specializing on a single algorithm
means that you cannot easily adapt to advances in cryptanalysis), then
you must take care to design your system so that the signature
verification module is given the input message (or at least the hash of
the message) as _input_, instead of expecting it to be produced as
_output_. With that design, signatures are not anymore a kind of
encryption.


Nevertheless, the RSA asymmetric encryption scheme and the RSA digital
signature scheme, as defined by PKCS#1, may use the same private key. In
a typical application, you will not apply them in the same place. For
instance, in an emailing software, you use your private key to decrypt
incoming messages, and to sign outgoing messages; you do not use
asymmetric _decryption_ and digital signature _generation_ on the same
data. Yet you can use the same key and, if proper protocols are used for
all operations, then there is no known attack (applying proper padding
application and verification, where appropriate, means that by applying
decryption on what looks like an encrypted message, you are not in fact
helping an attacker to forge a signature).

However, you usually want to use distinct keys, not due to a problem in
the RSA core operation, but because encryption and signature keys have
distinct life cycles. For instance, envision a corporation where
employees use RSA encryption and signatures for internal emails.
Encryption is meant to protect trade secrets with regards to
eavesdroppers (e.g. the competition, who are not necessarily law-abiding
people). Digital signatures are used to make employees accountable for
what they send. Now, imagine that a user (let's call him Bob) private
key is lost (Bob owns a dog named Barney, and Barney eats Bob's
smartcard). Bob cannot sign anymore, until he obtains a new smartcard
with a new private key. Signatures previously emitted by Bob are still
valid and verifiable: Bob's private key was lost, but his public key
is still known (it was published in the corporation directory so that
everyone may verify Bob's signature).

Now, Bob has also received a number of encrypted emails; these emails
are stored _encrypted_ in Bob's mailbox (they were encrypted because
they may contain sensitive data, and thus must not be stored unencrypted
on the corporation mail server). Now that Bob's private key is in
Barney's digestive system, the emails cannot be decrypted anymore. Data
loss is a critical problem in corporations, and cannot be tolerated.
Data recovery must be applicable, when decided by the corporation
hierarchy, possibly without the help of Bob himself (imagine that a
pissed off Barney, instead of Bob's wallet, ate Bob's throat). A copy of
Bob's private key must then be kept somewhere, possibly in a safe which
key is held by a group of directors. That procedure is known as
escrowing. But if Bob's private key is escrowed by a third party, then
it becomes difficult to make Bob legally accountable for the emails he
signed, because he could claim in court that the escrow holders had a
grudge against him and used his escrowed key to frame him.

The solution to that problem is to use distinct keys for encryption and
signature. The encryption key would be escrowed, while the signature key
would not be. This relates to the kind of security than we wish to
achieve: encryption is _a priori_ (we want to prevent attacks) while
signatures are _a posteriori_ (we want to be able to unambiguously put
the blame on Bob after the mishap). If you take this stance, then having
the same private key for both encryption and signatures is just a storage
optimization in setups where:
-- The security model implies similar life cycles for encryption and
signature keys.
-- The asymmetric encryption algorithm and the digital signature
algorithms happen to be able to use the same kind of key.


Historically, some countries (e.g. USA) have held export regulations
which would imply distinct limitations on the size of keys depending on
whether they should be used for encryption or for signatures. That kind
of legal constraint also advocates for the separation of encryption and
signature keys.


It is more of a gut feeling: the more I learn about it, the more do I
develop an "anything you say may be used against you" attitude.

Precisely: whenever you use your private key for an asymmetric
decryption on externally provided data, then this may be a devious
scheme from an attacker who tries to use you as a "device for applying
the private key" in order to computed a forged signature. And vice
versa. E.g., the attacker (call him Dave) sends to Bob an email which
claims to be encrypted with Bob's public key. In reality, Dave has sent
h(m) for a message m. Bob "decrypts" the message and gets something
which, as a message, is complete nonsense, because in reality what Bob
computed was h(m)^d mod n, which is a _signature_ over the message m.
Bob sends back an email to Dave stating: hey, what's that junk ? And
Dave answers: thanks, you've just sent me back a valid signature on a
shiny voucher. You legally owe me a million dollars.

If you take care to apply and enforce proper padding procedures then you
avoid that kind of issue, but this is only due to the fact that such
interactions between encryption and signatures were thoroughly analyzed
when the standard padding procedures were designed. So it is safe for
RSA, but do not assume as such for just any combination of an encryption
algorithm and a signature algorithm, if they happen to be usable with
the same keys (e.g. El-Gamal encryption and DSA signatures).


--Thomas Pornin
.

Relevant Pages

  • Re: RSA ecnryption confusion
    ... From the core mathematical RSA ... -- RSA asymmetric encryption, which can be used to encrypt confidential ... The other exponent is kept private. ... of the private key is the knowledge of everything about the modulus. ...
    (sci.crypt)
  • Re: RSA ecnryption confusion
    ... From the core mathematical RSA ... -- RSA asymmetric encryption, which can be used to encrypt confidential ... The other exponent is kept private. ... of the private key is the knowledge of everything about the modulus. ...
    (sci.crypt)
  • Re: Basic question about RSA
    ... all public-key schemes; ... that in RSA, the operation of "encrypting with the private key" is *not ... If we do not interchange keys, but refer as "encryption with private ... key" to the RSA signature generation algorithm, ...
    (sci.crypt)
  • Re: RSA Decryption with public key?
    ... you are hung out to dry here because the entity you must interact with has created a protocol that is cryptographically unsound. ... The thingy that with RSA often referred as ... "Decryption with public key" is actually a *Signature Verification ... encryption vs signature. ...
    (microsoft.public.dotnet.security)
  • Re: RSA Encrypt/Decrypt Problems
    ... in kind, for who it does not have much practical one of encryption, it can ... use RSA in order to crypt KEY and IV of an algorithm to symmetrical key DES, ... I in my programs encrypt with the private key and decrypt with the ...
    (microsoft.public.dotnet.security)