From daw@joseph.cs.berkeley.edu Wed Dec  4 13:50:42 PST 1996
Article: 59757 of sci.crypt
Path: agate!not-for-mail
From: daw@joseph.cs.berkeley.edu (David Wagner)
Newsgroups: sci.crypt
Subject: Re: Security of Des key encrypted with its self????
Date: 4 Dec 1996 13:49:06 -0800
Organization: ISAAC Group, UC Berkeley
Lines: 65
Message-ID: <584rki$79n@joseph.cs.berkeley.edu>
References: <omcpcgq00YUn0ZsEc0@andrew.cmu.edu>
NNTP-Posting-Host: joseph.cs.berkeley.edu

In article <omcpcgq00YUn0ZsEc0@andrew.cmu.edu>,
Adrian M Iley  <iley+@andrew.cmu.edu> wrote:
>     Does anyone know how easy it is to derive a Des key or unknown
> plaintexts if the following is done: The des key its self
> (56key+8parity) is used as the IVEC for des_pcbc_encrypt.
	[...]
>     I am especially interested in Known, and/or Chosen plaintext
> attacks, where the key or other unknown plaintexts may be derived. (even
> from repeated encryptions where the IVEC starts as the key)

This is bad, I think.  I describe one way to break it, below.

What system is this?  Is this Kerberos?


Suppose you have some known plaintext, namely the first block of
plaintext P[0], and you observe the corresponding ciphertext C[0].
You'll have the relation
	C[0] = Encrypt(P[0] xor K)
where encryption is done under the key K.

Now I show how to recover K in a chosen-ciphertext attack.  In an
active attack, suppose you intercept a new ciphertext C'[0],C'[1],...
and suppose you have some known plaintext -- namely you can predict
some plaintext block P'[n].  Replace C'[n+1] in the intercepted
ciphertext with C[0], and now inject the modified ciphertext
	C'[0],C'[1],...,C'[n],C[0],C'[n+2],C'[n+3],...,
onto the wire.  Under the premises of the chosen-ciphertext attack,
the attacker obtains the decryption of the modified ciphertext.  In
more detail, suppose the recipient decrypts the modified packet to
obtain the plaintext
	P'[0],P'[1],...,P'[n],P''[n+1],P''[n+2],P''[n+3],...
(Remember that we injected an "error" into the block numbered n+1,
so the decrypted plaintext will match the original sent plaintext
for blocks 0,1,...,n but thereafter will depart.)

Now we can recover K from P[0], P'[n], C'[n], and P''[n+1] in a
straightforward manner with very little work.  By the definition
of PCBC mode, we have the relation
	P''[n+1] = Decrypt(C[0]) xor C'[n] xor P'[n]
	         = P[0] xor K xor C'[n] xor P'[n].
Therefore we may recover K as
	K = P[0] xor C'[n] xor P'[n] xor P''[n+1].
This attack requires one chosen-ciphertext query, a little bit of
known plaintext, and very little computation.

I think this attack may even be practical to mount in real life,
if you can mount an active attack.  Known plaintext is often available
in the form of predictable headers, stereotyped text, etc.  Chosen
ciphertext queries are often available: for example, in an encrypted
telnet application, you wait till the person is in the middle of
typing an email message; then you inject some chosen ciphertext,
let them finish & send off the message, and watch as the email is
transmitted (in the clear!) to/from the SMTP server, recovering the
decryption of the chosen ciphertext in the process.

This attack doesn't really require anything all that special about
PCBC mode -- it just relies on the fact that it's a chaining mode
with limited error propagation.  In fact, I remember someone asking
(a while ago) about the security of CBC mode when the key is used
as the IV; back then I pointed out a (different) attack in a sci.crypt
post which is archived at
	http://www.cs.berkeley.edu/~daw/my-posts/key-as-iv-broken
The moral is, don't ever stick the key into a plaintext or ciphertext
port, or you might get screwed by chosen-plaintext/ciphertext attacks.