[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Matsui-san Attack
> ]> 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 [email protected] [email protected]
# ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465