From: wcs@anchor.ho.att.com (bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
Date: Mon, 31 Jan 94 23:55:26 PST
To: cypherpunks@toad.com
Subject: Re:  Matsui-san Attack
Message-ID: <9402010751.AA26117@anchor.ho.att.com>
MIME-Version: 1.0
Content-Type: text/plain


> ]> of a new attack by Mitsuru Matsui of Mitsubishi that requires 2^43
> ]> *known* plaintexts, not chosen ones.  The note I received says that it
> ]> ``breaks the scheme in 50 days on 12 HP9735 workstations''.  This was
> ]> presented last week at the Japanese Conference on Cryptography and
> ]> Information Security.


Fortunately, attacks requiring large quantities of known or chosen
plaintext aren't very relevant to secure email, since typically
each message has a different randomly-selected key used only for
that message; even if you discover the key, it isn't used in previous or
future messages so the compromise is limited.
A 1GB message gives about 2^27 8-byte texts, and if you have that much
known plaintext, you probably don't need to decrypt the rest :-)

On the other hand, if someone had a known-or-chosen plaintext attack on
a public-key algorithm, that would be interesting, since you can
generate as much chosen plaintext as you want.

> 50 days on 12 HP9735 = 600 days on a single HP9735
> The 735 has a pretty fast Mflop rating (compared to Sun, IBM, SGI, PC, and
> Macs).  Using a comparable breaker on the average machine, it is going
> to take two years to "break the scheme".
> That leaves two years to create stronger/tighter strategies.

Crypto usually cares more about integer MIPS than MFLOPS.
I'm not up on current HP models, but 12 HP machines should cost between
$100K and $1M, which makes this attack close to
the second-best attacks on DES, which will break a key in a day for
~$30-50M - Peter Wayner's design used Content Addressable Memory, and
somebody from DEC designed and I think built a Gallium Arsenide DES chip.
The best is Michael Wiener's design using CMOS gate arrays, which
should be able to break a key in about 3-4 hours for $1M.
Doing this well with general-purpose hardware is impressive.

But, yes, this means your PC will still take a while to crack DES;
on the other hand, the NSA has probably been building massively parallel
DES-crackers for a few years, and is more likely to try to break
secure email than most amateurs. :-)

		Bill
# Bill Stewart  AT&T Global Information Systems, aka NCR Corp
# 6870 Koll Center Parkway, Pleasanton CA, 94566 Phone 1-510-484-6204
# email bill.stewart@pleasantonca.ncr.com billstewart@attmail.com
# ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465