Known plaintext considered harmless
lcs Mixmaster Remailer
plaintext. They have heard that known plaintext can give a cryptanalyst
an entry point into breaking ciphers. Accordingly they fear known
plaintext and try to avoid it.
Sometimes they will even complicate their data structures or protocols
in order to avoid known plaintext. They will incorporate compression
for no good reason, or restructure headers, or make sure that fields
set aside for future expansion hold random values rather than zeros.
All this complicates their overall system design and introduces new
possibilities for errors.
We need to communicate clearly that known plaintext is no longer an issue.
With modern ciphers and a reasonable chaining mode, you don't have
to worry about known plaintext. If your cipher is weak against known
plaintext, you should be using a different cipher.
When designing data which will be protected by a cipher, the only
consideration should be the needs to which the data will be put.
Design for clarity and convenience.
NO CONSIDERATION WHATSOEVER should be given to manipulating or
constraining the data structures in the hopes of making the encryption
stronger!
In your overall system, the cipher is there to do the job of protecting
the plaintext. The job of the plaintext is to represent whatever data
is being communicated. Don't be misled into blurring these boundaries.
Modern ciphers are fully capable of providing confidentiality with any
and every plaintext. Let the cipher do its job, don't try to "help"
it in the other parts of your design.
Let us all agree that it is time to put concerns about known plaintext
behind us. Recommendations to avoid it are obsolete.
Terry Ritter
On 19 Jun 2001 05:20:32 -0000, in
<200106190520...@nym.alias.net>, in sci.crypt lcs Mixmaster
Remailer <m...@anon.lcs.mit.edu> wrote:
>[...]
>Let us all agree that it is time to put concerns about known plaintext
>behind us. Recommendations to avoid it are obsolete.
No.
"Known-plaintext" is an information condition; it is the condition of
knowing both the input to -- and the output from -- the secret
transformation. The value of such knowledge to any real attack should
be obvious.
Modern ciphers are indeed designed to resist known-plaintext. That is
a noble design goal. Whether or not it has been achieved is, of
course, of some continuing interest.
---
Terry Ritter rit...@io.com http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Tim Tyler
: NO CONSIDERATION WHATSOEVER should be given to manipulating or
: constraining the data structures in the hopes of making the
: encryption stronger! [...]
: Let us all agree that it is time to put concerns about known plaintext
: behind us. Recommendations to avoid it are obsolete.
You go far too far. While tying yourself in knots to avoid known
plaintext may be over the top, avoiding it *is* desirable.
You presume that cryptanalytic attack is the only possible method of
getting information relating to the key of a cypher. This is not the
case. If the number of possible keys can be reduced - by any means -
known-plaintext attacks can become a practical issue.
--
__________
|im |yler t...@iname.com Home page: http://alife.co.uk/tim/
John Myre
<snip>
> You go far too far. While tying yourself in knots to avoid known
> plaintext may be over the top, avoiding it *is* desirable.
But the question is: *how* desirable? Exactly how much effort
is it worth? I'd agree with (anonymous) that the proper solution
is to reinforce the cipher. Failure of software systems due to
unwarranted complexity is a *bad* problem.
> You presume that cryptanalytic attack is the only possible method of
> getting information relating to the key of a cypher.
?
> This is not the
> case. If the number of possible keys can be reduced - by any means -
> known-plaintext attacks can become a practical issue.
That is at best an exaggeration. You can reduce the number of
possible keys quite easily by brute force: guess a few keys,
decrypt the entire message for each guess, and discard the ones
that are clearly nonsense. (We must assume that any keyless
transformations (e.g., compression) are known to the attacker.)
In practice - this is simply not an issue.
The point is that if a simple keysearch can be made practical,
because the entropy (unknown bits in the key) is small enough,
then using obfuscation on the source text as a way to prevent
that attack is almost certainly pointless.
Terry's response is more reasoned. The suspicion that maybe we
are all fooling ourselves, that there *aren't* any ciphers that
we can trust are as strong as we think, is at least defensible.
I think he's wrong, but of course I can't prove it.
JM
John Myre
<snip>
> "Known-plaintext" is an information condition; it is the condition of
> knowing both the input to -- and the output from -- the secret
> transformation. The value of such knowledge to any real attack should
> be obvious.
>
> Modern ciphers are indeed designed to resist known-plaintext. That is
> a noble design goal. Whether or not it has been achieved is, of
> course, of some continuing interest.
Which is the point. Many experts believe that it has, which would
mean that the "obvious" value of known plaintext is in fact "very
little".
The lack of a proof for such strength is, in my view, insufficient
evidence for weakness such that plaintext manipulations specifically
to help the cipher are warranted. It's an engineering point of
view: separate the encryption itself from the rest of the application.
JM
lbudney...@nb.net
>
> The lack of a proof for such strength is, in my view, insufficient
> evidence for weakness such that plaintext manipulations specifically
> to help the cipher are warranted.
Note, however, that reducing known plaintext is trivial; compression
helps quite a lot. The cipher should be strong enough not to depend on
compression (or anything else), but not doing compression is just silly!
(1) It makes encryption easier by shrinking the file.
(2) It saves bandwidth by shrinking the ciphertext.
(3) Reducing known plaintext certainly can't hurt.
I would agree (for what that's worth!) if you'd said that *extreme*
efforts to eliminate known plaintext is just silly. But I wouldn't
deprecate an inexpensive measure which probably helps and definitely
has other benefits.
Len.
--
Wow. Another unbiased evaluation from Nick ``claims against Exim's
security ... firmly grounded in prejudice'' Maclaren.
-- Dan Bernstein, author of qmail
Terry Ritter
On Tue, 19 Jun 2001 10:46:22 -0600, in <3B2F81DE...@sandia.gov>,
in sci.crypt John Myre <jm...@sandia.gov> wrote:
>[...]
>Terry's response is more reasoned. The suspicion that maybe we
>are all fooling ourselves, that there *aren't* any ciphers that
>we can trust are as strong as we think, is at least defensible.
I think that viewpoint is not only defensible but also *appropriate*
for security analysis. (Also, the issue is not so much that no strong
ciphers exist, but that the particular cipher we propose to use may
have weakness.)
>I think he's wrong, but of course I can't prove it.
Wrong? How can it be *wrong* to have a suspicion of weakness, when
the assertion of strength is not based on proven fact?
Absent proof of strength in practice, suspicion of weakness is
entirely appropriate. We need to consider the consequences of our
hopes being wrong.
John Myre
<snip>
> Note, however, that reducing known plaintext is trivial; compression
> helps quite a lot. The cipher should be strong enough not to depend on
> compression (or anything else), but not doing compression is just silly!
>
> (1) It makes encryption easier by shrinking the file.
> (2) It saves bandwidth by shrinking the ciphertext.
> (3) Reducing known plaintext certainly can't hurt.
>
> I would agree (for what that's worth!) if you'd said that *extreme*
> efforts to eliminate known plaintext is just silly. But I wouldn't
> deprecate an inexpensive measure which probably helps and definitely
> has other benefits.
All true. But note that (the best) two of the three reasons
have nothing to do with cryptographic security. It will of
course be rare that compression cannot be justified, in
practice. I just think it's wrong to bring security into the
decision, because it's too easy to get your priorities wrong.
JM
Terry Ritter
On Tue, 19 Jun 2001 11:08:59 -0600, in <3B2F872B...@sandia.gov>,
in sci.crypt John Myre <jm...@sandia.gov> wrote:
>Terry Ritter wrote:
><snip>
>> "Known-plaintext" is an information condition; it is the condition of
>> knowing both the input to -- and the output from -- the secret
>> transformation. The value of such knowledge to any real attack should
>> be obvious.
>>
>> Modern ciphers are indeed designed to resist known-plaintext. That is
>> a noble design goal. Whether or not it has been achieved is, of
>> course, of some continuing interest.
>
>Which is the point. Many experts believe that it has, which would
>mean that the "obvious" value of known plaintext is in fact "very
>little".
The "obvious" value to which I referred is the process of
cryptanalysis itself:
Some keyed function takes plaintext to ciphertext. Consider trying to
expose that function while knowing only the plaintext but not the
ciphertext, or knowing the ciphertext but not the plaintext. We can
create toy examples for which this is easy, but in general, this is
very tough. Not knowing both the input and the output acts to hide
the ciphering function itself.
Now consider trying to expose the ciphering function knowing both the
plaintext and the ciphertext. We expect this to be tough anyway, if
we assume (that is, make an ASS out of U and ME) the cipher design is
strong. But we wouldn't have to hope as hard if there were no known
plaintext in the first place.
lcs Mixmaster Remailer
which appeared a few hours ago:
: From: Thierry Nivon <tni...@waika9.com>
: Date: Tue, 19 Jun 2001 22:50:33 +0200
: Message-ID: <9godml$2ou$2...@fenris.isp.9tel.net>
:
: because the beginning of the document is always (nearly) the same
: <xml ....
: wich brings a little (verry little) bit of information
:
: Thierry Nivon
:
: Mok-Kong Shen wrote:
:
: >
: > I read somewhere an article stating that the possibility
: > in the new standard for XML-security of user selective determination of
: > parts of an XML document to be encrypted
: > is essential, for otherwise one could encrypt only the
: > whole document and that would be bad for security. Could
: > someone explain why the encryption of the whole document
: > is bad in clear-cut terms? Thanks in advance.
: >
: > M. K. Shen
We see a claim that piecewise encryption of XML documents is essential,
with the suggested reason being that otherwise there is known plaintext
in that every document starts with "<xml".
Of course, it's unlikely that this is the true reason why the XML
encryption effort is supporting encryption of subparts. But it is
disturbing that it is offered as an explanation, that someone presumably
at least slightly knowledgeable in cryptography believes that it is
unsafe to encrypt XML documents because they all start the same way.
This is exactly the error which the cryptographic community must correct.
For too long have naive and inexperienced users been taught to fear
known plaintext and to produce elaborate monstrosities in a futile
attempt to avoid weakening their encryption. It is an abrogation of
the responsibility of professional cryptographers to allow users of this
technology to suffer under such a misconception.
Imagine if this attitude were allowed to go uncorrected, and if the
XML encryption group had actually adopted the need to encrypt parts, a
requirement which has added tremendous complexity to the specification,
purely out of a misguided fear about known plaintext! This disaster would
be the fault, ultimately, of the cryptographic community for failing to
speak with a clear and united voice on this issue.
It is time to put this sad error to an end. Known plaintext is not
harmful, and will not weaken a properly-applied encryption transform.
SCOTT19U.ZIP_GUY
<2001061922403...@nym.alias.net>:
>
>It is time to put this sad error to an end. Known plaintext is not
>harmful, and will not weaken a properly-applied encryption transform.
>
Actually any known plaintext is harmful and will weaken an ecryption
system. But if you properly compress to remove the common known parts
then you apply the encryption. Since if they are known they can be
added in during the decryption decompression process.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
John Savard
wrote, in part:
>It's an engineering point of
>view: separate the encryption itself from the rest of the application.
That does have validity, although there are also cases when the
encryption _is_ the application, in which case that concern does not
apply.
Also, a "reasonable chaining mode" leaves some latitude for doing, in
the encryption, things that might be done elsewhere.
However, if the application tends to leave certain fields blank, does
it make sense to separate this from, say, the _compression_ stage? If
there is nothing wrong about a compressor receiving side information
about its input, so as to be able to compress it more efficiently,
then can't we make similar allowances for an encryption stage? (Thus,
part of the decryption will be to restore the blank fields and so on,
with some short indicator handling the possibility that they will stop
being blank in future expansion.)
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
John Savard
wrote, in part:
>The point is that if a simple keysearch can be made practical,
>because the entropy (unknown bits in the key) is small enough,
>then using obfuscation on the source text as a way to prevent
>that attack is almost certainly pointless.
It's true that the old days of 40-bit keys are now behind us...finding
a way to achieve security under such a constraint may well be an
impossible challenge, but not entirely without value.
Particularly if those days might be coming back - in effect. What if
quantum computers start appearing at corner computer stores near you?
Won't simple keysearch get a lot simpler for all those back
intercepts?
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
John Savard
in part:
>On Tue, 19 Jun 2001 10:46:22 -0600, in <3B2F81DE...@sandia.gov>,
>in sci.crypt John Myre <jm...@sandia.gov> wrote:
>>I think he's wrong, but of course I can't prove it.
>Wrong? How can it be *wrong* to have a suspicion of weakness, when
>the assertion of strength is not based on proven fact?
>Absent proof of strength in practice, suspicion of weakness is
>entirely appropriate. We need to consider the consequences of our
>hopes being wrong.
Of course, he meant you would be "wrong" if the weakness did not in
fact exist, regardless of the fact that you are right that there is no
proof it does not.
In a way, that isn't fair, since in effect it does make it appear as
though you had done what David A. Scott did when he made his first
appearance on this newsgroup - assert for a fact that one or more
popular block ciphers (in his case, IDEA) is not secure.
It is possible to have reasons for confidence in something that fall
short of proof, and it is even possible for such reasons to be
sufficient to make some forms of precaution unwarranted.
On the one hand, I certainly could imagine cases where designing a
file format around eventual encryption of the files in question could
create serious problems in developing and debugging an application. On
the other, under most circumstances, the computational cost of
encryption is trivial these days, and making extra effort over and
above what is considered the "standard" seems difficult to argue
against.
As for the specific issue: known plaintext + small key = brute-force
search possible. Hence, any flaw in our ciphers that makes their
effective keys smaller, or any advance in computation, is more
threatening when the plaintext is known. But an answer is available
that doesn't involve the equivalent of redesigning the English
language to make it less redundant. Use larger keys, if your response
to known plaintext must be confined to the cipher stage.
John Savard
http://home.ecn.ab.ca/~jsavard/frhome.htm
Tom St Denis
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:90C5AFD90H110W...@207.36.190.226...
> m...@anon.lcs.mit.edu (lcs Mixmaster Remailer) wrote in
> <2001061922403...@nym.alias.net>:
>
>
> >
> >It is time to put this sad error to an end. Known plaintext is not
> >harmful, and will not weaken a properly-applied encryption transform.
> >
>
> Actually any known plaintext is harmful and will weaken an ecryption
> system. But if you properly compress to remove the common known parts
> then you apply the encryption. Since if they are known they can be
> added in during the decryption decompression process.
Hmm no.
Known text is not desirable, but not always a problem. For instance, look
at CTR modes of operations.
Tom
Tim Tyler
: Tim Tyler wrote:
: <snip>
:> You go far too far. While tying yourself in knots to avoid known
:> plaintext may be over the top, avoiding it *is* desirable.
: But the question is: *how* desirable? Exactly how much effort
: is it worth? I'd agree with (anonymous) that the proper solution
: is to reinforce the cipher. [...]
Reinforcing the cypher is not a solution. Consider, for example,
the case where there is no known attack on the cypher, but the key
generator is broken.
:> You presume that cryptanalytic attack is the only possible method of
:> getting information relating to the key of a cypher.
: ?
Attackers can get hold of information about keys by other means besides
cryptanalysis.
:> This is not the case. If the number of possible keys can be reduced -
:> by any means - known-plaintext attacks can become a practical issue.
: That is at best an exaggeration. You can reduce the number of
: possible keys quite easily by brute force: guess a few keys,
: decrypt the entire message for each guess, and discard the ones
: that are clearly nonsense. [...]
Known-plaintext attacks can *sometimes* become a practical issue, then.
: In practice - this is simply not an issue.
So cryptosystems are never compromised by regularities and lack of
entropy in key generaors?
: The point is that if a simple keysearch can be made practical,
: because the entropy (unknown bits in the key) is small enough,
: then using obfuscation on the source text as a way to prevent
: that attack is almost certainly pointless.
I believe I can see the point - but where is the argument supporting it?
: Terry's response is more reasoned. The suspicion that maybe we
: are all fooling ourselves, that there *aren't* any ciphers that
: we can trust are as strong as we think, is at least defensible.
: I think he's wrong, but of course I can't prove it.
Even in fantasy-land - where the cyphers are known to be theoretically
invulnerable - there are still other ways things can go wrong.
Known plaintext will never be irrelevant.
David Hopwood
lbudney...@nb.net wrote:
> John Myre <jm...@sandia.gov> writes:
> >
> > The lack of a proof for such strength is, in my view, insufficient
> > evidence for weakness such that plaintext manipulations specifically
> > to help the cipher are warranted.
>
> Note, however, that reducing known plaintext is trivial; compression
> helps quite a lot. The cipher should be strong enough not to depend on
> compression (or anything else), but not doing compression is just silly!
Not doing compression is not "just silly". Compression has a performance
cost (which typically isn't outweighed by encrypting less data [*]), and
requires fairly large buffers. Whether compression is of benefit to a
protocol depends on the relative costs of bandwidth and storage vs the
processing needed for compression. If an evaluation of those costs suggests
that it would not be worthwhile for cleartext, then it probably won't be
worthwhile when encryption is used either.
OTOH, since just before encryption is the "last chance" to compress,
there is a good case for supporting compression in cryptography standards.
It shouldn't be expected to improve security, though; if anything, it
complicates the security analysis. (For instance, do you authenticate
the compressed data or the uncompressed data? There is a case for doing
either.)
[*] I'm assuming relatively fast ciphers like Rijndael or RC4, with a
fast MAC if applicable.
> (1) It makes encryption easier by shrinking the file.
> (2) It saves bandwidth by shrinking the ciphertext.
> (3) Reducing known plaintext certainly can't hurt.
It can't hurt security (assuming it's integrated correctly with the
security protocol), but you might not want to use it for other reasons.
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBOy/gtDkCAxeYt5gVAQFYzwf8DvawcqlWfwegXxJekpJx+VtPlaZt+mNv
yq3aPUScglGRcjykl4H4j3DFBxJuZDpa0BAcAJ/k04z/J9YuUeCJCqRWtKdPQXQ0
g8rKn+Ism6tdDHj058I+UPj8ZYUEmqVyLbg0PxDQ2L9YPyaHKkXaPVeRsJ2a28eR
vfzjyrK+e4uo6AqqRoglYyZN5uQmlHg0JbnGydbcd0ZYV2NWiSddchVhxRlWisAz
VqPuZYRFDyx75jK7XYEGzkQdpJmif8aYjNUWGUvF1hjNFEe0nq4IJi0nBwaxPj4h
FiWloRPGCKfa9IX5qengSWlkPchvYRezqoyQh4x5t5XqU64xQ/C21w==
=bXdd
-----END PGP SIGNATURE-----
Douglas A. Gwyn
> Inexperienced users of crypto systems are often concerned about
> known plaintext. They have heard that known plaintext can give
> a cryptanalyst an entry point into breaking ciphers.
> Accordingly they fear known plaintext and try to avoid it.
(1) What evidence is there for any of the above claims?
(2) Resistance to a "known plaintext" attack is an essential
requirement for a general-purpose encryption system, because
in fact quite often the enemy *will* know or guess plaintext.
(3) Stereotypes do provide an opening wedge in cracking many
systems. If a collection of messages are stacked "in depth"
where the stereotype recurs, it can facilitate cryptanalysis.
Terry Ritter
On Tue, 19 Jun 2001 23:33:37 GMT, in
<3b2fde73...@news.powersurfr.com>, in sci.crypt
jsa...@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote:
>[...]
>It is possible to have reasons for confidence in something that fall
>short of proof, and it is even possible for such reasons to be
>sufficient to make some forms of precaution unwarranted.
Not in cryptography.
In the normal world where we build our intuition, we can see the
consequences of design error: If some make of car has problems, we
know (a human gets out and reports, or gets squished). If a computer
program has problems doing what we want, we know, because it is not
doing what we want (it may of course be doing *more* than we want, but
that is a different issue). If a medicine does not do what we want,
we know that too. In the normal world we know when things don't work.
Cryptography is fundamentally different: In cryptography, we want to
protect our information from opponents, but we have no way of knowing
whether any particular cipher is successful. We don't know who our
opponents are, and they don't tell us of their successes. There is
thus no feedback to the design and development process from the real
mission.
The feedback we have is from practice missions. And that's fine, as
far as it goes. But that has little to do with the real mission, and
so should not build confidence.
While we cannot affect that per se, we *can* develop systems which
reduce the consequences of weakness, and also expose as little
information as possible.
>[...]
>As for the specific issue: known plaintext + small key = brute-force
>search possible. Hence, any flaw in our ciphers that makes their
>effective keys smaller, or any advance in computation, is more
>threatening when the plaintext is known. But an answer is available
>that doesn't involve the equivalent of redesigning the English
>language to make it less redundant. Use larger keys, if your response
>to known plaintext must be confined to the cipher stage.
I disagree. The problem is not keyspace. We already have keyspace.
Adding more keyspace is no advantage here.
The problem is the improved ability to analyze a ciphering function
when one has both the input to -- and output from -- that function
(this is known-plaintext, as opposed to having ciphertext-only).
Some ciphers can be broken with ciphertext only. But the *reason* for
this is that their plaintext is structured, or correlated. Knowing
the plaintext, or something about it, is how we solve ciphers. When
that knowledge is not available, even simple, supposedly-"weak"
ciphers can be strong in practice.
The obvious approach to minimizing the risk of known-plaintext is to
encipher at least twice with different ciphers and keys, so that the
plaintext to the last cipher is both randomized and hidden even from
the authorized user. I always recommend using three ciphers, which
allows one to be completely broken without exposing the others.
lcs Mixmaster Remailer
> lcs Mixmaster Remailer wrote:
> > Inexperienced users of crypto systems are often concerned about
> > known plaintext. They have heard that known plaintext can give
> > a cryptanalyst an entry point into breaking ciphers.
> > Accordingly they fear known plaintext and try to avoid it.
>
> (1) What evidence is there for any of the above claims?
Already an example appeared on sci.crypt the day after the original
posting, which has been quoted elsewhere. Someone thought that XML
encryption was unsafe because every message began with the same string
"<xml".
Here is an example from RFC1889, a protocol for audio-video transport:
sequence number: 16 bits
The sequence number increments by one for each RTP data packet
sent, and may be used by the receiver to detect packet loss and
to restore packet sequence. The initial value of the sequence
number is random (unpredictable) to make known-plaintext attacks
on encryption more difficult, even if the source itself does not
encrypt, because the packets may flow through a translator that
does. Techniques for choosing unpredictable numbers are
discussed in [7].
Here is a perfect example from the W3C workgroup on forms,
http://lists.w3.org/Archives/Public/www-forms/2001Mar/0052.html:
This approach, however appealing it may be, lacks in two key areas.
The first is plain security. If you encrypt the whole form, then you
make yourself vulnerable to known- plaintext attacks. Since parts
of the form are known (e.g. tag names), they can be used to break the
encryption if it's vulnerable to known-plaintext attacks. Encrypting
just the sensitive information gives an attacker less to play with.
Here is an example from the IETF TLS (aka SSL) design group from 1996.
They flirt with the error but in the end they make the right decision.
http://lists.w3.org/Archives/Public/ietf-tls/1996OctDec/0170.html:
I think this is a good suggestion, except that I would specify the
contents of the block data rather than using random data. I don't
believe that random data adds significantly to the security of the
protocol, as any significant communication will be well beyond the
unicity distance; thus, the verifiable plaintext of the padding
won't aid attackers. The benefit of using predictable data is that
the peer can verify that padding is being done as expected, which
allows a greater rigidity around implementations, which I believe
aids security analysis.
If you'd like to avoid the padding data being known plaintext,
you could specify it in some what that it is unknown, yet
verifiable. However, the protocol should be strong against
known-plaintext attacks anyway, as such attacks are commonly available
to attackers.
An example from the XML encryption draft,
http://lists.w3.org/Archives/Public/xml-encryption/2000Dec/att-0024/01-XMLEncryption_v01.html:
5. It has been noted by Hal Finney, Steve Wiley, et al that encrypting
XML raises concerns over attacks based on known plaintext as well
as known length of the encrypted plaintext. This issue, in regards
to encrypting enumerated attributes values, is one reason for not
supporting attribute-value encryption.
A message from the XML encryption archives recommending compression
(aka "redundancy removal") to thwart known plaintext attacks,
http://lists.w3.org/Archives/Public/xml-encryption/2000Nov/0059.html:
>People didn't seem keen on compression.
Maybe we should use the term "redundancy removal" instead of
compression. This should be possible to harden encrypted docs against
known-plaintext attacks. How this is technically achieved should be
considered later. But it may be achieved via compression.
The original XML encryption organizational ("BoF") meeting notes
raise a point similar to the one which came up earlier today, concerns
about known plaintext due to the stereotypical nature of XML documents,
http://lists.w3.org/Archives/Public/xml-encryption/2000Sep/att-0014/01-XML_Encryption_BoF.htm:
Known plaintext attacks
E.g. if DTD is given, attackers can know an element to be encrypted
starts with a particular tag name. Good reason to not use stream
ciphers.
I can find more examples if you like. Or are you convinced now that
this is a widespread phenomenon?
> (2) Resistance to a "known plaintext" attack is an essential
> requirement for a general-purpose encryption system, because
> in fact quite often the enemy *will* know or guess plaintext.
Absolutely.
> (3) Stereotypes do provide an opening wedge in cracking many
> systems. If a collection of messages are stacked "in depth"
> where the stereotype recurs, it can facilitate cryptanalysis.
True in principle, but this is not something that a user should be
concerned about. Hundreds of man years have been spent analyzing
3DES and probably close to that for AES. Users don't have to worry
about avoiding known plaintext when using a strong algorithm like this.
The most brilliant cryptographers in the world have failed to find the
smallest weakness in these ciphers.
The danger from known plaintext when using a modern cipher like these
is so small, so hypothetical, so unrealistic, that it is unprofessional
for a cryptographer to allow the contrary belief to stand. The examples
above prove that it is a widespread mistake, quoted frequently by people
who think they know something about cryptography. The community has to
take on the responsibility of setting the record straight.
Tim Tyler
: lbudney...@nb.net wrote:
:> Note, however, that reducing known plaintext is trivial; compression
:> helps quite a lot. The cipher should be strong enough not to depend on
:> compression (or anything else), but not doing compression is just silly!
: Not doing compression is not "just silly". Compression has a performance
: cost (which typically isn't outweighed by encrypting less data [*])
Compression and encryption can sometimes be done in parallel. *Then* it's
almost always faster due to the fact that less data is encrypted - unless
your compressor is slower than your encryption.
Only on a serial machine is performance much of a concern.
: OTOH, since just before encryption is the "last chance" to compress,
: there is a good case for supporting compression in cryptography standards.
: It shouldn't be expected to improve security, though; if anything, it
: complicates the security analysis. (For instance, do you authenticate
: the compressed data or the uncompressed data? There is a case for doing
: either.)
I'm not sure I can see much case for authenticating the data after
compression. I suppose signatures won't compress well - but apart
from that...
: [*] I'm assuming relatively fast ciphers like Rijndael or RC4, with a
: fast MAC if applicable.
:> (1) It makes encryption easier by shrinking the file.
:> (2) It saves bandwidth by shrinking the ciphertext.
:> (3) Reducing known plaintext certainly can't hurt.
: It can't hurt security (assuming it's integrated correctly with the
: security protocol), but you might not want to use it for other reasons.
I think there are /some/ cases where it can damage security.
For example, if the plaintexts are all fixed size forms, then compressing
them may result in the attacker getting more information that not doing
so.
Forms with lots of additional data in them will not compress so well -
so you can see how much data there is in the form by the length of the
compressed file - while before they were all indistinguishable.
Tim Tyler
: Hundreds of man years have been spent analyzing
: 3DES and probably close to that for AES. Users don't have to worry
: about avoiding known plaintext when using a strong algorithm like this.
: The most brilliant cryptographers in the world have failed to find the
: smallest weakness in these ciphers.
Really? How do you know that? You don't know that. Indeed, it's quite
likely that you have never read anything by the world's best living
cryptanalysts.
: The danger from known plaintext when using a modern cipher like these
: is so small, so hypothetical, so unrealistic, that it is unprofessional
: for a cryptographer to allow the contrary belief to stand. [...]
Again, you assume that cryptanalytic attack is the only possible means of
key recovery. This is false. Even *if* the cypher were known to
be unbroken, there would still be a good case for reducing known-plaintext,
as a precaution to help in dealing with other possible problems.
XML's high redundancy decreases the unicity distance for it - making
measures that increase it again more desirable than usual.
lbudney...@nb.net
> lbudney...@nb.net wrote:
>> ...not doing compression is just silly!
>
> Not doing compression is not "just silly". Compression has a performance
1,000 pardons. I never intended the statement to be sweepingly true of
every context in the universe where encryption is used. There may indeed
be circumstances in which compression is clearly not the best idea. Are
you happy now?
Fact remains, that somehow deprecating compression is just silly. It has
its place.
Len.
--
Frugal Tip #55:
Get yourself a realistic-looking mongoose costume. Then, rent yourself
out to somebody who wants a rented mongoose.
Tim Tyler
: It is time to put this sad error to an end. Known plaintext is not
: harmful, and will not weaken a properly-applied encryption transform.
How do you know whan you have one of them?
How do you know how much entropy there is in your key generator?
How do you know whether your keybook has been quietly copied?
You don't know any of these things. Known plaintext is rightly considered
harmful. It is the assertion that is is harmless that is the "sad error".
John Savard
part:
>lcs Mixmaster Remailer <m...@anon.lcs.mit.edu> wrote:
>: Hundreds of man years have been spent analyzing
>: 3DES and probably close to that for AES. Users don't have to worry
>: about avoiding known plaintext when using a strong algorithm like this.
>: The most brilliant cryptographers in the world have failed to find the
>: smallest weakness in these ciphers.
>Really? How do you know that? You don't know that. Indeed, it's quite
>likely that you have never read anything by the world's best living
>cryptanalysts.
Well, he *is* using an anonymous remailer. So we don't _know_ that he
doesn't work for the NSA - or that his motive in writing this post is
not to get us to leave the known plaintext in to make his job easier.
I think we can leave that out of our thinking, though. The problem
isn't that Rijndael and Triple-DES are particularly likely to be less
strong than "advertised". As far as that is concerned, I have to admit
the 'conventional wisdom' is likely quite right. The problem is,
though, that if keeping one's secrets is felt to be important,
phrasing even good advice in terms of deliberately neglecting a
precaution, instead of spending one's time on more important things
(like possible side channels, exposure of one's plaintext data to
computer viruses) is like waving a red flag at a bull.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Savard
<m...@anon.lcs.mit.edu> wrote, in part:
>Inexperienced users of crypto systems are often concerned about known
>plaintext. They have heard that known plaintext can give a cryptanalyst
>an entry point into breaking ciphers. Accordingly they fear known
>plaintext and try to avoid it.
True.
>Sometimes they will even complicate their data structures or protocols
>in order to avoid known plaintext. They will incorporate compression
>for no good reason, or restructure headers, or make sure that fields
>set aside for future expansion hold random values rather than zeros.
>All this complicates their overall system design and introduces new
>possibilities for errors.
It certainly is important to remember that program bugs can result in
exposing plaintext.
>We need to communicate clearly that known plaintext is no longer an issue.
>With modern ciphers and a reasonable chaining mode, you don't have
>to worry about known plaintext. If your cipher is weak against known
>plaintext, you should be using a different cipher.
If you communicate _too_ clearly that "known plaintext is no longer an
issue", though, people might forget the need for a "reasonable
chaining mode". By noting that such a mode is still needed to
accompany a "modern cipher", you are admitting that known plaintext
_remains_ a consideration.
Incidentally, these "reasonable chaining modes" include random
initialization vectors.
>When designing data which will be protected by a cipher, the only
>consideration should be the needs to which the data will be put.
>Design for clarity and convenience.
>NO CONSIDERATION WHATSOEVER should be given to manipulating or
>constraining the data structures in the hopes of making the encryption
>stronger!
>In your overall system, the cipher is there to do the job of protecting
>the plaintext. The job of the plaintext is to represent whatever data
>is being communicated. Don't be misled into blurring these boundaries.
>Modern ciphers are fully capable of providing confidentiality with any
>and every plaintext. Let the cipher do its job, don't try to "help"
>it in the other parts of your design.
Now, this may well be sound advice if one is designing a word
processor or a paint program that happens to have an optional password
protection mode.
However, it is an unjustified assumption that every system which uses
encryption falls into that paradigm. Sometimes the encryption _is_ the
application.
>Let us all agree that it is time to put concerns about known plaintext
>behind us. Recommendations to avoid it are obsolete.
People who are interacting with cryptography at a user level, and are
using, as you point out, "modern ciphers and a reasonable chaining
mode", can indeed follow that advice. People trying to determine just
what constitutes a "reasonable chaining mode", or who are attempting
to design a "modern cipher", however, can't afford to forget its
dangers.
In addition, it is simply easier to compress plaintext effectively if
one has additional information about its expected structure.
Also, if one is just using Rijndael or 3DES, one has a well-defined
key size of 128 or 112 bits. Should we consider ourselves justified in
feeling complete confidence in the security of our encryption, once
we've settled on the "industry standard"? What about quantum
computers, for example? Not all data merely needs to remain
confidential for the next week, or the next month. Are you prepared to
tell me how powerful, and how cheap, computers will be 100 years from
now?
Making conventional encryption absurdly strong, though, instead of
merely as impressively strong as Rijndael and 3DES, is trivially easy.
Thus, another way of putting this argument behind us is simply to do
so, whether it is necessary or not. Because it is true that preventing
plaintext from leaking, and performing key management properly, are
the real problems that deserve time and attention.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Savard
<m...@anon.lcs.mit.edu> wrote, in part:
>Hundreds of man years have been spent analyzing
>3DES and probably close to that for AES. Users don't have to worry
>about avoiding known plaintext when using a strong algorithm like this.
>The most brilliant cryptographers in the world have failed to find the
>smallest weakness in these ciphers.
As has been noted, you are laying it on just a little bit thick here.
Yes, Rijndael has enough rounds that the Square attack seems to be
useless. But even a mere dabbler such as myself was able to note that
the number of rounds with the most common key sizes gave it disturbing
structural similarities to DES with an odd number of rounds, which is
known to be weak.
3DES is DES repeated three times, and while DES is nearly as strong as
its key size, small weaknesses have been found in it, most
specifically against linear cryptanalysis.
And, in any case, someone taking your statements above too closely to
heart might commit the error of forgetting to use a "reasonable
chaining mode" with one of these wonderful block ciphers.
The problem, though, isn't so much that the message you want the
cryptological community to convey is not true. In general, it is
indeed valid. It's just that an appearance of dogmatism is the last
thing one needs to get the message across effectively.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
SCOTT19U.ZIP_GUY
>
>True in principle, but this is not something that a user should be
>concerned about. Hundreds of man years have been spent analyzing
>3DES and probably close to that for AES. Users don't have to worry
>about avoiding known plaintext when using a strong algorithm like this.
>The most brilliant cryptographers in the world have failed to find the
>smallest weakness in these ciphers.
>
This is where your full of shit. No one in the open community
has any idea of the work of the most brillian cryptographers. Your
making the same mistake the germans and Japanese made by flasely
assuming strength. That is precisely what one should not do.
For XML they should use a bijective compressor tuned to XML
and then encrypt with a properly mated RIJNDAEL. Since that
is going to be the AES standard. If RIJNDAEL is weak the compression
still may save them till a new standard is adapted. For my own
use I would not use AES but for a standard of this type I am not
sure you really will have much choice.
>The danger from known plaintext when using a modern cipher like these
>is so small, so hypothetical, so unrealistic, that it is unprofessional
>for a cryptographer to allow the contrary belief to stand. The examples
>above prove that it is a widespread mistake, quoted frequently by people
>who think they know something about cryptography. The community has to
>take on the responsibility of setting the record straight.
Bullshit the dangers of known plaintext are always present and to
forget that is to make a serious mistake.
SCOTT19U.ZIP_GUY
I agree basically with what your said. But I don't think
you have ever completely described the nature of the three ciphers
that would be used in series. Do you argee they should be fully
bijective. Meaning false keys would lead to something in the input
message space so no information is given to attacker to break the
system.
Douglas A. Gwyn
> The danger from known plaintext when using a modern cipher like these
> is so small, so hypothetical, so unrealistic, that it is unprofessional
> for a cryptographer to allow the contrary belief to stand. The examples
> above prove that it is a widespread mistake, quoted frequently by people
> who think they know something about cryptography. The community has to
> take on the responsibility of setting the record straight.
I think the right way to present it is "Modern cryptosystems are
specifically designed for resistance to known-plaintext attacks,
among other things. Therefore, if you know that a modern
cryptosystem will be used, you needn't be concerned about the
possibility of a known-plaintext attack. However, if you can't
be sure what kind of encryption will be applied, then all bets
are off, and it *might* be useful to vary the plaintext somewhat;
however, there are many other protective measures that would be
more useful (like wrapping the plaintext in a modern encryption
that you have control over, before submitting it to be encrypted
with the unknown system)."
John Myre
<snip>
> If
> there is nothing wrong about a compressor receiving side information
> about its input, so as to be able to compress it more efficiently,
> then can't we make similar allowances for an encryption stage? (Thus,
> part of the decryption will be to restore the blank fields and so on,
> with some short indicator handling the possibility that they will stop
> being blank in future expansion.)
The only thing wrong with approaches like this is the practical
side effects of such design decisions on the implementation effort.
It's *easy* to f*** up your security by making mistakes in the
implementation. It's *hard* to be "sure" you haven't done so.
Complexity is the enemy of correctness. Therefore, it will most
often be best to KISS your encryption modules. If you want to do
compression, that's fine, but beware of compromising security by
implementation (or design!) problems.
JM
David Wagner
>lcs Mixmaster Remailer <m...@anon.lcs.mit.edu> wrote:
>: It is time to put this sad error to an end. Known plaintext is not
>: harmful, and will not weaken a properly-applied encryption transform.
>
>How do you know whan you have one of them?
>
>How do you know how much entropy there is in your key generator?
>
>How do you know whether your keybook has been quietly copied?
>
>You don't know any of these things.
If you any of these failures occur, all bets are off. Whether or not
you've tried to minimize known plaintext, getting those wrong puts your
system in great danger.
Therefore, I would argue that it is a better use of your energies to
spend time making sure you defend against those failure modes than to
worry about known plaintext.
David Wagner
>XML's high redundancy decreases the unicity distance for it
Even if you use compression, you'll still be using the key
far past the unicity distance. It seems hard to precisely
justify why the unicity distance should be relevant to systems
based on computational security.
David Wagner
complexity than have failed because there was a practical
cryptanalytic known-plaintext attack on a well-chosen cipher.
I'd gladly trade known plaintext for simplicity, any day.
Terry Ritter
On 20 Jun 2001 12:10:59 GMT, in
<90C6325BDH110W...@207.36.190.226>, in sci.crypt
david_...@emailv.com (SCOTT19U.ZIP_GUY) wrote:
>rit...@io.com (Terry Ritter) wrote in <3b30322a...@news.io.com>:
>[...]
>>Some ciphers can be broken with ciphertext only. But the *reason* for
>>this is that their plaintext is structured, or correlated. Knowing
>>the plaintext, or something about it, is how we solve ciphers. When
>>that knowledge is not available, even simple, supposedly-"weak"
>>ciphers can be strong in practice.
>>
>>The obvious approach to minimizing the risk of known-plaintext is to
>>encipher at least twice with different ciphers and keys, so that the
>>plaintext to the last cipher is both randomized and hidden even from
>>the authorized user. I always recommend using three ciphers, which
>>allows one to be completely broken without exposing the others.
>>
>
> I agree basically with what your said. But I don't think
>you have ever completely described the nature of the three ciphers
>that would be used in series. Do you argee they should be fully
>bijective. Meaning false keys would lead to something in the input
>message space so no information is given to attacker to break the
>system.
I don't like using the term "bijective" for this. Maybe "plaintext
complete" comes closer, as in every possible plaintext should be at
least technically valid. But whatever we call it, it certainly is a
desirable and possibly important property that the ideal system would
assure before invoking a cipher. Language does not have this
property, which is exactly why we can solve some simple ciphers.
Without some knowledge of the plaintext itself, or of structure in the
plaintext, breaking a cipher becomes very difficult. If we
communicate in distinct messages, and if the "plaintext" includes a
length field, that "length" had better be modulo or block size, or we
will be describing in plaintext a size the opponents can see as
ciphertext. This is a form of known plaintext. But known plaintext
is also common in salutations, signatures, HTML codes and so on.
On the other hand, even if a length is added to the input of the first
cipher, the input to the second and third ciphers should be well
distributed -- such that every possible plaintext seems possible --
and so not a problem. That sounds to me like a reason for using a
sequence or "cascade" of multiple ciphers, and is related to hiding
known plaintext.
As I see it, the problem is not so much the "bijective" nature of the
last cipher, but instead the known structure in the original
plaintext. This is a known-plaintext issue.
Mark Wooding
> If you communicate _too_ clearly that "known plaintext is no longer an
> issue", though, people might forget the need for a "reasonable
> chaining mode". By noting that such a mode is still needed to
> accompany a "modern cipher", you are admitting that known plaintext
> _remains_ a consideration.
I think that a block cipher alone doesn't actually constitute a `modern
cipher'. I think that name should only be applied to some
transformation which can be claimed (under stated assumptions) to be
IND-CPA. Hence, a construction based on a block cipher can only be
considerde a `modern cipher' if used in an appropriate mode (e.g., CBC,
CTR, OCB, whatever).
> Incidentally, these "reasonable chaining modes" include random
> initialization vectors.
Or, in the case of CTR, a counter. This actually makes CTR mode more
secure. (You use the current value of the counter as the IV for an
encryption, and then increment it by the number of blocks you
encrypted. Using a random IV adds an extra \mu^2 / 2^L term to the
advantage of the adversary.)
> However, it is an unjustified assumption that every system which uses
> encryption falls into that paradigm. Sometimes the encryption _is_ the
> application.
Even so. I don't think that (say) a VPN program should try to hide the
stereotyping of IP packets it's encrypting. It should strive to be
NM-CCA rather than IND-CPA, though -- chosen ciphertext is very easy in
such an application. (I changed my VPN program yesterday so that it had
a chance of being NM-CCA.)
-- [mdw]
lcs Mixmaster Remailer
> I think the right way to present it is "Modern cryptosystems are
> specifically designed for resistance to known-plaintext attacks,
> among other things. Therefore, if you know that a modern
> cryptosystem will be used, you needn't be concerned about the
> possibility of a known-plaintext attack.
An excellent summary.
> However, if you can't
> be sure what kind of encryption will be applied, then all bets
> are off, and it *might* be useful to vary the plaintext somewhat;
Here though you start to get ambiguous. How is an crypto-ignorant
protocol or data structure designer to know what to do with advice like
this? It "might" be useful to vary the plaintext "somewhat"? He has
to make concrete decisions. Should he specify that unused fields are
zeros, which makes the protocol cleaner and can detect errors and version
mismatch, or should he specify that they are filled with random values,
to prevent known plaintext? Which is it? He's got to make the decision.
Tell us, right now.
And if he does make changes like this, how much has he helped himself?
Should he go over his design to look for other places where there might
be known plaintext? Supose he notices that he has a bunch of data that
is easily guessed. Should he rearrange his data to intersperse this
relatively fixed data with more variable data, in the hopes that any
single encryption block will have a mix of the two types? Yes or no?
This is the kind of ad hoc, seat of the pants, ignorance-driven
manipulation which results from ambiguous advice like you have above.
It doesn't buy true security.
> however, there are many other protective measures that would be
> more useful (like wrapping the plaintext in a modern encryption
> that you have control over, before submitting it to be encrypted
> with the unknown system)."
Yes, this is much better advice. The point is to use good crypto.
That should be the beginning and the end of the advice from the crypto
community. It is our take-home message.
We don't say, use good crypto, but if you can't, maybe you ought to
eliminate obvious cases of known plaintext, but well, don't knock yourself
out doing it. That's not professional. Our advice as professional
cryptographers MUST BE to use professional-quality crypto. If someone
says they can't, we say, then you don't have security. We don't sell
them false hopes and weak obfuscation. That is unprofessional. In fact
it borders on fraud.
As crypto experts, we need to give expert advice. Use good crypto.
That's it.
Tim Tyler
:>: It is time to put this sad error to an end. Known plaintext is not
:>: harmful, and will not weaken a properly-applied encryption transform.
:>
:>How do you know whan you have one of them?
:>
:>How do you know how much entropy there is in your key generator?
:>
:>How do you know whether your keybook has been quietly copied?
:>
:>You don't know any of these things.
: If you any of these failures occur, all bets are off. Whether or not
: you've tried to minimize known plaintext, getting those wrong puts your
: system in great danger.
Indeed.
: Therefore, I would argue that it is a better use of your energies to
: spend time making sure you defend against those failure modes than to
: worry about known plaintext.
It depends on who you are, and what the relative expenditure is. As a
designer of an encryption device, you may have no control over the way
others feed keys to you. It may not be up to you to control how codebooks
are destroyed upon enemy capture. However, you /may/ be in a position to
eliminate some classes of known plaintexts.
Eliminating known plaintext may not help very much - or may only help
sometimes, but it can and does help. Whether you consider it worth
doing should be a function of the percieved costs and benefits.
Known plaintext *can* be harmful, and *can* weaken the security of
messages transmitted under encryption applied with great care.
Tim Tyler
: Tim Tyler wrote:
:>XML's high redundancy decreases the unicity distance for it
: Even if you use compression, you'll still be using the key
: far past the unicity distance. [...]
That depends on exactly what you are doing.
XML is not known for its conciceness - but then again it /is/ pretty
redundant, and a dedicated compressor could no-doubt perform wonders.
However, I expect those wonders would only rarely get you anywhere
near the unicity distance. Rarely is better than never, though.
: It seems hard to precisely justify why the unicity distance should be
: relevant to systems based on computational security.
Block cyphers are based mainly on computational security - but partly
on information-theoretic security. The former provides no guarantee of
secrecy, while the latter does. If you can get a guarantee that
even with a powerful cryptanalytic attack - or some super-duper quantum
computer - knowledge of the cyphertext cannot possibly reveal the key,
then that is something which might be considered desirable.
Even if you ignore the unicity distance there are still some
remaining security plus points for compressing. The attacker
gets less plaintext/cyphertext pairs, for example.
David Wagner
>David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>: Therefore, I would argue that it is a better use of your energies to
>: spend time making sure you defend against those failure modes than to
>: worry about known plaintext.
>
>It depends on who you are, and what the relative expenditure is. As a
>designer of an encryption device, you may have no control over the way
>others feed keys to you.
If you're a designer of an encryption device, you have no control
over the plaintext being fed to you, so you can't plausibly do anything
about known plaintext anyway.
In any case, I thought we were talking about protocol and systems design.
>Eliminating known plaintext may not help very much - or may only help
>sometimes, but it can and does help. Whether you consider it worth
>doing should be a function of the percieved costs and benefits.
Sure. I contend, though, that the cost is very high and the benefit
is low. The cost is complexity, and complexity is the worst enemy of
security. The benefit is only applicable if the cipher is weak (but not
too weak---it has to be just weak enough that there are practical known
plaintext attacks, but no practical attacks with the reduced amount of
knowledge on the text), and given the state of modern cryptography, this
failure mode currently seems to have a relatively low probability when
compared to the other types of failures of security, empirically speaking.
Tim Tyler
: I think the right way to present it is "Modern cryptosystems are
: specifically designed for resistance to known-plaintext attacks,
: among other things. Therefore, if you know that a modern
: cryptosystem will be used, you needn't be concerned about the
: possibility of a known-plaintext attack. [...]
Compare with: "Modern windows are designed not to break. Therefore,
if you fit your shop with modern windows, you needn't be concerned
about the possibility of them breaking."
Alas, this leaves the shoplifters out of the picture.
Tim Tyler
: I agree. Far more systems have failed from too much
: complexity than have failed because there was a practical
: cryptanalytic known-plaintext attack on a well-chosen cipher.
Indeed. However cryptanalytic known-plaintext attacks are *not* the only
type of failure that eliminating known plaintext helps defend against.
Ben Cantrick
David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>Tim Tyler wrote:
>>David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>>: Therefore, I would argue that it is a better use of your energies to
>>: spend time making sure you defend against those failure modes than to
>>: worry about known plaintext.
>>
>>It depends on who you are, and what the relative expenditure is. As a
>>designer of an encryption device, you may have no control over the way
>>others feed keys to you.
>
>If you're a designer of an encryption device, you have no control
>over the plaintext being fed to you, so you can't plausibly do anything
>about known plaintext anyway.
I'm not sure I always agree. What's to stop you from, say, putting a
block of 16 or 32 random bytes at the beginning of any plaintext fed to
you? Or putting in a random byte every 3rd byte or something. Yes, you
pay in complexity of device design (good random number gens aren't cheap)
and bandwidth, but if you're realy worried about known plaintext attacks,
maybe it's worth it.
-Ben
--
Ben Cantrick (mac...@dim.com) | Yes, the AnimEigo BGC dubs still suck.
BGC Nukem: http://www.dim.com/~mackys/bgcnukem.html
The Spamdogs: http://www.dim.com/~mackys/spamdogs
http://www.wins.uva.nl/~mes/jargon/a/AppendixB.html
lcs Mixmaster Remailer
> I agree. Far more systems have failed from too much
> complexity than have failed because there was a practical
> cryptanalytic known-plaintext attack on a well-chosen cipher.
> I'd gladly trade known plaintext for simplicity, any day.
As usual, you are a voice of reason.
I hope the well-earned reputation of David Wagner in this forum will
carry weight even if the arguments of an anonymous voice do not.
Tim Tyler
:>: Therefore, I would argue that it is a better use of your energies to
:>: spend time making sure you defend against those failure modes than to
:>: worry about known plaintext.
:>
:>It depends on who you are, and what the relative expenditure is. As a
:>designer of an encryption device, you may have no control over the way
:>others feed keys to you.
: If you're a designer of an encryption device, you have no control
: over the plaintext being fed to you, so you can't plausibly do anything
: about known plaintext anyway.
: In any case, I thought we were talking about protocol and systems design.
This thread seems to have as a motif XML encryption.
In that domain, it seems to me that there /is/ something that can be done
about known plaintext.
:>Eliminating known plaintext may not help very much - or may only help
:>sometimes, but it can and does help. Whether you consider it worth
:>doing should be a function of the percieved costs and benefits.
: Sure. I contend, though, that the cost is very high and the benefit
: is low. The cost is complexity, and complexity is the worst enemy of
: security. [...]
The costs of /not /compressing can include having signals being sent
for longer than necessary (resulting in increased possibility of
interception and being traced), signals taking longer to arrive,
and other problems.
Complexity is a factor to be weighed - but I don't think it's
necessarily overwhelming. It's not as though compression is rocket
science.
: The benefit is only applicable if the cipher is weak (but not
: too weak---it has to be just weak enough that there are practical known
: plaintext attacks, but no practical attacks with the reduced amount of
: knowledge on the text) [...]
This is something I dispute. As an example, another failure mode in
which known-plaintext can help is a random number generator with
insuifficient entropy - or something like a hashed password as a key.
If cryptanalytic attack was the /only/ consideration, correspondingly less
effort should be put into eliminating known plaintext - but it is only one
of a number of possible ways that the attacker can reduce the work
required for a brute force search.
John Savard
<m...@anon.lcs.mit.edu> wrote, in part:
>As crypto experts, we need to give expert advice. Use good crypto.
>That's it.
This is all very sensible, but do we know that even the good crypto
really is good? And shouldn't we encourage our clients to develop
critical thinking skills of their own, instead of simply uncritically
accepting "expert" advice?
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Myre
<snip>
> Complexity is a factor to be weighed - but I don't think it's
> necessarily overwhelming.
Remind me not to buy any important software from you.
Ok, ok, that was harsh. Still, I contend that complexity
is the single greatest obstacle to secure systems.
JM
John Myre
> : The benefit is only applicable if the cipher is weak (but not
> : too weak---it has to be just weak enough that there are practical known
> : plaintext attacks, but no practical attacks with the reduced amount of
> : knowledge on the text) [...]
>
> This is something I dispute. As an example, another failure mode in
> which known-plaintext can help is a random number generator with
> insuifficient entropy - or something like a hashed password as a key.
But the "just weak enough" objection applies here, as well.
> If cryptanalytic attack was the /only/ consideration, correspondingly less
> effort should be put into eliminating known plaintext - but it is only one
> of a number of possible ways that the attacker can reduce the work
> required for a brute force search.
Same answer, again.
If there is *any* way to verify a key guess, then brute force
will always work, if we have enough time. Plaintext obfuscation
techniques (compression, large block encryption) can only multiply
the work factor by a relatively small amount. It is *possible*
that this amount is enough to make the difference between secure
and not secure. It seems extraordinarly *unlikely* in any real,
practical system. If nothing else, note that the adversary's
capabilities, a moving target at best, factor in to the equation.
JM
David Wagner
>Complexity is a factor to be weighed - but I don't think it's
>necessarily overwhelming. It's not as though compression is rocket
>science.
Compression isn't rocket science. Security in the presence of complex
systems, on the other hand, is rocket science.
Consider the following, intended only as a random illustratory example
(since you picked compression as your example of a technique that adds
to complexity but reduces known plaintext). If you add compression,
you have to start worrying about the following new attack.
Consider: After the receiver decrypts a packet and verifies its
authenticity, and then subsequently decompresses the result, how do we
know that the decompressed result is also authentic? Well, in some cases,
it need not be. For example, if the decompressor has any side inputs
(let's say, a compression window, or a 'compression factor' tuning knob)
that have not been authenticated, then an attacker might be able to
affect the results of the decompression, despite the presence of a MAC
on the encrypted ciphertext. This could, in some (hopefully uncommon)
situations, potentially lead to a failure of the message authentication
property.
I'm not saying that this attack will always apply whenever you use
compression. Rather, I'm saying that it is an example of a new failure
mode that you have to worry about if you introduce the extra complexity
associated with measures for reducing known plaintext. The question is,
is this extra complexity worth the cost? In the case of reducing known
plaintext, I assert that the answer is almost always an emphatic "No!".
For me, one of the fantastic advantages of modern ciphers, which
are designed to be secure against all of these far-fetched academic
attacks, is that they give you an entire set of failure modes that you
no longer have to worry about when designing a system. As a result,
you can better concentrate on avoiding the resulting failure modes,
and that is a big win.
David Wagner
>: The benefit is only applicable if the cipher is weak (but not
>: too weak---it has to be just weak enough that there are practical known
>: plaintext attacks, but no practical attacks with the reduced amount of
>: knowledge on the text) [...]
>
>This is something I dispute. As an example, another failure mode in
>which known-plaintext can help is a random number generator with
>insuifficient entropy - or something like a hashed password as a key.
How?
Maybe you're imagining that a failed random number generator can make it
easy for the attacker to narrow down the keyspace to, say, only 2^20
possibilities, and then exhaustive keysearch is a terrible threat.
I certainly agree that this is a possible failure mode.
But it would be a mistake to expect to defend against this failure mode
by, say, compressing. After all, exhaustive keysearch will be possible
whenever you can find a total of 20 bits of redundancy spread out in any
way whatsoever among the entire set of messages encrypted under that
key, and it seems extremely difficult in practice to reduce the level
of redundancy enough that exhaustive keysearch becomes impossible.
David Wagner
>This is all very sensible, but do we know that even the good crypto
>really is good?
We don't. But we look at the most likely failures.
Which of the following is more likely?
- There's some flaw, but the RFC is so durn complicated that
noone ever notices it in time to prevent deployment of a broken system.
- There is a *practical* known-plaintext attack on AES or 3DES that
causes your system to break if you encrypted uncompressed text
but that isn't enough to break the system when you use compression.
I know which I'm putting my money on! (and it's not the latter)
David Wagner
>And shouldn't we encourage our clients to develop
>critical thinking skills of their own, instead of simply uncritically
>accepting "expert" advice?
There are better ways to accomplish this than to suggest using ECB mode.
John Savard
(David Wagner) wrote, in part:
>John Savard wrote:
That's certainly a good point.
The 'conventional wisdom' is fundamentally sound; I'm not trying to
dispute that. The anonymous poster here, though, is advocating it in
such a broad, categorical fashion as to invite suspicions of trolling
- and apparently there is other reason to suspect some sort of
personal issue with Joseph Atwood.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
Tim Tyler
: Tim Tyler wrote:
:>: The benefit is only applicable if the cipher is weak (but not
:>: too weak---it has to be just weak enough that there are practical known
:>: plaintext attacks, but no practical attacks with the reduced amount of
:>: knowledge on the text) [...]
:>
:>This is something I dispute. As an example, another failure mode in
:>which known-plaintext can help is a random number generator with
:>insuifficient entropy - or something like a hashed password as a key.
: How?
: Maybe you're imagining that a failed random number generator can make it
: easy for the attacker to narrow down the keyspace to, say, only 2^20
: possibilities, and then exhaustive keysearch is a terrible threat.
Yes.
: But it would be a mistake to expect to defend against this failure mode
: by, say, compressing. After all, exhaustive keysearch will be possible
: whenever you can find a total of 20 bits of redundancy spread out in any
: way whatsoever among the entire set of messages encrypted under that
: key, and it seems extremely difficult in practice to reduce the level
: of redundancy enough that exhaustive keysearch becomes impossible.
Varying quantities of information may be transmitted under keys.
If you're /always/ transmitting lots of information the defense doesn't
help.
If you /ever/ transmit small quantities of information under a key, it
can help.
This is essentially the same situation as cryptanalytic attack. I think
if you are regarding compression as an attempt to defend against broken
cyphers, you should equally consider it as a defense against low entropy
key generators.
David Wagner
>If you /ever/ transmit small quantities of information under a key, it
>can help.
Right. And my claim is that this case almost never happens (it is so
rare that it should have minimal weight in any decision). But I'll
certainly concede that my claim is purely empirical in nature, and can
only be settled by looking at real systems and doing some measurements.
I haven't done the measurements; I'm just going on my experience with
how crypto tends to be used, in the systems I've looked at. I freely
admit that I don't have any evidence for my claim that I could show you.
Tim Tyler
: Tim Tyler wrote:
:>Complexity is a factor to be weighed - but I don't think it's
:>necessarily overwhelming. It's not as though compression is rocket
:>science.
: Compression isn't rocket science. Security in the presence of complex
: systems, on the other hand, is rocket science.
: Consider the following, intended only as a random illustratory example
: (since you picked compression as your example of a technique that adds
: to complexity but reduces known plaintext). If you add compression,
: you have to start worrying about the following new attack.
: Consider: After the receiver decrypts a packet and verifies its
: authenticity, and then subsequently decompresses the result, how do we
: know that the decompressed result is also authentic? [...]
Signatures should normally be attacked to the document being signed.
Usually this occurs prior to compression.
: I'm not saying that this attack will always apply whenever you use
: compression. Rather, I'm saying that it is an example of a new failure
: mode that you have to worry about if you introduce the extra complexity
: associated with measures for reducing known plaintext. The question is,
: is this extra complexity worth the cost? In the case of reducing known
: plaintext, I assert that the answer is almost always an emphatic "No!".
There are always ways to do things wrong. Avoiding complexity at all
costs leads towards CTR mode, and ultimately ROT-N - surely not where
we should be going.
To some extent the remedy for doing things wrong is to learn how to do
them right. In many cases, this only needs to be done once. Today
combined compress-encrypt systems exist, and they can be used much like
any cypher. There are a *few* security differences because of the
compression, but I would not say they were much to write home about.
Tim Tyler
:> : The benefit is only applicable if the cipher is weak (but not
:> : too weak---it has to be just weak enough that there are practical known
:> : plaintext attacks, but no practical attacks with the reduced amount of
:> : knowledge on the text) [...]
:>
:> This is something I dispute. As an example, another failure mode in
:> which known-plaintext can help is a random number generator with
:> insuifficient entropy - or something like a hashed password as a key.
: But the "just weak enough" objection applies here, as well.
"the cipher is weak (but not too weak---it has to be just weak enough [])"
The "just weak enough" objection referred explicitly to the cypher.
If you wanted to apply the original statement to RNG failure, it would
need rephrasing.
: If there is *any* way to verify a key guess, then brute force
: will always work, if we have enough time. Plaintext obfuscation
: techniques (compression, large block encryption) can only multiply
: the work factor by a relatively small amount. [...]
You are mistaken here. Coompression can make a brute force search
impossible from a situation where a brute force search before
compression would yield a unique plaintext.
: It is *possible* that this amount is enough to make the difference
: between secure and not secure. It seems extraordinarly *unlikely* in
: any real, practical system.
Not really - all it has to do is lower the message size below the unicity
distance.
: If nothing else, note that the adversary's
: capabilities, a moving target at best, factor in to the equation.
The adversary's computational abilities don't enter into it, if
finding a unique solution has become theoretically impossible.
Tim Tyler
: I contend that complexity is the single greatest obstacle to secure systems.
Perhaps. Ignorance, stupidity, carelessness, lack of education
and laziness probably ought to be factored in somewhere.
David Wagner
>Signatures should normally be attacked to the document being signed.
>Usually this occurs prior to compression.
In application-layer encryption, yes. In network-layer encryption, no.
As I said before, I don't claim this applies to all systems. Rather,
it is an example of a more general point: As you add complexity, it can
become harder to verify whether the system is secure.
David Hopwood
Tim Tyler wrote:
> David Wagner <d...@mozart.cs.berkeley.edu> wrote:
> : I agree. Far more systems have failed from too much
> : complexity than have failed because there was a practical
> : cryptanalytic known-plaintext attack on a well-chosen cipher.
>
> Indeed. However cryptanalytic known-plaintext attacks are *not* the only
> type of failure that eliminating known plaintext helps defend against.
Modern ciphers are almost always used a long way past the unicity distance.
So, if the keyspace is reduced enough (by whatever means) to be searchable,
then the cipher can be broken, period. Reducing the amount of known plaintext
by compression (application-specific or otherwise) will not change this for
practical, real-world protocols.
Your (Tim Tyler's) argument seems to be that there are a few situations
where the message might already be short enough that compression will
reduce the length to below the unicity distance. I think this will happen
in so few cases that it is not worth bothering with as a security measure.
Of course, there are other, non-security-related reasons for using
compression, which should be considered on their merits. Also, excessive
redundancy of formats is undesirable regardless of whether they are
encrypted or not. (Redundancy is not excessive if there is a good reason
for it, such as human readability, or provision for future expansion.)
Re: the OP's argument - I generally agree that there is a great deal of FUD
and misunderstanding about the "dangers of known plaintext", and that some
protocols are unnecessarily bent out of shape because of that. The worst
cases are protocols that do not encrypt data that needs to be encrypted,
just because someone argued that it could provide known plaintext.
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBOzFCWDkCAxeYt5gVAQFr8wf+McYB8NgCh+m/Y48GGvxMC+mOFPPE6csq
FBVKROSkUPTyF/KLXiuK6OHqyuvIka1rfqedb8JFxOdBDI9T2EwTRZMmRBZA9FSR
UNHceGMlNSq6O/R8bW09QaL0u0UwuKbZln4IkInMTJOd+GMkoCy3gBEpUKQnwkN1
a5qCEkQ2H1bTdIz1gaKvlIz+TOGEYwJDOR9VpxndQaUpGB1257j+rqVxCjx4cvHE
ufGH0Ulfk4m2rvodOQQp5EvOy18hNCaMWfZ2tqxggK8GfUm8wVnLaS+tIyGkr/pb
5G+flHBw1oMiismhe1jAQK6HUMqitq91enpE8GkGgpu1TlVS0HPCUA==
=Uo9f
-----END PGP SIGNATURE-----
lcs Mixmaster Remailer
> Re: the OP's argument - I generally agree that there is a great deal of FUD
> and misunderstanding about the "dangers of known plaintext", and that some
> protocols are unnecessarily bent out of shape because of that. The worst
> cases are protocols that do not encrypt data that needs to be encrypted,
> just because someone argued that it could provide known plaintext.
Excellent point! Wasn't it claimed that the early versions of PGP failed
to encrypt the length fields of the private key numeric values because
of this reason? They were thought to be too guessable and would provide
known plaintext. Apparently the new key formats do have them encrypted,
which is surely superior. It's probably simpler as well.
Bryan Olson
Terry Ritter wrote:
>
> John Savard) wrote:
>
> >[...]
> >It is possible to have reasons for confidence in something that fall
> >short of proof, and it is even possible for such reasons to be
> >sufficient to make some forms of precaution unwarranted.
>
> Not in cryptography.
[...]
> The obvious approach to minimizing the risk of known-plaintext is to
> encipher at least twice with different ciphers and keys, so that the
> plaintext to the last cipher is both randomized and hidden even from
> the authorized user. I always recommend using three ciphers, which
> allows one to be completely broken without exposing the others.
Then the attacker gets known plaintext against a cipher that happens
to be built from two or three other ciphers. And if we believe we
cannot have confidence without proof, then we have the same problem
we started with. We are just as motivated to triple the ciphers that
that are themselves tripled ciphers.
--Bryan
Tim Tyler
:> : I agree. Far more systems have failed from too much
:> : complexity than have failed because there was a practical
:> : cryptanalytic known-plaintext attack on a well-chosen cipher.
:>
:> Indeed. However cryptanalytic known-plaintext attacks are *not* the only
:> type of failure that eliminating known plaintext helps defend against.
: Modern ciphers are almost always used a long way past the unicity distance.
: So, if the keyspace is reduced enough (by whatever means) to be searchable,
: then the cipher can be broken, period. [...]
It seems you go from "almost always" to complete certainty, without
showing your working. Also note that the unicity distance for the
system can be much larger when compression has been employed.
: Your (Tim Tyler's) argument seems to be that there are a few situations
: where the message might already be short enough that compression will
: reduce the length to below the unicity distance. I think this will happen
: in so few cases that it is not worth bothering with as a security measure.
: Of course, there are other, non-security-related reasons for using
: compression, which should be considered on their merits. [...]
To summarise - compression has a number of benefits, which include:
* Improved information-theoretic security when message size is
in the vicinity of the unicity distance;
* Fewer plaintext/cyphertext pairs given to opponent (this can be
achived in other ways as well);
* Plaintext diffusion - this can increase the work factor
significantly. E.g. say a message always ends "yours, Fred Bloggs."
Before compression, an attacker could decrypt the last block and
look for this text. After compression, he has to decrypt the entire
message, decompress the entire message, and then apply his test.
* Messages are shorter, can be transmitted faster, allowing less time
to be spent broadcasting a signal, reducing opportunities for tracing.
* Detecting correct decrypts after decompression takes more sophisticated
algorithms. Where before you could check for ASCII's missing bit, now
every decrypt has that. Where before you could check for randomness,
now every decrypt is highly non-random. This means more programming
work for each message type, more computer work in testing correct
decrypts, and more plaintext required to perform the tests in the first
place.
* Rejecting plaintexts is /slightly/ harder work - because of the
work in performing the additional unkeyed transform involved.
The argument that compression doesn't generally get messages down to the
unicity distance seems to assume that the unicity distance is small.
Recall that compression increases the unicity distance - and can do so
arbitrarily far. "Perfect compression" results in a unicity distance
which is infinite. In such a system, every cyphertext decrypts to a
plausible-looking plaintext. If this happens, brute force search is
not a practical possibility, regardless of message size.
We may not yet be anwhere near perfect compressors for the domain of
English text, but in other domains, much better can be done -
and compressors are improving all the time.
The unicity distance is the redundancy in the inputs to the encryptor.
After compression, this redundancy may be rather small - making the
unicity distance rather large.
Tim Tyler
: Tim Tyler wrote:
:>If you /ever/ transmit small quantities of information under a key, it
:>can help.
: Right. And my claim is that this case almost never happens (it is so
: rare that it should have minimal weight in any decision). [...]
I guess it depends on how small we are thinking.
The "small" refers to messages whose length is roughly equal to the
unicity distance for the system.
However, it is important to recall that compression can increase the
unicity distance - and can sometimes increase it dramatically.
For example if random ASCII (i.e. 7-bit) plaintexts were being transmitted
under a 128-bit key, then compression could increase the unicity distance
from thirty-something bytes to *infinity* - no matter how long your
messages were they would still be within the unicity distance.
No we may not have access to such compressors for the domain of English
text messages - but it seems worth noting that in some domains, the
unicity distance after compression has been applied can be quite large -
and will only grow as compression algorithms increase in sophistication.
Tim Tyler
: For example if random ASCII (i.e. 7-bit) plaintexts were being transmitted
: under a 128-bit key, then compression could increase the unicity distance
: from thirty-something bytes [...]
Apologies for this gross under-estimate.
This math makes no odds to the argument, though.
Mark Wooding
> Using a random IV adds an extra \mu^2 / 2^L term to the advantage of
> the adversary.)
Sorry, q, not \mu.
-- [mdw]
Terry Ritter
But that argument makes sense only if every "cipher" is the same as
every other "cipher," something we all know to be false. That is a
debating ploy, not an argument.
The "cipher" composed of a sequence of different ciphers is a vastly
more complex transformation than any component cipher, as we can see
from the expanded keyspace. Using a sequence of different ciphers is
how we multiply ciphers both in number and complexity; this is Shannon
multiplication of secrecy systems.
Even just a single tripling addresses practical problems that
conventional ciphering wisdom otherwise leaves open:
As one example, when we use one cipher alone, that cipher may actually
be already broken, in the context of the opponents. What we can do
about this is to place that same cipher in a stack with other ciphers.
That hides known-plaintext information. Knowing both clear ciphertext
and something about plaintext is how ciphers are broken; if we can
really hide either or both, a cipher becomes far stronger in practice.
Of course, even if one of the ciphers *is* broken in situ, the others
continue to protect our data. That is Shannon multiplication of
secrecy systems.
As another example, when we use one cipher alone, if our cipher is
already broken, we will continue to use it and so expose our data
day-after-day, until we do something about it. What we can do about
that is to change ciphers, and so have a new chance of getting a
strong one. And if we change ciphers frequently, we also have the
advantage of reducing the amount of data under any one cipher, which
reduces both the motivation and the ability to invest in attacks on
that cipher. Selecting among different ciphers is Shannon addition of
secrecy systems.
Clearly, if we do both -- use, say, three ciphers in sequence and
change them frequently -- we gain the advantage of changing ciphers,
with protection against using weak ciphers. And that is Shannan's
"algebra of secrecy systems."
---
Terry Ritter rit...@io.com http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
John Myre
>
> On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E...@nospam.net>,
> in sci.crypt Bryan Olson <nos...@nospam.net> wrote:
>
> >Terry Ritter wrote:
> >>
> >> The obvious approach to minimizing the risk of known-plaintext is to
> >> encipher at least twice with different ciphers and keys, so that the
> >> plaintext to the last cipher is both randomized and hidden even from
> >> the authorized user. I always recommend using three ciphers, which
> >> allows one to be completely broken without exposing the others.
> >
> >Then the attacker gets known plaintext against a cipher that happens
> >to be built from two or three other ciphers. And if we believe we
> >cannot have confidence without proof, then we have the same problem
> >we started with. We are just as motivated to triple the ciphers that
> >that are themselves tripled ciphers.
>
> But that argument makes sense only if every "cipher" is the same as
> every other "cipher," something we all know to be false. That is a
> debating ploy, not an argument.
It might be right to construct a cipher out of three component
ciphers, different in structure. It's incredibly difficult to
believe that it wouldn't be stronger. The *logical argument*,
however, goes to Bryan. From the premise that we don't know
the strength of our ciphers we can only conclude that we don't
know the strength of any construction based on them, either.
If we want to conclude that tripling is right, we have to assume
something like "most of our presumed-strong ciphers actually are
strong, we just don't know which ones," or some other premise
that says *something* about the component cipher strengths.
JM
Sean Furey
>Let us all agree that it is time to put concerns about known plaintext
>behind us. Recommendations to avoid it are obsolete.
As I see it (from a newbieish point of view) known plaintext is still
a problem. Whilst modern encryption algorithms may prevent the key
from being obtained with a known plaintext/ciphertext combination, it
makes brute forcing the message easier. There has been discussions
here recently about how you can tell if the plaintext you have
obtained using a particular key is the correct plaintext, with the
suggestion being to watch out for patterns. If you know the
plaintext, or what format it will take, it is much easier to look out
for these patterns.
--
Sean Furey, a happy and satisfied Debian user.
se...@furey.freeserve.co.uk
Paul Pires
John Myre <jm...@sandia.gov> wrote in message news:3B325669...@sandia.gov...
Playing Devils advocate. If the individual threat to all three
ciphers was something that involved known plaintext. Wouldn't
it be obvious that combining the ciphers must be more secure
since the intermediate ciphertexts (AKA the intermediate plaintexts)
are not preserved?
Cipher 1 may have a known plaintext but the corresponding ciphertext is gone.
Ciphert 2 has no known plaintext or ciphertext.
Cipher 3 has a known ciphertext but no known plaintext.
Is there any known "known plaintext attack" that works without knowledge
of the ciphertext? Is there any ciphertext only attack that can work when the
plaintext is unknowable and Pseudo-random? Forget the philosophy of multi
encryption and check the assumptions for all known attacks.
Sure this only applies to Known attacks, what about the unknown ones?
Who cares? It may be possible to *prove* that a method is unbreakable
to all known attacks to date, faster than brute force.
That has to be worth something.
This is the one part of this multi-encryption argument that I just can't
get a grip on. Folks seem to be arguing the Gotta-be-there weaknesses
of the individual ciphers but I can't see how the requirements for the
Gotta-be-there attacks are provided by the multi cipher example. It
looks like a no-go from front to back, middle out and back to front.
Am I too far gone here or just missing a clue?
Paul
David Wagner
>As I see it (from a newbieish point of view) known plaintext is still
>a problem. Whilst modern encryption algorithms may prevent the key
>from being obtained with a known plaintext/ciphertext combination, it
>makes brute forcing the message easier.
All good modern algorithms make brute-force keysearch attacks
totally infeasible, simply by making the key space large enough
to resist such attacks.
Terry Ritter
On Thu, 21 Jun 2001 21:58:11 +0000 (UTC), in
<9gtqlj$1qmc$2...@agate.berkeley.edu>, in sci.crypt
d...@mozart.cs.berkeley.edu (David Wagner) wrote:
Yes, but the argument goes way beyond brute force.
Without "knowing something" about the plaintext, opponents simply have
no way to know when they have the right key. It is the knowledge of
the plaintext, or of some structure in the plaintext, plus the
ciphertext, which allows someone to know when the correct key has been
found *by* *any* *approach* *at* *all*.
I think the reason we don't make a bigger deal out of known-plaintext
is that, in practice, it is so difficult to prevent. But a stack of
ciphers, by itself, does prevent known-plaintext exposure for the
individual ciphers. Yes, known-plaintext may exist for the overall
stack. However, the overall cipher has about three times the key bits
of the individual ciphers, and is a far more complex transformation.
The overall cipher is thus hardly the ideal target.
Douglas A. Gwyn
> Douglas A. Gwyn <DAG...@null.net> wrote:
> : I think the right way to present it is "Modern cryptosystems are
> : specifically designed for resistance to known-plaintext attacks,
> : among other things. Therefore, if you know that a modern
> : cryptosystem will be used, you needn't be concerned about the
> : possibility of a known-plaintext attack. [...]
> Compare with: "Modern windows are designed not to break. Therefore,
> if you fit your shop with modern windows, you needn't be concerned
> about the possibility of them breaking."
Assuming that modern windows were indeed unbreakable.
> Alas, this leaves the shoplifters out of the picture.
It also leaves purple unicorns out of the picture.
Terry Ritter
That "logical argument" is a "red herring": I made no claim that
cipher stacks have provable known strength. But since we are
comparing the situation where we have one cipher against having a
stack of three ciphers, the issue would seem to be the same in both
cases.
I claim that, simply by using a cipher stack, known-plaintext
information is not available to the opponent for use in attacks
against the component ciphers. Not exposing known-plaintext is a very
serious advantage.
>If we want to conclude that tripling is right, we have to assume
>something like "most of our presumed-strong ciphers actually are
>strong, we just don't know which ones," or some other premise
>that says *something* about the component cipher strengths.
Well, if we suppose that *all* are ciphers are weak, there might seem
to be no point in using ciphers at all.
On the other hand, multiciphering with three different ciphers and
independent keys makes an overall "cipher" that is arguably much
stronger than its component parts, and also prevents the exposure of
information which might otherwise have been used to attack those
parts. So even if every fundamental block cipher really is weak, the
multiciphering stack of three ciphers may *not* be.
Terry Ritter
On Thu, 21 Jun 2001 22:41:19 GMT, in <3B32780F...@null.net>, in
sci.crypt "Douglas A. Gwyn" <DAG...@null.net> wrote:
>Tim Tyler wrote:
>> Douglas A. Gwyn <DAG...@null.net> wrote:
>> : I think the right way to present it is "Modern cryptosystems are
>> : specifically designed for resistance to known-plaintext attacks,
>> : among other things. Therefore, if you know that a modern
>> : cryptosystem will be used, you needn't be concerned about the
>> : possibility of a known-plaintext attack. [...]
>> Compare with: "Modern windows are designed not to break. Therefore,
>> if you fit your shop with modern windows, you needn't be concerned
>> about the possibility of them breaking."
>
>Assuming that modern windows were indeed unbreakable.
Only if we ASSUME (that is, make an ASS out of U and ME), that modern
ciphers really *are* "indeed unbreakable." But every generation
thought their ciphers were unbreakable.
Simply being designed to be unbreakable is hardly the same thing.
That's a wish and a hope, not reality.
Mok-Kong Shen
Terry Ritter wrote:
>
[snip]
> On the other hand, multiciphering with three different ciphers and
> independent keys makes an overall "cipher" that is arguably much
> stronger than its component parts, and also prevents the exposure of
> information which might otherwise have been used to attack those
> parts. So even if every fundamental block cipher really is weak, the
> multiciphering stack of three ciphers may *not* be.
I guess that it could be useful in this connection to
recall the fact that a good block cipher needs a sufficient
number of rounds, which are put together in a cascading
fashion not 'entirely' different in principle to cascading
multiple ciphers.
M. K. Shen
DJohn37050
good thing. So it should not be considered harmless with zero effect. It
might have a negligible effect or it might be large but it is not zero.
Don Johnson
John Savard
wrote, in part:
>From the premise that we don't know
>the strength of our ciphers we can only conclude that we don't
>know the strength of any construction based on them, either.
True. But even a weak cipher, as long as it does have a variable key,
will indeed prevent a known-plaintext attack on the next cipher in the
chain. Similarly, a weak cipher with a variable key will deny known
ciphertext to the attacker of the preceding cipher in the chain.
So, in a certain case - where one of the three ciphers is weak only
against a known plaintext attack - something has been achieved, hence
improving the odds.
The point is, though, without proof of strength in either case, we
don't know either that using three ciphers is warranted (any one
recognized modern cipher may be strong enough, as generally believed)
or that it will be sufficient to solve the problem (our unknown
opponents may have even more powerful techniques than we guess).
Thus, using three ciphers in a row will only improve security under a
certain set of conditions.
This is a valid criticism.
But on the other hand, it's an easy enough thing to do, and, since
many messages need to stay secret for extended periods, and since
computers are getting faster at such a rate (even quantum computers
may be on the horizon) it's just possible that even if modern ciphers
are quite secure at present, it is really going to be worth tripling
up against threats that will emerge within the next 100 years.
To me, though, the killer criticism of using, say, a
Rijndael/MARS/SAFER+ sandwich for encryption is that the danger of a
breakthrough against block ciphers is - obviously - small in
comparison to the danger of solving far less messy problems of far
greater general utility and with a wider array of mathematical tools
to attack them. Factoring. Discrete logarithm.
If people are going to insist on using public-key cryptosystems to
distribute their keys, possible weaknesses in block ciphers in general
seem like a very small threat. (However, the risk that any single
block cipher could have a severe, unnoticed flaw is, I have to admit,
large enough to be real, which is a strong argument for
multiciphering.)
Thus, I tend to think that any serious attempt to upgrade the security
of conventional cryptography - and such attempts are quite possible,
and don't require inordinate amounts of computer time to implement -
is quite properly viewed as pointless, except for those who are
willing to give up the convenience of public-key cryptography. (They
might still *use* PKC, however, to augment the security of those
hand-transported secret keys.)
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Savard
<mok-ko...@t-online.de> wrote, in part:
>I guess that it could be useful in this connection to
>recall the fact that a good block cipher needs a sufficient
>number of rounds, which are put together in a cascading
>fashion not 'entirely' different in principle to cascading
>multiple ciphers.
True. Of course, an important difference is that block ciphers usually
repeat the same round many times, although with different subkeys, and
this could be bad if the round is weak in certain ways.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Savard
wrote, in part:
>Sure this only applies to Known attacks, what about the unknown ones?
>Who cares? It may be possible to *prove* that a method is unbreakable
>to all known attacks to date, faster than brute force.
>That has to be worth something.
>Am I too far gone here or just missing a clue?
The only thing missing here is that the individual ciphers it is being
proposed to triple up are *already* immune to any known attacks to
date that is faster than brute force!
Still, immunity to any unknown attack remotely similar to the kinds of
attacks that are known must be worth something...
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
David Wagner
>But even a weak cipher, as long as it does have a variable key,
>will indeed prevent a known-plaintext attack on the next cipher in the
>chain.
How do you know? If we don't know for certain whether our ciphers are
secure (and we don't know), we can't know this for certain, either.
David Wagner
Yes. Fortunately, we have proofs for our favorite modes of operation
that, so long as you don't try to get too close to the birthday, the
effect will be negligible. So this should not be a concern.
And it this should not be surprising. It is very rare in crypto to be
able to achieve zero effect; usually we have to be satisfied with giving
the attacker a negligible advantage, unless we are willing to use one-time
pads and so forth. If you're concerned about negligible advantages, then
you shouldn't waste time thinking about which mode of operation to use:
you must not use any computationally-secure cryptosystems, no matter what
mode they're in.
SCOTT19U.ZIP_GUY
>
>On Thu, 21 Jun 2001 22:41:19 GMT, in <3B32780F...@null.net>, in
>sci.crypt "Douglas A. Gwyn" <DAG...@null.net> wrote:
>
>>Tim Tyler wrote:
>>> Douglas A. Gwyn <DAG...@null.net> wrote:
>>> : I think the right way to present it is "Modern cryptosystems are
>>> : specifically designed for resistance to known-plaintext attacks,
>>> : among other things. Therefore, if you know that a modern
>>> : cryptosystem will be used, you needn't be concerned about the
>>> : possibility of a known-plaintext attack. [...]
>>> Compare with: "Modern windows are designed not to break. Therefore,
>>> if you fit your shop with modern windows, you needn't be concerned
>>> about the possibility of them breaking."
>>
>>Assuming that modern windows were indeed unbreakable.
>
>Only if we ASSUME (that is, make an ASS out of U and ME), that modern
>ciphers really *are* "indeed unbreakable." But every generation
>thought their ciphers were unbreakable.
>
One great teacher I had said look at history. Only a fool thinks
our frame of reference is different or that we are better. History
has showed. Every generation seemed to think they were unbreakable
and they were wrong. There is no reason to believe we are specail
and that we know they are unbreakable. Because it we do in 50 years
they will laugh at our stupidity. I am already laughing. since
Shannon has taught what some of the goals we should strive towards
and the fools say its of no concern with modern ciphers. They are wrong
and quantum computers for one thing will prove that.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Tom St Denis
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:90C7B8866H110W...@207.36.190.226...
... he says while insisting everything he does is correct ....
Def'n irony: see above.
Tom
David Hopwood
Tim Tyler wrote:
> David Hopwood <david....@zetnet.co.uk> wrote:
> : Tim Tyler wrote:
> :> David Wagner <d...@mozart.cs.berkeley.edu> wrote:
>
> :> : I agree. Far more systems have failed from too much
> :> : complexity than have failed because there was a practical
> :> : cryptanalytic known-plaintext attack on a well-chosen cipher.
> :>
> :> Indeed. However cryptanalytic known-plaintext attacks are *not* the only
> :> type of failure that eliminating known plaintext helps defend against.
>
> : Modern ciphers are almost always used a long way past the unicity distance.
> : So, if the keyspace is reduced enough (by whatever means) to be searchable,
> : then the cipher can be broken, period. [...]
>
> It seems you go from "almost always" to complete certainty, without
> showing your working.
Suppose the keyspace is searchable. If an attacker can break a cryptosystem
in almost all cases where that happens, it's more than enough from the
attacker's point of view. The aim of a cryptosystem is to prevent attacks
from being successful in more than a negligable fraction of cases. Obviously
there's a big difference between "negligable fraction" and "almost all".
> Also note that the unicity distance for the system can be much larger when
> compression has been employed.
My assumption is that the compressed text still has a significant amount of
redundancy - say, at least 0.1 bits/bit. This estimate is very generous to
your side of the argument; in fact, I've never seen a compressor do that well
on real-world data. Given this assumption, the unicity distance will be at
most 10 * log2(size of remaining keyspace) bits, and this is an upper bound on
the amount of compressed text that can be sent with information theoretic
security (in fact information starts to be leaked before that bound).
I don't consider a factor of at most 10 to be "much" larger, and for
general-purpose compressors like DEFLATE, etc., the effect of compression
on unicity distance will be considerably less than that. I don't care about
artificial examples like sending meaningless random data which is then
never used, since no-one would want to do that in practice.
> : Your (Tim Tyler's) argument seems to be that there are a few situations
> : where the message might already be short enough that compression will
> : reduce the length to below the unicity distance. I think this will happen
> : in so few cases that it is not worth bothering with as a security measure.
> : Of course, there are other, non-security-related reasons for using
> : compression, which should be considered on their merits. [...]
>
> To summarise - compression has a number of benefits, which include:
>
> * Improved information-theoretic security when message size is
> in the vicinity of the unicity distance;
See above.
> * Fewer plaintext/cyphertext pairs given to opponent (this can be
> achived in other ways as well);
This is not in dispute, but note that modern ciphers can reasonably be
expected to be computationally secure even when huge numbers of plaintext/
ciphertext pairs are available.
> * Plaintext diffusion - this can increase the work factor
> significantly.
At best it increases the work for a key search proportionally to the
length of the message, but if you want to do this reliably then you should
use an AONT; compression won't necessarily suffice, because it is not
designed to provide diffusion.
> E.g. say a message always ends "yours, Fred Bloggs."
> Before compression, an attacker could decrypt the last block and
> look for this text. After compression, he has to decrypt the entire
> message, decompress the entire message, and then apply his test.
If "Fred Bloggs" did not occur earlier in the message, then for typical
LZ-based algorithms, no, the attacker would not necessarily have to decrypt
the entire message.
> * Messages are shorter, can be transmitted faster, allowing less time
> to be spent broadcasting a signal, reducing opportunities for tracing.
They are shorter by a small factor. For most applications, tracing is not
an issue.
> * Detecting correct decrypts after decompression takes more sophisticated
> algorithms.
Not really. If you want to claim that, you'll have to demonstrate it for
real data and real compression algorithms.
> Where before you could check for ASCII's missing bit, now
> every decrypt has that. Where before you could check for randomness,
> now every decrypt is highly non-random. This means more programming
> work for each message type, more computer work in testing correct
> decrypts, and more plaintext required to perform the tests in the first
> place.
No, more plaintext is probably not required if the beginning of the
plaintext is redundant (since most compression algorithms have the property
that decompressing a prefix of the output will give a prefix of the input).
> * Rejecting plaintexts is /slightly/ harder work - because of the
> work in performing the additional unkeyed transform involved.
All of the above points amount to not very much security benefit.
> The argument that compression doesn't generally get messages down to the
> unicity distance seems to assume that the unicity distance is small.
The unicity distance *is* small for short-key ciphers used on typical
data formats - often only a few hundred bits.
> Recall that compression increases the unicity distance - and can do so
> arbitrarily far. "Perfect compression" results in a unicity distance
> which is infinite.
Perfect compression does not and cannot exist in non-trivial cases.
> In such a system, every cyphertext decrypts to a
> plausible-looking plaintext. If this happens, brute force search is
> not a practical possibility, regardless of message size.
>
> We may not yet be anwhere near perfect compressors for the domain of
> English text,
... nor is there any reason to believe that problem is solvable.
To even begin to approach that goal, the compressor would need
to include an English dictionary and grammar model [*] (otherwise the
attacker can detect redundancy by checking spelling and grammar).
That would make such compression impractical for most protocols.
[*] Or, for internationalised applications, a dictionary and grammar
model for every language that might be used.
> but in other domains, much better can be done - and compressors are
> improving all the time.
Meaningful data will have some redundancy that is difficult to remove,
because it is too hard to model accurately. I suspect this problem
is generally as hard for other formats as it is for natural language
text.
> The unicity distance is the redundancy in the inputs to the encryptor.
> After compression, this redundancy may be rather small - making the
> unicity distance rather large.
You keep repeating this, without any evidence that the unicity distance
would ever be large enough to provide a significant security benefit in
practical cases.
- --
David Hopwood <david....@zetnet.co.uk>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
iQEVAwUBOzKnDDkCAxeYt5gVAQHy2AgAtrMnuysI34FkZ+Y+R56p6QFIAMQ2x9Il
LqWfMGwmsxdVuHAIALjb9NQCCDXKYY6pjoP3Bep5yqPFEI9t/zBmD0oo2i6dnqYJ
AOmzqAI26i2iSaDuFjeU+63On2LYwAB+czKrmJ9HICnNdC2SfyBad3pBQLFvUDhU
U67jvcie4DU8H0qa4/Z5xOGvrs1wxHrixfQCeHxlxGwP91WrT2IbMatUBgE7ZxbR
fMC4725ec5j/R1hrizxJQ5rNi4iPkUdx46qtN6gPzHUx6GXkSZPgb52el9iN7PyF
UEjXpxZ1FABDNOJWSnHyUmxFSrLBcpl9nSnbbp9KNLGSq54w2y1pNw==
=bP22
-----END PGP SIGNATURE-----
Alexis Machado
"Mok-Kong Shen" <mok-ko...@t-online.de> wrote in message
news:3B328B5D...@t-online.de...
You discovered why cipher chaining is not necessary.
---
Alexis
Terry Ritter
On Thu, 21 Jun 2001 23:52:10 -0300, in
<tj5cfo5...@corp.supernews.com>, in sci.crypt "Alexis Machado"
<alexis...@ieg.com.br> wrote:
First of all, "chaining" is the worst possible description of
multiciphering: A "chain" is only as strong as its weakest link;
multiciphering is as strong as its strongest cipher.
Next, the point of multiciphering is not strength, per se. If we
could trust the strength we supposedly get from a single cipher, there
would be no point. Unfortunately there is no way to know how a cipher
will fare against real opponents; there is no feedback, thus no way to
know when we have succeeded or failed.
We cannot know how good a design really is with respect to real
opponents. The reason for multiciphering is to address this
uncertainty as best we can.
Using structurally different ciphers and different keys is
fundamentally different than just using more rounds. Usually we have
a fixed design and don't have the opportunity to triple the number of
rounds anyway. And we can't just go around re-designing standard
ciphers under the illusion that more rounds and an arbitrary expanded
key schedule is necessarily better; it is not.
Bryan Olson
Terry Ritter wrote:
>
> On Thu, 21 Jun 2001 01:50:22 -0700, in <3B31B54E...@nospam.net>,
> in sci.crypt Bryan Olson <nos...@nospam.net> wrote:
>
> >Terry Ritter wrote:
> >>
> >> John Savard) wrote:
> >>
> >> >[...]
> >> >It is possible to have reasons for confidence in something that fall
> >> >short of proof, and it is even possible for such reasons to be
> >> >sufficient to make some forms of precaution unwarranted.
> >>
> >> Not in cryptography.
> >
> >[...]
> >
> >> The obvious approach to minimizing the risk of known-plaintext is to
> >> encipher at least twice with different ciphers and keys, so that the
> >> plaintext to the last cipher is both randomized and hidden even from
> >> the authorized user. I always recommend using three ciphers, which
> >> allows one to be completely broken without exposing the others.
> >
> >Then the attacker gets known plaintext against a cipher that happens
> >to be built from two or three other ciphers. And if we believe we
> >cannot have confidence without proof, then we have the same problem
> >we started with. We are just as motivated to triple the ciphers that
> >that are themselves tripled ciphers.
>
> But that argument makes sense only if every "cipher" is the same as
> every other "cipher," something we all know to be false. That is a
> debating ploy, not an argument.
Oh spare us the nonsense. That mistake - evaluating all ciphers
as the same - is the error you commit when you disagreed with Savard's
quote above.
> The "cipher" composed of a sequence of different ciphers is a vastly
> more complex transformation than any component cipher, as we can see
> from the expanded keyspace.
But you don't even look at the component ciphers. You blindly
advocate composing three with no regard to their complexity.
Whatever the right extent of conservative design is, it makes
no sense to say it's automatically three times what any other
cipher designers choose.
--Bryan
SCOTT19U.ZIP_GUY
<3B32A75C...@zetnet.co.uk>:
>
>> Also note that the unicity distance for the system can be much larger
>> when compression has been employed.
>
>My assumption is that the compressed text still has a significant amount
>of redundancy - say, at least 0.1 bits/bit. This estimate is very
>generous to your side of the argument; in fact, I've never seen a
>compressor do that well on real-world data. Given this assumption, the
>unicity distance will be at most 10 * log2(size of remaining keyspace)
>bits, and this is an upper bound on the amount of compressed text that
>can be sent with information theoretic security (in fact information
>starts to be leaked before that bound).
>
>I don't consider a factor of at most 10 to be "much" larger, and for
>general-purpose compressors like DEFLATE, etc., the effect of
>compression on unicity distance will be considerably less than that. I
>don't care about artificial examples like sending meaningless random
>data which is then never used, since no-one would want to do that in
>practice.
Actaully if the uncity disctance increased by a factor of 10
then the amount of plain text needed goes up much higher since you
really are taking about the amount of "cipher text" the plain text
length would be the factor of 10 times however much it expands when
you decompress it.
Secondly the rest of stuff is talking about poor compressers
that start slowly. Obviously you've never heard of BWT compressors.
I can give you half the file and you want know what it means. Since
the actaully message is diffused through the whole thing during
the compression process.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
John Savard
(David Wagner) wrote, in part:
>John Savard wrote:
Maybe I just defined my terms badly. One can have a cipher that isn't
secure, but is still known to (usually) produce different ciphertext
for any plaintext if the key is changed.
Of course, in that connection, one might note that DESX doesn't gain
any resistance to differential cryptanalysis, which is usually
considered a "known-plaintext" attack. Because you don't really need
to know the plaintext itself with certainty, only the XOR between
pairs of plaintexts, to do differential cryptanalysis.
Thus, a cascade of three ciphers that are very weak against a
differential attack can still be submitted to a differential attack;
as long as one can cascade the characteristics. (If they're very weak,
there will be multiple possibilities.) So if some unknown attack has
similar properties...
I do agree that it is only for a very specific circumstance that
triple encipherment (for example) is neither unnecessary nor useless,
and there is no particularly compelling evidence to suggest that the
strength of contemporary block ciphers is in that narrow range. But I
also noted that, if triple encipherment is unnecessary at present, as
most experts believe, then within the next 75-100 years, advances in
computer power just might cause their strength to at least enter that
zone. Of course, on
http://home.ecn.ab.ca/~jsavard/crypto/co041205.htm
I suggest rather more extreme measures for the worriers among us than
mere triple encipherment.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
John Savard
(SCOTT19U.ZIP_GUY) wrote, in part:
>Every generation seemed to think they were unbreakable
>and they were wrong. There is no reason to believe we are specail
>and that we know they are unbreakable.
Actually, there _is_ a reason. The microchip. It lets us use
arbitrarily complicated ciphers.
So if we actually let ourselves go, and really made it work to
encipher our messages, instead of using algorithms designed to work at
blazing speed on minimal hardware, we might well have grounds for a
limited degree of confidence or even complacency.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html
Tim Tyler
: If we want to conclude that tripling is right, we have to assume
: something like "most of our presumed-strong ciphers actually are
: strong, we just don't know which ones," or some other premise
: that says *something* about the component cipher strengths.
That would be what was needed if we wanted to claim that a cypher stack
was *strong*.
You barely need to say anything to claim that it's *stronger* than any of
the individual encryptions.
No doubt the proper point of comparison for a cypher stack would be a
purpose-designed algorithm with three times the keyspace of conventional
cyphers.
--
__________
|im |yler http://rockz.co.uk/ http://alife.co.uk/ http://atoms.org.uk/
Tim Tyler
: Sean Furey wrote:
Which would be OK, *if* there were no other ways of getting
information about which keys might have been used, besides via
an examination of the cyphertext.
There *are* other ways. They are /well known/. For example,
exploiting a low-entropy key-generator.
Such considerations effectively *reverse* the conclusion - from:
"Known-plaintext is not a problem because brute-force is impractical"
...to...
"Known-plaintext /can/ be a problem, because it makes rejecting
keys practical - and this is useful, if the keyspace can be
reduced to a searchable region by other means".
--
__________
|im |yler t...@iname.com Home page: http://alife.co.uk/tim/
Tim Tyler
:> Douglas A. Gwyn <DAG...@null.net> wrote:
:> : I think the right way to present it is "Modern cryptosystems are
:> : specifically designed for resistance to known-plaintext attacks,
:> : among other things. Therefore, if you know that a modern
:> : cryptosystem will be used, you needn't be concerned about the
:> : possibility of a known-plaintext attack. [...]
:>
:> Compare with: "Modern windows are designed not to break. Therefore,
:> if you fit your shop with modern windows, you needn't be concerned
:> about the possibility of them breaking."
: Assuming that modern windows were indeed unbreakable.
This is exactly the assumption you are making about modern block cyphers.
:> Alas, this leaves the shoplifters out of the picture.
: It also leaves purple unicorns out of the picture.
Shoplifters try to break windows. Window manufacturers try to make them
hard to break.
Cryptanalysts try to break cyphers. Cryptographers try to make them
hard to break.
I really don't see where the purple unicorns enter into it - both
cryptanalysts and shoplifters *exist*. The idea that someone may be
trying to break your cypher is not necessarily a paranoid fantasy.
You might be able to argue that we see broken windows around, but not
broken cyphers.
I think we *do* see broken cyphers around - but anyway, there is an
important difference to note between the two systems.
When a shoplifter breaks a window, he graps the loot and scarpers,
leaving broken glass everywhere.
When a cryptanalyst breaks a cypher, he can resist the temptation
to get academic glory, and instead offer his services to those who would
wish to eavsdrop on the encrypted traffic. This can be far more lucrative.
Consequently he carefully cleans up after himself, and leaves as little
trace as possible to indicate that the cypher has been broken. Indeed
great effort is generally taken with any intercepted traffic to ensure
this secret is kept.
If you don't see broken cyphers, don't conclude that cyphers don't get
broken. This is probably what you would observe anyway.
Tim Tyler
:> : Tim Tyler wrote:
:> :> David Wagner <d...@mozart.cs.berkeley.edu> wrote:
:> : Modern ciphers are almost always used a long way past the unicity distance.
:> : So, if the keyspace is reduced enough (by whatever means) to be searchable,
:> : then the cipher can be broken, period. [...]
[...]
:> Also note that the unicity distance for the system can be much larger when
:> compression has been employed.
: My assumption is that the compressed text still has a significant amount of
: redundancy - say, at least 0.1 bits/bit. This estimate is very generous to
: your side of the argument; in fact, I've never seen a compressor do that well
: on real-world data. Given this assumption, the unicity distance will be at
: most 10 * log2(size of remaining keyspace) bits, and this is an upper
: bound on the amount of compressed text that can be sent with
: information theoretic security (in fact information starts to be leaked
: before that bound).
: I don't consider a factor of at most 10 to be "much" larger, and for
: general-purpose compressors like DEFLATE, etc., the effect of compression
: on unicity distance will be considerably less than that.
David Scott's point - that the unicity distance relates to the cyphertext,
and that the length of plaintext that can be sent increases faster than
the unicity distance because the cyphertext is subsequently decompressed,
and expands to form the plaintext - is a good one.
You don't think this size is significant? It will be in some applications.
Consider email encryption. Say you use Rijndael with a 256-bit key.
That gives a unicity distance of some 37 characters with English text.
English text has 84% redundancy. Taking your (admittedly optomistic)
example, say that is reduced to 10%. That gives a unicity distance of 320
characters of *cyphertext*. Decompress those 320 characters with your
(admittedly rather good) compressor and the message will be quite
significant - over 2.6K on average - if my sums based on your entropy
figures are correct.
This is not a fantastically and unrealistically short email message.
Sure some messages will be longer - but increasing the messages that could
be sent with some information-theortic security from 37 characters to a Kb
or so would be something worthwhile.
In practice, the unicity distance represents the point where there's a
single unique decrypt. Since a human being is likely to be a better
plausible plaintext-detector than any machine, you ideally want to get
things to a position where it is impractical for a human to search through
the decrypts - by making sure that there are thousands - or
tens-of-thousands of them. This is likely to involve the use of
larger keys.
[snip detailed objections]
Deano
content of the message secret, right? Never did understand this
'secrecy' thing. It always smacks to me of inadequacy. Why do some
people feel so inadequate that they have to 'specialise' themselves by
retaining some piece of knowledge?
Deano
Mark Wooding
> Playing Devils advocate. If the individual threat to all three
> ciphers was something that involved known plaintext. Wouldn't
> it be obvious that combining the ciphers must be more secure
> since the intermediate ciphertexts (AKA the intermediate plaintexts)
> are not preserved?
I think there's very little that's `obvious' around here. However, we
can /prove/ that cascading ciphers doesn't introduce any weaknesses,
assuming that they're keyed independently. (The proof is rather dull,
and included below for the sake of completeness. See Bellare, Desai,
Jokipii and Rogaway for background information.)
Proving that it actually helps seems very hard.
It's intuitively fairly clear that inventing a new key, pretending we
don't know what it is, and gluing a cipher with that key before or after
the encryption (which is basically what the proof below does) isn't the
most direct or efficient way of breaking an encryption scheme. But this
seems very hard to prove.
The proof
Suppose that X = (K, E, D) and Y = (K', E', D') are symmetric encryption
systems. Define Seq(X, Y) = (K^*, E^*, D^*) as follows:
* K^*(1^k) computes \kappa_X <- K (1^k) and \kappa_Y <- K'(1^k, and
returns the pair (\kappa_X, \kappa_Y)
* E^*(\kappa, x), where \kappa = (\kappa_X, \kappa_Y), computes c_X <-
E(\kappa_X, x) and returns c <- E'(\kappa_Y, c_X).
* D^*(\kappa, x), where \kappa = (\kappa_X, \kappa_Y), computes c_X<-
D'(\kappa_Y, x) and returns p <- D(\kappa_X, c_X).
Suppose A is an adversary which runs in time t, performs q_e queries to
a left-or-right encryption oracle totalling \mu_e bits, and performs q_d
queries to a decryption oracle totalling \mu_d bits, and has advantage
\epsilon distinguishing Seq(X, Y) in the left-or-right sense.
We construct the adversary A_X as follows:
Adversary A_X^{\mathcal{LR}(., .), \mathcal{D}(.)}
Choose \kappa <- K'(1^k)
Get b <- A^{\mathcal{LR}'(., .), \mathcal{D}'(.)} where
\mathcal{LR}'(l, r) = E'(\kappa, \mathcal{LR}(l, r))
\mathcal{D}'(c) = \mathcal{D}(D'(c))
return b
This adversary distinguishes X with the same advantage as A has against
Seq(X, Y), and makes the same number of queries ot its oracles. The
additional running time is only the time taken to run K'. The
additional size of the queries is related only to the ciphertext
expansion in E.
Similarly, we construct an adversary A_Y:
Adversary A_X^{\mathcal{LR}(., .), \mathcal{D}(.)}
Choose \kappa <- K(1^k)
Get b <- A^{\mathcal{LR}'(., .), \mathcal{D}'(.)} where
\mathcal{LR}'(l, r) = \mathcal{LR}(E(\kappa, l), E(\kappa, r))
\mathcal{D}'(c) = D'(\mathcal{D}(c))
return b
with the same properties against Y.
This proves that the combination Seq(X, Y) is no less secure than the
stronger of X and Y (in the left-or-right sense). If we define by
induction, Seq(A, B, C, ...) = Seq(A, Seq(B, Seq(C, ...))) we see can we
can build a cascade of ciphers which is at least as strong (in the
left-or-right sense) as the strongest cipher in the cascade, whichever
one that is. (Left-or-right security is at most a factor of 2 weaker
than real-or-random security, and much easier to use in this instance.)
-- [mdw]
SCOTT19U.ZIP_GUY
<3b32e2b9...@news.powersurfr.com>:
>On 22 Jun 2001 00:18:41 GMT, david_...@emailv.com
>(SCOTT19U.ZIP_GUY) wrote, in part:
>
>>Every generation seemed to think they were unbreakable
>>and they were wrong. There is no reason to believe we are specail
>>and that we know they are unbreakable.
>
>Actually, there _is_ a reason. The microchip. It lets us use
>arbitrarily complicated ciphers.
>
That same chip cuts both ways. Who would want to not use one
to break a cipher. All a chip does is compress time.
Tim Tyler
: jsa...@ecn.ab.SBLOK.ca.nowhere (John Savard) wrote in
:> david_...@emailv.com (SCOTT19U.ZIP_GUY) wrote, in part:
:>>Every generation seemed to think they were unbreakable
:>>and they were wrong. There is no reason to believe we are
:>>specail and that we know they are unbreakable.
:>
:>Actually, there _is_ a reason. The microchip. It lets us use
:>arbitrarily complicated ciphers.
: That same chip cuts both ways. Who would want to not use one
: to break a cipher. All a chip does is compress time.
Another reason would be that knowledge has improved -
today's cryptographers stand on the shoulders of giants.
At one time, nobody knew how to make a reasonable cypher that no-one could
break.
Now that situation is no longer with us - our strongest publicly-known
cyphers appear to be very strong, and resist all publicly-known attacks.
It seems possible that as time passes, the apparent gap between
public-codemakers and public-code-breakers will widen further.
This is not to encourage complanceny, though. For one thing, it is
possible that the hidden world is well in advance of public knowledge.
John Savard
part:
>I think there's very little that's `obvious' around here. However, we
>can /prove/ that cascading ciphers doesn't introduce any weaknesses,
>assuming that they're keyed independently.
That is not true when the second cipher in the chain is vulnerable to
a known-plaintext attack, particularly when the input to the first
cipher is either compressible, or is expanded by the first cipher.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html