A-B-a-b encryption

[Jerrold Leichter]

| > it came up lately in a discussion, and I couldn't put a name to it:
| > a means to use symmetric crypto without exchanging keys:
| >
| >   - Alice encrypts M with key A and sends it to Bob
| >   - Bob encrypts A(M) with key B and sends it to Alice
| >   - Alice decrypts B(A(M)) with key A, leaving B(M), sends it to Bob
| >   - Bob decrypts B(M) with key B leaving him with M.
| >
| > Are there algorithms for this already? What's the scheme called?
|
| "Stupid crypto", probably. Unless I'm missing something, this only works
| if A(A(M)) = M. Symetric crypto, not just symetric keys.
Not at all.

What's required here is that A and B commute - i.e., that A(B(X)) = B(A(X)).
(This is needed for the 3rd step.  If they don't commute, then decrypting
B(A(x)) with A gives you garbage.)  That's a relatively rare property for
cryptographic algorithms - but there are examples.

| NEVER willingly give the cryptanalyst the same message encrypted with
| the same system using two different keys.
No modern cryptosystem should be vulnerable against such an attack.  (Security
against chosen-plaintext attacks is a given these days.  If the attacker can
choose the plaintext, he can generate as many examples of this kind of things
he likes.)

Yes, older systems (pre-DES) - and toy systems - may be vulnerable.

| For the simple case, suppose F(X) = X ^ S (exclusive or with a string
| generated from the key).
|
| Then  M = A(M) ^ B(M) ^ B(A(M)), right?
Stream ciphers used in the standard mode - XOR the keystream with the
plaintext - have the property that encryption with any two keys commutes.
*However*, as your example shows, this particular encryption technique *must
not* be used for this key exchange.

| Probably something similar for other symetric systems.
Not necessarily.  Diffie-Helman has a form much like this (though it's not
exactly the same).  It's easy to construct a secure (but not useful!) variant
using RSA:  We give everyone a private/public key pair with respect to a fixed
N = pq, but we discard p and q.  Then, since encryption is just exponentia-
ation mod N, it's easy to see that encryption with any two keys commutes.
Further, the system is exactly as secure as the underlying RSA.  (This isn't
particularly *useful* because given a single private/public key pair, you can
get p and q back - so any participant can read and forge everyone else's
messages.  It is secure against any non-participant, though.)

Going back to the original question:  This idea has been around for a *long*
time.  I think a paper that was released a while back showing work done by the
British government cryptography organization that anticipated RSA's notion of
asymmetric crypto by several years mentioned it.  I think it goes by the name
"two-pass protocol".  The real-world analogue is nice to use in describing DH,
though again it's not *exactly* the same:  Alice takes a box, puts her message
inside it, and attaches her lock to the hasp.  She sends it to Bob, who adds
his own lock to the hasp, and sends it back to Alice.  Alice removes *her*
lock, and sends the box - now secured only by Bob's lock - back to him.  He
can remove his own lock and read the message. Alice and Bob need share no
secrets (i.e., each has a private collections of locks and keys; neither can
unlock the others' locks), but they can securely exchange a message since the
box, with the message inside, is never "out in public" without at least one
lock on it.
							-- Jerry

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