Your posting to sci.dcrypt could have been made to a better place.
The discussion list for pem is, and has been for many years,
pem-dev(_at_)tis(_dot_)com(_dot_) That is now the discussion list for the pem
working group
of the IETF, the cognizant standards body. With this message, I am
copying your message to that list. Here's hoping you will join the
discussion. Join the list with a message to
pem-dev-request(_at_)tis(_dot_)com(_dot_)
Regards, -Rob-
SHIREY(_at_)MITRE(_dot_)ORG * tel 703.883.7210 * fax 703.883.1397
Robert W. Shirey, The MITRE Corporation, Mail Stop Z202
7525 Colshire Drive, McLean, Virginia 22102-3481 USA
-------------------------------------------------------
Subject: Privacy-Enhanced Mail: Crypto Problems
From: Terry Ritter, ritter(_at_)cactus(_dot_)org
Date: Fri, 24 Sep 1993 06:35:30 GMT
In article <1993Sep24(_dot_)063530(_dot_)21163(_at_)cactus(_dot_)org> Terry
Ritter,
ritter(_at_)cactus(_dot_)org writes:
After reading about PEM in the August Communications of the ACM and
getting the relevant RFC's, I think we have some crypto problems,
and I think these problems should be recognized. Whether it is too
late to do anything about them is another issue.
PROPOSITION I: No cipher system should announce that the
ciphertext is, in fact, ciphertext.
A cryptanalyst finds a random-like message. Her first question is
whether the message is simply encoded object code for some program
on some machine, versus a real cipher. Any cipher system which
announces that it is a cipher inherently increases the risk of
attack, and, therefore, the risk of successful attack. Thus, the
construct:
----- BEGIN PRIVACY-ENHANCED MESSAGE -----
is cryptographically wrong. Creating such a label makes a message
stand out as one which would be interesting to investigate.
I also note that most of the currently-popular network ciphers do
something similar and are similarly cryptographically challenged.
PROPOSITION II: No cipher system should announce what cipher is
being employed.
A cryptanalyst finds a random-like message, and suspects that it is
a cipher. Her next question is how to attack this cipher. Any
cipher system which helps to answer this question inherently
increases the risk of successful attack. Thus, the construct:
DES-CBC
is cryptographically wrong. Ideally, the cipher process should be
able to vary dynamically from message to message, without external
indication.
Now, it may be argued that it is *necessary* to expose the cipher
type. This argument is wrong. I note that the two ends somehow
manage to exchange secret keys for DES; they could also exchange
cipher and cipher mode. This could be done by requiring each node
to have at least DES-CBC and starting out in that mode. Then one
node would send the other a list of supported ciphers and modes,
one would be chosen, confirmed and used. Ordinarily, private
communications do not occur just once, and thus there is plenty
of opportunity to negotiate stronger security.
PROPOSITION III: The mapping from enciphered binary to network-
transportable ASCII is itself part of the cipher.
It is obviously necessary to restrict the character-set to be used
in network transmission. Thus, it would be reasonable to state
that all ciphers must produce only characters in the set:
{A..Z,a..z,0..9,+,/}.
On the other hand, it is *not* reasonable to require all ciphers to
produce binary output, and then go through a cryptographically-
useless mapping to "transportable ASCII."
The mapping from binary to "transportable ASCII" is an example of
Simple Substitution, which is usually thought of as an incredibly
weak cipher. This opinion, however, is formed in the context of
a natural-language message with very strong statistical associations.
In contrast, enciphered data has virtually no statistical handles,
making the simple mapping to "transportable ASCII" a serious
cryptographic asset. This is a costless opportunity which should
not be neglected. A network cipher should use the cipher key to
generate an individual permutation for use as the network character
mapping.
---
Terry Ritter ritter(_at_)cactus(_dot_)org
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Vesselin Bontchev,
bontchev(_at_)news(_dot_)informatik(_dot_)uni-hamburg(_dot_)de
Date: Fri, 24 Sep 1993 08:39:41 GMT
In article <CDuo26(_dot_)HJ6(_at_)informatik(_dot_)uni-hamburg(_dot_)de>
Vesselin Bontchev,
bontchev(_at_)news(_dot_)informatik(_dot_)uni-hamburg(_dot_)de writes:
Terry Ritter (ritter(_at_)cactus(_dot_)org) writes:
PROPOSITION I: No cipher system should announce that the
ciphertext is, in fact, ciphertext.
Agreed, but first, unless steganogrphy is used, it is pretty trivial
to detect automatically that a message is compressed and/or encrypted
by using just frequency analysis and, second, the two communicating
sides should be able to understand each other that they are going to
exchange encrypted messages. Again, this is trivially intercepted.
PROPOSITION II: No cipher system should announce what cipher is
being employed.
But we are talking about Internet standards here. You could get an
encrypted message from anywhere, with no prior secret information
exchange - how will your system be able to guess what it was encrypted
with?
is cryptographically wrong. Ideally, the cipher process should be
able to vary dynamically from message to message, without external
indication.
The ability to vary the encryption method (e.g., DES, Triple-DES,
IDEA, etc.) from message to message is a good idea, but I don't see
how you can avoid revealing the encryption method.
Now, it may be argued that it is *necessary* to expose the cipher
type. This argument is wrong. I note that the two ends somehow
manage to exchange secret keys for DES; they could also exchange
cipher and cipher mode.
Aha, you mean to encrypt the information about the encryption method
used with the public key of the recepient, as it is currently done
with the secret keys? Yes, that sounds like a really good idea to me!
PROPOSITION III: The mapping from enciphered binary to network-
transportable ASCII is itself part of the cipher.
It is obviously necessary to restrict the character-set to be used
in network transmission. Thus, it would be reasonable to state
that all ciphers must produce only characters in the set:
{A..Z,a..z,0..9,+,/}.
But, both PGP and PEM are already doing that!
not be neglected. A network cipher should use the cipher key to
generate an individual permutation for use as the network character
mapping.
Why? As you have stated yourself, the simple permutation cyphers are
weak and don't provide further security...
Anyway, I have a fourth proposal.
PROPOSITION IV: A public key encrypted message should not reveal who
has signed it or who is able to decrypt it.
In fact, it must be perfectly possible to encrypt a message without
signing it at all. Failing to provide the above capabilities, leaves
the system open to traffic analysis. PEM has this problem - you can't
send unsigned messages and the whole world can see who has signed the
message. PGP has this part of the problem fixed, but it still outputs
messages like 'This message can be decrypted only by "Joe Random
<nobody(_at_)nohost(_dot_)noschool(_dot_)nodomain>"'. IMHO, it should only say
"This
message cannot be decrypted with the secret keys in your keyring" -
and the encrypted message should carry only some kind of checksum
packet that allows to verify whether a message is decryptable with a
particular key or not - and not the full ID of the receiver.
Regards,
Vesselin
--
Vesselin Vladimirov Bontchev Virus Test Center, University of Hamburg
Tel.:+49-40-54715-224, Fax: +49-40-54715-226 Fachbereich Informatik - AGN
< PGP 2.3 public key available on request. > Vogt-Koelln-Strasse 30, rm. 107 C
e-mail: bontchev(_at_)fbihh(_dot_)informatik(_dot_)uni-hamburg(_dot_)de
22527 Hamburg, Germany
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Terry Ritter, ritter(_at_)cactus(_dot_)org
Date: Fri, 24 Sep 1993 19:46:22 GMT
In article <1993Sep24(_dot_)194622(_dot_)3150(_at_)cactus(_dot_)org> Terry
Ritter,
ritter(_at_)cactus(_dot_)org writes:
In <CDuo26(_dot_)HJ6(_at_)informatik(_dot_)uni-hamburg(_dot_)de>
bontchev(_at_)news(_dot_)informatik(_dot_)uni-hamburg(_dot_)de (Vesselin
Bontchev) writes:
PROPOSITION I: No cipher system should announce that the
ciphertext is, in fact, ciphertext.
Agreed, but first, unless steganogrphy is used, it is pretty trivial
to detect automatically that a message is compressed and/or encrypted
by using just frequency analysis and, second, the two communicating
sides should be able to understand each other that they are going to
exchange encrypted messages. Again, this is trivially intercepted.
The issue is precisely the fact that compression or even simple
translation to "network ASCII" can have good statistics, and yet
not be ciphers. This might well be confusing to, for example, some
Law Enforcement technicians. Just how "trivial" is it for even the
least informed to detect that someone is using a cipher when the
cipher itself announces that fact to the world?
PROPOSITION II: No cipher system should announce what cipher is
being employed.
[...]
Aha, you mean to encrypt the information about the encryption method
used with the public key of the recepient, as it is currently done
with the secret keys? Yes, that sounds like a really good idea to me!
Another option is to start out in a common mode, and then negotiate
higher security from an essentially unbounded set of possible
ciphers and modes. The negotiation itself could be "piggybacked"
on normal message transmission, thus allowing frequent changes in
strategy.
PROPOSITION III: The mapping from enciphered binary to network-
transportable ASCII is itself part of the cipher.
Why? As you have stated yourself, the simple permutation cyphers are
weak and don't provide further security...
I don't recall saying any such thing. Judge for yourself:
The mapping from binary to "transportable ASCII" is an example of
Simple Substitution, which is usually thought of as an incredibly
weak cipher. This opinion, however, is formed in the context of
a natural-language message with very strong statistical associations.
In contrast, enciphered data has virtually no statistical handles,
making the simple mapping to "transportable ASCII" a serious
cryptographic asset. This is a costless opportunity which should
not be neglected. A network cipher should use the cipher key to
generate an individual permutation for use as the network character
mapping.
Simple Substitution on random-like data is not weak. Unless, of
course, you have an attack I have not heard of . . . .
Like most things in cryptography, Simple Substitution is a tool,
which can be used properly or improperly. Since such an operation
must occur anyway to get to or from "network ASCII," we have an
opportunity to use it properly (in the cryptographic sense), for
only the cost of initializing the permutation. Certainly this
should not be prohibited.
PROPOSITION IV: A public key encrypted message should not reveal who
has signed it or who is able to decrypt it.
Good!
Anybody have any more?
And why didn't the PEM people have this discussion with us, here in
sci.crypt, the home of crypto experts on Internet, before proposing
an Internet standard which uses cryptography on the Internet?
---
Terry Ritter ritter(_at_)cactus(_dot_)org
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Lulu of the lotus-eaters,
quilty(_at_)twain(_dot_)ucs(_dot_)umass(_dot_)edu
Date: 24 Sep 1993 23:21:23 GMT
In article <27vvdj$mjc(_at_)nic(_dot_)umass(_dot_)edu> Lulu of the lotus-eaters,
quilty(_at_)twain(_dot_)ucs(_dot_)umass(_dot_)edu writes:
Terry Ritter (ritter(_at_)cactus(_dot_)org) wrote:
: PROPOSITION I: No cipher system should announce that the
: ciphertext is, in fact, ciphertext.
: PROPOSITION II: No cipher system should announce what cipher is
: being employed.
Does the phrase "security by obscurity" come to mind? Do the problems
with the proposition then well up in one's mind immediately afterward?
Yours, Lulu...
_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY: Postmodern Enterprises _/_/_/
_/_/
~~~~~~~~~~~~~~~~[quilty(_at_)philos(_dot_)umass(_dot_)edu]~~~~~~~~~~~~~~~~~
_/_/
_/_/ The opinions expressed here must be those of my employer... _/_/
_/_/_/_/_/_/_/_/_/_/ Surely you don't think that *I* believe them! _/_/
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Roger Bryner, bryner(_at_)chemistry(_dot_)utah(_dot_)edu
Date: Sun, 26 Sep 1993 23:09:44 GMT
In article
<bryner(_dot_)28(_dot_)749084984(_at_)chemistry(_dot_)utah(_dot_)edu> Roger
Bryner,
bryner(_at_)chemistry(_dot_)utah(_dot_)edu writes:
In article <CDxDCA(_dot_)81J(_at_)acsu(_dot_)buffalo(_dot_)edu>
boyd(_at_)acsu(_dot_)buffalo(_dot_)edu (Daniel F Boyd)
writes:
From: boyd(_at_)acsu(_dot_)buffalo(_dot_)edu (Daniel F Boyd)
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
Date: Sat, 25 Sep 1993 19:40:58 GMT
In article <1993Sep24(_dot_)063530(_dot_)21163(_at_)cactus(_dot_)org>
ritter(_at_)cactus(_dot_)org (Terry Ritter) writes:
----- BEGIN PRIVACY-ENHANCED MESSAGE -----
is cryptographically wrong. Creating such a label makes a message
stand out as one which would be interesting to investigate.
The fundamental assumption of cryptography: the security of the system
lies only in the keys.
In the worst case, only. Would you have a problem even begining work on
breaking clipper?
Don't worry about the enemy noticing that you're exchanging encrypted
messages; they're going to try to read whatever you send anyway, just
because you're the one who sends it.
Not so. Even huge agencies have budgets. They can not look at everything.
Don't worry about the enemy knowing what cipher system you're using;
if it's strong enough then they are helpless without the key.
I think the more important point is, say you switch between 16 different
systems. This only adds four bits to the key, and also means that you
have to examine 16 different systems! Plus, if one of them is realy stupid,
you have shot yourself in the foot by using it.
Don't worry about trivialities like the encoding into ASCII; if
that was part of the cipher then you'd analyze it as such.
Yes, it would provide absolutily no security, just obscurity. Why is this
bad? The search algorithim for "BEGIN SECRET STUFF" is much smaller and
cheeper than the algorithim to distinguish ASCI psudo-code made to have
even a slight resembalance to english text.
All the issues you've mentioned are irrelevant to real security.
It seems to me that the issues are relevant to real world security, but
not to ideal security. Ideal security is nice, and incredibly powefull,
and usefull, but is not everything.
I realise this is SCI.CRYPT and most people in scientific cryptology concern
themselves with the much harder problem of ideal security, but maby there
should be a field of engineering.crypt:) to deal with this stuff.
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Edward J. Huff, huff(_at_)mcclb0(_dot_)med(_dot_)nyu(_dot_)edu
Date: 25 Sep 93 02:14:04 EST
In article <1993Sep25(_dot_)021404(_dot_)1(_at_)mcclb0> Edward J. Huff,
huff(_at_)mcclb0(_dot_)med(_dot_)nyu(_dot_)edu writes:
In article <27vvdj$mjc(_at_)nic(_dot_)umass(_dot_)edu>,
quilty(_at_)twain(_dot_)ucs(_dot_)umass(_dot_)edu (Lulu of the
lotus-eaters) writes:
Terry Ritter (ritter(_at_)cactus(_dot_)org) wrote:
: PROPOSITION I: No cipher system should announce that the
: ciphertext is, in fact, ciphertext.
: PROPOSITION II: No cipher system should announce what cipher is
: being employed.
Does the phrase "security by obscurity" come to mind? Do the problems
with the proposition then well up in one's mind immediately afterward?
Actually, no. What are they?
Security by obscurity is just another way of saying you can't read
the message unless you know the key. All cryptosystems are "by obscurity"
in that sense. If you just knew the key, you could read the message.
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: David K. Merriman, merriman(_at_)organic_sw(_dot_)win(_dot_)net
Date: Mon, 27 Sep 1993 01:02:12 GMT
In article <626(_at_)organic_sw(_dot_)win(_dot_)net> David K. Merriman,
merriman(_at_)organic_sw(_dot_)win(_dot_)net writes:
In article <1993Sep24(_dot_)194622(_dot_)3150(_at_)cactus(_dot_)org>, Terry
Ritter
(ritter(_at_)cactus(_dot_)org) writes:
PROPOSITION IV: A public key encrypted message should not reveal who
has signed it or who is able to decrypt it.
Would that include (encrypted) identification of the sender?
Dave Merriman
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
David K. Merriman
InterNet:merriman(_at_)organic_sw(_dot_)win(_dot_)net
3612 N. Country Club, Ste. 271 CompuServe: 71043,3153
Irving,TX 75062-3406
(214) 257-1215
"I must caution you, Terran, not to underestimate my powers....."
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Terry Ritter, ritter(_at_)cactus(_dot_)org
Date: Mon, 27 Sep 1993 07:18:00 GMT
In article <1993Sep27(_dot_)071800(_dot_)2489(_at_)cactus(_dot_)org> Terry
Ritter,
ritter(_at_)cactus(_dot_)org writes:
In <bryner(_dot_)28(_dot_)749084984(_at_)chemistry(_dot_)utah(_dot_)edu>
bryner(_at_)chemistry(_dot_)utah(_dot_)edu
(Roger Bryner) writes:
Don't worry about trivialities like the encoding into ASCII; if
that was part of the cipher then you'd analyze it as such.
Yes, it would provide absolutily no security, just obscurity.
So one might think. But I disagree.
Simple Substitution, *when used on random-like data*, can be a
strong transformation. But don't take *my* word for it:
"An example [of a 'strongly ideal' system] is a simple
substitution on an artificial language in which all
letters are equiprobable and successive letters
independently chosen."
Shannon, C. 1949. Communication Theory of Secrecy Systems.
Bell System Technical Journal. 28: 656-715.
(Section 17. Ideal Secrecy Systems. p. 699.)
Moreover, sufficient obscurity *is* security. Most ciphers are
based on the "needle-in-a-haystack" paradigm: The correct key
must be there, somewhere, and is protected only because there are
so many other keys which all look alike. In a very real sense,
DES itself provides only obscurity--hopefully, 56-bits of it.
A paraphrase: "Since DES uses substitution and substitution
provides absolutely no security, DES provides absolutely no
security." Not.
The output of DES is random-like; adding an unknown substitution
at this point means that The Opponent must be prepared to try each
possible transformation before even getting to DES. This is not
the same situation as a newspaper cipher, because DES has no (known)
ciphertext statistics which would help disclose the transformation.
Note that a Simple Substitution on N symbols has N! "keys."
The DES 56-bit key (2^56 key values) selects only a tiny subset
of the 64! possible 64-bit-to-64-bit substitutions. This means
that there is plenty of room for new overall substitutions which
are different than those otherwise available through DES alone.
Stronger DES under PEM
The network ASCII transformation normally used (and described under
PEM RFC's) is a 6-bit (64-element) substitution. That is, we chop
a 64-bit binary DES ciphertext block into 6-bit chunks, and convert
each to an ASCII character for transmission. Naturally, it takes
10+ of these chunks to send a single DES block.
Now assume that we create 11 different 64-entry substitution tables
and permute each under control of the User Key: (Normally, we
hash a key phrase into a substantial cryptographic RNG and use the
sequence to drive a shuffle for each table; a different hash drives
the DES key.) Instead of using a single pre-defined table, we use
a different unknown table for each chunk.
Now consider a known-plaintext attack on the new design: The
Opponent has both the ciphertext (*after* the transformation to
ASCII) and the plaintext for a particular block, and is working on
finding the key. One would imagine that this could be done by
trying all possible keys, one after the other (and this is the
usual basis for the theoretical design of key-search engines which
form the usual impression of cipher strength).
But trying each DES key, by itself, will not work on the design with
the 11 unknown tables, because if even a single ciphertext bit from
one table is wrong, DES will produce completely-different plaintext
which will not match the known plaintext. (It is important that
DES does not produce almost-correct results given almost-correct
input.) Thus, it is now necessary for The Opponent to brute-force
search the tables *as well* as DES, thus adding another 64 bits to
a brute-force search. Since the network translation is required
anyway, this added strength costs almost *nothing* in terms of
throughput (and just 11 shuffles of 64-element tables--something
like 1,000 RNG steps--during init).
I should point out that the small block size used in DES is
vulnerable to other attacks based on the very limited uncertainty
of language text when directly used as plaintext. (Some forms of
data-compression might thus provide additional security in DES
systems.) However, preventing normal brute-force attacks at
virtually no cost seems like a worthwhile engineering tradeoff,
one which certainly should not be prevented by the PEM
specifications themselves.
---
Terry Ritter ritter(_at_)cactus(_dot_)org
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Paul Crowley, pdc(_at_)dcs(_dot_)ed(_dot_)ac(_dot_)uk
Date: Mon, 27 Sep 1993 10:30:20 GMT
In article <CE0D6L(_dot_)C0(_at_)dcs(_dot_)ed(_dot_)ac(_dot_)uk> Paul Crowley,
pdc(_at_)dcs(_dot_)ed(_dot_)ac(_dot_)uk writes:
Quoting bryner(_at_)chemistry(_dot_)utah(_dot_)edu (Roger Bryner) in article
<bryner(_dot_)28(_dot_)749084984(_at_)chemistry(_dot_)utah(_dot_)edu>:
Don't worry about the enemy noticing that you're exchanging encrypted
messages; they're going to try to read whatever you send anyway, just
because you're the one who sends it.
Not so. Even huge agencies have budgets. They can not look at everything.
I'd much prefer a cryptosystem that used uuencode as its ASCII armour.
If you got a uuencoded file you weren't expecting and you couldn't work
out what it was, you could try decrypting the first block with your
private key to see if it turned into "IDEA_KEY: 1dd9e92634f63" or some
such. There's no way of telling what a uuencoded message is supposed to
be, and it makes things about a million times harder for anyone who's
looking for encrypted messages. Clearly, any message that passes every
randomness test once uudecoded is suspicious, since even compressed
output doesn't do that, but this is a very expensive test and it's very
hard to be sure.
Why should people who want to use secure crypto have to announce the
fact to the NSA? I'd really appreciate a good reply to this.
__ _____
\/ o\ Paul Crowley pdc(_at_)dcs(_dot_)ed(_dot_)ac(_dot_)uk \\ //
/\__/ Trust me. I know what I'm doing. \X/
PGPprint: 42A47697 54144EA4 BACFA9FD C9433347
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Daniel F Boyd, boyd(_at_)acsu(_dot_)buffalo(_dot_)edu
Date: Mon, 27 Sep 1993 14:57:22 GMT
In article <CE0pJn(_dot_)A7C(_at_)acsu(_dot_)buffalo(_dot_)edu> Daniel F Boyd,
boyd(_at_)acsu(_dot_)buffalo(_dot_)edu writes:
In article <1993Sep27(_dot_)071800(_dot_)2489(_at_)cactus(_dot_)org>
ritter(_at_)cactus(_dot_)org (Terry Ritter) writes:
(Normally, we hash a key phrase into a substantial cryptographic
RNG and use the sequence to drive a shuffle for each table; a
different hash drives the DES key.)
Ok, so what you're really doing is increasing the key length by adding
the keyphrase. An increased key length increases the cost -- which
you're conveniently ignoring when you say this system has no increased
cost.
Also, what particular 'substantial cryptographic RNG' are you talking
about? You are using special pleading; this RNG you're going to pull
out of your hat is where the all the supposed security of your idea
comes from. I don't know how expensive this cryptographic RNG is
going to be.
But trying each DES key, by itself, will not work on the design with
the 11 unknown tables, because if even a single ciphertext bit from
one table is wrong, DES will produce completely-different plaintext
which will not match the known plaintext.
You seem to think a known-plaintext attack consists of DECRYPTING with
all possible keys until you find one that correctly decrypts the
CIPHERTEXT. That's one way, sure -- but another way is to ENCRYPT
with all possible keys until I fine one that correctly encrypts the
PLAINTEXT.
With your system I can still do this forward attack on the DES part.
When I hit the right DES key, I get a DES ciphertext that will have
frequency statistics that match those of the ASCII-armored ciphertext.
Since the ASCII ciphertext is only one simple-substitution away from
my DES ciphertext, their frequency-distribution stats will match, and
I can check this in an automated way.
The shuffle table doesn't change over the entire message, so for each
DES key I try, I encrypt several ($n$) blocks worth of the known
plaintext. Each DES-encrypted block contains 11 chunks; there are 11
shuffle tables.
Now I look at the first chunk of each of the $n$ blocks, and compare
them to the corresponding first chunk of each of the shuffled
ciphertext blocks. I know that each of these (chunk, shuffled-chunk)
pairs has been shuffled by the same one of your shuffle tables.
Now I look for collisions. This is where two identical chunks map to
two different results, or two different chunks map to the same result.
If there are no collisions, (meaning that the DES key I've chosen
isn't inconsistent with any possible shuffle table) then I set asisde
this particular DES key to be examined later. Call this a 'hit'. If
I find a collision, any collision at all, I know I have the wrong DES
key (a miss) and I go on to the next DES key.
I will have exactly one true hit (the correct DES key) and possibly
many false hits. The longer the sample I try (the larger $n$ is) then
the less likely a false hit is. Indeed, I can try more blocks on each
DES key until I get a miss; this is cheaper than looking at the
statistics since I'm probably searching with a hardware DES chip.
Let's look at things carefully, OK? If the attacker doesn't know the
correct DES key, then he can't decrypt, period.
So assume the attacker knows the correct DES key. Now, solving the
system is trivial; it's just a simple substitution.
So your system is no stronger than DES.
Thus, it is now necessary for The Opponent to brute-force
search the tables *as well* as DES, thus adding another 64 bits to
a brute-force search.
There are 64 factorial possible substitution tables. This is not 64
bits, it is almost 296 bits per table. There are 11 tables, so this
means 3256 extra key bits. You are surreptitiously adding these 3256
bits onto the key length, but as I've shown, they don't help.
Since the network translation is required anyway, this added
strength costs almost *nothing* in terms of throughput (and just 11
shuffles of 64-element tables--something like 1,000 RNG
steps--during init).
The regular mapping to ASCII is done by addition and shifting; this
can be done all in registers. Your mapping requires a table lookup on
each character. I agree that your mapping is not very expensive.
What you're missing is that your mapping doesn't make the system more
secure.
I should point out that the small block size used in DES is
vulnerable to other attacks based on the very limited uncertainty
of language text when directly used as plaintext.
You are probably ignoring CFB mode when you talk about this.
(Some forms of data-compression might thus provide additional
security in DES systems.)
Yes; you should compress before encrypting. Compressing after
encryption is silly.
However, preventing normal brute-force attacks at
virtually no cost seems like a worthwhile engineering tradeoff,
one which certainly should not be prevented by the PEM
specifications themselves.
It's not 'virtually no cost'. It adds an entire new algorithm (the
cryptographic RNG you glossed over), thousands of bits to the key
length, and is still no stronger than DES.
Subject: Re: Privacy-Enhanced Mail: Crypto Problems
From: Daniel F Boyd, boyd(_at_)acsu(_dot_)buffalo(_dot_)edu
Date: Sat, 25 Sep 1993 19:40:58 GMT
In article <CDxDCA(_dot_)81J(_at_)acsu(_dot_)buffalo(_dot_)edu> Daniel F Boyd,
boyd(_at_)acsu(_dot_)buffalo(_dot_)edu writes:
In article <1993Sep24(_dot_)063530(_dot_)21163(_at_)cactus(_dot_)org>
ritter(_at_)cactus(_dot_)org (Terry Ritter) writes:
----- BEGIN PRIVACY-ENHANCED MESSAGE -----
is cryptographically wrong. Creating such a label makes a message
stand out as one which would be interesting to investigate.
The fundamental assumption of cryptography: the security of the system
lies only in the keys.
Don't worry about the enemy noticing that you're exchanging encrypted
messages; they're going to try to read whatever you send anyway, just
because you're the one who sends it.
Don't worry about the enemy knowing what cipher system you're using;
if it's strong enough then they are helpless without the key.
Don't worry about trivialities like the encoding into ASCII; if
that was part of the cipher then you'd analyze it as such.
All the issues you've mentioned are irrelevant to real security.