Newsgroups: sci.crypt
Path: cantaloupe.srv.cs.cmu.edu!magnesium.club.cc.cmu.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!europa.eng.gtefsd.com!howland.reston.ans.net!ira.uka.de!math.fu-berlin.de!news.th-darmstadt.de!minnie!usenet
From: pom@anke.imsd.uni-mainz.DE (Prof. Dr. Klaus Pommerening)
Subject: SUMMARY: DES: init vector as additional key?
Message-ID: <80ZCBWYQ@minnie.zdv.uni-mainz.de>
Keywords: DES, key search, initialisation vector
Sender: usenet@minnie.zdv.uni-mainz.de (USENET News System)
Nntp-Posting-Host: anke.imsd.uni-mainz.de
Organization: Johannes Gutenberg Universitaet Mainz
Date: Thu, 29 Apr 1993 07:54:07 GMT
Lines: 60

At the risk of getting lost in the clipper chip discussion I give a  
summary on my recent question:

In article <PQSCBCNH@minnie.zdv.uni-mainz.de> I wrote:
> The recent discussion in this news group suggests that a key search
> attack  
> against DES is quite feasible now. But normally DES is applied in CBC or 
> CFB  
> mode where one chooses a random init vector of 8 bytes. Questions:
> 
>  - Makes it sense to handle the init vector as an additional key? Then
> we have  
> a 56 + 64 = 120 bit key.
>  
>  - If yes: Is anything known about the security of this key scheme? Can 
> we  
> break it faster than by exhaustive search through the 120 bit key space?

Unfortunately the answer is no - concealing the initialisation vector  
essentially doesn't give any additional security. I got 3 answers (from  
grady@netcom.com, Mark.Lomas@cl.cam.ac.uk, smb@research.att.com) that  
opened my eyes. It's pretty simple:

Say E is encryption (and D decryption) with key K on 64-bit blocks.

Let c[0] be the initialisation vector,
m[1], m[2], ... the message blocks,
c[1], c[2], ... the cipher text blocks.

Then encryption in cipher block chaining (CBC) mode works by the formula

   c[i] = E(m[i] XOR c[i-1]),

and decryption by

   m[i] = c[i-1] XOR D(c[i]).

So if the attacker doesn't have c[0] this only affects the first message  
block m[1]. But she can do her key search attack on m[2], m[3], ...

The situation in cipher feedback (CFB) mode is a bit more complicated but  
similar and left as an exercise for the reader :-)

Finally there is the modified output feedback mode (OFB) where DES (or  
whatever block cipher you use) simply acts as random generator by

   s[i] = E(s[i-1]) with initialisation vector (= seed) s[0],

and encryption is given by

   c[i] = m[i] XOR s[i].

Here the usual `known plaintext' attack against XOR-bitstream ciphers  
reduces the cracking to key search for K.

--
Klaus Pommerening
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet
Obere Zahlbacher Strasse 69, W-6500 Mainz, Germany
