Cryptography Reference
In-Depth Information
RSA — the manufacturer can hide parts of the private user key in his public key
such that it cannot be proven by analyzing the public key. From the outside,
the software or hardware cannot be distinguished from a correctly working one.
The authors call them a bit clumsily
SETUP
(
Secretly Embedded Trapdoor
with Universal Protection
) systems.
Young and Yung define three types of SETUP systems:
weak, regular
, and
strong
. I briefly mentioned an example of a
weak SETUP system
in the last
example above: though the system apparently works all right, the fraud can be
detected by analyzing the outputs, but it cannot be used by third parties (since
they don't know the manufacturer's private key). Conversely,
regular SETUP
systems
don't manifest whether or not a fraud is built in, even after thorough
ciphertext analysis.
It might be desirable to have a SETUP system make use of its secret capabilities
only sometimes, for example, to make it harder to prove the fraud. We speak
of a
strong SETUP system
when 'honest' and 'dishonest' outputs cannot be
distinguished either in the future or in the past.
The authors implemented SETUP systems for a large number of algorithms and
protocols (RSA, ElGamal, DSA, Kerberos) and demonstrated their practical
use: computation times were only slightly longer, the costs remained within a
reasonable range.
The fact that the specific implementation is rather complicated doesn't matter,
for once it is programmed, the attack works automatically, enabling extensive
automated eavesdropping activities.
Potential Impact
SETUP systems enable particularly clever data espionage. I hope they are not
in use yet: the more reason to think about the potential impact such systems as
well as the countermeasures may have.
First of all, a hairsplitting thought about the impact: the signature law of 1997
discussed in Section 8.2.5 said that the private keys created for users must not
be stored in a trust center. An embedded SETUP trap would bypass this law by
nature (which is not in the law's sense, of course). The thing is that, especially
with RSA key generation, the two secret prime numbers required,
p
and
q
, can
be chosen such that they allow the manufacturer to easily compute them from
the public key created (more specifically, from the
pq
product). Naturally, trust
centers have to meet particularly strict requirements. But the centers and the
