Public key encrypt-then-sign or sign-then-encrypt?

James A. Donald jamesd at echeque.com
Tue May 15 16:36:17 EDT 2007


James A. Donald:
 > > Assume Ann's secret key is a, and her public key is A
 > > = G^a mod P
 > >
 > > Assume Bob's secret key is b, and his public key is B
 > > = G^b mod P
 > >
 > > Bob wants to send Ann a message.
 > >
 > > Bob generates a secret random number x, and sends Ann
 > > X = G^x mod P
 > >
 > > Ann responds with Y = G^y mod P, where y is another
 > > secret random number.
 > >
 > > Ann calculates [(B*X)^(a+y)] mod P

Travis H. wrote:
 > an identity-binding flaw:
 >
 > <http://lists.cypherpunks.ca/pipermail/otr-users/2005-July/000316.html>
 >
 > [...]
 >
 > : :    For example, if Bob thinks he's talking to
 > : :    Mallory, he may tell her something in
 > : :    confidence he would not want Alice to hear.
 > : :    Note that although Mallory could relate
 > : :    this confidential information to Alice
 > : :    herself, but in the attack scenario Alice
 > : :    has assurance that the message came from
 > : :    Bob rather than having to take Mallory's
 > : :    word for it.

The flaw in the protocol that you point out is that
Carol can allow Alice to use her public key without
having to reveal the public key to Alice, so that Alice
can pretend to be Carol.  Thus the flaw is that with
prearrangement, Carol may prove to one other person, but
to no one else, that Bob is saying such and such to
Carol, provided she knows in advance that Bob is going to say it.

Trouble is, I cannot see how to fix it without
introducing an additional public key operation, which
seems a high price for such a modest value attack.  If
Alice and Carol are working together in advance so that
Alice can be convinced that Bob is saying what Carol
knows he is going to say, Bob is pretty much hosed
anyway, for Alice can check the provenance of packets
that Carol claims are coming from Bob, or Carol may
simply reveal her private key to Alice.  The usual
threat is that things casually said a long time ago come
back to haunt you, retrospective revelation, not advance
revelation, and this attack does not threaten that.

Suppose Carol wants to prove to Alice that Bob is
saying what she claims he is saying.

Alice generates a transient secret key y and transient
public key Y = G^y, and gives Y to Carol. Carol receives
X = G^x from Bob, and gives him Y.  Carol's permanent
public key is C = G^c, Bob's permanent public key is B =
G^b

Bob calculates the shared secret (C*Y)^(b+x)

Carol calculates P = (B*X)^c, and gives it to Alice.

Alice calculates the shared secret [(B*X)^y]*P

Alice then converses with Bob, pretending to be Carol.

Is there any way to fix this without introducing an
additional exponentiation?  Perhaps by introducing an
additional multiplication? It does not seem worth while
introducing an additional public key operation, for such
a low value attack.

 > Contrast this to sign-then-encrypt, where Mallory
 > could decrypt, then forward to Alice.  Compare with
 > encrypt-then-sign.

But with encrypt then sign, Mallory can still prove his
decryption is correct.   He just has to reveal the
shared symmetric secret for the particular message.   So
encrypt then sign does not buy us anything.  With
encrypt then sign, messages Bob casually sent a long
time ago can still be revealed to the world, and proven
to have originated from Bob.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list