From: rja14@cl.cam.ac.uk (Ross Anderson)
Subject: Re: IBM password
Reply-To: rja14@cl.cam.ac.uk (Ross Anderson)
Organization: U of Cambridge, England
Date: Fri, 9 Oct 1992 14:40:04 GMT

In article <1992Oct6.153908.1597@infodev.cam.ac.uk>, I wrote:

||> I looked at what a PC dealer said was the top-selling office automation 
|> suite. It was called Da Vinci or something like that. Look, it's even 
|> got DES encryption!
|> .................           It takes one password of up to eight
|> characters and produces a ciphertext file with visible eight-byte block
|> patterns - must be ECB (or something similar but homemade).
|> 
|> Looks like a PC will be enough to do keysearch on this one: just encrypt
|> a null string with all the passwords in a dictionary, and sort the list.

In article <1992Oct08.185037.113247@watson.ibm.com>, a man from Big Blue 
(inventors of DES) commented:

> Looks like that? OK, try to break it on your PC and post the result (:-).
> Now seriously - it's still unfeasible to break on your home PC,
> or on your business supercomputer. There still are those 2^56
> space for the key, though that stupid ECB mode definitely
> makes it easier for various attacks (and I thought that
> nobody is using ECB in the real world :-). Those
> patterns you spotted aren't going to help you
> much - in order to be able to apply those
> you'll have to have more than 2^40 of
> those 8-bytes blocks with known
> corresponding plaintext (:-).

Rubbish. I'm talking keysearch, not differential cryptanalysis! What is 
the diversity of passwords that people choose? Experience with unix 
password crackers shows that you can guess a fair number of them by 
running through a dictionary. The key space is no longer anything like
2^56 - it'll be somwhere between 2^10 and 2^20.

You check each guess by encrypting a string of blanks by each trial password
until you get the common pattern. In fact, you only have to do these
trial encryptions once, and sort and store the result; you can then see at
once if a ciphertext was created using any of these passwords by just
looking in your list for the common pattern.

Reference: A Konheim (another IBM'mer): `Cryptography - A Primer' p 269ff.

Moral: having a good encryption algorithm is not enough. You also have to 
implement it sensibly.

In fact, one of the main design weaknesses of IBM's cryptographic products - 
such as the 3848 - is that designing the cryptographic protocol is left to 
the user. 

Even among large sophisticated mainframe sites, the density of people with
interest or expertise in cryptography is very low. So you end up with all 
sorts of horrors. 

For example, I've seen the master key for an interbank ATM network printed 
in clear in widely distributed programming documentation; I've come across 
another IBM site using PCF (the software version of the 3848) where the 
master keys for the live and test systems were identical - so programmers 
could work out the personal identification numbers for people's ATM cards 
on their test rig. 

If you want to find a bank's PIN check key, then rather than trying 2^56 
keys for one bank, you'd almost certainly be better to try a few billion 
dumb key choices for a large number of banks.

How many sites have a PIN check key of aaaabbbb where a and b are distinct 
bytes, for example? Even if only 5% of the 20,000 banks on worldwide ATM
networks are this stupid, it's still 1000 banks whose ATMs you can loot
using PC keysearch.

If you really want to do an experiment with a PC, that would be a much more
interesting attack than trashing Da Vinci. Given that most ATMs nowadays 
are networked together, it's enough to be able to break a few banks' keys.

Ross
Newsgroups: comp.security.misc