[3881] in cryptography@c2.net mail archive
On leaving the 56-bit key length limitation
daemon@ATHENA.MIT.EDU (Ed Gerck)
Wed Dec 30 20:15:01 1998
Date: Tue, 29 Dec 1998 01:21:28 -0200 (EDT)
From: Ed Gerck <egerck@mcg.org.br>
To: cryptography@c2.net
List:
After reading gazillions of messages on the "weak cryptography" that
looms upon some of us, due to recent 56-bit symmetric key-length
limitations of the Wassenaar Arrangement, it is perhaps time to thank
the various Jonahses for the wake-up call and take a different look
to life in Niniveh. And, similarly to Ninivians, I intend to show
below that the solution lies in our hands and we can indeed leave the
56-bit key length limitation -- not live with it.
1. First, I wish to point out that Theoretically-Secure Cryptographic
Systems (hereafter TSCS) do not depend on key-length for secrecy --
in their design region. In fact, Shannon already showed 50 years ago
that a TSCS does not depend on key-length when one works within the
system's "unicity distance". So, the factor we need to work on in
order to protect our privacy is "unicity distance" -- not key length.
And, as we all know, Wassenaar does not impose a limit on maximum
"unicity distance". So, we are free in regard to what matters to us,
our privacy, and we can leave the key length limitation.
2. Even though one usually thinks only of "one-time pads" and XOR
encoding when talking about theoretically secure systems, this is
just the simplest case. Almost any cryptographic system (DES, IDEA,
RSA, RC4, RC5, Twofish, etc.) is theoretically secure if used within
its "unicity distance" -- for example, even simple XOR encoding.
3. It is interesting to note that a TSCS cannot be attacked by
exaustive key-search -- denying thus the very "brute-force attack"
that looms over protocols under key length limitations. So, I can
even safely use 56-bit DES (notwithstanding fast and cheap hardware
key-searching devices) within a TSCS's design region.
4. A TSCS is secure against any attacker, including a computationally
unbounded attacker -- both in time, space and resources. Which may
well represent the broad level of attackers one may face in an open
environment, when compared with private resources.
5. Even though current versions of protocols such as SSL/TLS, S/MIME
and PGP ignore the issues of "unicity distance" (and indeed
compromise security for short key lengths)... this can IMO be
improved quite competitively and fast, to provide commercially useful
message lengths even under current key-length limitations. For
example, would a user feel limited if I say 56 Kbyte messages are
allowed for each 56-bit session key -- with theoretically unbreakable
security?
6. The final word on cryptographic strength is thus not to be found
in enforced export controls for key length. It is to be found in our
own drawing boards in terms of a system's "unicity distance" and its
derived design issues, which is feasible to deal with and lies in our
hands.
7. To reach the heart of the matter, one must devise ways to thwart
automatic surveillance decoding -- which is additional from only
making it harder or theoretically-impossible to decipher the
messages, as dealt with by TSCSs. The objective here is to make
decryption either ambiguous or ambiguously related to the key, even
if sucessful (say, by collusion, forced escrow, etc.). So, the
attacker would have difficulties to detect that a key does NOT work,
that it DOES work, and what the decrypted message is, from a possible
list of choices. To contrast, in DES, a given key either produces
garbage or readable text -- too easy for an attacker. One simple
suggestion is to reverse one or two random bits in each encrypted
block of a TSCS (in a block's "salt window" defined for example by
the key itself) so that automatic decoders would have to be much
augmented to cover the enlarged search space and search time would
also increase for every tried key (the user would do all that rather
quickly, since he has the right key). Another suggestion is to
develop TSCSs that can provide ambiguous and meaningful decryptions
-- which the user's system can choose based on some trusted
information provided out-of-band. This would also allow the user to
be able to always repudiate a message, either sent as his own or
received as by him, protecting his privacy if needed.
To close, in order to extract the full benefit from such approach to
security as commented in the seven items above, I believe that one
must first revisit the concept of "unicity distance" -- since it is
usually regarded more as a "proof-of-concept" definition than a
practical tool. Which is IMO due to a series of unfortunate
historical facts -- beginning with the name, since it is not a
"distance" (i.e., it is not a metric function that provides
distance).
BTW, on leaving the 56-bit key length limitation we may well bid
farewell to security systems which do not take into account the
message's statistics and perfunctorily pad bits -- which is a funny
flaw, since the attackers of such systems always tend to do
otherwise.
Comments?
Cheers,
Ed Gerck
______________________________________________________________________
Dr.rer.nat. E. Gerck egerck@mcg.org.br
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
