Cryptography-Digest Digest #595, Volume #13 Wed, 31 Jan 01 02:13:00 EST
Contents:
Re: Why Microsoft's Product Activation Stinks ("David Thompson")
Re: Differential Analysis ("David Thompson")
Re: On combining permutations and substitutions in encryption (Terry Ritter)
Re: Free Encryption Software ("George Peters")
Re: On combining permutations and substitutions in encryption (Terry Ritter)
Re: On combining permutations and substitutions in encryption (Terry Ritter)
Re: What do you do with broken crypto hardware? (Paul Rubin)
Re: Windows encryption: API and file system ("Douglas A. Gwyn")
Re: MIKE - alternative to SPEKE and PAK ("Michael Scott")
Shared key protocols ([EMAIL PROTECTED])
Re: Ciphertext Stealing question (John Savard)
More About Passwords (John Savard)
Re: Free Encryption Software (Splaat23)
Re: Algorithm M question (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "David Thompson" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Wed, 31 Jan 2001 04:40:46 GMT
(groups trimmed)
Richard Heathfield <[EMAIL PROTECTED]> wrote :
> [Sorry to reply to Joe's post when I'm really addressing the issues
> raised by Mr Szopa. Mr Szopa's article hasn't hit my newsfeed yet and
> may not do so for some time...]
>
Any ideas how the rest of us could get that to happen? <G>
--
- David.Thompson 1 now at worldnet.att.net
------------------------------
From: "David Thompson" <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Wed, 31 Jan 2001 04:41:34 GMT
Benjamin Goldberg <[EMAIL PROTECTED]> wrote :
> David Thompson wrote:
...
> > ++table[x^y][sbox[x]^sbox[y]]
> > if x and y are the two inputs, or
> > ++table[x][sbox[y]^sbox[y^x]]
> > if y is one input and x the input difference.
> > This is not the same as either your code
> > or Benjamin's as posted.
>
> Actually, I did have it right...
> See: <news:[EMAIL PROTECTED]>
...
> > ++table[x][sbox[x]^sbox[x^y]];
...
No, my second has sbox[y]. x is the difference
and y is an input. Your line tries to treat x
as both the difference and an input.
PS- Though in the source code (if ASCII)
there is only 1 bit difference. ('x' ^ 'y') == 1. <G>
--
- David.Thompson 1 now at worldnet.att.net
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 31 Jan 2001 04:49:09 GMT
On Tue, 30 Jan 2001 06:32:39 GMT, in
<betd6.8971$[EMAIL PROTECTED]>, in sci.crypt "Matt
Timmermans" <[EMAIL PROTECTED]> wrote:
>"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Really? Well, here is my first paragraph again, unchanged:
>> [...]
>> So, exactly what about the idea of addressing "currently-known and
>> most-likely" attacks sounds to you like "*any* attack"?
>
>Nothing at all. Your first paragraph, I conceded immediately. That's not
>the idea I quoted.
>
>I quoted this:
>
>> >"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
>> >news:[EMAIL PROTECTED]...
>> >> The obvious attack is on the RNG keyspace, the internal state. But we
>> >> can easily make ciphers with hundreds of thousands of bits of internal
>> >> state, which is far more than "large enough." When we do, we at least
>> >> have the opportunity of proving that any attack on the keyspace must
>> >> be impractical. There is nothing unreasonable about this.
>
>and was referring to the part where you explicitly said "any attack". You
>meant "any attack against the internal state",
That paragraph specifically refers to brute-force attacks on the
keyspace. That would include any attempt to simply step through the
internal state, along with any attempt to step through all possible
keys. It would not include, for example, some sort of interactive
chosen-RNG-state attack, where the output results influence the next
choice of RNG state. On the other hand, there might be something we
could say about that as well.
>and so did I:
>
>> <IYpd6.175740$[EMAIL PROTECTED]>, in sci.crypt "Matt
>> Timmermans" <[EMAIL PROTECTED]> wrote:
>> >[...]
>> >"Given this pt/ct pair, is it possible that the n'th
>> >bit of the RNG state is a 1"? is in NP if encryption is in P.
>
>And so, if P=NP, any DT cipher with bounded key size can be cracked in
>polynomial time. This is probably not a practical disadvantage, but it
>certainly is a hard barrier to provable security.
The particular issue is impracticality. The goal is to prove "no
non-interactive brute force attack can be practical." The proof
should be obvious.
>> "It is easy to have a prejudice that a cipher cannot be provably
>> secure. The most difficult part of this might be the implicit
>> understanding of "from any possible attack."
>
>"Prejudice" is a belief, and irrelevant, because you do not take *provable*
>security on faith -- you take it on proof. Please provide one.
Uh, how about "the state space is large enough." Q.E.D.
>I suspect
>the hard part will be in defining "any possible attack" in some strange way
>that suits your purposes.
A brute-force attack on keys hardly seems strange.
>> But most ciphers have a
>> range of currently-known and most-likely attacks, each of which might
>> be addressed and proven *impractical*, if not absolutely impossible."
>
>This is the part I didn't argue with. There is a big difference between
>proving security against a finite set of specific attacks and proving
>security against some set of attacks the gets bigger as people invent new
>algorithms. You keep saying that a cipher with bounded key size can be
>provably secure in the latter sense, and it's just not true Today -- "any
>possible attack against the RNG state" is one of these sets.
Sorry, but you have misinterpreted the intent, which I think was quite
clearly set out with a description of the Input and Output channels to
the RNG state.
"The information contained in RNG state has the specialized and
interesting property of being accessible from only two directions:
Input (the RNG is keyed), and Output (the RNG runs). Since Input
generally occurs at a particular time in a particular way (and, in a
real system, from a large random, not human chosen value), that end
should be fairly easy to secure *against practical attack*."
>So, I'm sorry -- DT can certainly be quite secure, but not provably so.
>Just like any other quality cipher.
My intent was set out in my first paragraph:
"It is easy to have a prejudice that a cipher cannot be provably
secure. The most difficult part of this might be the implicit
understanding of "from any possible attack." But most ciphers have a
range of currently-known and most-likely attacks, each of which might
be addressed and proven *impractical*, if not absolutely impossible."
Even if one cannot prove everything at once, that does not mean that
one cannot prove quite a lot, one thing at a time. Proofs may well
exist about types of attack, and the exercise of putting things in a
formal structure might be useful. It is also useful to think about
proving something *impractical* instead of actually *impossible*.
On the other hand, if one could get some sort of proof with respect to
the ability to limit the RNG state information exposed through the
combiner to the opponent, one might well have an interesting proof.
With respect to Dynamic Transposition, the vastly larger amount of RNG
information which performs a block permutation obviously cannot all be
revealed by that block in any way -- there simply is not enough
information in the permuted block to do that. And using any of that
information depends first on knowing the correct permutation, which is
also not exposed.
>> The information contained in RNG state has the specialized and
>> interesting property of being accessible from only two directions:
>> Input (the RNG is keyed), and Output (the RNG runs).
>
>I assume you just mean that the output is the only way he sees the state.
>If you've been assuming that the attacker doesn't know the RNG algorithm,
>then stop me now, because that would invalidate my arguments and your
>cipher.
Perhaps it would be best for someone who has not even heard of Retter
breaking MacLaren-Marsaglia (e.g., your recent thread "Algorithm M
question") to not teach about Kerckhoff.
>> Since Input
>> generally occurs at a particular time in a particular way (and, in a
>> real system, from a large random, not human chosen value), that end
>> should be fairly easy to secure *against practical attack*.
>
>Agreed again, as it does not imply provability.
I see no reason why proof could not be developed. Security proofs do
not have to be absolute statements of overall security; they may
instead say very specific small things about security in a provable
way.
>> >> I am unaware of any proofs in cryptography which would prevent one
>> >> from achieving a complete information hiding in a combiner or a
>> >> sequence or array of combiners.
>> [...]
>> Of course we cannot discuss the extent to which various combiner
>> structures hide RNG output, because those issues have not been
>> explored in the technical literature.
>
>It would help if you would simply define "complete information hiding". It
>would then be quite clear whether it was possible or not.
Answered in the original:
"We assume that the opponent has known plaintext, so any additive
combiner like XOR will immediately expose the ciphering sequence,
which then could be used to attack the RNG. But if we use a stronger
combiner -- for example, a keyed Latin square -- the ciphering
sequence is not so exposed. If we study this, we can show that some
RNG information is not hidden, but the most obvious information is
hidden. That is a clear improvement not anticipated in the
literature, so there is nothing to tell us how far that can go."
It should be obvious that XOR does not protect the confusion stream
against exposure from known-plaintext. A keyed Latin square provides
some protection, so it is also obvious that various amounts of such
protection are possible. What we do not know -- because it is not
addressed in the cryptographic literature -- is how far that process
can go.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "George Peters" <[EMAIL PROTECTED]>
Subject: Re: Free Encryption Software
Date: Tue, 30 Jan 2001 22:41:58 -0600
It is real, as you would have found if you had installed it rather than
deleted it. All of your questions and concerns would have answered if you
had investigated it futher.
"Splaat23" <[EMAIL PROTECTED]> wrote in message
news:957tgn$aje$[EMAIL PROTECTED]...
> Couldn't find any concise description of the algorithms used, so I
> deleted it. That .zip file has ~1000 files, a little much for me to
> wade through. Why is it using Enigma? Any particular reason I should
> use it? I really hope this message is real and not some stupid attempt
> at advertising...
>
> - Andrew
>
> In article <#MX$hlxiAHA.273@cpmsnbbsa07>,
> "George Peters" <[EMAIL PROTECTED]> wrote:
> > Greetings,
> >
> > An entire suite of encryption applications are available at
> > http://www.endecs.com/uenigma.zip . It contains two file systems,
> client
> > internet email, ftp and point to point communications and some source
> code.
> > Well worth the download.
> >
> > GP
> >
> >
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 31 Jan 2001 05:02:03 GMT
On Wed, 31 Jan 2001 04:49:09 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Terry Ritter) wrote:
>[...]
>Perhaps it would be best for someone who has not even heard of Retter
>breaking MacLaren-Marsaglia (e.g., your recent thread "Algorithm M
>question") to not teach about Kerckhoff.
Sorry, my mistake. My appologies to both.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On combining permutations and substitutions in encryption
Date: Wed, 31 Jan 2001 05:04:22 GMT
On Wed, 31 Jan 2001 05:02:03 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Terry Ritter) wrote:
>On Wed, 31 Jan 2001 04:49:09 GMT, in <[EMAIL PROTECTED]>,
>in sci.crypt [EMAIL PROTECTED] (Terry Ritter) wrote:
>
>Sorry, my mistake. My appologies to both.
And that would be "apologies."
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: What do you do with broken crypto hardware?
Date: 30 Jan 2001 21:09:56 -0800
[EMAIL PROTECTED] (Peter Gutmann) writes:
> In addition, erasing the cell doesn't necessarily mean the data is really gone.
> If you're really concerned I'd physically destroy the memory, and if you're
> really paranoid and worried about big-budget attackers, the crypto device it
> fed as well.
I heard back from the module manufacturer. They said in the one case
they had like that, they sent a representative to the customer site
and the customer destroyed the module in the rep's presence.
The manufacturer agreed, modules containing live keys should not be
sent anywhere. They are going to write instructions about how to
destroy a module in this situation.
Thanks for all the thoughts, everyone.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Windows encryption: API and file system
Date: Wed, 31 Jan 2001 05:40:05 GMT
"infinito.it" wrote:
> In fact, I remember an NSA* key ...
But you misremember it. The NSAKEY has been correctly explained
several times, including a couple of times in this newsgroup.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: MIKE - alternative to SPEKE and PAK
Date: Wed, 31 Jan 2001 05:45:46 GMT
"Thomas Wu" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Michael Scott" <[EMAIL PROTECTED]> writes:
> >
> > Actually not so easily fixed. Steve hasn't committed to his knowledge of
v
> > early enough, which allows an off-line dictionary attack as outlined in
Wu,
> > section 3.2.3, so....
> >
> > 3. Carol: A=3^a.4^x mod p Carol sends A to Steve
> > 4. Steve: B=v.3^b. u=4^r. Steve sends B and u to Carol.
> > 5. Carol calculates S=(B/4^x)^a.u^x. Steve calculates S=(A/v)^b.v^r
>
> But this is precisely Jablon's B- extension for converting a non-verifier
> based protocol into a verifier-based one; that's covered by his 1997
WETICE
> paper. If the server knows g^x and the client knows x, the server sends
> g^z (random z) and incorporates g^(zx) into the session key. The server
> can compute v^z, but the client is forced to compute (g^z)^x.
>
OK I didn't know that - although I should have. Thanks for the help and
hopefully continued interest. It really not as bad as 8 modexps, most
involve a fixed base, or may be calculated off-line. The on-line double
modexps benefit from "Shamir's trick" (HAC).
Mike Scott
> Obviously, one can use the existing A- and B- methods to augment MIKE
> (B-MIKE?), but that carries all the disadvantages of those extensions.
> For example, I count 8 modexps in the protocol now. I'll keep looking
> to see if there's a better solution for this problem.
>
> Tom
>
> > Mike Scott
>
> --
> Tom Wu * finger -l [EMAIL PROTECTED] for PGP
key *
> E-mail: [EMAIL PROTECTED] "Those who would give up their freedoms
in
> Phone: (650) 723-1565 exchange for security deserve
neither."
> http://www-cs-students.stanford.edu/~tjw/
http://srp.stanford.edu/srp/
------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Shared key protocols
Date: Wed, 31 Jan 2001 00:01:32 -0600
Hi. I'm trying to find the best algorithm to use for shared key
communications. I've done some research on Diffie-Helman, and there are
parts of the protocol that don't make sense. Are there any other Shared
key protocols that might also possibly be used? Where can I find out
more information about the Diffie-Helman implementations and other
shared key protocols? Any help is greatly apprecited. Thanks.
-George
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Ciphertext Stealing question
Date: Wed, 31 Jan 2001 06:19:11 GMT
On Wed, 31 Jan 2001 04:02:09 GMT, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote, in part:
>Otherwise, simply using the value 0 as
>IV will work fine.
Not if you're planning to use the same key for more than one message.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: More About Passwords
Date: Wed, 31 Jan 2001 06:16:33 GMT
Although some time back, I posted some ideas about a password protocol
designed to resist guessing attacks, I made a recent post about a
protocol without that property, but with other desirable ones: I was
wondering if something existing resembled it.
What would a protocol look like, though, that was secure against all
guessing attacks? I noted in the earlier post that it seemed to me
that there would have to be a secure computer involved in the process.
The later post also had a secure computer involved, but dealt with the
case where the connection to the secure computer couldn't be trusted.
Here, now, is what seems to me to be the natural way to combine these
things; again, I don't think I've come up with anything original here.
The user has only a password, and doesn't even have a public-private
key pair.
The secure computer has a table with user IDs, a salt value for each
user, and the first-order hash of the user's password. Also, it has a
public-private key pair of its own.
The host computer is assumed to be secure computationally, but the
files it keeps may have been read. It has a table with user IDs, and
the hash of the combination of the first-order hash of the user's
password and the salt value for the user.
Making an effective protocol out of this will require the use of EKE
or similar techniques, and EKE is the simplest one to explain.
Step 1: User sends user ID to host computer.
Step 2: Host computer generates a nonce public/private key pair, and a
random value. It sends the random value, and the nonce public key, to
the secure computer, encrypted with the secure computer's public key.
Also, the user ID is sent along with this, unencrypted.
Step 3: The secure computer generates a message which is sent to the
host computer for relay to the user's computer. First, it generates
its own random value. Then, it decrypts the message from the host
computer. The message to be sent to the user's computer is encrypted
conventionally with the first-order hash of the user's password, using
a method where changing a single bit of the message's plaintext
affects every bit in the encrypted message. It contains the two random
values, the user's salt value, and the host computer's nonce public
key. Note that the nonce public key must not be 'obvious' in a
brute-force search: so we are using EKE at this step.
Step 4: The host computer, recieving the message from the host
computer, retains a copy of that message, and sends it to the user's
computer.
Step 5: The user's computer prompts the user for the password.
The hash of the password is used to decode the recieved message.
Using the hash of the password, and the salt value from the message, a
hash is taken to arrive at the value retained on the host computer.
The user's computer generates a random value.
The original encrypted message is then subjected to the following:
- it is encrypted using the random value generated by the user's
computer
- it is encrypted using the random value from the host computer;
- it is subsequently encrypted using the value retained on the host
computer ( hash( hash( password ) + salt ) );
- it is hashed
- the random value generated by the user's computer is concatenated
with it
- it is finally encrypted using the host computer's nonce public key
The result is sent to the host computer.
Step 6: The host computer verifies that the result is correct, by
decrypting it, obtaining the user's computer's random value, and using
that value to duplicate the calculations leading up to the hash
encrypted within the result.
Adding a random value at each stage ensures that we never see the same
message encrypted with two different keys. At one point, I explicitly
note that an encryption method is needed that completely confounds the
plaintext, but that is also true of the encryptions guided by public
keys.
Step 5, of course, could probably safely omit some of its steps.
Also, in addition to the random value generated by the user's
computer, the random value generated by the security computer could be
sent, so that a value computed from all three random values could be
used as a session key.
One could even do a little coin-flipping here: the host computer's
random value, generated first, and seen by the other two computers,
could be the hash of another random value; and the session key could
be generated from this original random value combined with the other
two random values; the user's computer could verify the original
random value, and that would ensure none of the three computers could
control the session key.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: Free Encryption Software
Date: Wed, 31 Jan 2001 06:36:01 GMT
No, I'm fairly sure my concerns would not be addressed, because there
is no section addressing "Why this is secure?" Could you please
elaborate on this, for the benefit of the group, so that they can here
an overview of the algorithms used? Or at least point me to the
specific file in that archive and I might download it again to look.
"Real" in this context does not mean real software, as I'm sure that
yours is, especially from the complexity of the documentation and its
sheer size. "Real" means real security, as opposed to fake security.
- Andrew
In article <unkXjC0iAHA.272@cpmsnbbsa09>,
"George Peters" <[EMAIL PROTECTED]> wrote:
> It is real, as you would have found if you had installed it rather
than
> deleted it. All of your questions and concerns would have answered
if you
> had investigated it futher.
>
> "Splaat23" <[EMAIL PROTECTED]> wrote in message
> news:957tgn$aje$[EMAIL PROTECTED]...
> > Couldn't find any concise description of the algorithms used, so I
> > deleted it. That .zip file has ~1000 files, a little much for me to
> > wade through. Why is it using Enigma? Any particular reason I should
> > use it? I really hope this message is real and not some stupid
attempt
> > at advertising...
> >
> > - Andrew
> >
> > In article <#MX$hlxiAHA.273@cpmsnbbsa07>,
> > "George Peters" <[EMAIL PROTECTED]> wrote:
> > > Greetings,
> > >
> > > An entire suite of encryption applications are available at
> > > http://www.endecs.com/uenigma.zip . It contains two file systems,
> > client
> > > internet email, ftp and point to point communications and some
source
> > code.
> > > Well worth the download.
> > >
> > > GP
> > >
> > >
> >
> >
> > Sent via Deja.com
> > http://www.deja.com/
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Algorithm M question
Date: Wed, 31 Jan 2001 06:59:46 GMT
Terry Ritter wrote:
>
> On Wed, 31 Jan 2001 00:41:30 GMT, in
> <[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote:
>
> >[...]
> >A fast, statistically good generator, like MT, might be
> >usable for both PRNGs -- provided of course, that MT with scrambled
> >order outputs is secure.
>
> http://www.io.com/~ritter/RES/COMBCORR.HTM#Retter84
> http://www.io.com/~ritter/RES/COMBCORR.HTM#Retter85
] "It is the purpose of this paper to show that the algorithm can be
] attacked by searching for the key to one of its generators, while
] ignoring the other." "Therefore, the amount of computation required to
] break the combined keystream generator is only about twice what would
] be required if one of the input generators had been used to generate
] the keystream directly."
Does this attack still work if both prngA and prngB use the same MT
state? Also, it does not say anything about the amount of known
keystream needed -- it only says "twice the amount of computation"
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
