Cryptography-Digest Digest #47, Volume #9 Sun, 7 Feb 99 04:13:04 EST
Contents:
Re: MAC generation ("Richard Parker")
Re: SCOTT COMPRESSION (fungus)
Re: SCOTT COMPRESSION (Terry Ritter)
Re: *** Where Does The Randomness Come From ?!? *** ("PAC")
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: Foiling 56-bit export limitations: example with 70-bit DES
([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: MAC generation
Date: Sun, 07 Feb 1999 04:13:51 GMT
"Vadim Lebedev" <[EMAIL PROTECTED]> wrote, in part:
>the MAC will be MD5(S+SecretPassPhrase)
Vadim,
You might want to take a look at the research of Bellare, Canetti,
and Krawczyk. They've done a number of papers on using keyed hash
functions to do message authentication. Try the following URL:
<http://www.research.ibm.com/security/keyed-md5.html>
They recommend the following construction:
H(K XOR opad, H(K XOR ipad, text))
Where:
1) H is a cryptograhpic hash function, such as MD5 or SHA-1,
2) K is the secret key,
3) ipad is the byte 0x36 repeated for a hash block, and
4) opad is the byte 0x5C repeated for a hash block.
Richard Parker
<[EMAIL PROTECTED]>
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: SCOTT COMPRESSION
Date: Sun, 07 Feb 1999 16:05:11 +0100
Eric W Braeden wrote:
>
> OK, but why don't we back up and ask what the
> raison d'etre for compression is in the first place?
>
> When generating high quality random numbers for use
> in seeds or keys it is common to take a file of
> some-what random system numbers and compress
> it before hashing with SHA-1 or MD5. Since compression
> is a reversible process, the total entropy remains the
> same.
Data compression is a reversible process, cryptographic
hashing is not...
> If the source file is compressible, you have
> increased the "density" of the entropy fed to the
> hash function, but what does this get you?
>
More entropy in a fixed space.
Most crypto keys have a fixed size, eg. 128 bits. The more
entropy you can cram into that space, the better.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: SCOTT COMPRESSION
Date: Sun, 07 Feb 1999 05:01:58 GMT
On Sun, 07 Feb 1999 16:05:11 +0100, in
<[EMAIL PROTECTED]>, in sci.crypt fungus
<[EMAIL PROTECTED]> wrote:
>[...]
>Data compression is a reversible process, cryptographic
>hashing is not...
While true, this is also a step beyond.
IF we process more "entropy" than the bits we produce as output, then
*no* hash is reversible, cryptographic or not, linear or not. It is
not the "cryptographic" or complex-transformation part which makes a
hash irreversible, it is the loss of information.
The "cryptographic" part refers to a presumed impossibility of finding
or constructing two different messages which produce the same hash
value.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "PAC" <[EMAIL PROTECTED]>
Crossposted-To: sci.philosophy.meta,sci.physics,sci.skeptic
Subject: Re: *** Where Does The Randomness Come From ?!? ***
Date: Sat, 6 Feb 1999 21:50:37 -0800
PAC wrote in message <79j0m4$2b7$[EMAIL PROTECTED]>...
>
>Colin Day wrote in message <[EMAIL PROTECTED]>...
>>PAC wrote:
>>
>>Math is a closed system? I think that Godel would dispute that (if he
>weren't
>>dead)
>
> Then I'll let my stuff stand until he rises again (>;
>
> This is more my side from an earlier thread
>
>I do not understand what you mean. If you mean that math is a complete
>>system, then that is not correct. Mathematics suffers from its own
>>indeterminancy (Chaitin's Theorem) just as formal axiomatic systems
>>do (Godel's Theorem) and computers programs do (Turing's Theorem).
>
> "Never a complete system even when dealing with simple infinity, but
>whatever answers that come to math will still be mathematical and resolved
>by itself and nothing beyond that. Otherwise leaving the ends open I
>suppose can imply that even the simplest variable can be non-mathematical
>being that it's never determined and the equations vary with the variables.
>It has internal relations that will always resolve things mathematically.
> But this does imply that math=universe being that the universe would be
>considered complete and math not, but this is obvious since math is not the
>all of reality, yet the most approachable // to the universe that we have.
>Absolute completeness would never be a part of math unless it encompassed
>all of reality."
This falls simply to the classification of �variables�. Unresolved
variables, i.e. Godel-type entities, imaginary numbers, infinity-related
problems, have always been intrinsically a part of math and it is assumes by
math that variables are such to be unresolved and therefore the final
results acceptably kept in stasis.
As long as any formation can be kept in the status of an unresolved
variable to be manipulated by math as a variable, then the internal
consistency of mathematics still applies. In other words, it is acceptable
within the internal consistency of mathematics to have variables pinpointed
as variables to be resolved mathematically by outside definitions, even if
those definitions are in themselves variables for larger definitions.
Unless you raise the argument that the use of variables goes against the
nature of math itself, which isn�t the implication, then their use is part
of the internal consistency of math: that unresolved entities can exist in
math as long as they are encapsulated in variable-type entities that have no
other purpose towards themselves but to be used mathematically. Variables
represent the same building blocks as simple numbers so no inconsistency
really give, being that a number also can�t be resolved except as it
remains, in an inverse way, also isolated (like a variable) to itself in the
internally related counting number �1" that is also manipulated by the rules
of mathematics.
No mathematical relations are being violated by these mathematically
manipulated encapsulations. This being more the opposite of Godel�s
intention, that an even bigger equation can encapsulate a smaller incomplete
variable in its own definition as that variable being a workable entity for
mathematical consistency for the bigger equation.
Phil C.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 7 Feb 1999 06:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Foiling 56-bit export limitations: example with 70-bit DES
Date: Sun, 07 Feb 1999 04:18:19 GMT
In article <79f7q9$252$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <79dtqr$vu1$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> [snip]
> > |The reasons why adding a previous encryption to the plaintext is less
> > |effective than adding post encryption to the ciphertext are, mainly:
>
> I believe we are close to understanding one another. I agree that adding a
> previous encryption to the plaintext is less effective than adding post
> encryption to the ciphertext.
Ok -- actually, much more effective, 2^56 times more effective for DES.
> What I haven't seen you address is doing BOTH
> (i.e., adding a previous encryption to the plaintext, AND ALSO adding THE SAME
> post encryption to the ciphertext).
>
In reverse yes I believe I did address that, when I note that one should add
uncertainty to the ciphertext first, as I wrote in my last e-mail. So, I think
this covers the first part of what you ask for above (before the "AND ALSO").
I also provided a URL for mcg-talk archives where "how" to add pre-encoding
(let's not call it encryption since there is no trusted secret-key) to the
plaintext is discussed and differentiated from "how" to add post-encoding
(ditto) to the ciphertext. This is *very* important, since plaintext
statistics is quite different from ciphertext statistics -- so, you SHOULD
NOT use the SAME method for both if you want to be efficient AND secure.
This last paragraph then answers in the negative the second part of what you
ask for above -- not the SAME.
> [snip]
> > First, let me discuss your assumption. You suppose that repeating the DES
key
> > for the same message would make the post-encryption in M-DES less secure. I
> > affirm that this is not the case, not even for the same repeated M-bit
> > unknown-key. Can you please tell me how you derived your assumption? Maybe
I
> > can more easily spot the difficulty if you tell me the steps you took -- of
> > course, using the protocol given in http://www.mcg.org.br/unicity.htm
>
> Ciphertext sent to alice, C1 --> DES(M) XOR unknown_key1
>
> Send same message again, with same DES key, C2 --> DES(M) XOR unknown_key2
>
> If Mike knows
STOP 1: No, not possible.
How does Mike know? How can he be sure that the DES key AND the message are
repeated if the unknown_key is different? Note: what DES key, what message?
The only thing Mike can see are two entirely DIFFERENT byte strings C1 and C2
-- and, what could he rationally deduce from two entirely different and
random-looking strings?
Further, since there are 2^56 DES keys and many more possible messages (say
2^8000 for a 1 Kb short message) then the possibility even of two DIFFERENT C1
and C2 ciphertexts hiding the SAME message and SAME key must not be a logical
assumption.
Note then that Mike has no M-DES protocol reason to even suspect that the DES
key and the message are the same -- unless the unknown-key is ALSO the same
and the whole thing is repeated, C1 = C2. But, in this case, he gains nothing
besides knowing there was a repetition since C1 XOR C1 = 0.
So, if Mike is able to do what you say for different unknown-keys, then its
roots must be off-protocol (a gun, perhaps?), hence off the present M-DES
protocol analysis. But, I agree to suppose that he does know (gun, collusion,
etc.) or just assumes it -- so that the example can proceed.
Thus, let me call it a "wild-guess-attack" -- Mike wild-guesses that behind
two fully different byte strings C1 and C2 hide the SAME message and the SAME
DES key, so he must assume that C1 and C2 use different unknown-keys.
>that you sent the same message again, with the same DES key,
> then Mike can derive: unkown_key1 XOR unknown_key2 == C1 XOR C2.
>If unkown_key1 and unknown_key2 are entries in a publically known table, Mike's
> search time may have just been drastically reduced, since he knows you used
> two of the entries that, when XORED together, are equal to C1 XOR C2.
>
STOP 2: No, nigh-impossible.
;-) Note that I was a bit "perverse" in my reply to you -- since I have been
repeating this point but without being able to convey it, so I tried a more
graphical way. Note that my previous text (that you quoted above) says
specifically: "-- of course, using the protocol given in
http://www.mcg.org.br/unicity.htm" ... thus, what does the M-DES protocol
say? Surely this question must be asked, since you cannot say M-DES has a
weakness if you provide Bob and Alice with a de-faced M-DES -- so, the given
M-DES rules MUST be followed. At the given URL, it is written:
|...every session which randomly chooses a DES key (from 2^56) should also
|randomly choose the unknown key (from 2^M) and vice-versa -- even for small
M.
Thus, the case where the SAME DES key but DIFFERENT unknown-keys are used
would not happen unless so randomly choosen -- for which your probability is
lower than 1 in 2^112. This is effectively zero, even in the Universe`s
lifetime. However, for the truly paranoic, it may be soothing to know that
"publically known tables" are not needed for M-DES, as I will comment in a
next posting, even in situations under WA terms -- but are useful in the
present exercize, where the basic ideas are discussed in the simplest
possible setting.
In summary, the "wild-guess-attack" (even if wild-guessed out of STOP 1) will
be blocked by a nigh-impossibility at STOP 2.
> This weakness disappears
This weakness effectively does not happen -- STOP 1 and STOP 2.
>if you a) use a block cipher for the post-encryption,
There is a subtle point here, which I believe was not properly stressed. Can
you trust that block cipher? Can you guarantee it has no back-doors? The
answer is of course NO in both cases.
However, can you trust an XOR to be an XOR? Can you guarantee it has no
back-doors? Clearly, YES in both cases.
Thus, M-DES uses a least-assumption model -- in order to provide least-risk.
And, XOR is enough -- as above -- so, why complicate the issues and run the
risk of an intentioanl back-door or a future bug that is found?
Further, in this presentation, I stress simplicity -- in order to bring out
the concepts. That is also why 70-bist was chosen, and not 184-bits or even
prefect-secrecy (but, they are also possible and I will post them next, after
this thread exercizes the main topics in a public-discussion).
> and/or b) do BOTH pre-encryption AND post-encryption.
Pre-encoding is excellent -- to provide hardened plaintext -- please see the
current thread in mcg-talk and the recent findings by Tony Bartoletti on this
topic (as I mentioned in my previous msg). However, as I proved, extra
security bits from the unknown-key must first go to the ciphertext encoding
-- THEN, after that number of bits is exhausted (64 in DES), go for
pre-encoding. Not before and not as remedy to a mallady -- there is no
security mallady that needs it, contrary to what you first supposed in the
wild-guess-attack (as above).
>
> [snip]
> > This is not the issue here -- and, as everyone that has tried (did you?)
> > knows, each case is different. Indeed, the US export law seems to be quite
> > different for Netscape with 40-bit encryption for export and PGP that
exports
> > strong encryption -- both, US companies and US-made software.
>
> Each case is different, but if you propose to export a cryptosystem that does
> DES encryption with a 56-bit key, and then post-encrypts with an M-bit key
> (with M not equal to zero), you WILL NOT get mass-market approval. It's
> called "multiple encryption."
No, it is NOT -- because the key in not known to anyone. It should not even
be called "encryption" -- it is just encoding or scrambling. The sender is
just destroying his ciphertext and not telling anyone how to recover it --
both Alice and the attacker are gropping in the dark. However, Alice has the
right to know the 56-bit key -- that much is allowed. And, that much is
enough ;-)
>
> PGP doesn't export strong encryption software, they skirt the law by
> "publishing a book" about strong encryption software. If you are willing to
> go that route, you don't need any tricky schemes to implement 70-bit DES
> while claiming to the government that it's really only 56-bit DES.
No, I was just (off-topic) commenting that current US export rules are being
"relaxed" (their terms) to agree with the US-proposed WA. And, the WA is much
more clear in this regard (I believe you agree with this part) and easily
classifies M-DES as export-free since there are only 56-bits of secret-key in
the protocol.
Further, my intention is not to break any law or cause any harm. Mind you, I
can export any key-length whatever to wherever -- right from where I am
(Brazil is NOT in WA). My motivation (besides the intellectual challenge) is
to show: (i)security and bit-length are not equivalent, (ii) there is a whole
set of new possibilities for smart-cards and contrived situations but with
strong security, (iii) WA does not reduce privacy so let`s talk about other
things, (iv) etc.
>
> > However, you must not ignore that the US-sponsored change in the Wassenaar
> > Arrangement was exactly targeted to harmonize different criteria, inland and
> > abroad. Some have applauded the intiative as "loosening up the US export
> > restrictions" ... others have decried the initiative as "depriving the world
> > of its privacy". However, as I commented in the thread "On leaving the
56-bit
> > export limitation" -- both sides are mislead. The number of bits in a
> > secret-key is NOT a good metric for the security of the corresponding
cipher.
> > Which was the motivation for this thread -- to show that, yes, keep only
> > 56-bits secret ... we can still bootstrap that to 70-bit or even more to
> > 120-bit ... or even more as I will post here in the next days.
>
> Multiple encryption regulations can be circumvented, but only if you can make
> the case that you don't and can't know that multiple encryption is taking
> place.
The unknown-key is not a secret-key because its knowledge is not necessary
before that exact protocol begins -- this sufficient to desqualify it as
encryption for export purposes. In fact, the unknown-key is part of the
message and anyone is entitled to keep received messages private unless a
legal warrant is properly issued. And, I guess I must wait until eternity`s
end to see a regulation that will try to define what people ignore (ie,
cannot know).
> For example, you could get export approval for software that encrypts
> a file with 56-bit DES, places it in an accessible location on the web, and
> securely transmits the DES key to Alice. Now, if Alice retrieves the file
> during an SSL session, the multiple encryption is not the fault of any of the
> software packages used, so the fact that this can happen does not, by itself,
> make any of them un-exportable.
>
This is a good example -- but the file was NOT safe en route to that web
location.
> [snip]
> > And, this cannot be stopped by any regulation because it does not really
> > depend on the cipher (eg, DES) or the export-free software that implements
> > it, but how it is used -- which is as diverse as there are users and
> > applications. Since, here, the brute-force strength derives not from the
> > secret-key strength (but, from "open ignorance"), there is nothing that the
> > export-free software would need to do differently -- since the export-free
> > software deals only with the secret-key part, which can be 56-bit without
> > compromising security.
>
> But how will you integrate the DES and the M-DES? How do you make software
> package X, which uses DES, use M-DES, instead?
>
First, as I said, anything-key can be exported from where I am, so I can make
M-DES into a full application and offer worldwide download -- note also that
even though M-DES is not in public-domain (see the notice in the MCG site) it
is certainly publicly-known. Thus, this entire question of "how to export
M-DES" is theoretical at best.
However, if everyone worldwide would right now forget all that I and everyone
else already wrote on this (so that I could not claim it is publicly known), I
would not write any books on it (a la PGP) and if I would start making it
available only from the US, still I could just offer a software for packet
scrambling with an unknown-key before transmission. And, a software for packet
blind-recovery on reception. Which could turn ANY DES software into M-DES.
> > This is the point here -- secret-key bit-length is not the deciding factor
to
> > grade the security of cipher systems. And, what is -- cannot be controlled
by
> > controlling cryptography.
>
> Regulations can't stop guys like us from writing and distributing such
> schemes, but they are very effective at stopping mainstream companies from
> doing so.
Agreed. But Linux is an example otherwise. As I commented, this is not an
attempt to break any law but a honest and sober clarification of what IS
important in cipher systems -- and, as M-DES showcases, it is certainly not
the key-length by itself.
> M-DES is too strong for U.S. export, as far as I can see. Maybe you could
> describe for me an example of a cryptosystem that uses M-DES, and the software
> packages that you would try to submit for export approval?
Will do, in next postings as this will be far too long here. My intention is
first to clear up the issues in open discussions before going into details --
simplicity IMO helps to bring out the details.
>
> Furthermore, I think that the scheme I proposed is an improvement on M-DES --
> if you are willing to slow Alice down by an additional factor of four, you
> can slow Mike down by an additional factor of four times the number of blocks
> in the message (both are still slowed in decrypting the first block by adding
> M bits to the effective keysize).
I suggest we discuss it when the full protocol is presented. The example
given and the case for 70-bits were just to exercize the issues. Far better
protocols are possible -- and, yes, what you say of using more than one DES
is also an alternative discussed in the paper. The idea of forcing one to use
information from all blocks has also its merits and Tony has suggested a
Global-XOR function for that -- but it cannot work with streaming data and is
easily stopped in a DoS attack that strips out just one block. Thus, there
are more to it than this 70-bit M=DES exercize intends to handle.
>
> [snip]
> > > I can name a weakness. The post-encryption is much easier to break if
> > > the same message is sent twice with the same DES key.
> >
> > Why? Please prove that sending the same message twice with the same DES key
> > makes **the post-encryption** easier to break -- where I accept that you
> > focus only on the M-DES post-encryption mechanism with the XOR choice (even
> > though XOR is just one example, from all possible choices such as RC4, RC5,
> > RPK, Twofish, etc).
> >
> > Please, consider also the two possible cases: equal unknown-key and
different
> > unknown-keys in each transmission -- if you think that changes anything.
> > Please, read also what the paper says about it.
>
> See above.
I guess we cleared that above now, in my reply. The point is not that the
wild-guess-attack could not exist -- in a quaint way it does exist -- but
that it could not happen. Perhaps, we are in agreement? BTW, the 1:2^112
probability against that wild-guess-attack gets even lower in other modes of
M-DES.
Comments?
Cheers,
Ed Gerck
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
