[Cryptography] Should we always KeyWrap, even with Key Recovery?

[Ray Dillinger]

On 12/27/2016 09:07 AM, Phillip Hallam-Baker wrote:
> I am just working on some code and it occurs to me that the use of RSA to
> encrypt data under a session key might give an attacker more leverage than
> we need to allow.
> 
> With RSA we typically generate a random session key and encrypt that. The
> counterparty decrypts the blob to recover the key. If there are n
> counterparties there are n different encryptions of the same data under
> different RSA keys.

This is true, but so far I had been under the impression that it doesn't
matter for related-key purposes if the RSA key factors selected are
non-identical strong primes.

That said, my number-theory-fu is certainly much weaker than yours,
given your work at Verisign.  If you believe encrypting the same data
under different RSA keys could become a problem, you are far more likely
than I am to be correct about it.

Bearing this in mind, I devoted a few minutes to research to see if I
could find evidence to support your concern.  And it turns out that
there definitely is supporting evidence.

See this year's usenix paper at
(https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf).

Evidently an attacker is able to determine what implementation has been
used to generate primes, and therefore narrow down the possible set of
primes they need to check, based only on patterns detectable in the
public key.  This is yet another illustration of something whose
security has strong theoretical support being subject to implementation
constraints that reduce its security in practice.

Because detectable patterns in public keys based on prime selection
evidently exist, it seems very likely that many systems are selecting
from relatively small families of primes, and that therefore the
related-key attacks you're concerned about may become a real problem -
Especially given that Nancy's* pattern is to attack as many keys as
possible rather than investing all her power in attacking any single key.

> With DH we don't encrypt, we have a key agreement. If we have only one
> counterparty then we can perform the key agreement and use the result to
> generate the session key, preferably involving some sort of digest step. If
> however we have more than one recipient, we have to wrap the session key
> using the result of the key agreement.

Multiple-party DH is a known protocol.

See  http://www.mecs-press.org/ijwmt/ijwmt-v1-n4/IJWMT-V1-N4-9.pdf.

But I do not know of any good implementations of it which are at a
trustworthy/vetted/tested stage.  You are one of relatively few people
who most likely could produce one.

			Hope this helps....
					Bear

*: Incidentally, I have added Nancy and Harold to my own set of dramatis
personae.  Together, the two are even more pernicious than Eve and Mallory.

Nancy is the Nation-State attacker interested in mass surveillance and
breaking as many protocols as possible rather than breaking any
particular single instance of a protocol.  Traffic analysis, attacks on
entire families of keys, hardware and expertise both well beyond other
attackers, subversion of cryptographic standards, using legal force to
make otherwise trustworthy Trents and Harolds act in bad faith, etc.

Harold is the manufacturer of hardware like routers and NAT boxes, etc.
He is often located in nations with adversarial interests in the
activities of the nations or companies where the hardware gets used.

PS. Because detectable patterns due to particulars of the selection of
primes for RSA exist, it seems possible that they may also be applicable
to the selection of primes for DH key agreement.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20161228/bd268ab4/attachment.sig>