where Ka is Alice's public key and Ka-1 is her corresponding secret key. This scheme can elegantly be used to create a signature by applying the keys in the reverse order.
{{ M } Ka } Ka-1 = M
That arises the question how ModExp is used in PCP to create a signature. usually this can be answered by giving the protocol for signature creation and verification.
In case Alice and Bob cannot meet directly to exchange their public keys Ka and Kb they usually rely on the service of a third person ( the CA ) in which both of them have a certain degree of trust in, that this third person will check the key holder's identity as well as her ability to use the corresponding secret key and so on. The keys which are presented to the CA consist of the modulus, the public encryption value and the user's identification string (only this is a valid key) together with the hash of these three values. Note, that changing the user's identification will show up in the security hash! Thus the security hash protects the key material and simultaneously the user's name from manipulations even if the key is unsigned. After the CA has verified the security hash of Ka and Kb with Alice's and Bob's written details it sends both keys back to their owners and publishes them in a public directory.Preconditions A meets CA : A , Ka = (n1, e1, A, hash(n1+e1+A)) CA meets A : CA, KCA = (n0, e0, CA, hash(n0+e0+CA)) B meets CA : B , Kb = (n2, e2, B, hash(n2+e2+B)) CA meets B : CA, KCA = (n0, e0, CA, hash(n0+e0+CA)) CA verifies the security hash on Ka and Kb CA ----> A,B : Ka, CA, { T1, CA, hash(Ka) } KCA-1 CA ----> B,A : Kb, CA, { T2, CA, hash(Kb) } KCA-1 A and B verify the CA's signature and sign the keys themselves.Signing by Alice A ----> B : Signature = ( M, A, { T3, A, hash(M) } Ka-1 )
Verification by Bob Signature is good, if hash(M) corresponds with { { T3, A, hash(M) } Ka-1 } Ka = T3, A, hash(M)
Alice creates a signature on her message M by hashing the message and encrypting a timestamp T3, her name A and the hash of the message with her secret key sending this piece of crypto together with her name and the original message to Bob.
Before Bob can verify Alice's signature, he has to verify the CA's signature to make sure that he can use Alice's key in PCP which is only possible after he has signed this key with his own signing key. After that he decrypts the piece of crypto inside Alice's signature with her trusted public key Ka which reveals the hash value Alice has created and compares it to his own hash of the message M in the signature. If they don't match, either the message M is altered or replaced by an opponent or the crypted piece of information is replaced by a different one which had been created with Alice's secret key long ago, but using a different message. Or the signature is completely forged which is signalled in PCP as a bad signature.
The multiplicative homomorphism of RSA leads to another problem which comes into play when you encrypt messages. As I understand a method called Optimal Asymmetric Encryption Padding (OAEP) is used to protect encrypted plaintext from being forged and this usually applies only to short pieces of data like key packets. Extending OAEP to all encrypted plaintext would be roughly equivalent to signing the message, because a hash of the whole message body is needed in OAEP, so the additional step of encrypting the hash would not be expensive. But of course there are other reasons to introduce an Asymmetric Encryption Padding Scheme because without a carefully crafted manipulation of the plaintext the RSA encrypted blocks are exposed to a variety of attacks, which will be described before PCP's padding scheme will be analysed.
To prevent this kind of attack PCP checks every message the user is
about to sign whether it contains lines of cryptographic material -
which is everything made out of 0..9 on a line by itself - and issues
an unequivocal warning that the user should not proceed with the signing
process unless he knows what he is doing. The warning makes clear that
it always is prudent first to sign before encrypting something.
Another form of key spoofing attacks require compatible weak keys
(see [And-2000] p.4 for details) that will work if an attacker is able
to modify the modulus in a public key published in an unprotected place.
This will show up in PCP because before any key is used the
security hash is printed, so that the vigiliant user will notice that the
hash has changed. If the manipulation has occured before the user signs
the key and the correct unmanipulated security hash is on the key and has
been checked with the user (or a CA) then PCP will notice that the signed
key material gives a different security hash than the one which is signed.
This will lead to another unequivocal warning not to use the key before it
has been checked with first-hand knowledge.
But if the security hash is replaced as well - a daring attack - everything
looks fine, except that the length of
the modulus is considerably longer than the original and this will be
calculated and displayed to the user as well before the key is used. So if
you know that your mate uses a 2048 bit signing key and the length of
the public key shows more when it is used to verify, you know that something
is rotten with this key.
Key related Problems
Common Modulus Attack
As PCP stores public keys used for encryption in the directory
"trusted-keys" two different keys may have the same modulus by chance.
This would make encrypting a message using either key insecure,
because each of the different key owners can factor the
common modulus using her own secret key and thus is able
to deduce the other person's secret key from her public key
effectively. Checking the keys used by PCP for common moduli
is a must every time a new key enters the database.
Key spoofing Attacks
Some carefully crafted key spoofing attacks have been described in detail
by Ross Anderson and Roger Needham (see [AN-95a], [AN-95b]).
Especially when users try to sign something that contains already encrypted
material an opponent who is able to factor the modulus used for encryption
(i.e. at least Bob) can work out a different Message M' and publish a
modified public key for Bob so that the new Message M' looks like a
valid signature made by Alice on something that was encrypted for Bob.
(see [AN-95a] p.2 and [Bon] p.4 for details)
Low Public Encryption Exponent Attack
There is a serious problem arising from the fact that most
public keys commonly used have a very small public encryption
exponent e as part of the public key (e,N) which makes attacks
based on Coppersmith's theorem become practical.
Basically his theorem provides the means to find small
roots of polynomials modulus a composite N.
An attack will require, that the same message M is encrypted
with a number of different public keys. If for instance
the public encryption exponent is 17, which is a number used in
very many public keys today, an attacker can obtain the plaintext
after he has collected more than 17 different ciphertexts of
the same message and has used the method to compute 17th roots
based on Coppersmith's theorem effectively.
This attack can be defeated by carefully padding the message
before it is encrypted with the RSA primitive but only,
if some randomness is introcuced in the process of encryption.
In what way this will work inside PCP will be
explained later.
Oracle attacks will work in a way similar to blinding attacks on signatures (see [Bon] p.4 and 14) An attacker uses a random number r and computes C'=C*r mod N and sends C' for decryption to the victim. If the attacker knows that the plaintext will have a certain known structure, he can deduce information about the plaintext from the fact whether or not the victim accepts the message as a valid plaintext.
The attacker will only be able to replace a crypted block by another
one, if she can manage to keep the lower 256 bits inside the
encrypted packet the same. Otherwise the hash-chain is broken and
the decrypted material will disappear forever.
So she has to fix the lower 256 bits (the CHALLENGE)
of the new forged plaintext encrypted under Bob's public key.
And the value of the fixed part of the plaintext is
one she doesn't know unless she knows the initial Nonce in the OAEP
packet. If somehow she gains knowledge of the plaintext at stage i
she will know PAD-i XOR hash(PAD-i) and cannot recover the padded message.
And what is more, she will not learn about PAD-i from the observation
of the next packet because XORing the challenges will give only
knowledge of PAD-i XOR hash(hash(PAD-i)) and so on.
Fortunately the discussion brought a discrete logarithm hash functon
(SDLH) to light which was proposed years ago by Adi Shamir, and which
is not only based on an intuitive simple idea but also comes with a
prove
of collision-resistance given by Ronald L. Rivest in a posting to
the cryptography discussion forum.
Consequently PCP was redesigned to run in two different modes.
The "conservative mode", being the default mode, which addressed
the concerns of those who will only trust standard algorithms
uses SHA-1 as the hash algorithm under all circumstances. Clearly this
is a compromise solution because at this point the program relies on
a precompiled module implementing SHA-1 breaking with the idea of pure
crypto which should entirely be understandable by the user.
The second and "pure mode" will use Shamir's discrete logarithm
hash function which will be used with moduli longer than 1024 bit,
so that the hash values used in signatures will be that long as well.
This hash function is provably collision-resistant, I quote the prove
Ronald L. Rivest presented in his posting:
But the same method which is suitable to protect your secret key
cannot be used to encrypt a message that is meant to be sent to another
person for practical reasons which are generally known and accepted.
So the intuitive and secure OTP-method can be used locally only without
the need to transfer the OTP to another party securely.
Let me first describe in detail the secret decryption value d is
protected on your local computer system before I will discuss
the reasons against the plan to engage this method as a general
symmetric substitution for the RSA-encryption of plaintext.
The user's passphrase string is read in from the console
and then hashed into a 256 bit number (using the secret key's modulus),
the result of 78 decimal digits is then split into 13 pieces
consisting of 6 decimal digits each, providing 13 pointers into a
file which consists of at least 1100000 bytes of truly random data.
Each pointer provides a different sequence of random data with the
length of the modulus. All 13 random sequences are then XORed and
the resulting sequence is finally XORecd with the secure decryption
value d and stored in the file that holds the secret key.
When the secret key has to be used for signing or decryption the
passphrase is read in again and the 13 piece one-time-pad is
reconstructed to unlock the stored encryption value.
The sequence of random data is clearly used as a one-time-pad
because it will never be reused to encrypt anything else but the
secret key and if the hash function does not cluster, every possible
pointer is equally likely, depending only on the passphrase used, which
must contain as much entropy as the pointers.
To recover the pad one has to recover all 13 pointers used, i.e.
one has to guess the passphrase, if the hash is a one-way function.
A brute force attack on the secret key encryption would roughly require
to check all possible combinations of 13 sequences out of a million,
which is roughly proportional to enumerating all 256 bit hash values.
Usually it seems much more rewarding to make assumptions on the
passphrase and to try dictionary attacks instead of mounting a
fully fledged brute force attack, hoping that the user has a
weak passphrase. But if the passphrase has enough entropy the strength
of this encryption scheme is almost 256 bit, provided that the
entropy file is made out of truly random data, which is not an easy
job to do.
Ferguson, Schneier and Wagner (see [ FSW ]) published their cryptoanalytic
research on a randomized stream cipher implemented by
TriStrata
which was designed as a symmetric encryption
algorithm also using a 1 MByte random data pool but only 5 instead of
13 pointers to generate a keystream for encryption.
They analysed this smaller variation of an encryption scheme
first introduced by Maurer ([Mau-92]) which promised to be both
provably secure and at the same time practical using a very huge
amount of publicly available random data with 50 pointers.
In their analysis Ferguson et. al. showed that serveral attacks against
the smaller Maurer-like variant of the cipher are possible with a
complexity of 293 for an exhaustive search attack on the
pointer space and even 257 when a meet-in-the-middle attack
is being mounted. They also showed that improved attacks with a
complexity of only 239 are possible if one could induce
faults into the random pool or if one could find related keys whose
contributions to the keystream cancel out. They concluded that if
the number of pointers used is increased to 14 the complexity
of an attack would rise to 2128 but with only 5 pointers
the TriStrata system will not always be secure.
All attacks against the TriStrata variant are based on two assumptions
which are realistic for a symmetric cipher. Firstly, that the
random pool is publicly known, a fact we can suppose for PCP's
entropy file as well, even if it is protected by the OS's protection
and ACL mechanisms and secondly, that the stream of encrypted data
can be observed freely by the attacker who knows some bytes of the
plaintext because of some known structures of certain plaintexts
like WORD-documents and the like. Ferguson et. al. suppose that
the adversary knows at least 16 bytes of plaintext revealing 16 bytes
of the keystream. But this assumption of known plaintext is
unrealistic in the context of PCP's protection of the secret key
as the secret key does not only lack a known structure but also
even if a fraction of the secret key is known there are different
ways to reconstruct the rest of the secret decryption value
(see [Bon] p 11) and the protection is already broken.
Thus the special purpose the Maurer-like encryption scheme is used
for in PCP to protect the secret key will render the
known-plaintext attacks described by Ferguson et. al. useless.
But at the same time their cryptanalysis shows that such an encryption
scheme cannot safely be used as a general substitution for RSA encryption
inside PCP to speed up its performance. As long as the random pool
and the number of pointers are not increased considerably randomized
stream ciphers a la Maurer cannot be regarded as a secure cipher suitable
for the exchange of strongly encrypted messages.
But anyway there is one aspect of Ferguson's analysis which may affect
even PCP's protection of the secret key.
If the attacker is able to tamper with the stored pool and the
adversary can observe enough ciphertext encrypted with the manipulated
random pool she might locate the position of the pointers (see [FSW]
section 5.2). But in the context of PCP's protection mechanism the
attacker will not be able to observe the faulty ciphertext, because PCP
checks if the secret decryption value works correctly with
the public key, and if not, it will display a warning that the
secret key is unavailable and will simply stop working.
On the other hand as long as the attacker constantly keeps changing
the random pool and at the same time observes that Alice is happily
signing her files she knows that the manipulated bytes of the pool
are not inside the 13 sections which are used to create the
one-time-pad. But if she hits a significant byte Alice will notice that
her secret key does no longer work and if she is careful, she will
create a different entropy file to protect her secret key taken from
the safe again bringing the attacker back to square one.
Finally I would like to stress that the quality of the entropy file
is of utmost importance for the security of the secret key so that
it is prudent to spend as much care as possible to select the
1100000 Bytes of the random pool using a truly random source of
entropy.
Hash-Chain Encryption Padding
Due to a number of possible attacks we cannot use RSA on the
plaintext blocks directly and have to provide a padding method
that introduces randomness in addition to every plaintext block
before encryption is done. It is very much desirable that the padding method
will provide a means to check, whether a block can be decrypted
successfully or not.
The method used for padding relies on the secure transmission of an
initial number of 256 bit which will subsequently be used to generate
a hash-chain that provides a piece of information to blind the current
message block. Additionally the hash-chain gives a challenge, that
links consecutive message blocks so that chosen ciphertext attacks
can be detected.
The recipient can form the same hash-chain during decryption and
can recover the message with PAD1.
And she can check, if the current CHALLENGE is the XOR of both pads
at stage i. If not, an oracle attack is imminent and anyway integrity
is violated. In this case PCP now continues to decrypt (to prevent
timing attacks) and throws away the decrypted material leaving
a warning in the output file, that an oracle attack may have been launched
and the user will never see the decrypted material.
The recipient decodes the first block and learns the initial Nonce.
PAD1 = initial Nonce
PAD2 = hash(PAD1)
CHALLENGE = PAD1 XOR PAD2
Concatenate two numbers, the 256 bit CALLENGE and the padded message
with PAD1 extended to the whole length of the message.
i-th Block : Message XOR (repeated PAD1) || CHALLENGE
PAD1 = PAD2
PAD2 = hash(PAD2)
CHALLENGE = PAD1 XOR PAD2
Hashing within PCP
The hash
function which was originally designed for use with PCP
received a
highly reserved attention and the opinion was expressed, that
nothing new should be used but the standard hash functions which are
supposed to have been subject to intense scrutiny and review. On the
one hand this is surely an advantage of standard algorithms like SHA-1
but on the other hand, the underlying idea and the resulting code of
SHA-1 is not at all self-evident nor can it be regarded as pure crypto
because of the complexity of its operations and its impenetrability
beeing caused.
Shamir's discrete logarithm hash function (SDLH)
The SDLH is base on a simple idea that once the message is converted into
a long integer a hash of the message can be computed as follows:
hash(x) = g x (mod p*q)
given, that both p and q are large primes which are being kept secret
so that factoring n = p*q is computationally infeasible.
There are a number of issues to be addressed, especially when the SDLH
is being used together with the RSA signature scheme and a full analysis
of the SDLH's security can be found in the paper
"A Discrete Logarithm Hash Function for RSA Signatures". The analysis
shows, that SDLH can safely be used together with RSA once certain
conditions are met with regard to the selection of the user's key material.
For details I like to refer to the paper about SDLH.
The Protection of Your Secret Keys
The intention to keep the source code of PCP as small as possible
is not the only reason why there is no symmetric cipher in PCP.
At least when it comes to protecting your secret keys with a passhrase
some symmetric cipher is needed. So why shouldn't we use this method
instead of the painfully slow encryption mechanism with RSA keys?
The answer is simple, if you can generate a truly random sequence of data
which depends on your passphrase alone you can use this sequence as a
one-time-pad to protect your secrete key, because this one-time-pad
never has to leave your local system. This method will be secure
as long as it is computationally infeasible to recover the sequence
of random data used to protect your secret key.
References
in: Advances in Cryptology - CRYPTO '95, Springer LNCS
v 1070 pp10-18
in: Computer Science Today - Recent Trends and Developments
, J. van Leeuven (ed.), Springer LNCS vol 1000, pp 426-440
in: Codes and Ciphers (proceedings of fourth IMA
Conference on Cryptography and Coding,
December 1093), published by IMA (1995) pp 83-93
Journal of Cryptology, vol 5 no. 1, 1992 , pp. 53-66
This document is
signed digitally with PGP.